KrisLibrary  1.0.0
Namespaces | Classes | Typedefs | Functions | Variables
Graph

Template classes for general graph computations. More...

Namespaces

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

Classes

class  Graph::ApproximateShortestPathProblem< Node, Edge >
 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  Graph::CallbackBase< Node >
 A template base class for a graph traversal. More...
 
struct  Graph::CountCallback< Node >
 Count the number of nodes traversed. More...
 
struct  Graph::FindCallback< Node >
 Find a particular node. More...
 
struct  Graph::DepthIntCallback
 Get the depth of all nodes (in an indexed graph, such as Graph) More...
 
struct  Graph::TimeCallback< Node >
 Get the start/finish time of a traversal. More...
 
struct  Graph::TimeIntCallback
 Same as above, but for indexed graphs. More...
 
struct  Graph::CycleCallback< Node >
 Compute if the graph has a cycle. More...
 
struct  Graph::TopologicalSortCallback< Node >
 Perform topological sort, when used with DFS. More...
 
struct  Graph::TraversalGraphCallback< Node >
 Compute the traversal graph of a traversal. More...
 
struct  Graph::TraversalGraphIntCallback
 Same as above, but for indexed graphs. More...
 
struct  Graph::PathCallback< Node >
 
struct  Graph::PathIntCallback
 Same as above, but for indexed graphs. More...
 
struct  Graph::ShortestPathsIntCallback
 
struct  Graph::ComponentIntCallback
 
class  Graph::DirectedGraph< Node, Edge >
 A specialization of a Graph to be directed graph. More...
 
class  Graph::Graph< NodeData, EdgeData >
 Basic template graph structure. More...
 
class  Graph::ShortestPathProblem< Node, Edge >
 Single-source shortest paths (Dijkstra's algorithm) More...
 
class  Graph::TreeNode< T, E >
 A tree graph structure, represented directly at the node level. More...
 
class  Graph::UndirectedGraph< Node, Edge >
 A specialization of a Graph to be an undirected graph. More...
 

Typedefs

typedef CallbackBase< int > Graph::Graph< NodeData, EdgeData >::Callback
 
typedef std::list< EdgeData >::iterator Graph::Graph< NodeData, EdgeData >::EdgeDataPtr
 
typedef std::map< int, EdgeDataPtr > Graph::Graph< NodeData, EdgeData >::EdgeList
 
typedef std::map< int, EdgeDataPtr > Graph::Graph< NodeData, EdgeData >::CoEdgeList
 
typedef EdgeList::iterator Graph::Graph< NodeData, EdgeData >::EdgeListIterator
 
typedef CoEdgeList::iterator Graph::Graph< NodeData, EdgeData >::CoEdgeListIterator
 
typedef EdgeList::const_iterator Graph::Graph< NodeData, EdgeData >::ConstEdgeListIterator
 

Functions

void Graph::Graph< NodeData, EdgeData >::Resize (int n)
 
void Graph::Graph< NodeData, EdgeData >::Cleanup ()
 
bool Graph::Graph< NodeData, EdgeData >::IsValid () const
 
void Graph::Graph< NodeData, EdgeData >::Copy (const Graph< NodeData, EdgeData > &g)
 
void Graph::Graph< NodeData, EdgeData >::SetTranspose (const Graph< NodeData, EdgeData > &g)
 
int Graph::Graph< NodeData, EdgeData >::NumNodes () const
 
int Graph::Graph< NodeData, EdgeData >::AddNode (const NodeData &)
 Adds a new node to the node list and returns its index.
 
void Graph::Graph< NodeData, EdgeData >::DeleteNode (int n)
 Deletes node n. More...
 
void Graph::Graph< NodeData, EdgeData >::DeleteNodes (std::vector< int > &delnodes)
 Deletes several nodes at once. More...
 
int Graph::Graph< NodeData, EdgeData >::NumEdges () const
 
EdgeData & Graph::Graph< NodeData, EdgeData >::AddEdge (int i, int j)
 
EdgeData & Graph::Graph< NodeData, EdgeData >::AddEdge (int i, int j, const EdgeData &)
 
bool Graph::Graph< NodeData, EdgeData >::HasEdge (int i, int j) const
 
EdgeData * Graph::Graph< NodeData, EdgeData >::FindEdge (int i, int j) const
 
void Graph::Graph< NodeData, EdgeData >::DeleteEdge (int i, int j)
 
void Graph::Graph< NodeData, EdgeData >::DeleteOutgoingEdges (int i)
 
void Graph::Graph< NodeData, EdgeData >::DeleteIncomingEdges (int i)
 
size_t Graph::Graph< NodeData, EdgeData >::OutDegree (int n) const
 
size_t Graph::Graph< NodeData, EdgeData >::InDegree (int n) const
 
template<class Iterator >
void Graph::Graph< NodeData, EdgeData >::Begin (int n, Iterator &) const
 
void Graph::Graph< NodeData, EdgeData >::NewTraversal ()
 
template<class Iterator >
void Graph::Graph< NodeData, EdgeData >::DFS (Callback &, Iterator)
 
template<class Iterator >
void Graph::Graph< NodeData, EdgeData >::BFS (Callback &, Iterator)
 
template<class Iterator >
void Graph::Graph< NodeData, EdgeData >::SimpleDFS (Callback &, Iterator)
 
template<class Iterator >
void Graph::Graph< NodeData, EdgeData >::SimpleBFS (Callback &, Iterator)
 
template<class Iterator >
void Graph::Graph< NodeData, EdgeData >::GuidedDFS (Callback &, Iterator)
 
template<class Iterator >
void Graph::Graph< NodeData, EdgeData >::GuidedBFS (Callback &, Iterator)
 
template<class Iterator >
void Graph::Graph< NodeData, EdgeData >::_DFS (int node, Callback &f, Iterator)
 
template<class Iterator >
void Graph::Graph< NodeData, EdgeData >::_BFS (int node, Callback &f, Iterator)
 
template<class Iterator >
void Graph::Graph< NodeData, EdgeData >::_SimpleDFS (int node, Callback &f, Iterator)
 
template<class Iterator >
void Graph::Graph< NodeData, EdgeData >::_SimpleBFS (int node, Callback &f, Iterator)
 
template<class Iterator >
void Graph::Graph< NodeData, EdgeData >::_GuidedDFS (int node, Callback &f, Iterator)
 
template<class Iterator >
void Graph::Graph< NodeData, EdgeData >::_GuidedBFS (int node, Callback &f, Iterator)
 
void Graph::Graph< NodeData, EdgeData >::WriteDOT (std::ostream &out)
 
bool Graph::Load_TGF (std::istream &in, Graph< std::string, std::string > &G)
 Loads a graph from the Trivial Graph Format.
 
void Graph::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 Graph::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 Graph::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 Graph::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 Graph::NodesEdgesFromStrings (const Graph< std::string, std::string > &Gs, Graph< N, E > &G)
 De-serializes the graph's nodes and edges using the istream >> operator.
 
bool Graph::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 Graph::GetAncestorPath (const std::vector< int > &p, int n, int lastAncestor, std::vector< int > &path)
 Vector version of GetAncestorPath for convenience.
 
template<class Node >
void Graph::GetAncestorPath (const std::map< Node, Node > &p, Node n, std::list< Node > &path)
 Same as above, but with an arbitrary Node type.
 

Variables

std::vector< Color > Graph::Graph< NodeData, EdgeData >::nodeColor
 
std::vector< NodeData > Graph::Graph< NodeData, EdgeData >::nodes
 
std::vector< EdgeList > Graph::Graph< NodeData, EdgeData >::edges
 
std::vector< CoEdgeList > Graph::Graph< NodeData, EdgeData >::co_edges
 
std::list< EdgeData > Graph::Graph< NodeData, EdgeData >::edgeData
 

Detailed Description

Template classes for general graph computations.

Function Documentation

template<class NodeData , class EdgeData >
template<class Iterator >
void Graph::Graph< NodeData, EdgeData >::_DFS ( int  node,
Callback f,
Iterator  it 
)
template<class NodeData , class EdgeData >
void Graph::Graph< NodeData, EdgeData >::DeleteNode ( int  n)

Deletes node n.

Does so by moving the last node to position n. This modifies the node index of the last node from NumNodes()-1 to n.

template<class NodeData , class EdgeData >
void Graph::Graph< NodeData, EdgeData >::DeleteNodes ( std::vector< int > &  delnodes)

Deletes several nodes at once.

Takes a vector of nodes to delete, deletes them, and int the same vector returns the mapping of altered nodes. set to -1 if deleted, or the new index otherwise.

bool Graph::GetAncestorPath ( const std::vector< int > &  p,
int  n,
int  lastAncestor,
std::list< int > &  path 
)
inline

Calculates a path of nodes from a list of parents.

Parameters
pThe array of parents such that p[n] is the parent of node n
nThe destination node
lastAncestorEither the start node or -1
pathThe output path from lastAncestor to n
Returns
true if the path reached lastAncestor

Referenced by PRMStarPlanner::CheckPath(), MCRPlanner::CoveragePath(), MCRPlannerGoalSet::CoveragePath(), GetAncestorPath(), and PRMStarPlanner::GetPath().

template<class NodeData , class EdgeData >
void Graph::Graph< NodeData, EdgeData >::NewTraversal ( )

Call NewTraversal to erase history of previous searches by setting the node colors to white

Full-blown D[B]FS calls all callback functions.
SimpleD[B]fs ignores the descend/edge functions.
GuidedD[B]fs uses the Descend function rather than the color to determine if a node should be visited. Be careful with this to avoid infinite loops.

NOTE: only outgoing, reverse, or undirected iteration methods should be used.

References Graph::CallbackBase< Node >::Descend(), Graph::CallbackBase< Node >::NewComponent(), and Graph::CallbackBase< Node >::Stop().