COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/list_graph.hh @ 75:87623302a68f

Last change on this file since 75:87623302a68f was 75:87623302a68f, checked in by marci, 17 years ago

.

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