Basic Graph Utilities
[Tools and Utilities]

Detailed Description

This group describes some simple basic graph utilities.


Classes
class	ConEdgeIt< _Graph >
	Iterator for iterating on edges connected the same nodes. More...
class	ConUEdgeIt< _Graph >
	Iterator for iterating on uedges connected the same nodes. More...
class	GraphCopy< To, From >
	Class to copy a graph. More...
class	UGraphCopy< To, From >
	Class to copy an undirected graph. More...
class	BpUGraphCopy< To, From >
	Class to copy a bipartite undirected graph. More...
class	DynEdgeLookUp< G >
	Dynamic edge look up between given endpoints. More...
class	EdgeLookUp< G >
	Fast edge look up between given endpoints. More...
class	AllEdgeLookUp< G >
	Fast look up of all edges between given endpoints. More...
class	MapIt< Graph, Item, Map >
class	ConstMapIt< Graph, Item, Map >
class	FilterMapIt< Graph, Item, Map >
	Iterator for maps which filters items by the values. More...
Files
file	graph_utils.h
	Graph utilities.
file	map_iterator.h
	Iterators on the maps.
Defines
#define	GRAPH_TYPEDEFS(Graph)
	Creates convenience typedefs for the graph types and iterators.
#define	UGRAPH_TYPEDEFS(Graph)
	Creates convenience typedefs for the undirected graph types and iterators.
#define	BPUGRAPH_TYPEDEFS(Graph)
	Creates convenience typedefs for the bipartite undirected graph types and iterators.
Functions
template<typename Graph , typename Item >
int	countItems (const Graph &g)
	Function to count the items in the graph.
template<typename Graph >
int	countNodes (const Graph &g)
	Function to count the nodes in the graph.
template<typename Graph >
int	countANodes (const Graph &g)
	Function to count the anodes in the graph.
template<typename Graph >
int	countBNodes (const Graph &g)
	Function to count the bnodes in the graph.
template<typename Graph >
int	countEdges (const Graph &g)
	Function to count the edges in the graph.
template<typename Graph >
int	countUEdges (const Graph &g)
	Function to count the undirected edges in the graph.
template<typename Graph >
int	countOutEdges (const Graph &_g, const typename Graph::Node &_n)
	Function to count the number of the out-edges from node `n`.
template<typename Graph >
int	countInEdges (const Graph &_g, const typename Graph::Node &_n)
	Function to count the number of the in-edges to node `n`.
template<typename Graph >
int	countIncEdges (const Graph &_g, const typename Graph::Node &_n)
	Function to count the number of the inc-edges to node `n`.
template<typename Graph >
Graph::Edge	findEdge (const Graph &g, typename Graph::Node u, typename Graph::Node v, typename Graph::Edge prev=INVALID)
	Finds an edge between two nodes of a graph.
template<typename Graph >
Graph::UEdge	findUEdge (const Graph &g, typename Graph::Node u, typename Graph::Node v, typename Graph::UEdge p=INVALID)
	Finds an uedge between two nodes of a graph.
template<typename To , typename From , typename ItemIt , typename Ref >
void	copyMap (To &to, const From &from, ItemIt it, const Ref &ref)
	Copy a map.
template<typename To , typename From , typename ItemIt >
void	copyMap (To &to, const From &from, ItemIt it)
	Copy the from map to the to map.
template<typename To , typename From >
GraphCopy< To, From >	copyGraph (To &to, const From &from)
	Copy a graph to another graph.
template<typename To , typename From >
UGraphCopy< To, From >	copyUGraph (To &to, const From &from)
	Copy an undirected graph to another graph.
template<typename To , typename From >
BpUGraphCopy< To, From >	copyBpUGraph (To &to, const From &from)
	Copy a bipartite undirected graph to another graph.

Define Documentation

#define GRAPH_TYPEDEFS ( Graph )

This #define creates convenience typedefs for the following types of Graph: Node, NodeIt, Edge, EdgeIt, InEdgeIt, OutEdgeIt

Note:

If G it a template parameter, it should be used in this way.

       GRAPH_TYPEDEFS(typename G);

Warning:: There are no typedefs for the graph maps because of the lack of template typedefs in C++.

#define UGRAPH_TYPEDEFS ( Graph )

Value:

GRAPH_TYPEDEFS(Graph);                          \
    typedef Graph:: UEdge   UEdge;                      \
    typedef Graph:: UEdgeIt UEdgeIt;                    \
    typedef Graph:: IncEdgeIt   IncEdgeIt

This #define creates the same convenience typedefs as defined by GRAPH_TYPEDEFS(Graph) and three more, namely it creates UEdge, UEdgeIt, IncEdgeIt,

Note:

If G it a template parameter, it should be used in this way.

       UGRAPH_TYPEDEFS(typename G);

Warning:: There are no typedefs for the graph maps because of the lack of template typedefs in C++.

#define BPUGRAPH_TYPEDEFS ( Graph )

Value:

UGRAPH_TYPEDEFS(Graph);             \
    typedef Graph::ANode ANode;             \
    typedef Graph::BNode BNode;             \
    typedef Graph::ANodeIt ANodeIt;         \
    typedef Graph::BNodeIt BNodeIt

This #define creates the same convenience typedefs as defined by UGRAPH_TYPEDEFS(Graph) and two more, namely it creates ANodeIt, BNodeIt,

Note:

If G it a template parameter, it should be used in this way.

       BPUGRAPH_TYPEDEFS(typename G);

Warning:: There are no typedefs for the graph maps because of the lack of template typedefs in C++.

Function Documentation

int lemon::countItems ( const Graph & g ) [inline]

This function counts the items (nodes, edges etc) in the graph. The complexity of the function is O(n) because it iterates on all of the items.

int lemon::countNodes ( const Graph & g ) [inline]

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).

If the graph contains a nodeNum() member function and a NodeNumTag tag then this function calls directly the member function to query the cardinality of the node set.

int lemon::countANodes ( const Graph & g ) [inline]

This function counts the anodes in the graph. The complexity of the function is O(an) but for some graph structures it is specialized to run in O(1).

If the graph contains an aNodeNum() member function and a NodeNumTag tag then this function calls directly the member function to query the cardinality of the A-node set.

int lemon::countBNodes ( const Graph & g ) [inline]

This function counts the bnodes in the graph. The complexity of the function is O(bn) but for some graph structures it is specialized to run in O(1).

If the graph contains a bNodeNum() member function and a NodeNumTag tag then this function calls directly the member function to query the cardinality of the B-node set.

int lemon::countEdges ( const Graph & g ) [inline]

This function counts the edges in the graph. The complexity of the function is O(e) but for some graph structures it is specialized to run in O(1).

If the graph contains a edgeNum() member function and a EdgeNumTag tag then this function calls directly the member function to query the cardinality of the edge set.

int lemon::countUEdges ( const Graph & g ) [inline]

This function counts the undirected edges in the graph. The complexity of the function is O(e) but for some graph structures it is specialized to run in O(1).

If the graph contains a uEdgeNum() member function and a EdgeNumTag tag then this function calls directly the member function to query the cardinality of the undirected edge set.

int lemon::countOutEdges	(	const Graph &	_g,
		const typename Graph::Node &	_n
	)			`[inline]`

This function counts the number of the out-edges from node n in the graph.

int lemon::countInEdges	(	const Graph &	_g,
		const typename Graph::Node &	_n
	)			`[inline]`

This function counts the number of the in-edges to node n in the graph.

int lemon::countIncEdges	(	const Graph &	_g,
		const typename Graph::Node &	_n
	)			`[inline]`

This function counts the number of the inc-edges to node n in the graph.

Graph::Edge lemon::findEdge	(	const Graph &	g,
		typename Graph::Node	u,
		typename Graph::Node	v,
		typename Graph::Edge	prev = `INVALID`
	)			`[inline]`

Finds an edge from node u to node v in graph g.

If prev is INVALID (this is the default value), then it finds the first edge from u to v. Otherwise it looks for the next edge from u to v after prev.

Returns:: The found edge or INVALID if there is no such an edge.

Thus you can iterate through each edge from u to v as it follows.

      for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
        ...
      }

See also:

Graph::UEdge lemon::findUEdge	(	const Graph &	g,
		typename Graph::Node	u,
		typename Graph::Node	v,
		typename Graph::UEdge	p = `INVALID`
	)			`[inline]`

Finds an uedge from node u to node v in graph g. If the node u and node v is equal then each loop edge will be enumerated.

If prev is INVALID (this is the default value), then it finds the first edge from u to v. Otherwise it looks for the next edge from u to v after prev.

Returns:: The found edge or INVALID if there is no such an edge.

Thus you can iterate through each edge from u to v as it follows.

      for(UEdge e = findUEdge(g,u,v); e != INVALID; 
          e = findUEdge(g,u,v,e)) {
        ...
      }

See also:: ConEdgeIt

void lemon::copyMap	(	To &	to,
		const From &	from,
		ItemIt	it,
		const Ref &	ref
	)			`[inline]`

This function copies the from map to the to map. It uses the given iterator to iterate on the data structure and it uses the ref mapping to convert the from's keys to the to's keys.

void lemon::copyMap	(	To &	to,
		const From &	from,
		ItemIt	it
	)			`[inline]`

Copy the from map to the to map. It uses the given iterator to iterate on the data structure.

GraphCopy<To, From> lemon::copyGraph	(	To &	to,
		const From &	from
	)			`[inline]`

Copy a graph to another graph. The usage of the function:

      copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr).run();

After the copy the nr map will contain the mapping from the nodes of the from graph to the nodes of the to graph and ecr will contain the mapping from the edges of the to graph to the edges of the from graph.

See also:: GraphCopy

UGraphCopy<To, From> lemon::copyUGraph	(	To &	to,
		const From &	from
	)			`[inline]`

Copy an undirected graph to another graph. The usage of the function:

      copyUGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr).run();

After the copy the nr map will contain the mapping from the nodes of the from graph to the nodes of the to graph and ecr will contain the mapping from the edges of the to graph to the edges of the from graph.

See also:: UGraphCopy

BpUGraphCopy<To, From> lemon::copyBpUGraph	(	To &	to,
		const From &	from
	)			`[inline]`

Copy a bipartite undirected graph to another graph. The usage of the function:

      copyBpUGraph(trg, src).aNodeRef(anr).edgeCrossRef(ecr).run();

After the copy the nr map will contain the mapping from the nodes of the from graph to the nodes of the to graph and ecr will contain the mapping from the edges of the to graph to the edges of the from graph.

See also:: BpUGraphCopy

Basic Graph Utilities [Tools and Utilities]

Detailed Description

Classes

Files

Defines

Functions

Define Documentation

Function Documentation

Basic Graph Utilities
[Tools and Utilities]