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