COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/smart_graph.h @ 909:6a22e0dfd453

Last change on this file since 909:6a22e0dfd453 was 909:6a22e0dfd453, checked in by Balazs Dezso, 18 years ago

New symmetric Graph concept.
New symmetric list and smart graph.
Symmetric Graph tests based on the Graph Tests.

File size: 20.5 KB
Line 
1/* -*- C++ -*-
2 * src/hugo/smart_graph.h - Part of HUGOlib, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef HUGO_SMART_GRAPH_H
18#define HUGO_SMART_GRAPH_H
19
20///\ingroup graphs
21///\file
22///\brief SmartGraph and SymSmartGraph classes.
23
24#include <vector>
25#include <climits>
26
27#include <hugo/invalid.h>
28
29#include <hugo/array_map.h>
30#include <hugo/map_registry.h>
31
32#include <hugo/map_defines.h>
33
34namespace hugo {
35
36/// \addtogroup graphs
37/// @{
38//  class SymSmartGraph;
39
40  ///A smart graph class.
41
42  ///This is a simple and fast graph implementation.
43  ///It is also quite memory efficient, but at the price
44  ///that <b> it does not support node and edge deletion</b>.
45  ///It conforms to
46  ///the \ref skeleton::ExtendableGraph "ExtendableGraph" concept.
47  ///\sa skeleton::ExtendableGraph.
48  ///
49  ///\todo Some member functions could be \c static.
50  ///
51  ///\todo A possibly useful functionality: a function saveState() would
52  ///give back a data sturcture X and then the function restoreState(X)
53  ///would remove the nodes and edges added after the call of saveState().
54  ///Of course it should be used as a stack. (Maybe X is not necessary.)
55  ///
56  ///\author Alpar Juttner
57  class SmartGraph {
58
59    struct NodeT
60    {
61      int first_in,first_out;     
62      NodeT() : first_in(-1), first_out(-1) {}
63    };
64    struct EdgeT
65    {
66      int head, tail, next_in, next_out;     
67      //FIXME: is this necessary?
68      EdgeT() : next_in(-1), next_out(-1) {} 
69    };
70
71    std::vector<NodeT> nodes;
72
73    std::vector<EdgeT> edges;
74   
75   
76  public:
77
78    typedef SmartGraph Graph;
79
80    class Node;
81    class Edge;
82
83    class NodeIt;
84    class EdgeIt;
85    class OutEdgeIt;
86    class InEdgeIt;
87   
88    // Create map registries.
89    CREATE_MAP_REGISTRIES;
90    // Create node and edge maps.
91    CREATE_MAPS(ArrayMap);
92   
93  public:
94
95    SmartGraph() : nodes(), edges() { }
96    SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
97   
98    ///Number of nodes.
99    int nodeNum() const { return nodes.size(); }
100    ///Number of edges.
101    int edgeNum() const { return edges.size(); }
102
103    /// Maximum node ID.
104   
105    /// Maximum node ID.
106    ///\sa id(Node)
107    int maxNodeId() const { return nodes.size()-1; }
108    /// Maximum edge ID.
109   
110    /// Maximum edge ID.
111    ///\sa id(Edge)
112    int maxEdgeId() const { return edges.size()-1; }
113
114    Node tail(Edge e) const { return edges[e.n].tail; }
115    Node head(Edge e) const { return edges[e.n].head; }
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    /// Node ID.
127   
128    /// The ID of a valid Node is a nonnegative integer not greater than
129    /// \ref maxNodeId(). The range of the ID's is not surely continuous
130    /// and the greatest node ID can be actually less then \ref maxNodeId().
131    ///
132    /// The ID of the \ref INVALID node is -1.
133    ///\return The ID of the node \c v.
134    static int id(Node v) { return v.n; }
135    /// Edge ID.
136   
137    /// The ID of a valid Edge is a nonnegative integer not greater than
138    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
139    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
140    ///
141    /// The ID of the \ref INVALID edge is -1.
142    ///\return The ID of the edge \c e.
143    static int id(Edge e) { return e.n; }
144
145    Node addNode() {
146      Node n; n.n=nodes.size();
147      nodes.push_back(NodeT()); //FIXME: Hmmm...
148
149     
150      node_maps.add(n);
151      return n;
152    }
153   
154    Edge addEdge(Node u, Node v) {
155      Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
156      edges[e.n].tail=u.n; edges[e.n].head=v.n;
157      edges[e.n].next_out=nodes[u.n].first_out;
158      edges[e.n].next_in=nodes[v.n].first_in;
159      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
160
161      edge_maps.add(e);
162
163      return e;
164    }
165
166    /// Finds an edge between two nodes.
167
168    /// Finds an edge from node \c u to node \c v.
169    ///
170    /// If \c prev is \ref INVALID (this is the default value), then
171    /// It finds the first edge from \c u to \c v. Otherwise it looks for
172    /// the next edge from \c u to \c v after \c prev.
173    /// \return The found edge or INVALID if there is no such an edge.
174    Edge findEdge(Node u,Node v, Edge prev = INVALID)
175    {
176      int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
177      while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
178      prev.n=e;
179      return prev;
180    }
181   
182    void clear() {
183      edge_maps.clear();
184      edges.clear();
185      node_maps.clear();
186      nodes.clear();
187    }
188
189    class Node {
190      friend class SmartGraph;
191      template <typename T> friend class NodeMap;
192     
193      friend class Edge;
194      friend class OutEdgeIt;
195      friend class InEdgeIt;
196      friend class SymEdge;
197
198    protected:
199      int n;
200      friend int SmartGraph::id(Node v);
201      Node(int nn) {n=nn;}
202    public:
203      Node() {}
204      Node (Invalid) { n=-1; }
205      bool operator==(const Node i) const {return n==i.n;}
206      bool operator!=(const Node i) const {return n!=i.n;}
207      bool operator<(const Node i) const {return n<i.n;}
208      //      ///Validity check
209      //      operator bool() { return n!=-1; }
210    };
211   
212    class NodeIt : public Node {
213      const SmartGraph *G;
214      friend class SmartGraph;
215    public:
216      NodeIt() : Node() { }
217      NodeIt(const SmartGraph& _G,Node n) : Node(n), G(&_G) { }
218      NodeIt(Invalid i) : Node(i) { }
219      NodeIt(const SmartGraph& _G) : Node(_G.nodes.size()?0:-1), G(&_G) { }
220      NodeIt &operator++() {
221        n=(n+2)%(G->nodes.size()+1)-1;
222        return *this;
223      }
224//       ///Validity check
225//       operator bool() { return Node::operator bool(); }     
226    };
227
228    class Edge {
229      friend class SmartGraph;
230      template <typename T> friend class EdgeMap;
231
232      friend class SymSmartGraph;
233     
234      friend class Node;
235      friend class NodeIt;
236    protected:
237      int n;
238      friend int SmartGraph::id(Edge e);
239      Edge(int nn) {n=nn;}
240    public:
241      /// An Edge with id \c n.
242
243      Edge() { }
244      Edge (Invalid) { n=-1; }
245      bool operator==(const Edge i) const {return n==i.n;}
246      bool operator!=(const Edge i) const {return n!=i.n;}
247      bool operator<(const Edge i) const {return n<i.n;}
248//       ///Validity check
249//       operator bool() { return n!=-1; }
250
251      ///Set the edge to that have ID \c ID.
252      void setToId(int id) { n=id; }
253   };
254   
255    class EdgeIt : public Edge {
256      const SmartGraph *G;
257      friend class SmartGraph;
258    public:
259      EdgeIt(const SmartGraph& _G) : Edge(_G.edges.size()-1), G(&_G) { }
260      EdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
261      EdgeIt (Invalid i) : Edge(i) { }
262      EdgeIt() : Edge() { }
263      EdgeIt &operator++() { --n; return *this; }
264//       ///Validity check
265//       operator bool() { return Edge::operator bool(); }     
266    };
267   
268    class OutEdgeIt : public Edge {
269      const SmartGraph *G;
270      friend class SmartGraph;
271    public:
272      OutEdgeIt() : Edge() { }
273      OutEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
274      OutEdgeIt (Invalid i) : Edge(i) { }
275
276      OutEdgeIt(const SmartGraph& _G,const Node v)
277        : Edge(_G.nodes[v.n].first_out), G(&_G) {}
278      OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
279//       ///Validity check
280//       operator bool() { return Edge::operator bool(); }     
281    };
282   
283    class InEdgeIt : public Edge {
284      const SmartGraph *G;
285      friend class SmartGraph;
286    public:
287      InEdgeIt() : Edge() { }
288      InEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
289      InEdgeIt (Invalid i) : Edge(i) { }
290      InEdgeIt(const SmartGraph& _G,Node v)
291        : Edge(_G.nodes[v.n].first_in), G(&_G) { }
292      InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
293//       ///Validity check
294//       operator bool() { return Edge::operator bool(); }     
295    };
296
297  };
298
299
300
301  class SymSmartGraph : public SmartGraph {
302    typedef SmartGraph Parent;
303  public:
304
305    typedef SymSmartGraph Graph;
306
307    typedef SmartGraph::Node Node;
308    typedef SmartGraph::NodeIt NodeIt;
309
310    class SymEdge;
311    class SymEdgeIt;
312
313    class Edge;
314    class EdgeIt;
315    class OutEdgeIt;
316    class InEdgeIt;
317
318    template <typename Value>
319    class NodeMap : public Parent::NodeMap<Value> {     
320    public:
321      NodeMap(const SymSmartGraph& g)
322        : SymSmartGraph::Parent::NodeMap<Value>(g) {}
323      NodeMap(const SymSmartGraph& g, Value v)
324        : SymSmartGraph::Parent::NodeMap<Value>(g, v) {}
325      template<typename TT>
326      NodeMap(const NodeMap<TT>& copy)
327        : SymSmartGraph::Parent::NodeMap<Value>(copy) { }           
328    };
329
330    template <typename Value>
331    class SymEdgeMap : public Parent::EdgeMap<Value> {
332    public:
333      typedef SymEdge KeyType;
334
335      SymEdgeMap(const SymSmartGraph& g)
336        : SymSmartGraph::Parent::EdgeMap<Value>(g) {}
337      SymEdgeMap(const SymSmartGraph& g, Value v)
338        : SymSmartGraph::Parent::EdgeMap<Value>(g, v) {}
339      template<typename TT>
340      SymEdgeMap(const SymEdgeMap<TT>& copy)
341        : SymSmartGraph::Parent::EdgeMap<Value>(copy) { }
342     
343    };
344
345    // Create edge map registry.
346    CREATE_EDGE_MAP_REGISTRY;
347    // Create edge maps.
348    CREATE_EDGE_MAP(ArrayMap);
349
350    class Edge {
351      friend class SymSmartGraph;
352      friend class SymSmartGraph::EdgeIt;
353      friend class SymSmartGraph::OutEdgeIt;
354      friend class SymSmartGraph::InEdgeIt;
355     
356    protected:
357      int id;
358
359      Edge(int pid) { id = pid; }
360
361    public:
362      /// An Edge with id \c n.
363
364      Edge() { }
365      Edge (Invalid) { id = -1; }
366
367      operator SymEdge(){ return SymEdge(id >> 1);}
368     
369      bool operator==(const Edge i) const {return id == i.id;}
370      bool operator!=(const Edge i) const {return id != i.id;}
371      bool operator<(const Edge i) const {return id < i.id;}
372      //      ///Validity check
373      //      operator bool() { return n!=-1; }
374    };
375
376    class SymEdge : public SmartGraph::Edge {
377      friend class SymSmartGraph;
378      friend class SymSmartGraph::Edge;
379      typedef SmartGraph::Edge Parent;
380
381    protected:     
382      SymEdge(int pid) : Parent(pid) {}
383    public:
384
385      SymEdge() { }
386      SymEdge(const SmartGraph::Edge& i) : Parent(i) {}
387      SymEdge (Invalid) : Parent(INVALID) {}
388
389    };
390
391    class OutEdgeIt {
392      Parent::OutEdgeIt out;
393      Parent::InEdgeIt in;     
394    public:
395      OutEdgeIt() {}
396      OutEdgeIt(const SymSmartGraph& g, Edge e) {
397        if (e.id & 1 == 0) {   
398          out = Parent::OutEdgeIt(g, SymEdge(e));
399          in = Parent::InEdgeIt(g, g.tail(e));
400        } else {
401          out = Parent::OutEdgeIt(INVALID);
402          in = Parent::InEdgeIt(g, SymEdge(e));
403        }
404      }
405      OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
406
407      OutEdgeIt(const SymSmartGraph& g, const Node v)
408        : out(g, v), in(g, v) {}
409      OutEdgeIt &operator++() {
410        if (out != INVALID) {
411          ++out;
412        } else {
413          ++in;
414        }
415        return *this;
416      }
417
418      operator Edge() const {
419        if (out == INVALID && in == INVALID) return INVALID;
420        return out != INVALID ? forward(out) : backward(in);
421      }
422
423      bool operator==(const Edge i) const {return Edge(*this) == i;}
424      bool operator!=(const Edge i) const {return Edge(*this) != i;}
425      bool operator<(const Edge i) const {return Edge(*this) < i;}
426    };
427
428    class InEdgeIt {
429      Parent::OutEdgeIt out;
430      Parent::InEdgeIt in;     
431    public:
432      InEdgeIt() {}
433      InEdgeIt(const SymSmartGraph& g, Edge e) {
434        if (e.id & 1 == 0) {   
435          out = Parent::OutEdgeIt(g, SymEdge(e));
436          in = Parent::InEdgeIt(g, g.tail(e));
437        } else {
438          out = Parent::OutEdgeIt(INVALID);
439          in = Parent::InEdgeIt(g, SymEdge(e));
440        }
441      }
442      InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
443
444      InEdgeIt(const SymSmartGraph& g, const Node v)
445        : out(g, v), in(g, v) {}
446
447      InEdgeIt &operator++() {
448        if (out != INVALID) {
449          ++out;
450        } else {
451          ++in;
452        }
453        return *this;
454      }
455
456      operator Edge() const {
457        if (out == INVALID && in == INVALID) return INVALID;
458        return out != INVALID ? backward(out) : forward(in);
459      }
460
461      bool operator==(const Edge i) const {return Edge(*this) == i;}
462      bool operator!=(const Edge i) const {return Edge(*this) != i;}
463      bool operator<(const Edge i) const {return Edge(*this) < i;}
464    };
465
466    class SymEdgeIt : public Parent::EdgeIt {
467
468    public:
469      SymEdgeIt() {}
470
471      SymEdgeIt(const SymSmartGraph& g)
472        : SymSmartGraph::Parent::EdgeIt(g) {}
473
474      SymEdgeIt(const SymSmartGraph& g, SymEdge e)
475        : SymSmartGraph::Parent::EdgeIt(g, e) {}
476
477      SymEdgeIt(Invalid i)
478        : SymSmartGraph::Parent::EdgeIt(INVALID) {}
479
480      SymEdgeIt& operator++() {
481        SymSmartGraph::Parent::EdgeIt::operator++();
482        return *this;
483      }
484
485      operator SymEdge() const {
486        return SymEdge
487          (static_cast<const SymSmartGraph::Parent::EdgeIt&>(*this));
488      }
489      bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}
490      bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}
491      bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}
492    };
493
494    class EdgeIt {
495      SymEdgeIt it;
496      bool fw;
497    public:
498      EdgeIt(const SymSmartGraph& g) : it(g), fw(true) {}
499      EdgeIt (Invalid i) : it(i) { }
500      EdgeIt(const SymSmartGraph& g, Edge e)
501        : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }
502      EdgeIt() { }
503      EdgeIt& operator++() {
504        fw = !fw;
505        if (fw) ++it;
506        return *this;
507      }
508      operator Edge() const {
509        if (it == INVALID) return INVALID;
510        return fw ? forward(it) : backward(it);
511      }
512      bool operator==(const Edge i) const {return Edge(*this) == i;}
513      bool operator!=(const Edge i) const {return Edge(*this) != i;}
514      bool operator<(const Edge i) const {return Edge(*this) < i;}
515
516    };
517
518    ///Number of nodes.
519    int nodeNum() const { return Parent::nodeNum(); }
520    ///Number of edges.
521    int edgeNum() const { return 2*Parent::edgeNum(); }
522    ///Number of symmetric edges.
523    int symEdgeNum() const { return Parent::edgeNum(); }
524
525    /// Maximum node ID.
526   
527    /// Maximum node ID.
528    ///\sa id(Node)
529    int maxNodeId() const { return Parent::maxNodeId(); }
530    /// Maximum edge ID.
531   
532    /// Maximum edge ID.
533    ///\sa id(Edge)
534    int maxEdgeId() const { return 2*Parent::maxEdgeId(); }
535    /// Maximum symmetric edge ID.
536   
537    /// Maximum symmetric edge ID.
538    ///\sa id(SymEdge)
539    int maxSymEdgeId() const { return Parent::maxEdgeId(); }
540
541
542    Node tail(Edge e) const {
543      return e.id & 1 == 0 ?
544        Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e));
545    }
546
547    Node head(Edge e) const {
548      return e.id & 1 == 0 ?
549        Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e));
550    }
551
552    Node tail(SymEdge e) const {
553      return Parent::tail(e);
554    }
555
556    Node head(SymEdge e) const {
557      return Parent::head(e);
558    }
559
560    NodeIt& first(NodeIt& v) const {
561      v=NodeIt(*this); return v; }
562    EdgeIt& first(EdgeIt& e) const {
563      e=EdgeIt(*this); return e; }
564    SymEdgeIt& first(SymEdgeIt& e) const {
565      e=SymEdgeIt(*this); return e; }
566    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
567      e=OutEdgeIt(*this,v); return e; }
568    InEdgeIt& first(InEdgeIt& e, const Node v) const {
569      e=InEdgeIt(*this,v); return e; }
570
571    /// Node ID.
572   
573    /// The ID of a valid Node is a nonnegative integer not greater than
574    /// \ref maxNodeId(). The range of the ID's is not surely continuous
575    /// and the greatest node ID can be actually less then \ref maxNodeId().
576    ///
577    /// The ID of the \ref INVALID node is -1.
578    ///\return The ID of the node \c v.
579    static int id(Node v) { return Parent::id(v); }
580    /// Edge ID.
581   
582    /// The ID of a valid Edge is a nonnegative integer not greater than
583    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
584    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
585    ///
586    /// The ID of the \ref INVALID edge is -1.
587    ///\return The ID of the edge \c e.
588    static int id(Edge e) { return e.id; }
589
590    /// The ID of a valid SymEdge is a nonnegative integer not greater than
591    /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous
592    /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().
593    ///
594    /// The ID of the \ref INVALID symmetric edge is -1.
595    ///\return The ID of the edge \c e.
596    static int id(SymEdge e) { return Parent::id(e); }
597
598    /// Adds a new node to the graph.
599
600    /// \warning It adds the new node to the front of the list.
601    /// (i.e. the lastly added node becomes the first.)
602    Node addNode() {
603      return Parent::addNode();
604    }
605   
606    SymEdge addEdge(Node u, Node v) {
607      SymEdge se = Parent::addEdge(u, v);
608      edge_maps.add(forward(se));
609      edge_maps.add(backward(se));
610      return se;
611    }
612   
613    /// Finds an edge between two nodes.
614
615    /// Finds an edge from node \c u to node \c v.
616    ///
617    /// If \c prev is \ref INVALID (this is the default value), then
618    /// It finds the first edge from \c u to \c v. Otherwise it looks for
619    /// the next edge from \c u to \c v after \c prev.
620    /// \return The found edge or INVALID if there is no such an edge.
621    Edge findEdge(Node u, Node v, Edge prev = INVALID)
622    {     
623      if (prev == INVALID || id(prev) & 1 == 0) {
624        SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
625        if (se != INVALID) return forward(se);
626      } else {
627        SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
628        if (se != INVALID) return backward(se);
629      }
630      return INVALID;
631    }
632
633    /// Finds an symmetric edge between two nodes.
634
635    /// Finds an symmetric edge from node \c u to node \c v.
636    ///
637    /// If \c prev is \ref INVALID (this is the default value), then
638    /// It finds the first edge from \c u to \c v. Otherwise it looks for
639    /// the next edge from \c u to \c v after \c prev.
640    /// \return The found edge or INVALID if there is no such an edge.
641
642//     SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID)
643//     {     
644//       if (prev == INVALID || id(prev) & 1 == 0) {
645//      SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
646//      if (se != INVALID) return se;
647//       } else {
648//      SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
649//      if (se != INVALID) return se;   
650//       }
651//       return INVALID;
652//     }
653   
654  public:
655
656    void clear() {
657      edge_maps.clear();
658      Parent::clear();
659    }
660
661    static Edge opposite(Edge e) {
662      return Edge(id(e) ^ 1);
663    }
664
665    static Edge forward(SymEdge e) {
666      return Edge(id(e) << 1);
667    }
668
669    static Edge backward(SymEdge e) {
670      return Edge((id(e) << 1) & 1);
671    }
672
673  };
674  ///Graph for bidirectional edges.
675
676  ///The purpose of this graph structure is to handle graphs
677  ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
678  ///of oppositely directed edges.
679  ///There is a new edge map type called
680  ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
681  ///that complements this
682  ///feature by
683  ///storing shared values for the edge pairs. The usual
684  ///\ref Graph::EdgeMap "EdgeMap"
685  ///can be used
686  ///as well.
687  ///
688  ///The oppositely directed edge can also be obtained easily
689  ///using \ref opposite.
690  ///\warning It shares the similarity with \ref SmartGraph that
691  ///it is not possible to delete edges or nodes from the graph.
692  //\sa SmartGraph.
693
694  /*  class SymSmartGraph : public SmartGraph
695  {
696  public:
697    typedef SymSmartGraph Graph;
698
699    // Create symmetric map registry.
700    CREATE_SYM_EDGE_MAP_REGISTRY;
701    // Create symmetric edge map.
702    CREATE_SYM_EDGE_MAP(ArrayMap);
703
704
705    SymSmartGraph() : SmartGraph() { }
706    SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
707    ///Adds a pair of oppositely directed edges to the graph.
708    Edge addEdge(Node u, Node v)
709    {
710      Edge e = SmartGraph::addEdge(u,v);
711      Edge f = SmartGraph::addEdge(v,u);
712      sym_edge_maps.add(e);
713      sym_edge_maps.add(f);
714      return e;
715    }
716
717    ///The oppositely directed edge.
718
719    ///Returns the oppositely directed
720    ///pair of the edge \c e.
721    static Edge opposite(Edge e)
722    {
723      Edge f;
724      f.n = e.n - 2*(e.n%2) + 1;
725      return f;
726    }
727   
728
729    };*/
730 
731  /// @} 
732} //namespace hugo
733
734
735
736
737#endif //HUGO_SMART_GRAPH_H
Note: See TracBrowser for help on using the repository browser.