COIN-OR::LEMON - Graph Library

Changeset 970:d216e1c8b3fa in lemon-1.2


Ignore:
Timestamp:
11/28/12 11:54:43 (7 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
965:00f8d9f9920d (diff), 969:7e368d9b67f7 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge #453 to branches >=1.2

Files:
24 edited

Legend:

Unmodified
Added
Removed
  • lemon/concepts/graph_components.h

    r964 r970  
    109109
    110110          bool b;
     111          ignore_unused_variable_warning(b);
     112
    111113          b = (ia == ib) && (ia != ib);
    112114          b = (ia == INVALID) && (ib != INVALID);
  • lemon/concepts/graph_components.h

    r969 r970  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1919///\ingroup graph_concepts
    2020///\file
    21 ///\brief The concept of graph components.
     21///\brief The concepts of graph components.
    2222
    2323#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
     
    3939    /// \note This class is a template class so that we can use it to
    4040    /// create graph skeleton classes. The reason for this is that \c Node
    41     /// and \c Arc (or \c Edge) types should \e not derive from the same 
     41    /// and \c Arc (or \c Edge) types should \e not derive from the same
    4242    /// base class. For \c Node you should instantiate it with character
    4343    /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
     
    9090      ///
    9191      /// This operator defines an ordering of the items.
    92       /// It makes possible to use graph item types as key types in 
     92      /// It makes possible to use graph item types as key types in
    9393      /// associative containers (e.g. \c std::map).
    9494      ///
    95       /// \note This operator only have to define some strict ordering of
     95      /// \note This operator only has to define some strict ordering of
    9696      /// the items; this order has nothing to do with the iteration
    9797      /// ordering of the items.
     
    126126    /// This class describes the base interface of directed graph types.
    127127    /// All digraph %concepts have to conform to this class.
    128     /// It just provides types for nodes and arcs and functions 
     128    /// It just provides types for nodes and arcs and functions
    129129    /// to get the source and the target nodes of arcs.
    130130    class BaseDigraphComponent {
     
    434434    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
    435435    ///
    436     /// This class describes the concept of \c NodeIt, \c ArcIt and 
     436    /// This class describes the concept of \c NodeIt, \c ArcIt and
    437437    /// \c EdgeIt subtypes of digraph and graph types.
    438438    template <typename GR, typename Item>
     
    474474      /// next item.
    475475      GraphItemIt& operator++() { return *this; }
    476  
     476
    477477      /// \brief Equality operator
    478478      ///
     
    512512    };
    513513
    514     /// \brief Concept class for \c InArcIt, \c OutArcIt and 
     514    /// \brief Concept class for \c InArcIt, \c OutArcIt and
    515515    /// \c IncEdgeIt types.
    516516    ///
    517     /// This class describes the concept of \c InArcIt, \c OutArcIt 
     517    /// This class describes the concept of \c InArcIt, \c OutArcIt
    518518    /// and \c IncEdgeIt subtypes of digraph and graph types.
    519519    ///
    520520    /// \note Since these iterator classes do not inherit from the same
    521521    /// base class, there is an additional template parameter (selector)
    522     /// \c sel. For \c InArcIt you should instantiate it with character 
     522    /// \c sel. For \c InArcIt you should instantiate it with character
    523523    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
    524524    template <typename GR,
     
    541541      GraphIncIt(const GraphIncIt& it) : Item(it) {}
    542542
    543       /// \brief Constructor that sets the iterator to the first 
     543      /// \brief Constructor that sets the iterator to the first
    544544      /// incoming or outgoing arc.
    545545      ///
    546       /// Constructor that sets the iterator to the first arc 
     546      /// Constructor that sets the iterator to the first arc
    547547      /// incoming to or outgoing from the given node.
    548548      explicit GraphIncIt(const GR&, const Base&) {}
     
    819819      /// \brief Return the first edge incident to the given node.
    820820      ///
    821       /// This function gives back the first edge incident to the given 
     821      /// This function gives back the first edge incident to the given
    822822      /// node. The bool parameter gives back the direction for which the
    823       /// source node of the directed arc representing the edge is the 
     823      /// source node of the directed arc representing the edge is the
    824824      /// given node.
    825825      void firstInc(Edge&, bool&, const Node&) const {}
     
    828828      /// given node.
    829829      ///
    830       /// This function gives back the next edge incident to the given 
     830      /// This function gives back the next edge incident to the given
    831831      /// node. The bool parameter should be used as \c firstInc() use it.
    832832      void nextInc(Edge&, bool&) const {}
     
    10081008    ///
    10091009    /// This class describes the concept of standard graph maps, i.e.
    1010     /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and 
     1010    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
    10111011    /// graph types, which can be used for associating data to graph items.
    10121012    /// The standard graph maps must conform to the ReferenceMap concept.
     
    10631063          _Map m1(g);
    10641064          _Map m2(g,t);
    1065          
     1065
    10661066          // Copy constructor
    10671067          // _Map m3(m);
     
    10871087    ///
    10881088    /// This class describes the interface of mappable directed graphs.
    1089     /// It extends \ref BaseDigraphComponent with the standard digraph 
     1089    /// It extends \ref BaseDigraphComponent with the standard digraph
    10901090    /// map classes, namely \c NodeMap and \c ArcMap.
    10911091    /// This concept is part of the Digraph concept.
     
    12251225    ///
    12261226    /// This class describes the interface of mappable undirected graphs.
    1227     /// It extends \ref MappableDigraphComponent with the standard graph 
     1227    /// It extends \ref MappableDigraphComponent with the standard graph
    12281228    /// map class for edges (\c EdgeMap).
    12291229    /// This concept is part of the Graph concept.
     
    13111311    ///
    13121312    /// This class describes the interface of extendable directed graphs.
    1313     /// It extends \ref BaseDigraphComponent with functions for adding 
     1313    /// It extends \ref BaseDigraphComponent with functions for adding
    13141314    /// nodes and arcs to the digraph.
    13151315    /// This concept requires \ref AlterableDigraphComponent.
     
    13561356    ///
    13571357    /// This class describes the interface of extendable undirected graphs.
    1358     /// It extends \ref BaseGraphComponent with functions for adding 
     1358    /// It extends \ref BaseGraphComponent with functions for adding
    13591359    /// nodes and edges to the graph.
    13601360    /// This concept requires \ref AlterableGraphComponent.
     
    14011401    ///
    14021402    /// This class describes the interface of erasable directed graphs.
    1403     /// It extends \ref BaseDigraphComponent with functions for removing 
     1403    /// It extends \ref BaseDigraphComponent with functions for removing
    14041404    /// nodes and arcs from the digraph.
    14051405    /// This concept requires \ref AlterableDigraphComponent.
     
    14141414      /// \brief Erase a node from the digraph.
    14151415      ///
    1416       /// This function erases the given node from the digraph and all arcs 
     1416      /// This function erases the given node from the digraph and all arcs
    14171417      /// connected to the node.
    14181418      void erase(const Node&) {}
     
    14411441    ///
    14421442    /// This class describes the interface of erasable undirected graphs.
    1443     /// It extends \ref BaseGraphComponent with functions for removing 
     1443    /// It extends \ref BaseGraphComponent with functions for removing
    14441444    /// nodes and edges from the graph.
    14451445    /// This concept requires \ref AlterableGraphComponent.
  • test/bfs_test.cc

    r877 r970  
    6262  Arc e;
    6363  int l, i;
     64  ignore_unused_variable_warning(l,i);
    6465  bool b;
    6566  BType::DistMap d(G);
     
    151152  Digraph g;
    152153  bool b;
     154  ignore_unused_variable_warning(b);
     155
    153156  bfs(g).run(Node());
    154157  b=bfs(g).run(Node(),Node());
  • test/bfs_test.cc

    r969 r970  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8585    b = const_bfs_test.emptyQueue();
    8686    i = const_bfs_test.queueSize();
    87    
     87
    8888    bfs_test.start();
    8989    bfs_test.start(t);
     
    106106      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
    107107      ::Create bfs_test(G);
    108      
     108
    109109    concepts::ReadWriteMap<Node,Arc> pred_map;
    110110    concepts::ReadWriteMap<Node,int> dist_map;
    111111    concepts::ReadWriteMap<Node,bool> reached_map;
    112112    concepts::WriteMap<Node,bool> processed_map;
    113    
     113
    114114    bfs_test
    115115      .predMap(pred_map)
     
    121121    bfs_test.run(s,t);
    122122    bfs_test.run();
    123    
     123
    124124    bfs_test.init();
    125125    bfs_test.addSource(s);
     
    130130    b = bfs_test.emptyQueue();
    131131    i = bfs_test.queueSize();
    132    
     132
    133133    bfs_test.start();
    134134    bfs_test.start(t);
  • test/circulation_test.cc

    r877 r970  
    7474  VType v;
    7575  bool b;
     76  ignore_unused_variable_warning(v,b);
    7677
    7778  typedef Circulation<Digraph, CapMap, CapMap, SupplyMap>
  • test/circulation_test.cc

    r969 r970  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8383  CirculationType circ_test(g, lcap, ucap, supply);
    8484  const CirculationType& const_circ_test = circ_test;
    85    
     85
    8686  circ_test
    8787    .lowerMap(lcap)
     
    8989    .supplyMap(supply)
    9090    .flowMap(flow);
     91
     92  const CirculationType::Elevator& elev = const_circ_test.elevator();
     93  circ_test.elevator(const_cast<CirculationType::Elevator&>(elev));
     94  CirculationType::Tolerance tol = const_circ_test.tolerance();
     95  circ_test.tolerance(tol);
    9196
    9297  circ_test.init();
     
    99104  b = const_circ_test.barrier(n);
    100105  const_circ_test.barrierMap(bar);
    101  
     106
    102107  ignore_unused_variable_warning(fm);
    103108}
  • test/dfs_test.cc

    r942 r970  
    6868  int l, i;
    6969  bool b;
     70  ignore_unused_variable_warning(l,i,b);
     71
    7072  DType::DistMap d(G);
    7173  DType::PredMap p(G);
     
    152154  Digraph g;
    153155  bool b;
     156  ignore_unused_variable_warning(b);
     157
    154158  dfs(g).run(Node());
    155159  b=dfs(g).run(Node(),Node());
  • test/dfs_test.cc

    r969 r970  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8989    b = const_dfs_test.emptyQueue();
    9090    i = const_dfs_test.queueSize();
    91    
     91
    9292    dfs_test.start();
    9393    dfs_test.start(t);
     
    115115    concepts::ReadWriteMap<Node,bool> reached_map;
    116116    concepts::WriteMap<Node,bool> processed_map;
    117    
     117
    118118    dfs_test
    119119      .predMap(pred_map)
     
    132132    b = dfs_test.emptyQueue();
    133133    i = dfs_test.queueSize();
    134    
     134
    135135    dfs_test.start();
    136136    dfs_test.start(t);
  • test/dijkstra_test.cc

    r877 r970  
    6666  int i;
    6767  bool b;
     68  ignore_unused_variable_warning(l,i,b);
     69
    6870  DType::DistMap d(G);
    6971  DType::PredMap p(G);
     
    163165  Digraph g;
    164166  bool b;
     167  ignore_unused_variable_warning(b);
     168
    165169  dijkstra(g,LengthMap()).run(Node());
    166170  b=dijkstra(g,LengthMap()).run(Node(),Node());
  • test/dijkstra_test.cc

    r969 r970  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8888    b = const_dijkstra_test.emptyQueue();
    8989    i = const_dijkstra_test.queueSize();
    90    
     90
    9191    dijkstra_test.start();
    9292    dijkstra_test.start(t);
     
    112112      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
    113113      ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
    114       ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >, 
     114      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >,
    115115                concepts::ReadWriteMap<Node,int> >
    116116      ::Create dijkstra_test(G,length);
     
    122122    concepts::ReadWriteMap<Node,int> heap_cross_ref;
    123123    BinHeap<VType, concepts::ReadWriteMap<Node,int> > heap(heap_cross_ref);
    124    
     124
    125125    dijkstra_test
    126126      .lengthMap(length_map)
     
    139139    b = dijkstra_test.emptyQueue();
    140140    i = dijkstra_test.queueSize();
    141    
     141
    142142    dijkstra_test.start();
    143143    dijkstra_test.start(t);
  • test/gomory_hu_test.cc

    r877 r970  
    6969  Value v;
    7070  int d;
     71  ignore_unused_variable_warning(v,d);
    7172
    7273  GomoryHu<Graph, CapMap> gh_test(g, cap);
  • test/gomory_hu_test.cc

    r969 r970  
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
     4 *
     5 * Copyright (C) 2003-2010
     6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8 *
     9 * Permission to use, modify and distribute this software is granted
     10 * provided that this copyright notice appears in all copies. For
     11 * precise terms see the accompanying LICENSE file.
     12 *
     13 * This software is provided "AS IS" with no warranty of any kind,
     14 * express or implied, and with no claim as to its suitability for any
     15 * purpose.
     16 *
     17 */
     18
    119#include <iostream>
    220
     
    3452  "source 0\n"
    3553  "target 3\n";
    36  
     54
    3755void checkGomoryHuCompile()
    3856{
     
    7189
    7290int cutValue(const Graph& graph, const BoolNodeMap& cut,
    73              const IntEdgeMap& capacity) {
     91             const IntEdgeMap& capacity) {
    7492
    7593  int sum = 0;
     
    109127      int sum=0;
    110128      for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
    111         sum+=capacity[a]; 
     129        sum+=capacity[a];
    112130      check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
    113131
     
    120138    }
    121139  }
    122  
     140
    123141  return 0;
    124142}
  • test/hao_orlin_test.cc

    r877 r970  
    6767  CutMap cut;
    6868  Value v;
     69  ignore_unused_variable_warning(v);
    6970
    7071  HaoOrlin<Digraph, CapMap> ho_test(g, cap);
  • test/hao_orlin_test.cc

    r969 r970  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8585
    8686template <typename Graph, typename CapMap, typename CutMap>
    87 typename CapMap::Value 
     87typename CapMap::Value
    8888  cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
    8989{
     
    112112    ho.run();
    113113    ho.minCutMap(cut);
    114    
     114
    115115    check(ho.minCutValue() == 1, "Wrong cut value");
    116116    check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
     
    128128    ho.run();
    129129    ho.minCutMap(cut);
    130    
     130
    131131    check(ho.minCutValue() == 1, "Wrong cut value");
    132132    check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
    133133  }
    134  
     134
    135135  typedef Undirector<SmartDigraph> UGraph;
    136136  UGraph ugraph(graph);
    137  
     137
    138138  {
    139139    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1);
    140140    ho.run();
    141141    ho.minCutMap(cut);
    142    
     142
    143143    check(ho.minCutValue() == 2, "Wrong cut value");
    144144    check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value");
     
    148148    ho.run();
    149149    ho.minCutMap(cut);
    150    
     150
    151151    check(ho.minCutValue() == 5, "Wrong cut value");
    152152    check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value");
     
    156156    ho.run();
    157157    ho.minCutMap(cut);
    158    
     158
    159159    check(ho.minCutValue() == 5, "Wrong cut value");
    160160    check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value");
  • test/matching_test.cc

    r877 r970  
    146146  MaxMatching<Graph>::Status stat =
    147147    const_mat_test.status(n);
     148  ignore_unused_variable_warning(stat);
    148149  const MaxMatching<Graph>::StatusMap& smap =
    149150    const_mat_test.statusMap();
  • test/matching_test.cc

    r969 r970  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    135135  mat_test.startDense();
    136136  mat_test.run();
    137  
     137
    138138  const_mat_test.matchingSize();
    139139  const_mat_test.matching(e);
     
    144144  const_mat_test.mate(n);
    145145
    146   MaxMatching<Graph>::Status stat = 
     146  MaxMatching<Graph>::Status stat =
    147147    const_mat_test.status(n);
    148148  ignore_unused_variable_warning(stat);
     
    172172  mat_test.start();
    173173  mat_test.run();
    174  
     174
    175175  const_mat_test.matchingWeight();
    176176  const_mat_test.matchingSize();
     
    181181  e = mmap[n];
    182182  const_mat_test.mate(n);
    183  
     183
    184184  int k = 0;
    185185  const_mat_test.dualValue();
     
    209209  mat_test.start();
    210210  mat_test.run();
    211  
     211
    212212  const_mat_test.matchingWeight();
    213213  const_mat_test.matching(e);
     
    217217  e = mmap[n];
    218218  const_mat_test.mate(n);
    219  
     219
    220220  int k = 0;
    221221  const_mat_test.dualValue();
     
    403403      edgeMap("weight", weight).run();
    404404
    405     MaxMatching<SmartGraph> mm(graph);
    406     mm.run();
    407     checkMatching(graph, mm);
    408 
    409     MaxWeightedMatching<SmartGraph> mwm(graph, weight);
    410     mwm.run();
    411     checkWeightedMatching(graph, weight, mwm);
    412 
    413     MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
    414     bool perfect = mwpm.run();
    415 
    416     check(perfect == (mm.matchingSize() * 2 == countNodes(graph)),
    417           "Perfect matching found");
    418 
    419     if (perfect) {
    420       checkWeightedPerfectMatching(graph, weight, mwpm);
     405    bool perfect;
     406    {
     407      MaxMatching<SmartGraph> mm(graph);
     408      mm.run();
     409      checkMatching(graph, mm);
     410      perfect = 2 * mm.matchingSize() == countNodes(graph);
     411    }
     412
     413    {
     414      MaxWeightedMatching<SmartGraph> mwm(graph, weight);
     415      mwm.run();
     416      checkWeightedMatching(graph, weight, mwm);
     417    }
     418
     419    {
     420      MaxWeightedMatching<SmartGraph> mwm(graph, weight);
     421      mwm.init();
     422      mwm.start();
     423      checkWeightedMatching(graph, weight, mwm);
     424    }
     425
     426    {
     427      MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
     428      bool result = mwpm.run();
     429
     430      check(result == perfect, "Perfect matching found");
     431      if (perfect) {
     432        checkWeightedPerfectMatching(graph, weight, mwpm);
     433      }
     434    }
     435
     436    {
     437      MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
     438      mwpm.init();
     439      bool result = mwpm.start();
     440
     441      check(result == perfect, "Perfect matching found");
     442      if (perfect) {
     443        checkWeightedPerfectMatching(graph, weight, mwpm);
     444      }
    421445    }
    422446  }
  • test/min_cost_arborescence_test.cc

    r877 r970  
    9292  VType c;
    9393  bool b;
     94  ignore_unused_variable_warning(c,b);
    9495  int i;
    9596  CostMap cost;
  • test/min_cost_arborescence_test.cc

    r969 r970  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    112112  b = const_mcarb_test.emptyQueue();
    113113  i = const_mcarb_test.queueSize();
    114  
     114
    115115  c = const_mcarb_test.arborescenceCost();
    116116  b = const_mcarb_test.arborescence(e);
     
    122122  b = const_mcarb_test.reached(n);
    123123  b = const_mcarb_test.processed(n);
    124  
     124
    125125  i = const_mcarb_test.dualNum();
    126126  c = const_mcarb_test.dualValue();
    127127  i = const_mcarb_test.dualSize(i);
    128128  c = const_mcarb_test.dualValue(i);
    129  
     129
    130130  ignore_unused_variable_warning(am);
    131131  ignore_unused_variable_warning(pm);
  • test/preflow_test.cc

    r902 r970  
    8787  VType v;
    8888  bool b;
     89  ignore_unused_variable_warning(v,b);
    8990
    9091  typedef Preflow<Digraph, CapMap>
  • test/preflow_test.cc

    r969 r970  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9797  const PreflowType& const_preflow_test = preflow_test;
    9898
     99  const PreflowType::Elevator& elev = const_preflow_test.elevator();
     100  preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
     101  PreflowType::Tolerance tol = const_preflow_test.tolerance();
     102  preflow_test.tolerance(tol);
     103
    99104  preflow_test
    100105    .capacityMap(cap)
     
    115120  b = const_preflow_test.minCut(n);
    116121  const_preflow_test.minCutMap(cut);
    117  
     122
    118123  ignore_unused_variable_warning(fm);
    119124}
  • test/suurballe_test.cc

    r877 r970  
    118118  int f;
    119119  VType c;
     120  ignore_unused_variable_warning(f,c);
     121
    120122  c = const_suurb_test.totalLength();
    121123  f = const_suurb_test.flow(e);
  • test/suurballe_test.cc

    r969 r970  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2424#include <lemon/suurballe.h>
    2525#include <lemon/concepts/digraph.h>
     26#include <lemon/concepts/heap.h>
    2627
    2728#include "test_tools.h"
     
    8182  typedef Digraph::Arc Arc;
    8283  typedef concepts::ReadMap<Arc, VType> LengthMap;
    83  
    84   typedef Suurballe<Digraph, LengthMap> SuurballeType;
     84
     85  typedef Suurballe<Digraph, LengthMap> ST;
     86  typedef Suurballe<Digraph, LengthMap>
     87    ::SetFlowMap<ST::FlowMap>
     88    ::SetPotentialMap<ST::PotentialMap>
     89    ::SetPath<SimplePath<Digraph> >
     90    ::SetHeap<concepts::Heap<VType, Digraph::NodeMap<int> > >
     91    ::Create SuurballeType;
    8592
    8693  Digraph g;
     
    102109  k = suurb_test.run(n, n, k);
    103110  suurb_test.init(n);
     111  suurb_test.fullInit(n);
     112  suurb_test.start(n);
     113  suurb_test.start(n, k);
    104114  k = suurb_test.findFlow(n);
    105115  k = suurb_test.findFlow(n, k);
    106116  suurb_test.findPaths();
    107  
     117
    108118  int f;
    109119  VType c;
     
    119129  k = const_suurb_test.pathNum();
    120130  Path<Digraph> p = const_suurb_test.path(k);
    121  
     131
    122132  ignore_unused_variable_warning(fm);
    123133  ignore_unused_variable_warning(pm);
     
    198208    run();
    199209
    200   // Find 2 paths
     210  // Check run()
    201211  {
    202212    Suurballe<ListDigraph> suurballe(digraph, length);
     213
     214    // Find 2 paths
    203215    check(suurballe.run(s, t) == 2, "Wrong number of paths");
    204216    check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
     
    210222    for (int i = 0; i < suurballe.pathNum(); ++i)
    211223      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    212   }
    213 
    214   // Find 3 paths
    215   {
    216     Suurballe<ListDigraph> suurballe(digraph, length);
     224
     225    // Find 3 paths
    217226    check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
    218227    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
     
    224233    for (int i = 0; i < suurballe.pathNum(); ++i)
    225234      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    226   }
    227 
    228   // Find 5 paths (only 3 can be found)
    229   {
    230     Suurballe<ListDigraph> suurballe(digraph, length);
     235
     236    // Find 5 paths (only 3 can be found)
    231237    check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
    232238    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
     
    240246  }
    241247
     248  // Check fullInit() + start()
     249  {
     250    Suurballe<ListDigraph> suurballe(digraph, length);
     251    suurballe.fullInit(s);
     252
     253    // Find 2 paths
     254    check(suurballe.start(t) == 2, "Wrong number of paths");
     255    check(suurballe.totalLength() == 510, "The flow is not optimal");
     256
     257    // Find 3 paths
     258    check(suurballe.start(t, 3) == 3, "Wrong number of paths");
     259    check(suurballe.totalLength() == 1040, "The flow is not optimal");
     260
     261    // Find 5 paths (only 3 can be found)
     262    check(suurballe.start(t, 5) == 3, "Wrong number of paths");
     263    check(suurballe.totalLength() == 1040, "The flow is not optimal");
     264  }
     265
    242266  return 0;
    243267}
  • tools/dimacs-solver.cc

    r877 r968  
    118118  if (report) std::cerr << "Read the file: " << ti << '\n';
    119119
    120   ti.restart();
    121   NetworkSimplex<Digraph, Value> ns(g);
     120  typedef NetworkSimplex<Digraph, Value> MCF;
     121  ti.restart();
     122  MCF ns(g);
    122123  ns.lowerMap(lower).upperMap(cap).costMap(cost).supplyMap(sup);
    123124  if (sum_sup > 0) ns.supplyType(ns.LEQ);
    124125  if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
    125126  ti.restart();
    126   bool res = ns.run();
     127  typename MCF::ProblemType res = ns.run();
    127128  if (report) {
    128129    std::cerr << "Run NetworkSimplex: " << ti << "\n\n";
    129     std::cerr << "Feasible flow: " << (res ? "found" : "not found") << '\n';
     130    std::cerr << "Feasible flow: " << (res == MCF::OPTIMAL ? "found" : "not found") << '\n';
    130131    if (res) std::cerr << "Min flow cost: "
    131132                       << ns.template totalCost<LargeValue>() << '\n';
     
    188189
    189190int main(int argc, const char *argv[]) {
    190   typedef SmartDigraph Digraph;
    191 
    192   typedef Digraph::Arc Arc;
    193191
    194192  std::string inputName;
  • tools/dimacs-solver.cc

    r967 r968  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8989  pre.run();
    9090  if(report) std::cerr << "Run Preflow: " << ti << '\n';
    91   if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; 
    92 }
    93 
    94 template<class Value>
     91  if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';
     92}
     93
     94template<class Value, class LargeValue>
    9595void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
    9696               Value infty, DimacsDescriptor &desc)
     
    129129    std::cerr << "Run NetworkSimplex: " << ti << "\n\n";
    130130    std::cerr << "Feasible flow: " << (res == MCF::OPTIMAL ? "found" : "not found") << '\n';
    131     if (res) std::cerr << "Min flow cost: " << ns.totalCost() << '\n';
     131    if (res) std::cerr << "Min flow cost: "
     132                       << ns.template totalCost<LargeValue>() << '\n';
    132133  }
    133134}
     
    149150  if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
    150151  if(report) std::cerr << "\nCardinality of max matching: "
    151                        << mat.matchingSize() << '\n'; 
    152 }
    153 
    154 
    155 template<class Value>
     152                       << mat.matchingSize() << '\n';
     153}
     154
     155
     156template<class Value, class LargeValue>
    156157void solve(ArgParser &ap, std::istream &is, std::ostream &os,
    157158           DimacsDescriptor &desc)
     
    167168      exit(1);
    168169    }
    169  
     170
    170171  switch(desc.type)
    171172    {
    172173    case DimacsDescriptor::MIN:
    173       solve_min<Value>(ap,is,os,infty,desc);
     174      solve_min<Value, LargeValue>(ap,is,os,infty,desc);
    174175      break;
    175176    case DimacsDescriptor::MAX:
     
    236237
    237238  DimacsDescriptor desc = dimacsType(is);
    238  
     239
    239240  if(!ap.given("q"))
    240241    {
     
    261262      std::cout << "\n\n";
    262263    }
    263    
     264
    264265  if(ap.given("double"))
    265     solve<double>(ap,is,os,desc);
     266    solve<double, double>(ap,is,os,desc);
    266267  else if(ap.given("ldouble"))
    267     solve<long double>(ap,is,os,desc);
     268    solve<long double, long double>(ap,is,os,desc);
    268269#ifdef LEMON_HAVE_LONG_LONG
    269270  else if(ap.given("long"))
    270     solve<long long>(ap,is,os,desc);
     271    solve<long long, long long>(ap,is,os,desc);
     272  else solve<int, long long>(ap,is,os,desc);
     273#else
     274  else solve<int, long>(ap,is,os,desc);
    271275#endif
    272   else solve<int>(ap,is,os,desc);
    273276
    274277  return 0;
Note: See TracChangeset for help on using the changeset viewer.