1.1 --- a/src/work/marci/leda/leda_graph_wrapper.h Tue May 11 20:20:41 2004 +0000
1.2 +++ b/src/work/marci/leda/leda_graph_wrapper.h Tue May 11 21:26:29 2004 +0000
1.3 @@ -16,42 +16,27 @@
1.4
1.5 #include <hugo/invalid.h>
1.6
1.7 -/// The namespace of HugoLib
1.8 namespace hugo {
1.9
1.10 - // @defgroup empty_graph The LedaGraphWrapper class
1.11 - // @{
1.12 -
1.13 - /// A graph wrapperstructure for wrapping LEDA graphs in HUGO.
1.14 -
1.15 - /// This graph wrapper class wraps LEDA graph and LEDA parametrized graph
1.16 - /// and then the generic algorithms and wrappers of HUGO can be used
1.17 + /// \brief A graph wrapper structure for wrapping LEDA graphs in HUGO.
1.18 + ///
1.19 + /// This graph wrapper class wraps LEDA graphs and LEDA parametrized graphs
1.20 + /// to satisfy HUGO graph concepts.
1.21 + /// Then the generic HUGOlib algorithms and wrappers can be used
1.22 /// with LEDA graphs.
1.23 - /// This class provides all the common features of a grapf structure,
1.24 - /// however completely without implementations or real data structures
1.25 - /// behind the interface.
1.26 - /// All graph algorithms should compile with this class, but it will not
1.27 - /// run properly, of course.
1.28 - ///
1.29 - /// It can be used for checking the interface compatibility,
1.30 - /// or it can serve as a skeleton of a new graph structure.
1.31 - ///
1.32 - /// Also, you will find here the full documentation of a certain graph
1.33 - /// feature, the documentation of a real graph imlementation
1.34 - /// like @ref ListGraph or
1.35 - /// @ref SmartGraph will just refer to this structure.
1.36 + /// \ingroup gwrapper
1.37 template<typename Graph>
1.38 class LedaGraphWrapper
1.39 {
1.40 protected:
1.41 - Graph* _graph;
1.42 - LedaGraphWrapper() : _graph(0) { }
1.43 - void setGraph(Graph& __graph) { _graph=&__graph; }
1.44 + Graph* l_graph;
1.45 + LedaGraphWrapper() : l_graph(0) { }
1.46 + void setGraph(Graph& _l_graph) { l_graph=&_l_graph; }
1.47 public:
1.48
1.49 //LedaGraphWrapper() { }
1.50 - LedaGraphWrapper(Graph& __graph) : _graph(&__graph) { }
1.51 - LedaGraphWrapper(const LedaGraphWrapper &G) : _graph(G._graph) { }
1.52 + LedaGraphWrapper(Graph& _l_graph) : l_graph(&_l_graph) { }
1.53 + LedaGraphWrapper(const LedaGraphWrapper &G) : l_graph(G.l_graph) { }
1.54
1.55 template <typename T> class NodeMap;
1.56 template <typename T> class EdgeMap;
1.57 @@ -72,19 +57,19 @@
1.58 friend class OutEdgeIt;
1.59 protected:
1.60 template <typename T> friend class NodeMap;
1.61 - leda_node _n;
1.62 + leda_node l_n;
1.63 public: //FIXME
1.64 - Node(leda_node __n) : _n(__n) { }
1.65 + Node(leda_node _l_n) : l_n(_l_n) { }
1.66 public:
1.67 /// @warning The default constructor sets the iterator
1.68 /// to an undefined value.
1.69 Node() {} //FIXME
1.70 /// Initialize the iterator to be invalid
1.71 - Node(Invalid) : _n(0) { }
1.72 + Node(Invalid) : l_n(0) { }
1.73 //Node(const Node &) {}
1.74 - bool operator==(Node n) const { return _n==n._n; } //FIXME
1.75 - bool operator!=(Node n) const { return _n!=n._n; } //FIXME
1.76 - operator leda_node () { return _n; }
1.77 + bool operator==(Node n) const { return l_n==n.l_n; } //FIXME
1.78 + bool operator!=(Node n) const { return l_n!=n.l_n; } //FIXME
1.79 + operator leda_node () { return l_n; }
1.80 };
1.81
1.82 /// This iterator goes through each node.
1.83 @@ -96,7 +81,7 @@
1.84 /// Initialize the iterator to be invalid
1.85 NodeIt(Invalid i) : Node(i) {}
1.86 /// Sets the iterator to the first node of \c G.
1.87 - NodeIt(const LedaGraphWrapper &G) : Node(G._graph->first_node()) { }
1.88 + NodeIt(const LedaGraphWrapper &G) : Node(G.l_graph->first_node()) { }
1.89 //NodeIt(const NodeIt &) {} //FIXME
1.90 };
1.91
1.92 @@ -105,19 +90,19 @@
1.93 friend class LedaGraphWrapper;
1.94 protected:
1.95 template <typename T> friend class EdgeMap;
1.96 - leda_edge _e;
1.97 + leda_edge l_e;
1.98 public: //FIXME
1.99 - Edge(leda_edge __e) : _e(__e) { }
1.100 + Edge(leda_edge _l_e) : l_e(_l_e) { }
1.101 public:
1.102 /// @warning The default constructor sets the iterator
1.103 /// to an undefined value.
1.104 Edge() {} //FIXME
1.105 /// Initialize the iterator to be invalid
1.106 - Edge(Invalid) : _e(0) {}
1.107 + Edge(Invalid) : l_e(0) {}
1.108 //Edge(const Edge &) {}
1.109 - bool operator==(Edge e) const { return _e==e._e; } //FIXME
1.110 - bool operator!=(Edge e) const { return _e!=e._e; } //FIXME
1.111 - operator leda_edge () { return _e; }
1.112 + bool operator==(Edge e) const { return l_e==e.l_e; } //FIXME
1.113 + bool operator!=(Edge e) const { return l_e!=e.l_e; } //FIXME
1.114 + operator leda_edge () { return l_e; }
1.115 };
1.116
1.117 /// This iterator goes trought the outgoing edges of a certain graph.
1.118 @@ -135,7 +120,7 @@
1.119 /// node
1.120 ///@param n the node
1.121 ///@param G the graph
1.122 - OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_adj_edge(n._n)) { }
1.123 + OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_adj_edge(n.l_n)) { }
1.124 };
1.125
1.126 class InEdgeIt : public Edge {
1.127 @@ -145,7 +130,7 @@
1.128 InEdgeIt() {}
1.129 /// Initialize the iterator to be invalid
1.130 InEdgeIt(Invalid i) : Edge(i) {}
1.131 - InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_in_edge(n._n)) { }
1.132 + InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_in_edge(n.l_n)) { }
1.133 };
1.134
1.135 // class SymEdgeIt : public Edge {};
1.136 @@ -156,7 +141,7 @@
1.137 EdgeIt() {}
1.138 /// Initialize the iterator to be invalid
1.139 EdgeIt(Invalid i) : Edge(i) {}
1.140 - EdgeIt(const LedaGraphWrapper & G) : Edge(G._graph->first_edge()) { }
1.141 + EdgeIt(const LedaGraphWrapper & G) : Edge(G.l_graph->first_edge()) { }
1.142 };
1.143
1.144 /// First node of the graph.
1.145 @@ -189,23 +174,23 @@
1.146
1.147 /// Go to the next node.
1.148 NodeIt &next(NodeIt &i) const {
1.149 - i._n=_graph->succ_node(i._n);
1.150 + i.l_n=l_graph->succ_node(i.l_n);
1.151 return i;
1.152 }
1.153 /// Go to the next incoming edge.
1.154 InEdgeIt &next(InEdgeIt &i) const {
1.155 - i._e=_graph->in_succ(i._e);
1.156 + i.l_e=l_graph->in_succ(i.l_e);
1.157 return i;
1.158 }
1.159 /// Go to the next outgoing edge.
1.160 OutEdgeIt &next(OutEdgeIt &i) const {
1.161 - i._e=_graph->adj_succ(i._e);
1.162 + i.l_e=l_graph->adj_succ(i.l_e);
1.163 return i;
1.164 }
1.165 //SymEdgeIt &next(SymEdgeIt &) const {}
1.166 /// Go to the next edge.
1.167 EdgeIt &next(EdgeIt &i) const {
1.168 - i._e=_graph->succ_edge(i._e);
1.169 + i.l_e=l_graph->succ_edge(i.l_e);
1.170 return i;
1.171 }
1.172
1.173 @@ -225,11 +210,11 @@
1.174
1.175 ///Gives back the head node of an edge.
1.176 Node head(Edge e) const {
1.177 - return Node(_graph->target(e._e));
1.178 + return Node(l_graph->target(e.l_e));
1.179 }
1.180 ///Gives back the tail node of an edge.
1.181 Node tail(Edge e) const {
1.182 - return Node(_graph->source(e._e));
1.183 + return Node(l_graph->source(e.l_e));
1.184 }
1.185
1.186 Node aNode(InEdgeIt e) const { return head(e); }
1.187 @@ -241,30 +226,30 @@
1.188 // Node bNode(SymEdgeIt) const {}
1.189
1.190 /// Checks if a node iterator is valid
1.191 - bool valid(Node n) const { return n._n; }
1.192 + bool valid(Node n) const { return n.l_n; }
1.193 /// Checks if an edge iterator is valid
1.194 - bool valid(Edge e) const { return e._e; }
1.195 + bool valid(Edge e) const { return e.l_e; }
1.196
1.197 ///Gives back the \e id of a node.
1.198 - int id(Node n) const { return n._n->id(); }
1.199 + int id(Node n) const { return n.l_n->id(); }
1.200 ///Gives back the \e id of an edge.
1.201 - int id(Edge e) const { return e._e->id(); }
1.202 + int id(Edge e) const { return e.l_e->id(); }
1.203
1.204 //void setInvalid(Node &) const {};
1.205 //void setInvalid(Edge &) const {};
1.206
1.207 - Node addNode() const { return Node(_graph->new_node()); }
1.208 + Node addNode() const { return Node(l_graph->new_node()); }
1.209 Edge addEdge(Node tail, Node head) const {
1.210 - return Edge(_graph->new_edge(tail._n, head._n));
1.211 + return Edge(l_graph->new_edge(tail.l_n, head.l_n));
1.212 }
1.213
1.214 - void erase(Node n) const { _graph->del_node(n._n); }
1.215 - void erase(Edge e) const { _graph->del_edge(e._e); }
1.216 + void erase(Node n) const { l_graph->del_node(n.l_n); }
1.217 + void erase(Edge e) const { l_graph->del_edge(e.l_e); }
1.218
1.219 - void clear() const { _graph->clear(); }
1.220 + void clear() const { l_graph->clear(); }
1.221
1.222 - int nodeNum() const { return _graph->number_of_nodes(); }
1.223 - int edgeNum() const { return _graph->number_of_edges(); }
1.224 + int nodeNum() const { return l_graph->number_of_nodes(); }
1.225 + int edgeNum() const { return l_graph->number_of_edges(); }
1.226
1.227 ///Read/write map from the nodes to type \c T.
1.228 template<typename T> class NodeMap
1.229 @@ -274,16 +259,16 @@
1.230 typedef T ValueType;
1.231 typedef Node KeyType;
1.232
1.233 - NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
1.234 - NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
1.235 + NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {}
1.236 + NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
1.237
1.238 - void set(Node i, T t) { leda_stuff[i._n]=t; }
1.239 - T get(Node i) const { return leda_stuff[i._n]; } //FIXME: Is it necessary
1.240 - T &operator[](Node i) { return leda_stuff[i._n]; }
1.241 - const T &operator[](Node i) const { return leda_stuff[i._n]; }
1.242 + void set(Node i, T t) { leda_stuff[i.l_n]=t; }
1.243 + T get(Node i) const { return leda_stuff[i.l_n]; } //FIXME: Is it necessary
1.244 + T &operator[](Node i) { return leda_stuff[i.l_n]; }
1.245 + const T &operator[](Node i) const { return leda_stuff[i.l_n]; }
1.246
1.247 void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
1.248 - //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); } //FIXME: Is it necessary
1.249 + //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary
1.250 };
1.251
1.252 ///Read/write map from the edges to type \c T.
1.253 @@ -294,20 +279,25 @@
1.254 typedef T ValueType;
1.255 typedef Edge KeyType;
1.256
1.257 - EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
1.258 - EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
1.259 + EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {}
1.260 + EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
1.261
1.262 - void set(Edge i, T t) { leda_stuff[i._e]=t; }
1.263 - T get(Edge i) const { return leda_stuff[i._e]; } //FIXME: Is it necessary
1.264 - T &operator[](Edge i) { return leda_stuff[i._e]; }
1.265 - const T &operator[](Edge i) const { return leda_stuff[i._e]; }
1.266 + void set(Edge i, T t) { leda_stuff[i.l_e]=t; }
1.267 + T get(Edge i) const { return leda_stuff[i.l_e]; } //FIXME: Is it necessary
1.268 + T &operator[](Edge i) { return leda_stuff[i.l_e]; }
1.269 + const T &operator[](Edge i) const { return leda_stuff[i.l_e]; }
1.270
1.271 void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
1.272 - //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); } //FIXME: Is it necessary
1.273 + //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary
1.274 };
1.275
1.276 };
1.277
1.278 +
1.279 + /// \brief LEDA graph template.
1.280 + ///
1.281 + /// This graph stucture uses LEDA graphs for physical storage.
1.282 + /// \ingroup graphs
1.283 template<typename Graph>
1.284 class LedaGraph : public LedaGraphWrapper<Graph> {
1.285 typedef LedaGraphWrapper<Graph> Parent;
1.286 @@ -319,26 +309,6 @@
1.287 }
1.288 };
1.289
1.290 - // @}
1.291 -
1.292 } //namespace hugo
1.293
1.294 -
1.295 -
1.296 -// class EmptyBipGraph : public EmptyGraph
1.297 -// {
1.298 -// class ANode {};
1.299 -// class BNode {};
1.300 -
1.301 -// ANode &next(ANode &) {}
1.302 -// BNode &next(BNode &) {}
1.303 -
1.304 -// ANode &getFirst(ANode &) const {}
1.305 -// BNode &getFirst(BNode &) const {}
1.306 -
1.307 -// enum NodeClass { A = 0, B = 1 };
1.308 -// NodeClass getClass(Node n) {}
1.309 -
1.310 -// }
1.311 -
1.312 #endif // HUGO_LEDA_GRAPH_WRAPPER_H