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_typegetGeodesicTree_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_typegetGeodesicTree_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
 

Definition at line 455 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
 

Definition at line 446 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
 

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 402 of file GraphConceptAlgorithms.h.

Referenced by fold().

template<class Graph>
map< int , int > Graphs::getDistances_in const Graph graph,
int  init_v
 

Compute distances to the vertex init_v.

Definition at line 211 of file GraphConceptAlgorithms.h.

template<class Graph>
map< int , int > Graphs::getDistances_out const Graph graph,
int  init_v
 

Compute distances from the vertex init_v.

Definition at line 153 of file GraphConceptAlgorithms.h.

template<class Graph>
map< int , typename Graph::edge_type > Graphs::getGeodesicTree_in const Graph graph,
int  init_v
 

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 31 of file GraphConceptAlgorithms.h.

template<class Graph>
map< int , typename Graph::edge_type > Graphs::getGeodesicTree_out const Graph graph,
int  init_v
 

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 93 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
 

Revert the folding.

Definition at line 496 of file GraphConceptAlgorithms.h.

template<class VertexType, class EdgeType>
ostream& Graphs::operator<< ostream &  os,
const GraphConcept< VertexType, EdgeType > &  G
 

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
 

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

Definition at line 269 of file GraphConceptAlgorithms.h.

template<class edge_type>
void Graphs::reduce_path int  init_vertex,
list< edge_type > &  path
 

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

Definition at line 572 of file GraphConceptAlgorithms.h.

template<class LabelledGraph, class ConstIterator>
int Graphs::trace const LabelledGraph &  LG,
int  init_v,
ConstIterator  B,
ConstIterator  E
 

Definition at line 292 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
 

Definition at line 331 of file GraphConceptAlgorithms.h.

template<class LabelledGraph, class FoldDetailsConstIterator>
void Graphs::unfold LabelledGraph &  G,
FoldDetailsConstIterator  B,
FoldDetailsConstIterator  E
 

Revert the folding.

Definition at line 478 of file GraphConceptAlgorithms.h.


Generated on Sun Dec 3 10:59:07 2006 for CRyptography And Groups (CRAG) by  doxygen 1.4.6