COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [432:e9a568cc86e3:431:9dfaf6efc36f] in lemon-1.2


Ignore:
Files:
2 added
12 edited

Legend:

Unmodified
Added
Removed

  • lemon/bfs.h

    r420 r405  
    17421742    /// \pre Either \ref run(Node) "run()" or \ref init()
    17431743    /// must be called before using this function.
    1744     bool reached(Node v) const { return (*_reached)[v]; }
     1744    bool reached(Node v) { return (*_reached)[v]; }
    17451745
    17461746    ///@}

  • lemon/circulation.h

    r420 r402  
    420420    /// \pre Either \ref run() or \ref init() must be called before
    421421    /// using this function.
    422     const Elevator& elevator() const {
     422    const Elevator& elevator() {
    423423      return *_level;
    424424    }
    … …  
    645645    /// \pre Either \ref run() or \ref init() must be called before
    646646    /// using this function.
    647     const FlowMap& flowMap() const {
     647    const FlowMap& flowMap() {
    648648      return *_flow;
    649649    }
    … …  
    670670       \sa checkBarrier()
    671671    */
    672     bool barrier(const Node& node) const
     672    bool barrier(const Node& node)
    673673    {
    674674      return (*_level)[node] >= _el;
    … …  
    693693    /// \sa checkBarrier()
    694694    template<class BarrierMap>
    695     void barrierMap(BarrierMap &bar) const
     695    void barrierMap(BarrierMap &bar)
    696696    {
    697697      for(NodeIt n(_g);n!=INVALID;++n)
    … …  
    713713    ///Check if the found flow is a feasible circulation,
    714714    ///
    715     bool checkFlow() const {
     715    bool checkFlow() {
    716716      for(ArcIt e(_g);e!=INVALID;++e)
    717717        if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
    … …  
    731731    ///\sa barrier()
    732732    ///\sa barrierMap()
    733     bool checkBarrier() const
     733    bool checkBarrier()
    734734    {
    735735      Value delta=0;

  • lemon/connectivity.h

    r425 r417  
    1717 */
    1818
    19 #ifndef LEMON_CONNECTIVITY_H
    20 #define LEMON_CONNECTIVITY_H
     19#ifndef LEMON_TOPOLOGY_H
     20#define LEMON_TOPOLOGY_H
    2121
    2222#include <lemon/dfs.h>
    … …  
    155155  }
    156156
    157   namespace _connectivity_bits {
     157  namespace _topology_bits {
    158158
    159159    template <typename Digraph, typename Iterator >
    … …  
    189189
    190190    template <typename Digraph, typename ArcMap>
    191     struct StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> {
     191    struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
    192192    public:
    193193      typedef typename Digraph::Node Node;
    194194      typedef typename Digraph::Arc Arc;
    195195
    196       StronglyConnectedCutArcsVisitor(const Digraph& digraph,
    197                                       ArcMap& cutMap,
    198                                       int& cutNum)
     196      StronglyConnectedCutEdgesVisitor(const Digraph& digraph,
     197                                       ArcMap& cutMap,
     198                                       int& cutNum)
    199199        : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
    200           _compMap(digraph, -1), _num(-1) {
    201       }
    202 
    203       void start(const Node&) {
     200          _compMap(digraph), _num(0) {
     201      }
     202
     203      void stop(const Node&) {
    204204        ++_num;
    205205      }
    … …  
    249249    if (source == INVALID) return true;
    250250
    251     using namespace _connectivity_bits;
     251    using namespace _topology_bits;
    252252
    253253    typedef DfsVisitor<Digraph> Visitor;
    … …  
    266266
    267267    typedef ReverseDigraph<const Digraph> RDigraph;
    268     typedef typename RDigraph::NodeIt RNodeIt;
    269268    RDigraph rdigraph(digraph);
    270269
    … …  
    277276    rdfs.start();
    278277
    279     for (RNodeIt it(rdigraph); it != INVALID; ++it) {
     278    for (NodeIt it(rdigraph); it != INVALID; ++it) {
    280279      if (!rdfs.reached(it)) {
    281280        return false;
    … …  
    296295  /// direction.
    297296  ///
    298   /// \param digraph The graph.
     297  /// \param graph The graph.
    299298  /// \return The number of components
    300299  /// \note By definition, the empty graph has zero
    … …  
    304303    checkConcept<concepts::Digraph, Digraph>();
    305304
    306     using namespace _connectivity_bits;
     305    using namespace _topology_bits;
    307306
    308307    typedef typename Digraph::Node Node;
    … …  
    376375    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
    377376
    378     using namespace _connectivity_bits;
     377    using namespace _topology_bits;
    379378
    380379    typedef std::vector<Node> Container;
    … …  
    440439    checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
    441440
    442     using namespace _connectivity_bits;
     441    using namespace _topology_bits;
    443442
    444443    typedef std::vector<Node> Container;
    … …  
    465464    int cutNum = 0;
    466465
    467     typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
     466    typedef StronglyConnectedCutEdgesVisitor<RDigraph, ArcMap> RVisitor;
    468467    RVisitor rvisitor(rgraph, cutMap, cutNum);
    469468
    … …  
    480479  }
    481480
    482   namespace _connectivity_bits {
     481  namespace _topology_bits {
    483482
    484483    template <typename Digraph>
    … …  
    732731    typedef typename Graph::NodeIt NodeIt;
    733732
    734     using namespace _connectivity_bits;
     733    using namespace _topology_bits;
    735734
    736735    typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
    … …  
    775774    checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
    776775
    777     using namespace _connectivity_bits;
     776    using namespace _topology_bits;
    778777
    779778    typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
    … …  
    815814    checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
    816815
    817     using namespace _connectivity_bits;
     816    using namespace _topology_bits;
    818817
    819818    typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
    … …  
    834833  }
    835834
    836   namespace _connectivity_bits {
     835  namespace _topology_bits {
    837836
    838837    template <typename Digraph>
    … …  
    10551054    typedef typename Graph::NodeIt NodeIt;
    10561055
    1057     using namespace _connectivity_bits;
     1056    using namespace _topology_bits;
    10581057
    10591058    typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
    … …  
    10971096    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
    10981097
    1099     using namespace _connectivity_bits;
     1098    using namespace _topology_bits;
    11001099
    11011100    typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
    … …  
    11381137    checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
    11391138
    1140     using namespace _connectivity_bits;
     1139    using namespace _topology_bits;
    11411140
    11421141    typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
    … …  
    11581157
    11591158
    1160   namespace _connectivity_bits {
     1159  namespace _topology_bits {
    11611160
    11621161    template <typename Digraph, typename IntNodeMap>
    … …  
    11951194  template <typename Digraph, typename NodeMap>
    11961195  void topologicalSort(const Digraph& graph, NodeMap& order) {
    1197     using namespace _connectivity_bits;
     1196    using namespace _topology_bits;
    11981197
    11991198    checkConcept<concepts::Digraph, Digraph>();
    … …  
    12261225  /// that the given graph is DAG.
    12271226  ///
    1228   /// \param digraph The graph. It must be directed and acyclic.
     1227  /// \param graph The graph. It must be directed and acyclic.
    12291228  /// \retval order A readable - writable node map. The values will be set
    12301229  /// from 0 to the number of the nodes in the graph minus one. Each values
    … …  
    12361235  /// \see dag
    12371236  template <typename Digraph, typename NodeMap>
    1238   bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
    1239     using namespace _connectivity_bits;
     1237  bool checkedTopologicalSort(const Digraph& graph, NodeMap& order) {
     1238    using namespace _topology_bits;
    12401239
    12411240    checkConcept<concepts::Digraph, Digraph>();
    … …  
    12471246    typedef typename Digraph::Arc Arc;
    12481247
    1249     for (NodeIt it(digraph); it != INVALID; ++it) {
    1250       order.set(it, -1);
    1251     }
     1248    order = constMap<Node, int, -1>();
    12521249
    12531250    TopologicalSortVisitor<Digraph, NodeMap>
    1254       visitor(order, countNodes(digraph));
     1251      visitor(order, countNodes(graph));
    12551252
    12561253    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
    1257       dfs(digraph, visitor);
     1254      dfs(graph, visitor);
    12581255
    12591256    dfs.init();
    1260     for (NodeIt it(digraph); it != INVALID; ++it) {
     1257    for (NodeIt it(graph); it != INVALID; ++it) {
    12611258      if (!dfs.reached(it)) {
    12621259        dfs.addSource(it);
    12631260        while (!dfs.emptyQueue()) {
    1264            Arc arc = dfs.nextArc();
    1265            Node target = digraph.target(arc);
     1261           Arc edge = dfs.nextArc();
     1262           Node target = graph.target(edge);
    12661263           if (dfs.reached(target) && order[target] == -1) {
    12671264             return false;
    … …  
    12831280  /// \see acyclic
    12841281  template <typename Digraph>
    1285   bool dag(const Digraph& digraph) {
     1282  bool dag(const Digraph& graph) {
    12861283
    12871284    checkConcept<concepts::Digraph, Digraph>();
    … …  
    12941291
    12951292    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
    1296       Create dfs(digraph);
    1297 
    1298     ProcessedMap processed(digraph);
     1293      Create dfs(graph);
     1294
     1295    ProcessedMap processed(graph);
    12991296    dfs.processedMap(processed);
    13001297
    13011298    dfs.init();
    1302     for (NodeIt it(digraph); it != INVALID; ++it) {
     1299    for (NodeIt it(graph); it != INVALID; ++it) {
    13031300      if (!dfs.reached(it)) {
    13041301        dfs.addSource(it);
    13051302        while (!dfs.emptyQueue()) {
    13061303          Arc edge = dfs.nextArc();
    1307           Node target = digraph.target(edge);
     1304          Node target = graph.target(edge);
    13081305          if (dfs.reached(target) && !processed[target]) {
    13091306            return false;
    … …  
    13841381  }
    13851382
    1386   namespace _connectivity_bits {
     1383  namespace _topology_bits {
    13871384
    13881385    template <typename Digraph>
    … …  
    14531450  template<typename Graph>
    14541451  inline bool bipartite(const Graph &graph){
    1455     using namespace _connectivity_bits;
     1452    using namespace _topology_bits;
    14561453
    14571454    checkConcept<concepts::Graph, Graph>();
    … …  
    14931490  template<typename Graph, typename NodeMap>
    14941491  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
    1495     using namespace _connectivity_bits;
     1492    using namespace _topology_bits;
    14961493
    14971494    checkConcept<concepts::Graph, Graph>();
    … …  
    15241521  /// Returns true when there are not loop edges in the graph.
    15251522  template <typename Digraph>
    1526   bool loopFree(const Digraph& digraph) {
    1527     for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {
    1528       if (digraph.source(it) == digraph.target(it)) return false;
     1523  bool loopFree(const Digraph& graph) {
     1524    for (typename Digraph::ArcIt it(graph); it != INVALID; ++it) {
     1525      if (graph.source(it) == graph.target(it)) return false;
    15291526    }
    15301527    return true;
    … …  
    15351532  /// Returns true when there are not parallel edges in the graph.
    15361533  template <typename Digraph>
    1537   bool parallelFree(const Digraph& digraph) {
    1538     typename Digraph::template NodeMap<bool> reached(digraph, false);
    1539     for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
    1540       for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
    1541         if (reached[digraph.target(a)]) return false;
    1542         reached.set(digraph.target(a), true);
    1543       }
    1544       for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
    1545         reached.set(digraph.target(a), false);
     1534  bool parallelFree(const Digraph& graph) {
     1535    typename Digraph::template NodeMap<bool> reached(graph, false);
     1536    for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
     1537      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
     1538        if (reached[graph.target(e)]) return false;
     1539        reached.set(graph.target(e), true);
     1540      }
     1541      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
     1542        reached.set(graph.target(e), false);
    15461543      }
    15471544    }
    … …  
    15551552  /// the graph.
    15561553  template <typename Digraph>
    1557   bool simpleDigraph(const Digraph& digraph) {
    1558     typename Digraph::template NodeMap<bool> reached(digraph, false);
    1559     for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
     1554  bool simpleDigraph(const Digraph& graph) {
     1555    typename Digraph::template NodeMap<bool> reached(graph, false);
     1556    for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
    15601557      reached.set(n, true);
    1561       for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
    1562         if (reached[digraph.target(a)]) return false;
    1563         reached.set(digraph.target(a), true);
    1564       }
    1565       for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
    1566         reached.set(digraph.target(a), false);
     1558      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
     1559        if (reached[graph.target(e)]) return false;
     1560        reached.set(graph.target(e), true);
     1561      }
     1562      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
     1563        reached.set(graph.target(e), false);
    15671564      }
    15681565      reached.set(n, false);
    … …  
    15731570} //namespace lemon
    15741571
    1575 #endif //LEMON_CONNECTIVITY_H
     1572#endif //LEMON_TOPOLOGY_H

  • lemon/dfs.h

    r421 r405  
    14111411          } else {
    14121412            _visitor->leave(s);
    1413             _visitor->stop(s);
    14141413          }
    14151414        }
    … …  
    16271626    /// \pre Either \ref run(Node) "run()" or \ref init()
    16281627    /// must be called before using this function.
    1629     bool reached(Node v) const { return (*_reached)[v]; }
     1628    bool reached(Node v) { return (*_reached)[v]; }
    16301629
    16311630    ///@}

  • lemon/max_matching.h

    r425 r330  
    417417    /// \ref init(), \ref greedyInit() or \ref matchingInit()
    418418    /// functions first, then you can start the algorithm with the \ref
    419     /// startSparse() or startDense() functions.
     419    /// startParse() or startDense() functions.
    420420
    421421    ///@{

  • lemon/preflow.h

    r420 r393  
    367367    /// \pre Either \ref run() or \ref init() must be called before
    368368    /// using this function.
    369     const Elevator& elevator() const {
     369    const Elevator& elevator() {
    370370      return *_level;
    371371    }
    … …  
    919919    /// \pre Either \ref run() or \ref init() must be called before
    920920    /// using this function.
    921     const FlowMap& flowMap() const {
     921    const FlowMap& flowMap() {
    922922      return *_flow;
    923923    }

  • lemon/suurballe.h

    r425 r346  
    5252  ///
    5353  /// \note For finding node-disjoint paths this algorithm can be used
    54   /// with \ref SplitNodes.
     54  /// with \ref SplitDigraphAdaptor.
    5555#ifdef DOXYGEN
    5656  template <typename Digraph, typename LengthMap>

  • scripts/chg-len.py

    r422 r376  
    44
    55from mercurial import ui, hg
    6 from mercurial import util
    7 
    8 util.rcpath = lambda : []
    96
    107if len(sys.argv)>1 and sys.argv[1] in ["-h","--help"]:

  • test/CMakeLists.txt

    r424 r410  
    55SET(TESTS
    66  bfs_test
    7   circulation_test
    87  counter_test
    98  dfs_test
    … …  
    1211  dim_test
    1312  error_test
    14   graph_adaptor_test
    1513  graph_copy_test
    1614  graph_test
    … …  
    2119  maps_test
    2220  max_matching_test
     21  random_test
    2322  path_test
    24   preflow_test
    25   random_test
    26   suurballe_test
    2723  time_measure_test
    2824  unionfind_test)

  • test/Makefile.am

    r424 r418  
    11EXTRA_DIST += \
    2         test/CMakeLists.txt
     2        test/CMakeLists.txt \
     3        test/min_cost_flow_test.lgf \
     4        test/preflow_graph.lgf
    35
    46noinst_HEADERS += \
    … …  
    1921        test/graph_test \
    2022        test/graph_utils_test \
    21         test/hao_orlin_test \
    2223        test/heap_test \
    2324        test/kruskal_test \
     25        test/hao_orlin_test \
    2426        test/maps_test \
    2527        test/max_matching_test \
     28        test/random_test \
    2629        test/path_test \
    2730        test/preflow_test \
    28         test/random_test \
    2931        test/suurballe_test \
    3032        test/test_tools_fail \

  • test/preflow_test.cc

    r423 r394  
    1717 */
    1818
    19 #include <iostream>
     19#include <fstream>
     20#include <string>
    2021
    2122#include "test_tools.h"
    … …  
    2829
    2930using namespace lemon;
    30 
    31 char test_lgf[] =
    32   "@nodes\n"
    33   "label\n"
    34   "0\n"
    35   "1\n"
    36   "2\n"
    37   "3\n"
    38   "4\n"
    39   "5\n"
    40   "6\n"
    41   "7\n"
    42   "8\n"
    43   "9\n"
    44   "@arcs\n"
    45   "    label capacity\n"
    46   "0 1 0     20\n"
    47   "0 2 1     0\n"
    48   "1 1 2     3\n"
    49   "1 2 3     8\n"
    50   "1 3 4     8\n"
    51   "2 5 5     5\n"
    52   "3 2 6     5\n"
    53   "3 5 7     5\n"
    54   "3 6 8     5\n"
    55   "4 3 9     3\n"
    56   "5 7 10    3\n"
    57   "5 6 11    10\n"
    58   "5 8 12    10\n"
    59   "6 8 13    8\n"
    60   "8 9 14    20\n"
    61   "8 1 15    5\n"
    62   "9 5 16    5\n"
    63   "@attributes\n"
    64   "source 1\n"
    65   "target 8\n";
    6631
    6732void checkPreflowCompile()
    … …  
    159124  typedef Preflow<Digraph, CapMap> PType;
    160125
     126  std::string f_name;
     127  if( getenv("srcdir") )
     128    f_name = std::string(getenv("srcdir"));
     129  else f_name = ".";
     130  f_name += "/test/preflow_graph.lgf";
     131
     132  std::ifstream file(f_name.c_str());
     133
     134  check(file, "Input file '" << f_name << "' not found.");
     135
    161136  Digraph g;
    162137  Node s, t;
    163138  CapMap cap(g);
    164   std::istringstream input(test_lgf);
    165   DigraphReader<Digraph>(g,input).
     139  DigraphReader<Digraph>(g,file).
    166140    arcMap("capacity", cap).
    167141    node("source",s).

  • test/suurballe_test.cc

    r423 r346  
    1818
    1919#include <iostream>
     20#include <fstream>
    2021
    2122#include <lemon/list_graph.h>
    … …  
    2728
    2829using namespace lemon;
    29 
    30 char test_lgf[] =
    31   "@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"
    45   "@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"
    68   "@attributes\n"
    69   "source  1\n"
    70   "target 12\n"
    71   "@end\n";
    7230
    7331// Check the feasibility of the flow
    … …  
    13997  Node source, target;
    14098
    141   std::istringstream input(test_lgf);
     99  std::string fname;
     100  if(getenv("srcdir"))
     101    fname = std::string(getenv("srcdir"));
     102  else fname = ".";
     103  fname += "/test/min_cost_flow_test.lgf";
     104
     105  std::ifstream input(fname.c_str());
     106  check(input, "Input file '" << fname << "' not found");
    142107  DigraphReader<ListDigraph>(digraph, input).
    143108    arcMap("cost", length).
    … …  
    145110    node("target", target).
    146111    run();
     112  input.close();
    147113 
    148114  // Find 2 paths
Note: See TracChangeset for help on using the changeset viewer.