Generated on Wed Apr 29 2015 11:51:41 for GGL-4.1.2 by doxygen 1.8.3.1
Data Structures | Public Types | Public Member Functions | Static Public Member Functions | Static Protected Member Functions
sgm::Graph_Interface Class Referenceabstract

Interface of graphs for graph matching. More...

#include <Graph_Interface.hh>

Inheritance diagram for sgm::Graph_Interface:
Inheritance graph
[legend]

Data Structures

class  Edge_iterator
 
class  EdgeDescriptor
 
class  OutEdge_iterator
 

Public Types

typedef std::vector< size_t > CompLabel
 
typedef size_t IndexType
 Type for global indicex of nodes in the graph. More...
 

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
 
virtual std::string getNodeLabel (const IndexType &i) const =0
 
virtual size_t getNodeNumber (void) const =0
 
virtual OutEdge_iterator getOutEdgesBegin (const IndexType &i) const =0
 
virtual OutEdge_iterator getOutEdgesEnd (const IndexType &i) const =0
 
virtual bool operator!= (const Graph_Interface &toCompare) const
 
virtual bool operator== (const Graph_Interface &toCompare) const
 
virtual ~Graph_Interface ()
 Destruction. More...
 

Static Public Member Functions

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

Static Protected Member Functions

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

Detailed Description

     The class is used as an abstract interface to allow for a generic
     interface of the search algorithms in the library.
     It describes an undirected labeled graph.
Author
Martin Mann (c) 2008 http://www.bioinf.uni-freiburg.de/~mmann/

Definition at line 19 of file Graph_Interface.hh.

Member Typedef Documentation

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

Definition at line 284 of file Graph_Interface.hh.

Definition at line 23 of file Graph_Interface.hh.

Constructor & Destructor Documentation

virtual sgm::Graph_Interface::~Graph_Interface ( )
inlinevirtual

Definition at line 209 of file Graph_Interface.hh.

Member Function Documentation

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

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
gthe graph to check for connected components
compIDthe container to store the component ID information within
Returns
the number of connected components within g
virtual Edge_iterator sgm::Graph_Interface::getEdgesBegin ( const IndexType i,
const IndexType j 
) const
virtual

Access to the label of a specified edge

Parameters
ithe index of the first end node of interest
jthe 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
virtual

Access to the label of a specified edge

Parameters
ithe index of the first end node of interest
jthe 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 std::string sgm::Graph_Interface::getNodeLabel ( const IndexType i) const
pure virtual
virtual size_t sgm::Graph_Interface::getNodeNumber ( void  ) const
pure virtual
virtual OutEdge_iterator sgm::Graph_Interface::getOutEdgesBegin ( const IndexType i) const
pure virtual

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

Parameters
ithe index of the node of interest
Returns
the iterator to the first edge within the adjacency of i

Implemented in ggl::RightSidePattern, ggl::LeftSidePattern, sgm::Graph_boostV_p< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >, sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >, sgm::SubGraph, and ggl::chem::ClassIDGraph.

virtual OutEdge_iterator sgm::Graph_Interface::getOutEdgesEnd ( const IndexType i) const
pure virtual

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

Parameters
ithe index of the node of interest
Returns
the iterator the end of the adjacency iteration of i

Implemented in ggl::RightSidePattern, ggl::LeftSidePattern, sgm::Graph_boostV_p< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >, sgm::Graph_boost< GRAPH, NODE_LABEL_PROPERTY, EDGE_LABEL_PROPERTY, NODE_INDEX_PROPERTY >, sgm::SubGraph, and ggl::chem::ClassIDGraph.

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

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
thegraph to screen
curNodethe node to start the search from
compIDthe container to store the component ID information within
labelthe 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
virtual

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
toComparethe Graph_Interface to compare to
Returns
true if both graph interfaces are different
virtual bool sgm::Graph_Interface::operator== ( const Graph_Interface toCompare) const
virtual

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
toComparethe Graph_Interface to compare to
Returns
true if both graph interfaces are equal

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