00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef _MULTIGRAPH_H_
00018 #define _MULTIGRAPH_H_
00019
00020 #include <vector>
00021 #include <oasys/debug/InlineFormatter.h>
00022 #include <oasys/debug/Formatter.h>
00023 #include <oasys/debug/Logger.h>
00024 #include <oasys/util/StringBuffer.h>
00025 #include <oasys/util/Time.h>
00026
00027 namespace dtn {
00028
00029 class Bundle;
00030
00034 template <typename _NodeInfo, typename _EdgeInfo>
00035 class MultiGraph : public oasys::Formatter, public oasys::Logger {
00036 public:
00038 class Edge;
00039 class EdgeVector;
00040 class Node;
00041 class NodeVector;
00042 class WeightFn;
00044
00046 MultiGraph();
00047
00049 ~MultiGraph();
00050
00052 Node* add_node(const std::string& id, const _NodeInfo& info);
00053
00055 Node* find_node(const std::string& id) const;
00056
00058 bool del_node(const std::string& id);
00059
00061 Edge* add_edge(Node* a, Node* b, const _EdgeInfo& info);
00062
00064 Edge* find_edge(const Node* a, const Node* b, const _EdgeInfo& info);
00065
00068 bool del_edge(Node* node, Edge* edge);
00069
00074 void shortest_path(const Node* a, const Node* b,
00075 EdgeVector* path, WeightFn* weight_fn,
00076 Bundle* bundle = NULL);
00077
00080 Edge* best_next_hop(const Node* a, const Node* b, WeightFn* weight_fn,
00081 Bundle* bundle = NULL);
00082
00084 void clear();
00085
00087 int format(char* buf, size_t sz) const;
00088
00090 std::string dump() const
00091 {
00092 char buf[1024];
00093 int len = format(buf, sizeof(buf));
00094 return std::string(buf, len);
00095 }
00096
00098 const NodeVector& nodes() { return nodes_; }
00099
00103 struct SearchInfo {
00104 SearchInfo(Bundle* bundle);
00105
00106 Bundle* bundle_;
00107 oasys::Time now_;
00108 };
00109
00111 class WeightFn {
00112 public:
00113 virtual ~WeightFn() {}
00114 virtual u_int32_t operator()(const SearchInfo& info,
00115 const Edge* edge) = 0;
00116 };
00117
00119 class Node {
00120 public:
00122 Node(const std::string& id, const _NodeInfo info)
00123 : id_(id), info_(info) {}
00124
00125 ~Node();
00126
00127 bool del_edge(Edge* edge);
00128
00129 const std::string& id() const { return id_; }
00130
00131 const _NodeInfo& info() const { return info_; }
00132 _NodeInfo& mutable_info() { return info_; }
00133
00134 const EdgeVector& out_edges() const { return out_edges_; }
00135 const EdgeVector& in_edges() const { return in_edges_; }
00136
00137 EdgeVector& out_edges() { return out_edges_; }
00138 EdgeVector& in_edges() { return in_edges_; }
00139
00140 private:
00141 friend class MultiGraph;
00142
00143 std::string id_;
00144 _NodeInfo info_;
00145
00146 EdgeVector out_edges_;
00147 EdgeVector in_edges_;
00148
00149
00150
00151
00153 mutable u_int32_t distance_;
00154
00155 mutable enum {
00156 WHITE, GRAY, BLACK
00157 } color_;
00158
00159 mutable Edge* prev_;
00161 };
00162
00166 static u_int32_t NodeDistance(const Node* n) {
00167 return n->distance_;
00168 }
00169
00171 struct DijkstraCompare {
00172 bool operator()(const Node* a, const Node* b) const {
00173 return NodeDistance(a) > NodeDistance(b);
00174 }
00175 };
00176
00178 class Edge {
00179 public:
00181 Edge(Node* s, Node* d, const _EdgeInfo info)
00182 : source_(s), dest_(d), info_(info) {}
00183
00185 ~Edge() { source_ = NULL; dest_ = NULL; }
00186
00187 Node* source() { return source_; }
00188 Node* dest() { return dest_; }
00189 const Node* source() const { return source_; }
00190 const Node* dest() const { return dest_; }
00191
00192 const _EdgeInfo& info() const { return info_; }
00193 _EdgeInfo& mutable_info() { return info_; }
00194
00195 protected:
00196 Node* source_;
00197 Node* dest_;
00198 _EdgeInfo info_;
00199 };
00200
00201 typedef oasys::InlineFormatter<_EdgeInfo> EdgeFormatter;
00202
00204 class NodeVector : public oasys::Formatter,
00205 public std::vector<Node*> {
00206 public:
00207 int format(char* buf, size_t sz) const;
00208 std::string dump() const
00209 {
00210 char buf[1024];
00211 int len = format(buf, sizeof(buf));
00212 return std::string(buf, len);
00213 }
00214 };
00215
00217 class EdgeVector : public oasys::Formatter,
00218 public std::vector<Edge*> {
00219 public:
00220 int format(char* buf, size_t sz) const;
00221 void debug_format(oasys::StringBuffer* buf) const;
00222 std::string dump() const
00223 {
00224 char buf[1024];
00225 int len = format(buf, sizeof(buf));
00226 return std::string(buf, len);
00227 }
00228 };
00229
00230 protected:
00233 bool get_reverse_path(const Node* a, const Node* b, EdgeVector* path);
00234
00236 NodeVector nodes_;
00237 };
00238
00239 }
00240
00241 #include "MultiGraph.tcc"
00242
00243 #endif