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.
typedef std::map< Graph_vertex, Sub_graph_vertex >	Sub_vertex_map
	A map from the graph vertices to the sub graph vertices.

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

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

Modifiers
void	add_vertex (Graph_vertex v)
	Add a vertex to the Sub-graph.
void	add_vertex_with_induced_edges (Graph_vertex v)
	Add a vertex and its induced edges.
void	add_induced_edges (Graph_vertex v)
	Scans the neighborhood of v in the sub-graph and adds any induced edges.
void	add_edge (Graph_edge e)
	Add an edge to the sub-graph (adds the vertices if necessary)
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)
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).
unsigned	compute_current_score () const
	Return the score of the current sub-graph (weights of the connected-components)

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

template<class Graph>

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

template<class Graph>

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()

template<class Graph>

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]

template<class Graph>

void add_edge ( Graph_edge e )

inline

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

◆ add_edge() [2/2]

template<class Graph>

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()

template<class Graph>

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()

template<class Graph>

void add_induced_edges ( Graph_vertex v )

inline

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

◆ add_vertex()

template<class Graph>

void add_vertex ( Graph_vertex v )

inline

Add a vertex to the Sub-graph.

◆ add_vertex_with_induced_edges()

template<class Graph>

void add_vertex_with_induced_edges ( Graph_vertex v )

inline

Add a vertex and its induced edges.

◆ compute_current_score()

template<class Graph>

unsigned compute_current_score ( ) const

inline

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

◆ get_adjacent_vertices()

template<class Graph>

template<class OutputIterator>

void get_adjacent_vertices	(	Graph_vertex	u,
		OutputIterator	out )

inline

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

◆ get_connected_components()

template<class Graph>

template<class OutputIterator>

unsigned get_connected_components ( OutputIterator out ) const

inline

Return the connected components of the sub-graph.

◆ get_degree()

template<class Graph>

unsigned get_degree ( const Graph_vertex & v )

inline

Returns the degree of v in the sub-graph.

◆ get_edges()

template<class Graph>

template<class OutputIterator>

void get_edges ( OutputIterator out ) const

inline

Returns the edges of the sub-graph.

◆ get_max_degree()

template<class Graph>

unsigned get_max_degree ( )

inline

Return the max degree of the sub-graph.

◆ get_vertices()

template<class Graph>

template<class OutputIterator>

void get_vertices ( OutputIterator out ) const

inline

Returns the vertices of the sub-graph.

◆ has_vertex()

template<class Graph>

bool has_vertex ( Graph_vertex v ) const

inline

Check if the sub-graph contains a certain vertex.

◆ num_vertices()

template<class Graph>

unsigned num_vertices ( )

inline

Returns the number of vertices in the Sub graph.

◆ operator[]()

template<class Graph>

Vertex_property & operator[] ( Graph_vertex v )

inline

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

Classes

Public Types

Operator

Accessors

Modifiers

Detailed Description

Class Documentation

◆ SBL::CADS::T_Sub_graph::Sub_vertex_property

Member Typedef Documentation

◆ Sub_graph_type

◆ Sub_vertex_map

Member Function Documentation

◆ add_connected_component()

◆ add_edge() [1/2]

◆ add_edge() [2/2]

◆ add_free_edges()

◆ add_induced_edges()

◆ add_vertex()

◆ add_vertex_with_induced_edges()

◆ compute_current_score()

◆ get_adjacent_vertices()

◆ get_connected_components()

◆ get_degree()

◆ get_edges()

◆ get_max_degree()

◆ get_vertices()

◆ has_vertex()

◆ num_vertices()

◆ operator[]()