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.

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

Generated on Mon Sep 26 18:43:53 2011 for CRyptography And Groups (CRAG) by  doxygen 1.6.1