COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
07/13/08 20:51:02 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Apply unify-sources.sh to the source tree

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/concepts/graph_components.h

    r169 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
     
    5050    public:
    5151      /// \brief Default constructor.
    52       ///     
     52      ///
    5353      /// \warning The default constructor is not required to set
    5454      /// the item to some well-defined value. So you should consider it
     
    6767      /// \brief Assign operator for nodes.
    6868      ///
    69       /// The nodes are assignable. 
     69      /// The nodes are assignable.
    7070      ///
    7171      GraphItem& operator=(GraphItem const&) { return *this; }
     
    9393      template<typename _GraphItem>
    9494      struct Constraints {
    95         void constraints() {
    96           _GraphItem i1;
    97           _GraphItem i2 = i1;
    98           _GraphItem i3 = INVALID;
    99          
    100           i1 = i2 = i3;
    101 
    102           bool b;
    103           //      b = (ia == ib) && (ia != ib) && (ia < ib);
    104           b = (ia == ib) && (ia != ib);
    105           b = (ia == INVALID) && (ib != INVALID);
     95        void constraints() {
     96          _GraphItem i1;
     97          _GraphItem i2 = i1;
     98          _GraphItem i3 = INVALID;
     99
     100          i1 = i2 = i3;
     101
     102          bool b;
     103          //          b = (ia == ib) && (ia != ib) && (ia < ib);
     104          b = (ia == ib) && (ia != ib);
     105          b = (ia == INVALID) && (ib != INVALID);
    106106          b = (ia < ib);
    107         }
    108 
    109         const _GraphItem &ia;
    110         const _GraphItem &ib;
     107        }
     108
     109        const _GraphItem &ia;
     110        const _GraphItem &ib;
    111111      };
    112112    };
    113113
    114114    /// \brief An empty base directed graph class.
    115     /// 
     115    ///
    116116    /// This class provides the minimal set of features needed for a
    117117    /// directed graph structure. All digraph concepts have to be
     
    123123
    124124      typedef BaseDigraphComponent Digraph;
    125      
     125
    126126      /// \brief Node class of the digraph.
    127127      ///
    128       /// This class represents the Nodes of the digraph. 
     128      /// This class represents the Nodes of the digraph.
    129129      ///
    130130      typedef GraphItem<'n'> Node;
     
    132132      /// \brief Arc class of the digraph.
    133133      ///
    134       /// This class represents the Arcs of the digraph. 
     134      /// This class represents the Arcs of the digraph.
    135135      ///
    136136      typedef GraphItem<'e'> Arc;
     
    157157      template <typename _Digraph>
    158158      struct Constraints {
    159         typedef typename _Digraph::Node Node;
    160         typedef typename _Digraph::Arc Arc;
    161      
    162         void constraints() {
    163           checkConcept<GraphItem<'n'>, Node>();
    164           checkConcept<GraphItem<'a'>, Arc>();
    165           {
    166             Node n;
    167             Arc e(INVALID);
    168             n = digraph.source(e);
    169             n = digraph.target(e);
     159        typedef typename _Digraph::Node Node;
     160        typedef typename _Digraph::Arc Arc;
     161
     162        void constraints() {
     163          checkConcept<GraphItem<'n'>, Node>();
     164          checkConcept<GraphItem<'a'>, Arc>();
     165          {
     166            Node n;
     167            Arc e(INVALID);
     168            n = digraph.source(e);
     169            n = digraph.target(e);
    170170            n = digraph.oppositeNode(n, e);
    171           }     
    172         }
    173      
    174         const _Digraph& digraph;
     171          }
     172        }
     173
     174        const _Digraph& digraph;
    175175      };
    176176    };
    177177
    178178    /// \brief An empty base undirected graph class.
    179     /// 
     179    ///
    180180    /// This class provides the minimal set of features needed for an
    181181    /// undirected graph structure. All undirected graph concepts have
     
    200200        typedef GraphItem<'u'> Parent;
    201201        /// \brief Default constructor.
    202         ///     
     202        ///
    203203        /// \warning The default constructor is not required to set
    204204        /// the item to some well-defined value. So you should consider it
     
    218218        ///
    219219        /// Besides the core graph item functionality each arc should
    220         /// be convertible to the represented edge. 
     220        /// be convertible to the represented edge.
    221221        Edge(const Arc&) {}
    222222        /// \brief Assign arc to edge.
    223223        ///
    224224        /// Besides the core graph item functionality each arc should
    225         /// be convertible to the represented edge. 
     225        /// be convertible to the represented edge.
    226226        Edge& operator=(const Arc&) { return *this; }
    227227      };
     
    238238      /// Returns the directed arc from its direction and the
    239239      /// represented edge.
    240       Arc direct(const Edge&, bool) const { return INVALID;} 
     240      Arc direct(const Edge&, bool) const { return INVALID;}
    241241
    242242      /// \brief Returns the directed arc.
     
    244244      /// Returns the directed arc from its source and the
    245245      /// represented edge.
    246       Arc direct(const Edge&, const Node&) const { return INVALID;} 
     246      Arc direct(const Edge&, const Node&) const { return INVALID;}
    247247
    248248      /// \brief Returns the opposite arc.
     
    261261      /// Gives back the other ending of an edge.
    262262      Node v(const Edge&) const { return INVALID;}
    263      
     263
    264264      template <typename _Graph>
    265265      struct Constraints {
    266         typedef typename _Graph::Node Node;
    267         typedef typename _Graph::Arc Arc;
    268         typedef typename _Graph::Edge Edge;
    269      
    270         void constraints() {
     266        typedef typename _Graph::Node Node;
     267        typedef typename _Graph::Arc Arc;
     268        typedef typename _Graph::Edge Edge;
     269
     270        void constraints() {
    271271          checkConcept<BaseDigraphComponent, _Graph>();
    272           checkConcept<GraphItem<'u'>, Edge>();
    273           {
    274             Node n;
    275             Edge ue(INVALID);
     272          checkConcept<GraphItem<'u'>, Edge>();
     273          {
     274            Node n;
     275            Edge ue(INVALID);
    276276            Arc e;
    277             n = graph.u(ue);
    278             n = graph.v(ue);
     277            n = graph.u(ue);
     278            n = graph.v(ue);
    279279            e = graph.direct(ue, true);
    280280            e = graph.direct(ue, n);
     
    283283            bool d = graph.direction(e);
    284284            ignore_unused_variable_warning(d);
    285           }     
    286         }
    287      
    288         const _Graph& graph;
     285          }
     286        }
     287
     288        const _Graph& graph;
    289289      };
    290290
     
    292292
    293293    /// \brief An empty idable base digraph class.
    294     /// 
     294    ///
    295295    /// This class provides beside the core digraph features
    296296    /// core id functions for the digraph structure.
     
    305305      typedef typename Base::Arc Arc;
    306306
    307       /// \brief Gives back an unique integer id for the Node. 
    308       ///
    309       /// Gives back an unique integer id for the Node. 
     307      /// \brief Gives back an unique integer id for the Node.
     308      ///
     309      /// Gives back an unique integer id for the Node.
    310310      ///
    311311      int id(const Node&) const { return -1;}
     
    315315      /// Gives back the node by the unique id.
    316316      /// If the digraph does not contain node with the given id
    317       /// then the result of the function is undetermined. 
     317      /// then the result of the function is undetermined.
    318318      Node nodeFromId(int) const { return INVALID;}
    319319
    320       /// \brief Gives back an unique integer id for the Arc. 
    321       ///
    322       /// Gives back an unique integer id for the Arc. 
     320      /// \brief Gives back an unique integer id for the Arc.
     321      ///
     322      /// Gives back an unique integer id for the Arc.
    323323      ///
    324324      int id(const Arc&) const { return -1;}
     
    328328      /// Gives back the arc by the unique id.
    329329      /// If the digraph does not contain arc with the given id
    330       /// then the result of the function is undetermined. 
     330      /// then the result of the function is undetermined.
    331331      Arc arcFromId(int) const { return INVALID;}
    332332
     
    348348      struct Constraints {
    349349
    350         void constraints() {
    351           checkConcept<Base, _Digraph >();
    352           typename _Digraph::Node node;
    353           int nid = digraph.id(node);
    354           nid = digraph.id(node);
    355           node = digraph.nodeFromId(nid);
    356           typename _Digraph::Arc arc;
    357           int eid = digraph.id(arc);
    358           eid = digraph.id(arc);
    359           arc = digraph.arcFromId(eid);
    360 
    361           nid = digraph.maxNodeId();
    362           ignore_unused_variable_warning(nid);
    363           eid = digraph.maxArcId();
    364           ignore_unused_variable_warning(eid);
    365         }
    366 
    367         const _Digraph& digraph;
     350        void constraints() {
     351          checkConcept<Base, _Digraph >();
     352          typename _Digraph::Node node;
     353          int nid = digraph.id(node);
     354          nid = digraph.id(node);
     355          node = digraph.nodeFromId(nid);
     356          typename _Digraph::Arc arc;
     357          int eid = digraph.id(arc);
     358          eid = digraph.id(arc);
     359          arc = digraph.arcFromId(eid);
     360
     361          nid = digraph.maxNodeId();
     362          ignore_unused_variable_warning(nid);
     363          eid = digraph.maxArcId();
     364          ignore_unused_variable_warning(eid);
     365        }
     366
     367        const _Digraph& digraph;
    368368      };
    369369    };
    370370
    371371    /// \brief An empty idable base undirected graph class.
    372     /// 
     372    ///
    373373    /// This class provides beside the core undirected graph features
    374374    /// core id functions for the undirected graph structure.  The
     
    384384      using IDableDigraphComponent<_Base>::id;
    385385
    386       /// \brief Gives back an unique integer id for the Edge. 
    387       ///
    388       /// Gives back an unique integer id for the Edge. 
     386      /// \brief Gives back an unique integer id for the Edge.
     387      ///
     388      /// Gives back an unique integer id for the Edge.
    389389      ///
    390390      int id(const Edge&) const { return -1;}
     
    407407      struct Constraints {
    408408
    409         void constraints() {
    410           checkConcept<Base, _Graph >();
    411           checkConcept<IDableDigraphComponent<Base>, _Graph >();
    412           typename _Graph::Edge edge;
    413           int ueid = graph.id(edge);
    414           ueid = graph.id(edge);
    415           edge = graph.edgeFromId(ueid);
    416           ueid = graph.maxEdgeId();
    417           ignore_unused_variable_warning(ueid);
    418         }
    419 
    420         const _Graph& graph;
     409        void constraints() {
     410          checkConcept<Base, _Graph >();
     411          checkConcept<IDableDigraphComponent<Base>, _Graph >();
     412          typename _Graph::Edge edge;
     413          int ueid = graph.id(edge);
     414          ueid = graph.id(edge);
     415          edge = graph.edgeFromId(ueid);
     416          ueid = graph.maxEdgeId();
     417          ignore_unused_variable_warning(ueid);
     418        }
     419
     420        const _Graph& graph;
    421421      };
    422422    };
     
    451451      /// \brief Assign operator for items.
    452452      ///
    453       /// The items are assignable. 
    454       ///
    455       GraphItemIt& operator=(const GraphItemIt&) { return *this; }     
     453      /// The items are assignable.
     454      ///
     455      GraphItemIt& operator=(const GraphItemIt&) { return *this; }
    456456      /// \brief Next item.
    457       /// 
     457      ///
    458458      /// Assign the iterator to the next item.
    459459      ///
    460460      GraphItemIt& operator++() { return *this; }
    461461      /// \brief Equality operator
    462       /// 
     462      ///
    463463      /// Two iterators are equal if and only if they point to the
    464464      /// same object or both are invalid.
    465465      bool operator==(const GraphItemIt&) const { return true;}
    466466      /// \brief Inequality operator
    467       ///       
     467      ///
    468468      /// \sa operator==(Node n)
    469469      ///
    470470      bool operator!=(const GraphItemIt&) const { return true;}
    471      
     471
    472472      template<typename _GraphItemIt>
    473473      struct Constraints {
    474         void constraints() {
    475           _GraphItemIt it1(g); 
    476           _GraphItemIt it2;
    477 
    478           it2 = ++it1;
    479           ++it2 = it1;
    480           ++(++it1);
    481 
    482           _Item bi = it1;
    483           bi = it2;
    484         }
    485         _Graph& g;
     474        void constraints() {
     475          _GraphItemIt it1(g);
     476          _GraphItemIt it2;
     477
     478          it2 = ++it1;
     479          ++it2 = it1;
     480          ++(++it1);
     481
     482          _Item bi = it1;
     483          bi = it2;
     484        }
     485        _Graph& g;
    486486      };
    487487    };
     
    490490    ///
    491491    /// \note Because InArcIt and OutArcIt may not inherit from the same
    492     /// base class, the _selector is a additional template parameter. For 
    493     /// InArcIt you should instantiate it with character 'i' and for 
     492    /// base class, the _selector is a additional template parameter. For
     493    /// InArcIt you should instantiate it with character 'i' and for
    494494    /// OutArcIt with 'o'.
    495495    template <typename _Graph,
    496               typename _Item = typename _Graph::Arc,
    497               typename _Base = typename _Graph::Node, 
    498               char _selector = '0'>
     496              typename _Item = typename _Graph::Arc,
     497              typename _Base = typename _Graph::Node,
     498              char _selector = '0'>
    499499    class GraphIncIt : public _Item {
    500500    public:
     
    509509      ///
    510510      GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
    511       /// \brief Sets the iterator to the first arc incoming into or outgoing 
     511      /// \brief Sets the iterator to the first arc incoming into or outgoing
    512512      /// from the node.
    513513      ///
    514       /// Sets the iterator to the first arc incoming into or outgoing 
     514      /// Sets the iterator to the first arc incoming into or outgoing
    515515      /// from the node.
    516516      ///
     
    523523      /// \brief Assign operator for iterators.
    524524      ///
    525       /// The iterators are assignable. 
    526       ///
    527       GraphIncIt& operator=(GraphIncIt const&) { return *this; }     
     525      /// The iterators are assignable.
     526      ///
     527      GraphIncIt& operator=(GraphIncIt const&) { return *this; }
    528528      /// \brief Next item.
    529529      ///
     
    546546      template <typename _GraphIncIt>
    547547      struct Constraints {
    548         void constraints() {
    549           checkConcept<GraphItem<_selector>, _GraphIncIt>();
    550           _GraphIncIt it1(graph, node);
    551           _GraphIncIt it2;
    552 
    553           it2 = ++it1;
    554           ++it2 = it1;
    555           ++(++it1);
    556           _Item e = it1;
    557           e = it2;
    558 
    559         }
    560 
    561         _Item arc;
    562         _Base node;
    563         _Graph graph;
    564         _GraphIncIt it;
     548        void constraints() {
     549          checkConcept<GraphItem<_selector>, _GraphIncIt>();
     550          _GraphIncIt it1(graph, node);
     551          _GraphIncIt it2;
     552
     553          it2 = ++it1;
     554          ++it2 = it1;
     555          ++(++it1);
     556          _Item e = it1;
     557          e = it2;
     558
     559        }
     560
     561        _Item arc;
     562        _Base node;
     563        _Graph graph;
     564        _GraphIncIt it;
    565565      };
    566566    };
     
    576576
    577577    public:
    578    
     578
    579579      typedef _Base Base;
    580580      typedef typename Base::Node Node;
     
    584584
    585585      /// \name Base iteration
    586       /// 
     586      ///
    587587      /// This interface provides functions for iteration on digraph items
    588588      ///
    589       /// @{ 
     589      /// @{
    590590
    591591      /// \brief Gives back the first node in the iterating order.
    592       ///     
     592      ///
    593593      /// Gives back the first node in the iterating order.
    594       ///     
     594      ///
    595595      void first(Node&) const {}
    596596
     
    598598      ///
    599599      /// Gives back the next node in the iterating order.
    600       ///     
     600      ///
    601601      void next(Node&) const {}
    602602
     
    604604      ///
    605605      /// Gives back the first arc in the iterating order.
    606       ///     
     606      ///
    607607      void first(Arc&) const {}
    608608
     
    610610      ///
    611611      /// Gives back the next arc in the iterating order.
    612       ///     
     612      ///
    613613      void next(Arc&) const {}
    614614
     
    618618      ///
    619619      /// Gives back the first of the arcs point to the given node.
    620       ///     
     620      ///
    621621      void firstIn(Arc&, const Node&) const {}
    622622
     
    630630      /// \brief Gives back the first of the arcs start from the
    631631      /// given node.
    632       ///     
     632      ///
    633633      /// Gives back the first of the arcs start from the given node.
    634       ///     
     634      ///
    635635      void firstOut(Arc&, const Node&) const {}
    636636
     
    639639      ///
    640640      /// Gives back the next of the arcs start from the given node.
    641       ///     
     641      ///
    642642      void nextOut(Arc&) const {}
    643643
     
    645645
    646646      /// \name Class based iteration
    647       /// 
     647      ///
    648648      /// This interface provides functions for iteration on digraph items
    649649      ///
     
    700700      /// @}
    701701
    702       template <typename _Digraph> 
    703       struct Constraints {
    704         void constraints() {
    705           checkConcept<Base, _Digraph>();
     702      template <typename _Digraph>
     703      struct Constraints {
     704        void constraints() {
     705          checkConcept<Base, _Digraph>();
    706706
    707707          {
    708             typename _Digraph::Node node(INVALID);     
     708            typename _Digraph::Node node(INVALID);
    709709            typename _Digraph::Arc arc(INVALID);
    710710            {
     
    724724              digraph.nextOut(arc);
    725725            }
    726           }           
     726          }
    727727
    728728          {
     
    731731            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>,
    732732              typename _Digraph::NodeIt >();
    733             checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc, 
     733            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
    734734              typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>();
    735             checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc, 
     735            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
    736736              typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>();
    737737
     
    746746          }
    747747        }
    748        
    749         const _Digraph& digraph;
    750        
     748
     749        const _Digraph& digraph;
     750
    751751      };
    752752    };
     
    766766      typedef typename Base::Edge Edge;
    767767
    768    
     768
    769769      typedef IterableGraphComponent Graph;
    770770
    771771      /// \name Base iteration
    772       /// 
     772      ///
    773773      /// This interface provides functions for iteration on graph items
    774       /// @{ 
     774      /// @{
    775775
    776776      using IterableDigraphComponent<_Base>::first;
     
    781781      ///
    782782      /// Gives back the first edge in the iterating order.
    783       ///     
     783      ///
    784784      void first(Edge&) const {}
    785785
     
    788788      ///
    789789      /// Gives back the next edge in the iterating order.
    790       ///     
     790      ///
    791791      void next(Edge&) const {}
    792792
     
    815815
    816816      /// \name Class based iteration
    817       /// 
     817      ///
    818818      /// This interface provides functions for iteration on graph items
    819819      ///
     
    842842      /// @}
    843843
    844       template <typename _Graph> 
    845       struct Constraints {
    846         void constraints() {
    847           checkConcept<IterableDigraphComponent<Base>, _Graph>();
     844      template <typename _Graph>
     845      struct Constraints {
     846        void constraints() {
     847          checkConcept<IterableDigraphComponent<Base>, _Graph>();
    848848
    849849          {
     
    859859              graph.nextInc(edge, dir);
    860860            }
    861            
    862           }     
    863  
     861
     862          }
     863
    864864          {
    865865            checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
    866866              typename _Graph::EdgeIt >();
    867             checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 
     867            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
    868868              typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
    869            
     869
    870870            typename _Graph::Node n;
    871871            typename _Graph::IncEdgeIt ueit(INVALID);
     
    874874          }
    875875        }
    876        
    877         const _Graph& graph;
    878        
     876
     877        const _Graph& graph;
     878
    879879      };
    880880    };
    881881
    882882    /// \brief An empty alteration notifier digraph class.
    883     /// 
     883    ///
    884884    /// This class provides beside the core digraph features alteration
    885885    /// notifier interface for the digraph structure.  This implements
     
    898898
    899899      /// The node observer registry.
    900       typedef AlterationNotifier<AlterableDigraphComponent, Node> 
     900      typedef AlterationNotifier<AlterableDigraphComponent, Node>
    901901      NodeNotifier;
    902902      /// The arc observer registry.
    903       typedef AlterationNotifier<AlterableDigraphComponent, Arc> 
     903      typedef AlterationNotifier<AlterableDigraphComponent, Arc>
    904904      ArcNotifier;
    905      
     905
    906906      /// \brief Gives back the node alteration notifier.
    907907      ///
    908908      /// Gives back the node alteration notifier.
    909909      NodeNotifier& notifier(Node) const {
    910         return NodeNotifier();
     910        return NodeNotifier();
    911911      }
    912      
     912
    913913      /// \brief Gives back the arc alteration notifier.
    914914      ///
    915915      /// Gives back the arc alteration notifier.
    916916      ArcNotifier& notifier(Arc) const {
    917         return ArcNotifier();
     917        return ArcNotifier();
    918918      }
    919919
    920       template <typename _Digraph> 
    921       struct Constraints {
    922         void constraints() {
    923           checkConcept<Base, _Digraph>();
    924           typename _Digraph::NodeNotifier& nn 
     920      template <typename _Digraph>
     921      struct Constraints {
     922        void constraints() {
     923          checkConcept<Base, _Digraph>();
     924          typename _Digraph::NodeNotifier& nn
    925925            = digraph.notifier(typename _Digraph::Node());
    926926
    927           typename _Digraph::ArcNotifier& en 
     927          typename _Digraph::ArcNotifier& en
    928928            = digraph.notifier(typename _Digraph::Arc());
    929          
     929
    930930          ignore_unused_variable_warning(nn);
    931931          ignore_unused_variable_warning(en);
    932         }
    933        
    934         const _Digraph& digraph;
    935        
    936       };
    937      
     932        }
     933
     934        const _Digraph& digraph;
     935
     936      };
     937
    938938    };
    939939
    940940    /// \brief An empty alteration notifier undirected graph class.
    941     /// 
     941    ///
    942942    /// This class provides beside the core graph features alteration
    943943    /// notifier interface for the graph structure.  This implements
     
    955955
    956956      /// The arc observer registry.
    957       typedef AlterationNotifier<AlterableGraphComponent, Edge> 
     957      typedef AlterationNotifier<AlterableGraphComponent, Edge>
    958958      EdgeNotifier;
    959      
     959
    960960      /// \brief Gives back the arc alteration notifier.
    961961      ///
    962962      /// Gives back the arc alteration notifier.
    963963      EdgeNotifier& notifier(Edge) const {
    964         return EdgeNotifier();
     964        return EdgeNotifier();
    965965      }
    966966
    967       template <typename _Graph> 
    968       struct Constraints {
    969         void constraints() {
    970           checkConcept<AlterableGraphComponent<Base>, _Graph>();
    971           typename _Graph::EdgeNotifier& uen 
     967      template <typename _Graph>
     968      struct Constraints {
     969        void constraints() {
     970          checkConcept<AlterableGraphComponent<Base>, _Graph>();
     971          typename _Graph::EdgeNotifier& uen
    972972            = graph.notifier(typename _Graph::Edge());
    973973          ignore_unused_variable_warning(uen);
    974         }
    975        
    976         const _Graph& graph;
    977        
    978       };
    979      
     974        }
     975
     976        const _Graph& graph;
     977
     978      };
     979
    980980    };
    981981
    982982    /// \brief Class describing the concept of graph maps
    983     /// 
     983    ///
    984984    /// This class describes the common interface of the graph maps
    985985    /// (NodeMap, ArcMap), that is \ref maps-page "maps" which can be used to
     
    10101010      /// Copy Constructor.
    10111011      GraphMap(const GraphMap&) : Parent() {}
    1012      
     1012
    10131013      /// \brief Assign operator.
    10141014      ///
    10151015      /// Assign operator. It does not mofify the underlying graph,
    10161016      /// it just iterates on the current item set and set the  map
    1017       /// with the value returned by the assigned map. 
     1017      /// with the value returned by the assigned map.
    10181018      template <typename CMap>
    1019       GraphMap& operator=(const CMap&) { 
     1019      GraphMap& operator=(const CMap&) {
    10201020        checkConcept<ReadMap<Key, Value>, CMap>();
    10211021        return *this;
     
    10241024      template<typename _Map>
    10251025      struct Constraints {
    1026         void constraints() {
    1027           checkConcept<ReadWriteMap<Key, Value>, _Map >();
    1028           // Construction with a graph parameter
    1029           _Map a(g);
    1030           // Constructor with a graph and a default value parameter
    1031           _Map a2(g,t);
    1032           // Copy constructor.
    1033           _Map b(c);
    1034          
     1026        void constraints() {
     1027          checkConcept<ReadWriteMap<Key, Value>, _Map >();
     1028          // Construction with a graph parameter
     1029          _Map a(g);
     1030          // Constructor with a graph and a default value parameter
     1031          _Map a2(g,t);
     1032          // Copy constructor.
     1033          _Map b(c);
     1034
    10351035          ReadMap<Key, Value> cmap;
    10361036          b = cmap;
    10371037
    1038           ignore_unused_variable_warning(a2);
    1039           ignore_unused_variable_warning(b);
    1040         }
    1041 
    1042         const _Map &c;
    1043         const Graph &g;
    1044         const typename GraphMap::Value &t;
     1038          ignore_unused_variable_warning(a2);
     1039          ignore_unused_variable_warning(b);
     1040        }
     1041
     1042        const _Map &c;
     1043        const Graph &g;
     1044        const typename GraphMap::Value &t;
    10451045      };
    10461046
     
    10711071        typedef GraphMap<MappableDigraphComponent, Node, _Value> Parent;
    10721072
    1073         /// \brief Construct a new map.
    1074         ///
    1075         /// Construct a new map for the digraph.
    1076         explicit NodeMap(const MappableDigraphComponent& digraph)
     1073        /// \brief Construct a new map.
     1074        ///
     1075        /// Construct a new map for the digraph.
     1076        explicit NodeMap(const MappableDigraphComponent& digraph)
    10771077          : Parent(digraph) {}
    10781078
    1079         /// \brief Construct a new map with default value.
    1080         ///
    1081         /// Construct a new map for the digraph and initalise the values.
    1082         NodeMap(const MappableDigraphComponent& digraph, const _Value& value)
     1079        /// \brief Construct a new map with default value.
     1080        ///
     1081        /// Construct a new map for the digraph and initalise the values.
     1082        NodeMap(const MappableDigraphComponent& digraph, const _Value& value)
    10831083          : Parent(digraph, value) {}
    10841084
    1085         /// \brief Copy constructor.
    1086         ///
    1087         /// Copy Constructor.
    1088         NodeMap(const NodeMap& nm) : Parent(nm) {}
    1089 
    1090         /// \brief Assign operator.
    1091         ///
    1092         /// Assign operator.
     1085        /// \brief Copy constructor.
     1086        ///
     1087        /// Copy Constructor.
     1088        NodeMap(const NodeMap& nm) : Parent(nm) {}
     1089
     1090        /// \brief Assign operator.
     1091        ///
     1092        /// Assign operator.
    10931093        template <typename CMap>
    1094         NodeMap& operator=(const CMap&) { 
     1094        NodeMap& operator=(const CMap&) {
    10951095          checkConcept<ReadMap<Node, _Value>, CMap>();
    10961096          return *this;
     
    11081108        typedef GraphMap<MappableDigraphComponent, Arc, _Value> Parent;
    11091109
    1110         /// \brief Construct a new map.
    1111         ///
    1112         /// Construct a new map for the digraph.
    1113         explicit ArcMap(const MappableDigraphComponent& digraph)
     1110        /// \brief Construct a new map.
     1111        ///
     1112        /// Construct a new map for the digraph.
     1113        explicit ArcMap(const MappableDigraphComponent& digraph)
    11141114          : Parent(digraph) {}
    11151115
    1116         /// \brief Construct a new map with default value.
    1117         ///
    1118         /// Construct a new map for the digraph and initalise the values.
    1119         ArcMap(const MappableDigraphComponent& digraph, const _Value& value)
     1116        /// \brief Construct a new map with default value.
     1117        ///
     1118        /// Construct a new map for the digraph and initalise the values.
     1119        ArcMap(const MappableDigraphComponent& digraph, const _Value& value)
    11201120          : Parent(digraph, value) {}
    11211121
    1122         /// \brief Copy constructor.
    1123         ///
    1124         /// Copy Constructor.
    1125         ArcMap(const ArcMap& nm) : Parent(nm) {}
    1126 
    1127         /// \brief Assign operator.
    1128         ///
    1129         /// Assign operator.
     1122        /// \brief Copy constructor.
     1123        ///
     1124        /// Copy Constructor.
     1125        ArcMap(const ArcMap& nm) : Parent(nm) {}
     1126
     1127        /// \brief Assign operator.
     1128        ///
     1129        /// Assign operator.
    11301130        template <typename CMap>
    1131         ArcMap& operator=(const CMap&) { 
     1131        ArcMap& operator=(const CMap&) {
    11321132          checkConcept<ReadMap<Arc, _Value>, CMap>();
    11331133          return *this;
     
    11401140      struct Constraints {
    11411141
    1142         struct Dummy {
    1143           int value;
    1144           Dummy() : value(0) {}
    1145           Dummy(int _v) : value(_v) {}
    1146         };
    1147 
    1148         void constraints() {
    1149           checkConcept<Base, _Digraph>();
    1150           { // int map test
    1151             typedef typename _Digraph::template NodeMap<int> IntNodeMap;
    1152             checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>,
    1153               IntNodeMap >();
    1154           } { // bool map test
    1155             typedef typename _Digraph::template NodeMap<bool> BoolNodeMap;
    1156             checkConcept<GraphMap<_Digraph, typename _Digraph::Node, bool>,
    1157               BoolNodeMap >();
    1158           } { // Dummy map test
    1159             typedef typename _Digraph::template NodeMap<Dummy> DummyNodeMap;
    1160             checkConcept<GraphMap<_Digraph, typename _Digraph::Node, Dummy>,
    1161               DummyNodeMap >();
    1162           }
    1163 
    1164           { // int map test
    1165             typedef typename _Digraph::template ArcMap<int> IntArcMap;
    1166             checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>,
    1167               IntArcMap >();
    1168           } { // bool map test
    1169             typedef typename _Digraph::template ArcMap<bool> BoolArcMap;
    1170             checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>,
    1171               BoolArcMap >();
    1172           } { // Dummy map test
    1173             typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap;
    1174             checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>,
    1175               DummyArcMap >();
    1176           }
    1177         }
    1178 
    1179         _Digraph& digraph;
     1142        struct Dummy {
     1143          int value;
     1144          Dummy() : value(0) {}
     1145          Dummy(int _v) : value(_v) {}
     1146        };
     1147
     1148        void constraints() {
     1149          checkConcept<Base, _Digraph>();
     1150          { // int map test
     1151            typedef typename _Digraph::template NodeMap<int> IntNodeMap;
     1152            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>,
     1153              IntNodeMap >();
     1154          } { // bool map test
     1155            typedef typename _Digraph::template NodeMap<bool> BoolNodeMap;
     1156            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, bool>,
     1157              BoolNodeMap >();
     1158          } { // Dummy map test
     1159            typedef typename _Digraph::template NodeMap<Dummy> DummyNodeMap;
     1160            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, Dummy>,
     1161              DummyNodeMap >();
     1162          }
     1163
     1164          { // int map test
     1165            typedef typename _Digraph::template ArcMap<int> IntArcMap;
     1166            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>,
     1167              IntArcMap >();
     1168          } { // bool map test
     1169            typedef typename _Digraph::template ArcMap<bool> BoolArcMap;
     1170            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>,
     1171              BoolArcMap >();
     1172          } { // Dummy map test
     1173            typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap;
     1174            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>,
     1175              DummyArcMap >();
     1176          }
     1177        }
     1178
     1179        _Digraph& digraph;
    11801180      };
    11811181    };
     
    12001200      ///
    12011201      template <typename _Value>
    1202       class EdgeMap : public GraphMap<Graph, Edge, _Value> { 
     1202      class EdgeMap : public GraphMap<Graph, Edge, _Value> {
    12031203      public:
    12041204        typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent;
    12051205
    1206         /// \brief Construct a new map.
    1207         ///
    1208         /// Construct a new map for the graph.
    1209         explicit EdgeMap(const MappableGraphComponent& graph)
     1206        /// \brief Construct a new map.
     1207        ///
     1208        /// Construct a new map for the graph.
     1209        explicit EdgeMap(const MappableGraphComponent& graph)
    12101210          : Parent(graph) {}
    12111211
    1212         /// \brief Construct a new map with default value.
    1213         ///
    1214         /// Construct a new map for the graph and initalise the values.
    1215         EdgeMap(const MappableGraphComponent& graph, const _Value& value)
     1212        /// \brief Construct a new map with default value.
     1213        ///
     1214        /// Construct a new map for the graph and initalise the values.
     1215        EdgeMap(const MappableGraphComponent& graph, const _Value& value)
    12161216          : Parent(graph, value) {}
    12171217
    1218         /// \brief Copy constructor.
    1219         ///
    1220         /// Copy Constructor.
    1221         EdgeMap(const EdgeMap& nm) : Parent(nm) {}
    1222 
    1223         /// \brief Assign operator.
    1224         ///
    1225         /// Assign operator.
     1218        /// \brief Copy constructor.
     1219        ///
     1220        /// Copy Constructor.
     1221        EdgeMap(const EdgeMap& nm) : Parent(nm) {}
     1222
     1223        /// \brief Assign operator.
     1224        ///
     1225        /// Assign operator.
    12261226        template <typename CMap>
    1227         EdgeMap& operator=(const CMap&) { 
     1227        EdgeMap& operator=(const CMap&) {
    12281228          checkConcept<ReadMap<Edge, _Value>, CMap>();
    12291229          return *this;
     
    12361236      struct Constraints {
    12371237
    1238         struct Dummy {
    1239           int value;
    1240           Dummy() : value(0) {}
    1241           Dummy(int _v) : value(_v) {}
    1242         };
    1243 
    1244         void constraints() {
    1245           checkConcept<MappableGraphComponent<Base>, _Graph>();
    1246 
    1247           { // int map test
    1248             typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
    1249             checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
    1250               IntEdgeMap >();
    1251           } { // bool map test
    1252             typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
    1253             checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
    1254               BoolEdgeMap >();
    1255           } { // Dummy map test
    1256             typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
    1257             checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
    1258               DummyEdgeMap >();
    1259           }
    1260         }
    1261 
    1262         _Graph& graph;
     1238        struct Dummy {
     1239          int value;
     1240          Dummy() : value(0) {}
     1241          Dummy(int _v) : value(_v) {}
     1242        };
     1243
     1244        void constraints() {
     1245          checkConcept<MappableGraphComponent<Base>, _Graph>();
     1246
     1247          { // int map test
     1248            typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
     1249            checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
     1250              IntEdgeMap >();
     1251          } { // bool map test
     1252            typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
     1253            checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
     1254              BoolEdgeMap >();
     1255          } { // Dummy map test
     1256            typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
     1257            checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
     1258              DummyEdgeMap >();
     1259          }
     1260        }
     1261
     1262        _Graph& graph;
    12631263      };
    12641264    };
     
    12831283      ///
    12841284      Node addNode() {
    1285         return INVALID;
     1285        return INVALID;
    12861286      }
    1287    
     1287
    12881288      /// \brief Adds a new arc connects the given two nodes.
    12891289      ///
    12901290      /// Adds a new arc connects the the given two nodes.
    12911291      Arc addArc(const Node&, const Node&) {
    1292         return INVALID;
     1292        return INVALID;
    12931293      }
    12941294
    12951295      template <typename _Digraph>
    12961296      struct Constraints {
    1297         void constraints() {
     1297        void constraints() {
    12981298          checkConcept<Base, _Digraph>();
    1299           typename _Digraph::Node node_a, node_b;
    1300           node_a = digraph.addNode();
    1301           node_b = digraph.addNode();
    1302           typename _Digraph::Arc arc;
    1303           arc = digraph.addArc(node_a, node_b);
    1304         }
    1305 
    1306         _Digraph& digraph;
     1299          typename _Digraph::Node node_a, node_b;
     1300          node_a = digraph.addNode();
     1301          node_b = digraph.addNode();
     1302          typename _Digraph::Arc arc;
     1303          arc = digraph.addArc(node_a, node_b);
     1304        }
     1305
     1306        _Digraph& digraph;
    13071307      };
    13081308    };
     
    13281328      ///
    13291329      Node addNode() {
    1330         return INVALID;
     1330        return INVALID;
    13311331      }
    1332    
     1332
    13331333      /// \brief Adds a new arc connects the given two nodes.
    13341334      ///
    13351335      /// Adds a new arc connects the the given two nodes.
    13361336      Edge addArc(const Node&, const Node&) {
    1337         return INVALID;
     1337        return INVALID;
    13381338      }
    13391339
    13401340      template <typename _Graph>
    13411341      struct Constraints {
    1342         void constraints() {
    1343           checkConcept<Base, _Graph>();
    1344           typename _Graph::Node node_a, node_b;
    1345           node_a = graph.addNode();
    1346           node_b = graph.addNode();
    1347           typename _Graph::Edge edge;
    1348           edge = graph.addEdge(node_a, node_b);
    1349         }
    1350 
    1351         _Graph& graph;
     1342        void constraints() {
     1343          checkConcept<Base, _Graph>();
     1344          typename _Graph::Node node_a, node_b;
     1345          node_a = graph.addNode();
     1346          node_b = graph.addNode();
     1347          typename _Graph::Edge edge;
     1348          edge = graph.addEdge(node_a, node_b);
     1349        }
     1350
     1351        _Graph& graph;
    13521352      };
    13531353    };
    13541354
    13551355    /// \brief An empty erasable digraph class.
    1356     /// 
     1356    ///
    13571357    /// This class provides beside the core digraph features core erase
    13581358    /// functions for the digraph structure. The main difference between
     
    13691369      /// \brief Erase a node from the digraph.
    13701370      ///
    1371       /// Erase a node from the digraph. This function should 
     1371      /// Erase a node from the digraph. This function should
    13721372      /// erase all arcs connecting to the node.
    1373       void erase(const Node&) {}   
     1373      void erase(const Node&) {}
    13741374
    13751375      /// \brief Erase an arc from the digraph.
     
    13811381      template <typename _Digraph>
    13821382      struct Constraints {
    1383         void constraints() {
     1383        void constraints() {
    13841384          checkConcept<Base, _Digraph>();
    1385           typename _Digraph::Node node;
    1386           digraph.erase(node);
    1387           typename _Digraph::Arc arc;
    1388           digraph.erase(arc);
    1389         }
    1390 
    1391         _Digraph& digraph;
     1385          typename _Digraph::Node node;
     1386          digraph.erase(node);
     1387          typename _Digraph::Arc arc;
     1388          digraph.erase(arc);
     1389        }
     1390
     1391        _Digraph& digraph;
    13921392      };
    13931393    };
    13941394
    13951395    /// \brief An empty erasable base undirected graph class.
    1396     /// 
     1396    ///
    13971397    /// This class provides beside the core undirected graph features
    13981398    /// core erase functions for the undirceted graph structure. The
     
    14111411      /// Erase a node from the graph. This function should erase
    14121412      /// arcs connecting to the node.
    1413       void erase(const Node&) {}   
     1413      void erase(const Node&) {}
    14141414
    14151415      /// \brief Erase an arc from the graph.
     
    14211421      template <typename _Graph>
    14221422      struct Constraints {
    1423         void constraints() {
     1423        void constraints() {
    14241424          checkConcept<Base, _Graph>();
    1425           typename _Graph::Node node;
    1426           graph.erase(node);
    1427           typename _Graph::Edge edge;
    1428           graph.erase(edge);
    1429         }
    1430 
    1431         _Graph& graph;
     1425          typename _Graph::Node node;
     1426          graph.erase(node);
     1427          typename _Graph::Edge edge;
     1428          graph.erase(edge);
     1429        }
     1430
     1431        _Graph& graph;
    14321432      };
    14331433    };
     
    14491449      /// Erase all nodes and arcs from the digraph.
    14501450      ///
    1451       void clear() {}   
     1451      void clear() {}
    14521452
    14531453      template <typename _Digraph>
    14541454      struct Constraints {
    1455         void constraints() {
     1455        void constraints() {
    14561456          checkConcept<Base, _Digraph>();
    1457           digraph.clear();
    1458         }
    1459 
    1460         _Digraph digraph;
     1457          digraph.clear();
     1458        }
     1459
     1460        _Digraph digraph;
    14611461      };
    14621462    };
     
    14761476      template <typename _Graph>
    14771477      struct Constraints {
    1478         void constraints() {
     1478        void constraints() {
    14791479          checkConcept<ClearableGraphComponent<Base>, _Graph>();
    1480         }
    1481 
    1482         _Graph graph;
     1480        }
     1481
     1482        _Graph graph;
    14831483      };
    14841484    };
Note: See TracChangeset for help on using the changeset viewer.