COIN-OR::LEMON - Graph Library

Ignore:
Files:
1 added
12 edited

Legend:

Unmodified
Added
Removed
  • AUTHORS

    r320 r1072  
    2424
    2525Again, please visit the history of the old LEMON repository for more
    26 details: http://lemon.cs.elte.hu/svn/lemon/trunk
     26details: http://lemon.cs.elte.hu/hg/lemon-0.x
  • doc/lgf.dox

    r463 r1069  
    6464\endcode
    6565
    66 The \c \@arcs section is very similar to the \c \@nodes section,
    67 it again starts with a header line describing the names of the maps,
    68 but the \c "label" map is not obligatory here. The following lines
    69 describe the arcs. The first two tokens of each line are
    70 the source and the target node of the arc, respectively, then come the map
     66The \c \@arcs section is very similar to the \c \@nodes section, it
     67again starts with a header line describing the names of the maps, but
     68the \c "label" map is not obligatory here. The following lines
     69describe the arcs. The first two tokens of each line are the source
     70and the target node of the arc, respectively, then come the map
    7171values. The source and target tokens must be node labels.
    7272
     
    7979\endcode
    8080
     81If there is no map in the \c \@arcs section at all, then it must be
     82indicated by a sole '-' sign in the first line.
     83
     84\code
     85 @arcs
     86         -
     87 1   2
     88 1   3
     89 2   3
     90\endcode
     91
    8192The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can
    8293also store the edge set of an undirected graph. In such case there is
    8394a conventional method for store arc maps in the file, if two columns
    84 has the same caption with \c '+' and \c '-' prefix, then these columns
     95have the same caption with \c '+' and \c '-' prefix, then these columns
    8596can be regarded as the values of an arc map.
    8697
  • lemon/Makefile.am

    r728 r1102  
    11EXTRA_DIST += \
    22        lemon/lemon.pc.in \
     3        lemon/lemon.pc.cmake \
    34        lemon/CMakeLists.txt \
    45        lemon/config.h.cmake
  • lemon/bits/path_dump.h

    r576 r973  
    5050
    5151    bool empty() const {
    52       return predMap[target] != INVALID;
     52      return predMap[target] == INVALID;
    5353    }
    5454
     
    124124
    125125    bool empty() const {
    126       return source != target;
     126      return predMatrixMap(source, target) == INVALID;
    127127    }
    128128
  • lemon/core.h

    r718 r984  
    395395      static void copy(const From& from, Digraph &to,
    396396                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
     397        to.clear();
    397398        for (typename From::NodeIt it(from); it != INVALID; ++it) {
    398399          nodeRefMap[it] = to.addNode();
     
    422423      static void copy(const From& from, Graph &to,
    423424                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
     425        to.clear();
    424426        for (typename From::NodeIt it(from); it != INVALID; ++it) {
    425427          nodeRefMap[it] = to.addNode();
  • lemon/dfs.h

    r631 r1009  
    558558    void start(Node t)
    559559    {
    560       while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
     560      while ( !emptyQueue() && !(*_reached)[t] )
    561561        processNextArc();
    562562    }
     
    15101510    /// with addSource() before using this function.
    15111511    void start(Node t) {
    1512       while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
     1512      while ( !emptyQueue() && !(*_reached)[t] )
    15131513        processNextArc();
    15141514    }
  • lemon/graph_to_eps.h

    r664 r908  
    685685#else
    686686      os << bits::getWinFormattedDate();
     687      os << std::endl;
    687688#endif
    688689    }
    689     os << std::endl;
    690690
    691691    if (_autoArcWidthScale) {
  • lemon/lgf_reader.h

    r646 r1069  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    965965        int index = 0;
    966966        while (_reader_bits::readToken(line, map)) {
     967          if(map == "-") {
     968              if(index!=0)
     969                throw FormatError("'-' is not allowed as a map name");
     970              else if (line >> std::ws >> c)
     971                throw FormatError("Extra character at the end of line");
     972              else break;
     973            }
    967974          if (maps.find(map) != maps.end()) {
    968975            std::ostringstream msg;
     
    18351842        int index = 0;
    18361843        while (_reader_bits::readToken(line, map)) {
     1844          if(map == "-") {
     1845              if(index!=0)
     1846                throw FormatError("'-' is not allowed as a map name");
     1847              else if (line >> std::ws >> c)
     1848                throw FormatError("Extra character at the end of line");
     1849              else break;
     1850            }
    18371851          if (maps.find(map) != maps.end()) {
    18381852            std::ostringstream msg;
  • test/CMakeLists.txt

    r1061 r1069  
    3232  heap_test
    3333  kruskal_test
     34  lgf_test
    3435  maps_test
    3536  matching_test
  • test/Makefile.am

    r696 r1102  
    2626        test/heap_test \
    2727        test/kruskal_test \
     28        test/lgf_test \
    2829        test/maps_test \
    2930        test/matching_test \
     
    7172test_kruskal_test_SOURCES = test/kruskal_test.cc
    7273test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
     74test_lgf_test_SOURCES = test/lgf_test.cc
    7375test_lp_test_SOURCES = test/lp_test.cc
    7476test_maps_test_SOURCES = test/maps_test.cc
  • test/dfs_test.cc

    r632 r1009  
    5151  "@attributes\n"
    5252  "source 0\n"
    53   "target 5\n";
     53  "target 5\n"
     54  "source1 6\n"
     55  "target1 3\n";
     56
    5457
    5558void checkDfsCompile()
     
    180183  Digraph G;
    181184  Node s, t;
     185  Node s1, t1;
    182186
    183187  std::istringstream input(test_lgf);
     
    185189    node("source", s).
    186190    node("target", t).
     191    node("source1", s1).
     192    node("target1", t1).
    187193    run();
    188194
     
    211217
    212218  {
     219  Dfs<Digraph> dfs(G);
     220  check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
     221  }
     222 
     223  {
    213224    NullMap<Node,Arc> myPredMap;
    214225    dfs(G).predMap(myPredMap).run(s);
  • test/graph_copy_test.cc

    r463 r984  
    3030  const int nn = 10;
    3131
     32  // Build a digraph
    3233  SmartDigraph from;
    3334  SmartDigraph::NodeMap<int> fnm(from);
     
    5253  }
    5354
     55  // Test digraph copy
    5456  ListDigraph to;
    5557  ListDigraph::NodeMap<int> tnm(to);
     
    6971    nodeCrossRef(ncr).arcCrossRef(ecr).
    7072    node(fn, tn).arc(fa, ta).run();
     73 
     74  check(countNodes(from) == countNodes(to), "Wrong copy.");
     75  check(countArcs(from) == countArcs(to), "Wrong copy.");
    7176
    7277  for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {
     
    9196  check(tn == nr[fn], "Wrong copy.");
    9297  check(ta == er[fa], "Wrong copy.");
     98
     99  // Test repeated copy
     100  digraphCopy(from, to).run();
     101 
     102  check(countNodes(from) == countNodes(to), "Wrong copy.");
     103  check(countArcs(from) == countArcs(to), "Wrong copy.");
    93104}
    94105
     
    96107  const int nn = 10;
    97108
     109  // Build a graph
    98110  SmartGraph from;
    99111  SmartGraph::NodeMap<int> fnm(from);
     
    123135  }
    124136
     137  // Test graph copy
    125138  ListGraph to;
    126139  ListGraph::NodeMap<int> tnm(to);
     
    144157    nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).
    145158    node(fn, tn).arc(fa, ta).edge(fe, te).run();
     159
     160  check(countNodes(from) == countNodes(to), "Wrong copy.");
     161  check(countEdges(from) == countEdges(to), "Wrong copy.");
     162  check(countArcs(from) == countArcs(to), "Wrong copy.");
    146163
    147164  for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {
     
    181198  check(ta == ar[fa], "Wrong copy.");
    182199  check(te == er[fe], "Wrong copy.");
     200
     201  // Test repeated copy
     202  graphCopy(from, to).run();
     203 
     204  check(countNodes(from) == countNodes(to), "Wrong copy.");
     205  check(countEdges(from) == countEdges(to), "Wrong copy.");
     206  check(countArcs(from) == countArcs(to), "Wrong copy.");
    183207}
    184208
Note: See TracChangeset for help on using the changeset viewer.