COIN-OR::LEMON - Graph Library

source: lemon/lemon/concepts/bpgraph.h @ 1369:9fd86ec2cb81

Last change on this file since 1369:9fd86ec2cb81 was 1336:0759d974de81, checked in by Gabor Gevay <ggab90@…>, 6 years ago

STL style iterators (#325)

For

  • graph types,
  • graph adaptors,
  • paths,
  • iterable maps,
  • LP rows/cols and
  • active nodes is BellmanFord?
File size: 37.7 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2013
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///\ingroup graph_concepts
20///\file
21///\brief The concept of undirected graphs.
22
23#ifndef LEMON_CONCEPTS_BPGRAPH_H
24#define LEMON_CONCEPTS_BPGRAPH_H
25
26#include <lemon/concepts/graph_components.h>
27#include <lemon/concepts/maps.h>
28#include <lemon/concept_check.h>
29#include <lemon/core.h>
30#include <lemon/bits/stl_iterators.h>
31
32namespace lemon {
33  namespace concepts {
34
35    /// \ingroup graph_concepts
36    ///
37    /// \brief Class describing the concept of undirected bipartite graphs.
38    ///
39    /// This class describes the common interface of all undirected
40    /// bipartite graphs.
41    ///
42    /// Like all concept classes, it only provides an interface
43    /// without any sensible implementation. So any general algorithm for
44    /// undirected bipartite graphs should compile with this class,
45    /// but it will not run properly, of course.
46    /// An actual graph implementation like \ref ListBpGraph or
47    /// \ref SmartBpGraph may have additional functionality.
48    ///
49    /// The bipartite graphs also fulfill the concept of \ref Graph
50    /// "undirected graphs". Bipartite graphs provide a bipartition of
51    /// the node set, namely a red and blue set of the nodes. The
52    /// nodes can be iterated with the RedNodeIt and BlueNodeIt in the
53    /// two node sets. With RedNodeMap and BlueNodeMap values can be
54    /// assigned to the nodes in the two sets.
55    ///
56    /// The edges of the graph cannot connect two nodes of the same
57    /// set. The edges inherent orientation is from the red nodes to
58    /// the blue nodes.
59    ///
60    /// \sa Graph
61    class BpGraph {
62    private:
63      /// BpGraphs are \e not copy constructible. Use bpGraphCopy instead.
64      BpGraph(const BpGraph&) {}
65      /// \brief Assignment of a graph to another one is \e not allowed.
66      /// Use bpGraphCopy instead.
67      void operator=(const BpGraph&) {}
68
69    public:
70      /// Default constructor.
71      BpGraph() {}
72
73      /// \brief Undirected graphs should be tagged with \c UndirectedTag.
74      ///
75      /// Undirected graphs should be tagged with \c UndirectedTag.
76      ///
77      /// This tag helps the \c enable_if technics to make compile time
78      /// specializations for undirected graphs.
79      typedef True UndirectedTag;
80
81      /// The node type of the graph
82
83      /// This class identifies a node of the graph. It also serves
84      /// as a base class of the node iterators,
85      /// thus they convert to this type.
86      class Node {
87      public:
88        /// Default constructor
89
90        /// Default constructor.
91        /// \warning It sets the object to an undefined value.
92        Node() { }
93        /// Copy constructor.
94
95        /// Copy constructor.
96        ///
97        Node(const Node&) { }
98
99        /// %Invalid constructor \& conversion.
100
101        /// Initializes the object to be invalid.
102        /// \sa Invalid for more details.
103        Node(Invalid) { }
104        /// Equality operator
105
106        /// Equality operator.
107        ///
108        /// Two iterators are equal if and only if they point to the
109        /// same object or both are \c INVALID.
110        bool operator==(Node) const { return true; }
111
112        /// Inequality operator
113
114        /// Inequality operator.
115        bool operator!=(Node) const { return true; }
116
117        /// Artificial ordering operator.
118
119        /// Artificial ordering operator.
120        ///
121        /// \note This operator only has to define some strict ordering of
122        /// the items; this order has nothing to do with the iteration
123        /// ordering of the items.
124        bool operator<(Node) const { return false; }
125
126      };
127
128      /// Class to represent red nodes.
129
130      /// This class represents the red nodes of the graph. It does
131      /// not supposed to be used directly, because the nodes can be
132      /// represented as Node instances. This class can be used as
133      /// template parameter for special map classes.
134      class RedNode : public Node {
135      public:
136        /// Default constructor
137
138        /// Default constructor.
139        /// \warning It sets the object to an undefined value.
140        RedNode() { }
141        /// Copy constructor.
142
143        /// Copy constructor.
144        ///
145        RedNode(const RedNode&) : Node() { }
146
147        /// %Invalid constructor \& conversion.
148
149        /// Initializes the object to be invalid.
150        /// \sa Invalid for more details.
151        RedNode(Invalid) { }
152
153      };
154
155      /// Class to represent blue nodes.
156
157      /// This class represents the blue nodes of the graph. It does
158      /// not supposed to be used directly, because the nodes can be
159      /// represented as Node instances. This class can be used as
160      /// template parameter for special map classes.
161      class BlueNode : public Node {
162      public:
163        /// Default constructor
164
165        /// Default constructor.
166        /// \warning It sets the object to an undefined value.
167        BlueNode() { }
168        /// Copy constructor.
169
170        /// Copy constructor.
171        ///
172        BlueNode(const BlueNode&) : Node() { }
173
174        /// %Invalid constructor \& conversion.
175
176        /// Initializes the object to be invalid.
177        /// \sa Invalid for more details.
178        BlueNode(Invalid) { }
179
180      };
181
182      /// Iterator class for the red nodes.
183
184      /// This iterator goes through each red node of the graph.
185      /// Its usage is quite simple, for example, you can count the number
186      /// of red nodes in a graph \c g of type \c %BpGraph like this:
187      ///\code
188      /// int count=0;
189      /// for (BpGraph::RedNodeIt n(g); n!=INVALID; ++n) ++count;
190      ///\endcode
191      class RedNodeIt : public RedNode {
192      public:
193        /// Default constructor
194
195        /// Default constructor.
196        /// \warning It sets the iterator to an undefined value.
197        RedNodeIt() { }
198        /// Copy constructor.
199
200        /// Copy constructor.
201        ///
202        RedNodeIt(const RedNodeIt& n) : RedNode(n) { }
203        /// %Invalid constructor \& conversion.
204
205        /// Initializes the iterator to be invalid.
206        /// \sa Invalid for more details.
207        RedNodeIt(Invalid) { }
208        /// Sets the iterator to the first red node.
209
210        /// Sets the iterator to the first red node of the given
211        /// digraph.
212        explicit RedNodeIt(const BpGraph&) { }
213        /// Sets the iterator to the given red node.
214
215        /// Sets the iterator to the given red node of the given
216        /// digraph.
217        RedNodeIt(const BpGraph&, const RedNode&) { }
218        /// Next node.
219
220        /// Assign the iterator to the next red node.
221        ///
222        RedNodeIt& operator++() { return *this; }
223      };
224
225      /// \brief Gets the collection of the red nodes of the graph.
226      ///
227      /// This function can be used for iterating on
228      /// the red nodes of the graph. It returns a wrapped RedNodeIt,
229      /// which looks like an STL container (by having begin() and end())
230      /// which you can use in range-based for loops, stl algorithms, etc.
231      /// For example if g is a BpGraph, you can write:
232      ///\code
233      /// for(auto v: g.redNodes())
234      ///   doSomething(v);
235      ///\endcode
236      LemonRangeWrapper1<RedNodeIt, BpGraph> redNodes() const {
237        return LemonRangeWrapper1<RedNodeIt, BpGraph>(*this);
238      }
239
240
241      /// Iterator class for the blue nodes.
242
243      /// This iterator goes through each blue node of the graph.
244      /// Its usage is quite simple, for example, you can count the number
245      /// of blue nodes in a graph \c g of type \c %BpGraph like this:
246      ///\code
247      /// int count=0;
248      /// for (BpGraph::BlueNodeIt n(g); n!=INVALID; ++n) ++count;
249      ///\endcode
250      class BlueNodeIt : public BlueNode {
251      public:
252        /// Default constructor
253
254        /// Default constructor.
255        /// \warning It sets the iterator to an undefined value.
256        BlueNodeIt() { }
257        /// Copy constructor.
258
259        /// Copy constructor.
260        ///
261        BlueNodeIt(const BlueNodeIt& n) : BlueNode(n) { }
262        /// %Invalid constructor \& conversion.
263
264        /// Initializes the iterator to be invalid.
265        /// \sa Invalid for more details.
266        BlueNodeIt(Invalid) { }
267        /// Sets the iterator to the first blue node.
268
269        /// Sets the iterator to the first blue node of the given
270        /// digraph.
271        explicit BlueNodeIt(const BpGraph&) { }
272        /// Sets the iterator to the given blue node.
273
274        /// Sets the iterator to the given blue node of the given
275        /// digraph.
276        BlueNodeIt(const BpGraph&, const BlueNode&) { }
277        /// Next node.
278
279        /// Assign the iterator to the next blue node.
280        ///
281        BlueNodeIt& operator++() { return *this; }
282      };
283
284      /// \brief Gets the collection of the blue nodes of the graph.
285      ///
286      /// This function can be used for iterating on
287      /// the blue nodes of the graph. It returns a wrapped BlueNodeIt,
288      /// which looks like an STL container (by having begin() and end())
289      /// which you can use in range-based for loops, stl algorithms, etc.
290      /// For example if g is a BpGraph, you can write:
291      ///\code
292      /// for(auto v: g.blueNodes())
293      ///   doSomething(v);
294      ///\endcode
295      LemonRangeWrapper1<BlueNodeIt, BpGraph> blueNodes() const {
296        return LemonRangeWrapper1<BlueNodeIt, BpGraph>(*this);
297      }
298
299
300      /// Iterator class for the nodes.
301
302      /// This iterator goes through each node of the graph.
303      /// Its usage is quite simple, for example, you can count the number
304      /// of nodes in a graph \c g of type \c %BpGraph like this:
305      ///\code
306      /// int count=0;
307      /// for (BpGraph::NodeIt n(g); n!=INVALID; ++n) ++count;
308      ///\endcode
309      class NodeIt : public Node {
310      public:
311        /// Default constructor
312
313        /// Default constructor.
314        /// \warning It sets the iterator to an undefined value.
315        NodeIt() { }
316        /// Copy constructor.
317
318        /// Copy constructor.
319        ///
320        NodeIt(const NodeIt& n) : Node(n) { }
321        /// %Invalid constructor \& conversion.
322
323        /// Initializes the iterator to be invalid.
324        /// \sa Invalid for more details.
325        NodeIt(Invalid) { }
326        /// Sets the iterator to the first node.
327
328        /// Sets the iterator to the first node of the given digraph.
329        ///
330        explicit NodeIt(const BpGraph&) { }
331        /// Sets the iterator to the given node.
332
333        /// Sets the iterator to the given node of the given digraph.
334        ///
335        NodeIt(const BpGraph&, const Node&) { }
336        /// Next node.
337
338        /// Assign the iterator to the next node.
339        ///
340        NodeIt& operator++() { return *this; }
341      };
342
343      /// \brief Gets the collection of the nodes of the graph.
344      ///
345      /// This function can be used for iterating on
346      /// the nodes of the graph. It returns a wrapped NodeIt,
347      /// which looks like an STL container (by having begin() and end())
348      /// which you can use in range-based for loops, stl algorithms, etc.
349      /// For example if g is a BpGraph, you can write:
350      ///\code
351      /// for(auto v: g.nodes())
352      ///   doSomething(v);
353      ///\endcode
354      LemonRangeWrapper1<NodeIt, BpGraph> nodes() const {
355        return LemonRangeWrapper1<NodeIt, BpGraph>(*this);
356      }
357
358
359
360      /// The edge type of the graph
361
362      /// This class identifies an edge of the graph. It also serves
363      /// as a base class of the edge iterators,
364      /// thus they will convert to this type.
365      class Edge {
366      public:
367        /// Default constructor
368
369        /// Default constructor.
370        /// \warning It sets the object to an undefined value.
371        Edge() { }
372        /// Copy constructor.
373
374        /// Copy constructor.
375        ///
376        Edge(const Edge&) { }
377        /// %Invalid constructor \& conversion.
378
379        /// Initializes the object to be invalid.
380        /// \sa Invalid for more details.
381        Edge(Invalid) { }
382        /// Equality operator
383
384        /// Equality operator.
385        ///
386        /// Two iterators are equal if and only if they point to the
387        /// same object or both are \c INVALID.
388        bool operator==(Edge) const { return true; }
389        /// Inequality operator
390
391        /// Inequality operator.
392        bool operator!=(Edge) const { return true; }
393
394        /// Artificial ordering operator.
395
396        /// Artificial ordering operator.
397        ///
398        /// \note This operator only has to define some strict ordering of
399        /// the edges; this order has nothing to do with the iteration
400        /// ordering of the edges.
401        bool operator<(Edge) const { return false; }
402      };
403
404      /// Iterator class for the edges.
405
406      /// This iterator goes through each edge of the graph.
407      /// Its usage is quite simple, for example, you can count the number
408      /// of edges in a graph \c g of type \c %BpGraph as follows:
409      ///\code
410      /// int count=0;
411      /// for(BpGraph::EdgeIt e(g); e!=INVALID; ++e) ++count;
412      ///\endcode
413      class EdgeIt : public Edge {
414      public:
415        /// Default constructor
416
417        /// Default constructor.
418        /// \warning It sets the iterator to an undefined value.
419        EdgeIt() { }
420        /// Copy constructor.
421
422        /// Copy constructor.
423        ///
424        EdgeIt(const EdgeIt& e) : Edge(e) { }
425        /// %Invalid constructor \& conversion.
426
427        /// Initializes the iterator to be invalid.
428        /// \sa Invalid for more details.
429        EdgeIt(Invalid) { }
430        /// Sets the iterator to the first edge.
431
432        /// Sets the iterator to the first edge of the given graph.
433        ///
434        explicit EdgeIt(const BpGraph&) { }
435        /// Sets the iterator to the given edge.
436
437        /// Sets the iterator to the given edge of the given graph.
438        ///
439        EdgeIt(const BpGraph&, const Edge&) { }
440        /// Next edge
441
442        /// Assign the iterator to the next edge.
443        ///
444        EdgeIt& operator++() { return *this; }
445      };
446
447      /// \brief Gets the collection of the edges of the graph.
448      ///
449      /// This function can be used for iterating on the
450      /// edges of the graph. It returns a wrapped
451      /// EdgeIt, which looks like an STL container
452      /// (by having begin() and end()) which you can use in range-based
453      /// for loops, stl algorithms, etc.
454      /// For example if g is a BpGraph, you can write:
455      ///\code
456      /// for(auto e: g.edges())
457      ///   doSomething(e);
458      ///\endcode
459      LemonRangeWrapper1<EdgeIt, BpGraph> edges() const {
460        return LemonRangeWrapper1<EdgeIt, BpGraph>(*this);
461      }
462
463
464      /// Iterator class for the incident edges of a node.
465
466      /// This iterator goes trough the incident undirected edges
467      /// of a certain node of a graph.
468      /// Its usage is quite simple, for example, you can compute the
469      /// degree (i.e. the number of incident edges) of a node \c n
470      /// in a graph \c g of type \c %BpGraph as follows.
471      ///
472      ///\code
473      /// int count=0;
474      /// for(BpGraph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
475      ///\endcode
476      ///
477      /// \warning Loop edges will be iterated twice.
478      class IncEdgeIt : public Edge {
479      public:
480        /// Default constructor
481
482        /// Default constructor.
483        /// \warning It sets the iterator to an undefined value.
484        IncEdgeIt() { }
485        /// Copy constructor.
486
487        /// Copy constructor.
488        ///
489        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
490        /// %Invalid constructor \& conversion.
491
492        /// Initializes the iterator to be invalid.
493        /// \sa Invalid for more details.
494        IncEdgeIt(Invalid) { }
495        /// Sets the iterator to the first incident edge.
496
497        /// Sets the iterator to the first incident edge of the given node.
498        ///
499        IncEdgeIt(const BpGraph&, const Node&) { }
500        /// Sets the iterator to the given edge.
501
502        /// Sets the iterator to the given edge of the given graph.
503        ///
504        IncEdgeIt(const BpGraph&, const Edge&) { }
505        /// Next incident edge
506
507        /// Assign the iterator to the next incident edge
508        /// of the corresponding node.
509        IncEdgeIt& operator++() { return *this; }
510      };
511
512      /// \brief Gets the collection of the incident edges
513      ///  of a certain node of the graph.
514      ///
515      /// This function can be used for iterating on the
516      /// incident undirected edges of a certain node of the graph.
517      /// It returns a wrapped
518      /// IncEdgeIt, which looks like an STL container
519      /// (by having begin() and end()) which you can use in range-based
520      /// for loops, stl algorithms, etc.
521      /// For example if g is a BpGraph and u is a Node, you can write:
522      ///\code
523      /// for(auto e: g.incEdges(u))
524      ///   doSomething(e);
525      ///\endcode
526      LemonRangeWrapper2<IncEdgeIt, BpGraph, Node> incEdges(const Node& u) const {
527        return LemonRangeWrapper2<IncEdgeIt, BpGraph, Node>(*this, u);
528      }
529
530
531      /// The arc type of the graph
532
533      /// This class identifies a directed arc of the graph. It also serves
534      /// as a base class of the arc iterators,
535      /// thus they will convert to this type.
536      class Arc {
537      public:
538        /// Default constructor
539
540        /// Default constructor.
541        /// \warning It sets the object to an undefined value.
542        Arc() { }
543        /// Copy constructor.
544
545        /// Copy constructor.
546        ///
547        Arc(const Arc&) { }
548        /// %Invalid constructor \& conversion.
549
550        /// Initializes the object to be invalid.
551        /// \sa Invalid for more details.
552        Arc(Invalid) { }
553        /// Equality operator
554
555        /// Equality operator.
556        ///
557        /// Two iterators are equal if and only if they point to the
558        /// same object or both are \c INVALID.
559        bool operator==(Arc) const { return true; }
560        /// Inequality operator
561
562        /// Inequality operator.
563        bool operator!=(Arc) const { return true; }
564
565        /// Artificial ordering operator.
566
567        /// Artificial ordering operator.
568        ///
569        /// \note This operator only has to define some strict ordering of
570        /// the arcs; this order has nothing to do with the iteration
571        /// ordering of the arcs.
572        bool operator<(Arc) const { return false; }
573
574        /// Converison to \c Edge
575
576        /// Converison to \c Edge.
577        ///
578        operator Edge() const { return Edge(); }
579      };
580
581      /// Iterator class for the arcs.
582
583      /// This iterator goes through each directed arc of the graph.
584      /// Its usage is quite simple, for example, you can count the number
585      /// of arcs in a graph \c g of type \c %BpGraph as follows:
586      ///\code
587      /// int count=0;
588      /// for(BpGraph::ArcIt a(g); a!=INVALID; ++a) ++count;
589      ///\endcode
590      class ArcIt : public Arc {
591      public:
592        /// Default constructor
593
594        /// Default constructor.
595        /// \warning It sets the iterator to an undefined value.
596        ArcIt() { }
597        /// Copy constructor.
598
599        /// Copy constructor.
600        ///
601        ArcIt(const ArcIt& e) : Arc(e) { }
602        /// %Invalid constructor \& conversion.
603
604        /// Initializes the iterator to be invalid.
605        /// \sa Invalid for more details.
606        ArcIt(Invalid) { }
607        /// Sets the iterator to the first arc.
608
609        /// Sets the iterator to the first arc of the given graph.
610        ///
611        explicit ArcIt(const BpGraph &g)
612        {
613          ::lemon::ignore_unused_variable_warning(g);
614        }
615        /// Sets the iterator to the given arc.
616
617        /// Sets the iterator to the given arc of the given graph.
618        ///
619        ArcIt(const BpGraph&, const Arc&) { }
620        /// Next arc
621
622        /// Assign the iterator to the next arc.
623        ///
624        ArcIt& operator++() { return *this; }
625      };
626
627      /// \brief Gets the collection of the directed arcs of the graph.
628      ///
629      /// This function can be used for iterating on the
630      /// arcs of the graph. It returns a wrapped
631      /// ArcIt, which looks like an STL container
632      /// (by having begin() and end()) which you can use in range-based
633      /// for loops, stl algorithms, etc.
634      /// For example if g is a BpGraph you can write:
635      ///\code
636      /// for(auto a: g.arcs())
637      ///   doSomething(a);
638      ///\endcode
639      LemonRangeWrapper1<ArcIt, BpGraph> arcs() const {
640        return LemonRangeWrapper1<ArcIt, BpGraph>(*this);
641      }
642
643
644      /// Iterator class for the outgoing arcs of a node.
645
646      /// This iterator goes trough the \e outgoing directed arcs of a
647      /// certain node of a graph.
648      /// Its usage is quite simple, for example, you can count the number
649      /// of outgoing arcs of a node \c n
650      /// in a graph \c g of type \c %BpGraph as follows.
651      ///\code
652      /// int count=0;
653      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
654      ///\endcode
655      class OutArcIt : public Arc {
656      public:
657        /// Default constructor
658
659        /// Default constructor.
660        /// \warning It sets the iterator to an undefined value.
661        OutArcIt() { }
662        /// Copy constructor.
663
664        /// Copy constructor.
665        ///
666        OutArcIt(const OutArcIt& e) : Arc(e) { }
667        /// %Invalid constructor \& conversion.
668
669        /// Initializes the iterator to be invalid.
670        /// \sa Invalid for more details.
671        OutArcIt(Invalid) { }
672        /// Sets the iterator to the first outgoing arc.
673
674        /// Sets the iterator to the first outgoing arc of the given node.
675        ///
676        OutArcIt(const BpGraph& n, const Node& g) {
677          ::lemon::ignore_unused_variable_warning(n);
678          ::lemon::ignore_unused_variable_warning(g);
679        }
680        /// Sets the iterator to the given arc.
681
682        /// Sets the iterator to the given arc of the given graph.
683        ///
684        OutArcIt(const BpGraph&, const Arc&) { }
685        /// Next outgoing arc
686
687        /// Assign the iterator to the next
688        /// outgoing arc of the corresponding node.
689        OutArcIt& operator++() { return *this; }
690      };
691
692      /// \brief Gets the collection of the outgoing directed arcs of a
693      /// certain node of the graph.
694      ///
695      /// This function can be used for iterating on the
696      /// outgoing arcs of a certain node of the graph. It returns a wrapped
697      /// OutArcIt, which looks like an STL container
698      /// (by having begin() and end()) which you can use in range-based
699      /// for loops, stl algorithms, etc.
700      /// For example if g is a BpGraph and u is a Node, you can write:
701      ///\code
702      /// for(auto a: g.outArcs(u))
703      ///   doSomething(a);
704      ///\endcode
705      LemonRangeWrapper2<OutArcIt, BpGraph, Node> outArcs(const Node& u) const {
706        return LemonRangeWrapper2<OutArcIt, BpGraph, Node>(*this, u);
707      }
708
709
710      /// Iterator class for the incoming arcs of a node.
711
712      /// This iterator goes trough the \e incoming directed arcs of a
713      /// certain node of a graph.
714      /// Its usage is quite simple, for example, you can count the number
715      /// of incoming arcs of a node \c n
716      /// in a graph \c g of type \c %BpGraph as follows.
717      ///\code
718      /// int count=0;
719      /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
720      ///\endcode
721      class InArcIt : public Arc {
722      public:
723        /// Default constructor
724
725        /// Default constructor.
726        /// \warning It sets the iterator to an undefined value.
727        InArcIt() { }
728        /// Copy constructor.
729
730        /// Copy constructor.
731        ///
732        InArcIt(const InArcIt& e) : Arc(e) { }
733        /// %Invalid constructor \& conversion.
734
735        /// Initializes the iterator to be invalid.
736        /// \sa Invalid for more details.
737        InArcIt(Invalid) { }
738        /// Sets the iterator to the first incoming arc.
739
740        /// Sets the iterator to the first incoming arc of the given node.
741        ///
742        InArcIt(const BpGraph& g, const Node& n) {
743          ::lemon::ignore_unused_variable_warning(n);
744          ::lemon::ignore_unused_variable_warning(g);
745        }
746        /// Sets the iterator to the given arc.
747
748        /// Sets the iterator to the given arc of the given graph.
749        ///
750        InArcIt(const BpGraph&, const Arc&) { }
751        /// Next incoming arc
752
753        /// Assign the iterator to the next
754        /// incoming arc of the corresponding node.
755        InArcIt& operator++() { return *this; }
756      };
757
758      /// \brief Gets the collection of the incoming directed arcs of a
759      /// certain node of the graph.
760      ///
761      /// This function can be used for iterating on the
762      /// incoming arcs of a certain node of the graph. It returns a wrapped
763      /// InArcIt, which looks like an STL container
764      /// (by having begin() and end()) which you can use in range-based
765      /// for loops, stl algorithms, etc.
766      /// For example if g is a BpGraph and u is a Node, you can write:
767      ///\code
768      /// for(auto a: g.inArcs(u))
769      ///   doSomething(a);
770      ///\endcode
771      LemonRangeWrapper2<InArcIt, BpGraph, Node> inArcs(const Node& u) const {
772        return LemonRangeWrapper2<InArcIt, BpGraph, Node>(*this, u);
773      }
774
775
776      /// \brief Standard graph map type for the nodes.
777      ///
778      /// Standard graph map type for the nodes.
779      /// It conforms to the ReferenceMap concept.
780      template<class T>
781      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
782      {
783      public:
784
785        /// Constructor
786        explicit NodeMap(const BpGraph&) { }
787        /// Constructor with given initial value
788        NodeMap(const BpGraph&, T) { }
789
790      private:
791        ///Copy constructor
792        NodeMap(const NodeMap& nm) :
793          ReferenceMap<Node, T, T&, const T&>(nm) { }
794        ///Assignment operator
795        template <typename CMap>
796        NodeMap& operator=(const CMap&) {
797          checkConcept<ReadMap<Node, T>, CMap>();
798          return *this;
799        }
800      };
801
802      /// \brief Standard graph map type for the red nodes.
803      ///
804      /// Standard graph map type for the red nodes.
805      /// It conforms to the ReferenceMap concept.
806      template<class T>
807      class RedNodeMap : public ReferenceMap<Node, T, T&, const T&>
808      {
809      public:
810
811        /// Constructor
812        explicit RedNodeMap(const BpGraph&) { }
813        /// Constructor with given initial value
814        RedNodeMap(const BpGraph&, T) { }
815
816      private:
817        ///Copy constructor
818        RedNodeMap(const RedNodeMap& nm) :
819          ReferenceMap<Node, T, T&, const T&>(nm) { }
820        ///Assignment operator
821        template <typename CMap>
822        RedNodeMap& operator=(const CMap&) {
823          checkConcept<ReadMap<Node, T>, CMap>();
824          return *this;
825        }
826      };
827
828      /// \brief Standard graph map type for the blue nodes.
829      ///
830      /// Standard graph map type for the blue nodes.
831      /// It conforms to the ReferenceMap concept.
832      template<class T>
833      class BlueNodeMap : public ReferenceMap<Node, T, T&, const T&>
834      {
835      public:
836
837        /// Constructor
838        explicit BlueNodeMap(const BpGraph&) { }
839        /// Constructor with given initial value
840        BlueNodeMap(const BpGraph&, T) { }
841
842      private:
843        ///Copy constructor
844        BlueNodeMap(const BlueNodeMap& nm) :
845          ReferenceMap<Node, T, T&, const T&>(nm) { }
846        ///Assignment operator
847        template <typename CMap>
848        BlueNodeMap& operator=(const CMap&) {
849          checkConcept<ReadMap<Node, T>, CMap>();
850          return *this;
851        }
852      };
853
854      /// \brief Standard graph map type for the arcs.
855      ///
856      /// Standard graph map type for the arcs.
857      /// It conforms to the ReferenceMap concept.
858      template<class T>
859      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
860      {
861      public:
862
863        /// Constructor
864        explicit ArcMap(const BpGraph&) { }
865        /// Constructor with given initial value
866        ArcMap(const BpGraph&, T) { }
867
868      private:
869        ///Copy constructor
870        ArcMap(const ArcMap& em) :
871          ReferenceMap<Arc, T, T&, const T&>(em) { }
872        ///Assignment operator
873        template <typename CMap>
874        ArcMap& operator=(const CMap&) {
875          checkConcept<ReadMap<Arc, T>, CMap>();
876          return *this;
877        }
878      };
879
880      /// \brief Standard graph map type for the edges.
881      ///
882      /// Standard graph map type for the edges.
883      /// It conforms to the ReferenceMap concept.
884      template<class T>
885      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
886      {
887      public:
888
889        /// Constructor
890        explicit EdgeMap(const BpGraph&) { }
891        /// Constructor with given initial value
892        EdgeMap(const BpGraph&, T) { }
893
894      private:
895        ///Copy constructor
896        EdgeMap(const EdgeMap& em) :
897          ReferenceMap<Edge, T, T&, const T&>(em) {}
898        ///Assignment operator
899        template <typename CMap>
900        EdgeMap& operator=(const CMap&) {
901          checkConcept<ReadMap<Edge, T>, CMap>();
902          return *this;
903        }
904      };
905
906      /// \brief Gives back %true for red nodes.
907      ///
908      /// Gives back %true for red nodes.
909      bool red(const Node&) const { return true; }
910
911      /// \brief Gives back %true for blue nodes.
912      ///
913      /// Gives back %true for blue nodes.
914      bool blue(const Node&) const { return true; }
915
916      /// \brief Converts the node to red node object.
917      ///
918      /// This function converts unsafely the node to red node
919      /// object. It should be called only if the node is from the red
920      /// partition or INVALID.
921      RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
922
923      /// \brief Converts the node to blue node object.
924      ///
925      /// This function converts unsafely the node to blue node
926      /// object. It should be called only if the node is from the red
927      /// partition or INVALID.
928      BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
929
930      /// \brief Converts the node to red node object.
931      ///
932      /// This function converts safely the node to red node
933      /// object. If the node is not from the red partition, then it
934      /// returns INVALID.
935      RedNode asRedNode(const Node&) const { return RedNode(); }
936
937      /// \brief Converts the node to blue node object.
938      ///
939      /// This function converts unsafely the node to blue node
940      /// object. If the node is not from the blue partition, then it
941      /// returns INVALID.
942      BlueNode asBlueNode(const Node&) const { return BlueNode(); }
943
944      /// \brief Gives back the red end node of the edge.
945      ///
946      /// Gives back the red end node of the edge.
947      RedNode redNode(const Edge&) const { return RedNode(); }
948
949      /// \brief Gives back the blue end node of the edge.
950      ///
951      /// Gives back the blue end node of the edge.
952      BlueNode blueNode(const Edge&) const { return BlueNode(); }
953
954      /// \brief The first node of the edge.
955      ///
956      /// It is a synonim for the \c redNode().
957      Node u(Edge) const { return INVALID; }
958
959      /// \brief The second node of the edge.
960      ///
961      /// It is a synonim for the \c blueNode().
962      Node v(Edge) const { return INVALID; }
963
964      /// \brief The source node of the arc.
965      ///
966      /// Returns the source node of the given arc.
967      Node source(Arc) const { return INVALID; }
968
969      /// \brief The target node of the arc.
970      ///
971      /// Returns the target node of the given arc.
972      Node target(Arc) const { return INVALID; }
973
974      /// \brief The ID of the node.
975      ///
976      /// Returns the ID of the given node.
977      int id(Node) const { return -1; }
978
979      /// \brief The red ID of the node.
980      ///
981      /// Returns the red ID of the given node.
982      int id(RedNode) const { return -1; }
983
984      /// \brief The blue ID of the node.
985      ///
986      /// Returns the blue ID of the given node.
987      int id(BlueNode) const { return -1; }
988
989      /// \brief The ID of the edge.
990      ///
991      /// Returns the ID of the given edge.
992      int id(Edge) const { return -1; }
993
994      /// \brief The ID of the arc.
995      ///
996      /// Returns the ID of the given arc.
997      int id(Arc) const { return -1; }
998
999      /// \brief The node with the given ID.
1000      ///
1001      /// Returns the node with the given ID.
1002      /// \pre The argument should be a valid node ID in the graph.
1003      Node nodeFromId(int) const { return INVALID; }
1004
1005      /// \brief The edge with the given ID.
1006      ///
1007      /// Returns the edge with the given ID.
1008      /// \pre The argument should be a valid edge ID in the graph.
1009      Edge edgeFromId(int) const { return INVALID; }
1010
1011      /// \brief The arc with the given ID.
1012      ///
1013      /// Returns the arc with the given ID.
1014      /// \pre The argument should be a valid arc ID in the graph.
1015      Arc arcFromId(int) const { return INVALID; }
1016
1017      /// \brief An upper bound on the node IDs.
1018      ///
1019      /// Returns an upper bound on the node IDs.
1020      int maxNodeId() const { return -1; }
1021
1022      /// \brief An upper bound on the red IDs.
1023      ///
1024      /// Returns an upper bound on the red IDs.
1025      int maxRedId() const { return -1; }
1026
1027      /// \brief An upper bound on the blue IDs.
1028      ///
1029      /// Returns an upper bound on the blue IDs.
1030      int maxBlueId() const { return -1; }
1031
1032      /// \brief An upper bound on the edge IDs.
1033      ///
1034      /// Returns an upper bound on the edge IDs.
1035      int maxEdgeId() const { return -1; }
1036
1037      /// \brief An upper bound on the arc IDs.
1038      ///
1039      /// Returns an upper bound on the arc IDs.
1040      int maxArcId() const { return -1; }
1041
1042      /// \brief The direction of the arc.
1043      ///
1044      /// Returns \c true if the given arc goes from a red node to a blue node.
1045      bool direction(Arc) const { return true; }
1046
1047      /// \brief Direct the edge.
1048      ///
1049      /// Direct the given edge. The returned arc
1050      /// represents the given edge and its direction comes
1051      /// from the bool parameter. If it is \c true, then the source of the node
1052      /// will be a red node.
1053      Arc direct(Edge, bool) const {
1054        return INVALID;
1055      }
1056
1057      /// \brief Direct the edge.
1058      ///
1059      /// Direct the given edge. The returned arc represents the given
1060      /// edge and its source node is the given node.
1061      Arc direct(Edge, Node) const {
1062        return INVALID;
1063      }
1064
1065      /// \brief The oppositely directed arc.
1066      ///
1067      /// Returns the oppositely directed arc representing the same edge.
1068      Arc oppositeArc(Arc) const { return INVALID; }
1069
1070      /// \brief The opposite node on the edge.
1071      ///
1072      /// Returns the opposite node on the given edge.
1073      Node oppositeNode(Node, Edge) const { return INVALID; }
1074
1075      void first(Node&) const {}
1076      void next(Node&) const {}
1077
1078      void firstRed(RedNode&) const {}
1079      void nextRed(RedNode&) const {}
1080
1081      void firstBlue(BlueNode&) const {}
1082      void nextBlue(BlueNode&) const {}
1083
1084      void first(Edge&) const {}
1085      void next(Edge&) const {}
1086
1087      void first(Arc&) const {}
1088      void next(Arc&) const {}
1089
1090      void firstOut(Arc&, Node) const {}
1091      void nextOut(Arc&) const {}
1092
1093      void firstIn(Arc&, Node) const {}
1094      void nextIn(Arc&) const {}
1095
1096      void firstInc(Edge &, bool &, const Node &) const {}
1097      void nextInc(Edge &, bool &) const {}
1098
1099      // The second parameter is dummy.
1100      Node fromId(int, Node) const { return INVALID; }
1101      // The second parameter is dummy.
1102      Edge fromId(int, Edge) const { return INVALID; }
1103      // The second parameter is dummy.
1104      Arc fromId(int, Arc) const { return INVALID; }
1105
1106      // Dummy parameter.
1107      int maxId(Node) const { return -1; }
1108      // Dummy parameter.
1109      int maxId(RedNode) const { return -1; }
1110      // Dummy parameter.
1111      int maxId(BlueNode) const { return -1; }
1112      // Dummy parameter.
1113      int maxId(Edge) const { return -1; }
1114      // Dummy parameter.
1115      int maxId(Arc) const { return -1; }
1116
1117      /// \brief The base node of the iterator.
1118      ///
1119      /// Returns the base node of the given incident edge iterator.
1120      Node baseNode(IncEdgeIt) const { return INVALID; }
1121
1122      /// \brief The running node of the iterator.
1123      ///
1124      /// Returns the running node of the given incident edge iterator.
1125      Node runningNode(IncEdgeIt) const { return INVALID; }
1126
1127      /// \brief The base node of the iterator.
1128      ///
1129      /// Returns the base node of the given outgoing arc iterator
1130      /// (i.e. the source node of the corresponding arc).
1131      Node baseNode(OutArcIt) const { return INVALID; }
1132
1133      /// \brief The running node of the iterator.
1134      ///
1135      /// Returns the running node of the given outgoing arc iterator
1136      /// (i.e. the target node of the corresponding arc).
1137      Node runningNode(OutArcIt) const { return INVALID; }
1138
1139      /// \brief The base node of the iterator.
1140      ///
1141      /// Returns the base node of the given incoming arc iterator
1142      /// (i.e. the target node of the corresponding arc).
1143      Node baseNode(InArcIt) const { return INVALID; }
1144
1145      /// \brief The running node of the iterator.
1146      ///
1147      /// Returns the running node of the given incoming arc iterator
1148      /// (i.e. the source node of the corresponding arc).
1149      Node runningNode(InArcIt) const { return INVALID; }
1150
1151      template <typename _BpGraph>
1152      struct Constraints {
1153        void constraints() {
1154          checkConcept<BaseBpGraphComponent, _BpGraph>();
1155          checkConcept<IterableBpGraphComponent<>, _BpGraph>();
1156          checkConcept<IDableBpGraphComponent<>, _BpGraph>();
1157          checkConcept<MappableBpGraphComponent<>, _BpGraph>();
1158        }
1159      };
1160
1161    };
1162
1163  }
1164
1165}
1166
1167#endif
Note: See TracBrowser for help on using the repository browser.