Graph Namespace Reference

Namespace for all classes and functions in the Graph subdirectory. More...

Classes
class	ApproximateShortestPathProblem
	Approximate single-source shortest paths, whose output is at most (1+epsilon)^d times the true shortest path, where d is the depth of the node. This can be somewhat faster than running true shortest paths. More...
struct	CallbackBase
	A template base class for a graph traversal. More...
struct	CoEdgeIterator
struct	ComponentIntCallback
class	ConnectedComponents
struct	CountCallback
	Count the number of nodes traversed. More...
struct	CycleCallback
	Compute if the graph has a cycle. More...
struct	DepthIntCallback
	Get the depth of all nodes (in an indexed graph, such as Graph) More...
class	DirectedGraph
	A specialization of a Graph to be directed graph. More...
struct	EdgeIterator
struct	FindCallback
	Find a particular node. More...
class	Graph
	Basic template graph structure. More...
struct	PathCallback
struct	PathIntCallback
	Same as above, but for indexed graphs. More...
class	ShortestPathProblem
	Single-source shortest paths (Dijkstra's algorithm) More...
struct	ShortestPathsIntCallback
struct	TimeCallback
	Get the start/finish time of a traversal. More...
struct	TimeIntCallback
	Same as above, but for indexed graphs. More...
struct	TopologicalSortCallback
	Perform topological sort, when used with DFS. More...
struct	TraversalGraphCallback
	Compute the traversal graph of a traversal. More...
struct	TraversalGraphIntCallback
	Same as above, but for indexed graphs. More...
class	TreeNode
	A tree graph structure, represented directly at the node level. More...
struct	UndirectedEdgeIterator
class	UndirectedGraph
	A specialization of a Graph to be an undirected graph. More...

Typedefs
typedef double	Weight

Enumerations
enum	Color { White, Grey, Black }

Functions
template<class Edge >
Weight	ConstantWeight (const Edge &e)
template<class Edge >
Weight	StandardWeight (const Edge &e)
bool	Load_TGF (std::istream &in, Graph< std::string, std::string > &G)
	Loads a graph from the Trivial Graph Format.
void	Save_TGF (std::ostream &o, const Graph< std::string, std::string > &G)
	Saves a graph to the Trivial Graph Format.
template<class N , class E >
void	NodesToStrings (const Graph< N, E > &G, Graph< std::string, std::string > &Gs)
	Serializes the graph's nodes using the ostream << operator.
template<class N , class E >
bool	NodesFromStrings (const Graph< std::string, std::string > &Gs, Graph< N, E > &G)
	De-serializes the graph's nodes using the istream >> operator.
template<class N , class E >
void	NodesEdgesToStrings (const Graph< N, E > &G, Graph< std::string, std::string > &Gs)
	Serializes the graph's nodes and edges using the ostream << operator.
template<class N , class E >
bool	NodesEdgesFromStrings (const Graph< std::string, std::string > &Gs, Graph< N, E > &G)
	De-serializes the graph's nodes and edges using the istream >> operator.
template<class N1 , class E1 , class N2 , class E2 >
void	CopyStructure (const Graph< N1, E1 > &G1, Graph< N2, E2 > &G2)
	Copies the edge structure of G1 to G2 without setting its data.
template<class N1 , class E , class N2 , class F >
void	Transform (const Graph< N1, E > &G1, F f, Graph< N2, E > &G2)
	Transforms a graph G1 to G2 using the function f to transform nodes from G1 to G2. More...
template<class N1 , class E1 , class N2 , class E2 , class F , class G >
void	Transform (const Graph< N1, E1 > &G1, F f, G g, Graph< N2, E2 > &G2)
	Transforms a graph G1 to G2 using the function f to transform nodes from G1 to G2, and using g to transform edges from G1 to G2. More...
template<class Node , class Edge >
void	GetEdges (const Graph< Node, Edge > &G, std::vector< std::pair< int, int > > &edges)
	Gets a list of edges.
template<class Node , class Edge >
void	GetSubGraph (const Graph< Node, Edge > &G, const std::vector< int > &nodes, Graph< Node, Edge > &S)
	Creates the subgraph S of G induced by picking the nodes in nodes. More...
template<class Node , class Edge >
void	GetSubGraph (const Graph< Node, Edge > &G, int nmin, int nmax, Graph< Node, Edge > &S)
	Creates the subgraph S of G induced by nodes [nmin,nmax)
template<class Node , class Edge >
void	GetDualGraph (const Graph< Node, Edge > &G, Graph< std::pair< int, int >, int > &D)
	Creates the dual graph of G. The dual references into the graph.
template<class Node , class Edge >
void	GetDualGraphCopy (const Graph< Node, Edge > &G, Graph< Edge, Node > &D)
	Creates the dual graph of G and copies the data.
template<class Node , class Edge >
void	Get1Ring (const Graph< Node, Edge > &G, int node, std::set< int > &ring)
	Returns the undirected 1-ring of the given node.
template<class Node , class Edge >
void	GetNRing (const Graph< Node, Edge > &G, int node, int n, std::set< int > &ring)
	Returns the undirected n-ring of the given node.
template<class Node , class Edge >
void	Get1Ring (const Graph< Node, Edge > &G, const std::set< int > &nodes, std::set< int > &ring)
	Returns the undirected 1-ring of the given set of nodes.
bool	GetAncestorPath (const std::vector< int > &p, int n, int lastAncestor, std::list< int > &path)
	Calculates a path of nodes from a list of parents. More...
bool	GetAncestorPath (const std::vector< int > &p, int n, int lastAncestor, std::vector< int > &path)
	Vector version of GetAncestorPath for convenience.
template<class Node >
void	GetAncestorPath (const std::map< Node, Node > &p, Node n, std::list< Node > &path)
	Same as above, but with an arbitrary Node type.

Detailed Description

Namespace for all classes and functions in the Graph subdirectory.

Function Documentation

template<class Node , class Edge >

void Graph::GetSubGraph	(	const Graph< Node, Edge > &	G,
		const std::vector< int > &	nodes,
		Graph< Node, Edge > &	S
	)

Creates the subgraph S of G induced by picking the nodes in nodes.

Nodes is a sorted list of the node indices.

Referenced by DisplacementPlanner::BuildRoadmap().

template<class N1 , class E , class N2 , class F >

void Graph::Transform	(	const Graph< N1, E > &	G1,
		F	f,
		Graph< N2, E > &	G2
	)

Transforms a graph G1 to G2 using the function f to transform nodes from G1 to G2.

The semantics of f are that it takes params (a,b) where a is of type N1, and b is of type N2&, and transforms a to b.

template<class N1 , class E1 , class N2 , class E2 , class F , class G >

void Graph::Transform	(	const Graph< N1, E1 > &	G1,
		F	f,
		G	g,
		Graph< N2, E2 > &	G2
	)

Transforms a graph G1 to G2 using the function f to transform nodes from G1 to G2, and using g to transform edges from G1 to G2.

The semantics of f are that it takes params (a,b) where a is of type N1, and b is of type N2&, and transforms a to b.