Graph::Graph< NodeData, EdgeData > Class Template Reference

Basic template graph structure. More...

#include <Graph.h>

Public Types
typedef CallbackBase< int >	Callback
typedef std::list< EdgeData >::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	Resize (int n)
void	Cleanup ()
bool	IsValid () const
void	Copy (const Graph< NodeData, EdgeData > &g)
void	SetTranspose (const Graph< NodeData, EdgeData > &g)
int	NumNodes () const
int	AddNode (const NodeData &)
	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
EdgeData &	AddEdge (int i, int j)
EdgeData &	AddEdge (int i, int j, const EdgeData &)
bool	HasEdge (int i, int j) const
EdgeData *	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
template<class Iterator >
void	Begin (int n, Iterator &) const
void	NewTraversal ()
template<class Iterator >
void	DFS (Callback &, Iterator)
template<class Iterator >
void	BFS (Callback &, Iterator)
template<class Iterator >
void	SimpleDFS (Callback &, Iterator)
template<class Iterator >
void	SimpleBFS (Callback &, Iterator)
template<class Iterator >
void	GuidedDFS (Callback &, Iterator)
template<class Iterator >
void	GuidedBFS (Callback &, Iterator)
template<class Iterator >
void	_DFS (int node, Callback &f, Iterator)
template<class Iterator >
void	_BFS (int node, Callback &f, Iterator)
template<class Iterator >
void	_SimpleDFS (int node, Callback &f, Iterator)
template<class Iterator >
void	_SimpleBFS (int node, Callback &f, Iterator)
template<class Iterator >
void	_GuidedDFS (int node, Callback &f, Iterator)
template<class Iterator >
void	_GuidedBFS (int node, Callback &f, Iterator)
void	WriteDOT (std::ostream &out)

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

Detailed Description

template<class NodeData, class EdgeData>
class Graph::Graph< NodeData, EdgeData >

Basic template graph structure.

The graph is represented with nodes indexed by 0,...,NumNodes()-1, and for each node, an adjacency list of outgoing edges 'edges' and incoming edges 'co_edges'.

A NodeData is stored for each node in a vector 'nodes'. A EdgeData is stored for each edge in a list 'edgeData'. An adjacency list in 'edges' or 'co_edges' is represented as a map from adjacent node indices to EdgeData pointers.

Edges are most easily traversed using the EdgeListIterator classes in Edge.h. They allow forwards, backwards, or bidirectional traversals. For more strict definition of directed vs. undirected graphs, consider DirectedGraph or UndirectedGraph.

NodeData must have valid constructors and assignment operators. EdgeData must have a default constructor.

Basic traversal functions (DFS,BFS) are provided. More sophisticated computations should be written in as algorithm classes (see ShortestPathProblem).

---

The documentation for this class was generated from the following file:

• Graph.h