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