dtn::MultiGraph< _NodeInfo, _EdgeInfo > Class Template Reference

Data structure to represent a multigraph. More...

#include <MultiGraph.h>

List of all members.

Classes
struct	DijkstraCompare
	Helper class to compute Dijkstra distance. More...
class	Edge
	The edge class. More...
class	EdgeVector
	Helper data structure for a vector of edges. More...
class	Node
	The node class. More...
class	NodeVector
	Helper data structure for a vector of nodes. More...
struct	SearchInfo
	Struct used to encapsulate state that may be needed by weight functors and which is the same for a whole shortest path computation. More...
class	WeightFn
	The abstract weight function class. More...
Public Types
typedef oasys::InlineFormatter < _EdgeInfo >	EdgeFormatter
Public Member Functions
	MultiGraph ()
	Constructor.
	~MultiGraph ()
	Destructor.
Node *	add_node (const std::string &id, const _NodeInfo &info)
	Add a new node.
Node *	find_node (const std::string &id) const
	Find a node with the given id.
bool	del_node (const std::string &id)
	Delete a node and all its edges.
Edge *	add_edge (Node *a, Node *b, const _EdgeInfo &info)
	Add an edge.
Edge *	find_edge (const Node *a, const Node *b, const _EdgeInfo &info)
	Find an edge.
bool	del_edge (Node *node, Edge *edge)
	Remove the specified edge from the given node, deleting the Edge object.
void	shortest_path (const Node *a, const Node *b, EdgeVector *path, WeightFn *weight_fn, Bundle *bundle=NULL)
	Find the shortest path between two nodes by running Dijkstra's algorithm, filling in the edge vector with the best path.
Edge *	best_next_hop (const Node *a, const Node *b, WeightFn *weight_fn, Bundle *bundle=NULL)
	More limited version of the shortest path that just returns the next hop edge.
void	clear ()
	Clear the contents of the graph.
int	format (char *buf, size_t sz) const
	Virtual from Formatter.
std::string	dump () const
	Return a string dump of the graph.
const NodeVector &	nodes ()
	Accessor for the nodes array.
Static Public Member Functions
static u_int32_t	NodeDistance (const Node *n)
	XXX/demmer this stupid helper function is needed because DijkstraCompare can't be made a friend class of Node without crashing gcc 3.4.
Protected Member Functions
bool	get_reverse_path (const Node *a, const Node *b, EdgeVector *path)
	Helper function to follow the prev_ links that result from a Dijkstra search from a to b and build an EdgeVector.
Protected Attributes
NodeVector	nodes_
	The vector of all nodes.

---

Detailed Description

template<typename _NodeInfo, typename _EdgeInfo>
class dtn::MultiGraph< _NodeInfo, _EdgeInfo >

Data structure to represent a multigraph.

Definition at line 35 of file MultiGraph.h.

---

Member Typedef Documentation

template<typename _NodeInfo, typename _EdgeInfo>

typedef oasys::InlineFormatter<_EdgeInfo> dtn::MultiGraph< _NodeInfo, _EdgeInfo >::EdgeFormatter

Definition at line 201 of file MultiGraph.h.

---

Constructor & Destructor Documentation

template<typename _NodeInfo, typename _EdgeInfo>

dtn::MultiGraph< _NodeInfo, _EdgeInfo >::MultiGraph

(

)

Constructor.

template<typename _NodeInfo, typename _EdgeInfo>

dtn::MultiGraph< _NodeInfo, _EdgeInfo >::~MultiGraph

(

)

Destructor.

---

Member Function Documentation

template<typename _NodeInfo, typename _EdgeInfo>

Edge* dtn::MultiGraph< _NodeInfo, _EdgeInfo >::add_edge	(	Node *	a,
		Node *	b,
		const _EdgeInfo &	info
	)

Add an edge.

Referenced by dtn::DTLSRRouter::handle_contact_up(), dtn::DTLSRRouter::handle_lsa(), and dtn::DTLSRRouter::handle_registration_added().

template<typename _NodeInfo, typename _EdgeInfo>

Node* dtn::MultiGraph< _NodeInfo, _EdgeInfo >::add_node	(	const std::string &	id,
		const _NodeInfo &	info
	)

Add a new node.

Referenced by dtn::DTLSRRouter::handle_contact_up(), dtn::DTLSRRouter::handle_lsa(), dtn::DTLSRRouter::handle_registration_added(), and dtn::DTLSRRouter::initialize().

template<typename _NodeInfo, typename _EdgeInfo>

Edge* dtn::MultiGraph< _NodeInfo, _EdgeInfo >::best_next_hop	(	const Node *	a,
		const Node *	b,
		WeightFn *	weight_fn,
		Bundle *	bundle = NULL
	)

More limited version of the shortest path that just returns the next hop edge.

Referenced by dtn::DTLSRRouter::recompute_routes().

template<typename _NodeInfo, typename _EdgeInfo>

void dtn::MultiGraph< _NodeInfo, _EdgeInfo >::clear

(

)

Clear the contents of the graph.

template<typename _NodeInfo, typename _EdgeInfo>

bool dtn::MultiGraph< _NodeInfo, _EdgeInfo >::del_edge	(	Node *	node,
		Edge *	edge
	)

Remove the specified edge from the given node, deleting the Edge object.

Referenced by dtn::DTLSRRouter::remove_edge().

template<typename _NodeInfo, typename _EdgeInfo>

bool dtn::MultiGraph< _NodeInfo, _EdgeInfo >::del_node

(

const std::string &

id

)

Delete a node and all its edges.

template<typename _NodeInfo, typename _EdgeInfo>

std::string dtn::MultiGraph< _NodeInfo, _EdgeInfo >::dump

(

)

const [inline]

Return a string dump of the graph.

Definition at line 90 of file MultiGraph.h.

template<typename _NodeInfo, typename _EdgeInfo>

Edge* dtn::MultiGraph< _NodeInfo, _EdgeInfo >::find_edge	(	const Node *	a,
		const Node *	b,
		const _EdgeInfo &	info
	)

Find an edge.

Referenced by dtn::DTLSRRouter::handle_contact_up(), and dtn::DTLSRRouter::handle_registration_added().

template<typename _NodeInfo, typename _EdgeInfo>

Node* dtn::MultiGraph< _NodeInfo, _EdgeInfo >::find_node

(

const std::string &

id

)

const

Find a node with the given id.

Referenced by dtn::DTLSRRouter::handle_contact_down(), dtn::DTLSRRouter::handle_contact_up(), dtn::DTLSRRouter::handle_lsa(), and dtn::DTLSRRouter::handle_registration_added().

template<typename _NodeInfo, typename _EdgeInfo>

int dtn::MultiGraph< _NodeInfo, _EdgeInfo >::format	(	char *	buf,
		size_t	sz
	)			const

Virtual from Formatter.

Referenced by dtn::MultiGraph< NodeInfo, EdgeInfo >::dump().

template<typename _NodeInfo, typename _EdgeInfo>

bool dtn::MultiGraph< _NodeInfo, _EdgeInfo >::get_reverse_path	(	const Node *	a,
		const Node *	b,
		EdgeVector *	path
	)			[protected]

Helper function to follow the prev_ links that result from a Dijkstra search from a to b and build an EdgeVector.

template<typename _NodeInfo, typename _EdgeInfo>

static u_int32_t dtn::MultiGraph< _NodeInfo, _EdgeInfo >::NodeDistance

(

const Node *

n

)

[inline, static]

XXX/demmer this stupid helper function is needed because DijkstraCompare can't be made a friend class of Node without crashing gcc 3.4.

Definition at line 166 of file MultiGraph.h.

Referenced by dtn::MultiGraph< _NodeInfo, _EdgeInfo >::DijkstraCompare::operator()().

template<typename _NodeInfo, typename _EdgeInfo>

const NodeVector& dtn::MultiGraph< _NodeInfo, _EdgeInfo >::nodes

(

)

[inline]

Accessor for the nodes array.

Definition at line 98 of file MultiGraph.h.

Referenced by dtn::DTLSRRouter::recompute_routes().

template<typename _NodeInfo, typename _EdgeInfo>

void dtn::MultiGraph< _NodeInfo, _EdgeInfo >::shortest_path	(	const Node *	a,
		const Node *	b,
		EdgeVector *	path,
		WeightFn *	weight_fn,
		Bundle *	bundle = NULL
	)

Find the shortest path between two nodes by running Dijkstra's algorithm, filling in the edge vector with the best path.

Optionally also takes a bundle to route from a to b

---

Member Data Documentation

template<typename _NodeInfo, typename _EdgeInfo>

NodeVector dtn::MultiGraph< _NodeInfo, _EdgeInfo >::nodes_ [protected]

The vector of all nodes.

Definition at line 236 of file MultiGraph.h.

Referenced by dtn::MultiGraph< NodeInfo, EdgeInfo >::nodes().

---

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

• MultiGraph.h