COIN-OR::LEMON - Graph Library

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


Ignore:
Files:
28 edited

Legend:

Unmodified
Added
Removed
  • demo/graph_to_eps_demo.cc

    r440 r612  
    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

    r579 r617  
    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

    r492 r617  
    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

    r440 r617  
    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

    r535 r617  
    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

    r559 r617  
    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

    r580 r617  
    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

    r440 r617  
    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

    r580 r617  
    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

    r440 r616  
    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

    r492 r617  
    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

    r611 r622  
    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

    r584 r617  
    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

    r581 r617  
    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

    r559 r617  
    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

    r582 r617  
    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

    r584 r617  
    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

    r582 r617  
    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

    r582 r617  
    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

    r582 r617  
    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

    r584 r617  
    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

    r609 r618  
    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

    r582 r617  
    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

    r584 r623  
    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

    r609 r615  
    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

    r440 r623  
    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

    r611 r614  
    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

    r584 r623  
    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.