#include <SubGraph.hh>

Inheritance diagram for sgm::SubGraphPattern:

Public Types
typedef std::vector< size_t >	CompLabel

typedef std::vector < Match_Constraint * >	ConstraintVec
	container of matching constraints More...

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

typedef std::vector< IndexType >	NodeList
	Type that defines a node index subset to be present in a subgraph. More...

Public Member Functions
virtual const ConstraintVec &	getConstraints (void) const

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

virtual size_t	getNodeNumber (void) const

virtual OutEdge_iterator	getOutEdgesBegin (const IndexType &i) const

virtual OutEdge_iterator	getOutEdgesEnd (const IndexType &i) const

virtual const Graph_Interface &	getPatternGraph (void) const

virtual const std::string *	getUsedWildcard (void) const

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

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

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

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

	SubGraphPattern (const Graph_Interface &fullGraph, const NodeList &nodeList)

	SubGraphPattern (const Graph_Interface &fullGraph, const CompLabel &compLabel, const size_t subGraphLabel)

	SubGraphPattern (const Graph_Interface &fullGraph, const NodeList &nodeList, const ConstraintVec &matchConstraints)

	SubGraphPattern (const Graph_Interface &fullGraph, const CompLabel &compLabel, const size_t subGraphLabel, const ConstraintVec &matchConstraints)

	SubGraphPattern (const Graph_Interface &fullGraph, const NodeList &nodeList, const std::string &wildcardToUse)

	SubGraphPattern (const Graph_Interface &fullGraph, const CompLabel &compLabel, const size_t subGraphLabel, const std::string &wildcardToUse)

	SubGraphPattern (const Graph_Interface &fullGraph, const NodeList &nodeList, const ConstraintVec &matchConstraints, const std::string &wildcardToUse)

	SubGraphPattern (const Graph_Interface &fullGraph, const CompLabel &compLabel, const size_t subGraphLabel, const ConstraintVec &matchConstraints, const std::string &wildcardToUse)

virtual	~SubGraphPattern ()
	Destruction of the subgraph. More...

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

static ConstraintVec	copyConstraintVec (const ConstraintVec &toCopy)

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

static void	remapConstraints (const ConstraintVec &originalConstraints, const Match &full2sub, ConstraintVec &remappedConstraints)

Protected Attributes
Match	full2sub

const Graph_Interface &	fullGraph
	The original graph this object is a subgraph of. More...

const Graph_Interface *	graph
	the graph to be represented as a pattern More...

ConstraintVec	matchConstraints
	the additional match constraints to be fulfilled by each match More...

NodeList	nodeList
	The subset of node indices of fullGraph represented by this graph. More...

const std::string *	usedWildcard
	the wildcard string to be used for matching More...

Static Protected Attributes
static const IndexType	NOT_MAPPED_INDEX

Detailed Description

A Pattern that represents only a subset of the nodes of a graph and all edges between these nodes by wrapping the source graph and some additional constraints

Author: Martin Mann - 2010 - http://www.bioinf.uni-freiburg.de/~mmann/

Definition at line 192 of file SubGraph.hh.

Member Typedef Documentation

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

inherited

Definition at line 284 of file Graph_Interface.hh.

typedef std::vector< Match_Constraint* > sgm::Pattern_Interface::ConstraintVec

inherited

Definition at line 129 of file Pattern.hh.

typedef size_t sgm::Graph_Interface::IndexType

inherited

Definition at line 23 of file Graph_Interface.hh.

typedef std::vector< IndexType > sgm::SubGraph::NodeList

inherited

Definition at line 22 of file SubGraph.hh.

Constructor & Destructor Documentation

sgm::SubGraphPattern::SubGraphPattern	(	const Graph_Interface &	fullGraph,
		const NodeList &	nodeList
	)

Construction of a subgraph from explicit node list.

Parameters

fullGraph	the original graph this object should be a subgraph of
nodeList	the subset of node indices present in the subgraph

sgm::SubGraphPattern::SubGraphPattern	(	const Graph_Interface &	fullGraph,
		const CompLabel &	compLabel,
		const size_t	subGraphLabel
	)

Construction of a subgraph from a component labeling.

Parameters

fullGraph	the original graph this object should be a subgraph of
compLabel	component labeling of the fullGraph
subGraphLabel	the label in compLabel that defines the nodes of this subgraph

sgm::SubGraphPattern::SubGraphPattern	(	const Graph_Interface &	fullGraph,
		const NodeList &	nodeList,
		const ConstraintVec &	matchConstraints
	)

Construction of a subgraph from explicit node list.

Parameters

fullGraph	the original graph this object should be a subgraph of
nodeList	the subset of node indices present in the subgraph
matchConstraints	the additional matching constraints to be fulfilled for this pattern, NOTE: indices have to correspond to the initial fullGraph instance and to be compatible with the subgraph definition !

sgm::SubGraphPattern::SubGraphPattern	(	const Graph_Interface &	fullGraph,
		const CompLabel &	compLabel,
		const size_t	subGraphLabel,
		const ConstraintVec &	matchConstraints
	)

Construction of a subgraph from a component labeling.

Parameters

fullGraph	the original graph this object should be a subgraph of
compLabel	component labeling of the fullGraph
subGraphLabel	the label in compLabel that defines the nodes of this subgraph
matchConstraints	the additional matching constraints to be fulfilled for this pattern, NOTE: indices have to correspond to the initial fullGraph instance and to be compatible with the subgraph definition !

sgm::SubGraphPattern::SubGraphPattern	(	const Graph_Interface &	fullGraph,
		const NodeList &	nodeList,
		const std::string &	wildcardToUse
	)

Construction of a subgraph from explicit node list.

Parameters

fullGraph	the original graph this object should be a subgraph of
nodeList	the subset of node indices present in the subgraph
wildcardToUse	the wildcard to use for matching

sgm::SubGraphPattern::SubGraphPattern	(	const Graph_Interface &	fullGraph,
		const CompLabel &	compLabel,
		const size_t	subGraphLabel,
		const std::string &	wildcardToUse
	)

Construction of a subgraph from a component labeling.

Parameters

fullGraph	the original graph this object should be a subgraph of
compLabel	component labeling of the fullGraph
subGraphLabel	the label in compLabel that defines the nodes of this subgraph
wildcardToUse	the wildcard to use for matching

sgm::SubGraphPattern::SubGraphPattern	(	const Graph_Interface &	fullGraph,
		const NodeList &	nodeList,
		const ConstraintVec &	matchConstraints,
		const std::string &	wildcardToUse
	)

Construction of a subgraph from explicit node list.

Parameters

fullGraph	the original graph this object should be a subgraph of
nodeList	the subset of node indices present in the subgraph
matchConstraints	the additional matching constraints to be fulfilled for this pattern, NOTE: indices have to correspond to the initial fullGraph instance and to be compatible with the subgraph definition !
wildcardToUse	the wildcard to use for matching

sgm::SubGraphPattern::SubGraphPattern	(	const Graph_Interface &	fullGraph,
		const CompLabel &	compLabel,
		const size_t	subGraphLabel,
		const ConstraintVec &	matchConstraints,
		const std::string &	wildcardToUse
	)

Construction of a subgraph from a component labeling.

Parameters

fullGraph	the original graph this object should be a subgraph of
compLabel	component labeling of the fullGraph
subGraphLabel	the label in compLabel that defines the nodes of this subgraph
matchConstraints	the additional matching constraints to be fulfilled for this pattern, NOTE: indices have to correspond to the initial fullGraph instance and to be compatible with the subgraph definition !
wildcardToUse	the wildcard to use for matching

virtual sgm::SubGraphPattern::~SubGraphPattern ( )

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

static ConstraintVec sgm::Pattern::copyConstraintVec ( const ConstraintVec & toCopy )

staticinherited

Does a deep copy of the given constraint vector

Parameters

toCopy the ConstraintVec instance to copy

Returns: the deep copy of the given vector of MatchConstraints

virtual const ConstraintVec& sgm::Pattern::getConstraints ( void ) const

virtualinherited

Access to the matching constraints that have to be fulfilled by a match of this pattern graph

Returns: the matching constraints to validate

Implements sgm::Pattern_Interface.

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

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

virtualinherited

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.

virtual size_t sgm::SubGraph::getNodeNumber ( void ) const

virtualinherited

Access to the number of nodes of the subgraph

Returns: the overall node number

Implements sgm::Graph_Interface.

virtual OutEdge_iterator sgm::SubGraph::getOutEdgesBegin ( const IndexType & i ) const

virtualinherited

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.

virtual OutEdge_iterator sgm::SubGraph::getOutEdgesEnd ( const IndexType & i ) const

virtualinherited

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.

virtual const Graph_Interface& sgm::Pattern::getPatternGraph ( void ) const

virtualinherited

Access to the pattern graph to be matched

Returns: the pattern graph

Implements sgm::Pattern_Interface.

virtual const std::string* sgm::Pattern::getUsedWildcard ( void ) const

virtualinherited

Access to the wildcard to be used when matching this pattern onto some other graph.

Returns: the wildcard string to be used for edge and node labels, or NULL if no wildcard should be applied

Implements sgm::Pattern_Interface.

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::Pattern_Interface::operator!= ( const Pattern_Interface & toCompare ) const

virtualinherited

Inequality comparison

Parameters

toCompare the Pattern to compare to

Returns: true if both describe the different patterns

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::Pattern_Interface::operator== ( const Pattern_Interface & toCompare ) const

virtualinherited

Equality comparison

Parameters

toCompare the Pattern to compare to

Returns: true if both describe the same pattern

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

static void sgm::SubGraphPattern::remapConstraints	(	const ConstraintVec &	originalConstraints,
		const Match &	full2sub,
		ConstraintVec &	remappedConstraints
	)

staticprotected

Does the reindexing of the nodes within the given match constraints onto the new indices within the subgraph, where the index mapping is given by full2sub.

Parameters

originalConstraints	the matching constraints to be remapped
full2sub	the mapping of the indices used in the given constraints onto nodes within the subgraph.
remappedConstraints	the container that will hold the remapped matching constraints

Field Documentation

Match sgm::SubGraph::full2sub

protectedinherited

Mapping of global indices of fullGraph to local indices of this subgraph

Definition at line 114 of file SubGraph.hh.

const Graph_Interface& sgm::SubGraph::fullGraph

protectedinherited

Definition at line 107 of file SubGraph.hh.

const Graph_Interface* sgm::Pattern::graph

protectedinherited

Definition at line 193 of file Pattern.hh.

ConstraintVec sgm::Pattern::matchConstraints

protectedinherited

Definition at line 196 of file Pattern.hh.

NodeList sgm::SubGraph::nodeList

protectedinherited

Definition at line 110 of file SubGraph.hh.

const IndexType sgm::SubGraph::NOT_MAPPED_INDEX

staticprotectedinherited

Definition at line 104 of file SubGraph.hh.

const std::string* sgm::Pattern::usedWildcard

protectedinherited

Definition at line 199 of file Pattern.hh.

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

src/sgm/SubGraph.hh

Public Types

Public Member Functions

Static Public Member Functions

Static Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Field Documentation