T_Sub_graph< Graph > Class Template Reference

A superstructure over the Graph used to represent non-induced sub-graphs. More...

#include <Graph_superstructures.hpp>

Classes
struct	Sub_vertex_property
	Sub graph vertex property (wee link it to the vertex it represents in the Graph) More...

Public Types
typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, Sub_vertex_property, Edge_weight_property >	Sub_graph_type
	The basic sub-graph type is defined using boost::graph. More...
typedef std::map< Graph_vertex, Sub_graph_vertex >	Sub_vertex_map
	A map from the graph vertices to the sub graph vertices. More...

Constructors
	T_Sub_graph (Graph &g)
	T_Sub_graph (Graph *g=NULL)
	T_Sub_graph (const Sub_graph &other)

Operator
Vertex_property &	operator[] (Graph_vertex v)
	Overloading the [] operator allows us to operate only on the original graph vertices. More...

Accessors
unsigned	num_vertices ()
	Returns the number of vertices in the Sub graph. More...
bool	has_vertex (Graph_vertex v) const
	Check if the sub-graph contains a certain vertex. More...
unsigned	get_degree (const Graph_vertex &v)
	Returns the degree of v in the sub-graph. More...
template<class OutputIterator >
void	get_adjacent_vertices (Graph_vertex u, OutputIterator out)
	Returns the adjacent vertices of u in the sub-graph. More...
void	add_connected_component (const std::vector< Graph_vertex > &cc)
	Add a connected component (given as a vector of vertices) More...
template<class OutputIterator >
void	get_vertices (OutputIterator out) const
	Returns the vertices of the sub-graph. More...
template<class OutputIterator >
void	get_edges (OutputIterator out) const
	Returns the edges of the sub-graph. More...
template<class OutputIterator >
unsigned	get_connected_components (OutputIterator out) const
	Return the connected components of the sub-graph. More...
unsigned	get_max_degree ()
	Return the max degree of the sub-graph. More...

Modifiers
void	add_vertex (Graph_vertex v)
	Add a vertex to the Sub-graph. More...
void	add_vertex_with_induced_edges (Graph_vertex v)
	Add a vertex and its induced edges. More...
void	add_induced_edges (Graph_vertex v)
	Scans the neighborhood of v in the sub-graph and adds any induced edges. More...
void	add_edge (Graph_edge e)
	Add an edge to the sub-graph (adds the vertices if necessary) More...
void	add_edge (Graph_vertex u, Graph_vertex v)
	Adds an edge between u and v in the sub-graph (assumes it exists in the graph) More...
void	add_free_edges ()
	Add the "free" edges (the ones in the original graph that haven't been considered and do not fuse two connected components in the sub-graph). More...
unsigned	compute_current_score () const
	Return the score of the current sub-graph (weights of the connected-components) More...
int	compute_current_diameter () const

Detailed Description

template<class Graph>
class SBL::CADS::T_Sub_graph< Graph >

A superstructure over the Graph used to represent non-induced sub-graphs.

Template Parameters

Graph

Representation of a graph.

---

Class Documentation

SBL::CADS::T_Sub_graph::Sub_vertex_property

struct SBL::CADS::T_Sub_graph::Sub_vertex_property

template<class Graph>
struct SBL::CADS::T_Sub_graph< Graph >::Sub_vertex_property

Sub graph vertex property (wee link it to the vertex it represents in the Graph)

Member Typedef Documentation

Sub_graph_type

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Sub_vertex_property, Edge_weight_property> Sub_graph_type

The basic sub-graph type is defined using boost::graph.

Sub_vertex_map

typedef std::map<Graph_vertex, Sub_graph_vertex> Sub_vertex_map

A map from the graph vertices to the sub graph vertices.

Member Function Documentation

add_connected_component()

void add_connected_component ( const std::vector< Graph_vertex > &  cc )

inline

Add a connected component (given as a vector of vertices)

add_edge() [1/2]

void add_edge ( Graph_edge  e )

inline

Add an edge to the sub-graph (adds the vertices if necessary)

add_edge() [2/2]

void add_edge ( Graph_vertex  u, Graph_vertex  v  )

inline

Adds an edge between u and v in the sub-graph (assumes it exists in the graph)

add_free_edges()

void add_free_edges ( )

inline

Add the "free" edges (the ones in the original graph that haven't been considered and do not fuse two connected components in the sub-graph).

add_induced_edges()

void add_induced_edges ( Graph_vertex  v )

inline

Scans the neighborhood of v in the sub-graph and adds any induced edges.

add_vertex()

void add_vertex ( Graph_vertex  v )

inline

Add a vertex to the Sub-graph.

add_vertex_with_induced_edges()

void add_vertex_with_induced_edges ( Graph_vertex  v )

inline

Add a vertex and its induced edges.

compute_current_score()

unsigned compute_current_score ( ) const

inline

Return the score of the current sub-graph (weights of the connected-components)

get_adjacent_vertices()

void get_adjacent_vertices ( Graph_vertex  u, OutputIterator  out  )

inline

Returns the adjacent vertices of u in the sub-graph.

get_connected_components()

unsigned get_connected_components ( OutputIterator  out ) const

inline

Return the connected components of the sub-graph.

get_degree()

unsigned get_degree ( const Graph_vertex &  v )

inline

Returns the degree of v in the sub-graph.

get_edges()

void get_edges ( OutputIterator  out ) const

inline

Returns the edges of the sub-graph.

get_max_degree()

unsigned get_max_degree ( )

inline

Return the max degree of the sub-graph.

get_vertices()

void get_vertices ( OutputIterator  out ) const

inline

Returns the vertices of the sub-graph.

has_vertex()

bool has_vertex ( Graph_vertex  v ) const

inline

Check if the sub-graph contains a certain vertex.

num_vertices()

unsigned num_vertices ( )

inline

Returns the number of vertices in the Sub graph.

operator[]()

Vertex_property& operator[] ( Graph_vertex  v )

inline

Overloading the [] operator allows us to operate only on the original graph vertices.