COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [624:1f631044c290:621:b536eaacb39b] in lemon-main


Ignore:
Files:
28 edited

Legend:

Unmodified
Added
Removed

  • demo/graph_to_eps_demo.cc

    r612 r440  
    183183  ListDigraph::NodeMap<Point> hcoords(h);
    184184
    185   int cols=int(std::sqrt(double(palette.size())));
     185  int cols=int(sqrt(double(palette.size())));
    186186  for(int i=0;i<int(paletteW.size());i++) {
    187187    Node n=h.addNode();

  • lemon/adaptors.h

    r617 r579  
    110110    template <typename V>
    111111    class NodeMap : public DGR::template NodeMap<V> {
     112    public:
     113
    112114      typedef typename DGR::template NodeMap<V> Parent;
    113115
    114     public:
    115116      explicit NodeMap(const Adaptor& adaptor)
    116117        : Parent(*adaptor._digraph) {}
     118
    117119      NodeMap(const Adaptor& adaptor, const V& value)
    118120        : Parent(*adaptor._digraph, value) { }
    … …  
    133135    template <typename V>
    134136    class ArcMap : public DGR::template ArcMap<V> {
     137    public:
     138
    135139      typedef typename DGR::template ArcMap<V> Parent;
    136140
    137     public:
    138141      explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)
    139142        : Parent(*adaptor._digraph) {}
     143
    140144      ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value)
    141145        : Parent(*adaptor._digraph, value) {}
    … …  
    252256    template <typename V>
    253257    class NodeMap : public GR::template NodeMap<V> {
     258    public:
    254259      typedef typename GR::template NodeMap<V> Parent;
    255 
    256     public:
    257260      explicit NodeMap(const GraphAdaptorBase<GR>& adapter)
    258261        : Parent(*adapter._graph) {}
    … …  
    275278    template <typename V>
    276279    class ArcMap : public GR::template ArcMap<V> {
     280    public:
    277281      typedef typename GR::template ArcMap<V> Parent;
    278 
    279     public:
    280282      explicit ArcMap(const GraphAdaptorBase<GR>& adapter)
    281283        : Parent(*adapter._graph) {}
    … …  
    297299    template <typename V>
    298300    class EdgeMap : public GR::template EdgeMap<V> {
     301    public:
    299302      typedef typename GR::template EdgeMap<V> Parent;
    300 
    301     public:
    302303      explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)
    303304        : Parent(*adapter._graph) {}
    … …  
    321322  template <typename DGR>
    322323  class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {
     324  public:
     325    typedef DGR Digraph;
    323326    typedef DigraphAdaptorBase<DGR> Parent;
    324   public:
    325     typedef DGR Digraph;
    326327  protected:
    327328    ReverseDigraphBase() : Parent() { }
    … …  
    374375    public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {
    375376#endif
    376     typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;
    377377  public:
    378378    /// The type of the adapted digraph.
    379379    typedef DGR Digraph;
     380    typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;
    380381  protected:
    381382    ReverseDigraph() { }
    … …  
    403404  template <typename DGR, typename NF, typename AF, bool ch = true>
    404405  class SubDigraphBase : public DigraphAdaptorBase<DGR> {
    405     typedef DigraphAdaptorBase<DGR> Parent;
    406406  public:
    407407    typedef DGR Digraph;
    … …  
    410410
    411411    typedef SubDigraphBase Adaptor;
     412    typedef DigraphAdaptorBase<DGR> Parent;
    412413  protected:
    413414    NF* _node_filter;
    … …  
    509510      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    510511              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    511       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    512         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    513 
    514512    public:
    515513      typedef V Value;
     514      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     515            LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    516516
    517517      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
    … …  
    536536      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    537537              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     538    public:
     539      typedef V Value;
    538540      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    539541        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
    540 
    541     public:
    542       typedef V Value;
    543542
    544543      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
    … …  
    564563  class SubDigraphBase<DGR, NF, AF, false>
    565564    : public DigraphAdaptorBase<DGR> {
    566     typedef DigraphAdaptorBase<DGR> Parent;
    567565  public:
    568566    typedef DGR Digraph;
    … …  
    571569
    572570    typedef SubDigraphBase Adaptor;
     571    typedef DigraphAdaptorBase<Digraph> Parent;
    573572  protected:
    574573    NF* _node_filter;
    … …  
    652651      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    653652          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
     653    public:
     654      typedef V Value;
    654655      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    655656        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    656 
    657     public:
    658       typedef V Value;
    659657
    660658      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
    … …  
    679677      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    680678          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
    681       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    682         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
    683 
    684679    public:
    685680      typedef V Value;
     681      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
     682          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
    686683
    687684      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
    … …  
    867864  template <typename GR, typename NF, typename EF, bool ch = true>
    868865  class SubGraphBase : public GraphAdaptorBase<GR> {
    869     typedef GraphAdaptorBase<GR> Parent;
    870866  public:
    871867    typedef GR Graph;
    … …  
    874870
    875871    typedef SubGraphBase Adaptor;
     872    typedef GraphAdaptorBase<GR> Parent;
    876873  protected:
    877874
    … …  
    10201017      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10211018          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
     1019    public:
     1020      typedef V Value;
    10221021      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10231022        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    1024 
    1025     public:
    1026       typedef V Value;
    10271023
    10281024      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
    … …  
    10471043      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10481044          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
     1045    public:
     1046      typedef V Value;
    10491047      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10501048        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    1051 
    1052     public:
    1053       typedef V Value;
    10541049
    10551050      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
    … …  
    10741069      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10751070        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
     1071    public:
     1072      typedef V Value;
    10761073      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10771074        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    1078 
    1079     public:
    1080       typedef V Value;
    10811075
    10821076      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
    … …  
    11031097  class SubGraphBase<GR, NF, EF, false>
    11041098    : public GraphAdaptorBase<GR> {
    1105     typedef GraphAdaptorBase<GR> Parent;
    11061099  public:
    11071100    typedef GR Graph;
    … …  
    11101103
    11111104    typedef SubGraphBase Adaptor;
     1105    typedef GraphAdaptorBase<GR> Parent;
    11121106  protected:
    11131107    NF* _node_filter;
    … …  
    12181212      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12191213          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
     1214    public:
     1215      typedef V Value;
    12201216      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12211217        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    1222 
    1223     public:
    1224       typedef V Value;
    12251218
    12261219      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
    … …  
    12451238      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12461239          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
     1240    public:
     1241      typedef V Value;
    12471242      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12481243        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    1249 
    1250     public:
    1251       typedef V Value;
    12521244
    12531245      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
    … …  
    12721264      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12731265        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1274       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    1275         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    1276 
    12771266    public:
    12781267      typedef V Value;
     1268      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1269                  LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    12791270
    12801271      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
    … …  
    14951486                     true> > {
    14961487#endif
     1488  public:
     1489
     1490    typedef GR Digraph;
     1491    typedef NF NodeFilterMap;
     1492
    14971493    typedef DigraphAdaptorExtender<
    14981494      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
    14991495                     true> > Parent;
    1500 
    1501   public:
    1502 
    1503     typedef GR Digraph;
    1504     typedef NF NodeFilterMap;
    15051496
    15061497    typedef typename Parent::Node Node;
    … …  
    15581549                   true> > {
    15591550
     1551  public:
     1552    typedef GR Graph;
     1553    typedef NF NodeFilterMap;
    15601554    typedef GraphAdaptorExtender<
    15611555      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
    15621556                   true> > Parent;
    15631557
    1564   public:
    1565 
    1566     typedef GR Graph;
    1567     typedef NF NodeFilterMap;
    1568 
    15691558    typedef typename Parent::Node Node;
    1570 
    15711559  protected:
    15721560    ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;
    … …  
    16421630                     AF, false> > {
    16431631#endif
    1644     typedef DigraphAdaptorExtender<
    1645       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
    1646                      AF, false> > Parent;
    1647 
    1648   public:
    1649 
     1632  public:
    16501633    /// The type of the adapted digraph.
    16511634    typedef DGR Digraph;
    16521635    /// The type of the arc filter map.
    16531636    typedef AF ArcFilterMap;
     1637
     1638    typedef DigraphAdaptorExtender<
     1639      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
     1640                     AF, false> > Parent;
    16541641
    16551642    typedef typename Parent::Arc Arc;
    … …  
    17521739                   EF, false> > {
    17531740#endif
    1754     typedef GraphAdaptorExtender<
    1755       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
    1756                    EF, false> > Parent;
    1757 
    1758   public:
    1759 
     1741  public:
    17601742    /// The type of the adapted graph.
    17611743    typedef GR Graph;
    17621744    /// The type of the edge filter map.
    17631745    typedef EF EdgeFilterMap;
     1746
     1747    typedef GraphAdaptorExtender<
     1748      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
     1749                   EF, false> > Parent;
    17641750
    17651751    typedef typename Parent::Edge Edge;
    … …  
    21262112    template <typename V>
    21272113    class NodeMap : public DGR::template NodeMap<V> {
    2128       typedef typename DGR::template NodeMap<V> Parent;
    2129 
    21302114    public:
     2115
    21312116      typedef V Value;
     2117      typedef typename DGR::template NodeMap<Value> Parent;
    21322118
    21332119      explicit NodeMap(const UndirectorBase<DGR>& adaptor)
    … …  
    21522138    template <typename V>
    21532139    class ArcMap
    2154       : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > {
    2155       typedef SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > Parent;
    2156 
     2140      : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> >
     2141    {
    21572142    public:
    21582143      typedef V Value;
     2144      typedef SubMapExtender<Adaptor, ArcMapBase<V> > Parent;
    21592145
    21602146      explicit ArcMap(const UndirectorBase<DGR>& adaptor)
    … …  
    21782164    template <typename V>
    21792165    class EdgeMap : public Digraph::template ArcMap<V> {
     2166    public:
     2167
     2168      typedef V Value;
    21802169      typedef typename Digraph::template ArcMap<V> Parent;
    2181 
    2182     public:
    2183       typedef V Value;
    21842170
    21852171      explicit EdgeMap(const UndirectorBase<DGR>& adaptor)
    … …  
    22532239    public GraphAdaptorExtender<UndirectorBase<DGR> > {
    22542240#endif
    2255     typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
    22562241  public:
    22572242    /// The type of the adapted digraph.
    22582243    typedef DGR Digraph;
     2244    typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
    22592245  protected:
    22602246    Undirector() { }
    … …  
    24642450    template <typename V>
    24652451    class NodeMap : public GR::template NodeMap<V> {
     2452    public:
     2453
    24662454      typedef typename GR::template NodeMap<V> Parent;
    2467 
    2468     public:
    24692455
    24702456      explicit NodeMap(const OrienterBase<GR, DM>& adapter)
    … …  
    24892475    template <typename V>
    24902476    class ArcMap : public GR::template EdgeMap<V> {
     2477    public:
     2478
    24912479      typedef typename Graph::template EdgeMap<V> Parent;
    2492 
    2493     public:
    24942480
    24952481      explicit ArcMap(const OrienterBase<GR, DM>& adapter)
    … …  
    25612547    public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
    25622548#endif
    2563     typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
    25642549  public:
    25652550
    … …  
    25692554    typedef DM DirectionMap;
    25702555
     2556    typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
    25712557    typedef typename Parent::Arc Arc;
    2572 
    25732558  protected:
    25742559    Orienter() { }
    2575 
    25762560  public:
    25772561
    … …  
    28832867  template <typename DGR>
    28842868  class SplitNodesBase {
     2869  public:
     2870
     2871    typedef DGR Digraph;
    28852872    typedef DigraphAdaptorBase<const DGR> Parent;
    2886 
    2887   public:
    2888 
    2889     typedef DGR Digraph;
    28902873    typedef SplitNodesBase Adaptor;
    28912874
    … …  
    32463229    template <typename V>
    32473230    class NodeMap
    3248       : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > {
    3249       typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > Parent;
    3250 
     3231      : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> >
     3232    {
    32513233    public:
    32523234      typedef V Value;
     3235      typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<Value> > Parent;
    32533236
    32543237      NodeMap(const SplitNodesBase<DGR>& adaptor)
    … …  
    32723255    template <typename V>
    32733256    class ArcMap
    3274       : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > {
    3275       typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > Parent;
    3276 
     3257      : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> >
     3258    {
    32773259    public:
    32783260      typedef V Value;
     3261      typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<Value> > Parent;
    32793262
    32803263      ArcMap(const SplitNodesBase<DGR>& adaptor)
    … …  
    33423325    : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {
    33433326#endif
     3327  public:
     3328    typedef DGR Digraph;
    33443329    typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
    3345 
    3346   public:
    3347     typedef DGR Digraph;
    33483330
    33493331    typedef typename DGR::Node DigraphNode;

  • lemon/bits/array_map.h

    r617 r503  
    4848  public:
    4949    // The graph type.
    50     typedef _Graph GraphType;
     50    typedef _Graph Graph;
    5151    // The item type.
    5252    typedef _Item Item;
    … …  
    6464    typedef _Value& Reference;
    6565
    66     // The map type.
    67     typedef ArrayMap Map;
    68 
    6966    // The notifier type.
    7067    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    7168
    72   private:
    73  
    7469    // The MapBase of the Map which imlements the core regisitry function.
    7570    typedef typename Notifier::ObserverBase Parent;
    7671
     72  private:
    7773    typedef std::allocator<Value> Allocator;
    7874
    … …  
    8278    //
    8379    // Graph initialized map constructor.
    84     explicit ArrayMap(const GraphType& graph) {
     80    explicit ArrayMap(const Graph& graph) {
    8581      Parent::attach(graph.notifier(Item()));
    8682      allocate_memory();
    … …  
    9692    //
    9793    // It constructs a map and initialize all of the the map.
    98     ArrayMap(const GraphType& graph, const Value& value) {
     94    ArrayMap(const Graph& graph, const Value& value) {
    9995      Parent::attach(graph.notifier(Item()));
    10096      allocate_memory();

  • lemon/bits/base_extender.h

    r617 r440  
    3939  template <typename Base>
    4040  class UndirDigraphExtender : public Base {
     41
     42  public:
     43
    4144    typedef Base Parent;
    42 
    43   public:
    44 
    4545    typedef typename Parent::Arc Edge;
    4646    typedef typename Parent::Node Node;
    … …  
    281281  template <typename Base>
    282282  class BidirBpGraphExtender : public Base {
     283  public:
    283284    typedef Base Parent;
    284 
    285   public:
    286285    typedef BidirBpGraphExtender Digraph;
    287286

  • lemon/bits/default_map.h

    r617 r535  
    154154  class DefaultMap
    155155    : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
     156  public:
    156157    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
     158    typedef DefaultMap<_Graph, _Item, _Value> Map;
    157159
    158   public:
    159     typedef DefaultMap<_Graph, _Item, _Value> Map;
    160    
    161     typedef typename Parent::GraphType GraphType;
     160    typedef typename Parent::Graph Graph;
    162161    typedef typename Parent::Value Value;
    163162
    164     explicit DefaultMap(const GraphType& graph) : Parent(graph) {}
    165     DefaultMap(const GraphType& graph, const Value& value)
     163    explicit DefaultMap(const Graph& graph) : Parent(graph) {}
     164    DefaultMap(const Graph& graph, const Value& value)
    166165      : Parent(graph, value) {}
    167166

  • lemon/bits/edge_set_extender.h

    r617 r559  
    3535  template <typename Base>
    3636  class ArcSetExtender : public Base {
     37  public:
     38
    3739    typedef Base Parent;
    38 
    39   public:
    40 
    4140    typedef ArcSetExtender Digraph;
    4241
    … …  
    220219    class ArcMap
    221220      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
     221    public:
     222      typedef ArcSetExtender Digraph;
    222223      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    223224
    224     public:
    225225      explicit ArcMap(const Digraph& _g)
    226226        : Parent(_g) {}
    … …  
    275275  template <typename Base>
    276276  class EdgeSetExtender : public Base {
     277
     278  public:
     279
    277280    typedef Base Parent;
    278 
    279   public:
    280 
    281     typedef EdgeSetExtender Graph;
     281    typedef EdgeSetExtender Digraph;
    282282
    283283    typedef typename Parent::Node Node;
    284284    typedef typename Parent::Arc Arc;
    285285    typedef typename Parent::Edge Edge;
     286
    286287
    287288    int maxId(Node) const {
    … …  
    350351
    351352    class NodeIt : public Node {
    352       const Graph* graph;
     353      const Digraph* digraph;
    353354    public:
    354355
    … …  
    357358      NodeIt(Invalid i) : Node(i) { }
    358359
    359       explicit NodeIt(const Graph& _graph) : graph(&_graph) {
     360      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
    360361        _graph.first(static_cast<Node&>(*this));
    361362      }
    362363
    363       NodeIt(const Graph& _graph, const Node& node)
    364         : Node(node), graph(&_graph) {}
     364      NodeIt(const Digraph& _graph, const Node& node)
     365        : Node(node), digraph(&_graph) {}
    365366
    366367      NodeIt& operator++() {
    367         graph->next(*this);
     368        digraph->next(*this);
    368369        return *this;
    369370      }
    … …  
    373374
    374375    class ArcIt : public Arc {
    375       const Graph* graph;
     376      const Digraph* digraph;
    376377    public:
    377378
    … …  
    380381      ArcIt(Invalid i) : Arc(i) { }
    381382
    382       explicit ArcIt(const Graph& _graph) : graph(&_graph) {
     383      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
    383384        _graph.first(static_cast<Arc&>(*this));
    384385      }
    385386
    386       ArcIt(const Graph& _graph, const Arc& e) :
    387         Arc(e), graph(&_graph) { }
     387      ArcIt(const Digraph& _graph, const Arc& e) :
     388        Arc(e), digraph(&_graph) { }
    388389
    389390      ArcIt& operator++() {
    390         graph->next(*this);
     391        digraph->next(*this);
    391392        return *this;
    392393      }
    … …  
    396397
    397398    class OutArcIt : public Arc {
    398       const Graph* graph;
     399      const Digraph* digraph;
    399400    public:
    400401
    … …  
    403404      OutArcIt(Invalid i) : Arc(i) { }
    404405
    405       OutArcIt(const Graph& _graph, const Node& node)
    406         : graph(&_graph) {
     406      OutArcIt(const Digraph& _graph, const Node& node)
     407        : digraph(&_graph) {
    407408        _graph.firstOut(*this, node);
    408409      }
    409410
    410       OutArcIt(const Graph& _graph, const Arc& arc)
    411         : Arc(arc), graph(&_graph) {}
     411      OutArcIt(const Digraph& _graph, const Arc& arc)
     412        : Arc(arc), digraph(&_graph) {}
    412413
    413414      OutArcIt& operator++() {
    414         graph->nextOut(*this);
     415        digraph->nextOut(*this);
    415416        return *this;
    416417      }
    … …  
    420421
    421422    class InArcIt : public Arc {
    422       const Graph* graph;
     423      const Digraph* digraph;
    423424    public:
    424425
    … …  
    427428      InArcIt(Invalid i) : Arc(i) { }
    428429
    429       InArcIt(const Graph& _graph, const Node& node)
    430         : graph(&_graph) {
     430      InArcIt(const Digraph& _graph, const Node& node)
     431        : digraph(&_graph) {
    431432        _graph.firstIn(*this, node);
    432433      }
    433434
    434       InArcIt(const Graph& _graph, const Arc& arc) :
    435         Arc(arc), graph(&_graph) {}
     435      InArcIt(const Digraph& _graph, const Arc& arc) :
     436        Arc(arc), digraph(&_graph) {}
    436437
    437438      InArcIt& operator++() {
    438         graph->nextIn(*this);
     439        digraph->nextIn(*this);
    439440        return *this;
    440441      }
    … …  
    444445
    445446    class EdgeIt : public Parent::Edge {
    446       const Graph* graph;
     447      const Digraph* digraph;
    447448    public:
    448449
    … …  
    451452      EdgeIt(Invalid i) : Edge(i) { }
    452453
    453       explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
     454      explicit EdgeIt(const Digraph& _graph) : digraph(&_graph) {
    454455        _graph.first(static_cast<Edge&>(*this));
    455456      }
    456457
    457       EdgeIt(const Graph& _graph, const Edge& e) :
    458         Edge(e), graph(&_graph) { }
     458      EdgeIt(const Digraph& _graph, const Edge& e) :
     459        Edge(e), digraph(&_graph) { }
    459460
    460461      EdgeIt& operator++() {
    461         graph->next(*this);
     462        digraph->next(*this);
    462463        return *this;
    463464      }
    … …  
    467468    class IncEdgeIt : public Parent::Edge {
    468469      friend class EdgeSetExtender;
    469       const Graph* graph;
     470      const Digraph* digraph;
    470471      bool direction;
    471472    public:
    … …  
    475476      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
    476477
    477       IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
     478      IncEdgeIt(const Digraph& _graph, const Node &n) : digraph(&_graph) {
    478479        _graph.firstInc(*this, direction, n);
    479480      }
    480481
    481       IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
    482         : graph(&_graph), Edge(ue) {
     482      IncEdgeIt(const Digraph& _graph, const Edge &ue, const Node &n)
     483        : digraph(&_graph), Edge(ue) {
    483484        direction = (_graph.source(ue) == n);
    484485      }
    485486
    486487      IncEdgeIt& operator++() {
    487         graph->nextInc(*this, direction);
     488        digraph->nextInc(*this, direction);
    488489        return *this;
    489490      }
    … …  
    534535    template <typename _Value>
    535536    class ArcMap
    536       : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
    537       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    538 
    539     public:
    540       ArcMap(const Graph& _g)
     537      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
     538    public:
     539      typedef EdgeSetExtender Digraph;
     540      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
     541
     542      ArcMap(const Digraph& _g)
    541543        : Parent(_g) {}
    542       ArcMap(const Graph& _g, const _Value& _v)
     544      ArcMap(const Digraph& _g, const _Value& _v)
    543545        : Parent(_g, _v) {}
    544546
    … …  
    558560    template <typename _Value>
    559561    class EdgeMap
    560       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    561       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    562 
    563     public:
    564       EdgeMap(const Graph& _g)
     562      : public MapExtender<DefaultMap<Digraph, Edge, _Value> > {
     563    public:
     564      typedef EdgeSetExtender Digraph;
     565      typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
     566
     567      EdgeMap(const Digraph& _g)
    565568        : Parent(_g) {}
    566569
    567       EdgeMap(const Graph& _g, const _Value& _v)
     570      EdgeMap(const Digraph& _g, const _Value& _v)
    568571        : Parent(_g, _v) {}
    569572

  • lemon/bits/graph_adaptor_extender.h

    r617 r580  
    2727  template <typename _Digraph>
    2828  class DigraphAdaptorExtender : public _Digraph {
     29  public:
     30
    2931    typedef _Digraph Parent;
    30 
    31   public:
    32 
    3332    typedef _Digraph Digraph;
    3433    typedef DigraphAdaptorExtender Adaptor;
    … …  
    175174  template <typename _Graph>
    176175  class GraphAdaptorExtender : public _Graph {
     176  public:
     177
    177178    typedef _Graph Parent;
    178 
    179   public:
    180 
    181179    typedef _Graph Graph;
    182180    typedef GraphAdaptorExtender Adaptor;

  • lemon/bits/graph_extender.h

    r617 r440  
    3838  template <typename Base>
    3939  class DigraphExtender : public Base {
     40  public:
     41
    4042    typedef Base Parent;
    41 
    42   public:
    43 
    4443    typedef DigraphExtender Digraph;
    4544
    … …  
    220219    class NodeMap
    221220      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
     221    public:
     222      typedef DigraphExtender Digraph;
    222223      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
    223224
    224     public:
    225225      explicit NodeMap(const Digraph& digraph)
    226226        : Parent(digraph) {}
    … …  
    244244    class ArcMap
    245245      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
     246    public:
     247      typedef DigraphExtender Digraph;
    246248      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    247249
    248     public:
    249250      explicit ArcMap(const Digraph& digraph)
    250251        : Parent(digraph) {}
    … …  
    330331  template <typename Base>
    331332  class GraphExtender : public Base {
     333  public:
     334
    332335    typedef Base Parent;
    333 
    334   public:
    335 
    336336    typedef GraphExtender Graph;
    337337
    … …  
    602602    class NodeMap
    603603      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
     604    public:
     605      typedef GraphExtender Graph;
    604606      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
    605607
    606     public:
    607608      NodeMap(const Graph& graph)
    608609        : Parent(graph) {}
    … …  
    626627    class ArcMap
    627628      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
     629    public:
     630      typedef GraphExtender Graph;
    628631      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    629632
    630     public:
    631633      ArcMap(const Graph& graph)
    632634        : Parent(graph) {}
    … …  
    650652    class EdgeMap
    651653      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
     654    public:
     655      typedef GraphExtender Graph;
    652656      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    653657
    654     public:
    655658      EdgeMap(const Graph& graph)
    656659        : Parent(graph) {}

  • lemon/bits/map_extender.h

    r617 r580  
    3737  template <typename _Map>
    3838  class MapExtender : public _Map {
     39  public:
     40
    3941    typedef _Map Parent;
    40     typedef typename Parent::GraphType GraphType;
    41 
    42   public:
    43 
    4442    typedef MapExtender Map;
     43
     44
     45    typedef typename Parent::Graph Graph;
    4546    typedef typename Parent::Key Item;
    4647
    … …  
    5859  public:
    5960
    60     MapExtender(const GraphType& graph)
     61    MapExtender(const Graph& graph)
    6162      : Parent(graph) {}
    6263
    63     MapExtender(const GraphType& graph, const Value& value)
     64    MapExtender(const Graph& graph, const Value& value)
    6465      : Parent(graph, value) {}
    6566
    … …  
    7778  public:
    7879    class MapIt : public Item {
    79       typedef Item Parent;
    80 
    81     public:
    82 
     80    public:
     81
     82      typedef Item Parent;
    8383      typedef typename Map::Value Value;
    8484
    … …  
    117117
    118118    class ConstMapIt : public Item {
    119       typedef Item Parent;
    120 
    121     public:
     119    public:
     120
     121      typedef Item Parent;
    122122
    123123      typedef typename Map::Value Value;
    … …  
    148148
    149149    class ItemIt : public Item {
    150       typedef Item Parent;
    151 
    152     public:
     150    public:
     151
     152      typedef Item Parent;
    153153
    154154      ItemIt() {}
    … …  
    179179  template <typename _Graph, typename _Map>
    180180  class SubMapExtender : public _Map {
     181  public:
     182
    181183    typedef _Map Parent;
    182     typedef _Graph GraphType;
    183 
    184   public:
    185 
    186184    typedef SubMapExtender Map;
     185
     186    typedef _Graph Graph;
     187
    187188    typedef typename Parent::Key Item;
    188189
    … …  
    200201  public:
    201202
    202     SubMapExtender(const GraphType& _graph)
     203    SubMapExtender(const Graph& _graph)
    203204      : Parent(_graph), graph(_graph) {}
    204205
    205     SubMapExtender(const GraphType& _graph, const Value& _value)
     206    SubMapExtender(const Graph& _graph, const Value& _value)
    206207      : Parent(_graph, _value), graph(_graph) {}
    207208
    … …  
    223224  public:
    224225    class MapIt : public Item {
    225       typedef Item Parent;
    226 
    227     public:
     226    public:
     227
     228      typedef Item Parent;
    228229      typedef typename Map::Value Value;
    229230
    … …  
    262263
    263264    class ConstMapIt : public Item {
    264       typedef Item Parent;
    265 
    266     public:
     265    public:
     266
     267      typedef Item Parent;
    267268
    268269      typedef typename Map::Value Value;
    … …  
    293294
    294295    class ItemIt : public Item {
    295       typedef Item Parent;
    296 
    297     public:
     296    public:
     297
     298      typedef Item Parent;
    298299
    299300      ItemIt() {}
    … …  
    320321  private:
    321322
    322     const GraphType& graph;
     323    const Graph& graph;
    323324
    324325  };

  • lemon/bits/traits.h

    r616 r440  
    3030  struct InvalidType {};
    3131
    32   template <typename GR, typename _Item>
     32  template <typename _Graph, typename _Item>
    3333  class ItemSetTraits {};
    3434
    3535
    36   template <typename GR, typename Enable = void>
     36  template <typename Graph, typename Enable = void>
    3737  struct NodeNotifierIndicator {
    3838    typedef InvalidType Type;
    3939  };
    40   template <typename GR>
     40  template <typename Graph>
    4141  struct NodeNotifierIndicator<
    42     GR,
    43     typename enable_if<typename GR::NodeNotifier::Notifier, void>::type
    44   > {
    45     typedef typename GR::NodeNotifier Type;
    46   };
    47 
    48   template <typename GR>
    49   class ItemSetTraits<GR, typename GR::Node> {
     42    Graph,
     43    typename enable_if<typename Graph::NodeNotifier::Notifier, void>::type
     44  > {
     45    typedef typename Graph::NodeNotifier Type;
     46  };
     47
     48  template <typename _Graph>
     49  class ItemSetTraits<_Graph, typename _Graph::Node> {
    5050  public:
    5151
    52     typedef GR Graph;
    53     typedef GR Digraph;
    54 
    55     typedef typename GR::Node Item;
    56     typedef typename GR::NodeIt ItemIt;
    57 
    58     typedef typename NodeNotifierIndicator<GR>::Type ItemNotifier;
    59 
    60     template <typename V>
    61     class Map : public GR::template NodeMap<V> {
    62       typedef typename GR::template NodeMap<V> Parent;
    63 
     52    typedef _Graph Graph;
     53
     54    typedef typename Graph::Node Item;
     55    typedef typename Graph::NodeIt ItemIt;
     56
     57    typedef typename NodeNotifierIndicator<Graph>::Type ItemNotifier;
     58
     59    template <typename _Value>
     60    class Map : public Graph::template NodeMap<_Value> {
    6461    public:
    65       typedef typename GR::template NodeMap<V> Type;
     62      typedef typename Graph::template NodeMap<_Value> Parent;
     63      typedef typename Graph::template NodeMap<_Value> Type;
    6664      typedef typename Parent::Value Value;
    6765
    68       Map(const GR& _digraph) : Parent(_digraph) {}
    69       Map(const GR& _digraph, const Value& _value)
     66      Map(const Graph& _digraph) : Parent(_digraph) {}
     67      Map(const Graph& _digraph, const Value& _value)
    7068        : Parent(_digraph, _value) {}
    7169
    … …  
    7472  };
    7573
    76   template <typename GR, typename Enable = void>
     74  template <typename Graph, typename Enable = void>
    7775  struct ArcNotifierIndicator {
    7876    typedef InvalidType Type;
    7977  };
    80   template <typename GR>
     78  template <typename Graph>
    8179  struct ArcNotifierIndicator<
    82     GR,
    83     typename enable_if<typename GR::ArcNotifier::Notifier, void>::type
    84   > {
    85     typedef typename GR::ArcNotifier Type;
    86   };
    87 
    88   template <typename GR>
    89   class ItemSetTraits<GR, typename GR::Arc> {
     80    Graph,
     81    typename enable_if<typename Graph::ArcNotifier::Notifier, void>::type
     82  > {
     83    typedef typename Graph::ArcNotifier Type;
     84  };
     85
     86  template <typename _Graph>
     87  class ItemSetTraits<_Graph, typename _Graph::Arc> {
    9088  public:
    9189
    92     typedef GR Graph;
    93     typedef GR Digraph;
    94 
    95     typedef typename GR::Arc Item;
    96     typedef typename GR::ArcIt ItemIt;
    97 
    98     typedef typename ArcNotifierIndicator<GR>::Type ItemNotifier;
    99 
    100     template <typename V>
    101     class Map : public GR::template ArcMap<V> {
    102       typedef typename GR::template ArcMap<V> Parent;
    103 
     90    typedef _Graph Graph;
     91
     92    typedef typename Graph::Arc Item;
     93    typedef typename Graph::ArcIt ItemIt;
     94
     95    typedef typename ArcNotifierIndicator<Graph>::Type ItemNotifier;
     96
     97    template <typename _Value>
     98    class Map : public Graph::template ArcMap<_Value> {
    10499    public:
    105       typedef typename GR::template ArcMap<V> Type;
     100      typedef typename Graph::template ArcMap<_Value> Parent;
     101      typedef typename Graph::template ArcMap<_Value> Type;
    106102      typedef typename Parent::Value Value;
    107103
    108       Map(const GR& _digraph) : Parent(_digraph) {}
    109       Map(const GR& _digraph, const Value& _value)
     104      Map(const Graph& _digraph) : Parent(_digraph) {}
     105      Map(const Graph& _digraph, const Value& _value)
    110106        : Parent(_digraph, _value) {}
    111107    };
    … …  
    113109  };
    114110
    115   template <typename GR, typename Enable = void>
     111  template <typename Graph, typename Enable = void>
    116112  struct EdgeNotifierIndicator {
    117113    typedef InvalidType Type;
    118114  };
    119   template <typename GR>
     115  template <typename Graph>
    120116  struct EdgeNotifierIndicator<
    121     GR,
    122     typename enable_if<typename GR::EdgeNotifier::Notifier, void>::type
    123   > {
    124     typedef typename GR::EdgeNotifier Type;
    125   };
    126 
    127   template <typename GR>
    128   class ItemSetTraits<GR, typename GR::Edge> {
     117    Graph,
     118    typename enable_if<typename Graph::EdgeNotifier::Notifier, void>::type
     119  > {
     120    typedef typename Graph::EdgeNotifier Type;
     121  };
     122
     123  template <typename _Graph>
     124  class ItemSetTraits<_Graph, typename _Graph::Edge> {
    129125  public:
    130126
    131     typedef GR Graph;
    132     typedef GR Digraph;
    133 
    134     typedef typename GR::Edge Item;
    135     typedef typename GR::EdgeIt ItemIt;
    136 
    137     typedef typename EdgeNotifierIndicator<GR>::Type ItemNotifier;
    138 
    139     template <typename V>
    140     class Map : public GR::template EdgeMap<V> {
    141       typedef typename GR::template EdgeMap<V> Parent;
    142 
     127    typedef _Graph Graph;
     128
     129    typedef typename Graph::Edge Item;
     130    typedef typename Graph::EdgeIt ItemIt;
     131
     132    typedef typename EdgeNotifierIndicator<Graph>::Type ItemNotifier;
     133
     134    template <typename _Value>
     135    class Map : public Graph::template EdgeMap<_Value> {
    143136    public:
    144       typedef typename GR::template EdgeMap<V> Type;
     137      typedef typename Graph::template EdgeMap<_Value> Parent;
     138      typedef typename Graph::template EdgeMap<_Value> Type;
    145139      typedef typename Parent::Value Value;
    146140
    147       Map(const GR& _digraph) : Parent(_digraph) {}
    148       Map(const GR& _digraph, const Value& _value)
     141      Map(const Graph& _digraph) : Parent(_digraph) {}
     142      Map(const Graph& _digraph, const Value& _value)
    149143        : Parent(_digraph, _value) {}
    150144    };
    … …  
    211205  // Indicators for the tags
    212206
    213   template <typename GR, typename Enable = void>
     207  template <typename Graph, typename Enable = void>
    214208  struct NodeNumTagIndicator {
    215209    static const bool value = false;
    216210  };
    217211
    218   template <typename GR>
     212  template <typename Graph>
    219213  struct NodeNumTagIndicator<
    220     GR,
    221     typename enable_if<typename GR::NodeNumTag, void>::type
    222   > {
    223     static const bool value = true;
    224   };
    225 
    226   template <typename GR, typename Enable = void>
     214    Graph,
     215    typename enable_if<typename Graph::NodeNumTag, void>::type
     216  > {
     217    static const bool value = true;
     218  };
     219
     220  template <typename Graph, typename Enable = void>
    227221  struct ArcNumTagIndicator {
    228222    static const bool value = false;
    229223  };
    230224
    231   template <typename GR>
     225  template <typename Graph>
    232226  struct ArcNumTagIndicator<
    233     GR,
    234     typename enable_if<typename GR::ArcNumTag, void>::type
    235   > {
    236     static const bool value = true;
    237   };
    238 
    239   template <typename GR, typename Enable = void>
     227    Graph,
     228    typename enable_if<typename Graph::ArcNumTag, void>::type
     229  > {
     230    static const bool value = true;
     231  };
     232
     233  template <typename Graph, typename Enable = void>
    240234  struct EdgeNumTagIndicator {
    241235    static const bool value = false;
    242236  };
    243237
    244   template <typename GR>
     238  template <typename Graph>
    245239  struct EdgeNumTagIndicator<
    246     GR,
    247     typename enable_if<typename GR::EdgeNumTag, void>::type
    248   > {
    249     static const bool value = true;
    250   };
    251 
    252   template <typename GR, typename Enable = void>
     240    Graph,
     241    typename enable_if<typename Graph::EdgeNumTag, void>::type
     242  > {
     243    static const bool value = true;
     244  };
     245
     246  template <typename Graph, typename Enable = void>
    253247  struct FindArcTagIndicator {
    254248    static const bool value = false;
    255249  };
    256250
    257   template <typename GR>
     251  template <typename Graph>
    258252  struct FindArcTagIndicator<
    259     GR,
    260     typename enable_if<typename GR::FindArcTag, void>::type
    261   > {
    262     static const bool value = true;
    263   };
    264 
    265   template <typename GR, typename Enable = void>
     253    Graph,
     254    typename enable_if<typename Graph::FindArcTag, void>::type
     255  > {
     256    static const bool value = true;
     257  };
     258
     259  template <typename Graph, typename Enable = void>
    266260  struct FindEdgeTagIndicator {
    267261    static const bool value = false;
    268262  };
    269263
    270   template <typename GR>
     264  template <typename Graph>
    271265  struct FindEdgeTagIndicator<
    272     GR,
    273     typename enable_if<typename GR::FindEdgeTag, void>::type
    274   > {
    275     static const bool value = true;
    276   };
    277 
    278   template <typename GR, typename Enable = void>
     266    Graph,
     267    typename enable_if<typename Graph::FindEdgeTag, void>::type
     268  > {
     269    static const bool value = true;
     270  };
     271
     272  template <typename Graph, typename Enable = void>
    279273  struct UndirectedTagIndicator {
    280274    static const bool value = false;
    281275  };
    282276
    283   template <typename GR>
     277  template <typename Graph>
    284278  struct UndirectedTagIndicator<
    285     GR,
    286     typename enable_if<typename GR::UndirectedTag, void>::type
    287   > {
    288     static const bool value = true;
    289   };
    290 
    291   template <typename GR, typename Enable = void>
     279    Graph,
     280    typename enable_if<typename Graph::UndirectedTag, void>::type
     281  > {
     282    static const bool value = true;
     283  };
     284
     285  template <typename Graph, typename Enable = void>
    292286  struct BuildTagIndicator {
    293287    static const bool value = false;
    294288  };
    295289
    296   template <typename GR>
     290  template <typename Graph>
    297291  struct BuildTagIndicator<
    298     GR,
    299     typename enable_if<typename GR::BuildTag, void>::type
     292    Graph,
     293    typename enable_if<typename Graph::BuildTag, void>::type
    300294  > {
    301295    static const bool value = true;

  • lemon/bits/vector_map.h

    r617 r503  
    5757
    5858    // The graph type of the map.
    59     typedef _Graph GraphType;
     59    typedef _Graph Graph;
    6060    // The item type of the map.
    6161    typedef _Item Item;
    … …  
    7373    // The map type.
    7474    typedef VectorMap Map;
     75    // The base class of the map.
     76    typedef typename Notifier::ObserverBase Parent;
    7577
    7678    // The reference type of the map;
    … …  
    7981    typedef typename Container::const_reference ConstReference;
    8082
    81   private:
    82 
    83     // The base class of the map.
    84     typedef typename Notifier::ObserverBase Parent;
    85 
    86   public:
    8783
    8884    // \brief Constructor to attach the new map into the notifier.
    … …  
    9086    // It constructs a map and attachs it into the notifier.
    9187    // It adds all the items of the graph to the map.
    92     VectorMap(const GraphType& graph) {
     88    VectorMap(const Graph& graph) {
    9389      Parent::attach(graph.notifier(Item()));
    9490      container.resize(Parent::notifier()->maxId() + 1);
    … …  
    9995    // It constructs a map uses a given value to initialize the map.
    10096    // It adds all the items of the graph to the map.
    101     VectorMap(const GraphType& graph, const Value& value) {
     97    VectorMap(const Graph& graph, const Value& value) {
    10298      Parent::attach(graph.notifier(Item()));
    10399      container.resize(Parent::notifier()->maxId() + 1, value);

  • lemon/circulation.h

    r622 r611  
    2222#include <lemon/tolerance.h>
    2323#include <lemon/elevator.h>
    24 #include <limits>
    2524
    2625///\ingroup max_flow
    … …  
    121120
    122121     The exact formulation of this problem is the following.
    123      Let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$
    124      \f$upper: A\rightarrow\mathbf{R}\cup\{\infty\}\f$ denote the lower and
    125      upper bounds on the arcs, for which \f$lower(uv) \leq upper(uv)\f$
     122     Let \f$G=(V,A)\f$ be a digraph,
     123     \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and
     124     upper bounds on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$
    126125     holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
    127126     denotes the signed supply values of the nodes.
    … …  
    129128     supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
    130129     \f$-sup(u)\f$ demand.
    131      A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$
     130     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$
    132131     solution of the following problem.
    133132
    … …  
    152151     the direction of the arcs and taking the negative of the supply values
    153152     (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
    154 
    155      This algorithm either calculates a feasible circulation, or provides
    156      a \ref barrier() "barrier", which prooves that a feasible soultion
    157      cannot exist.
    158153
    159154     Note that this algorithm also provides a feasible solution for the
    … …  
    343338  private:
    344339
    345     bool checkBoundMaps() {
    346       for (ArcIt e(_g);e!=INVALID;++e) {
    347         if (_tol.less((*_up)[e], (*_lo)[e])) return false;
    348       }
    349       return true;
    350     }
    351 
    352340    void createStructures() {
    353341      _node_num = _el = countNodes(_g);
    … …  
    393381    /// Sets the upper bound (capacity) map.
    394382    /// \return <tt>(*this)</tt>
    395     Circulation& upperMap(const UpperMap& map) {
     383    Circulation& upperMap(const LowerMap& map) {
    396384      _up = &map;
    397385      return *this;
    … …  
    480468    void init()
    481469    {
    482       LEMON_DEBUG(checkBoundMaps(),
    483         "Upper bounds must be greater or equal to the lower bounds");
    484 
    485470      createStructures();
    486471
    … …  
    512497    void greedyInit()
    513498    {
    514       LEMON_DEBUG(checkBoundMaps(),
    515         "Upper bounds must be greater or equal to the lower bounds");
    516 
    517499      createStructures();
    518500
    … …  
    522504
    523505      for (ArcIt e(_g);e!=INVALID;++e) {
    524         if (!_tol.less(-(*_excess)[_g.target(e)], (*_up)[e])) {
     506        if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
    525507          _flow->set(e, (*_up)[e]);
    526508          (*_excess)[_g.target(e)] += (*_up)[e];
    527509          (*_excess)[_g.source(e)] -= (*_up)[e];
    528         } else if (_tol.less(-(*_excess)[_g.target(e)], (*_lo)[e])) {
     510        } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
    529511          _flow->set(e, (*_lo)[e]);
    530512          (*_excess)[_g.target(e)] += (*_lo)[e];
    … …  
    767749    {
    768750      Flow delta=0;
    769       Flow inf_cap = std::numeric_limits<Flow>::has_infinity ?
    770         std::numeric_limits<Flow>::infinity() :
    771         std::numeric_limits<Flow>::max();
    772751      for(NodeIt n(_g);n!=INVALID;++n)
    773752        if(barrier(n))
    … …  
    777756          Node s=_g.source(e);
    778757          Node t=_g.target(e);
    779           if(barrier(s)&&!barrier(t)) {
    780             if (_tol.less(inf_cap - (*_up)[e], delta)) return false;
    781             delta+=(*_up)[e];
    782           }
     758          if(barrier(s)&&!barrier(t)) delta+=(*_up)[e];
    783759          else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e];
    784760        }

  • lemon/concepts/graph_components.h

    r617 r584  
    181181    class BaseGraphComponent : public BaseDigraphComponent {
    182182    public:
    183 
    184       typedef BaseGraphComponent Graph;
    185 
    186183      typedef BaseDigraphComponent::Node Node;
    187184      typedef BaseDigraphComponent::Arc Arc;
    … …  
    193190      /// represented by two opposite directed arcs.
    194191      class Edge : public GraphItem<'e'> {
     192      public:
    195193        typedef GraphItem<'e'> Parent;
    196194
    197       public:
    198195        /// \brief Default constructor.
    199196        ///
    … …  
    995992    template <typename GR, typename K, typename V>
    996993    class GraphMap : public ReferenceMap<K, V, V&, const V&> {
    997       typedef ReferenceMap<K, V, V&, const V&> Parent;
    998 
    999     public:
    1000 
     994    public:
     995
     996      typedef ReadWriteMap<K, V> Parent;
     997
     998      /// The graph type of the map.
     999      typedef GR Graph;
    10011000      /// The key type of the map.
    10021001      typedef K Key;
    … …  
    10141013      ///
    10151014      /// Construct a new map for the graph.
    1016       explicit GraphMap(const GR&) {}
     1015      explicit GraphMap(const Graph&) {}
    10171016      /// \brief Construct a new map with default value.
    10181017      ///
    10191018      /// Construct a new map for the graph and initalize the values.
    1020       GraphMap(const GR&, const Value&) {}
     1019      GraphMap(const Graph&, const Value&) {}
    10211020
    10221021    private:
    … …  
    10591058
    10601059        const _Map &m;
    1061         const GR &g;
     1060        const Graph &g;
    10621061        const typename GraphMap::Value &t;
    10631062      };
    … …  
    10871086      template <typename V>
    10881087      class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> {
     1088      public:
    10891089        typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
    10901090
    1091       public:
    10921091        /// \brief Construct a new map.
    10931092        ///
    … …  
    11251124      template <typename V>
    11261125      class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> {
     1126      public:
    11271127        typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
    11281128
    1129       public:
    11301129        /// \brief Construct a new map.
    11311130        ///
    … …  
    12231222      template <typename V>
    12241223      class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> {
     1224      public:
    12251225        typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
    12261226
    1227       public:
    12281227        /// \brief Construct a new map.
    12291228        ///

  • lemon/core.h

    r617 r581  
    10371037  template <typename GR>
    10381038  class ConArcIt : public GR::Arc {
    1039     typedef typename GR::Arc Parent;
    1040 
    10411039  public:
    10421040
    1043     typedef typename GR::Arc Arc;
    1044     typedef typename GR::Node Node;
     1041    typedef GR Graph;
     1042    typedef typename Graph::Arc Parent;
     1043
     1044    typedef typename Graph::Arc Arc;
     1045    typedef typename Graph::Node Node;
    10451046
    10461047    /// \brief Constructor.
    … …  
    10481049    /// Construct a new ConArcIt iterating on the arcs that
    10491050    /// connects nodes \c u and \c v.
    1050     ConArcIt(const GR& g, Node u, Node v) : _graph(g) {
     1051    ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
    10511052      Parent::operator=(findArc(_graph, u, v));
    10521053    }
    … …  
    10551056    ///
    10561057    /// Construct a new ConArcIt that continues the iterating from arc \c a.
    1057     ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {}
     1058    ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
    10581059
    10591060    /// \brief Increment operator.
    … …  
    10661067    }
    10671068  private:
    1068     const GR& _graph;
     1069    const Graph& _graph;
    10691070  };
    10701071
    … …  
    11591160  template <typename GR>
    11601161  class ConEdgeIt : public GR::Edge {
    1161     typedef typename GR::Edge Parent;
    1162 
    11631162  public:
    11641163
    1165     typedef typename GR::Edge Edge;
    1166     typedef typename GR::Node Node;
     1164    typedef GR Graph;
     1165    typedef typename Graph::Edge Parent;
     1166
     1167    typedef typename Graph::Edge Edge;
     1168    typedef typename Graph::Node Node;
    11671169
    11681170    /// \brief Constructor.
    … …  
    11701172    /// Construct a new ConEdgeIt iterating on the edges that
    11711173    /// connects nodes \c u and \c v.
    1172     ConEdgeIt(const GR& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
     1174    ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
    11731175      Parent::operator=(findEdge(_graph, _u, _v));
    11741176    }
    … …  
    11771179    ///
    11781180    /// Construct a new ConEdgeIt that continues iterating from edge \c e.
    1179     ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {}
     1181    ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
    11801182
    11811183    /// \brief Increment operator.
    … …  
    11871189    }
    11881190  private:
    1189     const GR& _graph;
     1191    const Graph& _graph;
    11901192    Node _u, _v;
    11911193  };
    … …  
    12181220    : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
    12191221  {
     1222  public:
    12201223    typedef typename ItemSetTraits<GR, typename GR::Arc>
    12211224    ::ItemNotifier::ObserverBase Parent;
    12221225
    12231226    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    1224 
    1225   public:
    1226 
    1227     /// The Digraph type
    12281227    typedef GR Digraph;
    12291228
    … …  
    12311230
    12321231    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
     1232    public:
     1233
    12331234      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
    1234 
    1235     public:
    12361235
    12371236      AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
    … …  
    12581257      }
    12591258    };
     1259
     1260    const Digraph &_g;
     1261    AutoNodeMap _head;
     1262    typename Digraph::template ArcMap<Arc> _parent;
     1263    typename Digraph::template ArcMap<Arc> _left;
     1264    typename Digraph::template ArcMap<Arc> _right;
    12601265
    12611266    class ArcLess {
    … …  
    12681273      }
    12691274    };
    1270 
    1271   protected:
    1272 
    1273     const Digraph &_g;
    1274     AutoNodeMap _head;
    1275     typename Digraph::template ArcMap<Arc> _parent;
    1276     typename Digraph::template ArcMap<Arc> _left;
    1277     typename Digraph::template ArcMap<Arc> _right;
    12781275
    12791276  public:
    … …  
    16341631  class ArcLookUp
    16351632  {
     1633  public:
    16361634    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    1637 
    1638   public:
    1639 
    1640     /// The Digraph type
    16411635    typedef GR Digraph;
    16421636
    … …  
    17531747
    17541748    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    1755 
    1756     typename GR::template ArcMap<Arc> _next;
     1749    typedef GR Digraph;
     1750
     1751    typename Digraph::template ArcMap<Arc> _next;
    17571752
    17581753    Arc refreshNext(Arc head,Arc next=INVALID)
    … …  
    17731768
    17741769  public:
    1775 
    1776     /// The Digraph type
    1777     typedef GR Digraph;
    1778 
    17791770    ///Constructor
    17801771

  • lemon/edge_set.h

    r617 r559  
    3434  public:
    3535
     36    typedef GR Graph;
    3637    typedef typename GR::Node Node;
    3738    typedef typename GR::NodeIt NodeIt;
    … …  
    208209    template <typename V>
    209210    class NodeMap : public GR::template NodeMap<V> {
     211    public:
     212
    210213      typedef typename GR::template NodeMap<V> Parent;
    211 
    212     public:
    213214
    214215      explicit NodeMap(const ListArcSetBase<GR>& arcset)
    … …  
    259260  template <typename GR>
    260261  class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
     262
     263  public:
     264
    261265    typedef ArcSetExtender<ListArcSetBase<GR> > Parent;
    262 
    263   public:
    264266
    265267    typedef typename Parent::Node Node;
    266268    typedef typename Parent::Arc Arc;
     269
     270    typedef GR Graph;
     271
    267272
    268273    typedef typename Parent::NodesImplBase NodesImplBase;
    … …  
    288293
    289294    class NodesImpl : public NodesImplBase {
     295    public:
    290296      typedef NodesImplBase Parent;
    291297
    292     public:
    293298      NodesImpl(const GR& graph, ListArcSet& arcset)
    294299        : Parent(graph), _arcset(arcset) {}
    … …  
    350355  public:
    351356
     357    typedef GR Graph;
    352358    typedef typename GR::Node Node;
    353359    typedef typename GR::NodeIt NodeIt;
    … …  
    632638    template <typename V>
    633639    class NodeMap : public GR::template NodeMap<V> {
     640    public:
     641
    634642      typedef typename GR::template NodeMap<V> Parent;
    635 
    636     public:
    637643
    638644      explicit NodeMap(const ListEdgeSetBase<GR>& arcset)
    … …  
    683689  template <typename GR>
    684690  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
     691
     692  public:
     693
    685694    typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;
    686 
    687   public:
    688695
    689696    typedef typename Parent::Node Node;
    690697    typedef typename Parent::Arc Arc;
    691698    typedef typename Parent::Edge Edge;
     699
     700    typedef GR Graph;
     701
    692702
    693703    typedef typename Parent::NodesImplBase NodesImplBase;
    … …  
    708718
    709719    class NodesImpl : public NodesImplBase {
     720    public:
    710721      typedef NodesImplBase Parent;
    711722
    712     public:
    713723      NodesImpl(const GR& graph, ListEdgeSet& arcset)
    714724        : Parent(graph), _arcset(arcset) {}
    … …  
    770780  public:
    771781
    772     typedef typename GR::Node Node;
    773     typedef typename GR::NodeIt NodeIt;
     782    typedef GR Graph;
     783    typedef typename Graph::Node Node;
     784    typedef typename Graph::NodeIt NodeIt;
    774785
    775786  protected:
    … …  
    890901    template <typename V>
    891902    class NodeMap : public GR::template NodeMap<V> {
     903    public:
     904
    892905      typedef typename GR::template NodeMap<V> Parent;
    893 
    894     public:
    895906
    896907      explicit NodeMap(const SmartArcSetBase<GR>& arcset)
    … …  
    946957  template <typename GR>
    947958  class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
     959
     960  public:
     961
    948962    typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;
    949 
    950   public:
    951963
    952964    typedef typename Parent::Node Node;
    953965    typedef typename Parent::Arc Arc;
     966
     967    typedef GR Graph;
    954968
    955969  protected:
    … …  
    970984
    971985    class NodesImpl : public NodesImplBase {
     986    public:
    972987      typedef NodesImplBase Parent;
    973988
    974     public:
    975989      NodesImpl(const GR& graph, SmartArcSet& arcset)
    976990        : Parent(graph), _arcset(arcset) {}
    … …  
    10491063  public:
    10501064
     1065    typedef GR Graph;
    10511066    typedef typename GR::Node Node;
    10521067    typedef typename GR::NodeIt NodeIt;
    … …  
    12351250    template <typename V>
    12361251    class NodeMap : public GR::template NodeMap<V> {
     1252    public:
     1253
    12371254      typedef typename GR::template NodeMap<V> Parent;
    1238 
    1239     public:
    12401255
    12411256      explicit NodeMap(const SmartEdgeSetBase<GR>& arcset)
    … …  
    12901305  template <typename GR>
    12911306  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
     1307
     1308  public:
     1309
    12921310    typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;
    1293 
    1294   public:
    12951311
    12961312    typedef typename Parent::Node Node;
    … …  
    12981314    typedef typename Parent::Edge Edge;
    12991315
     1316    typedef GR Graph;
     1317
    13001318  protected:
    13011319
    … …  
    13141332
    13151333    class NodesImpl : public NodesImplBase {
     1334    public:
    13161335      typedef NodesImplBase Parent;
    13171336
    1318     public:
    13191337      NodesImpl(const GR& graph, SmartEdgeSet& arcset)
    13201338        : Parent(graph), _arcset(arcset) {}

  • lemon/full_graph.h

    r617 r582  
    3232  public:
    3333
    34     typedef FullDigraphBase Digraph;
     34    typedef FullDigraphBase Graph;
    3535
    3636    class Node;
    … …  
    170170  /// \sa FullGraph
    171171  class FullDigraph : public ExtendedFullDigraphBase {
     172  public:
     173
    172174    typedef ExtendedFullDigraphBase Parent;
    173 
    174   public:
    175175
    176176    /// \brief Constructor
    … …  
    227227
    228228  class FullGraphBase {
     229    int _node_num;
     230    int _edge_num;
    229231  public:
    230232
    … …  
    236238
    237239  protected:
    238 
    239     int _node_num;
    240     int _edge_num;
    241240
    242241    FullGraphBase() {}
    … …  
    539538  /// \sa FullDigraph
    540539  class FullGraph : public ExtendedFullGraphBase {
     540  public:
     541
    541542    typedef ExtendedFullGraphBase Parent;
    542 
    543   public:
    544543
    545544    /// \brief Constructor

  • lemon/graph_to_eps.h

    r617 r584  
    7070{
    7171  typedef GR Graph;
    72   typedef GR Digraph;
    7372  typedef typename Graph::Node Node;
    7473  typedef typename Graph::NodeIt NodeIt;
    … …  
    243242
    244243  typedef typename T::Graph Graph;
    245   typedef typename T::Digraph Digraph;
    246244  typedef typename Graph::Node Node;
    247245  typedef typename Graph::NodeIt NodeIt;

  • lemon/grid_graph.h

    r617 r582  
    500500  /// "Graph concept".
    501501  class GridGraph : public ExtendedGridGraphBase {
     502  public:
     503
    502504    typedef ExtendedGridGraphBase Parent;
    503 
    504   public:
    505505
    506506    /// \brief Map to get the indices of the nodes as dim2::Point<int>.

  • lemon/hypercube_graph.h

    r617 r582  
    295295  /// "Graph concept".
    296296  class HypercubeGraph : public ExtendedHypercubeGraphBase {
     297  public:
     298
    297299    typedef ExtendedHypercubeGraphBase Parent;
    298 
    299   public:
    300300
    301301    /// \brief Constructs a hypercube graph with \c dim dimensions.

  • lemon/list_graph.h

    r617 r582  
    324324
    325325  class ListDigraph : public ExtendedListDigraphBase {
    326     typedef ExtendedListDigraphBase Parent;
    327 
    328326  private:
    329327    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
    … …  
    339337    void operator=(const ListDigraph &) {}
    340338  public:
     339
     340    typedef ExtendedListDigraphBase Parent;
    341341
    342342    /// Constructor
    … …  
    794794  public:
    795795
    796     typedef ListGraphBase Graph;
     796    typedef ListGraphBase Digraph;
    797797
    798798    class Node;
    … …  
    11771177
    11781178  class ListGraph : public ExtendedListGraphBase {
    1179     typedef ExtendedListGraphBase Parent;
    1180 
    11811179  private:
    11821180    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
    … …  
    11971195    ///
    11981196    ListGraph() {}
     1197
     1198    typedef ExtendedListGraphBase Parent;
    11991199
    12001200    typedef Parent::OutArcIt IncEdgeIt;

  • lemon/maps.h

    r617 r584  
    18391839    /// The graph type of IdMap.
    18401840    typedef GR Graph;
    1841     typedef GR Digraph;
    18421841    /// The key type of IdMap (\c Node, \c Arc or \c Edge).
    18431842    typedef K Item;
    … …  
    19311930    /// The graph type of CrossRefMap.
    19321931    typedef GR Graph;
    1933     typedef GR Digraph;
    19341932    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
    19351933    typedef K Item;
    … …  
    21352133    /// The graph type of RangeIdMap.
    21362134    typedef GR Graph;
    2137     typedef GR Digraph;
    21382135    /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge).
    21392136    typedef K Item;
    … …  
    24982495  public:
    24992496   
    2500     /// The graph type of InDegMap
    2501     typedef GR Graph;
     2497    /// The digraph type
    25022498    typedef GR Digraph;
    25032499    /// The key type
    … …  
    26282624  public:
    26292625
    2630     /// The graph type of OutDegMap
    2631     typedef GR Graph;
     2626    /// The digraph type
    26322627    typedef GR Digraph;
    26332628    /// The key type

  • lemon/network_simplex.h

    r618 r609  
    382382        const int MIN_BLOCK_SIZE = 10;
    383383
    384         _block_size = std::max( int(BLOCK_SIZE_FACTOR *
    385                                     std::sqrt(double(_arc_num))),
     384        _block_size = std::max( int(BLOCK_SIZE_FACTOR * sqrt(_arc_num)),
    386385                                MIN_BLOCK_SIZE );
    387386      }
    … …  
    459458        const int MIN_MINOR_LIMIT = 3;
    460459
    461         _list_length = std::max( int(LIST_LENGTH_FACTOR *
    462                                      std::sqrt(double(_arc_num))),
     460        _list_length = std::max( int(LIST_LENGTH_FACTOR * sqrt(_arc_num)),
    463461                                 MIN_LIST_LENGTH );
    464462        _minor_limit = std::max( int(MINOR_LIMIT_FACTOR * _list_length),
    … …  
    580578        const int MIN_HEAD_LENGTH = 3;
    581579
    582         _block_size = std::max( int(BLOCK_SIZE_FACTOR *
    583                                     std::sqrt(double(_arc_num))),
     580        _block_size = std::max( int(BLOCK_SIZE_FACTOR * sqrt(_arc_num)),
    584581                                MIN_BLOCK_SIZE );
    585582        _head_length = std::max( int(HEAD_LENGTH_FACTOR * _block_size),
    … …  
    11481145      // Run Circulation to check if a feasible solution exists
    11491146      typedef ConstMap<Arc, Flow> ConstArcMap;
    1150       ConstArcMap zero_arc_map(0), inf_arc_map(inf_cap);
    11511147      FlowNodeMap *csup = NULL;
    11521148      bool local_csup = false;
    … …  
    11691165          } else {
    11701166            Circulation<GR, FlowArcMap, ConstArcMap, FlowNodeMap>
    1171               circ(_graph, *_plower, inf_arc_map, *csup);
     1167              circ(_graph, *_plower, ConstArcMap(inf_cap), *csup);
    11721168            circ_result = circ.run();
    11731169          }
    … …  
    11751171          if (_pupper) {
    11761172            Circulation<GR, ConstArcMap, FlowArcMap, FlowNodeMap>
    1177               circ(_graph, zero_arc_map, *_pupper, *csup);
     1173              circ(_graph, ConstArcMap(0), *_pupper, *csup);
    11781174            circ_result = circ.run();
    11791175          } else {
    11801176            Circulation<GR, ConstArcMap, ConstArcMap, FlowNodeMap>
    1181               circ(_graph, zero_arc_map, inf_arc_map, *csup);
     1177              circ(_graph, ConstArcMap(0), ConstArcMap(inf_cap), *csup);
    11821178            circ_result = circ.run();
    11831179          }
    … …  
    11961192          } else {
    11971193            Circulation<RevGraph, FlowArcMap, ConstArcMap, NegNodeMap>
    1198               circ(rgraph, *_plower, inf_arc_map, neg_csup);
     1194              circ(rgraph, *_plower, ConstArcMap(inf_cap), neg_csup);
    11991195            circ_result = circ.run();
    12001196          }
    … …  
    12021198          if (_pupper) {
    12031199            Circulation<RevGraph, ConstArcMap, FlowArcMap, NegNodeMap>
    1204               circ(rgraph, zero_arc_map, *_pupper, neg_csup);
     1200              circ(rgraph, ConstArcMap(0), *_pupper, neg_csup);
    12051201            circ_result = circ.run();
    12061202          } else {
    12071203            Circulation<RevGraph, ConstArcMap, ConstArcMap, NegNodeMap>
    1208               circ(rgraph, zero_arc_map, inf_arc_map, neg_csup);
     1204              circ(rgraph, ConstArcMap(0), ConstArcMap(inf_cap), neg_csup);
    12091205            circ_result = circ.run();
    12101206          }
    … …  
    12301226
    12311227      // Store the arcs in a mixed order
    1232       int k = std::max(int(std::sqrt(double(_arc_num))), 10);
     1228      int k = std::max(int(sqrt(_arc_num)), 10);
    12331229      int i = 0;
    12341230      for (ArcIt e(_graph); e != INVALID; ++e) {

  • lemon/smart_graph.h

    r617 r582  
    5656  public:
    5757
    58     typedef SmartDigraphBase Digraph;
     58    typedef SmartDigraphBase Graph;
    5959
    6060    class Node;
    … …  
    196196  ///\sa concepts::Digraph.
    197197  class SmartDigraph : public ExtendedSmartDigraphBase {
     198  public:
     199
    198200    typedef ExtendedSmartDigraphBase Parent;
    199201
    … …  
    419421  public:
    420422
    421     typedef SmartGraphBase Graph;
     423    typedef SmartGraphBase Digraph;
    422424
    423425    class Node;
    … …  
    630632  /// \sa concepts::Graph.
    631633  class SmartGraph : public ExtendedSmartGraphBase {
    632     typedef ExtendedSmartGraphBase Parent;
    633 
    634634  private:
    635635
    … …  
    648648
    649649  public:
     650
     651    typedef ExtendedSmartGraphBase Parent;
    650652
    651653    /// Constructor

  • lemon/suurballe.h

    r623 r584  
    2626
    2727#include <vector>
    28 #include <limits>
    2928#include <lemon/bin_heap.h>
    3029#include <lemon/path.h>
    … …  
    4443  /// from a given source node to a given target node in a digraph.
    4544  ///
    46   /// Note that this problem is a special case of the \ref min_cost_flow
    47   /// "minimum cost flow problem". This implementation is actually an
    48   /// efficient specialized version of the \ref CapacityScaling
    49   /// "Successive Shortest Path" algorithm directly for this problem.
    50   /// Therefore this class provides query functions for flow values and
    51   /// node potentials (the dual solution) just like the minimum cost flow
    52   /// algorithms.
     45  /// In fact, this implementation is the specialization of the
     46  /// \ref CapacityScaling "successive shortest path" algorithm.
    5347  ///
    5448  /// \tparam GR The digraph type the algorithm runs on.
    55   /// \tparam LEN The type of the length map.
    56   /// The default value is <tt>GR::ArcMap<int></tt>.
     49  /// The default value is \c ListDigraph.
     50  /// \tparam LEN The type of the length (cost) map.
     51  /// The default value is <tt>Digraph::ArcMap<int></tt>.
    5752  ///
    5853  /// \warning Length values should be \e non-negative \e integers.
    5954  ///
    6055  /// \note For finding node-disjoint paths this algorithm can be used
    61   /// along with the \ref SplitNodes adaptor.
     56  /// with \ref SplitNodes.
    6257#ifdef DOXYGEN
    6358  template <typename GR, typename LEN>
    6459#else
    65   template < typename GR,
     60  template < typename GR = ListDigraph,
    6661             typename LEN = typename GR::template ArcMap<int> >
    6762#endif
    … …  
    8176    /// The type of the lengths.
    8277    typedef typename LengthMap::Value Length;
    83 #ifdef DOXYGEN
    84     /// The type of the flow map.
    85     typedef GR::ArcMap<int> FlowMap;
    86     /// The type of the potential map.
    87     typedef GR::NodeMap<Length> PotentialMap;
    88 #else
    8978    /// The type of the flow map.
    9079    typedef typename Digraph::template ArcMap<int> FlowMap;
    9180    /// The type of the potential map.
    9281    typedef typename Digraph::template NodeMap<Length> PotentialMap;
    93 #endif
    94 
    9582    /// The type of the path structures.
    96     typedef SimplePath<GR> Path;
     83    typedef SimplePath<Digraph> Path;
    9784
    9885  private:
    9986
    100     // ResidualDijkstra is a special implementation of the
    101     // Dijkstra algorithm for finding shortest paths in the
    102     // residual network with respect to the reduced arc lengths
    103     // and modifying the node potentials according to the
    104     // distance of the nodes.
     87    /// \brief Special implementation of the Dijkstra algorithm
     88    /// for finding shortest paths in the residual network.
     89    ///
     90    /// \ref ResidualDijkstra is a special implementation of the
     91    /// \ref Dijkstra algorithm for finding shortest paths in the
     92    /// residual network of the digraph with respect to the reduced arc
     93    /// lengths and modifying the node potentials according to the
     94    /// distance of the nodes.
    10595    class ResidualDijkstra
    10696    {
    … …  
    131121
    132122      /// Constructor.
    133       ResidualDijkstra( const Digraph &graph,
     123      ResidualDijkstra( const Digraph &digraph,
    134124                        const FlowMap &flow,
    135125                        const LengthMap &length,
    … …  
    137127                        PredMap &pred,
    138128                        Node s, Node t ) :
    139         _graph(graph), _flow(flow), _length(length), _potential(potential),
    140         _dist(graph), _pred(pred), _s(s), _t(t) {}
     129        _graph(digraph), _flow(flow), _length(length), _potential(potential),
     130        _dist(digraph), _pred(pred), _s(s), _t(t) {}
    141131
    142132      /// \brief Run the algorithm. It returns \c true if a path is found
    … …  
    247237    /// Constructor.
    248238    ///
    249     /// \param graph The digraph the algorithm runs on.
     239    /// \param digraph The digraph the algorithm runs on.
    250240    /// \param length The length (cost) values of the arcs.
    251     Suurballe( const Digraph &graph,
    252                const LengthMap &length ) :
    253       _graph(graph), _length(length), _flow(0), _local_flow(false),
    254       _potential(0), _local_potential(false), _pred(graph)
    255     {
    256       LEMON_ASSERT(std::numeric_limits<Length>::is_integer,
    257         "The length type of Suurballe must be integer");
    258     }
     241    /// \param s The source node.
     242    /// \param t The target node.
     243    Suurballe( const Digraph &digraph,
     244               const LengthMap &length,
     245               Node s, Node t ) :
     246      _graph(digraph), _length(length), _flow(0), _local_flow(false),
     247      _potential(0), _local_potential(false), _source(s), _target(t),
     248      _pred(digraph) {}
    259249
    260250    /// Destructor.
    … …  
    268258    ///
    269259    /// This function sets the flow map.
    270     /// If it is not used before calling \ref run() or \ref init(),
    271     /// an instance will be allocated automatically. The destructor
    272     /// deallocates this automatically allocated map, of course.
    273     ///
    274     /// The found flow contains only 0 and 1 values, since it is the
    275     /// union of the found arc-disjoint paths.
     260    ///
     261    /// The found flow contains only 0 and 1 values. It is the union of
     262    /// the found arc-disjoint paths.
    276263    ///
    277264    /// \return <tt>(*this)</tt>
    … …  
    288275    ///
    289276    /// This function sets the potential map.
    290     /// If it is not used before calling \ref run() or \ref init(),
    291     /// an instance will be allocated automatically. The destructor
    292     /// deallocates this automatically allocated map, of course.
    293     ///
    294     /// The node potentials provide the dual solution of the underlying
    295     /// \ref min_cost_flow "minimum cost flow problem".
     277    ///
     278    /// The potentials provide the dual solution of the underlying
     279    /// minimum cost flow problem.
    296280    ///
    297281    /// \return <tt>(*this)</tt>
    … …  
    318302    /// This function runs the algorithm.
    319303    ///
    320     /// \param s The source node.
    321     /// \param t The target node.
    322304    /// \param k The number of paths to be found.
    323305    ///
    … …  
    326308    /// arc-disjoint paths found.
    327309    ///
    328     /// \note Apart from the return value, <tt>s.run(s, t, k)</tt> is
    329     /// just a shortcut of the following code.
     310    /// \note Apart from the return value, <tt>s.run(k)</tt> is just a
     311    /// shortcut of the following code.
    330312    /// \code
    331     ///   s.init(s);
    332     ///   s.findFlow(t, k);
     313    ///   s.init();
     314    ///   s.findFlow(k);
    333315    ///   s.findPaths();
    334316    /// \endcode
    335     int run(const Node& s, const Node& t, int k = 2) {
    336       init(s);
    337       findFlow(t, k);
     317    int run(int k = 2) {
     318      init();
     319      findFlow(k);
    338320      findPaths();
    339321      return _path_num;
    … …  
    343325    ///
    344326    /// This function initializes the algorithm.
    345     ///
    346     /// \param s The source node.
    347     void init(const Node& s) {
    348       _source = s;
    349 
     327    void init() {
    350328      // Initialize maps
    351329      if (!_flow) {
    … …  
    359337      for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
    360338      for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
    361     }
    362 
    363     /// \brief Execute the algorithm to find an optimal flow.
     339
     340      _dijkstra = new ResidualDijkstra( _graph, *_flow, _length,
     341                                        *_potential, _pred,
     342                                        _source, _target );
     343    }
     344
     345    /// \brief Execute the successive shortest path algorithm to find
     346    /// an optimal flow.
    364347    ///
    365348    /// This function executes the successive shortest path algorithm to
    366     /// find a minimum cost flow, which is the union of \c k (or less)
     349    /// find a minimum cost flow, which is the union of \c k or less
    367350    /// arc-disjoint paths.
    368351    ///
    369     /// \param t The target node.
    370     /// \param k The number of paths to be found.
    371     ///
    372352    /// \return \c k if there are at least \c k arc-disjoint paths from
    373     /// the source node to the given node \c t in the digraph.
    374     /// Otherwise it returns the number of arc-disjoint paths found.
     353    /// \c s to \c t in the digraph. Otherwise it returns the number of
     354    /// arc-disjoint paths found.
    375355    ///
    376356    /// \pre \ref init() must be called before using this function.
    377     int findFlow(const Node& t, int k = 2) {
    378       _target = t;
    379       _dijkstra =
    380         new ResidualDijkstra( _graph, *_flow, _length, *_potential, _pred,
    381                               _source, _target );
    382 
     357    int findFlow(int k = 2) {
    383358      // Find shortest paths
    384359      _path_num = 0;
    … …  
    406381    /// \brief Compute the paths from the flow.
    407382    ///
    408     /// This function computes the paths from the found minimum cost flow,
    409     /// which is the union of some arc-disjoint paths.
     383    /// This function computes the paths from the flow.
    410384    ///
    411385    /// \pre \ref init() and \ref findFlow() must be called before using
    412386    /// this function.
    413387    void findPaths() {
     388      // Create the residual flow map (the union of the paths not found
     389      // so far)
    414390      FlowMap res_flow(_graph);
    415391      for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];
    … …  
    438414    /// @{
    439415
    440     /// \brief Return the total length of the found paths.
    441     ///
    442     /// This function returns the total length of the found paths, i.e.
    443     /// the total cost of the found flow.
    444     /// The complexity of the function is O(e).
     416    /// \brief Return a const reference to the arc map storing the
     417    /// found flow.
     418    ///
     419    /// This function returns a const reference to the arc map storing
     420    /// the flow that is the union of the found arc-disjoint paths.
     421    ///
     422    /// \pre \ref run() or \ref findFlow() must be called before using
     423    /// this function.
     424    const FlowMap& flowMap() const {
     425      return *_flow;
     426    }
     427
     428    /// \brief Return a const reference to the node map storing the
     429    /// found potentials (the dual solution).
     430    ///
     431    /// This function returns a const reference to the node map storing
     432    /// the found potentials that provide the dual solution of the
     433    /// underlying minimum cost flow problem.
     434    ///
     435    /// \pre \ref run() or \ref findFlow() must be called before using
     436    /// this function.
     437    const PotentialMap& potentialMap() const {
     438      return *_potential;
     439    }
     440
     441    /// \brief Return the flow on the given arc.
     442    ///
     443    /// This function returns the flow on the given arc.
     444    /// It is \c 1 if the arc is involved in one of the found paths,
     445    /// otherwise it is \c 0.
     446    ///
     447    /// \pre \ref run() or \ref findFlow() must be called before using
     448    /// this function.
     449    int flow(const Arc& arc) const {
     450      return (*_flow)[arc];
     451    }
     452
     453    /// \brief Return the potential of the given node.
     454    ///
     455    /// This function returns the potential of the given node.
     456    ///
     457    /// \pre \ref run() or \ref findFlow() must be called before using
     458    /// this function.
     459    Length potential(const Node& node) const {
     460      return (*_potential)[node];
     461    }
     462
     463    /// \brief Return the total length (cost) of the found paths (flow).
     464    ///
     465    /// This function returns the total length (cost) of the found paths
     466    /// (flow). The complexity of the function is O(e).
    445467    ///
    446468    /// \pre \ref run() or \ref findFlow() must be called before using
    … …  
    453475    }
    454476
    455     /// \brief Return the flow value on the given arc.
    456     ///
    457     /// This function returns the flow value on the given arc.
    458     /// It is \c 1 if the arc is involved in one of the found arc-disjoint
    459     /// paths, otherwise it is \c 0.
    460     ///
    461     /// \pre \ref run() or \ref findFlow() must be called before using
    462     /// this function.
    463     int flow(const Arc& arc) const {
    464       return (*_flow)[arc];
    465     }
    466 
    467     /// \brief Return a const reference to an arc map storing the
    468     /// found flow.
    469     ///
    470     /// This function returns a const reference to an arc map storing
    471     /// the flow that is the union of the found arc-disjoint paths.
    472     ///
    473     /// \pre \ref run() or \ref findFlow() must be called before using
    474     /// this function.
    475     const FlowMap& flowMap() const {
    476       return *_flow;
    477     }
    478 
    479     /// \brief Return the potential of the given node.
    480     ///
    481     /// This function returns the potential of the given node.
    482     /// The node potentials provide the dual solution of the
    483     /// underlying \ref min_cost_flow "minimum cost flow problem".
    484     ///
    485     /// \pre \ref run() or \ref findFlow() must be called before using
    486     /// this function.
    487     Length potential(const Node& node) const {
    488       return (*_potential)[node];
    489     }
    490 
    491     /// \brief Return a const reference to a node map storing the
    492     /// found potentials (the dual solution).
    493     ///
    494     /// This function returns a const reference to a node map storing
    495     /// the found potentials that provide the dual solution of the
    496     /// underlying \ref min_cost_flow "minimum cost flow problem".
    497     ///
    498     /// \pre \ref run() or \ref findFlow() must be called before using
    499     /// this function.
    500     const PotentialMap& potentialMap() const {
    501       return *_potential;
    502     }
    503 
    504477    /// \brief Return the number of the found paths.
    505478    ///
    … …  
    516489    /// This function returns a const reference to the specified path.
    517490    ///
    518     /// \param i The function returns the <tt>i</tt>-th path.
     491    /// \param i The function returns the \c i-th path.
    519492    /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.
    520493    ///

  • test/min_cost_flow_test.cc

    r615 r609  
    234234    typedef int Flow;
    235235    typedef int Cost;
    236     typedef concepts::Digraph GR;
     236    // TODO: This typedef should be enabled if the standard maps are
     237    // reference maps in the graph concepts (See #190).
     238/**/
     239    //typedef concepts::Digraph GR;
     240    typedef ListDigraph GR;
     241/**/
    237242    checkConcept< McfClassConcept<GR, Flow, Cost>,
    238243                  NetworkSimplex<GR, Flow, Cost> >();

  • test/suurballe_test.cc

    r623 r440  
    2323#include <lemon/path.h>
    2424#include <lemon/suurballe.h>
    25 #include <lemon/concepts/digraph.h>
    2625
    2726#include "test_tools.h"
    … …  
    3130char test_lgf[] =
    3231  "@nodes\n"
    33   "label\n"
    34   "1\n"
    35   "2\n"
    36   "3\n"
    37   "4\n"
    38   "5\n"
    39   "6\n"
    40   "7\n"
    41   "8\n"
    42   "9\n"
    43   "10\n"
    44   "11\n"
    45   "12\n"
     32  "label supply1 supply2 supply3\n"
     33  "1     0        20      27\n"
     34  "2     0       -4        0\n"
     35  "3     0        0        0\n"
     36  "4     0        0        0\n"
     37  "5     0        9        0\n"
     38  "6     0       -6        0\n"
     39  "7     0        0        0\n"
     40  "8     0        0        0\n"
     41  "9     0        3        0\n"
     42  "10    0       -2        0\n"
     43  "11    0        0        0\n"
     44  "12    0       -20     -27\n"
    4645  "@arcs\n"
    47   "      length\n"
    48   " 1  2  70\n"
    49   " 1  3 150\n"
    50   " 1  4  80\n"
    51   " 2  8  80\n"
    52   " 3  5 140\n"
    53   " 4  6  60\n"
    54   " 4  7  80\n"
    55   " 4  8 110\n"
    56   " 5  7  60\n"
    57   " 5 11 120\n"
    58   " 6  3   0\n"
    59   " 6  9 140\n"
    60   " 6 10  90\n"
    61   " 7  1  30\n"
    62   " 8 12  60\n"
    63   " 9 12  50\n"
    64   "10 12  70\n"
    65   "10  2 100\n"
    66   "10  7  60\n"
    67   "11 10  20\n"
    68   "12 11  30\n"
     46  "      cost capacity lower1 lower2\n"
     47  " 1  2  70  11       0      8\n"
     48  " 1  3 150   3       0      1\n"
     49  " 1  4  80  15       0      2\n"
     50  " 2  8  80  12       0      0\n"
     51  " 3  5 140   5       0      3\n"
     52  " 4  6  60  10       0      1\n"
     53  " 4  7  80   2       0      0\n"
     54  " 4  8 110   3       0      0\n"
     55  " 5  7  60  14       0      0\n"
     56  " 5 11 120  12       0      0\n"
     57  " 6  3   0   3       0      0\n"
     58  " 6  9 140   4       0      0\n"
     59  " 6 10  90   8       0      0\n"
     60  " 7  1  30   5       0      0\n"
     61  " 8 12  60  16       0      4\n"
     62  " 9 12  50   6       0      0\n"
     63  "10 12  70  13       0      5\n"
     64  "10  2 100   7       0      0\n"
     65  "10  7  60  10       0      0\n"
     66  "11 10  20  14       0      6\n"
     67  "12 11  30  10       0      0\n"
    6968  "@attributes\n"
    7069  "source  1\n"
    7170  "target 12\n"
    7271  "@end\n";
    73 
    74 // Check the interface of Suurballe
    75 void checkSuurballeCompile()
    76 {
    77   typedef int VType;
    78   typedef concepts::Digraph Digraph;
    79 
    80   typedef Digraph::Node Node;
    81   typedef Digraph::Arc Arc;
    82   typedef concepts::ReadMap<Arc, VType> LengthMap;
    83  
    84   typedef Suurballe<Digraph, LengthMap> SuurballeType;
    85 
    86   Digraph g;
    87   Node n;
    88   Arc e;
    89   LengthMap len;
    90   SuurballeType::FlowMap flow(g);
    91   SuurballeType::PotentialMap pi(g);
    92 
    93   SuurballeType suurb_test(g, len);
    94   const SuurballeType& const_suurb_test = suurb_test;
    95 
    96   suurb_test
    97     .flowMap(flow)
    98     .potentialMap(pi);
    99 
    100   int k;
    101   k = suurb_test.run(n, n);
    102   k = suurb_test.run(n, n, k);
    103   suurb_test.init(n);
    104   k = suurb_test.findFlow(n);
    105   k = suurb_test.findFlow(n, k);
    106   suurb_test.findPaths();
    107  
    108   int f;
    109   VType c;
    110   c = const_suurb_test.totalLength();
    111   f = const_suurb_test.flow(e);
    112   const SuurballeType::FlowMap& fm =
    113     const_suurb_test.flowMap();
    114   c = const_suurb_test.potential(n);
    115   const SuurballeType::PotentialMap& pm =
    116     const_suurb_test.potentialMap();
    117   k = const_suurb_test.pathNum();
    118   Path<Digraph> p = const_suurb_test.path(k);
    119  
    120   ignore_unused_variable_warning(fm);
    121   ignore_unused_variable_warning(pm);
    122 }
    12372
    12473// Check the feasibility of the flow
    … …  
    170119                typename Digraph::Node s, typename Digraph::Node t)
    171120{
     121  // Check the "Complementary Slackness" optimality condition
    172122  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    173123  Node n = s;
    … …  
    187137  ListDigraph digraph;
    188138  ListDigraph::ArcMap<int> length(digraph);
    189   Node s, t;
     139  Node source, target;
    190140
    191141  std::istringstream input(test_lgf);
    192142  DigraphReader<ListDigraph>(digraph, input).
    193     arcMap("length", length).
    194     node("source", s).
    195     node("target", t).
     143    arcMap("cost", length).
     144    node("source", source).
     145    node("target", target).
    196146    run();
    197147
    198148  // Find 2 paths
    199149  {
    200     Suurballe<ListDigraph> suurballe(digraph, length);
    201     check(suurballe.run(s, t) == 2, "Wrong number of paths");
    202     check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
     150    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
     151    check(suurballe.run(2) == 2, "Wrong number of paths");
     152    check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),
    203153          "The flow is not feasible");
    204154    check(suurballe.totalLength() == 510, "The flow is not optimal");
    … …  
    207157          "Wrong potentials");
    208158    for (int i = 0; i < suurballe.pathNum(); ++i)
    209       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
     159      check(checkPath(digraph, suurballe.path(i), source, target),
     160            "Wrong path");
    210161  }
    211162
    212163  // Find 3 paths
    213164  {
    214     Suurballe<ListDigraph> suurballe(digraph, length);
    215     check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
    216     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
     165    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
     166    check(suurballe.run(3) == 3, "Wrong number of paths");
     167    check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
    217168          "The flow is not feasible");
    218169    check(suurballe.totalLength() == 1040, "The flow is not optimal");
    … …  
    221172          "Wrong potentials");
    222173    for (int i = 0; i < suurballe.pathNum(); ++i)
    223       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
     174      check(checkPath(digraph, suurballe.path(i), source, target),
     175            "Wrong path");
    224176  }
    225177
    226178  // Find 5 paths (only 3 can be found)
    227179  {
    228     Suurballe<ListDigraph> suurballe(digraph, length);
    229     check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
    230     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
     180    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
     181    check(suurballe.run(5) == 3, "Wrong number of paths");
     182    check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
    231183          "The flow is not feasible");
    232184    check(suurballe.totalLength() == 1040, "The flow is not optimal");
    … …  
    235187          "Wrong potentials");
    236188    for (int i = 0; i < suurballe.pathNum(); ++i)
    237       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
     189      check(checkPath(digraph, suurballe.path(i), source, target),
     190            "Wrong path");
    238191  }
    239192

  • tools/dimacs-solver.cc

    r614 r611  
    9494template<class Value>
    9595void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
    96                Value infty, DimacsDescriptor &desc)
     96               DimacsDescriptor &desc)
    9797{
    9898  bool report = !ap.given("q");
    … …  
    101101  Digraph::NodeMap<Value> sup(g);
    102102  Timer ti;
    103 
    104   ti.restart();
    105   readDimacsMin(is, g, lower, cap, cost, sup, infty, desc);
    106   ti.stop();
    107   Value sum_sup = 0;
    108   for (Digraph::NodeIt n(g); n != INVALID; ++n) {
    109     sum_sup += sup[n];
    110   }
    111   if (report) {
    112     std::cerr << "Sum of supply values: " << sum_sup << "\n";
    113     if (sum_sup <= 0)
    114       std::cerr << "GEQ supply contraints are used for NetworkSimplex\n\n";
    115     else
    116       std::cerr << "LEQ supply contraints are used for NetworkSimplex\n\n";
    117   }
     103  ti.restart();
     104  readDimacsMin(is, g, lower, cap, cost, sup, 0, desc);
    118105  if (report) std::cerr << "Read the file: " << ti << '\n';
    119 
    120106  ti.restart();
    121107  NetworkSimplex<Digraph, Value> ns(g);
    122108  ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
    123   if (sum_sup > 0) ns.problemType(ns.LEQ);
    124109  if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
    125110  ti.restart();
    126   bool res = ns.run();
    127   if (report) {
    128     std::cerr << "Run NetworkSimplex: " << ti << "\n\n";
    129     std::cerr << "Feasible flow: " << (res ? "found" : "not found") << '\n';
    130     if (res) std::cerr << "Min flow cost: " << ns.totalCost() << '\n';
    131   }
     111  ns.run();
     112  if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n';
     113  if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n';
    132114}
    133115
    … …  
    170152    {
    171153    case DimacsDescriptor::MIN:
    172       solve_min<Value>(ap,is,os,infty,desc);
     154      solve_min<Value>(ap,is,os,desc);
    173155      break;
    174156    case DimacsDescriptor::MAX:

  • tools/lgf-gen.cc

    r623 r584  
    6666  double tlen=0;
    6767  for(EdgeIt e(g);e!=INVALID;++e)
    68     tlen+=std::sqrt((coords[g.v(e)]-coords[g.u(e)]).normSquare());
     68    tlen+=sqrt((coords[g.v(e)]-coords[g.u(e)]).normSquare());
    6969  return tlen;
    7070}
    … …  
    189189      (r.x * r.x + r.y * r.y) * (p.x * q.y - q.x * p.y);
    190190
    191     return d / (2 * a) + std::sqrt((d * d + e * e) / (4 * a * a) + f / a);
     191    return d / (2 * a) + sqrt((d * d + e * e) / (4 * a * a) + f / a);
    192192  }
    193193
    … …  
    207207    double b = (q.x - sx) * p.y - (p.x - sx) * q.y;
    208208    double d = (q.x - sx) * (p.x - sx) * (p - q).normSquare();
    209     return (b - std::sqrt(d)) / a;
     209    return (b - sqrt(d)) / a;
    210210  }
    211211
    … …  
    481481      g.erase(*ei);
    482482      ConstMap<Arc,int> cegy(1);
    483       Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy);
    484       int k=sur.run(a,b,2);
     483      Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy,a,b);
     484      int k=sur.run(2);
    485485      if(k<2 || sur.totalLength()>d)
    486486        g.addEdge(a,b);
    … …  
    512512      if(e==INVALID) {
    513513        ConstMap<Arc,int> cegy(1);
    514         Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy);
    515         int k=sur.run(pi->a,pi->b,2);
     514        Suurballe<ListGraph,ConstMap<Arc,int> >
     515          sur(g,cegy,pi->a,pi->b);
     516        int k=sur.run(2);
    516517        if(k<2 || sur.totalLength()>d)
    517518          {
    … …  
    720721
    721722  if (ap["rand"]) {
    722     int seed = int(time(0));
     723    int seed = time(0);
    723724    std::cout << "Random number seed: " << seed << std::endl;
    724725    rnd = Random(seed);
    … …  
    813814  double tlen=0;
    814815  for(EdgeIt e(g);e!=INVALID;++e)
    815     tlen+=std::sqrt((coords[g.v(e)]-coords[g.u(e)]).normSquare());
     816    tlen+=sqrt((coords[g.v(e)]-coords[g.u(e)]).normSquare());
    816817  std::cout << "Total arc length  : " << tlen << std::endl;
    817818
Note: See TracChangeset for help on using the changeset viewer.