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

#include <MultiGraph.h>

List of all members.


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.


Public Types

typedef oasys::InlineFormatter
< _EdgeInfo > 
EdgeFormatter

Public Member Functions

 MultiGraph ()
 Constructor.
 ~MultiGraph ()
 Destructor.
Nodeadd_node (const std::string &id, const _NodeInfo &info)
 Add a new node.
Nodefind_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.
Edgeadd_edge (Node *a, Node *b, const _EdgeInfo &info)
 Add an edge.
Edgefind_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.
Edgebest_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 NodeVectornodes ()
 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.

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...

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>
Node* dtn::MultiGraph< _NodeInfo, _EdgeInfo >::add_node ( const std::string &  id,
const _NodeInfo &  info 
)

template<typename _NodeInfo, typename _EdgeInfo>
Node* dtn::MultiGraph< _NodeInfo, _EdgeInfo >::find_node ( const std::string &  id  )  const

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>
Edge* dtn::MultiGraph< _NodeInfo, _EdgeInfo >::add_edge ( Node a,
Node b,
const _EdgeInfo &  info 
)

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

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>
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

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>
int dtn::MultiGraph< _NodeInfo, _EdgeInfo >::format ( char *  buf,
size_t  sz 
) const

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>
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>
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>
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.


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< dtn::DTLSRRouter::NodeInfo, dtn::DTLSRRouter::EdgeInfo >::nodes().


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

Generated on Mon Jul 21 14:12:21 2008 for DTN Reference Implementation by  doxygen 1.5.6