COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/deba/test_graph.h @ 627:6cc21a9c9fda

Last change on this file since 627:6cc21a9c9fda was 627:6cc21a9c9fda, checked in by Balazs Dezso, 20 years ago
File size: 16.3 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_LIST_GRAPH_H
3#define HUGO_LIST_GRAPH_H
4
5#include <iostream>
6#include <vector>
7
8#include "invalid.h"
9
10#include "vector_map_factory.h"
11
12namespace hugo {
13
14  template <typename It>
15  int count(It it) {
16    int i=0;
17    for( ; it.valid(); ++it) { ++i; }
18    return i;
19  }
20
21  class ListGraph {
22    class node_item;
23    class edge_item;
24  public:
25    class Node;
26    class NodeIt;
27    class Edge;
28    class EdgeIt;
29    class OutEdgeIt;
30    class InEdgeIt;
31    class SymEdgeIt;
32   
33    //    template <typename T> class NodeMap;
34    //    template <typename T> class EdgeMap;
35  private:
36    //    template <typename T> friend class NodeMap;
37    //   template <typename T> friend class EdgeMap;
38 
39  private:
40
41 
42  public:
43       
44    typedef MapRegistry<ListGraph, Node, NodeIt> NodeMapRegistry;
45    typedef VectorMapFactory<NodeMapRegistry> NodeMapFactory;
46    NodeMapRegistry node_maps;
47
48
49
50    typedef MapRegistry<ListGraph, Edge, EdgeIt> EdgeMapRegistry;
51    typedef VectorMapFactory<EdgeMapRegistry> EdgeMapFactory;
52    EdgeMapRegistry edge_maps;
53 
54
55    int node_id;
56    int edge_id;
57    int _node_num;
58    int _edge_num;
59
60    node_item* _first_node;
61    node_item* _last_node;
62
63    class node_item {
64      friend class ListGraph;
65      template <typename T> friend class NodeMap;
66     
67      friend class Node;
68      friend class NodeIt;
69      friend class Edge;
70      friend class EdgeIt;
71      friend class OutEdgeIt;
72      friend class InEdgeIt;
73      friend class SymEdgeIt;
74      friend std::ostream& operator<<(std::ostream& os, const Node& i);
75      friend std::ostream& operator<<(std::ostream& os, const Edge& i);
76      //ListGraph* G;
77      int id;
78      edge_item* _first_out_edge;
79      edge_item* _last_out_edge;
80      edge_item* _first_in_edge;
81      edge_item* _last_in_edge;
82      node_item* _next_node;
83      node_item* _prev_node;
84    public:
85      node_item() { }
86    };
87
88    class edge_item {
89      friend class ListGraph;
90      template <typename T> friend class EdgeMap;
91
92      friend class Node;
93      friend class NodeIt;
94      friend class Edge;
95      friend class EdgeIt;
96      friend class OutEdgeIt;
97      friend class InEdgeIt;
98      friend class SymEdgeIt;
99      friend std::ostream& operator<<(std::ostream& os, const Edge& i);
100      //ListGraph* G;
101      int id;
102      node_item* _tail;
103      node_item* _head;
104      edge_item* _next_out;
105      edge_item* _prev_out;
106      edge_item* _next_in;
107      edge_item* _prev_in;
108    public:
109      edge_item() { }
110    };
111
112    node_item* _add_node() {
113      node_item* p=new node_item;
114      p->id=node_id++;
115      p->_first_out_edge=0;
116      p->_last_out_edge=0;
117      p->_first_in_edge=0;
118      p->_last_in_edge=0;
119      p->_prev_node=_last_node;
120      p->_next_node=0;
121      if (_last_node) _last_node->_next_node=p;
122      _last_node=p;
123      if (!_first_node) _first_node=p;
124
125      ++_node_num;
126      return p;
127    }
128
129    edge_item* _add_edge(node_item* _tail, node_item* _head) {
130      edge_item* e=new edge_item;
131      e->id=edge_id++;
132      e->_tail=_tail;
133      e->_head=_head;
134     
135      e->_prev_out=_tail->_last_out_edge;
136      if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
137      _tail->_last_out_edge=e;
138      if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
139      e->_next_out=0;
140 
141      e->_prev_in=_head->_last_in_edge;
142      if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
143      _head->_last_in_edge=e;
144      if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
145      e->_next_in=0;
146
147      ++_edge_num;
148      return e;
149    }
150
151    //deletes a node which has no out edge and no in edge
152    void _delete_node(node_item* v) {
153      if (v->_next_node) (v->_next_node)->_prev_node=v->_prev_node; else
154        _last_node=v->_prev_node;
155      if (v->_prev_node) (v->_prev_node)->_next_node=v->_next_node; else
156        _first_node=v->_next_node;
157
158      delete v;
159      --_node_num;
160    }
161
162    void _delete_edge(edge_item* e) {
163      if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
164        (e->_tail)->_last_out_edge=e->_prev_out;
165      if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
166        (e->_tail)->_first_out_edge=e->_next_out;
167      if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
168        (e->_head)->_last_in_edge=e->_prev_in;
169      if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
170        (e->_head)->_first_in_edge=e->_next_in;
171
172      delete e;
173      --_edge_num;
174    }
175
176    void _set_tail(edge_item* e, node_item* _tail) {
177      if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
178        (e->_tail)->_last_out_edge=e->_prev_out;
179      if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
180        (e->_tail)->_first_out_edge=e->_next_out;
181     
182      e->_tail=_tail;
183     
184      e->_prev_out=_tail->_last_out_edge;
185      if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
186      _tail->_last_out_edge=e;
187      if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
188      e->_next_out=0;
189    }
190
191    void _set_head(edge_item* e, node_item* _head) {
192      if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
193        (e->_head)->_last_in_edge=e->_prev_in;
194      if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
195        (e->_head)->_first_in_edge=e->_next_in;
196     
197      e->_head=_head;
198     
199      e->_prev_in=_head->_last_in_edge;
200      if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
201      _head->_last_in_edge=e;
202      if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
203      e->_next_in=0;
204    }
205
206  public:
207
208    /* default constructor */
209
210    ListGraph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0){ }
211   
212    ~ListGraph() {
213      while (first<NodeIt>().valid()) erase(first<NodeIt>());
214    }
215
216    int nodeNum() const { return _node_num; }
217    int edgeNum() const { return _edge_num; }
218
219    /* functions to construct iterators from the graph, or from each other */
220
221    //NodeIt firstNode() const { return NodeIt(*this); }
222    //EdgeIt firstEdge() const { return EdgeIt(*this); }
223   
224    //OutEdgeIt firstOutEdge(const Node v) const { return OutEdgeIt(v); }
225    //InEdgeIt firstInEdge(const Node v) const { return InEdgeIt(v); }
226    //SymEdgeIt firstSymEdge(const Node v) const { return SymEdgeIt(v); }
227    Node tail(Edge e) const { return e.tailNode(); }
228    Node head(Edge e) const { return e.headNode(); }
229
230    Node aNode(const OutEdgeIt& e) const { return e.aNode(); }
231    Node aNode(const InEdgeIt& e) const { return e.aNode(); }
232    Node aNode(const SymEdgeIt& e) const { return e.aNode(); }
233
234    Node bNode(const OutEdgeIt& e) const { return e.bNode(); }
235    Node bNode(const InEdgeIt& e) const { return e.bNode(); }
236    Node bNode(const SymEdgeIt& e) const { return e.bNode(); }
237
238    //Node invalid_node() { return Node(); }
239    //Edge invalid_edge() { return Edge(); }
240    //OutEdgeIt invalid_out_edge() { return OutEdgeIt(); }
241    //InEdgeIt invalid_in_edge() { return InEdgeIt(); }
242    //SymEdgeIt invalid_sym_edge() { return SymEdgeIt(); }
243
244    /* same methods in other style */
245    /* for experimental purpose */
246
247    NodeIt& /*getF*/first(NodeIt& v) const {
248      v=NodeIt(*this); return v; }
249    EdgeIt& /*getF*/first(EdgeIt& e) const {
250      e=EdgeIt(*this); return e; }
251    OutEdgeIt& /*getF*/first(OutEdgeIt& e, Node v) const {
252      e=OutEdgeIt(*this, v); return e; }
253    InEdgeIt& /*getF*/first(InEdgeIt& e, Node v) const {
254      e=InEdgeIt(*this, v); return e; }
255    SymEdgeIt& /*getF*/first(SymEdgeIt& e, Node v) const {
256      e=SymEdgeIt(*this, v); return e; }
257    //void getTail(Node& n, const Edge& e) const { n=tail(e); }
258    //void getHead(Node& n, const Edge& e) const { n=head(e); }
259
260    //void getANode(Node& n, const OutEdgeIt& e) const { n=e.aNode(); }
261    //void getANode(Node& n, const InEdgeIt& e) const { n=e.aNode(); }
262    //void getANode(Node& n, const SymEdgeIt& e) const { n=e.aNode(); }
263    //void getBNode(Node& n, const OutEdgeIt& e) const { n=e.bNode(); }
264    //void getBNode(Node& n, const InEdgeIt& e) const { n=e.bNode(); }
265    //void getBNode(Node& n, const SymEdgeIt& e) const { n=e.bNode(); }
266    //void get_invalid(Node& n) { n=Node(); }
267    //void get_invalid(Edge& e) { e=Edge(); }
268    //void get_invalid(OutEdgeIt& e) { e=OutEdgeIt(); }
269    //void get_invalid(InEdgeIt& e) { e=InEdgeIt(); }
270    //void get_invalid(SymEdgeIt& e) { e=SymEdgeIt(); }
271
272    template< typename It >
273    It first() const {
274      It e;
275      /*getF*/first(e);
276      return e;
277    }
278
279    template< typename It >
280    It first(Node v) const {
281      It e;
282      /*getF*/first(e, v);
283      return e;
284    }
285
286    bool valid(Node n) const { return n.valid(); }
287    bool valid(Edge e) const { return e.valid(); }
288   
289    template <typename It> It getNext(It it) const {
290      It tmp(it); return next(tmp); }
291    template <typename It> It& next(It& it) const { return ++it; }
292   
293
294    /* for getting id's of graph objects */
295    /* these are important for the implementation of property vectors */
296
297    int id(Node v) const { return v.node->id; }
298    int id(Edge e) const { return e.edge->id; }
299
300    /* adding nodes and edges */
301
302    Node addNode() {
303      Node n = _add_node();
304      node_maps.add(n);
305      return n;
306    }
307    Edge addEdge(Node u, Node v) {
308      Edge e = _add_edge(u.node, v.node);
309      edge_maps.add(e);
310      return e;
311    }
312
313    void erase(Node i) {
314      node_maps.erase(i);
315      while (first<OutEdgeIt>(i).valid()) erase(first<OutEdgeIt>(i));
316      while (first<InEdgeIt>(i).valid()) erase(first<InEdgeIt>(i));
317      _delete_node(i.node);
318    }
319 
320    void erase(Edge e) {
321      edge_maps.erase(e);
322      _delete_edge(e.edge);
323    }
324
325    void clear() {
326      while (first<NodeIt>().valid()) erase(first<NodeIt>());
327    }
328
329    void setTail(Edge e, Node tail) {
330      _set_tail(e.edge, tail.node);
331    }
332
333    void setHead(Edge e, Node head) {
334      _set_head(e.edge, head.node);
335    }
336
337    /* stream operations, for testing purpose */
338
339    friend std::ostream& operator<<(std::ostream& os, const Node& i) {
340      os << i.node->id; return os;
341    }
342    friend std::ostream& operator<<(std::ostream& os, const Edge& i) {
343      os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")";
344      return os;
345    }
346
347    class Node {
348      friend class ListGraph;
349      template <typename T> friend class NodeMap;
350
351      friend class Edge;
352      friend class OutEdgeIt;
353      friend class InEdgeIt;
354      friend class SymEdgeIt;
355      //public:  //FIXME: It is required by op= of NodeIt
356    protected:
357      node_item* node;
358    protected:
359      friend int ListGraph::id(Node v) const;
360    public:
361      Node() /*: node(0)*/ { }
362      Node(const Invalid&) : node(0) { }
363    protected:
364      Node(node_item* _node) : node(_node) { }
365      bool valid() const { return (node); }
366    public:
367      //void makeInvalid() { node=0; }
368      friend bool operator==(Node u, Node v) { return v.node==u.node; }
369      friend bool operator!=(Node u, Node v) { return v.node!=u.node; }
370      friend std::ostream& operator<<(std::ostream& os, const Node& i);
371    };
372   
373    class NodeIt : public Node {
374      friend class ListGraph;
375      //protected:
376    public: //for everybody but marci
377      NodeIt(const ListGraph& G) : Node(G._first_node) { }
378    public:
379      NodeIt() : Node() { }
380      NodeIt(const Invalid& i) : Node(i) { }
381    protected:
382      NodeIt(node_item* v) : Node(v) { }
383      NodeIt& operator++() { node=node->_next_node; return *this; }
384      //FIXME::
385      //      NodeIt& operator=(const Node& e)
386      //      { node=e.node; return *this; }
387    };
388
389    class Edge {
390      friend class ListGraph;
391      template <typename T> friend class EdgeMap;
392     
393      friend class Node;
394      friend class NodeIt;
395    protected:
396      edge_item* edge;
397      friend int ListGraph::id(Edge e) const;
398    public:
399      Edge() /*: edge(0)*/ { }
400      Edge(const Invalid&) : edge(0) { }
401      //Edge() { }
402    protected:
403      Edge(edge_item* _edge) : edge(_edge) { }
404      bool valid() const { return (edge); }
405    public:
406      //void makeInvalid() { edge=0; }
407      friend bool operator==(Edge u, Edge v) { return v.edge==u.edge; }
408      friend bool operator!=(Edge u, Edge v) { return v.edge!=u.edge; }
409    protected:
410      Node tailNode() const { return Node(edge->_tail); }
411      Node headNode() const { return Node(edge->_head); }
412    public:
413      friend std::ostream& operator<<(std::ostream& os, const Edge& i);
414    };
415   
416    class EdgeIt : public Edge {
417      friend class ListGraph;
418      //protected:
419    public: //for alpar
420      EdgeIt(const ListGraph& G) {
421        node_item* v=G._first_node;
422        if (v) edge=v->_first_out_edge; else edge=0;
423        while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
424      }
425    public:
426      EdgeIt() : Edge() { }
427      EdgeIt(const Invalid& i) : Edge(i) { }
428    protected:
429      EdgeIt(edge_item* _e) : Edge(_e) { }
430      EdgeIt& operator++() {
431        node_item* v=edge->_tail;
432        edge=edge->_next_out;
433        while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
434        return *this;
435      }
436    };
437   
438    class OutEdgeIt : public Edge {
439      friend class ListGraph;
440      //node_item* v;
441      //protected:
442    protected: //for alpar
443      OutEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
444    public:
445      OutEdgeIt() : Edge()/*, v(0)*/ { }
446      OutEdgeIt(const Invalid& i) : Edge(i) { }
447      OutEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
448    protected:
449      OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
450    protected:
451      Node aNode() const { return Node(edge->_tail); }
452      Node bNode() const { return Node(edge->_head); }
453    };
454   
455    class InEdgeIt : public Edge {
456      friend class ListGraph;
457      //node_item* v;
458      //protected:
459    protected: //for alpar
460      InEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
461    public:
462      InEdgeIt() : Edge()/*, v(0)*/ { }
463      InEdgeIt(const Invalid& i) : Edge(i) { }
464      InEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
465    protected:
466      InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
467    protected:
468      Node aNode() const { return Node(edge->_head); }
469      Node bNode() const { return Node(edge->_tail); }
470    };
471
472    class SymEdgeIt : public Edge {
473      friend class ListGraph;
474      bool out_or_in; //1 iff out, 0 iff in
475      //node_item* v;
476      //protected:
477    public: //for alpar
478      SymEdgeIt(const Node& _v) /*: v(_v.node)*/ {
479        out_or_in=1;
480        edge=_v.node->_first_out_edge;
481        if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
482      }
483    public:
484      SymEdgeIt() : Edge() /*, v(0)*/ { }
485      SymEdgeIt(const Invalid& i) : Edge(i) { }
486      SymEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ {
487        out_or_in=1;
488        edge=_v.node->_first_out_edge;
489        if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
490      }
491    protected:
492      SymEdgeIt& operator++() {
493        if (out_or_in) {
494          node_item* v=edge->_tail;
495          edge=edge->_next_out;
496          if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
497        } else {
498          edge=edge->_next_in;
499        }
500        return *this;
501      }
502    protected:
503      Node aNode() const {
504        return (out_or_in) ? Node(edge->_tail) : Node(edge->_head); }
505      Node bNode() const {
506        return (out_or_in) ? Node(edge->_head) : Node(edge->_tail); }
507    };
508
509  };
510
511  //   template< typename T >
512  //   T ListGraph::first() const {
513  //     std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>();" << std::endl;
514  //     return T();
515  //   }
516
517  //   template<>
518  //   ListGraph::NodeIt ListGraph::first<ListGraph::NodeIt>() const {
519  //     return firstNode();
520  //   }
521
522  //   template<>
523  //   ListGraph::EdgeIt ListGraph::first<ListGraph::EdgeIt>() const {
524  //     return firstEdge();
525  //   }
526
527  //   template< typename T >
528  //   T ListGraph::first(ListGraph::Node v) const {
529  //     std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>(ListGRaph::Node);" << std::endl;
530  //     return T();
531  //   }
532
533  //   template<>
534  //   ListGraph::OutEdgeIt ListGraph::first<ListGraph::OutEdgeIt>(const ListGraph::Node v) const {
535  //     return firstOutEdge(v);
536  //   }
537
538  //   template<>
539  //   ListGraph::InEdgeIt ListGraph::first<ListGraph::InEdgeIt>(const ListGraph::Node v) const {
540  //     return firstInEdge(v);
541  //   }
542
543  //   template<>
544  //   ListGraph::SymEdgeIt ListGraph::first<ListGraph::SymEdgeIt>(const ListGraph::Node v) const {
545  //     return firstSymEdge(v);
546  //   }
547
548
549} //namespace hugo
550
551#endif //HUGO_LIST_GRAPH_H
Note: See TracBrowser for help on using the repository browser.