COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
28 edited

Legend:

Unmodified
Added
Removed

  • demo/graph_to_eps_demo.cc

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

  • lemon/adaptors.h

    r626 r664  
    110110    template <typename V>
    111111    class NodeMap : public DGR::template NodeMap<V> {
     112      typedef typename DGR::template NodeMap<V> Parent;
     113
    112114    public:
    113 
    114       typedef typename DGR::template NodeMap<V> Parent;
    115 
    116115      explicit NodeMap(const Adaptor& adaptor)
    117116        : Parent(*adaptor._digraph) {}
    118 
    119117      NodeMap(const Adaptor& adaptor, const V& value)
    120118        : Parent(*adaptor._digraph, value) { }
    … …  
    135133    template <typename V>
    136134    class ArcMap : public DGR::template ArcMap<V> {
     135      typedef typename DGR::template ArcMap<V> Parent;
     136
    137137    public:
    138 
    139       typedef typename DGR::template ArcMap<V> Parent;
    140 
    141138      explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)
    142139        : Parent(*adaptor._digraph) {}
    143 
    144140      ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value)
    145141        : Parent(*adaptor._digraph, value) {}
    … …  
    256252    template <typename V>
    257253    class NodeMap : public GR::template NodeMap<V> {
     254      typedef typename GR::template NodeMap<V> Parent;
     255
    258256    public:
    259       typedef typename GR::template NodeMap<V> Parent;
    260257      explicit NodeMap(const GraphAdaptorBase<GR>& adapter)
    261258        : Parent(*adapter._graph) {}
    … …  
    278275    template <typename V>
    279276    class ArcMap : public GR::template ArcMap<V> {
     277      typedef typename GR::template ArcMap<V> Parent;
     278
    280279    public:
    281       typedef typename GR::template ArcMap<V> Parent;
    282280      explicit ArcMap(const GraphAdaptorBase<GR>& adapter)
    283281        : Parent(*adapter._graph) {}
    … …  
    299297    template <typename V>
    300298    class EdgeMap : public GR::template EdgeMap<V> {
     299      typedef typename GR::template EdgeMap<V> Parent;
     300
    301301    public:
    302       typedef typename GR::template EdgeMap<V> Parent;
    303302      explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)
    304303        : Parent(*adapter._graph) {}
    … …  
    322321  template <typename DGR>
    323322  class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {
     323    typedef DigraphAdaptorBase<DGR> Parent;
    324324  public:
    325325    typedef DGR Digraph;
    326     typedef DigraphAdaptorBase<DGR> Parent;
    327326  protected:
    328327    ReverseDigraphBase() : Parent() { }
    … …  
    375374    public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {
    376375#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;
    381380  protected:
    382381    ReverseDigraph() { }
    … …  
    404403  template <typename DGR, typename NF, typename AF, bool ch = true>
    405404  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;
    413412  protected:
    414413    NF* _node_filter;
    … …  
    510509      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    511510              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
    512514    public:
    513515      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      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     539        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
     540
    538541    public:
    539542      typedef V Value;
    540       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    541         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
    542543
    543544      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
    … …  
    563564  class SubDigraphBase<DGR, NF, AF, false>
    564565    : public DigraphAdaptorBase<DGR> {
     566    typedef DigraphAdaptorBase<DGR> Parent;
    565567  public:
    566568    typedef DGR Digraph;
    … …  
    569571
    570572    typedef SubDigraphBase Adaptor;
    571     typedef DigraphAdaptorBase<Digraph> Parent;
    572573  protected:
    573574    NF* _node_filter;
    … …  
    651652      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    652653          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
     654      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
     655        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
     656
    653657    public:
    654658      typedef V Value;
    655       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    656         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    657659
    658660      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
    … …  
    677679      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    678680          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
    679684    public:
    680685      typedef V Value;
    681       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    682           LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
    683686
    684687      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
    … …  
    864867  template <typename GR, typename NF, typename EF, bool ch = true>
    865868  class SubGraphBase : public GraphAdaptorBase<GR> {
     869    typedef GraphAdaptorBase<GR> Parent;
    866870  public:
    867871    typedef GR Graph;
    … …  
    870874
    871875    typedef SubGraphBase Adaptor;
    872     typedef GraphAdaptorBase<GR> Parent;
    873876  protected:
    874877
    … …  
    10171020      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10181021          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
     1022      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1023        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
     1024
    10191025    public:
    10201026      typedef V Value;
    1021       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    1022         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    10231027
    10241028      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
    … …  
    10431047      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10441048          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
     1049      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1050        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
     1051
    10451052    public:
    10461053      typedef V Value;
    1047       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    1048         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    10491054
    10501055      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
    … …  
    10691074      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10701075        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
     1076      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1077        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
     1078
    10711079    public:
    10721080      typedef V Value;
    1073       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    1074         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    10751081
    10761082      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
    … …  
    10971103  class SubGraphBase<GR, NF, EF, false>
    10981104    : public GraphAdaptorBase<GR> {
     1105    typedef GraphAdaptorBase<GR> Parent;
    10991106  public:
    11001107    typedef GR Graph;
    … …  
    11031110
    11041111    typedef SubGraphBase Adaptor;
    1105     typedef GraphAdaptorBase<GR> Parent;
    11061112  protected:
    11071113    NF* _node_filter;
    … …  
    12121218      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12131219          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
     1220      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1221        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
     1222
    12141223    public:
    12151224      typedef V Value;
    1216       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    1217         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    12181225
    12191226      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
    … …  
    12381245      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12391246          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
     1247      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1248        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
     1249
    12401250    public:
    12411251      typedef V Value;
    1242       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    1243         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    12441252
    12451253      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
    … …  
    12641272      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12651273        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
    12661277    public:
    12671278      typedef V Value;
    1268       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    1269                   LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    12701279
    12711280      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
    … …  
    14861495                     true> > {
    14871496#endif
    1488   public:
    1489 
    1490     typedef GR Digraph;
    1491     typedef NF NodeFilterMap;
    1492 
    14931497    typedef DigraphAdaptorExtender<
    14941498      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
    14951499                     true> > Parent;
     1500
     1501  public:
     1502
     1503    typedef GR Digraph;
     1504    typedef NF NodeFilterMap;
    14961505
    14971506    typedef typename Parent::Node Node;
    … …  
    15491558                   true> > {
    15501559
    1551   public:
    1552     typedef GR Graph;
    1553     typedef NF NodeFilterMap;
    15541560    typedef GraphAdaptorExtender<
    15551561      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
    15561562                   true> > Parent;
    15571563
     1564  public:
     1565
     1566    typedef GR Graph;
     1567    typedef NF NodeFilterMap;
     1568
    15581569    typedef typename Parent::Node Node;
     1570
    15591571  protected:
    15601572    ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;
    … …  
    16301642                     AF, false> > {
    16311643#endif
    1632   public:
     1644    typedef DigraphAdaptorExtender<
     1645      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
     1646                     AF, false> > Parent;
     1647
     1648  public:
     1649
    16331650    /// The type of the adapted digraph.
    16341651    typedef DGR Digraph;
    16351652    /// The type of the arc filter map.
    16361653    typedef AF ArcFilterMap;
    1637 
    1638     typedef DigraphAdaptorExtender<
    1639       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
    1640                      AF, false> > Parent;
    16411654
    16421655    typedef typename Parent::Arc Arc;
    … …  
    17391752                   EF, false> > {
    17401753#endif
    1741   public:
     1754    typedef GraphAdaptorExtender<
     1755      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
     1756                   EF, false> > Parent;
     1757
     1758  public:
     1759
    17421760    /// The type of the adapted graph.
    17431761    typedef GR Graph;
    17441762    /// The type of the edge filter map.
    17451763    typedef EF EdgeFilterMap;
    1746 
    1747     typedef GraphAdaptorExtender<
    1748       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
    1749                    EF, false> > Parent;
    17501764
    17511765    typedef typename Parent::Edge Edge;
    … …  
    21122126    template <typename V>
    21132127    class NodeMap : public DGR::template NodeMap<V> {
     2128      typedef typename DGR::template NodeMap<V> Parent;
     2129
    21142130    public:
    2115 
    21162131      typedef V Value;
    2117       typedef typename DGR::template NodeMap<Value> Parent;
    21182132
    21192133      explicit NodeMap(const UndirectorBase<DGR>& adaptor)
    … …  
    21382152    template <typename V>
    21392153    class ArcMap
    2140       : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> >
    2141     {
     2154      : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > {
     2155      typedef SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > Parent;
     2156
    21422157    public:
    21432158      typedef V Value;
    2144       typedef SubMapExtender<Adaptor, ArcMapBase<V> > Parent;
    21452159
    21462160      explicit ArcMap(const UndirectorBase<DGR>& adaptor)
    … …  
    21642178    template <typename V>
    21652179    class EdgeMap : public Digraph::template ArcMap<V> {
     2180      typedef typename Digraph::template ArcMap<V> Parent;
     2181
    21662182    public:
    2167 
    21682183      typedef V Value;
    2169       typedef typename Digraph::template ArcMap<V> Parent;
    21702184
    21712185      explicit EdgeMap(const UndirectorBase<DGR>& adaptor)
    … …  
    22392253    public GraphAdaptorExtender<UndirectorBase<DGR> > {
    22402254#endif
     2255    typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
    22412256  public:
    22422257    /// The type of the adapted digraph.
    22432258    typedef DGR Digraph;
    2244     typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
    22452259  protected:
    22462260    Undirector() { }
    … …  
    24502464    template <typename V>
    24512465    class NodeMap : public GR::template NodeMap<V> {
     2466      typedef typename GR::template NodeMap<V> Parent;
     2467
    24522468    public:
    2453 
    2454       typedef typename GR::template NodeMap<V> Parent;
    24552469
    24562470      explicit NodeMap(const OrienterBase<GR, DM>& adapter)
    … …  
    24752489    template <typename V>
    24762490    class ArcMap : public GR::template EdgeMap<V> {
     2491      typedef typename Graph::template EdgeMap<V> Parent;
     2492
    24772493    public:
    2478 
    2479       typedef typename Graph::template EdgeMap<V> Parent;
    24802494
    24812495      explicit ArcMap(const OrienterBase<GR, DM>& adapter)
    … …  
    25472561    public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
    25482562#endif
     2563    typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
    25492564  public:
    25502565
    … …  
    25542569    typedef DM DirectionMap;
    25552570
    2556     typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
    25572571    typedef typename Parent::Arc Arc;
     2572
    25582573  protected:
    25592574    Orienter() { }
     2575
    25602576  public:
    25612577
    … …  
    28672883  template <typename DGR>
    28682884  class SplitNodesBase {
     2885    typedef DigraphAdaptorBase<const DGR> Parent;
     2886
    28692887  public:
    28702888
    28712889    typedef DGR Digraph;
    2872     typedef DigraphAdaptorBase<const DGR> Parent;
    28732890    typedef SplitNodesBase Adaptor;
    28742891
    … …  
    32293246    template <typename V>
    32303247    class NodeMap
    3231       : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> >
    3232     {
     3248      : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > {
     3249      typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > Parent;
     3250
    32333251    public:
    32343252      typedef V Value;
    3235       typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<Value> > Parent;
    32363253
    32373254      NodeMap(const SplitNodesBase<DGR>& adaptor)
    … …  
    32553272    template <typename V>
    32563273    class ArcMap
    3257       : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> >
    3258     {
     3274      : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > {
     3275      typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > Parent;
     3276
    32593277    public:
    32603278      typedef V Value;
    3261       typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<Value> > Parent;
    32623279
    32633280      ArcMap(const SplitNodesBase<DGR>& adaptor)
    … …  
    33253342    : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {
    33263343#endif
     3344    typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
     3345
    33273346  public:
    33283347    typedef DGR Digraph;
    3329     typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
    33303348
    33313349    typedef typename DGR::Node DigraphNode;

  • lemon/bits/array_map.h

    r525 r664  
    4848  public:
    4949    // The graph type.
    50     typedef _Graph Graph;
     50    typedef _Graph GraphType;
    5151    // The item type.
    5252    typedef _Item Item;
    … …  
    6464    typedef _Value& Reference;
    6565
     66    // The map type.
     67    typedef ArrayMap Map;
     68
    6669    // The notifier type.
    6770    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    6871
     72  private:
     73 
    6974    // The MapBase of the Map which imlements the core regisitry function.
    7075    typedef typename Notifier::ObserverBase Parent;
    7176
    72   private:
    7377    typedef std::allocator<Value> Allocator;
    7478
    … …  
    7882    //
    7983    // Graph initialized map constructor.
    80     explicit ArrayMap(const Graph& graph) {
     84    explicit ArrayMap(const GraphType& graph) {
    8185      Parent::attach(graph.notifier(Item()));
    8286      allocate_memory();
    … …  
    9296    //
    9397    // It constructs a map and initialize all of the the map.
    94     ArrayMap(const Graph& graph, const Value& value) {
     98    ArrayMap(const GraphType& graph, const Value& value) {
    9599      Parent::attach(graph.notifier(Item()));
    96100      allocate_memory();

  • lemon/bits/base_extender.h

    r463 r664  
    3939  template <typename Base>
    4040  class UndirDigraphExtender : public Base {
     41    typedef Base Parent;
    4142
    4243  public:
    4344
    44     typedef Base Parent;
    4545    typedef typename Parent::Arc Edge;
    4646    typedef typename Parent::Node Node;
    … …  
    281281  template <typename Base>
    282282  class BidirBpGraphExtender : public Base {
     283    typedef Base Parent;
     284
    283285  public:
    284     typedef Base Parent;
    285286    typedef BidirBpGraphExtender Digraph;
    286287

  • lemon/bits/default_map.h

    r582 r664  
    154154  class DefaultMap
    155155    : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
     156    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
     157
    156158  public:
    157     typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
    158159    typedef DefaultMap<_Graph, _Item, _Value> Map;
    159 
    160     typedef typename Parent::Graph Graph;
     160   
     161    typedef typename Parent::GraphType GraphType;
    161162    typedef typename Parent::Value Value;
    162163
    163     explicit DefaultMap(const Graph& graph) : Parent(graph) {}
    164     DefaultMap(const Graph& graph, const Value& value)
     164    explicit DefaultMap(const GraphType& graph) : Parent(graph) {}
     165    DefaultMap(const GraphType& graph, const Value& value)
    165166      : Parent(graph, value) {}
    166167

  • lemon/bits/edge_set_extender.h

    r606 r664  
    3535  template <typename Base>
    3636  class ArcSetExtender : public Base {
     37    typedef Base Parent;
     38
    3739  public:
    3840
    39     typedef Base Parent;
    4041    typedef ArcSetExtender Digraph;
    4142
    … …  
    219220    class ArcMap
    220221      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
    221     public:
    222       typedef ArcSetExtender Digraph;
    223222      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    224223
     224    public:
    225225      explicit ArcMap(const Digraph& _g)
    226226        : Parent(_g) {}
    … …  
    275275  template <typename Base>
    276276  class EdgeSetExtender : public Base {
     277    typedef Base Parent;
    277278
    278279  public:
    279280
    280     typedef Base Parent;
    281     typedef EdgeSetExtender Digraph;
     281    typedef EdgeSetExtender Graph;
    282282
    283283    typedef typename Parent::Node Node;
    284284    typedef typename Parent::Arc Arc;
    285285    typedef typename Parent::Edge Edge;
    286 
    287286
    288287    int maxId(Node) const {
    … …  
    351350
    352351    class NodeIt : public Node {
    353       const Digraph* digraph;
     352      const Graph* graph;
    354353    public:
    355354
    … …  
    358357      NodeIt(Invalid i) : Node(i) { }
    359358
    360       explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
     359      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
    361360        _graph.first(static_cast<Node&>(*this));
    362361      }
    363362
    364       NodeIt(const Digraph& _graph, const Node& node)
    365         : Node(node), digraph(&_graph) {}
     363      NodeIt(const Graph& _graph, const Node& node)
     364        : Node(node), graph(&_graph) {}
    366365
    367366      NodeIt& operator++() {
    368         digraph->next(*this);
     367        graph->next(*this);
    369368        return *this;
    370369      }
    … …  
    374373
    375374    class ArcIt : public Arc {
    376       const Digraph* digraph;
     375      const Graph* graph;
    377376    public:
    378377
    … …  
    381380      ArcIt(Invalid i) : Arc(i) { }
    382381
    383       explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
     382      explicit ArcIt(const Graph& _graph) : graph(&_graph) {
    384383        _graph.first(static_cast<Arc&>(*this));
    385384      }
    386385
    387       ArcIt(const Digraph& _graph, const Arc& e) :
    388         Arc(e), digraph(&_graph) { }
     386      ArcIt(const Graph& _graph, const Arc& e) :
     387        Arc(e), graph(&_graph) { }
    389388
    390389      ArcIt& operator++() {
    391         digraph->next(*this);
     390        graph->next(*this);
    392391        return *this;
    393392      }
    … …  
    397396
    398397    class OutArcIt : public Arc {
    399       const Digraph* digraph;
     398      const Graph* graph;
    400399    public:
    401400
    … …  
    404403      OutArcIt(Invalid i) : Arc(i) { }
    405404
    406       OutArcIt(const Digraph& _graph, const Node& node)
    407         : digraph(&_graph) {
     405      OutArcIt(const Graph& _graph, const Node& node)
     406        : graph(&_graph) {
    408407        _graph.firstOut(*this, node);
    409408      }
    410409
    411       OutArcIt(const Digraph& _graph, const Arc& arc)
    412         : Arc(arc), digraph(&_graph) {}
     410      OutArcIt(const Graph& _graph, const Arc& arc)
     411        : Arc(arc), graph(&_graph) {}
    413412
    414413      OutArcIt& operator++() {
    415         digraph->nextOut(*this);
     414        graph->nextOut(*this);
    416415        return *this;
    417416      }
    … …  
    421420
    422421    class InArcIt : public Arc {
    423       const Digraph* digraph;
     422      const Graph* graph;
    424423    public:
    425424
    … …  
    428427      InArcIt(Invalid i) : Arc(i) { }
    429428
    430       InArcIt(const Digraph& _graph, const Node& node)
    431         : digraph(&_graph) {
     429      InArcIt(const Graph& _graph, const Node& node)
     430        : graph(&_graph) {
    432431        _graph.firstIn(*this, node);
    433432      }
    434433
    435       InArcIt(const Digraph& _graph, const Arc& arc) :
    436         Arc(arc), digraph(&_graph) {}
     434      InArcIt(const Graph& _graph, const Arc& arc) :
     435        Arc(arc), graph(&_graph) {}
    437436
    438437      InArcIt& operator++() {
    439         digraph->nextIn(*this);
     438        graph->nextIn(*this);
    440439        return *this;
    441440      }
    … …  
    445444
    446445    class EdgeIt : public Parent::Edge {
    447       const Digraph* digraph;
     446      const Graph* graph;
    448447    public:
    449448
    … …  
    452451      EdgeIt(Invalid i) : Edge(i) { }
    453452
    454       explicit EdgeIt(const Digraph& _graph) : digraph(&_graph) {
     453      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
    455454        _graph.first(static_cast<Edge&>(*this));
    456455      }
    457456
    458       EdgeIt(const Digraph& _graph, const Edge& e) :
    459         Edge(e), digraph(&_graph) { }
     457      EdgeIt(const Graph& _graph, const Edge& e) :
     458        Edge(e), graph(&_graph) { }
    460459
    461460      EdgeIt& operator++() {
    462         digraph->next(*this);
     461        graph->next(*this);
    463462        return *this;
    464463      }
    … …  
    468467    class IncEdgeIt : public Parent::Edge {
    469468      friend class EdgeSetExtender;
    470       const Digraph* digraph;
     469      const Graph* graph;
    471470      bool direction;
    472471    public:
    … …  
    476475      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
    477476
    478       IncEdgeIt(const Digraph& _graph, const Node &n) : digraph(&_graph) {
     477      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
    479478        _graph.firstInc(*this, direction, n);
    480479      }
    481480
    482       IncEdgeIt(const Digraph& _graph, const Edge &ue, const Node &n)
    483         : digraph(&_graph), Edge(ue) {
     481      IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
     482        : graph(&_graph), Edge(ue) {
    484483        direction = (_graph.source(ue) == n);
    485484      }
    486485
    487486      IncEdgeIt& operator++() {
    488         digraph->nextInc(*this, direction);
     487        graph->nextInc(*this, direction);
    489488        return *this;
    490489      }
    … …  
    535534    template <typename _Value>
    536535    class ArcMap
    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)
     536      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
     537      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
     538
     539    public:
     540      ArcMap(const Graph& _g)
    543541        : Parent(_g) {}
    544       ArcMap(const Digraph& _g, const _Value& _v)
     542      ArcMap(const Graph& _g, const _Value& _v)
    545543        : Parent(_g, _v) {}
    546544
    … …  
    560558    template <typename _Value>
    561559    class EdgeMap
    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)
     560      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
     561      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
     562
     563    public:
     564      EdgeMap(const Graph& _g)
    568565        : Parent(_g) {}
    569566
    570       EdgeMap(const Digraph& _g, const _Value& _v)
     567      EdgeMap(const Graph& _g, const _Value& _v)
    571568        : Parent(_g, _v) {}
    572569

  • lemon/bits/graph_adaptor_extender.h

    r627 r664  
    2727  template <typename _Digraph>
    2828  class DigraphAdaptorExtender : public _Digraph {
     29    typedef _Digraph Parent;
     30
    2931  public:
    3032
    31     typedef _Digraph Parent;
    3233    typedef _Digraph Digraph;
    3334    typedef DigraphAdaptorExtender Adaptor;
    … …  
    174175  template <typename _Graph>
    175176  class GraphAdaptorExtender : public _Graph {
     177    typedef _Graph Parent;
     178
    176179  public:
    177180
    178     typedef _Graph Parent;
    179181    typedef _Graph Graph;
    180182    typedef GraphAdaptorExtender Adaptor;

  • lemon/bits/graph_extender.h

    r463 r664  
    3838  template <typename Base>
    3939  class DigraphExtender : public Base {
     40    typedef Base Parent;
     41
    4042  public:
    4143
    42     typedef Base Parent;
    4344    typedef DigraphExtender Digraph;
    4445
    … …  
    219220    class NodeMap
    220221      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
    221     public:
    222       typedef DigraphExtender Digraph;
    223222      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
    224223
     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;
    248246      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    249247
     248    public:
    250249      explicit ArcMap(const Digraph& digraph)
    251250        : Parent(digraph) {}
    … …  
    331330  template <typename Base>
    332331  class GraphExtender : public Base {
     332    typedef Base Parent;
     333
    333334  public:
    334335
    335     typedef Base Parent;
    336336    typedef GraphExtender Graph;
    337337
    … …  
    602602    class NodeMap
    603603      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
    604     public:
    605       typedef GraphExtender Graph;
    606604      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
    607605
     606    public:
    608607      NodeMap(const Graph& graph)
    609608        : Parent(graph) {}
    … …  
    627626    class ArcMap
    628627      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
    629     public:
    630       typedef GraphExtender Graph;
    631628      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    632629
     630    public:
    633631      ArcMap(const Graph& graph)
    634632        : Parent(graph) {}
    … …  
    652650    class EdgeMap
    653651      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    654     public:
    655       typedef GraphExtender Graph;
    656652      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    657653
     654    public:
    658655      EdgeMap(const Graph& graph)
    659656        : Parent(graph) {}

  • lemon/bits/map_extender.h

    r627 r664  
    3737  template <typename _Map>
    3838  class MapExtender : public _Map {
    39   public:
    40 
    4139    typedef _Map Parent;
     40    typedef typename Parent::GraphType GraphType;
     41
     42  public:
     43
    4244    typedef MapExtender Map;
    43 
    44 
    45     typedef typename Parent::Graph Graph;
    4645    typedef typename Parent::Key Item;
    4746
    … …  
    5958  public:
    6059
    61     MapExtender(const Graph& graph)
     60    MapExtender(const GraphType& graph)
    6261      : Parent(graph) {}
    6362
    64     MapExtender(const Graph& graph, const Value& value)
     63    MapExtender(const GraphType& graph, const Value& value)
    6564      : Parent(graph, value) {}
    6665
    … …  
    7877  public:
    7978    class MapIt : public Item {
    80     public:
    81 
    82       typedef Item Parent;
     79      typedef Item Parent;
     80
     81    public:
     82
    8383      typedef typename Map::Value Value;
    8484
    … …  
    117117
    118118    class ConstMapIt : public Item {
    119     public:
    120 
    121       typedef Item Parent;
     119      typedef Item Parent;
     120
     121    public:
    122122
    123123      typedef typename Map::Value Value;
    … …  
    148148
    149149    class ItemIt : public Item {
    150     public:
    151 
    152       typedef Item Parent;
     150      typedef Item Parent;
     151
     152    public:
    153153
    154154      ItemIt() {}
    … …  
    179179  template <typename _Graph, typename _Map>
    180180  class SubMapExtender : public _Map {
    181   public:
    182 
    183181    typedef _Map Parent;
     182    typedef _Graph GraphType;
     183
     184  public:
     185
    184186    typedef SubMapExtender Map;
    185 
    186     typedef _Graph Graph;
    187 
    188187    typedef typename Parent::Key Item;
    189188
    … …  
    201200  public:
    202201
    203     SubMapExtender(const Graph& _graph)
     202    SubMapExtender(const GraphType& _graph)
    204203      : Parent(_graph), graph(_graph) {}
    205204
    206     SubMapExtender(const Graph& _graph, const Value& _value)
     205    SubMapExtender(const GraphType& _graph, const Value& _value)
    207206      : Parent(_graph, _value), graph(_graph) {}
    208207
    … …  
    224223  public:
    225224    class MapIt : public Item {
    226     public:
    227 
    228       typedef Item Parent;
     225      typedef Item Parent;
     226
     227    public:
    229228      typedef typename Map::Value Value;
    230229
    … …  
    263262
    264263    class ConstMapIt : public Item {
    265     public:
    266 
    267       typedef Item Parent;
     264      typedef Item Parent;
     265
     266    public:
    268267
    269268      typedef typename Map::Value Value;
    … …  
    294293
    295294    class ItemIt : public Item {
    296     public:
    297 
    298       typedef Item Parent;
     295      typedef Item Parent;
     296
     297    public:
    299298
    300299      ItemIt() {}
    … …  
    321320  private:
    322321
    323     const Graph& graph;
     322    const GraphType& graph;
    324323
    325324  };

  • lemon/bits/traits.h

    r463 r663  
    3030  struct InvalidType {};
    3131
    32   template <typename _Graph, typename _Item>
     32  template <typename GR, typename _Item>
    3333  class ItemSetTraits {};
    3434
    3535
    36   template <typename Graph, typename Enable = void>
     36  template <typename GR, typename Enable = void>
    3737  struct NodeNotifierIndicator {
    3838    typedef InvalidType Type;
    3939  };
    40   template <typename Graph>
     40  template <typename GR>
    4141  struct NodeNotifierIndicator<
    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> {
     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> {
    5050  public:
    5151
    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> {
     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
    6164    public:
    62       typedef typename Graph::template NodeMap<_Value> Parent;
    63       typedef typename Graph::template NodeMap<_Value> Type;
     65      typedef typename GR::template NodeMap<V> Type;
    6466      typedef typename Parent::Value Value;
    6567
    66       Map(const Graph& _digraph) : Parent(_digraph) {}
    67       Map(const Graph& _digraph, const Value& _value)
     68      Map(const GR& _digraph) : Parent(_digraph) {}
     69      Map(const GR& _digraph, const Value& _value)
    6870        : Parent(_digraph, _value) {}
    6971
    … …  
    7274  };
    7375
    74   template <typename Graph, typename Enable = void>
     76  template <typename GR, typename Enable = void>
    7577  struct ArcNotifierIndicator {
    7678    typedef InvalidType Type;
    7779  };
    78   template <typename Graph>
     80  template <typename GR>
    7981  struct ArcNotifierIndicator<
    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> {
     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> {
    8890  public:
    8991
    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> {
     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
    99104    public:
    100       typedef typename Graph::template ArcMap<_Value> Parent;
    101       typedef typename Graph::template ArcMap<_Value> Type;
     105      typedef typename GR::template ArcMap<V> Type;
    102106      typedef typename Parent::Value Value;
    103107
    104       Map(const Graph& _digraph) : Parent(_digraph) {}
    105       Map(const Graph& _digraph, const Value& _value)
     108      Map(const GR& _digraph) : Parent(_digraph) {}
     109      Map(const GR& _digraph, const Value& _value)
    106110        : Parent(_digraph, _value) {}
    107111    };
    … …  
    109113  };
    110114
    111   template <typename Graph, typename Enable = void>
     115  template <typename GR, typename Enable = void>
    112116  struct EdgeNotifierIndicator {
    113117    typedef InvalidType Type;
    114118  };
    115   template <typename Graph>
     119  template <typename GR>
    116120  struct EdgeNotifierIndicator<
    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> {
     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> {
    125129  public:
    126130
    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> {
     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
    136143    public:
    137       typedef typename Graph::template EdgeMap<_Value> Parent;
    138       typedef typename Graph::template EdgeMap<_Value> Type;
     144      typedef typename GR::template EdgeMap<V> Type;
    139145      typedef typename Parent::Value Value;
    140146
    141       Map(const Graph& _digraph) : Parent(_digraph) {}
    142       Map(const Graph& _digraph, const Value& _value)
     147      Map(const GR& _digraph) : Parent(_digraph) {}
     148      Map(const GR& _digraph, const Value& _value)
    143149        : Parent(_digraph, _value) {}
    144150    };
    … …  
    205211  // Indicators for the tags
    206212
    207   template <typename Graph, typename Enable = void>
     213  template <typename GR, typename Enable = void>
    208214  struct NodeNumTagIndicator {
    209215    static const bool value = false;
    210216  };
    211217
    212   template <typename Graph>
     218  template <typename GR>
    213219  struct NodeNumTagIndicator<
    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>
     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>
    221227  struct ArcNumTagIndicator {
    222228    static const bool value = false;
    223229  };
    224230
    225   template <typename Graph>
     231  template <typename GR>
    226232  struct ArcNumTagIndicator<
    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>
     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>
    234240  struct EdgeNumTagIndicator {
    235241    static const bool value = false;
    236242  };
    237243
    238   template <typename Graph>
     244  template <typename GR>
    239245  struct EdgeNumTagIndicator<
    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>
     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>
    247253  struct FindArcTagIndicator {
    248254    static const bool value = false;
    249255  };
    250256
    251   template <typename Graph>
     257  template <typename GR>
    252258  struct FindArcTagIndicator<
    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>
     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>
    260266  struct FindEdgeTagIndicator {
    261267    static const bool value = false;
    262268  };
    263269
    264   template <typename Graph>
     270  template <typename GR>
    265271  struct FindEdgeTagIndicator<
    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>
     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>
    273279  struct UndirectedTagIndicator {
    274280    static const bool value = false;
    275281  };
    276282
    277   template <typename Graph>
     283  template <typename GR>
    278284  struct UndirectedTagIndicator<
    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>
     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>
    286292  struct BuildTagIndicator {
    287293    static const bool value = false;
    288294  };
    289295
    290   template <typename Graph>
     296  template <typename GR>
    291297  struct BuildTagIndicator<
    292     Graph,
    293     typename enable_if<typename Graph::BuildTag, void>::type
     298    GR,
     299    typename enable_if<typename GR::BuildTag, void>::type
    294300  > {
    295301    static const bool value = true;

  • lemon/bits/vector_map.h

    r525 r664  
    5757
    5858    // The graph type of the map.
    59     typedef _Graph Graph;
     59    typedef _Graph GraphType;
    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;
    7775
    7876    // The reference type of the map;
    … …  
    8179    typedef typename Container::const_reference ConstReference;
    8280
     81  private:
     82
     83    // The base class of the map.
     84    typedef typename Notifier::ObserverBase Parent;
     85
     86  public:
    8387
    8488    // \brief Constructor to attach the new map into the notifier.
    … …  
    8690    // It constructs a map and attachs it into the notifier.
    8791    // It adds all the items of the graph to the map.
    88     VectorMap(const Graph& graph) {
     92    VectorMap(const GraphType& graph) {
    8993      Parent::attach(graph.notifier(Item()));
    9094      container.resize(Parent::notifier()->maxId() + 1);
    … …  
    9599    // It constructs a map uses a given value to initialize the map.
    96100    // It adds all the items of the graph to the map.
    97     VectorMap(const Graph& graph, const Value& value) {
     101    VectorMap(const GraphType& graph, const Value& value) {
    98102      Parent::attach(graph.notifier(Item()));
    99103      container.resize(Parent::notifier()->maxId() + 1, value);

  • lemon/circulation.h

    r658 r669  
    2222#include <lemon/tolerance.h>
    2323#include <lemon/elevator.h>
     24#include <limits>
    2425
    2526///\ingroup max_flow
    … …  
    120121
    121122     The exact formulation of this problem is the following.
    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$
     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$
    125126     holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
    126127     denotes the signed supply values of the nodes.
    … …  
    128129     supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
    129130     \f$-sup(u)\f$ demand.
    130      A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$
     131     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$
    131132     solution of the following problem.
    132133
    … …  
    151152     the direction of the arcs and taking the negative of the supply values
    152153     (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.
    153158
    154159     Note that this algorithm also provides a feasible solution for the
    … …  
    338343  private:
    339344
     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
    340352    void createStructures() {
    341353      _node_num = _el = countNodes(_g);
    … …  
    381393    /// Sets the upper bound (capacity) map.
    382394    /// \return <tt>(*this)</tt>
    383     Circulation& upperMap(const LowerMap& map) {
     395    Circulation& upperMap(const UpperMap& map) {
    384396      _up = &map;
    385397      return *this;
    … …  
    468480    void init()
    469481    {
     482      LEMON_DEBUG(checkBoundMaps(),
     483        "Upper bounds must be greater or equal to the lower bounds");
     484
    470485      createStructures();
    471486
    … …  
    497512    void greedyInit()
    498513    {
     514      LEMON_DEBUG(checkBoundMaps(),
     515        "Upper bounds must be greater or equal to the lower bounds");
     516
    499517      createStructures();
    500518
    … …  
    504522
    505523      for (ArcIt e(_g);e!=INVALID;++e) {
    506         if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
     524        if (!_tol.less(-(*_excess)[_g.target(e)], (*_up)[e])) {
    507525          _flow->set(e, (*_up)[e]);
    508526          (*_excess)[_g.target(e)] += (*_up)[e];
    509527          (*_excess)[_g.source(e)] -= (*_up)[e];
    510         } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
     528        } else if (_tol.less(-(*_excess)[_g.target(e)], (*_lo)[e])) {
    511529          _flow->set(e, (*_lo)[e]);
    512530          (*_excess)[_g.target(e)] += (*_lo)[e];
    … …  
    749767    {
    750768      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();
    751772      for(NodeIt n(_g);n!=INVALID;++n)
    752773        if(barrier(n))
    … …  
    756777          Node s=_g.source(e);
    757778          Node t=_g.target(e);
    758           if(barrier(s)&&!barrier(t)) delta+=(*_up)[e];
     779          if(barrier(s)&&!barrier(t)) {
     780            if (_tol.less(inf_cap - (*_up)[e], delta)) return false;
     781            delta+=(*_up)[e];
     782          }
    759783          else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e];
    760784        }

  • lemon/concepts/graph_components.h

    r631 r664  
    181181    class BaseGraphComponent : public BaseDigraphComponent {
    182182    public:
     183
     184      typedef BaseGraphComponent Graph;
     185
    183186      typedef BaseDigraphComponent::Node Node;
    184187      typedef BaseDigraphComponent::Arc Arc;
    … …  
    190193      /// represented by two opposite directed arcs.
    191194      class Edge : public GraphItem<'e'> {
     195        typedef GraphItem<'e'> Parent;
     196
    192197      public:
    193         typedef GraphItem<'e'> Parent;
    194 
    195198        /// \brief Default constructor.
    196199        ///
    … …  
    992995    template <typename GR, typename K, typename V>
    993996    class GraphMap : public ReferenceMap<K, V, V&, const V&> {
    994     public:
    995 
    996       typedef ReadWriteMap<K, V> Parent;
    997 
    998       /// The graph type of the map.
    999       typedef GR Graph;
     997      typedef ReferenceMap<K, V, V&, const V&> Parent;
     998
     999    public:
     1000
    10001001      /// The key type of the map.
    10011002      typedef K Key;
    … …  
    10131014      ///
    10141015      /// Construct a new map for the graph.
    1015       explicit GraphMap(const Graph&) {}
     1016      explicit GraphMap(const GR&) {}
    10161017      /// \brief Construct a new map with default value.
    10171018      ///
    10181019      /// Construct a new map for the graph and initalize the values.
    1019       GraphMap(const Graph&, const Value&) {}
     1020      GraphMap(const GR&, const Value&) {}
    10201021
    10211022    private:
    … …  
    10581059
    10591060        const _Map &m;
    1060         const Graph &g;
     1061        const GR &g;
    10611062        const typename GraphMap::Value &t;
    10621063      };
    … …  
    10861087      template <typename V>
    10871088      class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> {
     1089        typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
     1090
    10881091      public:
    1089         typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
    1090 
    10911092        /// \brief Construct a new map.
    10921093        ///
    … …  
    11241125      template <typename V>
    11251126      class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> {
     1127        typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
     1128
    11261129      public:
    1127         typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
    1128 
    11291130        /// \brief Construct a new map.
    11301131        ///
    … …  
    12221223      template <typename V>
    12231224      class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> {
     1225        typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
     1226
    12241227      public:
    1225         typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
    1226 
    12271228        /// \brief Construct a new map.
    12281229        ///

  • lemon/core.h

    r628 r664  
    10371037  template <typename GR>
    10381038  class ConArcIt : public GR::Arc {
     1039    typedef typename GR::Arc Parent;
     1040
    10391041  public:
    10401042
    1041     typedef GR Graph;
    1042     typedef typename Graph::Arc Parent;
    1043 
    1044     typedef typename Graph::Arc Arc;
    1045     typedef typename Graph::Node Node;
     1043    typedef typename GR::Arc Arc;
     1044    typedef typename GR::Node Node;
    10461045
    10471046    /// \brief Constructor.
    … …  
    10491048    /// Construct a new ConArcIt iterating on the arcs that
    10501049    /// connects nodes \c u and \c v.
    1051     ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
     1050    ConArcIt(const GR& g, Node u, Node v) : _graph(g) {
    10521051      Parent::operator=(findArc(_graph, u, v));
    10531052    }
    … …  
    10561055    ///
    10571056    /// Construct a new ConArcIt that continues the iterating from arc \c a.
    1058     ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
     1057    ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {}
    10591058
    10601059    /// \brief Increment operator.
    … …  
    10671066    }
    10681067  private:
    1069     const Graph& _graph;
     1068    const GR& _graph;
    10701069  };
    10711070
    … …  
    11601159  template <typename GR>
    11611160  class ConEdgeIt : public GR::Edge {
     1161    typedef typename GR::Edge Parent;
     1162
    11621163  public:
    11631164
    1164     typedef GR Graph;
    1165     typedef typename Graph::Edge Parent;
    1166 
    1167     typedef typename Graph::Edge Edge;
    1168     typedef typename Graph::Node Node;
     1165    typedef typename GR::Edge Edge;
     1166    typedef typename GR::Node Node;
    11691167
    11701168    /// \brief Constructor.
    … …  
    11721170    /// Construct a new ConEdgeIt iterating on the edges that
    11731171    /// connects nodes \c u and \c v.
    1174     ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
     1172    ConEdgeIt(const GR& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
    11751173      Parent::operator=(findEdge(_graph, _u, _v));
    11761174    }
    … …  
    11791177    ///
    11801178    /// Construct a new ConEdgeIt that continues iterating from edge \c e.
    1181     ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
     1179    ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {}
    11821180
    11831181    /// \brief Increment operator.
    … …  
    11891187    }
    11901188  private:
    1191     const Graph& _graph;
     1189    const GR& _graph;
    11921190    Node _u, _v;
    11931191  };
    … …  
    12201218    : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
    12211219  {
    1222   public:
    12231220    typedef typename ItemSetTraits<GR, typename GR::Arc>
    12241221    ::ItemNotifier::ObserverBase Parent;
    12251222
    12261223    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1224
     1225  public:
     1226
     1227    /// The Digraph type
    12271228    typedef GR Digraph;
    12281229
    … …  
    12301231
    12311232    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
     1233      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
     1234
    12321235    public:
    1233 
    1234       typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
    12351236
    12361237      AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
    … …  
    12571258      }
    12581259    };
    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;
    12651260
    12661261    class ArcLess {
    … …  
    12731268      }
    12741269    };
     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;
    12751278
    12761279  public:
    … …  
    16311634  class ArcLookUp
    16321635  {
     1636    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1637
    16331638  public:
    1634     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1639
     1640    /// The Digraph type
    16351641    typedef GR Digraph;
    16361642
    … …  
    17471753
    17481754    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    1749     typedef GR Digraph;
    1750 
    1751     typename Digraph::template ArcMap<Arc> _next;
     1755
     1756    typename GR::template ArcMap<Arc> _next;
    17521757
    17531758    Arc refreshNext(Arc head,Arc next=INVALID)
    … …  
    17681773
    17691774  public:
     1775
     1776    /// The Digraph type
     1777    typedef GR Digraph;
     1778
    17701779    ///Constructor
    17711780

  • lemon/edge_set.h

    r606 r664  
    3434  public:
    3535
    36     typedef GR Graph;
    3736    typedef typename GR::Node Node;
    3837    typedef typename GR::NodeIt NodeIt;
    … …  
    209208    template <typename V>
    210209    class NodeMap : public GR::template NodeMap<V> {
     210      typedef typename GR::template NodeMap<V> Parent;
     211
    211212    public:
    212 
    213       typedef typename GR::template NodeMap<V> Parent;
    214213
    215214      explicit NodeMap(const ListArcSetBase<GR>& arcset)
    … …  
    260259  template <typename GR>
    261260  class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
    262 
    263   public:
    264 
    265261    typedef ArcSetExtender<ListArcSetBase<GR> > Parent;
     262
     263  public:
    266264
    267265    typedef typename Parent::Node Node;
    268266    typedef typename Parent::Arc Arc;
    269 
    270     typedef GR Graph;
    271 
    272267
    273268    typedef typename Parent::NodesImplBase NodesImplBase;
    … …  
    293288
    294289    class NodesImpl : public NodesImplBase {
     290      typedef NodesImplBase Parent;
     291
    295292    public:
    296       typedef NodesImplBase Parent;
    297 
    298293      NodesImpl(const GR& graph, ListArcSet& arcset)
    299294        : Parent(graph), _arcset(arcset) {}
    … …  
    355350  public:
    356351
    357     typedef GR Graph;
    358352    typedef typename GR::Node Node;
    359353    typedef typename GR::NodeIt NodeIt;
    … …  
    638632    template <typename V>
    639633    class NodeMap : public GR::template NodeMap<V> {
     634      typedef typename GR::template NodeMap<V> Parent;
     635
    640636    public:
    641 
    642       typedef typename GR::template NodeMap<V> Parent;
    643637
    644638      explicit NodeMap(const ListEdgeSetBase<GR>& arcset)
    … …  
    689683  template <typename GR>
    690684  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
    691 
    692   public:
    693 
    694685    typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;
     686
     687  public:
    695688
    696689    typedef typename Parent::Node Node;
    697690    typedef typename Parent::Arc Arc;
    698691    typedef typename Parent::Edge Edge;
    699 
    700     typedef GR Graph;
    701 
    702692
    703693    typedef typename Parent::NodesImplBase NodesImplBase;
    … …  
    718708
    719709    class NodesImpl : public NodesImplBase {
     710      typedef NodesImplBase Parent;
     711
    720712    public:
    721       typedef NodesImplBase Parent;
    722 
    723713      NodesImpl(const GR& graph, ListEdgeSet& arcset)
    724714        : Parent(graph), _arcset(arcset) {}
    … …  
    780770  public:
    781771
    782     typedef GR Graph;
    783     typedef typename Graph::Node Node;
    784     typedef typename Graph::NodeIt NodeIt;
     772    typedef typename GR::Node Node;
     773    typedef typename GR::NodeIt NodeIt;
    785774
    786775  protected:
    … …  
    901890    template <typename V>
    902891    class NodeMap : public GR::template NodeMap<V> {
     892      typedef typename GR::template NodeMap<V> Parent;
     893
    903894    public:
    904 
    905       typedef typename GR::template NodeMap<V> Parent;
    906895
    907896      explicit NodeMap(const SmartArcSetBase<GR>& arcset)
    … …  
    957946  template <typename GR>
    958947  class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
    959 
    960   public:
    961 
    962948    typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;
     949
     950  public:
    963951
    964952    typedef typename Parent::Node Node;
    965953    typedef typename Parent::Arc Arc;
    966 
    967     typedef GR Graph;
    968954
    969955  protected:
    … …  
    984970
    985971    class NodesImpl : public NodesImplBase {
     972      typedef NodesImplBase Parent;
     973
    986974    public:
    987       typedef NodesImplBase Parent;
    988 
    989975      NodesImpl(const GR& graph, SmartArcSet& arcset)
    990976        : Parent(graph), _arcset(arcset) {}
    … …  
    10631049  public:
    10641050
    1065     typedef GR Graph;
    10661051    typedef typename GR::Node Node;
    10671052    typedef typename GR::NodeIt NodeIt;
    … …  
    12501235    template <typename V>
    12511236    class NodeMap : public GR::template NodeMap<V> {
     1237      typedef typename GR::template NodeMap<V> Parent;
     1238
    12521239    public:
    1253 
    1254       typedef typename GR::template NodeMap<V> Parent;
    12551240
    12561241      explicit NodeMap(const SmartEdgeSetBase<GR>& arcset)
    … …  
    13051290  template <typename GR>
    13061291  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
    1307 
    1308   public:
    1309 
    13101292    typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;
     1293
     1294  public:
    13111295
    13121296    typedef typename Parent::Node Node;
    … …  
    13141298    typedef typename Parent::Edge Edge;
    13151299
    1316     typedef GR Graph;
    1317 
    13181300  protected:
    13191301
    … …  
    13321314
    13331315    class NodesImpl : public NodesImplBase {
     1316      typedef NodesImplBase Parent;
     1317
    13341318    public:
    1335       typedef NodesImplBase Parent;
    1336 
    13371319      NodesImpl(const GR& graph, SmartEdgeSet& arcset)
    13381320        : Parent(graph), _arcset(arcset) {}

  • lemon/full_graph.h

    r629 r664  
    3232  public:
    3333
    34     typedef FullDigraphBase Graph;
     34    typedef FullDigraphBase Digraph;
    3535
    3636    class Node;
    … …  
    170170  /// \sa FullGraph
    171171  class FullDigraph : public ExtendedFullDigraphBase {
     172    typedef ExtendedFullDigraphBase Parent;
     173
    172174  public:
    173 
    174     typedef ExtendedFullDigraphBase Parent;
    175175
    176176    /// \brief Constructor
    … …  
    227227
    228228  class FullGraphBase {
    229     int _node_num;
    230     int _edge_num;
    231229  public:
    232230
    … …  
    238236
    239237  protected:
     238
     239    int _node_num;
     240    int _edge_num;
    240241
    241242    FullGraphBase() {}
    … …  
    538539  /// \sa FullDigraph
    539540  class FullGraph : public ExtendedFullGraphBase {
     541    typedef ExtendedFullGraphBase Parent;
     542
    540543  public:
    541 
    542     typedef ExtendedFullGraphBase Parent;
    543544
    544545    /// \brief Constructor

  • lemon/graph_to_eps.h

    r631 r664  
    7070{
    7171  typedef GR Graph;
     72  typedef GR Digraph;
    7273  typedef typename Graph::Node Node;
    7374  typedef typename Graph::NodeIt NodeIt;
    … …  
    242243
    243244  typedef typename T::Graph Graph;
     245  typedef typename T::Digraph Digraph;
    244246  typedef typename Graph::Node Node;
    245247  typedef typename Graph::NodeIt NodeIt;

  • lemon/grid_graph.h

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

  • lemon/hypercube_graph.h

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

  • lemon/list_graph.h

    r629 r664  
    324324
    325325  class ListDigraph : public ExtendedListDigraphBase {
     326    typedef ExtendedListDigraphBase Parent;
     327
    326328  private:
    327329    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
    … …  
    337339    void operator=(const ListDigraph &) {}
    338340  public:
    339 
    340     typedef ExtendedListDigraphBase Parent;
    341341
    342342    /// Constructor
    … …  
    794794  public:
    795795
    796     typedef ListGraphBase Digraph;
     796    typedef ListGraphBase Graph;
    797797
    798798    class Node;
    … …  
    11771177
    11781178  class ListGraph : public ExtendedListGraphBase {
     1179    typedef ExtendedListGraphBase Parent;
     1180
    11791181  private:
    11801182    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
    … …  
    11951197    ///
    11961198    ListGraph() {}
    1197 
    1198     typedef ExtendedListGraphBase Parent;
    11991199
    12001200    typedef Parent::OutArcIt IncEdgeIt;

  • lemon/maps.h

    r631 r664  
    18391839    /// The graph type of IdMap.
    18401840    typedef GR Graph;
     1841    typedef GR Digraph;
    18411842    /// The key type of IdMap (\c Node, \c Arc or \c Edge).
    18421843    typedef K Item;
    … …  
    19301931    /// The graph type of CrossRefMap.
    19311932    typedef GR Graph;
     1933    typedef GR Digraph;
    19321934    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
    19331935    typedef K Item;
    … …  
    21332135    /// The graph type of RangeIdMap.
    21342136    typedef GR Graph;
     2137    typedef GR Digraph;
    21352138    /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge).
    21362139    typedef K Item;
    … …  
    24952498  public:
    24962499   
    2497     /// The digraph type
     2500    /// The graph type of InDegMap
     2501    typedef GR Graph;
    24982502    typedef GR Digraph;
    24992503    /// The key type
    … …  
    26242628  public:
    26252629
    2626     /// The digraph type
     2630    /// The graph type of OutDegMap
     2631    typedef GR Graph;
    26272632    typedef GR Digraph;
    26282633    /// The key type

  • lemon/network_simplex.h

    r656 r665  
    382382        const int MIN_BLOCK_SIZE = 10;
    383383
    384         _block_size = std::max( int(BLOCK_SIZE_FACTOR * sqrt(_arc_num)),
     384        _block_size = std::max( int(BLOCK_SIZE_FACTOR *
     385                                    std::sqrt(double(_arc_num))),
    385386                                MIN_BLOCK_SIZE );
    386387      }
    … …  
    458459        const int MIN_MINOR_LIMIT = 3;
    459460
    460         _list_length = std::max( int(LIST_LENGTH_FACTOR * sqrt(_arc_num)),
     461        _list_length = std::max( int(LIST_LENGTH_FACTOR *
     462                                     std::sqrt(double(_arc_num))),
    461463                                 MIN_LIST_LENGTH );
    462464        _minor_limit = std::max( int(MINOR_LIMIT_FACTOR * _list_length),
    … …  
    578580        const int MIN_HEAD_LENGTH = 3;
    579581
    580         _block_size = std::max( int(BLOCK_SIZE_FACTOR * sqrt(_arc_num)),
     582        _block_size = std::max( int(BLOCK_SIZE_FACTOR *
     583                                    std::sqrt(double(_arc_num))),
    581584                                MIN_BLOCK_SIZE );
    582585        _head_length = std::max( int(HEAD_LENGTH_FACTOR * _block_size),
    … …  
    11451148      // Run Circulation to check if a feasible solution exists
    11461149      typedef ConstMap<Arc, Flow> ConstArcMap;
     1150      ConstArcMap zero_arc_map(0), inf_arc_map(inf_cap);
    11471151      FlowNodeMap *csup = NULL;
    11481152      bool local_csup = false;
    … …  
    11651169          } else {
    11661170            Circulation<GR, FlowArcMap, ConstArcMap, FlowNodeMap>
    1167               circ(_graph, *_plower, ConstArcMap(inf_cap), *csup);
     1171              circ(_graph, *_plower, inf_arc_map, *csup);
    11681172            circ_result = circ.run();
    11691173          }
    … …  
    11711175          if (_pupper) {
    11721176            Circulation<GR, ConstArcMap, FlowArcMap, FlowNodeMap>
    1173               circ(_graph, ConstArcMap(0), *_pupper, *csup);
     1177              circ(_graph, zero_arc_map, *_pupper, *csup);
    11741178            circ_result = circ.run();
    11751179          } else {
    11761180            Circulation<GR, ConstArcMap, ConstArcMap, FlowNodeMap>
    1177               circ(_graph, ConstArcMap(0), ConstArcMap(inf_cap), *csup);
     1181              circ(_graph, zero_arc_map, inf_arc_map, *csup);
    11781182            circ_result = circ.run();
    11791183          }
    … …  
    11921196          } else {
    11931197            Circulation<RevGraph, FlowArcMap, ConstArcMap, NegNodeMap>
    1194               circ(rgraph, *_plower, ConstArcMap(inf_cap), neg_csup);
     1198              circ(rgraph, *_plower, inf_arc_map, neg_csup);
    11951199            circ_result = circ.run();
    11961200          }
    … …  
    11981202          if (_pupper) {
    11991203            Circulation<RevGraph, ConstArcMap, FlowArcMap, NegNodeMap>
    1200               circ(rgraph, ConstArcMap(0), *_pupper, neg_csup);
     1204              circ(rgraph, zero_arc_map, *_pupper, neg_csup);
    12011205            circ_result = circ.run();
    12021206          } else {
    12031207            Circulation<RevGraph, ConstArcMap, ConstArcMap, NegNodeMap>
    1204               circ(rgraph, ConstArcMap(0), ConstArcMap(inf_cap), neg_csup);
     1208              circ(rgraph, zero_arc_map, inf_arc_map, neg_csup);
    12051209            circ_result = circ.run();
    12061210          }
    … …  
    12261230
    12271231      // Store the arcs in a mixed order
    1228       int k = std::max(int(sqrt(_arc_num)), 10);
     1232      int k = std::max(int(std::sqrt(double(_arc_num))), 10);
    12291233      int i = 0;
    12301234      for (ArcIt e(_graph); e != INVALID; ++e) {

  • lemon/smart_graph.h

    r629 r664  
    5656  public:
    5757
    58     typedef SmartDigraphBase Graph;
     58    typedef SmartDigraphBase Digraph;
    5959
    6060    class Node;
    … …  
    196196  ///\sa concepts::Digraph.
    197197  class SmartDigraph : public ExtendedSmartDigraphBase {
    198   public:
    199 
    200198    typedef ExtendedSmartDigraphBase Parent;
    201199
    … …  
    421419  public:
    422420
    423     typedef SmartGraphBase Digraph;
     421    typedef SmartGraphBase Graph;
    424422
    425423    class Node;
    … …  
    632630  /// \sa concepts::Graph.
    633631  class SmartGraph : public ExtendedSmartGraphBase {
     632    typedef ExtendedSmartGraphBase Parent;
     633
    634634  private:
    635635
    … …  
    648648
    649649  public:
    650 
    651     typedef ExtendedSmartGraphBase Parent;
    652650
    653651    /// Constructor

  • lemon/suurballe.h

    r631 r670  
    2626
    2727#include <vector>
     28#include <limits>
    2829#include <lemon/bin_heap.h>
    2930#include <lemon/path.h>
    … …  
    4344  /// from a given source node to a given target node in a digraph.
    4445  ///
    45   /// In fact, this implementation is the specialization of the
    46   /// \ref CapacityScaling "successive shortest path" algorithm.
     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.
    4753  ///
    4854  /// \tparam GR The digraph type the algorithm runs on.
    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>.
     55  /// \tparam LEN The type of the length map.
     56  /// The default value is <tt>GR::ArcMap<int></tt>.
    5257  ///
    5358  /// \warning Length values should be \e non-negative \e integers.
    5459  ///
    5560  /// \note For finding node-disjoint paths this algorithm can be used
    56   /// with \ref SplitNodes.
     61  /// along with the \ref SplitNodes adaptor.
    5762#ifdef DOXYGEN
    5863  template <typename GR, typename LEN>
    5964#else
    60   template < typename GR = ListDigraph,
     65  template < typename GR,
    6166             typename LEN = typename GR::template ArcMap<int> >
    6267#endif
    … …  
    7681    /// The type of the lengths.
    7782    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
    7889    /// The type of the flow map.
    7990    typedef typename Digraph::template ArcMap<int> FlowMap;
    8091    /// The type of the potential map.
    8192    typedef typename Digraph::template NodeMap<Length> PotentialMap;
     93#endif
     94
    8295    /// The type of the path structures.
    83     typedef SimplePath<Digraph> Path;
     96    typedef SimplePath<GR> Path;
    8497
    8598  private:
    8699
    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.
     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.
    95105    class ResidualDijkstra
    96106    {
    … …  
    121131
    122132      /// Constructor.
    123       ResidualDijkstra( const Digraph &digraph,
     133      ResidualDijkstra( const Digraph &graph,
    124134                        const FlowMap &flow,
    125135                        const LengthMap &length,
    … …  
    127137                        PredMap &pred,
    128138                        Node s, Node t ) :
    129         _graph(digraph), _flow(flow), _length(length), _potential(potential),
    130         _dist(digraph), _pred(pred), _s(s), _t(t) {}
     139        _graph(graph), _flow(flow), _length(length), _potential(potential),
     140        _dist(graph), _pred(pred), _s(s), _t(t) {}
    131141
    132142      /// \brief Run the algorithm. It returns \c true if a path is found
    … …  
    237247    /// Constructor.
    238248    ///
    239     /// \param digraph The digraph the algorithm runs on.
     249    /// \param graph The digraph the algorithm runs on.
    240250    /// \param length The length (cost) values of the arcs.
    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) {}
     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    }
    249259
    250260    /// Destructor.
    … …  
    258268    ///
    259269    /// This function sets the flow map.
    260     ///
    261     /// The found flow contains only 0 and 1 values. It is the union of
    262     /// the found arc-disjoint paths.
     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.
    263276    ///
    264277    /// \return <tt>(*this)</tt>
    … …  
    275288    ///
    276289    /// This function sets the potential map.
    277     ///
    278     /// The potentials provide the dual solution of the underlying
    279     /// minimum cost flow problem.
     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".
    280296    ///
    281297    /// \return <tt>(*this)</tt>
    … …  
    302318    /// This function runs the algorithm.
    303319    ///
     320    /// \param s The source node.
     321    /// \param t The target node.
    304322    /// \param k The number of paths to be found.
    305323    ///
    … …  
    308326    /// arc-disjoint paths found.
    309327    ///
    310     /// \note Apart from the return value, <tt>s.run(k)</tt> is just a
    311     /// shortcut of the following code.
     328    /// \note Apart from the return value, <tt>s.run(s, t, k)</tt> is
     329    /// just a shortcut of the following code.
    312330    /// \code
    313     ///   s.init();
    314     ///   s.findFlow(k);
     331    ///   s.init(s);
     332    ///   s.findFlow(t, k);
    315333    ///   s.findPaths();
    316334    /// \endcode
    317     int run(int k = 2) {
    318       init();
    319       findFlow(k);
     335    int run(const Node& s, const Node& t, int k = 2) {
     336      init(s);
     337      findFlow(t, k);
    320338      findPaths();
    321339      return _path_num;
    … …  
    325343    ///
    326344    /// This function initializes the algorithm.
    327     void init() {
     345    ///
     346    /// \param s The source node.
     347    void init(const Node& s) {
     348      _source = s;
     349
    328350      // Initialize maps
    329351      if (!_flow) {
    … …  
    337359      for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
    338360      for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
    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.
     361    }
     362
     363    /// \brief Execute the algorithm to find an optimal flow.
    347364    ///
    348365    /// This function executes the successive shortest path algorithm to
    349     /// find a minimum cost flow, which is the union of \c k or less
     366    /// find a minimum cost flow, which is the union of \c k (or less)
    350367    /// arc-disjoint paths.
    351368    ///
     369    /// \param t The target node.
     370    /// \param k The number of paths to be found.
     371    ///
    352372    /// \return \c k if there are at least \c k arc-disjoint paths from
    353     /// \c s to \c t in the digraph. Otherwise it returns the number of
    354     /// arc-disjoint paths found.
     373    /// the source node to the given node \c t in the digraph.
     374    /// Otherwise it returns the number of arc-disjoint paths found.
    355375    ///
    356376    /// \pre \ref init() must be called before using this function.
    357     int findFlow(int k = 2) {
     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
    358383      // Find shortest paths
    359384      _path_num = 0;
    … …  
    381406    /// \brief Compute the paths from the flow.
    382407    ///
    383     /// This function computes the paths from the flow.
     408    /// This function computes the paths from the found minimum cost flow,
     409    /// which is the union of some arc-disjoint paths.
    384410    ///
    385411    /// \pre \ref init() and \ref findFlow() must be called before using
    386412    /// this function.
    387413    void findPaths() {
    388       // Create the residual flow map (the union of the paths not found
    389       // so far)
    390414      FlowMap res_flow(_graph);
    391415      for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];
    … …  
    414438    /// @{
    415439
    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).
     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).
    467445    ///
    468446    /// \pre \ref run() or \ref findFlow() must be called before using
    … …  
    475453    }
    476454
     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
    477504    /// \brief Return the number of the found paths.
    478505    ///
    … …  
    489516    /// This function returns a const reference to the specified path.
    490517    ///
    491     /// \param i The function returns the \c i-th path.
     518    /// \param i The function returns the <tt>i</tt>-th path.
    492519    /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.
    493520    ///

  • test/min_cost_flow_test.cc

    r656 r662  
    234234    typedef int Flow;
    235235    typedef int Cost;
    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 /**/
     236    typedef concepts::Digraph GR;
    242237    checkConcept< McfClassConcept<GR, Flow, Cost>,
    243238                  NetworkSimplex<GR, Flow, Cost> >();

  • test/suurballe_test.cc

    r463 r670  
    2323#include <lemon/path.h>
    2424#include <lemon/suurballe.h>
     25#include <lemon/concepts/digraph.h>
    2526
    2627#include "test_tools.h"
    … …  
    3031char test_lgf[] =
    3132  "@nodes\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"
     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"
    4546  "@arcs\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"
     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"
    6869  "@attributes\n"
    6970  "source  1\n"
    7071  "target 12\n"
    7172  "@end\n";
     73
     74// Check the interface of Suurballe
     75void 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}
    72123
    73124// Check the feasibility of the flow
    … …  
    119170                typename Digraph::Node s, typename Digraph::Node t)
    120171{
    121   // Check the "Complementary Slackness" optimality condition
    122172  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    123173  Node n = s;
    … …  
    137187  ListDigraph digraph;
    138188  ListDigraph::ArcMap<int> length(digraph);
    139   Node source, target;
     189  Node s, t;
    140190
    141191  std::istringstream input(test_lgf);
    142192  DigraphReader<ListDigraph>(digraph, input).
    143     arcMap("cost", length).
    144     node("source", source).
    145     node("target", target).
     193    arcMap("length", length).
     194    node("source", s).
     195    node("target", t).
    146196    run();
    147197
    148198  // Find 2 paths
    149199  {
    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),
     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),
    153203          "The flow is not feasible");
    154204    check(suurballe.totalLength() == 510, "The flow is not optimal");
    … …  
    157207          "Wrong potentials");
    158208    for (int i = 0; i < suurballe.pathNum(); ++i)
    159       check(checkPath(digraph, suurballe.path(i), source, target),
    160             "Wrong path");
     209      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    161210  }
    162211
    163212  // Find 3 paths
    164213  {
    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),
     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),
    168217          "The flow is not feasible");
    169218    check(suurballe.totalLength() == 1040, "The flow is not optimal");
    … …  
    172221          "Wrong potentials");
    173222    for (int i = 0; i < suurballe.pathNum(); ++i)
    174       check(checkPath(digraph, suurballe.path(i), source, target),
    175             "Wrong path");
     223      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    176224  }
    177225
    178226  // Find 5 paths (only 3 can be found)
    179227  {
    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),
     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),
    183231          "The flow is not feasible");
    184232    check(suurballe.totalLength() == 1040, "The flow is not optimal");
    … …  
    187235          "Wrong potentials");
    188236    for (int i = 0; i < suurballe.pathNum(); ++i)
    189       check(checkPath(digraph, suurballe.path(i), source, target),
    190             "Wrong path");
     237      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    191238  }
    192239

  • tools/dimacs-solver.cc

    r658 r661  
    9494template<class Value>
    9595void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
    96                DimacsDescriptor &desc)
     96               Value infty, DimacsDescriptor &desc)
    9797{
    9898  bool report = !ap.given("q");
    … …  
    101101  Digraph::NodeMap<Value> sup(g);
    102102  Timer ti;
    103   ti.restart();
    104   readDimacsMin(is, g, lower, cap, cost, sup, 0, desc);
     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  }
    105118  if (report) std::cerr << "Read the file: " << ti << '\n';
     119
    106120  ti.restart();
    107121  NetworkSimplex<Digraph, Value> ns(g);
    108122  ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
     123  if (sum_sup > 0) ns.problemType(ns.LEQ);
    109124  if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
    110125  ti.restart();
    111   ns.run();
    112   if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n';
    113   if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n';
     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  }
    114132}
    115133
    … …  
    152170    {
    153171    case DimacsDescriptor::MIN:
    154       solve_min<Value>(ap,is,os,desc);
     172      solve_min<Value>(ap,is,os,infty,desc);
    155173      break;
    156174    case DimacsDescriptor::MAX:

  • tools/lgf-gen.cc

    r631 r670  
    6666  double tlen=0;
    6767  for(EdgeIt e(g);e!=INVALID;++e)
    68     tlen+=sqrt((coords[g.v(e)]-coords[g.u(e)]).normSquare());
     68    tlen+=std::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) + sqrt((d * d + e * e) / (4 * a * a) + f / a);
     191    return d / (2 * a) + std::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 - sqrt(d)) / a;
     209    return (b - std::sqrt(d)) / a;
    210210  }
    211211
    … …  
    481481      g.erase(*ei);
    482482      ConstMap<Arc,int> cegy(1);
    483       Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy,a,b);
    484       int k=sur.run(2);
     483      Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy);
     484      int k=sur.run(a,b,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> >
    515           sur(g,cegy,pi->a,pi->b);
    516         int k=sur.run(2);
     514        Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy);
     515        int k=sur.run(pi->a,pi->b,2);
    517516        if(k<2 || sur.totalLength()>d)
    518517          {
    … …  
    721720
    722721  if (ap["rand"]) {
    723     int seed = time(0);
     722    int seed = int(time(0));
    724723    std::cout << "Random number seed: " << seed << std::endl;
    725724    rnd = Random(seed);
    … …  
    814813  double tlen=0;
    815814  for(EdgeIt e(g);e!=INVALID;++e)
    816     tlen+=sqrt((coords[g.v(e)]-coords[g.u(e)]).normSquare());
     815    tlen+=std::sqrt((coords[g.v(e)]-coords[g.u(e)]).normSquare());
    817816  std::cout << "Total arc length  : " << tlen << std::endl;
    818817
Note: See TracChangeset for help on using the changeset viewer.