--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/servlib/routing/MultiGraph.h Thu Apr 21 14:57:45 2011 +0100
@@ -0,0 +1,243 @@
+/*
+ * Copyright 2007 Intel Corporation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef _MULTIGRAPH_H_
+#define _MULTIGRAPH_H_
+
+#include <vector>
+#include <oasys/debug/InlineFormatter.h>
+#include <oasys/debug/Formatter.h>
+#include <oasys/debug/Logger.h>
+#include <oasys/util/StringBuffer.h>
+#include <oasys/util/Time.h>
+
+namespace dtn {
+
+class Bundle;
+
+/**
+ * Data structure to represent a multigraph.
+ */
+template <typename _NodeInfo, typename _EdgeInfo>
+class MultiGraph : public oasys::Formatter, public oasys::Logger {
+public:
+ /// @{ Forward Declarations of helper classes
+ class Edge;
+ class EdgeVector;
+ class Node;
+ class NodeVector;
+ class WeightFn;
+ /// @}
+
+ /// Constructor
+ MultiGraph();
+
+ /// Destructor
+ ~MultiGraph();
+
+ /// Add a new node
+ Node* add_node(const std::string& id, const _NodeInfo& info);
+
+ /// Find a node with the given id
+ Node* find_node(const std::string& id) const;
+
+ /// Delete a node and all its edges
+ bool del_node(const std::string& id);
+
+ /// Add an edge
+ Edge* add_edge(Node* a, Node* b, const _EdgeInfo& info);
+
+ /// Find an edge
+ Edge* find_edge(const Node* a, const Node* b, const _EdgeInfo& info);
+
+ /// Remove the specified edge from the given node, deleting the
+ /// Edge object
+ bool del_edge(Node* node, Edge* edge);
+
+ /// 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
+ void shortest_path(const Node* a, const Node* b,
+ EdgeVector* path, WeightFn* weight_fn,
+ Bundle* bundle = NULL);
+
+ /// More limited version of the shortest path that just returns
+ /// the next hop edge.
+ Edge* best_next_hop(const Node* a, const Node* b, WeightFn* weight_fn,
+ Bundle* bundle = NULL);
+
+ /// Clear the contents of the graph
+ void clear();
+
+ /// Virtual from Formatter
+ int format(char* buf, size_t sz) const;
+
+ /// Return a string dump of the graph
+ std::string dump() const
+ {
+ char buf[1024];
+ int len = format(buf, sizeof(buf));
+ return std::string(buf, len);
+ }
+
+ /// Accessor for the nodes array
+ const NodeVector& nodes() { return nodes_; }
+
+ /// Struct used to encapsulate state that may be needed by weight
+ /// functors and which is the same for a whole shortest path
+ /// computation.
+ struct SearchInfo {
+ SearchInfo(Bundle* bundle);
+
+ Bundle* bundle_;
+ oasys::Time now_;
+ };
+
+ /// The abstract weight function class
+ class WeightFn {
+ public:
+ virtual ~WeightFn() {}
+ virtual u_int32_t operator()(const SearchInfo& info,
+ const Edge* edge) = 0;
+ };
+
+ /// The node class
+ class Node {
+ public:
+ /// Constructor
+ Node(const std::string& id, const _NodeInfo info)
+ : id_(id), info_(info) {}
+
+ ~Node();
+
+ bool del_edge(Edge* edge);
+
+ const std::string& id() const { return id_; }
+
+ const _NodeInfo& info() const { return info_; }
+ _NodeInfo& mutable_info() { return info_; }
+
+ const EdgeVector& out_edges() const { return out_edges_; }
+ const EdgeVector& in_edges() const { return in_edges_; }
+
+ EdgeVector& out_edges() { return out_edges_; }
+ EdgeVector& in_edges() { return in_edges_; }
+
+ private:
+ friend class MultiGraph;
+
+ std::string id_;
+ _NodeInfo info_;
+
+ EdgeVector out_edges_;
+ EdgeVector in_edges_;
+
+ // XXX/demmer see below
+ // friend class MultiGraph::DijkstraCompare;
+
+ /// @{ Dijkstra algorithm state
+ mutable u_int32_t distance_;
+
+ mutable enum {
+ WHITE, GRAY, BLACK
+ } color_;
+
+ mutable Edge* prev_;
+ /// @}
+ };
+
+ /// XXX/demmer this stupid helper function is needed because
+ /// DijkstraCompare can't be made a friend class of Node without
+ /// crashing gcc 3.4
+ static u_int32_t NodeDistance(const Node* n) {
+ return n->distance_;
+ }
+
+ /// Helper class to compute Dijkstra distance
+ struct DijkstraCompare {
+ bool operator()(const Node* a, const Node* b) const {
+ return NodeDistance(a) > NodeDistance(b);
+ }
+ };
+
+ /// The edge class.
+ class Edge {
+ public:
+ /// Constructor
+ Edge(Node* s, Node* d, const _EdgeInfo info)
+ : source_(s), dest_(d), info_(info) {}
+
+ /// Destructor clears contents for debugging purposes
+ ~Edge() { source_ = NULL; dest_ = NULL; }
+
+ Node* source() { return source_; }
+ Node* dest() { return dest_; }
+ const Node* source() const { return source_; }
+ const Node* dest() const { return dest_; }
+
+ const _EdgeInfo& info() const { return info_; }
+ _EdgeInfo& mutable_info() { return info_; }
+
+ protected:
+ Node* source_;
+ Node* dest_;
+ _EdgeInfo info_;
+ };
+
+ typedef oasys::InlineFormatter<_EdgeInfo> EdgeFormatter;
+
+ /// Helper data structure for a vector of nodes
+ class NodeVector : public oasys::Formatter,
+ public std::vector<Node*> {
+ public:
+ int format(char* buf, size_t sz) const;
+ std::string dump() const
+ {
+ char buf[1024];
+ int len = format(buf, sizeof(buf));
+ return std::string(buf, len);
+ }
+ };
+
+ /// Helper data structure for a vector of edges
+ class EdgeVector : public oasys::Formatter,
+ public std::vector<Edge*> {
+ public:
+ int format(char* buf, size_t sz) const;
+ void debug_format(oasys::StringBuffer* buf) const;
+ std::string dump() const
+ {
+ char buf[1024];
+ int len = format(buf, sizeof(buf));
+ return std::string(buf, len);
+ }
+ };
+
+protected:
+ /// Helper function to follow the prev_ links that result from a
+ /// Dijkstra search from a to b and build an EdgeVector
+ bool get_reverse_path(const Node* a, const Node* b, EdgeVector* path);
+
+ /// The vector of all nodes
+ NodeVector nodes_;
+};
+
+} // namespace dtn
+
+#include "MultiGraph.tcc"
+
+#endif /* _MULTIGRAPH_H_ */