A specialization of a Graph to be an undirected graph. More...
#include <UndirectedGraph.h>
Inheritance diagram for Graph::UndirectedGraph< Node, Edge >:
Public Types | |
| typedef Graph< Node, Edge > | P |
| typedef Graph< Node, Edge >::Callback | Callback |
| typedef UndirectedEdgeIterator< Edge > | Iterator |
 Public Types inherited from Graph::Graph< Node, Edge > | |
| typedef CallbackBase< int > | Callback |
| typedef std::list< Edge >::iterator | EdgeDataPtr |
| typedef std::map< int, EdgeDataPtr > | EdgeList |
| typedef std::map< int, EdgeDataPtr > | CoEdgeList |
| typedef EdgeList::iterator | EdgeListIterator |
| typedef CoEdgeList::iterator | CoEdgeListIterator |
| typedef EdgeList::const_iterator | ConstEdgeListIterator |
Public Member Functions | |
| void | Order (int &a, int &b) const |
| Edge & | AddEdge (int i, int j) |
| Edge & | AddEdge (int i, int j, const Edge &e) |
| bool | HasEdge (int i, int j) const |
| Edge * | FindEdge (int i, int j) const |
| void | DeleteEdge (int i, int j) |
| void | DeleteIncomingEdges (int i) |
| void | DeleteNode (int n) |
| void | DeleteNodes (std::vector< int > &delnodes) |
| void | DFS (Callback &f) |
| void | BFS (Callback &f) |
| void | SimpleDFS (Callback &f) |
| void | SimpleBFS (Callback &f) |
| void | GuidedDFS (Callback &f) |
| void | GuidedBFS (Callback &f) |
| void | _DFS (int node, Callback &f) |
| NOTE: these do not call NewTraversal() | |
| void | _BFS (int node, Callback &f) |
| void | _SimpleDFS (int node, Callback &f) |
| void | _SimpleBFS (int node, Callback &f) |
| void | _GuidedDFS (int node, Callback &f) |
| void | _GuidedBFS (int node, Callback &f) |
| size_t | Degree (int n) const |
| bool | IsConnected (int n1, int n2) |
| std::list< int > | TopologicalSort () |
| Returns the topological sort of the graph, O(n) time. | |
| bool | HasCycle () |
| Returns true if there is any cycle, O(n) time. | |
| bool | IsValid () const |
| void | NormalizeEdges (int n) |
| Public Member Functions inherited from Graph::Graph< Node, Edge > | |
| void | Resize (int n) |
| void | Cleanup () |
| bool | IsValid () const |
| void | Copy (const Graph< Node, Edge > &g) |
| void | SetTranspose (const Graph< Node, Edge > &g) |
| int | NumNodes () const |
| int | AddNode (const Node &) |
| Adds a new node to the node list and returns its index. | |
| void | DeleteNode (int n) |
| Deletes node n. More... | |
| void | DeleteNodes (std::vector< int > &delnodes) |
| Deletes several nodes at once. More... | |
| int | NumEdges () const |
| Edge & | AddEdge (int i, int j) |
| Edge & | AddEdge (int i, int j, const Edge &) |
| bool | HasEdge (int i, int j) const |
| Edge * | FindEdge (int i, int j) const |
| void | DeleteEdge (int i, int j) |
| void | DeleteOutgoingEdges (int i) |
| void | DeleteIncomingEdges (int i) |
| size_t | OutDegree (int n) const |
| size_t | InDegree (int n) const |
| void | Begin (int n, Iterator &) const |
| void | NewTraversal () |
| void | DFS (Callback &, Iterator) |
| void | BFS (Callback &, Iterator) |
| void | SimpleDFS (Callback &, Iterator) |
| void | SimpleBFS (Callback &, Iterator) |
| void | GuidedDFS (Callback &, Iterator) |
| void | GuidedBFS (Callback &, Iterator) |
| void | _DFS (int node, Callback &f, Iterator) |
| void | _BFS (int node, Callback &f, Iterator) |
| void | _SimpleDFS (int node, Callback &f, Iterator) |
| void | _SimpleBFS (int node, Callback &f, Iterator) |
| void | _GuidedDFS (int node, Callback &f, Iterator) |
| void | _GuidedBFS (int node, Callback &f, Iterator) |
| void | WriteDOT (std::ostream &out) |
Additional Inherited Members | |
| Public Attributes inherited from Graph::Graph< Node, Edge > | |
| std::vector< Color > | nodeColor |
| std::vector< Node > | nodes |
| std::vector< EdgeList > | edges |
| std::vector< CoEdgeList > | co_edges |
| std::list< Edge > | edgeData |
Detailed Description
template<class Node, class Edge>
class Graph::UndirectedGraph< Node, Edge >
A specialization of a Graph to be an undirected graph.
All edges (i,j) have i<j. All co-edges (i,j) have j>i.
Member Function Documentation
template<class Node , class Edge >
| bool Graph::UndirectedGraph< Node, Edge >::IsConnected | ( | int | n1, |
| int | n2 | ||
| ) |
Returns true if the two nodes are connected by a path. O(n log n) time in the worst case. For better running time for connected components, especially for many queries, use ConnectedComponents in ConnectedComponents.h
Referenced by Graph::UndirectedGraph< CSpace *, CSpace * >::_DFS().
The documentation for this class was generated from the following file:
