COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/list_graph.hh @ 69:24c2c2989e0f

Last change on this file since 69:24c2c2989e0f was 69:24c2c2989e0f, checked in by marci, 17 years ago

.

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