KrisLibrary
1.0.0
|
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... | |
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. | |
Template classes for general graph computations.
void Graph::Graph< NodeData, EdgeData >::_DFS | ( | int | node, |
Callback & | f, | ||
Iterator | it | ||
) |
The following perform a traversal from a given node. They do not call NewTraversal().
References Graph::CallbackBase< Node >::BackEdge(), Graph::CallbackBase< Node >::CrossEdge(), Graph::CallbackBase< Node >::Descend(), Graph::CallbackBase< Node >::ForwardEdge(), Graph::CallbackBase< Node >::PostVisit(), Graph::CallbackBase< Node >::Stop(), and Graph::CallbackBase< Node >::Visit().
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.
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.
|
inline |
Calculates a path of nodes from a list of parents.
p | The array of parents such that p[n] is the parent of node n |
n | The destination node |
lastAncestor | Either the start node or -1 |
path | The output path from lastAncestor to n |
Referenced by PRMStarPlanner::CheckPath(), MCRPlanner::CoveragePath(), MCRPlannerGoalSet::CoveragePath(), GetAncestorPath(), and PRMStarPlanner::GetPath().
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().