Graphs Namespace Reference

Classes
class	GraphConceptRep
	Representation class for graph types. More...
class	GraphConcept
	The main class for graph types. More...
struct	FoldDetails
Functions
template<class VertexType , class EdgeType >
ostream &	operator<< (ostream &os, const GraphConcept< VertexType, EdgeType > &G)
	Output the graph.
template<class Graph >
map< int, typename Graph::edge_type >	getGeodesicTree_in (const Graph &graph, int init_v)
	Compute directed geodesic tree "inward" to the vertex init_v.
template<class Graph >
map< int, typename Graph::edge_type >	getGeodesicTree_out (const Graph &graph, int init_v)
	Compute geodesic directed tree starting the vertex init_v.
template<class Graph >
map< int, int >	getDistances_out (const Graph &graph, int init_v)
	Compute distances from the vertex init_v.
template<class Graph >
map< int, int >	getDistances_in (const Graph &graph, int init_v)
	Compute distances to the vertex init_v.
template<class edge_type >
pair< bool, list< edge_type > >	readoffGeodesicTree (const map< int, edge_type > &tree, int v)
	Function finds a path in the tree starting from the state st_num to the root.
template<class LabelledGraph , class ConstIterator >
int	trace (const LabelledGraph &LG, int init_v, ConstIterator B, ConstIterator E)
template<class LabelledGraph , class ConstIterator >
pair< bool, list< typename LabelledGraph::edge_type > >	trace_path (const LabelledGraph &LG, int init_v, ConstIterator B, ConstIterator E)
template<class LabelledGraph >
void	fold (LabelledGraph &G, set< int > candidates, list< FoldDetails< typename LabelledGraph::vertex_type, typename LabelledGraph::edge_type > > *details=NULL)
	Fold a labelled graph. To aplly this function the graph edges must have theLabel defined.
template<class LabelledGraph >
void	fold (const LabelledGraph &G, int candidate, list< FoldDetails< typename LabelledGraph::vertex_type, typename LabelledGraph::edge_type > > *details=NULL)
template<class LabelledGraph >
void	fold (const LabelledGraph &G, list< FoldDetails< typename LabelledGraph::vertex_type, typename LabelledGraph::edge_type > > *details=NULL)
template<class LabelledGraph , class FoldDetailsConstIterator >
void	unfold (LabelledGraph &G, FoldDetailsConstIterator B, FoldDetailsConstIterator E)
	Revert the folding.
template<class LabelledGraph , class FoldDetailsConstIterator >
void	liftup (const LabelledGraph &graph, int init_vertex, list< typename LabelledGraph::edge_type > &path, FoldDetailsConstIterator B, FoldDetailsConstIterator E)
	Revert the folding.
template<class edge_type >
void	reduce_path (int init_vertex, list< edge_type > &path)
	Reduce a path (remove all pairs of consequent inverse edges).

---

Detailed Description

EdgeType must support: e.inverse( v ), where v is the number of the origin

---

Function Documentation

template<class LabelledGraph >

void Graphs::fold	(	const LabelledGraph &	G,
		list< FoldDetails< typename LabelledGraph::vertex_type, typename LabelledGraph::edge_type > > *	details = NULL
	)			[inline]

Definition at line 457 of file GraphConceptAlgorithms.h.

References fold().

template<class LabelledGraph >

void Graphs::fold	(	const LabelledGraph &	G,
		int	candidate,
		list< FoldDetails< typename LabelledGraph::vertex_type, typename LabelledGraph::edge_type > > *	details = NULL
	)			[inline]

Definition at line 448 of file GraphConceptAlgorithms.h.

References fold().

template<class LabelledGraph >

void Graphs::fold	(	LabelledGraph &	G,
		set< int >	candidates,
		list< FoldDetails< typename LabelledGraph::vertex_type, typename LabelledGraph::edge_type > > *	details = NULL
	)			[inline]

Fold a labelled graph. To aplly this function the graph edges must have theLabel defined.

The graph is not folded if there is a vertex and two different edges leaving it equally labelled. In that event "fold" pinches end-points of these edges.

Definition at line 404 of file GraphConceptAlgorithms.h.

Referenced by fold().

template<class Graph >

map< int , int > Graphs::getDistances_in	(	const Graph &	graph,
		int	init_v
	)			[inline]

Compute distances to the vertex init_v.

Definition at line 213 of file GraphConceptAlgorithms.h.

template<class Graph >

map< int , int > Graphs::getDistances_out	(	const Graph &	graph,
		int	init_v
	)			[inline]

Compute distances from the vertex init_v.

Definition at line 155 of file GraphConceptAlgorithms.h.

template<class Graph >

map< int , typename Graph::edge_type > Graphs::getGeodesicTree_in	(	const Graph &	graph,
		int	init_v
	)			[inline]

Compute directed geodesic tree "inward" to the vertex init_v.

Returns a list of edges that form a a geodesic subtree of a graph directed to the vertex init_vert. If init_vert is reachable from V if and only if result[V] is defined.

Definition at line 33 of file GraphConceptAlgorithms.h.

template<class Graph >

map< int , typename Graph::edge_type > Graphs::getGeodesicTree_out	(	const Graph &	graph,
		int	init_v
	)			[inline]

Compute geodesic directed tree starting the vertex init_v.

Returns a list of edges that form a a geodesic subtree of a graph directed to the vertex init_vert. If init_vert is reachable from V if and only if result[V] is defined.

Definition at line 95 of file GraphConceptAlgorithms.h.

template<class LabelledGraph , class FoldDetailsConstIterator >

void Graphs::liftup	(	const LabelledGraph &	graph,
		int	init_vertex,
		list< typename LabelledGraph::edge_type > &	path,
		FoldDetailsConstIterator	B,
		FoldDetailsConstIterator	E
	)			[inline]

Revert the folding.

Definition at line 498 of file GraphConceptAlgorithms.h.

References reduce_path().

template<class VertexType , class EdgeType >

ostream& Graphs::operator<<	(	ostream &	os,
		const GraphConcept< VertexType, EdgeType > &	G
	)			[inline]

Output the graph.

To use this function a function ostream& operator << ( ostream& os , const EdgeType& E ) must be defined. Otherwise you will get an error when linking.

Definition at line 346 of file GraphConcept.h.

template<class edge_type >

pair< bool , list< edge_type > > Graphs::readoffGeodesicTree	(	const map< int, edge_type > &	tree,
		int	v
	)			[inline]

Function finds a path in the tree starting from the state st_num to the root.

Definition at line 271 of file GraphConceptAlgorithms.h.

template<class edge_type >

void Graphs::reduce_path	(	int	init_vertex,
		list< edge_type > &	path
	)			[inline]

Reduce a path (remove all pairs of consequent inverse edges).

Definition at line 574 of file GraphConceptAlgorithms.h.

Referenced by liftup().

template<class LabelledGraph , class ConstIterator >

int Graphs::trace	(	const LabelledGraph &	LG,
		int	init_v,
		ConstIterator	B,
		ConstIterator	E
	)			[inline]

Definition at line 294 of file GraphConceptAlgorithms.h.

template<class LabelledGraph , class ConstIterator >

pair< bool , list< typename LabelledGraph::edge_type > > Graphs::trace_path	(	const LabelledGraph &	LG,
		int	init_v,
		ConstIterator	B,
		ConstIterator	E
	)			[inline]

Definition at line 333 of file GraphConceptAlgorithms.h.

template<class LabelledGraph , class FoldDetailsConstIterator >

void Graphs::unfold	(	LabelledGraph &	G,
		FoldDetailsConstIterator	B,
		FoldDetailsConstIterator	E
	)			[inline]

Revert the folding.

Definition at line 480 of file GraphConceptAlgorithms.h.