Graph_Interface wrapper for boost graphs. More...

#include <Graph_boost.hh>

Inheritance diagram for sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >:

Data Structures
class	EdgeDescriptor

Public Types
typedef std::vector< size_t >	CompLabel

typedef size_t	IndexType
	Type for global indicex of nodes in the graph. More...

typedef GRAPH	InternalBoostGraph

Public Member Functions
virtual Edge_iterator	getEdgesBegin (const IndexType &i, const IndexType &j) const

virtual Edge_iterator	getEdgesEnd (const IndexType &i, const IndexType &j) const

const GRAPH &	getGraph (void) const

virtual std::string	getNodeLabel (const IndexType &i) const

virtual size_t	getNodeNumber (void) const

virtual OutEdge_iterator	getOutEdgesBegin (const IndexType &i) const

virtual OutEdge_iterator	getOutEdgesEnd (const IndexType &i) const

	Graph_boost (const GRAPH &graph)

virtual bool	operator!= (const Graph_Interface &toCompare) const

virtual bool	operator== (const Graph_Interface &toCompare) const

virtual	~Graph_boost ()
	Destruction. More...

Static Public Member Functions
static size_t	connectedComponents (const Graph_Interface &g, CompLabel &compID)

static size_t	countRealNodeNumber (const GRAPH &graph)

static void	indexGraph (GRAPH &graph)

Protected Types
typedef boost::property_map < GRAPH, EDGE_LABEL_PROPERTY > ::const_type	EdgeLabelMap

typedef boost::property_map < GRAPH, NODE_INDEX_PROPERTY > ::const_type	NodeIndexMap

Static Protected Member Functions
static void	labelAdjacentNodes (const Graph_Interface &g, const size_t curNode, CompLabel &compID, const size_t label)

Protected Attributes
EdgeLabelMap	edgeLabelMap
	edge label access More...

const GRAPH &	graph
	the graph to map More...

const size_t	graphSize
	the number of nodes of graph More...

NodeIndexMap	nodeIndexMap
	node index access More...

boost::property_map< GRAPH, NODE_LABEL_PROPERTY > ::const_type	nodeLabelMap
	node label access More...

Detailed Description

template<class GRAPH, typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>
class sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >

     This class implements the Graph interface of a labeled undirected
     graph. It is used as an interface of an undirected labeled
     boost graph to the sub graph matching algorithms of the sgm library.
     The template parameter GRAPH represents the type of the
     boost graph to use. The type names NODE_LABEL_PROPERTY and
     EDGE_LABEL_PROPERTY are used to generate the node and edge labels of
     the  graph. The type name NODE_INDEX_PROPERTY is used to derive the
     corresponding local node index for a certain vertex in covered graph.

Author: Martin Mann (c) 2008 http://www.bioinf.uni-freiburg.de/~mmann/

Definition at line 47 of file Graph_boost.hh.

Member Typedef Documentation

typedef std::vector<size_t> sgm::Graph_Interface::CompLabel

inherited

Definition at line 284 of file Graph_Interface.hh.

template<class GRAPH , typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>

typedef boost::property_map<GRAPH, EDGE_LABEL_PROPERTY>::const_type sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >::EdgeLabelMap

protected

Definition at line 64 of file Graph_boost.hh.

typedef size_t sgm::Graph_Interface::IndexType

inherited

Definition at line 23 of file Graph_Interface.hh.

template<class GRAPH , typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>

typedef GRAPH sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >::InternalBoostGraph

Definition at line 70 of file Graph_boost.hh.

template<class GRAPH , typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>

typedef boost::property_map<GRAPH, NODE_INDEX_PROPERTY>::const_type sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >::NodeIndexMap

protected

Definition at line 56 of file Graph_boost.hh.

Constructor & Destructor Documentation

template<class GRAPH , typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>

sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >::Graph_boost ( const GRAPH & graph )

Construction of the interface graph.

Parameters

graph the boost graph to use as internal data structure

template<class GRAPH , typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>

virtual sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >::~Graph_boost ( )

virtual

Member Function Documentation

static size_t sgm::Graph_Interface::connectedComponents	(	const Graph_Interface &	g,
		CompLabel &	compID
	)

staticinherited

Computes the connected components of a given graph. It stores the connected component ID of each node within the provided container and returns the number of components.

Parameters

g	the graph to check for connected components
compID	the container to store the component ID information within

Returns: the number of connected components within g

template<class GRAPH , typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>

static size_t sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >::countRealNodeNumber ( const GRAPH & graph )

static

Counts the number of nodes a boost graph represents since the number returned by boost::num_vertices might not be correct, e.g. for boost::filtered_graph instances.

Parameters

graph the graph to check

Returns: the graph's number of nodes

virtual Edge_iterator sgm::Graph_Interface::getEdgesBegin	(	const IndexType &	i,
		const IndexType &	j
	)		const

virtualinherited

Access to the label of a specified edge

Parameters

i	the index of the first end node of interest
j	the index of the second end node of interest

Returns: the edge iterator pointing to the first edge between node i and j or to getEdgesEnd(i,j) if no edge exists

virtual Edge_iterator sgm::Graph_Interface::getEdgesEnd	(	const IndexType &	i,
		const IndexType &	j
	)		const

virtualinherited

Access to the label of a specified edge

Parameters

i	the index of the first end node of interest
j	the index of the second end node of interest

Returns: the edge iterator pointing to the first edge between node i and j or to getEdgesEnd(i,j) if no edge exists

template<class GRAPH , typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>

const GRAPH& sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >::getGraph ( void ) const

Access to the internal GRAPH object

Returns: a refence to the graph object

template<class GRAPH , typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>

virtual std::string sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >::getNodeLabel ( const IndexType & i ) const

virtual

Access to the label of a specified node

Parameters

i	the index of the node of interest

Returns: a string representation of the node label

Implements sgm::Graph_Interface.

template<class GRAPH , typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>

virtual size_t sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >::getNodeNumber ( void ) const

virtual

Access to the number of nodes of the graph

Returns: the overall node number

Implements sgm::Graph_Interface.

template<class GRAPH , typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>

virtual OutEdge_iterator sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >::getOutEdgesBegin ( const IndexType & i ) const

virtual

Access to iteration begin for the edge in the adjacency list of a specified node

Parameters

i	the index of the node of interest

Returns: the iterator to the first edge within the adjacency of i

Implements sgm::Graph_Interface.

template<class GRAPH , typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>

virtual OutEdge_iterator sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >::getOutEdgesEnd ( const IndexType & i ) const

virtual

Access to iteration end for the edge in the adjacency list of a specified node

Parameters

i	the index of the node of interest

Returns: the iterator the end of the adjacency iteration of i

Implements sgm::Graph_Interface.

template<class GRAPH , typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>

static void sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >::indexGraph ( GRAPH & graph )

static

Static member function that allows for the indexing of the nodes in the graph. It opens the property map for NODE_INDEX_PROPERTY and sets an index with [0,num_vertices(g)) along the ordering defined by the vertex iterators. Therefore, this function can be used to set the necessary local indexes before creating a Graph_boost object. NOTE : The property map is NOT CONSTRUCTED has to be already part of the GRAPH definition! It is ONLY FILLED!

static void sgm::Graph_Interface::labelAdjacentNodes	(	const Graph_Interface &	g,
		const size_t	curNode,
		CompLabel &	compID,
		const size_t	label
	)

staticprotectedinherited

Performs a depths-first-search labeling of all accessible nodes starting from curNode within g. The reached nodes are labeled with the given label in the component ID container compID

Parameters

the	graph to screen
curNode	the node to start the search from
compID	the container to store the component ID information within
label	the component ID to be used for all nodes of the connected component reachable from curNode

virtual bool sgm::Graph_Interface::operator!= ( const Graph_Interface & toCompare ) const

virtualinherited

Interface inequality comparison : NOTE : this function checks whether the interfaces of two graphs are identical or not, i.e. nodes with same index are equal and the order of adjacent edges is the same. This function performs NO GRAPH ISOMORPHISM !!! Thus, slight changes in the node order etc. will result in a non-equal interface!

Parameters

toCompare the Graph_Interface to compare to

Returns: true if both graph interfaces are different

virtual bool sgm::Graph_Interface::operator== ( const Graph_Interface & toCompare ) const

virtualinherited

Interface equality comparison : NOTE : this function checks whether the interfaces of two graphs are identical or not, i.e. nodes with same index are equal and the order of adjacent edges is the same. This function performs NO GRAPH ISOMORPHISM !!! Thus, slight changes in the node order etc. will result in a non-equal interface!

Parameters

toCompare the Graph_Interface to compare to

Returns: true if both graph interfaces are equal

Field Documentation

template<class GRAPH , typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>

EdgeLabelMap sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >::edgeLabelMap

protected

Definition at line 66 of file Graph_boost.hh.

template<class GRAPH , typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>

const GRAPH& sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >::graph

protected

Definition at line 52 of file Graph_boost.hh.

template<class GRAPH , typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>

const size_t sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >::graphSize

protected

Definition at line 54 of file Graph_boost.hh.

template<class GRAPH , typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>

NodeIndexMap sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >::nodeIndexMap

protected

Definition at line 58 of file Graph_boost.hh.

template<class GRAPH , typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>

boost::property_map<GRAPH, NODE_LABEL_PROPERTY>::const_type sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >::nodeLabelMap

protected

Definition at line 62 of file Graph_boost.hh.

The documentation for this class was generated from the following file:

src/sgm/Graph_boost.hh

Data Structures

Public Types

Public Member Functions

Static Public Member Functions

Protected Types

Static Protected Member Functions

Protected Attributes

Detailed Description

template<class GRAPH, typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t> class sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Field Documentation

template<class GRAPH, typename NODE_LABEL_PROPERTY = boost::vertex_name_t, typename EDGE_LABEL_PROPERTY = boost::edge_name_t, typename NODE_INDEX_PROPERTY = boost::vertex_index_t>
class sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >