COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/full_graph.h @ 2256:b22dfb6c5ff3

Last change on this file since 2256:b22dfb6c5ff3 was 2256:b22dfb6c5ff3, checked in by Alpar Juttner, 17 years ago

Graph imlementations actually provide ReferenceMaps?.

File size: 21.3 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_FULL_GRAPH_H
20#define LEMON_FULL_GRAPH_H
21
22#include <cmath>
23
24#include <lemon/bits/base_extender.h>
25#include <lemon/bits/graph_extender.h>
26
27#include <lemon/bits/invalid.h>
28#include <lemon/bits/utility.h>
29
30
31///\ingroup graphs
32///\file
33///\brief FullGraph and FullUGraph classes.
34
35
36namespace lemon {
37
38  class FullGraphBase {
39    int _nodeNum;
40    int _edgeNum;
41  public:
42
43    typedef FullGraphBase Graph;
44
45    class Node;
46    class Edge;
47
48  protected:
49
50    FullGraphBase() {}
51
52    void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
53
54  public:
55   
56    typedef True NodeNumTag;
57    typedef True EdgeNumTag;
58
59    Node operator()(int index) const { return Node(index); }
60    int index(const Node& node) const { return node.id; }
61
62    Edge edge(const Node& u, const Node& v) const {
63      return Edge(*this, u.id, v.id);
64    }
65
66    int nodeNum() const { return _nodeNum; }
67    int edgeNum() const { return _edgeNum; }
68
69    int maxNodeId() const { return _nodeNum-1; }
70    int maxEdgeId() const { return _edgeNum-1; }
71
72    Node source(Edge e) const { return e.id % _nodeNum; }
73    Node target(Edge e) const { return e.id / _nodeNum; }
74
75
76    static int id(Node v) { return v.id; }
77    static int id(Edge e) { return e.id; }
78
79    static Node nodeFromId(int id) { return Node(id);}
80   
81    static Edge edgeFromId(int id) { return Edge(id);}
82
83    typedef True FindEdgeTag;
84
85    Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
86      return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
87    }
88   
89     
90    class Node {
91      friend class FullGraphBase;
92
93    protected:
94      int id;
95      Node(int _id) : id(_id) {}
96    public:
97      Node() {}
98      Node (Invalid) : id(-1) {}
99      bool operator==(const Node node) const {return id == node.id;}
100      bool operator!=(const Node node) const {return id != node.id;}
101      bool operator<(const Node node) const {return id < node.id;}
102    };
103   
104
105
106    class Edge {
107      friend class FullGraphBase;
108     
109    protected:
110      int id;  // _nodeNum * target + source;
111
112      Edge(int _id) : id(_id) {}
113
114      Edge(const FullGraphBase& _graph, int source, int target)
115        : id(_graph._nodeNum * target+source) {}
116    public:
117      Edge() { }
118      Edge (Invalid) { id = -1; }
119      bool operator==(const Edge edge) const {return id == edge.id;}
120      bool operator!=(const Edge edge) const {return id != edge.id;}
121      bool operator<(const Edge edge) const {return id < edge.id;}
122    };
123
124    void first(Node& node) const {
125      node.id = _nodeNum-1;
126    }
127
128    static void next(Node& node) {
129      --node.id;
130    }
131
132    void first(Edge& edge) const {
133      edge.id = _edgeNum-1;
134    }
135
136    static void next(Edge& edge) {
137      --edge.id;
138    }
139
140    void firstOut(Edge& edge, const Node& node) const {
141      edge.id = _edgeNum + node.id - _nodeNum;
142    }
143
144    void nextOut(Edge& edge) const {
145      edge.id -= _nodeNum;
146      if (edge.id < 0) edge.id = -1;
147    }
148
149    void firstIn(Edge& edge, const Node& node) const {
150      edge.id = node.id * _nodeNum;
151    }
152   
153    void nextIn(Edge& edge) const {
154      ++edge.id;
155      if (edge.id % _nodeNum == 0) edge.id = -1;
156    }
157
158  };
159
160  typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
161
162  /// \ingroup graphs
163  ///
164  /// \brief A full graph class.
165  ///
166  /// This is a simple and fast directed full graph implementation.
167  /// It is completely static, so you can neither add nor delete either
168  /// edges or nodes.
169  /// Thus it conforms to
170  /// the \ref concept::Graph "Graph" concept and
171  ///it also has an
172  ///important extra feature that
173  ///its maps are real \ref concept::ReferenceMap "reference map"s.
174  /// \sa concept::Graph.
175  ///
176  /// \sa FullUGraph
177  ///
178  /// \author Alpar Juttner
179  class FullGraph : public ExtendedFullGraphBase {
180  public:
181
182    typedef ExtendedFullGraphBase Parent;
183
184    /// \brief Constructor
185    FullGraph() { construct(0); }
186
187    /// \brief Constructor
188    ///
189    FullGraph(int n) { construct(n); }
190
191    /// \brief Resize the graph
192    ///
193    /// Resize the graph. The function will fully destroy and build the graph.
194    /// This cause that the maps of the graph will reallocated
195    /// automatically and the previous values will be lost.
196    void resize(int n) {
197      Parent::getNotifier(Edge()).clear();
198      Parent::getNotifier(Node()).clear();
199      construct(n);
200      Parent::getNotifier(Node()).build();
201      Parent::getNotifier(Edge()).build();
202    }
203
204    /// \brief Returns the node with the given index.
205    ///
206    /// Returns the node with the given index. Because it is a
207    /// static size graph the node's of the graph can be indiced
208    /// by the range from 0 to \e nodeNum()-1 and the index of
209    /// the node can accessed by the \e index() member.
210    Node operator()(int index) const { return Parent::operator()(index); }
211
212    /// \brief Returns the index of the node.
213    ///
214    /// Returns the index of the node. Because it is a
215    /// static size graph the node's of the graph can be indiced
216    /// by the range from 0 to \e nodeNum()-1 and the index of
217    /// the node can accessed by the \e index() member.
218    int index(const Node& node) const { return Parent::index(node); }
219
220    /// \brief Returns the edge connects the given nodes.
221    ///
222    /// Returns the edge connects the given nodes.
223    Edge edge(const Node& u, const Node& v) const {
224      return Parent::edge(u, v);
225    }
226
227    /// \brief Number of nodes.
228    int nodeNum() const { return Parent::nodeNum(); }
229    /// \brief Number of edges.
230    int edgeNum() const { return Parent::edgeNum(); }
231  };
232
233
234  class FullUGraphBase {
235    int _nodeNum;
236    int _edgeNum;
237  public:
238
239    typedef FullUGraphBase Graph;
240
241    class Node;
242    class Edge;
243
244  protected:
245
246    FullUGraphBase() {}
247
248    void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
249
250  public:
251
252
253    Node operator()(int index) const { return Node(index); }
254    int index(const Node& node) const { return node.id; }
255
256    Edge edge(const Node& u, const Node& v) const {
257      return Edge(u.id * (u.id - 1) / 2 + v.id);
258    }
259
260    typedef True NodeNumTag;
261    typedef True EdgeNumTag;
262
263    int nodeNum() const { return _nodeNum; }
264    int edgeNum() const { return _edgeNum; }
265
266    int maxNodeId() const { return _nodeNum-1; }
267    int maxEdgeId() const { return _edgeNum-1; }
268
269    static Node nodeFromId(int id) { return Node(id);}
270    static Edge edgeFromId(int id) { return Edge(id);}
271
272    Node source(Edge e) const {
273      /// \todo we may do it faster
274      return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
275    }
276
277    Node target(Edge e) const {
278      int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
279      return Node(e.id - (source) * (source - 1) / 2);
280    }
281
282    static int id(Node v) { return v.id; }
283    static int id(Edge e) { return e.id; }
284
285    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
286      if (prev.id != -1 || u.id <= v.id) return Edge(-1);
287      return Edge(u.id * (u.id - 1) / 2 + v.id);
288    }
289
290    typedef True FindEdgeTag;
291   
292     
293    class Node {
294      friend class FullUGraphBase;
295
296    protected:
297      int id;
298      Node(int _id) { id = _id;}
299    public:
300      Node() {}
301      Node (Invalid) { id = -1; }
302      bool operator==(const Node node) const {return id == node.id;}
303      bool operator!=(const Node node) const {return id != node.id;}
304      bool operator<(const Node node) const {return id < node.id;}
305    };
306   
307
308
309    class Edge {
310      friend class FullUGraphBase;
311     
312    protected:
313      int id;  // _nodeNum * target + source;
314
315      Edge(int _id) : id(_id) {}
316
317    public:
318      Edge() { }
319      Edge (Invalid) { id = -1; }
320      bool operator==(const Edge edge) const {return id == edge.id;}
321      bool operator!=(const Edge edge) const {return id != edge.id;}
322      bool operator<(const Edge edge) const {return id < edge.id;}
323    };
324
325    void first(Node& node) const {
326      node.id = _nodeNum - 1;
327    }
328
329    static void next(Node& node) {
330      --node.id;
331    }
332
333    void first(Edge& edge) const {
334      edge.id = _edgeNum - 1;
335    }
336
337    static void next(Edge& edge) {
338      --edge.id;
339    }
340
341    void firstOut(Edge& edge, const Node& node) const {     
342      int src = node.id;
343      int trg = 0;
344      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
345    }
346
347    /// \todo with specialized iterators we can make faster iterating
348    void nextOut(Edge& edge) const {
349      int src = source(edge).id;
350      int trg = target(edge).id;
351      ++trg;
352      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
353    }
354
355    void firstIn(Edge& edge, const Node& node) const {
356      int src = node.id + 1;
357      int trg = node.id;
358      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
359    }
360   
361    void nextIn(Edge& edge) const {
362      int src = source(edge).id;
363      int trg = target(edge).id;
364      ++src;
365      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
366    }
367
368  };
369
370  typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> >
371  ExtendedFullUGraphBase;
372
373  /// \ingroup graphs
374  ///
375  /// \brief An undirected full graph class.
376  ///
377  /// This is a simple and fast undirected full graph implementation.
378  /// It is completely static, so you can neither add nor delete either
379  /// edges or nodes.
380  ///
381  /// The main difference beetween the \e FullGraph and \e FullUGraph class
382  /// is that this class conforms to the undirected graph concept and
383  /// it does not contain the loop edges.
384  ///
385  ///It also has an
386  ///important extra feature that
387  ///its maps are real \ref concept::ReferenceMap "reference map"s.
388  ///
389  /// \sa FullGraph
390  ///
391  /// \author Balazs Dezso
392  class FullUGraph : public ExtendedFullUGraphBase {
393  public:
394
395    typedef ExtendedFullUGraphBase Parent;
396
397    /// \brief Constructor
398    FullUGraph() { construct(0); }
399
400    /// \brief Constructor
401    FullUGraph(int n) { construct(n); }
402
403    /// \brief Resize the graph
404    ///
405    /// Resize the graph. The function will fully destroy and build the graph.
406    /// This cause that the maps of the graph will reallocated
407    /// automatically and the previous values will be lost.
408    void resize(int n) {
409      Parent::getNotifier(Edge()).clear();
410      Parent::getNotifier(UEdge()).clear();
411      Parent::getNotifier(Node()).clear();
412      construct(n);
413      Parent::getNotifier(Node()).build();
414      Parent::getNotifier(UEdge()).build();
415      Parent::getNotifier(Edge()).build();
416    }
417
418    /// \brief Returns the node with the given index.
419    ///
420    /// Returns the node with the given index. Because it is a
421    /// static size graph the node's of the graph can be indiced
422    /// by the range from 0 to \e nodeNum()-1 and the index of
423    /// the node can accessed by the \e index() member.
424    Node operator()(int index) const { return Parent::operator()(index); }
425
426    /// \brief Returns the index of the node.
427    ///
428    /// Returns the index of the node. Because it is a
429    /// static size graph the node's of the graph can be indiced
430    /// by the range from 0 to \e nodeNum()-1 and the index of
431    /// the node can accessed by the \e index() member.
432    int index(const Node& node) const { return Parent::index(node); }
433
434    /// \brief Number of nodes.
435    int nodeNum() const { return Parent::nodeNum(); }
436    /// \brief Number of edges.
437    int edgeNum() const { return Parent::edgeNum(); }
438    /// \brief Number of undirected edges.
439    int uEdgeNum() const { return Parent::uEdgeNum(); }
440
441    /// \brief Returns the edge connects the given nodes.
442    ///
443    /// Returns the edge connects the given nodes.
444    Edge edge(const Node& u, const Node& v) const {
445      if (Parent::index(u) > Parent::index(v)) {
446        return Parent::direct(Parent::edge(u, v), true);
447      } else if (Parent::index(u) == Parent::index(v)) {
448        return INVALID;
449      } else {
450        return Parent::direct(Parent::edge(v, u), false);
451      }
452    }
453
454    /// \brief Returns the undirected edge connects the given nodes.
455    ///
456    /// Returns the undirected edge connects the given nodes.
457    UEdge uEdge(const Node& u, const Node& v) const {
458      if (Parent::index(u) > Parent::index(v)) {
459        return Parent::edge(u, v);
460      } else if (Parent::index(u) == Parent::index(v)) {
461        return INVALID;
462      } else {
463        return Parent::edge(v, u);
464      }
465    }
466  };
467
468
469  class FullBpUGraphBase {
470  protected:
471
472    int _aNodeNum;
473    int _bNodeNum;
474
475    int _edgeNum;
476
477  protected:
478
479    FullBpUGraphBase() {}
480
481    void construct(int aNodeNum, int bNodeNum) {
482      _aNodeNum = aNodeNum;
483      _bNodeNum = bNodeNum;
484      _edgeNum = aNodeNum * bNodeNum;
485    }
486
487  public:
488
489    class NodeSetError : public LogicError {
490    public:
491      virtual const char* what() const throw() {
492        return "lemon::FullBpUGraph::NodeSetError";
493      }
494    };
495 
496    class Node {
497      friend class FullBpUGraphBase;
498    protected:
499      int id;
500
501      Node(int _id) : id(_id) {}
502    public:
503      Node() {}
504      Node(Invalid) { id = -1; }
505      bool operator==(const Node i) const {return id==i.id;}
506      bool operator!=(const Node i) const {return id!=i.id;}
507      bool operator<(const Node i) const {return id<i.id;}
508    };
509
510    class UEdge {
511      friend class FullBpUGraphBase;
512    protected:
513      int id;
514
515      UEdge(int _id) { id = _id;}
516    public:
517      UEdge() {}
518      UEdge (Invalid) { id = -1; }
519      bool operator==(const UEdge i) const {return id==i.id;}
520      bool operator!=(const UEdge i) const {return id!=i.id;}
521      bool operator<(const UEdge i) const {return id<i.id;}
522    };
523
524    Node aNode(int index) const { return Node(index << 1); }
525    Node bNode(int index) const { return Node((index << 1) + 1); }
526
527    int aNodeIndex(const Node& node) const { return node.id >> 1; }
528    int bNodeIndex(const Node& node) const { return node.id >> 1; }
529
530    UEdge uEdge(const Node& u, const Node& v) const {
531      if (((u.id ^ v.id) & 1) != 1) {
532        return UEdge(-1);
533      } else if ((u.id & 1) == 0) {
534        return UEdge((u.id >> 1) * _bNodeNum + (v.id >> 1));
535      } else {
536        return UEdge((v.id >> 1) * _bNodeNum + (u.id >> 1));
537      }
538    }
539
540    void firstANode(Node& node) const {
541      node.id = 2 * _aNodeNum - 2;
542      if (node.id < 0) node.id = -1;
543    }
544    void nextANode(Node& node) const {
545      node.id -= 2;
546      if (node.id < 0) node.id = -1;
547    }
548
549    void firstBNode(Node& node) const {
550      node.id = 2 * _bNodeNum - 1;
551    }
552    void nextBNode(Node& node) const {
553      node.id -= 2;
554    }
555
556    void first(Node& node) const {
557      if (_aNodeNum > 0) {
558        node.id = 2 * _aNodeNum - 2;
559      } else {
560        node.id = 2 * _bNodeNum - 1;
561      }
562    }
563    void next(Node& node) const {
564      node.id -= 2;
565      if (node.id == -2) {
566        node.id = 2 * _bNodeNum - 1;
567      }
568    }
569 
570    void first(UEdge& edge) const {
571      edge.id = _edgeNum - 1;
572    }
573    void next(UEdge& edge) const {
574      --edge.id;
575    }
576
577    void firstFromANode(UEdge& edge, const Node& node) const {
578      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
579      edge.id = (node.id >> 1) * _bNodeNum;
580    }
581    void nextFromANode(UEdge& edge) const {
582      ++(edge.id);
583      if (edge.id % _bNodeNum == 0) edge.id = -1;
584    }
585
586    void firstFromBNode(UEdge& edge, const Node& node) const {
587      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
588      edge.id = (node.id >> 1);
589    }
590    void nextFromBNode(UEdge& edge) const {
591      edge.id += _bNodeNum;
592      if (edge.id >= _edgeNum) edge.id = -1;
593    }
594
595    static int id(const Node& node) {
596      return node.id;
597    }
598    static Node nodeFromId(int id) {
599      return Node(id);
600    }
601    int maxNodeId() const {
602      return _aNodeNum > _bNodeNum ?
603        _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
604    }
605 
606    static int id(const UEdge& edge) {
607      return edge.id;
608    }
609    static UEdge uEdgeFromId(int id) {
610      return UEdge(id);
611    }
612    int maxUEdgeId() const {
613      return _edgeNum - 1;
614    }
615 
616    static int aNodeId(const Node& node) {
617      return node.id >> 1;
618    }
619    static Node nodeFromANodeId(int id) {
620      return Node(id << 1);
621    }
622    int maxANodeId() const {
623      return _aNodeNum;
624    }
625
626    static int bNodeId(const Node& node) {
627      return node.id >> 1;
628    }
629    static Node nodeFromBNodeId(int id) {
630      return Node((id << 1) + 1);
631    }
632    int maxBNodeId() const {
633      return _bNodeNum;
634    }
635
636    Node aNode(const UEdge& edge) const {
637      return Node((edge.id / _bNodeNum) << 1);
638    }
639    Node bNode(const UEdge& edge) const {
640      return Node(((edge.id % _bNodeNum) << 1) + 1);
641    }
642
643    static bool aNode(const Node& node) {
644      return (node.id & 1) == 0;
645    }
646
647    static bool bNode(const Node& node) {
648      return (node.id & 1) == 1;
649    }
650
651
652    typedef True NodeNumTag;
653    int nodeNum() const { return _aNodeNum + _bNodeNum; }
654    int aNodeNum() const { return _aNodeNum; }
655    int bNodeNum() const { return _bNodeNum; }
656
657    typedef True EdgeNumTag;
658    int uEdgeNum() const { return _edgeNum; }
659
660
661    typedef True FindEdgeTag;
662    UEdge findUEdge(Node u, Node v, UEdge prev = INVALID) const {
663      if (prev.id != -1 || ((u.id ^ v.id) & 1) != 1) {
664        return UEdge(-1);
665      } else if ((u.id & 1) == 0) {
666        return UEdge((u.id >> 1) * _bNodeNum + (v.id >> 1));
667      } else {
668        return UEdge((v.id >> 1) * _bNodeNum + (u.id >> 1));
669      }
670    }
671
672  };
673
674
675  typedef BpUGraphExtender<BidirBpUGraphExtender<FullBpUGraphBase> >
676  ExtendedFullBpUGraphBase;
677
678
679  /// \ingroup graphs
680  ///
681  /// \brief An undirected full bipartite graph class.
682  ///
683  /// This is a simple and fast bipartite undirected full graph implementation.
684  /// It is completely static, so you can neither add nor delete either
685  /// edges or nodes.
686  ///
687  /// \author Balazs Dezso
688  class FullBpUGraph :
689    public ExtendedFullBpUGraphBase {
690  public:
691
692    typedef ExtendedFullBpUGraphBase Parent;
693
694    FullBpUGraph() {
695      Parent::construct(0, 0);
696    }
697
698    FullBpUGraph(int aNodeNum, int bNodeNum) {
699      Parent::construct(aNodeNum, bNodeNum);
700    }
701
702    /// \brief Resize the graph
703    ///
704    /// Resize the graph
705    void resize(int n, int m) {
706      Parent::getNotifier(Edge()).clear();
707      Parent::getNotifier(UEdge()).clear();
708      Parent::getNotifier(Node()).clear();
709      Parent::getNotifier(ANode()).clear();
710      Parent::getNotifier(BNode()).clear();
711      construct(n, m);
712      Parent::getNotifier(ANode()).build();
713      Parent::getNotifier(BNode()).build();
714      Parent::getNotifier(Node()).build();
715      Parent::getNotifier(UEdge()).build();
716      Parent::getNotifier(Edge()).build();
717    }
718
719    /// \brief Number of nodes.
720    int nodeNum() const { return Parent::nodeNum(); }
721    /// \brief Number of A-nodes.
722    int aNodeNum() const { return Parent::aNodeNum(); }
723    /// \brief Number of B-nodes.
724    int bNodeNum() const { return Parent::bNodeNum(); }
725    /// \brief Number of edges.
726    int edgeNum() const { return Parent::edgeNum(); }
727    /// \brief Number of undirected edges.
728    int uEdgeNum() const { return Parent::uEdgeNum(); }
729
730
731    using Parent::aNode;
732    using Parent::bNode;
733
734    /// \brief Returns the A-node with the given index.
735    ///
736    /// Returns the A-node with the given index. Because it is a
737    /// static size graph the node's of the graph can be indiced
738    /// by the range from 0 to \e aNodeNum()-1 and the index of
739    /// the node can accessed by the \e aNodeIndex() member.
740    Node aNode(int index) const { return Parent::aNode(index); }
741
742    /// \brief Returns the B-node with the given index.
743    ///
744    /// Returns the B-node with the given index. Because it is a
745    /// static size graph the node's of the graph can be indiced
746    /// by the range from 0 to \e bNodeNum()-1 and the index of
747    /// the node can accessed by the \e bNodeIndex() member.
748    Node bNode(int index) const { return Parent::bNode(index); }
749
750    /// \brief Returns the index of the A-node.
751    ///
752    /// Returns the index of the A-node. Because it is a
753    /// static size graph the node's of the graph can be indiced
754    /// by the range from 0 to \e aNodeNum()-1 and the index of
755    /// the node can accessed by the \e aNodeIndex() member.
756    int aNodeIndex(const Node& node) const { return Parent::aNodeIndex(node); }
757
758    /// \brief Returns the index of the B-node.
759    ///
760    /// Returns the index of the B-node. Because it is a
761    /// static size graph the node's of the graph can be indiced
762    /// by the range from 0 to \e bNodeNum()-1 and the index of
763    /// the node can accessed by the \e bNodeIndex() member.
764    int bNodeIndex(const Node& node) const { return Parent::bNodeIndex(node); }
765
766    /// \brief Returns the edge connects the given nodes.
767    ///
768    /// Returns the edge connects the given nodes.
769    Edge edge(const Node& u, const Node& v) const {
770      UEdge uedge = Parent::uEdge(u, v);
771      if (uedge != INVALID) {
772        return Parent::direct(uedge, Parent::aNode(u));
773      } else {
774        return INVALID;
775      }
776    }
777
778    /// \brief Returns the undirected edge connects the given nodes.
779    ///
780    /// Returns the undirected edge connects the given nodes.
781    UEdge uEdge(const Node& u, const Node& v) const {
782      return Parent::uEdge(u, v);
783    }
784  };
785
786} //namespace lemon
787
788
789#endif //LEMON_FULL_GRAPH_H
Note: See TracBrowser for help on using the repository browser.