COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/deba/list_graph.h @ 701:c03e073b8394

Last change on this file since 701:c03e073b8394 was 701:c03e073b8394, checked in by Balazs Dezso, 16 years ago
File size: 10.6 KB
Line 
1// -*- mode:C++ -*-
2
3#ifndef HUGO_LIST_GRAPH_H
4#define HUGO_LIST_GRAPH_H
5
6///\ingroup graphs
7///\file
8///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
9
10#include <vector>
11#include <climits>
12
13#include "invalid.h"
14
15#include "vector_map_factory.h"
16#include "map_registry.h"
17
18#include "map_defines.h"
19
20namespace hugo {
21
22/// \addtogroup graphs
23/// @{
24
25  ///A list graph class.
26
27  ///This is a simple and fast erasable graph implementation.
28  ///
29  ///It conforms to the graph interface documented under
30  ///the description of \ref GraphSkeleton.
31  ///\sa \ref GraphSkeleton.
32  class ListGraph {
33
34    //Nodes are double linked.
35    //The free nodes are only single linked using the "next" field.
36    struct NodeT
37    {
38      int first_in,first_out;
39      int prev, next;
40      //      NodeT() {}
41    };
42    //Edges are double linked.
43    //The free edges are only single linked using the "next_in" field.
44    struct EdgeT
45    {
46      int head, tail;
47      int prev_in, prev_out;
48      int next_in, next_out;
49      //FIXME: is this necessary?
50      //      EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {} 
51    };
52
53    std::vector<NodeT> nodes;
54    //The first node
55    int first_node;
56    //The first free node
57    int first_free_node;
58    std::vector<EdgeT> edges;
59    //The first free edge
60    int first_free_edge;
61   
62  protected:
63   
64  public:
65   
66    class Node;
67    class Edge;
68
69    typedef ListGraph Graph;
70
71  public:
72
73    class NodeIt;
74    class EdgeIt;
75    class OutEdgeIt;
76    class InEdgeIt;
77   
78    CREATE_MAP_REGISTRIES;
79    CREATE_MAPS(VectorMapFactory);
80
81  public:
82
83    ListGraph() : nodes(), first_node(-1),
84                  first_free_node(-1), edges(), first_free_edge(-1) {}
85    ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
86                                     first_free_node(_g.first_free_node),
87                                     edges(_g.edges),
88                                     first_free_edge(_g.first_free_edge) {}
89   
90
91    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
92    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
93
94    ///Set the expected number of edges
95
96    ///With this function, it is possible to set the expected number of edges.
97    ///The use of this fasten the building of the graph and makes
98    ///it possible to avoid the superfluous memory allocation.
99    void reserveEdge(int n) { edges.reserve(n); };
100   
101    ///\bug This function does something different than
102    ///its name would suggests...
103    int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
104    ///\bug This function does something different than
105    ///its name would suggests...
106    int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
107
108    Node tail(Edge e) const { return edges[e.n].tail; }
109    Node head(Edge e) const { return edges[e.n].head; }
110
111    Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
112    Node aNode(InEdgeIt e) const { return edges[e.n].head; }
113
114    Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
115    Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
116
117    NodeIt& first(NodeIt& v) const {
118      v=NodeIt(*this); return v; }
119    EdgeIt& first(EdgeIt& e) const {
120      e=EdgeIt(*this); return e; }
121    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
122      e=OutEdgeIt(*this,v); return e; }
123    InEdgeIt& first(InEdgeIt& e, const Node v) const {
124      e=InEdgeIt(*this,v); return e; }
125
126//     template< typename It >
127//     It first() const { It e; first(e); return e; }
128
129//     template< typename It >
130//     It first(Node v) const { It e; first(e,v); return e; }
131
132    bool valid(Edge e) const { return e.n!=-1; }
133    bool valid(Node n) const { return n.n!=-1; }
134   
135    void setInvalid(Edge &e) { e.n=-1; }
136    void setInvalid(Node &n) { n.n=-1; }
137   
138    template <typename It> It getNext(It it) const
139    { It tmp(it); return next(tmp); }
140
141    NodeIt& next(NodeIt& it) const {
142      it.n=nodes[it.n].next;
143      return it;
144    }
145    OutEdgeIt& next(OutEdgeIt& it) const
146    { it.n=edges[it.n].next_out; return it; }
147    InEdgeIt& next(InEdgeIt& it) const
148    { it.n=edges[it.n].next_in; return it; }
149    EdgeIt& next(EdgeIt& it) const {
150      if(edges[it.n].next_in!=-1) {
151        it.n=edges[it.n].next_in;
152      }
153      else {
154        int n;
155        for(n=nodes[edges[it.n].head].next;
156            n!=-1 && nodes[n].first_in == -1;
157            n = nodes[n].next) ;
158        it.n = (n==-1)?-1:nodes[n].first_in;
159      }
160      return it;
161    }
162
163    int id(Node v) const { return v.n; }
164    int id(Edge e) const { return e.n; }
165
166    /// Adds a new node to the graph.
167
168    /// \todo It adds the nodes in a reversed order.
169    /// (i.e. the lastly added node becomes the first.)
170    Node addNode() {
171      int n;
172     
173      if(first_free_node==-1)
174        {
175          n = nodes.size();
176          nodes.push_back(NodeT());
177        }
178      else {
179        n = first_free_node;
180        first_free_node = nodes[n].next;
181      }
182     
183      nodes[n].next = first_node;
184      if(first_node != -1) nodes[first_node].prev = n;
185      first_node = n;
186      nodes[n].prev = -1;
187     
188      nodes[n].first_in = nodes[n].first_out = -1;
189     
190      Node nn; nn.n=n;
191
192      //Update dynamic maps
193      node_maps.add(nn);
194
195      return nn;
196    }
197   
198    Edge addEdge(Node u, Node v) {
199      int n;
200     
201      if(first_free_edge==-1)
202        {
203          n = edges.size();
204          edges.push_back(EdgeT());
205        }
206      else {
207        n = first_free_edge;
208        first_free_edge = edges[n].next_in;
209      }
210     
211      edges[n].tail = u.n; edges[n].head = v.n;
212
213      edges[n].next_out = nodes[u.n].first_out;
214      if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
215      edges[n].next_in = nodes[v.n].first_in;
216      if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
217      edges[n].prev_in = edges[n].prev_out = -1;
218       
219      nodes[u.n].first_out = nodes[v.n].first_in = n;
220
221      Edge e; e.n=n;
222
223      //Update dynamic maps
224      edge_maps.add(e);
225
226      return e;
227    }
228
229  private:
230    void eraseEdge(int n) {
231     
232      if(edges[n].next_in!=-1)
233        edges[edges[n].next_in].prev_in = edges[n].prev_in;
234      if(edges[n].prev_in!=-1)
235        edges[edges[n].prev_in].next_in = edges[n].next_in;
236      else nodes[edges[n].head].first_in = edges[n].next_in;
237     
238      if(edges[n].next_out!=-1)
239        edges[edges[n].next_out].prev_out = edges[n].prev_out;
240      if(edges[n].prev_out!=-1)
241        edges[edges[n].prev_out].next_out = edges[n].next_out;
242      else nodes[edges[n].tail].first_out = edges[n].next_out;
243     
244      edges[n].next_in = first_free_edge;
245      first_free_edge = n;     
246
247      //Update dynamic maps
248      Edge e; e.n=n;
249    }
250     
251  public:
252
253    void erase(Node nn) {
254      int n=nn.n;
255     
256      int m;
257      while((m=nodes[n].first_in)!=-1) eraseEdge(m);
258      while((m=nodes[n].first_out)!=-1) eraseEdge(m);
259
260      if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
261      if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
262      else first_node = nodes[n].next;
263     
264      nodes[n].next = first_free_node;
265      first_free_node = n;
266
267      //Update dynamic maps
268      node_maps.erase(nn);
269     }
270   
271    void erase(Edge e) {
272      edge_maps.erase(e);
273      eraseEdge(e.n);
274    }
275
276    ///\bug Dynamic maps must be updated!
277    ///
278    void clear() {
279      nodes.clear();edges.clear();
280      first_node=first_free_node=first_free_edge=-1;
281    }
282
283    class Node {
284      friend class ListGraph;
285      template <typename T> friend class NodeMap;
286       
287      friend class Edge;
288      friend class OutEdgeIt;
289      friend class InEdgeIt;
290      friend class SymEdge;
291
292    protected:
293      int n;
294      friend int ListGraph::id(Node v) const;
295      Node(int nn) {n=nn;}
296    public:
297      Node() {}
298      Node (Invalid) { n=-1; }
299      bool operator==(const Node i) const {return n==i.n;}
300      bool operator!=(const Node i) const {return n!=i.n;}
301      bool operator<(const Node i) const {return n<i.n;}
302    };
303   
304    class NodeIt : public Node {
305      friend class ListGraph;
306    public:
307      NodeIt() : Node() { }
308      NodeIt(Invalid i) : Node(i) { }
309      NodeIt(const ListGraph& G) : Node(G.first_node) { }
310      ///\todo Undocumented conversion Node -\> NodeIt.
311      NodeIt(const ListGraph& G, const Node &n) : Node(n) { }
312    };
313
314    class Edge {
315      friend class ListGraph;
316      template <typename T> friend class EdgeMap;
317
318      //template <typename T> friend class SymListGraph::SymEdgeMap;     
319      //friend Edge SymListGraph::opposite(Edge) const;
320     
321      friend class Node;
322      friend class NodeIt;
323    protected:
324      int n;
325      friend int ListGraph::id(Edge e) const;
326
327      Edge(int nn) {n=nn;}
328    public:
329      Edge() { }
330      Edge (Invalid) { n=-1; }
331      bool operator==(const Edge i) const {return n==i.n;}
332      bool operator!=(const Edge i) const {return n!=i.n;}
333      bool operator<(const Edge i) const {return n<i.n;}
334      ///\bug This is a workaround until somebody tells me how to
335      ///make class \c SymListGraph::SymEdgeMap friend of Edge
336      int &idref() {return n;}
337      const int &idref() const {return n;}
338    };
339   
340    class EdgeIt : public Edge {
341      friend class ListGraph;
342    public:
343      EdgeIt(const ListGraph& G) : Edge() {
344        int m;
345        for(m=G.first_node;
346            m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
347        n = (m==-1)?-1:G.nodes[m].first_in;
348      }
349      EdgeIt (Invalid i) : Edge(i) { }
350      EdgeIt() : Edge() { }
351      ///\bug This is a workaround until somebody tells me how to
352      ///make class \c SymListGraph::SymEdgeMap friend of Edge
353      int &idref() {return n;}
354    };
355   
356    class OutEdgeIt : public Edge {
357      friend class ListGraph;
358    public:
359      OutEdgeIt() : Edge() { }
360      OutEdgeIt (Invalid i) : Edge(i) { }
361
362      OutEdgeIt(const ListGraph& G,const Node v)
363        : Edge(G.nodes[v.n].first_out) {}
364    };
365   
366    class InEdgeIt : public Edge {
367      friend class ListGraph;
368    public:
369      InEdgeIt() : Edge() { }
370      InEdgeIt (Invalid i) : Edge(i) { }
371      InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in) {}
372    };
373
374  };
375
376  ///Graph for bidirectional edges.
377
378  ///The purpose of this graph structure is to handle graphs
379  ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
380  ///of oppositely directed edges.
381  ///There is a new edge map type called
382  ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
383  ///that complements this
384  ///feature by
385  ///storing shared values for the edge pairs. The usual
386  ///\ref GraphSkeleton::EdgeMap "EdgeMap"
387  ///can be used
388  ///as well.
389  ///
390  ///The oppositely directed edge can also be obtained easily
391  ///using \ref opposite.
392  ///
393  ///Here erase(Edge) deletes a pair of edges.
394  ///
395  ///\todo this date structure need some reconsiderations. Maybe it
396  ///should be implemented independently from ListGraph.
397
398}
399
400#endif //HUGO_LIST_GRAPH_H
Note: See TracBrowser for help on using the repository browser.