1.1 --- a/src/work/marci/leda/leda_graph_wrapper.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,384 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#ifndef LEMON_LEDA_GRAPH_WRAPPER_H
1.6 -#define LEMON_LEDA_GRAPH_WRAPPER_H
1.7 -
1.8 -#include <LEDA/graph.h>
1.9 -#include <LEDA/node_array.h>
1.10 -#include <LEDA/edge_array.h>
1.11 -#include <LEDA/node_map.h>
1.12 -#include <LEDA/edge_map.h>
1.13 -//#include <LEDA/graph_alg.h>
1.14 -//#include <LEDA/dimacs.h>
1.15 -
1.16 -//#if defined(LEDA_NAMESPACE)
1.17 -//using namespace leda;
1.18 -//#endif
1.19 -
1.20 -#include <lemon/invalid.h>
1.21 -
1.22 -namespace lemon {
1.23 -
1.24 - /// \brief A graph wrapper structure for wrapping LEDA graphs in LEMON.
1.25 - ///
1.26 - /// This graph wrapper class wraps LEDA graphs and LEDA parametrized graphs
1.27 - /// to satisfy LEMON graph concepts.
1.28 - /// Then the generic LEMON algorithms and wrappers can be used
1.29 - /// with LEDA graphs.
1.30 - /// \ingroup gwrapper
1.31 - template<typename Graph>
1.32 - class LedaGraphWrapper
1.33 - {
1.34 - protected:
1.35 - Graph* l_graph;
1.36 - LedaGraphWrapper() : l_graph(0) { }
1.37 - void setGraph(Graph& _l_graph) { l_graph=&_l_graph; }
1.38 - public:
1.39 -
1.40 - /// Constructor for wrapping LEDA graphs.
1.41 - LedaGraphWrapper(Graph& _l_graph) : l_graph(&_l_graph) { }
1.42 - /// Copy constructor
1.43 - LedaGraphWrapper(const LedaGraphWrapper &g) : l_graph(g.l_graph) { }
1.44 -
1.45 - template <typename T> class NodeMap;
1.46 - template <typename T> class EdgeMap;
1.47 - template <typename T> class NodeMapWrapper;
1.48 - template <typename T> class EdgeMapWrapper;
1.49 -
1.50 - class Node;
1.51 - class NodeIt;
1.52 - class Edge;
1.53 - class EdgeIt;
1.54 - class OutEdgeIt;
1.55 - class InEdgeIt;
1.56 -
1.57 - /// Trivial node-iterator
1.58 - class Node {
1.59 - friend class LedaGraphWrapper<Graph>;
1.60 - //friend class Edge;
1.61 - friend class EdgeIt;
1.62 - friend class InEdgeIt;
1.63 - friend class OutEdgeIt;
1.64 - protected:
1.65 - template <typename T> friend class NodeMap;
1.66 - leda_node l_n;
1.67 - public: //FIXME
1.68 - Node(leda_node _l_n) : l_n(_l_n) { }
1.69 - public:
1.70 - /// @warning The default constructor sets the iterator
1.71 - /// to an undefined value.
1.72 - Node() { } //FIXME
1.73 - /// Initialize the iterator to be invalid
1.74 - Node(Invalid) : l_n(0) { }
1.75 - //Node(const Node &) {}
1.76 - bool operator==(Node n) const { return l_n==n.l_n; } //FIXME
1.77 - bool operator!=(Node n) const { return l_n!=n.l_n; } //FIXME
1.78 - operator leda_node () { return l_n; }
1.79 - };
1.80 -
1.81 - /// This iterator goes through each node.
1.82 - class NodeIt : public Node {
1.83 - public:
1.84 - /// @warning The default constructor sets the iterator
1.85 - /// to an undefined value.
1.86 - NodeIt() { } //FIXME
1.87 - /// Initialize the iterator to be invalid
1.88 - NodeIt(Invalid i) : Node(i) { }
1.89 - /// Sets the iterator to the first node of \c G.
1.90 - NodeIt(const LedaGraphWrapper &G) : Node(G.l_graph->first_node()) { }
1.91 - //NodeIt(const NodeIt &) {} //FIXME
1.92 - };
1.93 -
1.94 - /// Trivial edge-iterator.
1.95 - class Edge {
1.96 - friend class LedaGraphWrapper;
1.97 - protected:
1.98 - template <typename T> friend class EdgeMap;
1.99 - leda_edge l_e;
1.100 - public: //FIXME
1.101 - Edge(leda_edge _l_e) : l_e(_l_e) { }
1.102 - public:
1.103 - /// @warning The default constructor sets the iterator
1.104 - /// to an undefined value.
1.105 - Edge() { } //FIXME
1.106 - /// Initialize the iterator to be invalid
1.107 - Edge(Invalid) : l_e(0) { }
1.108 - //Edge(const Edge &) {}
1.109 - bool operator==(Edge e) const { return l_e==e.l_e; } //FIXME
1.110 - bool operator!=(Edge e) const { return l_e!=e.l_e; } //FIXME
1.111 - operator leda_edge () { return l_e; }
1.112 - };
1.113 -
1.114 - /// This iterator goes trought the outgoing edges of a certain node.
1.115 - class OutEdgeIt : public Edge {
1.116 - public:
1.117 - /// @warning The default constructor sets the iterator
1.118 - /// to an undefined value.
1.119 - OutEdgeIt() { }
1.120 - /// Initialize the iterator to be invalid
1.121 - OutEdgeIt(Invalid i) : Edge(i) { }
1.122 - /// This constructor sets the iterator to first outgoing edge.
1.123 -
1.124 - /// This constructor set the iterator to the first outgoing edge of
1.125 - /// node
1.126 - ///@param n the node
1.127 - ///@param G the graph
1.128 - OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_adj_edge(n.l_n)) { }
1.129 - };
1.130 -
1.131 - /// This iterator goes trought the incoming edges of a certain node.
1.132 - class InEdgeIt : public Edge {
1.133 - public:
1.134 - /// @warning The default constructor sets the iterator
1.135 - /// to an undefined value.
1.136 - InEdgeIt() { }
1.137 - /// Initialize the iterator to be invalid
1.138 - InEdgeIt(Invalid i) : Edge(i) { }
1.139 - InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_in_edge(n.l_n)) { }
1.140 - };
1.141 -
1.142 - // class SymEdgeIt : public Edge {};
1.143 -
1.144 - /// This iterator goes trought the edges of the graph.
1.145 - class EdgeIt : public Edge {
1.146 - public:
1.147 - /// @warning The default constructor sets the iterator
1.148 - /// to an undefined value.
1.149 - EdgeIt() { }
1.150 - /// Initialize the iterator to be invalid
1.151 - EdgeIt(Invalid i) : Edge(i) { }
1.152 - EdgeIt(const LedaGraphWrapper & G) : Edge(G.l_graph->first_edge()) { }
1.153 - };
1.154 -
1.155 - /// First node of the graph.
1.156 - ///
1.157 - /// \post \c i and the return value will be the first node.
1.158 - ///
1.159 - NodeIt &first(NodeIt &i) const { i=NodeIt(*this); return i; }
1.160 -
1.161 - /// The first outgoing edge.
1.162 - InEdgeIt &first(InEdgeIt &i, Node n) const {
1.163 - i=InEdgeIt(*this, n);
1.164 - return i;
1.165 - }
1.166 - /// The first incoming edge.
1.167 - OutEdgeIt &first(OutEdgeIt &i, Node n) const {
1.168 - i=OutEdgeIt(*this, n);
1.169 - return i;
1.170 - }
1.171 - // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
1.172 - /// The first edge of the graph.
1.173 - EdgeIt &first(EdgeIt &i) const {
1.174 - i=EdgeIt(*this);
1.175 - return i; }
1.176 -
1.177 -// Node getNext(Node) const {}
1.178 -// InEdgeIt getNext(InEdgeIt) const {}
1.179 -// OutEdgeIt getNext(OutEdgeIt) const {}
1.180 -// //SymEdgeIt getNext(SymEdgeIt) const {}
1.181 -// EdgeIt getNext(EdgeIt) const {}
1.182 -
1.183 - /// Go to the next node.
1.184 - NodeIt &next(NodeIt &i) const {
1.185 - i.l_n=l_graph->succ_node(i.l_n);
1.186 - return i;
1.187 - }
1.188 - /// Go to the next incoming edge.
1.189 - InEdgeIt &next(InEdgeIt &i) const {
1.190 - i.l_e=l_graph->in_succ(i.l_e);
1.191 - return i;
1.192 - }
1.193 - /// Go to the next outgoing edge.
1.194 - OutEdgeIt &next(OutEdgeIt &i) const {
1.195 - i.l_e=l_graph->adj_succ(i.l_e);
1.196 - return i;
1.197 - }
1.198 - //SymEdgeIt &next(SymEdgeIt &) const {}
1.199 - /// Go to the next edge.
1.200 - EdgeIt &next(EdgeIt &i) const {
1.201 - i.l_e=l_graph->succ_edge(i.l_e);
1.202 - return i;
1.203 - }
1.204 -
1.205 -// template< typename It >
1.206 -// It first() const {
1.207 -// It e;
1.208 -// first(e);
1.209 -// return e;
1.210 -// }
1.211 -
1.212 -// template< typename It >
1.213 -// It first(Node v) const {
1.214 -// It e;
1.215 -// first(e, v);
1.216 -// return e;
1.217 -// }
1.218 -
1.219 - ///Gives back the target node of an edge.
1.220 - Node target(Edge e) const {
1.221 - return Node(l_graph->target(e.l_e));
1.222 - }
1.223 - ///Gives back the source node of an edge.
1.224 - Node source(Edge e) const {
1.225 - return Node(l_graph->source(e.l_e));
1.226 - }
1.227 -
1.228 - Node aNode(InEdgeIt e) const { return target(e); }
1.229 - Node aNode(OutEdgeIt e) const { return source(e); }
1.230 - // Node aNode(SymEdgeIt) const {}
1.231 -
1.232 - Node bNode(InEdgeIt e) const { return source(e); }
1.233 - Node bNode(OutEdgeIt e) const { return target(e); }
1.234 - // Node bNode(SymEdgeIt) const {}
1.235 -
1.236 - /// Checks if a node iterator is valid
1.237 - bool valid(Node n) const { return n.l_n; }
1.238 - /// Checks if an edge iterator is valid
1.239 - bool valid(Edge e) const { return e.l_e; }
1.240 -
1.241 - ///Gives back the \e id of a node.
1.242 - int id(Node n) const { return n.l_n->id(); }
1.243 - ///Gives back the \e id of an edge.
1.244 - int id(Edge e) const { return e.l_e->id(); }
1.245 -
1.246 - //void setInvalid(Node &) const {};
1.247 - //void setInvalid(Edge &) const {};
1.248 -
1.249 - Node addNode() const { return Node(l_graph->new_node()); }
1.250 - Edge addEdge(Node source, Node target) const {
1.251 - return Edge(l_graph->new_edge(source.l_n, target.l_n));
1.252 - }
1.253 -
1.254 - void erase(Node n) const { l_graph->del_node(n.l_n); }
1.255 - void erase(Edge e) const { l_graph->del_edge(e.l_e); }
1.256 -
1.257 - void clear() const { l_graph->clear(); }
1.258 -
1.259 - int nodeNum() const { return l_graph->number_of_nodes(); }
1.260 - int edgeNum() const { return l_graph->number_of_edges(); }
1.261 -
1.262 - /// Read/write map from the nodes to type \c T.
1.263 - template<typename T> class NodeMap
1.264 - {
1.265 - leda_node_map<T> leda_stuff;
1.266 - public:
1.267 - typedef T Value;
1.268 - typedef Node Key;
1.269 -
1.270 - NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {}
1.271 - NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
1.272 -
1.273 - void set(Node i, T t) { leda_stuff[i.l_n]=t; }
1.274 - T get(Node i) const { return leda_stuff[i.l_n]; } //FIXME: Is it necessary
1.275 - T &operator[](Node i) { return leda_stuff[i.l_n]; }
1.276 - const T &operator[](Node i) const { return leda_stuff[i.l_n]; }
1.277 -
1.278 - void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
1.279 - //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary
1.280 - };
1.281 -
1.282 - /// Read/write map from the edges to type \c T.
1.283 - template<typename T> class EdgeMap
1.284 - {
1.285 - leda_edge_map<T> leda_stuff;
1.286 - public:
1.287 - typedef T Value;
1.288 - typedef Edge Key;
1.289 -
1.290 - EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {}
1.291 - EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
1.292 -
1.293 - void set(Edge i, T t) { leda_stuff[i.l_e]=t; }
1.294 - T get(Edge i) const { return leda_stuff[i.l_e]; } //FIXME: Is it necessary
1.295 - T &operator[](Edge i) { return leda_stuff[i.l_e]; }
1.296 - const T &operator[](Edge i) const { return leda_stuff[i.l_e]; }
1.297 -
1.298 - void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
1.299 - //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary
1.300 - };
1.301 -
1.302 -
1.303 - /// This class is to wrap existing
1.304 - /// LEDA node-maps to LEMON ones.
1.305 - template<typename T> class NodeMapWrapper
1.306 - {
1.307 - leda_node_array<T>* leda_stuff;
1.308 - public:
1.309 - typedef T Value;
1.310 - typedef Node Key;
1.311 -
1.312 - NodeMapWrapper(leda_node_array<T>& _leda_stuff) :
1.313 - leda_stuff(&_leda_stuff) { }
1.314 - //NodeMap(leda_node_map& &G, T t) : leda_stuff(*(G.l_graph), t) {}
1.315 -
1.316 - void set(Node i, T t) { (*leda_stuff)[i.l_n]=t; }
1.317 - //T get(Node i) const { return (*leda_stuff)[i.l_n]; } //FIXME: Is it necessary
1.318 - T &operator[](Node i) { return (*leda_stuff)[i.l_n]; }
1.319 - const T &operator[](Node i) const { return (*leda_stuff)[i.l_n]; }
1.320 -
1.321 - void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
1.322 - //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary
1.323 - };
1.324 -
1.325 - /// This class is to wrap existing
1.326 - /// LEDA edge-maps to LEMON ones.
1.327 - template<typename T> class EdgeMapWrapper
1.328 - {
1.329 - leda_edge_array<T>* leda_stuff;
1.330 - public:
1.331 - typedef T Value;
1.332 - typedef Edge Key;
1.333 -
1.334 - EdgeMapWrapper(leda_edge_array<T>& _leda_stuff) :
1.335 - leda_stuff(_leda_stuff) { }
1.336 - //EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
1.337 -
1.338 - void set(Edge i, T t) { (*leda_stuff)[i.l_e]=t; }
1.339 - //T get(Edge i) const { return (*leda_stuff)[i.l_e]; } //FIXME: Is it necessary
1.340 - T &operator[](Edge i) { return (*leda_stuff)[i.l_e]; }
1.341 - const T &operator[](Edge i) const { return (*leda_stuff)[i.l_e]; }
1.342 -
1.343 - void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
1.344 - //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary
1.345 - };
1.346 -
1.347 - /// This class is used for access node-data of
1.348 - /// LEDA parametrized graphs.
1.349 - template<typename T>
1.350 - class NodeDataMap : public NodeMapWrapper<T>
1.351 - {
1.352 - public:
1.353 - NodeDataMap(LedaGraphWrapper<Graph>& LGW) :
1.354 - NodeMapWrapper<T>(*(LGW._g_graph).node_data()) { }
1.355 - };
1.356 -
1.357 - /// This class is used for access edge-data of
1.358 - /// LEDA parametrized graphs.
1.359 - template<typename T>
1.360 - class EdgeDataMap : public EdgeMapWrapper<T>
1.361 - {
1.362 - public:
1.363 - EdgeDataMap(LedaGraphWrapper<Graph>& LGW) :
1.364 - EdgeMapWrapper<T>(*(LGW._g_graph).edge_data()) { }
1.365 - };
1.366 -
1.367 - };
1.368 -
1.369 -
1.370 - /// \brief LEDA graph template.
1.371 - ///
1.372 - /// This graph stucture uses LEDA graphs for physical storage.
1.373 - /// \ingroup graphs
1.374 - template<typename Graph>
1.375 - class LedaGraph : public LedaGraphWrapper<Graph> {
1.376 - typedef LedaGraphWrapper<Graph> Parent;
1.377 - protected:
1.378 - Graph gr;
1.379 - public:
1.380 - LedaGraph() {
1.381 - Parent::setGraph(gr);
1.382 - }
1.383 - };
1.384 -
1.385 -} //namespace lemon
1.386 -
1.387 -#endif // LEMON_LEDA_GRAPH_WRAPPER_H