COIN-OR::LEMON - Graph Library

Changeset 937:17e36e175725 in lemon-1.2 for lemon


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

Location:
lemon
Files:
12 edited

Legend:

Unmodified
Added
Removed
  • 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;
Note: See TracChangeset for help on using the changeset viewer.