#include <MultiGraph.h>
Definition at line 35 of file MultiGraph.h.
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. | |
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... |
typedef oasys::InlineFormatter<_EdgeInfo> dtn::MultiGraph< _NodeInfo, _EdgeInfo >::EdgeFormatter |
Definition at line 201 of file MultiGraph.h.
dtn::MultiGraph< _NodeInfo, _EdgeInfo >::MultiGraph | ( | ) |
Constructor.
dtn::MultiGraph< _NodeInfo, _EdgeInfo >::~MultiGraph | ( | ) |
Destructor.
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().
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().
bool dtn::MultiGraph< _NodeInfo, _EdgeInfo >::del_node | ( | const std::string & | id | ) |
Delete a node and all its edges.
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().
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().
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().
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
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().
void dtn::MultiGraph< _NodeInfo, _EdgeInfo >::clear | ( | ) |
Clear the contents of the graph.
int dtn::MultiGraph< _NodeInfo, _EdgeInfo >::format | ( | char * | buf, | |
size_t | sz | |||
) | const |
Virtual from Formatter.
Referenced by dtn::MultiGraph< dtn::DTLSRRouter::NodeInfo, dtn::DTLSRRouter::EdgeInfo >::dump().
std::string dtn::MultiGraph< _NodeInfo, _EdgeInfo >::dump | ( | ) | const [inline] |
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().
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()().
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.
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().