1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/leda_graph_wrapper.h Tue Mar 16 15:27:20 2004 +0000
1.3 @@ -0,0 +1,316 @@
1.4 +// -*- c++ -*-
1.5 +#ifndef HUGO_LEDA_GRAPH_WRAPPER_H
1.6 +#define HUGO_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 <invalid.h>
1.21 +
1.22 +/// The namespace of HugoLib
1.23 +namespace hugo {
1.24 +
1.25 + // @defgroup empty_graph The LedaGraphWrapper class
1.26 + // @{
1.27 +
1.28 + /// An empty graph class.
1.29 +
1.30 + /// This class provides all the common features of a grapf structure,
1.31 + /// however completely without implementations or real data structures
1.32 + /// behind the interface.
1.33 + /// All graph algorithms should compile with this class, but it will not
1.34 + /// run properly, of course.
1.35 + ///
1.36 + /// It can be used for checking the interface compatibility,
1.37 + /// or it can serve as a skeleton of a new graph structure.
1.38 + ///
1.39 + /// Also, you will find here the full documentation of a certain graph
1.40 + /// feature, the documentation of a real graph imlementation
1.41 + /// like @ref ListGraph or
1.42 + /// @ref SmartGraph will just refer to this structure.
1.43 + template<typename Graph>
1.44 + class LedaGraphWrapper
1.45 + {
1.46 + Graph* _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 +
1.53 + template <typename T> class NodeMap;
1.54 + template <typename T> class EdgeMap;
1.55 +
1.56 + /// The base type of the node iterators.
1.57 + class Node {
1.58 + friend class LedaGraphWrapper;
1.59 + //friend class Edge;
1.60 + friend class EdgeIt;
1.61 + friend class InEdgeIt;
1.62 + friend class OutEdgeIt;
1.63 + protected:
1.64 + template <typename T> friend class NodeMap;
1.65 + leda_node _n;
1.66 + Node(leda_node __n) : _n(__n) { }
1.67 + public:
1.68 + /// @warning The default constructor sets the iterator
1.69 + /// to an undefined value.
1.70 + Node() {} //FIXME
1.71 + /// Initialize the iterator to be invalid
1.72 + Node(Invalid) : _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 + };
1.77 +
1.78 + /// This iterator goes through each node.
1.79 + class NodeIt : public Node {
1.80 + public:
1.81 + /// @warning The default constructor sets the iterator
1.82 + /// to an undefined value.
1.83 + NodeIt() {} //FIXME
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 NodeIt &) {} //FIXME
1.89 + };
1.90 +
1.91 + /// The base type of the edge iterators.
1.92 + class Edge {
1.93 + friend class LedaGraphWrapper;
1.94 + protected:
1.95 + template <typename T> friend class EdgeMap;
1.96 + leda_edge _e;
1.97 + Edge(leda_edge __e) : _e(__e) { }
1.98 + public:
1.99 + /// @warning The default constructor sets the iterator
1.100 + /// to an undefined value.
1.101 + Edge() {} //FIXME
1.102 + /// Initialize the iterator to be invalid
1.103 + Edge(Invalid) : _e(0) {}
1.104 + //Edge(const Edge &) {}
1.105 + bool operator==(Edge e) const { return _e==e._e; } //FIXME
1.106 + bool operator!=(Edge e) const { return _e!=e._e; } //FIXME
1.107 + };
1.108 +
1.109 + /// This iterator goes trought the outgoing edges of a certain graph.
1.110 +
1.111 + class OutEdgeIt : public Edge {
1.112 + public:
1.113 + /// @warning The default constructor sets the iterator
1.114 + /// to an undefined value.
1.115 + OutEdgeIt() {}
1.116 + /// Initialize the iterator to be invalid
1.117 + OutEdgeIt(Invalid i) : Edge(i) {}
1.118 + /// This constructor sets the iterator to first outgoing edge.
1.119 +
1.120 + /// This constructor set the iterator to the first outgoing edge of
1.121 + /// node
1.122 + ///@param n the node
1.123 + ///@param G the graph
1.124 + OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_adj_edge(n._n)) { }
1.125 + };
1.126 +
1.127 + class InEdgeIt : public Edge {
1.128 + public:
1.129 + /// @warning The default constructor sets the iterator
1.130 + /// to an undefined value.
1.131 + InEdgeIt() {}
1.132 + /// Initialize the iterator to be invalid
1.133 + InEdgeIt(Invalid i) : Edge(i) {}
1.134 + InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_in_edge(n._n)) { }
1.135 + };
1.136 +
1.137 + // class SymEdgeIt : public Edge {};
1.138 + class EdgeIt : public Edge {
1.139 + public:
1.140 + /// @warning The default constructor sets the iterator
1.141 + /// to an undefined value.
1.142 + EdgeIt() {}
1.143 + /// Initialize the iterator to be invalid
1.144 + EdgeIt(Invalid i) : Edge(i) {}
1.145 + EdgeIt(const LedaGraphWrapper & G) : Edge(G._graph->first_edge()) { }
1.146 + };
1.147 +
1.148 + /// First node of the graph.
1.149 +
1.150 + /// \post \c i and the return value will be the first node.
1.151 + ///
1.152 + NodeIt &first(NodeIt &i) const { i=NodeIt(*this); return i; }
1.153 +
1.154 + /// The first outgoing edge.
1.155 + InEdgeIt &first(InEdgeIt &i, Node n) const {
1.156 + i=InEdgeIt(*this, n);
1.157 + return i;
1.158 + }
1.159 + /// The first incoming edge.
1.160 + OutEdgeIt &first(OutEdgeIt &i, Node n) const {
1.161 + i=OutEdgeIt(*this, n);
1.162 + return i;
1.163 + }
1.164 + // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
1.165 + /// The first edge of the Graph.
1.166 + EdgeIt &first(EdgeIt &i) const {
1.167 + i=EdgeIt(*this);
1.168 + return i; }
1.169 +
1.170 +// Node getNext(Node) const {}
1.171 +// InEdgeIt getNext(InEdgeIt) const {}
1.172 +// OutEdgeIt getNext(OutEdgeIt) const {}
1.173 +// //SymEdgeIt getNext(SymEdgeIt) const {}
1.174 +// EdgeIt getNext(EdgeIt) const {}
1.175 +
1.176 + /// Go to the next node.
1.177 + NodeIt &next(NodeIt &i) const {
1.178 + i._n=_graph->succ_node(i._n);
1.179 + return i;
1.180 + }
1.181 + /// Go to the next incoming edge.
1.182 + InEdgeIt &next(InEdgeIt &i) const {
1.183 + i._e=_graph->in_succ(i._e);
1.184 + return i;
1.185 + }
1.186 + /// Go to the next outgoing edge.
1.187 + OutEdgeIt &next(OutEdgeIt &i) const {
1.188 + i._e=_graph->adj_succ(i._e);
1.189 + return i;
1.190 + }
1.191 + //SymEdgeIt &next(SymEdgeIt &) const {}
1.192 + /// Go to the next edge.
1.193 + EdgeIt &next(EdgeIt &i) const {
1.194 + i._e=_graph->succ_edge(i._e);
1.195 + return i;
1.196 + }
1.197 +
1.198 + template< typename It >
1.199 + It first() const {
1.200 + It e;
1.201 + first(e);
1.202 + return e;
1.203 + }
1.204 +
1.205 + template< typename It >
1.206 + It first(Node v) const {
1.207 + It e;
1.208 + first(e, v);
1.209 + return e;
1.210 + }
1.211 +
1.212 + ///Gives back the head node of an edge.
1.213 + Node head(Edge e) const {
1.214 + return Node(_graph->target(e._e));
1.215 + }
1.216 + ///Gives back the tail node of an edge.
1.217 + Node tail(Edge e) const {
1.218 + return Node(_graph->source(e._e));
1.219 + }
1.220 +
1.221 + Node aNode(InEdgeIt e) const { return head(e); }
1.222 + Node aNode(OutEdgeIt e) const { return tail(e); }
1.223 + // Node aNode(SymEdgeIt) const {}
1.224 +
1.225 + Node bNode(InEdgeIt e) const { return tail(e); }
1.226 + Node bNode(OutEdgeIt e) const { return head(e); }
1.227 + // Node bNode(SymEdgeIt) const {}
1.228 +
1.229 + /// Checks if a node iterator is valid
1.230 + bool valid(Node n) const { return n._n; }
1.231 + /// Checks if an edge iterator is valid
1.232 + bool valid(Edge e) const { return e._e; }
1.233 +
1.234 + ///Gives back the \e id of a node.
1.235 + int id(Node n) const { return n._n->id(); }
1.236 + ///Gives back the \e id of an edge.
1.237 + int id(Edge e) const { return e._e->id(); }
1.238 +
1.239 + //void setInvalid(Node &) const {};
1.240 + //void setInvalid(Edge &) const {};
1.241 +
1.242 + Node addNode() const { return Node(_graph->new_node()); }
1.243 + Edge addEdge(Node tail, Node head) const {
1.244 + return Edge(_graph->new_edge(tail._n, head._n));
1.245 + }
1.246 +
1.247 + void erase(Node n) const { _graph->del_node(n._n); }
1.248 + void erase(Edge e) const { _graph->del_edge(e._e); }
1.249 +
1.250 + void clear() const { _graph->clear(); }
1.251 +
1.252 + int nodeNum() const { return _graph->number_of_nodes(); }
1.253 + int edgeNum() const { return _graph->number_of_edges(); }
1.254 +
1.255 + ///Read/write map from the nodes to type \c T.
1.256 + template<typename T> class NodeMap
1.257 + {
1.258 + leda_node_map<T> leda_stuff;
1.259 + public:
1.260 + typedef T ValueType;
1.261 + typedef Node KeyType;
1.262 +
1.263 + NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
1.264 + NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
1.265 +
1.266 + void set(Node i, T t) { leda_stuff[i._n]=t; }
1.267 + T get(Node i) const { return leda_stuff[i._n]; } //FIXME: Is it necessary
1.268 + T &operator[](Node i) { return leda_stuff[i._n]; }
1.269 + const T &operator[](Node i) const { return leda_stuff[i._n]; }
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 + };
1.274 +
1.275 + ///Read/write map from the edges to type \c T.
1.276 + template<typename T> class EdgeMap
1.277 + {
1.278 + leda_edge_map<T> leda_stuff;
1.279 + public:
1.280 + typedef T ValueType;
1.281 + typedef Edge KeyType;
1.282 +
1.283 + EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
1.284 + EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
1.285 +
1.286 + void set(Edge i, T t) { leda_stuff[i._e]=t; }
1.287 + T get(Edge i) const { return leda_stuff[i._e]; } //FIXME: Is it necessary
1.288 + T &operator[](Edge i) { return leda_stuff[i._e]; }
1.289 + const T &operator[](Edge i) const { return leda_stuff[i._e]; }
1.290 +
1.291 + void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
1.292 + //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); } //FIXME: Is it necessary
1.293 + };
1.294 +
1.295 + };
1.296 +
1.297 + // @}
1.298 +
1.299 +} //namespace hugo
1.300 +
1.301 +
1.302 +
1.303 +// class EmptyBipGraph : public EmptyGraph
1.304 +// {
1.305 +// class ANode {};
1.306 +// class BNode {};
1.307 +
1.308 +// ANode &next(ANode &) {}
1.309 +// BNode &next(BNode &) {}
1.310 +
1.311 +// ANode &getFirst(ANode &) const {}
1.312 +// BNode &getFirst(BNode &) const {}
1.313 +
1.314 +// enum NodeClass { A = 0, B = 1 };
1.315 +// NodeClass getClass(Node n) {}
1.316 +
1.317 +// }
1.318 +
1.319 +#endif // HUGO_LEDA_GRAPH_WRAPPER_H