Basic Graph Utilities
The same group on the Doxygen site.
- group Basic Graph Utilities
Simple basic graph utilities.
This group contains some simple basic graph utilities.
Classes
Class |
Description |
|---|---|
Class to copy a digraph. |
|
Class to copy a graph. |
|
Class to copy a bipartite graph. |
|
Iterator for iterating on parallel arcs connecting the same nodes. |
|
Iterator for iterating on parallel edges connecting the same nodes. |
|
Dynamic arc look-up between given endpoints. |
|
Fast arc look-up between given endpoints. |
|
Fast look-up of all arcs between given endpoints. |
Other classes of its headers
Class |
Description |
|---|---|
Dummy type to make it easier to create invalid iterators. |
Functions and other members
-
template< typename Graph , typename Item >
inline int countItems( const Graph & g ) Function to count the items in a graph.
This function counts the items (nodes, arcs etc.) in a graph. The complexity of the function is linear because it iterates on all of the items.
-
template< typename Graph >
inline int countNodes( const Graph & g ) Function to count the nodes in the graph.
This function counts the nodes in the graph. The complexity of the function is O(n), but for some graph structures it is specialized to run in O(1).
Note
If the graph contains a
nodeNum()member function and aNodeNumTagtag then this function calls directly the member function to query the cardinality of the node set.
-
template< typename Graph >
inline int countRedNodes( const Graph & g ) Function to count the red nodes in the graph.
This function counts the red nodes in the graph. The complexity of the function is O(n) but for some graph structures it is specialized to run in O(1).
If the graph contains a redNum() member function and a NodeNumTag tag then this function calls directly the member function to query the cardinality of the node set.
-
template< typename Graph >
inline int countBlueNodes( const Graph & g ) Function to count the blue nodes in the graph.
This function counts the blue nodes in the graph. The complexity of the function is O(n) but for some graph structures it is specialized to run in O(1).
If the graph contains a blueNum() member function and a NodeNumTag tag then this function calls directly the member function to query the cardinality of the node set.
-
template< typename Graph >
inline int countArcs( const Graph & g ) Function to count the arcs in the graph.
This function counts the arcs in the graph. The complexity of the function is O(m), but for some graph structures it is specialized to run in O(1).
Note
If the graph contains a
arcNum()member function and aArcNumTagtag then this function calls directly the member function to query the cardinality of the arc set.
-
template< typename Graph >
inline int countEdges( const Graph & g ) Function to count the edges in the graph.
This function counts the edges in the graph. The complexity of the function is O(m), but for some graph structures it is specialized to run in O(1).
Note
If the graph contains a
edgeNum()member function and aEdgeNumTagtag then this function calls directly the member function to query the cardinality of the edge set.
-
template< typename Graph , typename DegIt >
inline int countNodeDegree(
)
-
template< typename Graph >
inline int countOutArcs(
) Function to count the number of the out-arcs from node
n.This function counts the number of the out-arcs from node
nin the graphg.
-
template< typename Graph >
inline int countInArcs(
) Function to count the number of the in-arcs to node
n.This function counts the number of the in-arcs to node
nin the graphg.
-
template< typename Graph >
inline int countIncEdges(
) Function to count the number of the inc-edges to node
n.This function counts the number of the inc-edges to node
nin the undirected graphg.
-
template< typename GR >
bool undirected( const GR & g ) Check whether a graph is undirected.
This function returns
trueif the given graph is undirected.
-
template< typename From , typename To >
DigraphCopy< From , To > digraphCopy(
) Copy a digraph to another digraph.
This function copies a digraph to another digraph. The complete usage of it is detailed in the DigraphCopy class, but a short example shows a basic work:
digraphCopy( src , trg ).nodeRef( nr ).arcCrossRef( acr ).run();
After the copy the
nrmap will contain the mapping from the nodes of thefromdigraph to the nodes of thetodigraph andacrwill contain the mapping from the arcs of thetodigraph to the arcs of thefromdigraph.See also
-
template< typename From , typename To >
GraphCopy< From , To > graphCopy(
) Copy a graph to another graph.
This function copies a graph to another graph. The complete usage of it is detailed in the GraphCopy class, but a short example shows a basic work:
graphCopy( src , trg ).nodeRef( nr ).edgeCrossRef( ecr ).run();
After the copy the
nrmap will contain the mapping from the nodes of thefromgraph to the nodes of thetograph andecrwill contain the mapping from the edges of thetograph to the edges of thefromgraph.See also
-
template< typename From , typename To >
BpGraphCopy< From , To > bpGraphCopy(
) Copy a graph to another graph.
This function copies a graph to another graph. The complete usage of it is detailed in the BpGraphCopy class, but a short example shows a basic work:
graphCopy( src , trg ).nodeRef( nr ).edgeCrossRef( ecr ).run();
After the copy the
nrmap will contain the mapping from the nodes of thefromgraph to the nodes of thetograph andecrwill contain the mapping from the edges of thetograph to the edges of thefromgraph.See also
-
template< typename Graph >
inline Graph::Arc findArc(
) Find an arc between two nodes of a digraph.
This function finds an arc from node
uto nodevin the digraphg.If
previs INVALID (this is the default value), then it finds the first arc fromutov. Otherwise it looks for the next arc fromutovafterprev.
Thus you can iterate through each arc from
utovas it follows.for( Arc e = findArc( g , u , v ) ; e != INVALID ; e = findArc( g , u , v , e ) ) { ... }
See also
See also
Note
ConArcIt provides iterator interface for the same functionality.
- Returns:
The found arc or INVALID if there is no such an arc.
-
template< typename Graph >
inline Graph::Edge findEdge(
) Find an edge between two nodes of a graph.
This function finds an edge from node
uto nodevin graphg. If nodeuand nodevis equal then each loop edge will be enumerated once.If
previs INVALID (this is the default value), then it finds the first edge fromutov. Otherwise it looks for the next edge fromutovafterprev.
Thus you can iterate through each edge between
uandvas it follows.for( Edge e = findEdge( g , u , v ) ; e != INVALID ; e = findEdge( g , u , v , e ) ) { ... }
See also
Note
ConEdgeIt provides iterator interface for the same functionality.
- Returns:
The found edge or INVALID if there is no such an edge.
-
DIGRAPH_TYPEDEFS(Digraph)
Create convenience typedefs for the digraph types and iterators.
This
#definecreates convenient type definitions for the following types ofDigraph:Node,NodeIt,Arc,ArcIt,InArcIt,OutArcIt,BoolNodeMap,IntNodeMap,DoubleNodeMap,BoolArcMap,IntArcMap,DoubleArcMap.Note
If the graph type is a dependent type, ie. the graph type depend on a template parameter, then use
TEMPLATE_DIGRAPH_TYPEDEFS()macro.
-
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph)
Create convenience typedefs for the digraph types and iterators.
See also
Note
Use this macro, if the graph type is a dependent type, ie. the graph type depend on a template parameter.
-
GRAPH_TYPEDEFS(Graph)
Create convenience typedefs for the graph types and iterators.
This
#definecreates the same convenient type definitions as defined by DIGRAPH_TYPEDEFS(Graph) and six more, namely it createsEdge,EdgeIt,IncEdgeIt,BoolEdgeMap,IntEdgeMap,DoubleEdgeMap.Note
If the graph type is a dependent type, ie. the graph type depend on a template parameter, then use
TEMPLATE_GRAPH_TYPEDEFS()macro.
-
TEMPLATE_GRAPH_TYPEDEFS(Graph)
Create convenience typedefs for the graph types and iterators.
See also
Note
Use this macro, if the graph type is a dependent type, ie. the graph type depend on a template parameter.
-
BPGRAPH_TYPEDEFS(BpGraph)
Create convenience typedefs for the bipartite graph types and iterators.
This
#definecreates the same convenient type definitions as defined by GRAPH_TYPEDEFS(BpGraph) and ten more, namely it createsRedNode,RedNodeIt,BoolRedNodeMap,IntRedNodeMap,DoubleRedNodeMap,BlueNode,BlueNodeIt,BoolBlueNodeMap,IntBlueNodeMap,DoubleBlueNodeMap.Note
If the graph type is a dependent type, ie. the graph type depend on a template parameter, then use
TEMPLATE_BPGRAPH_TYPEDEFS()macro.
-
TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph)
Create convenience typedefs for the bipartite graph types and iterators.
See also
Note
Use this macro, if the graph type is a dependent type, ie. the graph type depend on a template parameter.