COIN-OR::LEMON - Graph Library

Changeset 937:17e36e175725 in lemon-1.2


Ignore:
Timestamp:
12/20/11 17:35:45 (8 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
932:2eebc8f7dca5 (diff), 930:b96574ff36ec (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

Files:
22 edited

Legend:

Unmodified
Added
Removed
  • doc/lgf.dox

    r922 r923  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/lgf.dox

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

    r929 r937  
    22        lemon/lemon.pc.in \
    33        lemon/lemon.pc.cmake \
    4         lemon/CMakeLists.txt
     4        lemon/CMakeLists.txt \
     5        lemon/config.h.cmake
    56
    67pkgconfig_DATA += lemon/lemon.pc
     
    910
    1011lemon_libemon_la_SOURCES = \
    11         lemon/arg_parser.cc \
    12         lemon/base.cc \
    13         lemon/color.cc \
    14         lemon/random.cc \
     12        lemon/arg_parser.cc \
     13        lemon/base.cc \
     14        lemon/color.cc \
     15        lemon/lp_base.cc \
     16        lemon/lp_skeleton.cc \
     17        lemon/random.cc \
    1518        lemon/bits/windows.cc
    1619
    17 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
    18 #lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
     20nodist_lemon_HEADERS = lemon/config.h   
    1921
    20 nodist_lemon_HEADERS = lemon/config.h
     22lemon_libemon_la_CXXFLAGS = \
     23        $(AM_CXXFLAGS) \
     24        $(GLPK_CFLAGS) \
     25        $(CPLEX_CFLAGS) \
     26        $(SOPLEX_CXXFLAGS) \
     27        $(CLP_CXXFLAGS) \
     28        $(CBC_CXXFLAGS)
     29
     30lemon_libemon_la_LDFLAGS = \
     31        $(GLPK_LIBS) \
     32        $(CPLEX_LIBS) \
     33        $(SOPLEX_LIBS) \
     34        $(CLP_LIBS) \
     35        $(CBC_LIBS)
     36
     37if HAVE_GLPK
     38lemon_libemon_la_SOURCES += lemon/glpk.cc
     39endif
     40
     41if HAVE_CPLEX
     42lemon_libemon_la_SOURCES += lemon/cplex.cc
     43endif
     44
     45if HAVE_SOPLEX
     46lemon_libemon_la_SOURCES += lemon/soplex.cc
     47endif
     48
     49if HAVE_CLP
     50lemon_libemon_la_SOURCES += lemon/clp.cc
     51endif
     52
     53if HAVE_CBC
     54lemon_libemon_la_SOURCES += lemon/cbc.cc
     55endif
    2156
    2257lemon_HEADERS += \
    23         lemon/arg_parser.h \
     58        lemon/adaptors.h \
     59        lemon/arg_parser.h \
    2460        lemon/assert.h \
    25         lemon/bfs.h \
    26         lemon/bin_heap.h \
    27         lemon/color.h \
     61        lemon/bfs.h \
     62        lemon/bin_heap.h \
     63        lemon/bucket_heap.h \
     64        lemon/cbc.h \
     65        lemon/circulation.h \
     66        lemon/clp.h \
     67        lemon/color.h \
    2868        lemon/concept_check.h \
    29         lemon/counter.h \
     69        lemon/connectivity.h \
     70        lemon/counter.h \
    3071        lemon/core.h \
    31         lemon/dfs.h \
    32         lemon/dijkstra.h \
    33         lemon/dim2.h \
     72        lemon/cplex.h \
     73        lemon/dfs.h \
     74        lemon/dijkstra.h \
     75        lemon/dim2.h \
     76        lemon/dimacs.h \
     77        lemon/edge_set.h \
     78        lemon/elevator.h \
    3479        lemon/error.h \
    35         lemon/graph_to_eps.h \
     80        lemon/euler.h \
     81        lemon/fib_heap.h \
     82        lemon/full_graph.h \
     83        lemon/glpk.h \
     84        lemon/gomory_hu.h \
     85        lemon/graph_to_eps.h \
     86        lemon/grid_graph.h \
     87        lemon/hypercube_graph.h \
    3688        lemon/kruskal.h \
     89        lemon/hao_orlin.h \
    3790        lemon/lgf_reader.h \
    3891        lemon/lgf_writer.h \
    3992        lemon/list_graph.h \
     93        lemon/lp.h \
     94        lemon/lp_base.h \
     95        lemon/lp_skeleton.h \
     96        lemon/list_graph.h \
    4097        lemon/maps.h \
     98        lemon/matching.h \
    4199        lemon/math.h \
     100        lemon/min_cost_arborescence.h \
     101        lemon/nauty_reader.h \
     102        lemon/network_simplex.h \
    42103        lemon/path.h \
    43         lemon/random.h \
     104        lemon/preflow.h \
     105        lemon/radix_heap.h \
     106        lemon/radix_sort.h \
     107        lemon/random.h \
    44108        lemon/smart_graph.h \
    45         lemon/time_measure.h \
    46         lemon/tolerance.h \
     109        lemon/soplex.h \
     110        lemon/suurballe.h \
     111        lemon/time_measure.h \
     112        lemon/tolerance.h \
    47113        lemon/unionfind.h \
    48114        lemon/bits/windows.h
     
    51117        lemon/bits/alteration_notifier.h \
    52118        lemon/bits/array_map.h \
    53         lemon/bits/base_extender.h \
    54         lemon/bits/bezier.h \
     119        lemon/bits/bezier.h \
    55120        lemon/bits/default_map.h \
    56         lemon/bits/enable_if.h \
     121        lemon/bits/edge_set_extender.h \
     122        lemon/bits/enable_if.h \
     123        lemon/bits/graph_adaptor_extender.h \
    57124        lemon/bits/graph_extender.h \
    58125        lemon/bits/map_extender.h \
    59126        lemon/bits/path_dump.h \
     127        lemon/bits/solver_bits.h \
    60128        lemon/bits/traits.h \
     129        lemon/bits/variant.h \
    61130        lemon/bits/vector_map.h
    62131
  • lemon/Makefile.am

    r681 r937  
    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

    r889 r890  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1717 */
    1818
    19 #ifndef LEMON_BITS_PRED_MAP_PATH_H
    20 #define LEMON_BITS_PRED_MAP_PATH_H
     19#ifndef LEMON_BITS_PATH_DUMP_H
     20#define LEMON_BITS_PATH_DUMP_H
     21
     22#include <lemon/core.h>
     23#include <lemon/concept_check.h>
    2124
    2225namespace lemon {
  • lemon/bits/path_dump.h

    r529 r890  
    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

    r893 r937  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2727#include <lemon/bits/traits.h>
    2828#include <lemon/assert.h>
     29
     30// Disable the following warnings when compiling with MSVC:
     31// C4250: 'class1' : inherits 'class2::member' via dominance
     32// C4355: 'this' : used in base member initializer list
     33// C4503: 'function' : decorated name length exceeded, name was truncated
     34// C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
     35// C4996: 'function': was declared deprecated
     36#ifdef _MSC_VER
     37#pragma warning( disable : 4250 4355 4503 4800 4996 )
     38#endif
    2939
    3040///\file
     
    10371047  ///\sa findArc()
    10381048  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
    1039   template <typename _Graph>
    1040   class ConArcIt : public _Graph::Arc {
     1049  template <typename GR>
     1050  class ConArcIt : public GR::Arc {
     1051    typedef typename GR::Arc Parent;
     1052
    10411053  public:
    10421054
    1043     typedef _Graph Graph;
    1044     typedef typename Graph::Arc Parent;
    1045 
    1046     typedef typename Graph::Arc Arc;
    1047     typedef typename Graph::Node Node;
     1055    typedef typename GR::Arc Arc;
     1056    typedef typename GR::Node Node;
    10481057
    10491058    /// \brief Constructor.
     
    10511060    /// Construct a new ConArcIt iterating on the arcs that
    10521061    /// connects nodes \c u and \c v.
    1053     ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
     1062    ConArcIt(const GR& g, Node u, Node v) : _graph(g) {
    10541063      Parent::operator=(findArc(_graph, u, v));
    10551064    }
     
    10581067    ///
    10591068    /// Construct a new ConArcIt that continues the iterating from arc \c a.
    1060     ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
     1069    ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {}
    10611070
    10621071    /// \brief Increment operator.
     
    10691078    }
    10701079  private:
    1071     const Graph& _graph;
     1080    const GR& _graph;
    10721081  };
    10731082
     
    11601169  ///
    11611170  ///\sa findEdge()
    1162   template <typename _Graph>
    1163   class ConEdgeIt : public _Graph::Edge {
     1171  template <typename GR>
     1172  class ConEdgeIt : public GR::Edge {
     1173    typedef typename GR::Edge Parent;
     1174
    11641175  public:
    11651176
    1166     typedef _Graph Graph;
    1167     typedef typename Graph::Edge Parent;
    1168 
    1169     typedef typename Graph::Edge Edge;
    1170     typedef typename Graph::Node Node;
     1177    typedef typename GR::Edge Edge;
     1178    typedef typename GR::Node Node;
    11711179
    11721180    /// \brief Constructor.
     
    11741182    /// Construct a new ConEdgeIt iterating on the edges that
    11751183    /// connects nodes \c u and \c v.
    1176     ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
     1184    ConEdgeIt(const GR& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
    11771185      Parent::operator=(findEdge(_graph, _u, _v));
    11781186    }
     
    11811189    ///
    11821190    /// Construct a new ConEdgeIt that continues iterating from edge \c e.
    1183     ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
     1191    ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {}
    11841192
    11851193    /// \brief Increment operator.
     
    11911199    }
    11921200  private:
    1193     const Graph& _graph;
     1201    const GR& _graph;
    11941202    Node _u, _v;
    11951203  };
     
    12141222  ///queries.
    12151223  ///
    1216   ///\tparam G The type of the underlying digraph.
     1224  ///\tparam GR The type of the underlying digraph.
    12171225  ///
    12181226  ///\sa ArcLookUp
    12191227  ///\sa AllArcLookUp
    1220   template<class G>
     1228  template <typename GR>
    12211229  class DynArcLookUp
    1222     : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
     1230    : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
    12231231  {
     1232    typedef typename ItemSetTraits<GR, typename GR::Arc>
     1233    ::ItemNotifier::ObserverBase Parent;
     1234
     1235    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1236
    12241237  public:
    1225     typedef typename ItemSetTraits<G, typename G::Arc>
    1226     ::ItemNotifier::ObserverBase Parent;
    1227 
    1228     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1229     typedef G Digraph;
     1238
     1239    /// The Digraph type
     1240    typedef GR Digraph;
    12301241
    12311242  protected:
    12321243
    1233     class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
     1244    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
     1245      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
     1246
    12341247    public:
    12351248
    1236       typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
    1237 
    1238       AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
     1249      AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
    12391250
    12401251      virtual void add(const Node& node) {
     
    12591270      }
    12601271    };
    1261 
    1262     const Digraph &_g;
    1263     AutoNodeMap _head;
    1264     typename Digraph::template ArcMap<Arc> _parent;
    1265     typename Digraph::template ArcMap<Arc> _left;
    1266     typename Digraph::template ArcMap<Arc> _right;
    12671272
    12681273    class ArcLess {
     
    12761281    };
    12771282
     1283  protected:
     1284
     1285    const Digraph &_g;
     1286    AutoNodeMap _head;
     1287    typename Digraph::template ArcMap<Arc> _parent;
     1288    typename Digraph::template ArcMap<Arc> _left;
     1289    typename Digraph::template ArcMap<Arc> _right;
     1290
    12781291  public:
    12791292
     
    13181331    virtual void clear() {
    13191332      for(NodeIt n(_g);n!=INVALID;++n) {
    1320         _head.set(n, INVALID);
     1333        _head[n] = INVALID;
    13211334      }
    13221335    }
     
    13251338      Node s = _g.source(arc);
    13261339      Node t = _g.target(arc);
    1327       _left.set(arc, INVALID);
    1328       _right.set(arc, INVALID);
     1340      _left[arc] = INVALID;
     1341      _right[arc] = INVALID;
    13291342
    13301343      Arc e = _head[s];
    13311344      if (e == INVALID) {
    1332         _head.set(s, arc);
    1333         _parent.set(arc, INVALID);
     1345        _head[s] = arc;
     1346        _parent[arc] = INVALID;
    13341347        return;
    13351348      }
     
    13371350        if (t < _g.target(e)) {
    13381351          if (_left[e] == INVALID) {
    1339             _left.set(e, arc);
    1340             _parent.set(arc, e);
     1352            _left[e] = arc;
     1353            _parent[arc] = e;
    13411354            splay(arc);
    13421355            return;
     
    13461359        } else {
    13471360          if (_right[e] == INVALID) {
    1348             _right.set(e, arc);
    1349             _parent.set(arc, e);
     1361            _right[e] = arc;
     1362            _parent[arc] = e;
    13501363            splay(arc);
    13511364            return;
     
    13601373      if (_left[arc] == INVALID) {
    13611374        if (_right[arc] != INVALID) {
    1362           _parent.set(_right[arc], _parent[arc]);
     1375          _parent[_right[arc]] = _parent[arc];
    13631376        }
    13641377        if (_parent[arc] != INVALID) {
    13651378          if (_left[_parent[arc]] == arc) {
    1366             _left.set(_parent[arc], _right[arc]);
     1379            _left[_parent[arc]] = _right[arc];
    13671380          } else {
    1368             _right.set(_parent[arc], _right[arc]);
     1381            _right[_parent[arc]] = _right[arc];
    13691382          }
    13701383        } else {
    1371           _head.set(_g.source(arc), _right[arc]);
     1384          _head[_g.source(arc)] = _right[arc];
    13721385        }
    13731386      } else if (_right[arc] == INVALID) {
    1374         _parent.set(_left[arc], _parent[arc]);
     1387        _parent[_left[arc]] = _parent[arc];
    13751388        if (_parent[arc] != INVALID) {
    13761389          if (_left[_parent[arc]] == arc) {
    1377             _left.set(_parent[arc], _left[arc]);
     1390            _left[_parent[arc]] = _left[arc];
    13781391          } else {
    1379             _right.set(_parent[arc], _left[arc]);
     1392            _right[_parent[arc]] = _left[arc];
    13801393          }
    13811394        } else {
    1382           _head.set(_g.source(arc), _left[arc]);
     1395          _head[_g.source(arc)] = _left[arc];
    13831396        }
    13841397      } else {
     
    13901403          }
    13911404          Arc s = _parent[e];
    1392           _right.set(_parent[e], _left[e]);
     1405          _right[_parent[e]] = _left[e];
    13931406          if (_left[e] != INVALID) {
    1394             _parent.set(_left[e], _parent[e]);
     1407            _parent[_left[e]] = _parent[e];
    13951408          }
    13961409
    1397           _left.set(e, _left[arc]);
    1398           _parent.set(_left[arc], e);
    1399           _right.set(e, _right[arc]);
    1400           _parent.set(_right[arc], e);
    1401 
    1402           _parent.set(e, _parent[arc]);
     1410          _left[e] = _left[arc];
     1411          _parent[_left[arc]] = e;
     1412          _right[e] = _right[arc];
     1413          _parent[_right[arc]] = e;
     1414
     1415          _parent[e] = _parent[arc];
    14031416          if (_parent[arc] != INVALID) {
    14041417            if (_left[_parent[arc]] == arc) {
    1405               _left.set(_parent[arc], e);
     1418              _left[_parent[arc]] = e;
    14061419            } else {
    1407               _right.set(_parent[arc], e);
     1420              _right[_parent[arc]] = e;
    14081421            }
    14091422          }
    14101423          splay(s);
    14111424        } else {
    1412           _right.set(e, _right[arc]);
    1413           _parent.set(_right[arc], e);
    1414           _parent.set(e, _parent[arc]);
     1425          _right[e] = _right[arc];
     1426          _parent[_right[arc]] = e;
     1427          _parent[e] = _parent[arc];
    14151428
    14161429          if (_parent[arc] != INVALID) {
    14171430            if (_left[_parent[arc]] == arc) {
    1418               _left.set(_parent[arc], e);
     1431              _left[_parent[arc]] = e;
    14191432            } else {
    1420               _right.set(_parent[arc], e);
     1433              _right[_parent[arc]] = e;
    14211434            }
    14221435          } else {
    1423             _head.set(_g.source(arc), e);
     1436            _head[_g.source(arc)] = e;
    14241437          }
    14251438        }
     
    14331446      if (a < m) {
    14341447        Arc left = refreshRec(v,a,m-1);
    1435         _left.set(me, left);
    1436         _parent.set(left, me);
     1448        _left[me] = left;
     1449        _parent[left] = me;
    14371450      } else {
    1438         _left.set(me, INVALID);
     1451        _left[me] = INVALID;
    14391452      }
    14401453      if (m < b) {
    14411454        Arc right = refreshRec(v,m+1,b);
    1442         _right.set(me, right);
    1443         _parent.set(right, me);
     1455        _right[me] = right;
     1456        _parent[right] = me;
    14441457      } else {
    1445         _right.set(me, INVALID);
     1458        _right[me] = INVALID;
    14461459      }
    14471460      return me;
     
    14551468          std::sort(v.begin(),v.end(),ArcLess(_g));
    14561469          Arc head = refreshRec(v,0,v.size()-1);
    1457           _head.set(n, head);
    1458           _parent.set(head, INVALID);
    1459         }
    1460         else _head.set(n, INVALID);
     1470          _head[n] = head;
     1471          _parent[head] = INVALID;
     1472        }
     1473        else _head[n] = INVALID;
    14611474      }
    14621475    }
     
    14641477    void zig(Arc v) {
    14651478      Arc w = _parent[v];
    1466       _parent.set(v, _parent[w]);
    1467       _parent.set(w, v);
    1468       _left.set(w, _right[v]);
    1469       _right.set(v, w);
     1479      _parent[v] = _parent[w];
     1480      _parent[w] = v;
     1481      _left[w] = _right[v];
     1482      _right[v] = w;
    14701483      if (_parent[v] != INVALID) {
    14711484        if (_right[_parent[v]] == w) {
    1472           _right.set(_parent[v], v);
     1485          _right[_parent[v]] = v;
    14731486        } else {
    1474           _left.set(_parent[v], v);
     1487          _left[_parent[v]] = v;
    14751488        }
    14761489      }
    14771490      if (_left[w] != INVALID){
    1478         _parent.set(_left[w], w);
     1491        _parent[_left[w]] = w;
    14791492      }
    14801493    }
     
    14821495    void zag(Arc v) {
    14831496      Arc w = _parent[v];
    1484       _parent.set(v, _parent[w]);
    1485       _parent.set(w, v);
    1486       _right.set(w, _left[v]);
    1487       _left.set(v, w);
     1497      _parent[v] = _parent[w];
     1498      _parent[w] = v;
     1499      _right[w] = _left[v];
     1500      _left[v] = w;
    14881501      if (_parent[v] != INVALID){
    14891502        if (_left[_parent[v]] == w) {
    1490           _left.set(_parent[v], v);
     1503          _left[_parent[v]] = v;
    14911504        } else {
    1492           _right.set(_parent[v], v);
     1505          _right[_parent[v]] = v;
    14931506        }
    14941507      }
    14951508      if (_right[w] != INVALID){
    1496         _parent.set(_right[w], w);
     1509        _parent[_right[w]] = w;
    14971510      }
    14981511    }
     
    16261639  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
    16271640  ///
    1628   ///\tparam G The type of the underlying digraph.
     1641  ///\tparam GR The type of the underlying digraph.
    16291642  ///
    16301643  ///\sa DynArcLookUp
    16311644  ///\sa AllArcLookUp
    1632   template<class G>
     1645  template<class GR>
    16331646  class ArcLookUp
    16341647  {
     1648    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1649
    16351650  public:
    1636     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1637     typedef G Digraph;
     1651
     1652    /// The Digraph type
     1653    typedef GR Digraph;
    16381654
    16391655  protected:
     
    17361752  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
    17371753  ///
    1738   ///\tparam G The type of the underlying digraph.
     1754  ///\tparam GR The type of the underlying digraph.
    17391755  ///
    17401756  ///\sa DynArcLookUp
    17411757  ///\sa ArcLookUp
    1742   template<class G>
    1743   class AllArcLookUp : public ArcLookUp<G>
     1758  template<class GR>
     1759  class AllArcLookUp : public ArcLookUp<GR>
    17441760  {
    1745     using ArcLookUp<G>::_g;
    1746     using ArcLookUp<G>::_right;
    1747     using ArcLookUp<G>::_left;
    1748     using ArcLookUp<G>::_head;
    1749 
    1750     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1751     typedef G Digraph;
    1752 
    1753     typename Digraph::template ArcMap<Arc> _next;
     1761    using ArcLookUp<GR>::_g;
     1762    using ArcLookUp<GR>::_right;
     1763    using ArcLookUp<GR>::_left;
     1764    using ArcLookUp<GR>::_head;
     1765
     1766    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1767
     1768    typename GR::template ArcMap<Arc> _next;
    17541769
    17551770    Arc refreshNext(Arc head,Arc next=INVALID)
     
    17701785
    17711786  public:
     1787
     1788    /// The Digraph type
     1789    typedef GR Digraph;
     1790
    17721791    ///Constructor
    17731792
     
    17761795    ///It builds up the search database, which remains valid until the digraph
    17771796    ///changes.
    1778     AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
     1797    AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();}
    17791798
    17801799    ///Refresh the data structure at a node.
     
    17861805    void refresh(Node n)
    17871806    {
    1788       ArcLookUp<G>::refresh(n);
     1807      ArcLookUp<GR>::refresh(n);
    17891808      refreshNext(_head[n]);
    17901809    }
     
    18331852    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
    18341853#else
    1835     using ArcLookUp<G>::operator() ;
     1854    using ArcLookUp<GR>::operator() ;
    18361855    Arc operator()(Node s, Node t, Arc prev) const
    18371856    {
  • lemon/core.h

    r671 r937  
    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

    r899 r937  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    5050    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    52     ///Instantiates a PredMap.
    53 
    54     ///This function instantiates a PredMap.
     52    ///Instantiates a \c PredMap.
     53
     54    ///This function instantiates a \ref PredMap.
    5555    ///\param g is the digraph, to which we would like to define the
    56     ///PredMap.
     56    ///\ref PredMap.
    5757    static PredMap *createPredMap(const Digraph &g)
    5858    {
     
    6565    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6666    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    67     ///Instantiates a ProcessedMap.
    68 
    69     ///This function instantiates a ProcessedMap.
     67    ///Instantiates a \c ProcessedMap.
     68
     69    ///This function instantiates a \ref ProcessedMap.
    7070    ///\param g is the digraph, to which
    71     ///we would like to define the ProcessedMap
     71    ///we would like to define the \ref ProcessedMap.
    7272#ifdef DOXYGEN
    7373    static ProcessedMap *createProcessedMap(const Digraph &g)
     
    8484    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8585    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    86     ///Instantiates a ReachedMap.
    87 
    88     ///This function instantiates a ReachedMap.
     86    ///Instantiates a \c ReachedMap.
     87
     88    ///This function instantiates a \ref ReachedMap.
    8989    ///\param g is the digraph, to which
    90     ///we would like to define the ReachedMap.
     90    ///we would like to define the \ref ReachedMap.
    9191    static ReachedMap *createReachedMap(const Digraph &g)
    9292    {
     
    9999    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    100100    typedef typename Digraph::template NodeMap<int> DistMap;
    101     ///Instantiates a DistMap.
    102 
    103     ///This function instantiates a DistMap.
     101    ///Instantiates a \c DistMap.
     102
     103    ///This function instantiates a \ref DistMap.
    104104    ///\param g is the digraph, to which we would like to define the
    105     ///DistMap.
     105    ///\ref DistMap.
    106106    static DistMap *createDistMap(const Digraph &g)
    107107    {
     
    120120  ///
    121121  ///\tparam GR The type of the digraph the algorithm runs on.
    122   ///The default value is \ref ListDigraph. The value of GR is not used
    123   ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
    124   ///\tparam TR Traits class to set various data types used by the algorithm.
    125   ///The default traits class is
    126   ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
    127   ///See \ref DfsDefaultTraits for the documentation of
    128   ///a Dfs traits class.
     122  ///The default type is \ref ListDigraph.
    129123#ifdef DOXYGEN
    130124  template <typename GR,
     
    152146    typedef PredMapPath<Digraph, PredMap> Path;
    153147
    154     ///The traits class.
     148    ///The \ref DfsDefaultTraits "traits class" of the algorithm.
    155149    typedef TR Traits;
    156150
     
    213207    typedef Dfs Create;
    214208
    215     ///\name Named template parameters
     209    ///\name Named Template Parameters
    216210
    217211    ///@{
     
    227221    };
    228222    ///\brief \ref named-templ-param "Named parameter" for setting
    229     ///PredMap type.
     223    ///\c PredMap type.
    230224    ///
    231225    ///\ref named-templ-param "Named parameter" for setting
    232     ///PredMap type.
     226    ///\c PredMap type.
     227    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    233228    template <class T>
    234229    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
     
    246241    };
    247242    ///\brief \ref named-templ-param "Named parameter" for setting
    248     ///DistMap type.
     243    ///\c DistMap type.
    249244    ///
    250245    ///\ref named-templ-param "Named parameter" for setting
    251     ///DistMap type.
     246    ///\c DistMap type.
     247    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    252248    template <class T>
    253249    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
     
    265261    };
    266262    ///\brief \ref named-templ-param "Named parameter" for setting
    267     ///ReachedMap type.
     263    ///\c ReachedMap type.
    268264    ///
    269265    ///\ref named-templ-param "Named parameter" for setting
    270     ///ReachedMap type.
     266    ///\c ReachedMap type.
     267    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    271268    template <class T>
    272269    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
     
    284281    };
    285282    ///\brief \ref named-templ-param "Named parameter" for setting
    286     ///ProcessedMap type.
     283    ///\c ProcessedMap type.
    287284    ///
    288285    ///\ref named-templ-param "Named parameter" for setting
    289     ///ProcessedMap type.
     286    ///\c ProcessedMap type.
     287    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    290288    template <class T>
    291289    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
     
    301299    };
    302300    ///\brief \ref named-templ-param "Named parameter" for setting
    303     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     301    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    304302    ///
    305303    ///\ref named-templ-param "Named parameter" for setting
    306     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     304    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    307305    ///If you don't set it explicitly, it will be automatically allocated.
    308306    struct SetStandardProcessedMap :
     
    339337
    340338    ///Sets the map that stores the predecessor arcs.
    341     ///If you don't use this function before calling \ref run(),
    342     ///it will allocate one. The destructor deallocates this
    343     ///automatically allocated map, of course.
     339    ///If you don't use this function before calling \ref run(Node) "run()"
     340    ///or \ref init(), an instance will be allocated automatically.
     341    ///The destructor deallocates this automatically allocated map,
     342    ///of course.
    344343    ///\return <tt> (*this) </tt>
    345344    Dfs &predMap(PredMap &m)
     
    356355
    357356    ///Sets the map that indicates which nodes are reached.
    358     ///If you don't use this function before calling \ref run(),
    359     ///it will allocate one. The destructor deallocates this
    360     ///automatically allocated map, of course.
     357    ///If you don't use this function before calling \ref run(Node) "run()"
     358    ///or \ref init(), an instance will be allocated automatically.
     359    ///The destructor deallocates this automatically allocated map,
     360    ///of course.
    361361    ///\return <tt> (*this) </tt>
    362362    Dfs &reachedMap(ReachedMap &m)
     
    373373
    374374    ///Sets the map that indicates which nodes are processed.
    375     ///If you don't use this function before calling \ref run(),
    376     ///it will allocate one. The destructor deallocates this
    377     ///automatically allocated map, of course.
     375    ///If you don't use this function before calling \ref run(Node) "run()"
     376    ///or \ref init(), an instance will be allocated automatically.
     377    ///The destructor deallocates this automatically allocated map,
     378    ///of course.
    378379    ///\return <tt> (*this) </tt>
    379380    Dfs &processedMap(ProcessedMap &m)
     
    391392    ///Sets the map that stores the distances of the nodes calculated by
    392393    ///the algorithm.
    393     ///If you don't use this function before calling \ref run(),
    394     ///it will allocate one. The destructor deallocates this
    395     ///automatically allocated map, of course.
     394    ///If you don't use this function before calling \ref run(Node) "run()"
     395    ///or \ref init(), an instance will be allocated automatically.
     396    ///The destructor deallocates this automatically allocated map,
     397    ///of course.
    396398    ///\return <tt> (*this) </tt>
    397399    Dfs &distMap(DistMap &m)
     
    407409  public:
    408410
    409     ///\name Execution control
    410     ///The simplest way to execute the algorithm is to use
    411     ///one of the member functions called \ref lemon::Dfs::run() "run()".
    412     ///\n
    413     ///If you need more control on the execution, first you must call
    414     ///\ref lemon::Dfs::init() "init()", then you can add a source node
    415     ///with \ref lemon::Dfs::addSource() "addSource()".
    416     ///Finally \ref lemon::Dfs::start() "start()" will perform the
    417     ///actual path computation.
     411    ///\name Execution Control
     412    ///The simplest way to execute the DFS algorithm is to use one of the
     413    ///member functions called \ref run(Node) "run()".\n
     414    ///If you need more control on the execution, first you have to call
     415    ///\ref init(), then you can add a source node with \ref addSource()
     416    ///and perform the actual computation with \ref start().
     417    ///This procedure can be repeated if there are nodes that have not
     418    ///been reached.
    418419
    419420    ///@{
    420421
     422    ///\brief Initializes the internal data structures.
     423    ///
    421424    ///Initializes the internal data structures.
    422 
    423     ///Initializes the internal data structures.
    424     ///
    425425    void init()
    426426    {
     
    439439    ///Adds a new source node to the set of nodes to be processed.
    440440    ///
    441     ///\pre The stack must be empty. (Otherwise the algorithm gives
    442     ///false results.)
    443     ///
    444     ///\warning Distances will be wrong (or at least strange) in case of
    445     ///multiple sources.
     441    ///\pre The stack must be empty. Otherwise the algorithm gives
     442    ///wrong results. (One of the outgoing arcs of all the source nodes
     443    ///except for the last one will not be visited and distances will
     444    ///also be wrong.)
    446445    void addSource(Node s)
    447446    {
     
    507506    }
    508507
    509     ///\brief Returns \c false if there are nodes
    510     ///to be processed.
    511     ///
    512     ///Returns \c false if there are nodes
    513     ///to be processed in the queue (stack).
     508    ///Returns \c false if there are nodes to be processed.
     509
     510    ///Returns \c false if there are nodes to be processed
     511    ///in the queue (stack).
    514512    bool emptyQueue() const { return _stack_head<0; }
    515513
    516514    ///Returns the number of the nodes to be processed.
    517515
    518     ///Returns the number of the nodes to be processed in the queue (stack).
     516    ///Returns the number of the nodes to be processed
     517    ///in the queue (stack).
    519518    int queueSize() const { return _stack_head+1; }
    520519
     
    638637    ///
    639638    ///The algorithm computes
    640     ///- the %DFS tree,
    641     ///- the distance of each node from the root in the %DFS tree.
     639    ///- the %DFS tree (forest),
     640    ///- the distance of each node from the root(s) in the %DFS tree.
    642641    ///
    643642    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
     
    664663
    665664    ///\name Query Functions
    666     ///The result of the %DFS algorithm can be obtained using these
     665    ///The results of the DFS algorithm can be obtained using these
    667666    ///functions.\n
    668     ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
    669     ///"start()" must be called before using them.
     667    ///Either \ref run(Node) "run()" or \ref start() should be called
     668    ///before using them.
    670669
    671670    ///@{
     
    675674    ///Returns the DFS path to a node.
    676675    ///
    677     ///\warning \c t should be reachable from the root.
    678     ///
    679     ///\pre Either \ref run() or \ref start() must be called before
    680     ///using this function.
     676    ///\warning \c t should be reached from the root(s).
     677    ///
     678    ///\pre Either \ref run(Node) "run()" or \ref init()
     679    ///must be called before using this function.
    681680    Path path(Node t) const { return Path(*G, *_pred, t); }
    682681
    683     ///The distance of a node from the root.
    684 
    685     ///Returns the distance of a node from the root.
    686     ///
    687     ///\warning If node \c v is not reachable from the root, then
     682    ///The distance of a node from the root(s).
     683
     684    ///Returns the distance of a node from the root(s).
     685    ///
     686    ///\warning If node \c v is not reached from the root(s), then
    688687    ///the return value of this function is undefined.
    689688    ///
    690     ///\pre Either \ref run() or \ref start() must be called before
    691     ///using this function.
     689    ///\pre Either \ref run(Node) "run()" or \ref init()
     690    ///must be called before using this function.
    692691    int dist(Node v) const { return (*_dist)[v]; }
    693692
     
    695694
    696695    ///This function returns the 'previous arc' of the %DFS tree for the
    697     ///node \c v, i.e. it returns the last arc of a %DFS path from the
    698     ///root to \c v. It is \c INVALID
    699     ///if \c v is not reachable from the root(s) or if \c v is a root.
     696    ///node \c v, i.e. it returns the last arc of a %DFS path from a
     697    ///root to \c v. It is \c INVALID if \c v is not reached from the
     698    ///root(s) or if \c v is a root.
    700699    ///
    701700    ///The %DFS tree used here is equal to the %DFS tree used in
    702701    ///\ref predNode().
    703702    ///
    704     ///\pre Either \ref run() or \ref start() must be called before using
    705     ///this function.
     703    ///\pre Either \ref run(Node) "run()" or \ref init()
     704    ///must be called before using this function.
    706705    Arc predArc(Node v) const { return (*_pred)[v];}
    707706
     
    710709    ///This function returns the 'previous node' of the %DFS
    711710    ///tree for the node \c v, i.e. it returns the last but one node
    712     ///from a %DFS path from the root to \c v. It is \c INVALID
    713     ///if \c v is not reachable from the root(s) or if \c v is a root.
     711    ///from a %DFS path from a root to \c v. It is \c INVALID
     712    ///if \c v is not reached from the root(s) or if \c v is a root.
    714713    ///
    715714    ///The %DFS tree used here is equal to the %DFS tree used in
    716715    ///\ref predArc().
    717716    ///
    718     ///\pre Either \ref run() or \ref start() must be called before
    719     ///using this function.
     717    ///\pre Either \ref run(Node) "run()" or \ref init()
     718    ///must be called before using this function.
    720719    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    721720                                  G->source((*_pred)[v]); }
     
    727726    ///distances of the nodes calculated by the algorithm.
    728727    ///
    729     ///\pre Either \ref run() or \ref init()
     728    ///\pre Either \ref run(Node) "run()" or \ref init()
    730729    ///must be called before using this function.
    731730    const DistMap &distMap() const { return *_dist;}
     
    737736    ///arcs, which form the DFS tree.
    738737    ///
    739     ///\pre Either \ref run() or \ref init()
     738    ///\pre Either \ref run(Node) "run()" or \ref init()
    740739    ///must be called before using this function.
    741740    const PredMap &predMap() const { return *_pred;}
    742741
    743     ///Checks if a node is reachable from the root(s).
    744 
    745     ///Returns \c true if \c v is reachable from the root(s).
    746     ///\pre Either \ref run() or \ref start()
     742    ///Checks if a node is reached from the root(s).
     743
     744    ///Returns \c true if \c v is reached from the root(s).
     745    ///
     746    ///\pre Either \ref run(Node) "run()" or \ref init()
    747747    ///must be called before using this function.
    748748    bool reached(Node v) const { return (*_reached)[v]; }
     
    890890  /// This auxiliary class is created to implement the
    891891  /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
    892   /// It does not have own \ref run() method, it uses the functions
    893   /// and features of the plain \ref Dfs.
     892  /// It does not have own \ref run(Node) "run()" method, it uses the
     893  /// functions and features of the plain \ref Dfs.
    894894  ///
    895895  /// This class should only be used through the \ref dfs() function,
     
    11111111  ///  bool reached = dfs(g).path(p).dist(d).run(s,t);
    11121112  ///\endcode
    1113 
    1114   ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
     1113  ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()"
    11151114  ///to the end of the parameter list.
    11161115  ///\sa DfsWizard
     
    11281127  /// This class defines the interface of the DfsVisit events, and
    11291128  /// it could be the base of a real visitor class.
    1130   template <typename _Digraph>
     1129  template <typename GR>
    11311130  struct DfsVisitor {
    1132     typedef _Digraph Digraph;
     1131    typedef GR Digraph;
    11331132    typedef typename Digraph::Arc Arc;
    11341133    typedef typename Digraph::Node Node;
     
    11661165  };
    11671166#else
    1168   template <typename _Digraph>
     1167  template <typename GR>
    11691168  struct DfsVisitor {
    1170     typedef _Digraph Digraph;
     1169    typedef GR Digraph;
    11711170    typedef typename Digraph::Arc Arc;
    11721171    typedef typename Digraph::Node Node;
     
    12011200  /// Default traits class of DfsVisit class.
    12021201  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1203   template<class _Digraph>
     1202  template<class GR>
    12041203  struct DfsVisitDefaultTraits {
    12051204
    12061205    /// \brief The type of the digraph the algorithm runs on.
    1207     typedef _Digraph Digraph;
     1206    typedef GR Digraph;
    12081207
    12091208    /// \brief The type of the map that indicates which nodes are reached.
     
    12261225  /// \ingroup search
    12271226  ///
    1228   /// \brief %DFS algorithm class with visitor interface.
     1227  /// \brief DFS algorithm class with visitor interface.
    12291228  ///
    1230   /// This class provides an efficient implementation of the %DFS algorithm
     1229  /// This class provides an efficient implementation of the DFS algorithm
    12311230  /// with visitor interface.
    12321231  ///
    1233   /// The %DfsVisit class provides an alternative interface to the Dfs
     1232  /// The DfsVisit class provides an alternative interface to the Dfs
    12341233  /// class. It works with callback mechanism, the DfsVisit object calls
    12351234  /// the member functions of the \c Visitor class on every DFS event.
     
    12401239  /// instead.
    12411240  ///
    1242   /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1243   /// The default value is
    1244   /// \ref ListDigraph. The value of _Digraph is not used directly by
    1245   /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
    1246   /// \tparam _Visitor The Visitor type that is used by the algorithm.
    1247   /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
     1241  /// \tparam GR The type of the digraph the algorithm runs on.
     1242  /// The default type is \ref ListDigraph.
     1243  /// The value of GR is not used directly by \ref DfsVisit,
     1244  /// it is only passed to \ref DfsVisitDefaultTraits.
     1245  /// \tparam VS The Visitor type that is used by the algorithm.
     1246  /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
    12481247  /// does not observe the DFS events. If you want to observe the DFS
    12491248  /// events, you should implement your own visitor class.
    1250   /// \tparam _Traits Traits class to set various data types used by the
     1249  /// \tparam TR Traits class to set various data types used by the
    12511250  /// algorithm. The default traits class is
    1252   /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
     1251  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
    12531252  /// See \ref DfsVisitDefaultTraits for the documentation of
    12541253  /// a DFS visit traits class.
    12551254#ifdef DOXYGEN
    1256   template <typename _Digraph, typename _Visitor, typename _Traits>
     1255  template <typename GR, typename VS, typename TR>
    12571256#else
    1258   template <typename _Digraph = ListDigraph,
    1259             typename _Visitor = DfsVisitor<_Digraph>,
    1260             typename _Traits = DfsVisitDefaultTraits<_Digraph> >
     1257  template <typename GR = ListDigraph,
     1258            typename VS = DfsVisitor<GR>,
     1259            typename TR = DfsVisitDefaultTraits<GR> >
    12611260#endif
    12621261  class DfsVisit {
     
    12641263
    12651264    ///The traits class.
    1266     typedef _Traits Traits;
     1265    typedef TR Traits;
    12671266
    12681267    ///The type of the digraph the algorithm runs on.
     
    12701269
    12711270    ///The visitor type used by the algorithm.
    1272     typedef _Visitor Visitor;
     1271    typedef VS Visitor;
    12731272
    12741273    ///The type of the map that indicates which nodes are reached.
     
    13101309    typedef DfsVisit Create;
    13111310
    1312     /// \name Named template parameters
     1311    /// \name Named Template Parameters
    13131312
    13141313    ///@{
     
    13521351    ///
    13531352    /// Sets the map that indicates which nodes are reached.
    1354     /// If you don't use this function before calling \ref run(),
    1355     /// it will allocate one. The destructor deallocates this
    1356     /// automatically allocated map, of course.
     1353    /// If you don't use this function before calling \ref run(Node) "run()"
     1354    /// or \ref init(), an instance will be allocated automatically.
     1355    /// The destructor deallocates this automatically allocated map,
     1356    /// of course.
    13571357    /// \return <tt> (*this) </tt>
    13581358    DfsVisit &reachedMap(ReachedMap &m) {
     
    13671367  public:
    13681368
    1369     /// \name Execution control
    1370     /// The simplest way to execute the algorithm is to use
    1371     /// one of the member functions called \ref lemon::DfsVisit::run()
    1372     /// "run()".
    1373     /// \n
    1374     /// If you need more control on the execution, first you must call
    1375     /// \ref lemon::DfsVisit::init() "init()", then you can add several
    1376     /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
    1377     /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
    1378     /// actual path computation.
     1369    /// \name Execution Control
     1370    /// The simplest way to execute the DFS algorithm is to use one of the
     1371    /// member functions called \ref run(Node) "run()".\n
     1372    /// If you need more control on the execution, first you have to call
     1373    /// \ref init(), then you can add a source node with \ref addSource()
     1374    /// and perform the actual computation with \ref start().
     1375    /// This procedure can be repeated if there are nodes that have not
     1376    /// been reached.
    13791377
    13801378    /// @{
     
    13921390    }
    13931391
    1394     ///Adds a new source node.
    1395 
    1396     ///Adds a new source node to the set of nodes to be processed.
    1397     ///
    1398     ///\pre The stack must be empty. (Otherwise the algorithm gives
    1399     ///false results.)
    1400     ///
    1401     ///\warning Distances will be wrong (or at least strange) in case of
    1402     ///multiple sources.
     1392    /// \brief Adds a new source node.
     1393    ///
     1394    /// Adds a new source node to the set of nodes to be processed.
     1395    ///
     1396    /// \pre The stack must be empty. Otherwise the algorithm gives
     1397    /// wrong results. (One of the outgoing arcs of all the source nodes
     1398    /// except for the last one will not be visited and distances will
     1399    /// also be wrong.)
    14031400    void addSource(Node s)
    14041401    {
     
    14141411          } else {
    14151412            _visitor->leave(s);
     1413            _visitor->stop(s);
    14161414          }
    14171415        }
     
    15901588    ///
    15911589    /// The algorithm computes
    1592     /// - the %DFS tree,
    1593     /// - the distance of each node from the root in the %DFS tree.
     1590    /// - the %DFS tree (forest),
     1591    /// - the distance of each node from the root(s) in the %DFS tree.
    15941592    ///
    15951593    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
     
    16161614
    16171615    /// \name Query Functions
    1618     /// The result of the %DFS algorithm can be obtained using these
     1616    /// The results of the DFS algorithm can be obtained using these
    16191617    /// functions.\n
    1620     /// Either \ref lemon::DfsVisit::run() "run()" or
    1621     /// \ref lemon::DfsVisit::start() "start()" must be called before
    1622     /// using them.
     1618    /// Either \ref run(Node) "run()" or \ref start() should be called
     1619    /// before using them.
     1620
    16231621    ///@{
    16241622
    1625     /// \brief Checks if a node is reachable from the root(s).
    1626     ///
    1627     /// Returns \c true if \c v is reachable from the root(s).
    1628     /// \pre Either \ref run() or \ref start()
     1623    /// \brief Checks if a node is reached from the root(s).
     1624    ///
     1625    /// Returns \c true if \c v is reached from the root(s).
     1626    ///
     1627    /// \pre Either \ref run(Node) "run()" or \ref init()
    16291628    /// must be called before using this function.
    1630     bool reached(Node v) { return (*_reached)[v]; }
     1629    bool reached(Node v) const { return (*_reached)[v]; }
    16311630
    16321631    ///@}
  • lemon/dfs.h

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

    r837 r937  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6565///Default traits class of \ref GraphToEps.
    6666///
    67 ///\c G is the type of the underlying graph.
    68 template<class G>
     67///\param GR is the type of the underlying graph.
     68template<class GR>
    6969struct DefaultGraphToEpsTraits
    7070{
    71   typedef G Graph;
     71  typedef GR Graph;
     72  typedef GR Digraph;
    7273  typedef typename Graph::Node Node;
    7374  typedef typename Graph::NodeIt NodeIt;
     
    140141
    141142  ///Constructor
    142   ///\param _g  Reference to the graph to be printed.
    143   ///\param _os Reference to the output stream.
    144   ///\param _os Reference to the output stream.
     143  ///\param gr  Reference to the graph to be printed.
     144  ///\param ost Reference to the output stream.
    145145  ///By default it is <tt>std::cout</tt>.
    146   ///\param _pros If it is \c true, then the \c ostream referenced by \c _os
     146  ///\param pros If it is \c true, then the \c ostream referenced by \c os
    147147  ///will be explicitly deallocated by the destructor.
    148   DefaultGraphToEpsTraits(const G &_g,std::ostream& _os=std::cout,
    149                           bool _pros=false) :
    150     g(_g), os(_os),
     148  DefaultGraphToEpsTraits(const GR &gr, std::ostream& ost = std::cout,
     149                          bool pros = false) :
     150    g(gr), os(ost),
    151151    _coords(dim2::Point<double>(1,1)), _nodeSizes(1), _nodeShapes(0),
    152152    _nodeColors(WHITE), _arcColors(BLACK),
     
    159159    _showNodeText(false), _nodeTexts(false), _nodeTextSize(1),
    160160    _showNodePsText(false), _nodePsTexts(false), _nodePsTextsPreamble(0),
    161     _undirected(lemon::UndirectedTagIndicator<G>::value),
    162     _pleaseRemoveOsStream(_pros), _scaleToA4(false),
     161    _undirected(lemon::UndirectedTagIndicator<GR>::value),
     162    _pleaseRemoveOsStream(pros), _scaleToA4(false),
    163163    _nodeTextColorType(SAME_COL), _nodeTextColors(BLACK),
    164164    _autoNodeScale(false),
     
    243243
    244244  typedef typename T::Graph Graph;
     245  typedef typename T::Digraph Digraph;
    245246  typedef typename Graph::Node Node;
    246247  typedef typename Graph::NodeIt NodeIt;
     
    270271    ///\image html nodeshape_1.png
    271272    ///\image latex nodeshape_1.eps "SQUARE shape (1)" width=2cm
    272     ///
    273273    SQUARE=1,
    274274    /// = 2
    275275    ///\image html nodeshape_2.png
    276276    ///\image latex nodeshape_2.eps "DIAMOND shape (2)" width=2cm
    277     ///
    278277    DIAMOND=2,
    279278    /// = 3
    280279    ///\image html nodeshape_3.png
    281     ///\image latex nodeshape_2.eps "MALE shape (4)" width=2cm
    282     ///
     280    ///\image latex nodeshape_3.eps "MALE shape (3)" width=2cm
    283281    MALE=3,
    284282    /// = 4
    285283    ///\image html nodeshape_4.png
    286     ///\image latex nodeshape_2.eps "FEMALE shape (4)" width=2cm
    287     ///
     284    ///\image latex nodeshape_4.eps "FEMALE shape (4)" width=2cm
    288285    FEMALE=4
    289286  };
     
    11351132///to the end of the parameter list.
    11361133///\sa GraphToEps
    1137 ///\sa graphToEps(G &g, const char *file_name)
    1138 template<class G>
    1139 GraphToEps<DefaultGraphToEpsTraits<G> >
    1140 graphToEps(G &g, std::ostream& os=std::cout)
     1134///\sa graphToEps(GR &g, const char *file_name)
     1135template<class GR>
     1136GraphToEps<DefaultGraphToEpsTraits<GR> >
     1137graphToEps(GR &g, std::ostream& os=std::cout)
    11411138{
    11421139  return
    1143     GraphToEps<DefaultGraphToEpsTraits<G> >(DefaultGraphToEpsTraits<G>(g,os));
     1140    GraphToEps<DefaultGraphToEpsTraits<GR> >(DefaultGraphToEpsTraits<GR>(g,os));
    11441141}
    11451142
     
    11481145///\ingroup eps_io
    11491146///This function does the same as
    1150 ///\ref graphToEps(G &g,std::ostream& os)
     1147///\ref graphToEps(GR &g,std::ostream& os)
    11511148///but it writes its output into the file \c file_name
    11521149///instead of a stream.
    1153 ///\sa graphToEps(G &g, std::ostream& os)
    1154 template<class G>
    1155 GraphToEps<DefaultGraphToEpsTraits<G> >
    1156 graphToEps(G &g,const char *file_name)
     1150///\sa graphToEps(GR &g, std::ostream& os)
     1151template<class GR>
     1152GraphToEps<DefaultGraphToEpsTraits<GR> >
     1153graphToEps(GR &g,const char *file_name)
    11571154{
    11581155  std::ostream* os = new std::ofstream(file_name);
     
    11611158    throw IoError("Cannot write file", file_name);
    11621159  }
    1163   return GraphToEps<DefaultGraphToEpsTraits<G> >
    1164     (DefaultGraphToEpsTraits<G>(g,*os,true));
     1160  return GraphToEps<DefaultGraphToEpsTraits<GR> >
     1161    (DefaultGraphToEpsTraits<GR>(g,*os,true));
    11651162}
    11661163
     
    11691166///\ingroup eps_io
    11701167///This function does the same as
    1171 ///\ref graphToEps(G &g,std::ostream& os)
     1168///\ref graphToEps(GR &g,std::ostream& os)
    11721169///but it writes its output into the file \c file_name
    11731170///instead of a stream.
    1174 ///\sa graphToEps(G &g, std::ostream& os)
    1175 template<class G>
    1176 GraphToEps<DefaultGraphToEpsTraits<G> >
    1177 graphToEps(G &g,const std::string& file_name)
     1171///\sa graphToEps(GR &g, std::ostream& os)
     1172template<class GR>
     1173GraphToEps<DefaultGraphToEpsTraits<GR> >
     1174graphToEps(GR &g,const std::string& file_name)
    11781175{
    11791176  std::ostream* os = new std::ofstream(file_name.c_str());
     
    11821179    throw IoError("Cannot write file", file_name);
    11831180  }
    1184   return GraphToEps<DefaultGraphToEpsTraits<G> >
    1185     (DefaultGraphToEpsTraits<G>(g,*os,true));
     1181  return GraphToEps<DefaultGraphToEpsTraits<GR> >
     1182    (DefaultGraphToEpsTraits<GR>(g,*os,true));
    11861183}
    11871184
  • lemon/graph_to_eps.h

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

    r922 r937  
    102102    };
    103103
    104     template <typename _Graph, bool _dir, typename _Map,
     104    template <typename _GR, bool _dir, typename _Map,
    105105              typename _Converter = DefaultConverter<typename _Map::Value> >
    106     class GraphArcMapStorage : public MapStorageBase<typename _Graph::Edge> {
     106    class GraphArcMapStorage : public MapStorageBase<typename _GR::Edge> {
    107107    public:
    108108      typedef _Map Map;
    109109      typedef _Converter Converter;
    110       typedef _Graph Graph;
    111       typedef typename Graph::Edge Item;
     110      typedef _GR GR;
     111      typedef typename GR::Edge Item;
    112112      static const bool dir = _dir;
    113113
    114114    private:
    115       const Graph& _graph;
     115      const GR& _graph;
    116116      Map& _map;
    117117      Converter _converter;
    118118
    119119    public:
    120       GraphArcMapStorage(const Graph& graph, Map& map,
     120      GraphArcMapStorage(const GR& graph, Map& map,
    121121                         const Converter& converter = Converter())
    122122        : _graph(graph), _map(map), _converter(converter) {}
     
    174174    };
    175175
    176     template <typename Graph>
     176    template <typename GR>
    177177    struct GraphArcLookUpConverter {
    178       const Graph& _graph;
    179       const std::map<std::string, typename Graph::Edge>& _map;
    180 
    181       GraphArcLookUpConverter(const Graph& graph,
     178      const GR& _graph;
     179      const std::map<std::string, typename GR::Edge>& _map;
     180
     181      GraphArcLookUpConverter(const GR& graph,
    182182                              const std::map<std::string,
    183                                              typename Graph::Edge>& map)
     183                                             typename GR::Edge>& map)
    184184        : _graph(graph), _map(map) {}
    185185
    186       typename Graph::Arc operator()(const std::string& str) {
     186      typename GR::Arc operator()(const std::string& str) {
    187187        if (str.empty() || (str[0] != '+' && str[0] != '-')) {
    188188          throw FormatError("Item must start with '+' or '-'");
    189189        }
    190         typename std::map<std::string, typename Graph::Edge>
     190        typename std::map<std::string, typename GR::Edge>
    191191          ::const_iterator it = _map.find(str.substr(1));
    192192        if (it == _map.end()) {
     
    388388  }
    389389
    390   template <typename Digraph>
     390  template <typename DGR>
    391391  class DigraphReader;
    392392
    393   template <typename Digraph>
    394   DigraphReader<Digraph> digraphReader(Digraph& digraph,
    395                                        std::istream& is = std::cin);
    396   template <typename Digraph>
    397   DigraphReader<Digraph> digraphReader(Digraph& digraph, const std::string& fn);
    398   template <typename Digraph>
    399   DigraphReader<Digraph> digraphReader(Digraph& digraph, const char *fn);
     393  template <typename TDGR>
     394  DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is = std::cin);
     395  template <typename TDGR>
     396  DigraphReader<TDGR> digraphReader(TDGR& digraph, const std::string& fn);
     397  template <typename TDGR>
     398  DigraphReader<TDGR> digraphReader(TDGR& digraph, const char *fn);
    400399
    401400  /// \ingroup lemon_io
     
    420419  ///
    421420  ///\code
    422   /// DigraphReader<Digraph>(digraph, std::cin).
     421  /// DigraphReader<DGR>(digraph, std::cin).
    423422  ///   nodeMap("coordinates", coord_map).
    424423  ///   arcMap("capacity", cap_map).
     
    449448  /// a single pass, because the arcs are not constructed when the node
    450449  /// maps are read.
    451   template <typename _Digraph>
     450  template <typename DGR>
    452451  class DigraphReader {
    453452  public:
    454453
    455     typedef _Digraph Digraph;
    456     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
     454    typedef DGR Digraph;
    457455
    458456  private:
    459457
     458    TEMPLATE_DIGRAPH_TYPEDEFS(DGR);
    460459
    461460    std::istream* _is;
     
    463462    std::string _filename;
    464463
    465     Digraph& _digraph;
     464    DGR& _digraph;
    466465
    467466    std::string _nodes_caption;
     
    501500    /// Construct a directed graph reader, which reads from the given
    502501    /// input stream.
    503     DigraphReader(Digraph& digraph, std::istream& is = std::cin)
     502    DigraphReader(DGR& digraph, std::istream& is = std::cin)
    504503      : _is(&is), local_is(false), _digraph(digraph),
    505504        _use_nodes(false), _use_arcs(false),
     
    510509    /// Construct a directed graph reader, which reads from the given
    511510    /// file.
    512     DigraphReader(Digraph& digraph, const std::string& fn)
     511    DigraphReader(DGR& digraph, const std::string& fn)
    513512      : _is(new std::ifstream(fn.c_str())), local_is(true),
    514513        _filename(fn), _digraph(digraph),
     
    525524    /// Construct a directed graph reader, which reads from the given
    526525    /// file.
    527     DigraphReader(Digraph& digraph, const char* fn)
     526    DigraphReader(DGR& digraph, const char* fn)
    528527      : _is(new std::ifstream(fn)), local_is(true),
    529528        _filename(fn), _digraph(digraph),
     
    561560  private:
    562561
    563     template <typename DGR>
    564     friend DigraphReader<DGR> digraphReader(DGR& digraph, std::istream& is);
    565     template <typename DGR>
    566     friend DigraphReader<DGR> digraphReader(DGR& digraph,
    567                                             const std::string& fn);
    568     template <typename DGR>
    569     friend DigraphReader<DGR> digraphReader(DGR& digraph, const char *fn);
     562    template <typename TDGR>
     563    friend DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is);
     564    template <typename TDGR>
     565    friend DigraphReader<TDGR> digraphReader(TDGR& digraph,
     566                                             const std::string& fn);
     567    template <typename TDGR>
     568    friend DigraphReader<TDGR> digraphReader(TDGR& digraph, const char *fn);
    570569
    571570    DigraphReader(DigraphReader& other)
     
    594593  public:
    595594
    596     /// \name Reading rules
     595    /// \name Reading Rules
    597596    /// @{
    598597
     
    699698    /// @}
    700699
    701     /// \name Select section by name
     700    /// \name Select Section by Name
    702701    /// @{
    703702
     
    728727    /// @}
    729728
    730     /// \name Using previously constructed node or arc set
     729    /// \name Using Previously Constructed Node or Arc Set
    731730    /// @{
    732731
     
    848847        readLine();
    849848      }
    850       line.putback(c);
     849      if (readSuccess()) {
     850        line.putback(c);
     851      }
    851852    }
    852853
     
    11221123  public:
    11231124
    1124     /// \name Execution of the reader
     1125    /// \name Execution of the Reader
    11251126    /// @{
    11261127
     
    11941195
    11951196  };
     1197 
     1198  /// \ingroup lemon_io
     1199  ///
     1200  /// \brief Return a \ref DigraphReader class
     1201  ///
     1202  /// This function just returns a \ref DigraphReader class.
     1203  ///
     1204  /// With this function a digraph can be read from an
     1205  /// \ref lgf-format "LGF" file or input stream with several maps and
     1206  /// attributes. For example, there is network flow problem on a
     1207  /// digraph, i.e. a digraph with a \e capacity map on the arcs and
     1208  /// \e source and \e target nodes. This digraph can be read with the
     1209  /// following code:
     1210  ///
     1211  ///\code
     1212  ///ListDigraph digraph;
     1213  ///ListDigraph::ArcMap<int> cm(digraph);
     1214  ///ListDigraph::Node src, trg;
     1215  ///digraphReader(digraph, std::cin).
     1216  ///  arcMap("capacity", cap).
     1217  ///  node("source", src).
     1218  ///  node("target", trg).
     1219  ///  run();
     1220  ///\endcode
     1221  ///
     1222  /// For a complete documentation, please see the \ref DigraphReader
     1223  /// class documentation.
     1224  /// \warning Don't forget to put the \ref DigraphReader::run() "run()"
     1225  /// to the end of the parameter list.
     1226  /// \relates DigraphReader
     1227  /// \sa digraphReader(TDGR& digraph, const std::string& fn)
     1228  /// \sa digraphReader(TDGR& digraph, const char* fn)
     1229  template <typename TDGR>
     1230  DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is) {
     1231    DigraphReader<TDGR> tmp(digraph, is);
     1232    return tmp;
     1233  }
    11961234
    11971235  /// \brief Return a \ref DigraphReader class
     
    11991237  /// This function just returns a \ref DigraphReader class.
    12001238  /// \relates DigraphReader
    1201   template <typename Digraph>
    1202   DigraphReader<Digraph> digraphReader(Digraph& digraph, std::istream& is) {
    1203     DigraphReader<Digraph> tmp(digraph, is);
     1239  /// \sa digraphReader(TDGR& digraph, std::istream& is)
     1240  template <typename TDGR>
     1241  DigraphReader<TDGR> digraphReader(TDGR& digraph, const std::string& fn) {
     1242    DigraphReader<TDGR> tmp(digraph, fn);
    12041243    return tmp;
    12051244  }
     
    12091248  /// This function just returns a \ref DigraphReader class.
    12101249  /// \relates DigraphReader
    1211   template <typename Digraph>
    1212   DigraphReader<Digraph> digraphReader(Digraph& digraph,
    1213                                        const std::string& fn) {
    1214     DigraphReader<Digraph> tmp(digraph, fn);
     1250  /// \sa digraphReader(TDGR& digraph, std::istream& is)
     1251  template <typename TDGR>
     1252  DigraphReader<TDGR> digraphReader(TDGR& digraph, const char* fn) {
     1253    DigraphReader<TDGR> tmp(digraph, fn);
    12151254    return tmp;
    12161255  }
    12171256
    1218   /// \brief Return a \ref DigraphReader class
    1219   ///
    1220   /// This function just returns a \ref DigraphReader class.
    1221   /// \relates DigraphReader
    1222   template <typename Digraph>
    1223   DigraphReader<Digraph> digraphReader(Digraph& digraph, const char* fn) {
    1224     DigraphReader<Digraph> tmp(digraph, fn);
    1225     return tmp;
    1226   }
    1227 
    1228   template <typename Graph>
     1257  template <typename GR>
    12291258  class GraphReader;
    12301259 
    1231   template <typename Graph>
    1232   GraphReader<Graph> graphReader(Graph& graph,
    1233                                  std::istream& is = std::cin);
    1234   template <typename Graph>
    1235   GraphReader<Graph> graphReader(Graph& graph, const std::string& fn);
    1236   template <typename Graph>
    1237   GraphReader<Graph> graphReader(Graph& graph, const char *fn);
     1260  template <typename TGR>
     1261  GraphReader<TGR> graphReader(TGR& graph, std::istream& is = std::cin);
     1262  template <typename TGR>
     1263  GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
     1264  template <typename TGR>
     1265  GraphReader<TGR> graphReader(TGR& graph, const char *fn);
    12381266
    12391267  /// \ingroup lemon_io
     
    12521280  /// arc map.  Similarly, an attribute can be read into an arc, if
    12531281  /// it's value is an edge label prefixed with \c '+' or \c '-'.
    1254   template <typename _Graph>
     1282  template <typename GR>
    12551283  class GraphReader {
    12561284  public:
    12571285
    1258     typedef _Graph Graph;
    1259     TEMPLATE_GRAPH_TYPEDEFS(Graph);
     1286    typedef GR Graph;
    12601287
    12611288  private:
     1289
     1290    TEMPLATE_GRAPH_TYPEDEFS(GR);
    12621291
    12631292    std::istream* _is;
     
    12651294    std::string _filename;
    12661295
    1267     Graph& _graph;
     1296    GR& _graph;
    12681297
    12691298    std::string _nodes_caption;
     
    13031332    /// Construct an undirected graph reader, which reads from the given
    13041333    /// input stream.
    1305     GraphReader(Graph& graph, std::istream& is = std::cin)
     1334    GraphReader(GR& graph, std::istream& is = std::cin)
    13061335      : _is(&is), local_is(false), _graph(graph),
    13071336        _use_nodes(false), _use_edges(false),
     
    13121341    /// Construct an undirected graph reader, which reads from the given
    13131342    /// file.
    1314     GraphReader(Graph& graph, const std::string& fn)
     1343    GraphReader(GR& graph, const std::string& fn)
    13151344      : _is(new std::ifstream(fn.c_str())), local_is(true),
    13161345        _filename(fn), _graph(graph),
     
    13271356    /// Construct an undirected graph reader, which reads from the given
    13281357    /// file.
    1329     GraphReader(Graph& graph, const char* fn)
     1358    GraphReader(GR& graph, const char* fn)
    13301359      : _is(new std::ifstream(fn)), local_is(true),
    13311360        _filename(fn), _graph(graph),
     
    13621391
    13631392  private:
    1364     template <typename GR>
    1365     friend GraphReader<GR> graphReader(GR& graph, std::istream& is);
    1366     template <typename GR>
    1367     friend GraphReader<GR> graphReader(GR& graph, const std::string& fn);
    1368     template <typename GR>
    1369     friend GraphReader<GR> graphReader(GR& graph, const char *fn);
     1393    template <typename TGR>
     1394    friend GraphReader<TGR> graphReader(TGR& graph, std::istream& is);
     1395    template <typename TGR>
     1396    friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
     1397    template <typename TGR>
     1398    friend GraphReader<TGR> graphReader(TGR& graph, const char *fn);
    13701399
    13711400    GraphReader(GraphReader& other)
     
    13941423  public:
    13951424
    1396     /// \name Reading rules
     1425    /// \name Reading Rules
    13971426    /// @{
    13981427
     
    14591488      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
    14601489      _reader_bits::MapStorageBase<Edge>* backward_storage =
    1461         new _reader_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
     1490        new _reader_bits::GraphArcMapStorage<GR, false, Map>(_graph, map);
    14621491      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
    14631492      return *this;
     
    14731502      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
    14741503      _reader_bits::MapStorageBase<Edge>* forward_storage =
    1475         new _reader_bits::GraphArcMapStorage<Graph, true, Map, Converter>
     1504        new _reader_bits::GraphArcMapStorage<GR, true, Map, Converter>
    14761505        (_graph, map, converter);
    14771506      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
    14781507      _reader_bits::MapStorageBase<Edge>* backward_storage =
    1479         new _reader_bits::GraphArcMapStorage<Graph, false, Map, Converter>
     1508        new _reader_bits::GraphArcMapStorage<GR, false, Map, Converter>
    14801509        (_graph, map, converter);
    14811510      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
     
    15351564    /// Add an arc reading rule to reader.
    15361565    GraphReader& arc(const std::string& caption, Arc& arc) {
    1537       typedef _reader_bits::GraphArcLookUpConverter<Graph> Converter;
     1566      typedef _reader_bits::GraphArcLookUpConverter<GR> Converter;
    15381567      Converter converter(_graph, _edge_index);
    15391568      _reader_bits::ValueStorageBase* storage =
     
    15451574    /// @}
    15461575
    1547     /// \name Select section by name
     1576    /// \name Select Section by Name
    15481577    /// @{
    15491578
     
    15741603    /// @}
    15751604
    1576     /// \name Using previously constructed node or edge set
     1605    /// \name Using Previously Constructed Node or Edge Set
    15771606    /// @{
    15781607
     
    16951724        readLine();
    16961725      }
    1697       line.putback(c);
     1726      if (readSuccess()) {
     1727        line.putback(c);
     1728      }
    16981729    }
    16991730
     
    19692000  public:
    19702001
    1971     /// \name Execution of the reader
     2002    /// \name Execution of the Reader
    19722003    /// @{
    19732004
     
    20432074  };
    20442075
     2076  /// \ingroup lemon_io
     2077  ///
     2078  /// \brief Return a \ref GraphReader class
     2079  ///
     2080  /// This function just returns a \ref GraphReader class.
     2081  ///
     2082  /// With this function a graph can be read from an
     2083  /// \ref lgf-format "LGF" file or input stream with several maps and
     2084  /// attributes. For example, there is weighted matching problem on a
     2085  /// graph, i.e. a graph with a \e weight map on the edges. This
     2086  /// graph can be read with the following code:
     2087  ///
     2088  ///\code
     2089  ///ListGraph graph;
     2090  ///ListGraph::EdgeMap<int> weight(graph);
     2091  ///graphReader(graph, std::cin).
     2092  ///  edgeMap("weight", weight).
     2093  ///  run();
     2094  ///\endcode
     2095  ///
     2096  /// For a complete documentation, please see the \ref GraphReader
     2097  /// class documentation.
     2098  /// \warning Don't forget to put the \ref GraphReader::run() "run()"
     2099  /// to the end of the parameter list.
     2100  /// \relates GraphReader
     2101  /// \sa graphReader(TGR& graph, const std::string& fn)
     2102  /// \sa graphReader(TGR& graph, const char* fn)
     2103  template <typename TGR>
     2104  GraphReader<TGR> graphReader(TGR& graph, std::istream& is) {
     2105    GraphReader<TGR> tmp(graph, is);
     2106    return tmp;
     2107  }
     2108
    20452109  /// \brief Return a \ref GraphReader class
    20462110  ///
    20472111  /// This function just returns a \ref GraphReader class.
    20482112  /// \relates GraphReader
    2049   template <typename Graph>
    2050   GraphReader<Graph> graphReader(Graph& graph, std::istream& is) {
    2051     GraphReader<Graph> tmp(graph, is);
     2113  /// \sa graphReader(TGR& graph, std::istream& is)
     2114  template <typename TGR>
     2115  GraphReader<TGR> graphReader(TGR& graph, const std::string& fn) {
     2116    GraphReader<TGR> tmp(graph, fn);
    20522117    return tmp;
    20532118  }
     
    20572122  /// This function just returns a \ref GraphReader class.
    20582123  /// \relates GraphReader
    2059   template <typename Graph>
    2060   GraphReader<Graph> graphReader(Graph& graph, const std::string& fn) {
    2061     GraphReader<Graph> tmp(graph, fn);
    2062     return tmp;
    2063   }
    2064 
    2065   /// \brief Return a \ref GraphReader class
    2066   ///
    2067   /// This function just returns a \ref GraphReader class.
    2068   /// \relates GraphReader
    2069   template <typename Graph>
    2070   GraphReader<Graph> graphReader(Graph& graph, const char* fn) {
    2071     GraphReader<Graph> tmp(graph, fn);
     2124  /// \sa graphReader(TGR& graph, std::istream& is)
     2125  template <typename TGR>
     2126  GraphReader<TGR> graphReader(TGR& graph, const char* fn) {
     2127    GraphReader<TGR> tmp(graph, fn);
    20722128    return tmp;
    20732129  }
     
    21682224  public:
    21692225
    2170     /// \name Section readers
     2226    /// \name Section Readers
    21712227    /// @{
    21722228
     
    22592315        readLine();
    22602316      }
    2261       line.putback(c);
     2317      if (readSuccess()) {
     2318        line.putback(c);
     2319      }
    22622320    }
    22632321
     
    22652323
    22662324
    2267     /// \name Execution of the reader
     2325    /// \name Execution of the Reader
    22682326    /// @{
    22692327
     
    23242382  };
    23252383
     2384  /// \ingroup lemon_io
     2385  ///
    23262386  /// \brief Return a \ref SectionReader class
    23272387  ///
    23282388  /// This function just returns a \ref SectionReader class.
     2389  ///
     2390  /// Please see SectionReader documentation about the custom section
     2391  /// input.
     2392  ///
    23292393  /// \relates SectionReader
     2394  /// \sa sectionReader(const std::string& fn)
     2395  /// \sa sectionReader(const char *fn)
    23302396  inline SectionReader sectionReader(std::istream& is) {
    23312397    SectionReader tmp(is);
     
    23372403  /// This function just returns a \ref SectionReader class.
    23382404  /// \relates SectionReader
     2405  /// \sa sectionReader(std::istream& is)
    23392406  inline SectionReader sectionReader(const std::string& fn) {
    23402407    SectionReader tmp(fn);
     
    23462413  /// This function just returns a \ref SectionReader class.
    23472414  /// \relates SectionReader
     2415  /// \sa sectionReader(std::istream& is)
    23482416  inline SectionReader sectionReader(const char* fn) {
    23492417    SectionReader tmp(fn);
     
    24472515
    24482516
    2449     /// \name Node sections
     2517    /// \name Node Sections
    24502518    /// @{
    24512519
     
    24732541    /// @}
    24742542
    2475     /// \name Arc/Edge sections
     2543    /// \name Arc/Edge Sections
    24762544    /// @{
    24772545
     
    25312599    /// @}
    25322600
    2533     /// \name Attribute sections
     2601    /// \name Attribute Sections
    25342602    /// @{
    25352603
     
    25572625    /// @}
    25582626
    2559     /// \name Extra sections
     2627    /// \name Extra Sections
    25602628    /// @{
    25612629
     
    26002668        readLine();
    26012669      }
    2602       line.putback(c);
     2670      if (readSuccess()) {
     2671        line.putback(c);
     2672      }
    26032673    }
    26042674
     
    26312701  public:
    26322702
    2633     /// \name Execution of the contents reader
     2703    /// \name Execution of the Contents Reader
    26342704    /// @{
    26352705
  • lemon/lgf_reader.h

    r599 r937  
    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

    r922 r937  
    11INCLUDE_DIRECTORIES(
    2   ${CMAKE_SOURCE_DIR}
     2  ${PROJECT_SOURCE_DIR}
    33  ${PROJECT_BINARY_DIR}
    44)
    55
    6 LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
     6LINK_DIRECTORIES(
     7  ${PROJECT_BINARY_DIR}/lemon
     8)
     9
     10SET(TEST_WITH_VALGRIND "NO" CACHE STRING
     11  "Run the test with valgrind (YES/NO).")
     12SET(VALGRIND_FLAGS "" CACHE STRING "Valgrind flags used by the tests.")
    713
    814SET(TESTS
     15  adaptors_test
    916  bfs_test
     17  circulation_test
     18  connectivity_test
    1019  counter_test
    1120  dfs_test
     
    1322  dijkstra_test
    1423  dim_test
     24  edge_set_test
    1525  error_test
     26  euler_test
     27  gomory_hu_test
    1628  graph_copy_test
    1729  graph_test
    1830  graph_utils_test
     31  hao_orlin_test
    1932  heap_test
    2033  kruskal_test
    2134  lgf_test
    2235  maps_test
     36  matching_test
     37  min_cost_arborescence_test
     38  min_cost_flow_test
     39  path_test
     40  preflow_test
     41  radix_sort_test
    2342  random_test
    24   path_test
     43  suurballe_test
    2544  time_measure_test
    26   unionfind_test)
     45  unionfind_test
     46)
     47
     48IF(LEMON_HAVE_LP)
     49  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     50    ADD_EXECUTABLE(lp_test lp_test.cc)
     51  ELSE()
     52    ADD_EXECUTABLE(lp_test EXCLUDE_FROM_ALL lp_test.cc)
     53  ENDIF()
     54
     55  SET(LP_TEST_LIBS lemon)
     56
     57  IF(LEMON_HAVE_GLPK)
     58    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${GLPK_LIBRARIES})
     59  ENDIF()
     60  IF(LEMON_HAVE_CPLEX)
     61    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${CPLEX_LIBRARIES})
     62  ENDIF()
     63  IF(LEMON_HAVE_CLP)
     64    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${COIN_CLP_LIBRARIES})
     65  ENDIF()
     66
     67  TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS})
     68  ADD_TEST(lp_test lp_test)
     69  ADD_DEPENDENCIES(check lp_test)
     70
     71  IF(WIN32 AND LEMON_HAVE_GLPK)
     72    GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)
     73    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
     74    ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
     75      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}
     76      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}
     77      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
     78    )
     79  ENDIF()
     80
     81  IF(WIN32 AND LEMON_HAVE_CPLEX)
     82    GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)
     83    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
     84    ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
     85      COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
     86    )
     87  ENDIF()
     88ENDIF()
     89
     90IF(LEMON_HAVE_MIP)
     91  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     92    ADD_EXECUTABLE(mip_test mip_test.cc)
     93  ELSE()
     94    ADD_EXECUTABLE(mip_test EXCLUDE_FROM_ALL mip_test.cc)
     95  ENDIF()
     96
     97  SET(MIP_TEST_LIBS lemon)
     98
     99  IF(LEMON_HAVE_GLPK)
     100    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${GLPK_LIBRARIES})
     101  ENDIF()
     102  IF(LEMON_HAVE_CPLEX)
     103    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${CPLEX_LIBRARIES})
     104  ENDIF()
     105  IF(LEMON_HAVE_CBC)
     106    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${COIN_CBC_LIBRARIES})
     107  ENDIF()
     108
     109  TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS})
     110  ADD_TEST(mip_test mip_test)
     111  ADD_DEPENDENCIES(check mip_test)
     112
     113  IF(WIN32 AND LEMON_HAVE_GLPK)
     114    GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION)
     115    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
     116    ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD
     117      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}
     118      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}
     119      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
     120    )
     121  ENDIF()
     122
     123  IF(WIN32 AND LEMON_HAVE_CPLEX)
     124    GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION)
     125    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
     126    ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD
     127      COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
     128    )
     129  ENDIF()
     130ENDIF()
    27131
    28132FOREACH(TEST_NAME ${TESTS})
    29   ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
     133  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     134    ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
     135  ELSE()
     136    ADD_EXECUTABLE(${TEST_NAME} EXCLUDE_FROM_ALL ${TEST_NAME}.cc)
     137  ENDIF()
    30138  TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)
    31   ADD_TEST(${TEST_NAME} ${TEST_NAME})
    32 ENDFOREACH(TEST_NAME)
     139    IF(TEST_WITH_VALGRIND)
     140      ADD_TEST(${TEST_NAME}
     141        valgrind --error-exitcode=1 ${VALGRIND_FLAGS}
     142        ${CMAKE_CURRENT_BINARY_DIR}/${TEST_NAME} )
     143    ELSE()
     144      ADD_TEST(${TEST_NAME} ${TEST_NAME})
     145    ENDIF()
     146  ADD_DEPENDENCIES(check ${TEST_NAME})
     147ENDFOREACH()
  • test/CMakeLists.txt

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

    r922 r937  
    44noinst_HEADERS += \
    55        test/graph_test.h \
    6         test/test_tools.h
     6        test/test_tools.h
    77
    88check_PROGRAMS += \
     9        test/adaptors_test \
    910        test/bfs_test \
    10         test/counter_test \
     11        test/circulation_test \
     12        test/connectivity_test \
     13        test/counter_test \
    1114        test/dfs_test \
    1215        test/digraph_test \
    1316        test/dijkstra_test \
    14         test/dim_test \
     17        test/dim_test \
     18        test/edge_set_test \
    1519        test/error_test \
     20        test/euler_test \
     21        test/gomory_hu_test \
    1622        test/graph_copy_test \
    1723        test/graph_test \
    1824        test/graph_utils_test \
     25        test/hao_orlin_test \
    1926        test/heap_test \
    2027        test/kruskal_test \
    2128        test/lgf_test \
    22         test/maps_test \
    23         test/random_test \
    24         test/path_test \
    25         test/test_tools_fail \
    26         test/test_tools_pass \
    27         test/time_measure_test \
     29        test/maps_test \
     30        test/matching_test \
     31        test/min_cost_arborescence_test \
     32        test/min_cost_flow_test \
     33        test/path_test \
     34        test/preflow_test \
     35        test/radix_sort_test \
     36        test/random_test \
     37        test/suurballe_test \
     38        test/test_tools_fail \
     39        test/test_tools_pass \
     40        test/time_measure_test \
    2841        test/unionfind_test
     42
     43test_test_tools_pass_DEPENDENCIES = demo
     44
     45if HAVE_LP
     46check_PROGRAMS += test/lp_test
     47endif HAVE_LP
     48if HAVE_MIP
     49check_PROGRAMS += test/mip_test
     50endif HAVE_MIP
    2951
    3052TESTS += $(check_PROGRAMS)
    3153XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
    3254
     55test_adaptors_test_SOURCES = test/adaptors_test.cc
    3356test_bfs_test_SOURCES = test/bfs_test.cc
     57test_circulation_test_SOURCES = test/circulation_test.cc
    3458test_counter_test_SOURCES = test/counter_test.cc
     59test_connectivity_test_SOURCES = test/connectivity_test.cc
    3560test_dfs_test_SOURCES = test/dfs_test.cc
    3661test_digraph_test_SOURCES = test/digraph_test.cc
    3762test_dijkstra_test_SOURCES = test/dijkstra_test.cc
    3863test_dim_test_SOURCES = test/dim_test.cc
     64test_edge_set_test_SOURCES = test/edge_set_test.cc
    3965test_error_test_SOURCES = test/error_test.cc
     66test_euler_test_SOURCES = test/euler_test.cc
     67test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc
    4068test_graph_copy_test_SOURCES = test/graph_copy_test.cc
    4169test_graph_test_SOURCES = test/graph_test.cc
     
    4371test_heap_test_SOURCES = test/heap_test.cc
    4472test_kruskal_test_SOURCES = test/kruskal_test.cc
     73test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
    4574test_lgf_test_SOURCES = test/lgf_test.cc
     75test_lp_test_SOURCES = test/lp_test.cc
    4676test_maps_test_SOURCES = test/maps_test.cc
     77test_mip_test_SOURCES = test/mip_test.cc
     78test_matching_test_SOURCES = test/matching_test.cc
     79test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
     80test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
    4781test_path_test_SOURCES = test/path_test.cc
     82test_preflow_test_SOURCES = test/preflow_test.cc
     83test_radix_sort_test_SOURCES = test/radix_sort_test.cc
     84test_suurballe_test_SOURCES = test/suurballe_test.cc
    4885test_random_test_SOURCES = test/random_test.cc
    4986test_test_tools_fail_SOURCES = test/test_tools_fail.cc
  • test/Makefile.am

    r649 r937  
    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

    r899 r937  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6666  Node s, t;
    6767  Arc e;
    68   int l;
     68  int l, i;
    6969  bool b;
    7070  DType::DistMap d(G);
    7171  DType::PredMap p(G);
    7272  Path<Digraph> pp;
     73  concepts::ReadMap<Arc,bool> am;
    7374
    7475  {
    7576    DType dfs_test(G);
     77    const DType& const_dfs_test = dfs_test;
    7678
    7779    dfs_test.run(s);
     
    7981    dfs_test.run();
    8082
    81     l  = dfs_test.dist(t);
    82     e  = dfs_test.predArc(t);
    83     s  = dfs_test.predNode(t);
    84     b  = dfs_test.reached(t);
    85     d  = dfs_test.distMap();
    86     p  = dfs_test.predMap();
    87     pp = dfs_test.path(t);
     83    dfs_test.init();
     84    dfs_test.addSource(s);
     85    e = dfs_test.processNextArc();
     86    e = const_dfs_test.nextArc();
     87    b = const_dfs_test.emptyQueue();
     88    i = const_dfs_test.queueSize();
     89   
     90    dfs_test.start();
     91    dfs_test.start(t);
     92    dfs_test.start(am);
     93
     94    l  = const_dfs_test.dist(t);
     95    e  = const_dfs_test.predArc(t);
     96    s  = const_dfs_test.predNode(t);
     97    b  = const_dfs_test.reached(t);
     98    d  = const_dfs_test.distMap();
     99    p  = const_dfs_test.predMap();
     100    pp = const_dfs_test.path(t);
    88101  }
    89102  {
     
    92105      ::SetDistMap<concepts::ReadWriteMap<Node,int> >
    93106      ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
     107      ::SetStandardProcessedMap
    94108      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
    95       ::SetStandardProcessedMap
    96109      ::Create dfs_test(G);
     110
     111    concepts::ReadWriteMap<Node,Arc> pred_map;
     112    concepts::ReadWriteMap<Node,int> dist_map;
     113    concepts::ReadWriteMap<Node,bool> reached_map;
     114    concepts::WriteMap<Node,bool> processed_map;
     115   
     116    dfs_test
     117      .predMap(pred_map)
     118      .distMap(dist_map)
     119      .reachedMap(reached_map)
     120      .processedMap(processed_map);
    97121
    98122    dfs_test.run(s);
    99123    dfs_test.run(s,t);
    100124    dfs_test.run();
     125    dfs_test.init();
     126
     127    dfs_test.addSource(s);
     128    e = dfs_test.processNextArc();
     129    e = dfs_test.nextArc();
     130    b = dfs_test.emptyQueue();
     131    i = dfs_test.queueSize();
     132   
     133    dfs_test.start();
     134    dfs_test.start(t);
     135    dfs_test.start(am);
    101136
    102137    l  = dfs_test.dist(t);
  • test/dfs_test.cc

    r585 r937  
    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

    r893 r896  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • test/graph_copy_test.cc

    r440 r896  
    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.