Graph Search

Detailed Description

This group contains the common graph search algorithms, namely breadth-first search (BFS) and depth-first search (DFS) [6].

Classes
class	Bfs< GR, TR >
	BFS algorithm class. More...
class	BfsVisit< GR, VS, TR >
	BFS algorithm class with visitor interface. More...
class	Dfs< GR, TR >
	DFS algorithm class. More...
class	DfsVisit< GR, VS, TR >
	DFS algorithm class with visitor interface. More...
class	MaxCardinalitySearch< GR, CAP, TR >
	Maximum Cardinality Search algorithm class. More...
struct	Bfs< GR, TR >::SetDistMap< T >
	Named parameter for setting DistMap type. More...
struct	Bfs< GR, TR >::SetPredMap< T >
	Named parameter for setting PredMap type. More...
struct	Bfs< GR, TR >::SetProcessedMap< T >
	Named parameter for setting ProcessedMap type. More...
struct	Bfs< GR, TR >::SetReachedMap< T >
	Named parameter for setting ReachedMap type. More...
struct	Bfs< GR, TR >::SetStandardProcessedMap
	Named parameter for setting ProcessedMap type to be Digraph::NodeMap<bool>. More...
struct	BfsVisit< GR, VS, TR >::SetReachedMap< T >
struct	Dfs< GR, TR >::SetDistMap< T >
	Named parameter for setting DistMap type. More...
struct	Dfs< GR, TR >::SetPredMap< T >
	Named parameter for setting PredMap type. More...
struct	Dfs< GR, TR >::SetProcessedMap< T >
	Named parameter for setting ProcessedMap type. More...
struct	Dfs< GR, TR >::SetReachedMap< T >
	Named parameter for setting ReachedMap type. More...
struct	Dfs< GR, TR >::SetStandardProcessedMap
	Named parameter for setting ProcessedMap type to be Digraph::NodeMap<bool>. More...
struct	DfsVisit< GR, VS, TR >::SetReachedMap< T >
struct	MaxCardinalitySearch< GR, CAP, TR >::SetCapacityMap< T >
	Named parameter for setting CapacityMap type More...
struct	MaxCardinalitySearch< GR, CAP, TR >::SetCardinalityMap< T >
	Named parameter for setting CardinalityMap type More...
struct	MaxCardinalitySearch< GR, CAP, TR >::SetHeap< H, CR >
	Named parameter for setting heap and cross reference type More...
struct	MaxCardinalitySearch< GR, CAP, TR >::SetProcessedMap< T >
	Named parameter for setting ProcessedMap type More...
struct	MaxCardinalitySearch< GR, CAP, TR >::SetStandardHeap< H, CR >
	Named parameter for setting heap and cross reference type with automatic allocation More...

Files
file	bfs.h
	BFS algorithm.
file	dfs.h
	DFS algorithm.
file	max_cardinality_search.h
	Maximum cardinality search in undirected digraphs.

Functions
template<class GR >
BfsWizard< BfsWizardBase< GR > >	bfs (const GR &digraph)
	Function-type interface for BFS algorithm.
template<class GR >
DfsWizard< DfsWizardBase< GR > >	dfs (const GR &digraph)
	Function-type interface for DFS algorithm.

Function Documentation

BfsWizard<BfsWizardBase<GR> > lemon::bfs

(

const GR &

digraph

)

Function-type interface for BFS algorithm.

This function also has several named parameters, they are declared as the members of class BfsWizard. The following examples show how to use these parameters.

// Compute shortest path from node s to each node
bfs(g).predMap(preds).distMap(dists).run(s);

// Compute shortest path from s to t
bool reached = bfs(g).path(p).dist(d).run(s,t);

Warning

Don't forget to put the run() to the end of the parameter list.

See Also

BfsWizard

Bfs

DfsWizard<DfsWizardBase<GR> > lemon::dfs

(

const GR &

digraph

)

Function-type interface for DFS algorithm.

This function also has several named parameters, they are declared as the members of class DfsWizard. The following examples show how to use these parameters.

// Compute the DFS tree
dfs(g).predMap(preds).distMap(dists).run(s);

// Compute the DFS path from s to t
bool reached = dfs(g).path(p).dist(d).run(s,t);

Warning

Don't forget to put the run() to the end of the parameter list.

See Also

DfsWizard

Dfs