Changes in / [833:e20173729589:835:c92296660262] in lemon

Files:

• Makefile.am (modified) (1 diff)
• doc/Doxyfile.in (modified) (3 diffs)
• doc/groups.dox (modified) (8 diffs)
• doc/mainpage.dox (modified) (2 diffs)
• doc/min_cost_flow.dox (modified) (1 diff)
• doc/references.bib (modified) (15 diffs)
• lemon/Makefile.am (modified) (2 diffs)
• lemon/adaptors.h (modified) (10 diffs)
• lemon/bellman_ford.h (modified) (2 diffs)
• lemon/bfs.h (modified) (3 diffs)
• lemon/bits/graph_extender.h (modified) (2 diffs)
• lemon/dfs.h (modified) (3 diffs)
• lemon/dijkstra.h (modified) (1 diff)
• lemon/edge_set.h (modified) (7 diffs)
• lemon/full_graph.h (modified) (8 diffs)
• lemon/grid_graph.h (modified) (1 diff)
• lemon/hartmann_orlin.h (added)
• lemon/howard.h (added)
• lemon/hypercube_graph.h (modified) (3 diffs)
• lemon/karp.h (added)
• lemon/list_graph.h (modified) (8 diffs)
• lemon/network_simplex.h (modified) (1 diff)
• lemon/path.h (modified) (11 diffs)
• lemon/preflow.h (modified) (1 diff)
• lemon/smart_graph.h (modified) (5 diffs)
• lemon/static_graph.h (added)
• scripts/bib2dox.py (modified) (3 diffs)
• test/CMakeLists.txt (modified) (1 diff)
• test/Makefile.am (modified) (2 diffs)
• test/adaptors_test.cc (modified) (3 diffs)
• test/bellman_ford_test.cc (modified) (2 diffs)
• test/digraph_test.cc (modified) (4 diffs)
• test/min_mean_cycle_test.cc (added)
• test/test_tools.h (modified) (1 diff)

Makefile.am

@@ -18 +18 @@
         cmake/FindGLPK.cmake \
         cmake/FindCOIN.cmake \
+        cmake/LEMONConfig.cmake.in \
         cmake/version.cmake.in \
         cmake/version.cmake \

doc/Doxyfile.in

@@ -1 @@
-# Doxyfile 1.5.7.1
+# Doxyfile 1.5.9
 
 #---------------------------------------------------------------------------
@@ -22 +22 @@
 QT_AUTOBRIEF           = NO
 MULTILINE_CPP_IS_BRIEF = NO
-DETAILS_AT_TOP         = YES
 INHERIT_DOCS           = NO
 SEPARATE_MEMBER_PAGES  = NO
@@ -225 +224 @@
 SKIP_FUNCTION_MACROS   = YES
 #---------------------------------------------------------------------------
-# Configuration::additions related to external references   
+# Options related to the search engine   
 #---------------------------------------------------------------------------
 TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "

doc/groups.dox

@@ -317 +317 @@
 
 This group contains the common graph search algorithms, namely
-\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
+\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
+\ref clrs01algorithms.
 */
 
@@ -325 +326 @@
 \brief Algorithms for finding shortest paths.
 
-This group contains the algorithms for finding shortest paths in digraphs.
+This group contains the algorithms for finding shortest paths in digraphs
+\ref clrs01algorithms.
 
  - \ref Dijkstra algorithm for finding shortest paths from a source node
@@ -347 +349 @@
 
 This group contains the algorithms for finding minimum cost spanning
-trees and arborescences.
+trees and arborescences \ref clrs01algorithms.
 */
 
@@ -356 +358 @@
 
 This group contains the algorithms for finding maximum flows and
-feasible circulations.
+feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
 
 The \e maximum \e flow \e problem is to find a flow of maximum value between
@@ -371 +373 @@
 
 LEMON contains several algorithms for solving maximum flow problems:
-- \ref EdmondsKarp Edmonds-Karp algorithm.
-- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
-- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
-- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
-
-In most cases the \ref Preflow "Preflow" algorithm provides the
+- \ref EdmondsKarp Edmonds-Karp algorithm
+  \ref edmondskarp72theoretical.
+- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
+  \ref goldberg88newapproach.
+- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
+  \ref dinic70algorithm, \ref sleator83dynamic.
+- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
+  \ref goldberg88newapproach, \ref sleator83dynamic.
+
+In most cases the \ref Preflow algorithm provides the
 fastest method for computing a maximum flow. All implementations
 also provide functions to query the minimum cut, which is the dual
@@ -394 +400 @@
 
 This group contains the algorithms for finding minimum cost flows and
-circulations. For more information about this problem and its dual
-solution see \ref min_cost_flow "Minimum Cost Flow Problem".
+circulations \ref amo93networkflows. For more information about this
+problem and its dual solution, see \ref min_cost_flow
+"Minimum Cost Flow Problem".
 
 LEMON contains several algorithms for this problem.
  - \ref NetworkSimplex Primal Network Simplex algorithm with various
-   pivot strategies.
+   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
-   cost scaling.
+   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
+   \ref bunnagel98efficient.
  - \ref CapacityScaling Successive Shortest %Path algorithm with optional
-   capacity scaling.
- - \ref CancelAndTighten The Cancel and Tighten algorithm.
- - \ref CycleCanceling Cycle-Canceling algorithms.
+   capacity scaling \ref edmondskarp72theoretical.
+ - \ref CancelAndTighten The Cancel and Tighten algorithm
+   \ref goldberg89cyclecanceling.
+ - \ref CycleCanceling Cycle-Canceling algorithms
+   \ref klein67primal, \ref goldberg89cyclecanceling.
 
 In general NetworkSimplex is the most efficient implementation,
@@ -441 +451 @@
 If you want to find minimum cut just between two distinict nodes,
 see the \ref max_flow "maximum flow problem".
+*/
+
+/**
+@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
+@ingroup algs
+\brief Algorithms for finding minimum mean cycles.
+
+This group contains the algorithms for finding minimum mean cycles
+\ref clrs01algorithms, \ref amo93networkflows.
+
+The \e minimum \e mean \e cycle \e problem is to find a directed cycle
+of minimum mean length (cost) in a digraph.
+The mean length of a cycle is the average length of its arcs, i.e. the
+ratio between the total length of the cycle and the number of arcs on it.
+
+This problem has an important connection to \e conservative \e length
+\e functions, too. A length function on the arcs of a digraph is called
+conservative if and only if there is no directed cycle of negative total
+length. For an arbitrary length function, the negative of the minimum
+cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
+arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
+function.
+
+LEMON contains three algorithms for solving the minimum mean cycle problem:
+- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
+  \ref dasdan98minmeancycle.
+- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
+  version of Karp's algorithm \ref dasdan98minmeancycle.
+- \ref Howard "Howard"'s policy iteration algorithm
+  \ref dasdan98minmeancycle.
+
+In practice, the Howard algorithm proved to be by far the most efficient
+one, though the best known theoretical bound on its running time is
+exponential.
+Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
+O(n<sup>2</sup>+e), but the latter one is typically faster due to the
+applied early termination scheme.
 */
 
@@ -535 +582 @@
 
 /**
-@defgroup lp_group Lp and Mip Solvers
+@defgroup lp_group LP and MIP Solvers
 @ingroup gen_opt_group
-\brief Lp and Mip solver interfaces for LEMON.
-
-This group contains Lp and Mip solver interfaces for LEMON. The
-various LP solvers could be used in the same manner with this
-interface.
+\brief LP and MIP solver interfaces for LEMON.
+
+This group contains LP and MIP solver interfaces for LEMON.
+Various LP solvers could be used in the same manner with this
+high-level interface.
+
+The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
+\ref cplex, \ref soplex.
 */
 

doc/mainpage.dox

@@ -22 +22 @@
 \section intro Introduction
 
-\subsection whatis What is LEMON
-
-LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
-and <b>O</b>ptimization in <b>N</b>etworks.
-It is a C++ template
-library aimed at combinatorial optimization tasks which
-often involve in working
-with graphs.
+<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
+and <b>O</b>ptimization in <b>N</b>etworks</i>.
+It is a C++ template library providing efficient implementation of common
+data structures and algorithms with focus on combinatorial optimization
+problems in graphs and networks.
 
 <b>
@@ -39 +36 @@
 </b>
 
-\subsection howtoread How to read the documentation
+The project is maintained by the 
+<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
+Combinatorial Optimization</a> \ref egres
+at the Operations Research Department of the
+<a href="http://www.elte.hu/">E&ouml;tv&ouml;s Lor&aacute;nd University,
+Budapest</a>, Hungary.
+LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
+initiative \ref coinor.
+
+\section howtoread How to Read the Documentation
 
 If you would like to get to know the library, see

doc/min_cost_flow.dox

@@ -27 +27 @@
 minimum total cost from a set of supply nodes to a set of demand nodes
 in a network with capacity constraints (lower and upper bounds)
-and arc costs.
+and arc costs \ref amo93networkflows.
 
 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,

doc/references.bib

@@ -13 +13 @@
   title =        {{EGRES} -- {E}gerv{\'a}ry {R}esearch {G}roup on
                   {C}ombinatorial {O}ptimization},
-  howpublished = {\url{http://www.cs.elte.hu/egres/}},
-  year =         2009
+  url =          {http://www.cs.elte.hu/egres/}
 }
 
@@ -21 +20 @@
   title =        {{COIN-OR} -- {C}omputational {I}nfrastructure for
                   {O}perations {R}esearch},
-  howpublished = {\url{http://www.coin-or.org/}},
-  year =         2009
+  url =          {http://www.coin-or.org/}
 }
 
@@ -31 +29 @@
   key =          {Boost},
   title =        {{B}oost {C++} {L}ibraries},
-  howpublished = {\url{http://www.boost.org/}},
-  year =         2009
+  url =          {http://www.boost.org/}
 }
 
@@ -48 +45 @@
   title =        {{LEDA} -- {L}ibrary of {E}fficient {D}ata {T}ypes and
                   {A}lgorithms},
-  howpublished = {\url{http://www.algorithmic-solutions.com/}},
-  year =         2009
+  url =          {http://www.algorithmic-solutions.com/}
 }
 
@@ -68 +64 @@
   key =          {CMake},
   title =        {{CMake} -- {C}ross {P}latform {M}ake},
-  howpublished = {\url{http://www.cmake.org/}},
-  year =         2009
+  url =          {http://www.cmake.org/}
 }
 
@@ -76 +71 @@
   title =        {{Doxygen} -- {S}ource code documentation generator
                   tool},
-  howpublished = {\url{http://www.doxygen.org/}},
-  year =         2009
+  url =          {http://www.doxygen.org/}
 }
 
@@ -86 +80 @@
   key =          {GLPK},
   title =        {{GLPK} -- {GNU} {L}inear {P}rogramming {K}it},
-  howpublished = {\url{http://www.gnu.org/software/glpk/}},
-  year =         2009
+  url =          {http://www.gnu.org/software/glpk/}
 }
 
@@ -93 +86 @@
   key =          {Clp},
   title =        {{Clp} -- {Coin-Or} {L}inear {P}rogramming},
-  howpublished = {\url{http://projects.coin-or.org/Clp/}},
-  year =         2009
+  url =          {http://projects.coin-or.org/Clp/}
 }
 
@@ -100 +92 @@
   key =          {Cbc},
   title =        {{Cbc} -- {Coin-Or} {B}ranch and {C}ut},
-  howpublished = {\url{http://projects.coin-or.org/Cbc/}},
-  year =         2009
+  url =          {http://projects.coin-or.org/Cbc/}
 }
 
@@ -107 +98 @@
   key =          {CPLEX},
   title =        {{ILOG} {CPLEX}},
-  howpublished = {\url{http://www.ilog.com/}},
-  year =         2009
+  url =          {http://www.ilog.com/}
 }
 
@@ -115 +105 @@
   title =        {{SoPlex} -- {T}he {S}equential {O}bject-{O}riented
                   {S}implex},
-  howpublished = {\url{http://soplex.zib.de/}},
-  year =         2009
+  url =          {http://soplex.zib.de/}
 }
 
@@ -162 +151 @@
 %%%%% Maximum flow algorithms %%%%%
 
-@inproceedings{goldberg86newapproach,
+@article{edmondskarp72theoretical,
+  author =       {Jack Edmonds and Richard M. Karp},
+  title =        {Theoretical improvements in algorithmic efficiency
+                  for network flow problems},
+  journal =      {Journal of the ACM},
+  year =         1972,
+  volume =       19,
+  number =       2,
+  pages =        {248-264}
+}
+
+@article{goldberg88newapproach,
   author =       {Andrew V. Goldberg and Robert E. Tarjan},
   title =        {A new approach to the maximum flow problem},
-  booktitle =    {STOC '86: Proceedings of the Eighteenth Annual ACM
-                  Symposium on Theory of Computing},
-  year =         1986,
-  publisher =    {ACM Press},
-  address =      {New York, NY},
-  pages =        {136-146}
+  journal =      {Journal of the ACM},
+  year =         1988,
+  volume =       35,
+  number =       4,
+  pages =        {921-940}
 }
 
@@ -241 +240 @@
 }
 
-@inproceedings{goldberg88cyclecanceling,
+@article{goldberg89cyclecanceling,
   author =       {Andrew V. Goldberg and Robert E. Tarjan},
   title =        {Finding minimum-cost circulations by canceling
                   negative cycles},
-  booktitle =    {STOC '88: Proceedings of the Twentieth Annual ACM
-                  Symposium on Theory of Computing},
-  year =         1988,
-  publisher =    {ACM Press},
-  address =      {New York, NY},
-  pages =        {388-397}
-}
-
-@article{edmondskarp72theoretical,
-  author =       {Jack Edmonds and Richard M. Karp},
-  title =        {Theoretical improvements in algorithmic efficiency
-                  for network flow problems},
   journal =      {Journal of the ACM},
-  year =         1972,
-  volume =       19,
-  number =       2,
-  pages =        {248-264}
-}
-
-@inproceedings{goldberg87approximation,
-  author =       {Andrew V. Goldberg and Robert E. Tarjan},
-  title =        {Solving minimum-cost flow problems by successive
-                  approximation},
-  booktitle =    {STOC '87: Proceedings of the Nineteenth Annual ACM
-                  Symposium on Theory of Computing},
-  year =         1987,
-  publisher =    {ACM Press},
-  address =      {New York, NY},
-  pages =        {7-18}
-}
-
-@article{goldberg90finding,
+  year =         1989,
+  volume =       36,
+  number =       4,
+  pages =        {873-886}
+}
+
+@article{goldberg90approximation,
   author =       {Andrew V. Goldberg and Robert E. Tarjan},
   title =        {Finding Minimum-Cost Circulations by Successive
@@ -309 +284 @@
 }
 
+@book{dantzig63linearprog,
+  author =       {George B. Dantzig},
+  title =        {Linear Programming and Extensions},
+  publisher =    {Princeton University Press},
+  year =         1963
+}
+
 @mastersthesis{kellyoneill91netsimplex,
   author =       {Damian J. Kelly and Garrett M. O'Neill},
@@ -318 +300 @@
   month =        sep,
 }
-
-@techreport{lobel96networksimplex,
-  author =       {Andreas L{\"o}bel},
-  title =        {Solving large-scale real-world minimum-cost flow
-                  problems by a network simplex method},
-  institution =  {Konrad-Zuse-Zentrum fur Informationstechnik Berlin
-                  ({ZIB})},
-  address =      {Berlin, Germany},
-  year =         1996,
-  number =       {SC 96-7}
-}
-
-@article{frangioni06computational,
-  author =       {Antonio Frangioni and Antonio Manca},
-  title =        {A Computational Study of Cost Reoptimization for
-                  Min-Cost Flow Problems},
-  journal =      {INFORMS Journal On Computing},
-  year =         2006,
-  volume =       18,
-  number =       1,
-  pages =        {61-70}
-}

lemon/Makefile.am

@@ -87 +87 @@
         lemon/graph_to_eps.h \
         lemon/grid_graph.h \
+        lemon/hartmann_orlin.h \
+        lemon/howard.h \
         lemon/hypercube_graph.h \
+        lemon/karp.h \
         lemon/kary_heap.h \
         lemon/kruskal.h \
@@ -111 +114 @@
         lemon/smart_graph.h \
         lemon/soplex.h \
+        lemon/static_graph.h \
         lemon/suurballe.h \
         lemon/time_measure.h \

lemon/adaptors.h

@@ -361 +361 @@
   /// parameter is set to be \c const.
   ///
+  /// This class provides item counting in the same time as the adapted
+  /// digraph structure.
+  ///
   /// \tparam DGR The type of the adapted digraph.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -719 +722 @@
   /// by adding or removing nodes or arcs, unless the \c GR template
   /// parameter is set to be \c const.
+  ///
+  /// This class provides only linear time counting for nodes and arcs.
   ///
   /// \tparam DGR The type of the adapted digraph.
@@ -1315 +1320 @@
   /// parameter is set to be \c const.
   ///
+  /// This class provides only linear time counting for nodes, edges and arcs.
+  ///
   /// \tparam GR The type of the adapted graph.
   /// It must conform to the \ref concepts::Graph "Graph" concept.
@@ -1471 +1478 @@
   /// by adding or removing nodes or arcs/edges, unless the \c GR template
   /// parameter is set to be \c const.
+  ///
+  /// This class provides only linear time item counting.
   ///
   /// \tparam GR The type of the adapted digraph or graph.
@@ -1620 +1629 @@
   /// parameter is set to be \c const.
   ///
+  /// This class provides only linear time counting for nodes and arcs.
+  ///
   /// \tparam DGR The type of the adapted digraph.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -1729 +1740 @@
   /// by adding or removing nodes or edges, unless the \c GR template
   /// parameter is set to be \c const.
+  ///
+  /// This class provides only linear time counting for nodes, edges and arcs.
   ///
   /// \tparam GR The type of the adapted graph.
@@ -2233 +2246 @@
   /// parameter is set to be \c const.
   ///
+  /// This class provides item counting in the same time as the adapted
+  /// digraph structure.
+  ///
   /// \tparam DGR The type of the adapted digraph.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -2535 +2551 @@
   /// by adding or removing nodes or arcs, unless the \c GR template
   /// parameter is set to be \c const.
+  ///
+  /// This class provides item counting in the same time as the adapted
+  /// graph structure.
   ///
   /// \tparam GR The type of the adapted graph.
@@ -2678 +2697 @@
   /// arcs).
   /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
+  ///
+  /// This class provides only linear time counting for nodes and arcs.
   ///
   /// \tparam DGR The type of the adapted digraph.
@@ -3326 +3347 @@
   /// in the adaptor.
   ///
+  /// This class provides item counting in the same time as the adapted
+  /// digraph structure.
+  ///
   /// \tparam DGR The type of the adapted digraph.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.

lemon/bellman_ford.h

@@ -24 +24 @@
 /// \brief Bellman-Ford algorithm.
 
+#include <lemon/list_graph.h>
 #include <lemon/bits/path_dump.h>
 #include <lemon/core.h>
@@ -776 +777 @@
     /// length if the algorithm has already found one.
     /// Otherwise it gives back an empty path.
-    lemon::Path<Digraph> negativeCycle() {
+    lemon::Path<Digraph> negativeCycle() const {
       typename Digraph::template NodeMap<int> state(*_gr, -1);
       lemon::Path<Digraph> cycle;

lemon/bfs.h

@@ -702 +702 @@
     ///Runs the algorithm to visit all nodes in the digraph.
 
-    ///This method runs the %BFS algorithm in order to
-    ///compute the shortest path to each node.
-    ///
-    ///The algorithm computes
-    ///- the shortest path tree (forest),
-    ///- the distance of each node from the root(s).
+    ///This method runs the %BFS algorithm in order to visit all nodes
+    ///in the digraph.
     ///
     ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
@@ -1047 +1043 @@
     ///Runs BFS algorithm to visit all nodes in the digraph.
 
-    ///This method runs BFS algorithm in order to compute
-    ///the shortest path to each node.
+    ///This method runs BFS algorithm in order to visit all nodes
+    ///in the digraph.
     void run()
     {
@@ -1696 +1692 @@
     /// \brief Runs the algorithm to visit all nodes in the digraph.
     ///
-    /// This method runs the %BFS algorithm in order to
-    /// compute the shortest path to each node.
-    ///
-    /// The algorithm computes
-    /// - the shortest path tree (forest),
-    /// - the distance of each node from the root(s).
+    /// This method runs the %BFS algorithm in order to visit all nodes
+    /// in the digraph.
     ///
     /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.

lemon/bits/graph_extender.h

@@ -57 +57 @@
     }
 
-    Node fromId(int id, Node) const {
+    static Node fromId(int id, Node) {
       return Parent::nodeFromId(id);
     }
 
-    Arc fromId(int id, Arc) const {
+    static Arc fromId(int id, Arc) {
       return Parent::arcFromId(id);
     }
@@ -356 +356 @@
     }
 
-    Node fromId(int id, Node) const {
+    static Node fromId(int id, Node) {
       return Parent::nodeFromId(id);
     }
 
-    Arc fromId(int id, Arc) const {
+    static Arc fromId(int id, Arc) {
       return Parent::arcFromId(id);
     }
 
-    Edge fromId(int id, Edge) const {
+    static Edge fromId(int id, Edge) {
       return Parent::edgeFromId(id);
     }

lemon/dfs.h

@@ -634 +634 @@
     ///Runs the algorithm to visit all nodes in the digraph.
 
-    ///This method runs the %DFS algorithm in order to compute the
-    ///%DFS path to each node.
-    ///
-    ///The algorithm computes
-    ///- the %DFS tree (forest),
-    ///- the distance of each node from the root(s) in the %DFS tree.
+    ///This method runs the %DFS algorithm in order to visit all nodes
+    ///in the digraph.
     ///
     ///\note <tt>d.run()</tt> is just a shortcut of the following code.
@@ -977 +973 @@
     ///Runs DFS algorithm to visit all nodes in the digraph.
 
-    ///This method runs DFS algorithm in order to compute
-    ///the DFS path to each node.
+    ///This method runs DFS algorithm in order to visit all nodes
+    ///in the digraph.
     void run()
     {
@@ -1579 +1575 @@
     /// \brief Runs the algorithm to visit all nodes in the digraph.
 
-    /// This method runs the %DFS algorithm in order to
-    /// compute the %DFS path to each node.
-    ///
-    /// The algorithm computes
-    /// - the %DFS tree (forest),
-    /// - the distance of each node from the root(s) in the %DFS tree.
+    /// This method runs the %DFS algorithm in order to visit all nodes
+    /// in the digraph.
     ///
     /// \note <tt>d.run()</tt> is just a shortcut of the following code.

lemon/dijkstra.h

@@ -207 +207 @@
 
     ///The type of the arc lengths.
-    typedef typename TR::LengthMap::Value Value;
+    typedef typename TR::Value Value;
     ///The type of the map that stores the arc lengths.
     typedef typename TR::LengthMap LengthMap;

lemon/edge_set.h

@@ -256 +256 @@
   /// all arcs incident to the given node is erased from the arc set.
   ///
+  /// This class fully conforms to the \ref concepts::Digraph
+  /// "Digraph" concept.
+  /// It provides only linear time counting for nodes and arcs.
+  ///
   /// \param GR The type of the graph which shares its node set with
   /// this class. Its interface must conform to the
   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   /// concept.
-  ///
-  /// This class fully conforms to the \ref concepts::Digraph
-  /// "Digraph" concept.
   template <typename GR>
   class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
@@ -686 +687 @@
   /// incident to the given node is erased from the arc set.
   ///
+  /// This class fully conforms to the \ref concepts::Graph "Graph"
+  /// concept.
+  /// It provides only linear time counting for nodes, edges and arcs.
+  ///
   /// \param GR The type of the graph which shares its node set
   /// with this class. Its interface must conform to the
   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
-  /// concept.
-  ///
-  /// This class fully conforms to the \ref concepts::Graph "Graph"
   /// concept.
   template <typename GR>
@@ -868 +870 @@
     }
 
-    void next(Arc& arc) const {
+    static void next(Arc& arc) {
       --arc.id;
     }
@@ -955 +957 @@
   /// arcs. Therefore the arcs cannot be erased from the arc sets.
   ///
+  /// This class fully conforms to the \ref concepts::Digraph "Digraph"
+  /// concept.
+  /// It provides only linear time counting for nodes and arcs.
+  ///
   /// \warning If a node is erased from the underlying graph and this
   /// node is the source or target of one arc in the arc set, then
   /// the arc set is invalidated, and it cannot be used anymore. The
   /// validity can be checked with the \c valid() member function.
-  ///
-  /// This class fully conforms to the \ref concepts::Digraph
-  /// "Digraph" concept.
   template <typename GR>
   class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
@@ -1174 +1177 @@
     }
 
-    void next(Arc& arc) const {
+    static void next(Arc& arc) {
       --arc.id;
     }
@@ -1182 +1185 @@
     }
 
-    void next(Edge& arc) const {
+    static void next(Edge& arc) {
       --arc.id;
     }
@@ -1305 +1308 @@
   /// edges cannot be erased from the edge sets.
   ///
+  /// This class fully conforms to the \ref concepts::Graph "Graph"
+  /// concept.
+  /// It provides only linear time counting for nodes, edges and arcs.
+  ///
   /// \warning If a node is erased from the underlying graph and this
   /// node is incident to one edge in the edge set, then the edge set
   /// is invalidated, and it cannot be used anymore. The validity can
   /// be checked with the \c valid() member function.
-  ///
-  /// This class fully conforms to the \ref concepts::Graph
-  /// "Graph" concept.
   template <typename GR>
   class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {

lemon/full_graph.h

@@ -52 +52 @@
 
     Node operator()(int ix) const { return Node(ix); }
-    int index(const Node& node) const { return node._id; }
+    static int index(const Node& node) { return node._id; }
 
     Arc arc(const Node& s, const Node& t) const {
@@ -163 +163 @@
   /// only in the concept class.
   ///
+  /// This class provides constant time counting for nodes and arcs.
+  ///
   /// \note FullDigraph and FullGraph classes are very similar,
   /// but there are two differences. While this class conforms only
@@ -205 +207 @@
     /// completely static, the nodes can be indexed with integers from
     /// the range <tt>[0..nodeNum()-1]</tt>.
+    /// The index of a node is the same as its ID.
     /// \sa index()
     Node operator()(int ix) const { return Parent::operator()(ix); }
@@ -213 +216 @@
     /// completely static, the nodes can be indexed with integers from
     /// the range <tt>[0..nodeNum()-1]</tt>.
+    /// The index of a node is the same as its ID.
     /// \sa operator()()
-    int index(Node node) const { return Parent::index(node); }
+    static int index(const Node& node) { return Parent::index(node); }
 
     /// \brief Returns the arc connecting the given nodes.
@@ -288 +292 @@
 
     Node operator()(int ix) const { return Node(ix); }
-    int index(const Node& node) const { return node._id; }
+    static int index(const Node& node) { return node._id; }
 
     Edge edge(const Node& u, const Node& v) const {
@@ -536 +540 @@
   /// only in the concept class.
   ///
+  /// This class provides constant time counting for nodes, edges and arcs.
+  ///
   /// \note FullDigraph and FullGraph classes are very similar,
   /// but there are two differences. While FullDigraph
@@ -580 +586 @@
     /// completely static, the nodes can be indexed with integers from
     /// the range <tt>[0..nodeNum()-1]</tt>.
+    /// The index of a node is the same as its ID.
     /// \sa index()
     Node operator()(int ix) const { return Parent::operator()(ix); }
@@ -588 +595 @@
     /// completely static, the nodes can be indexed with integers from
     /// the range <tt>[0..nodeNum()-1]</tt>.
+    /// The index of a node is the same as its ID.
     /// \sa operator()()
-    int index(Node node) const { return Parent::index(node); }
+    static int index(const Node& node) { return Parent::index(node); }
 
     /// \brief Returns the arc connecting the given nodes.

lemon/grid_graph.h

@@ -504 +504 @@
   /// Most of its member functions and nested classes are documented
   /// only in the concept class.
+  ///
+  /// This class provides constant time counting for nodes, edges and arcs.
   class GridGraph : public ExtendedGridGraphBase {
     typedef ExtendedGridGraphBase Parent;

lemon/hypercube_graph.h

@@ -263 +263 @@
     }
 
-    int index(Node node) const {
+    static int index(Node node) {
       return node._id;
     }
@@ -295 +295 @@
   /// only in the concept class.
   ///
+  /// This class provides constant time counting for nodes, edges and arcs.
+  ///
   /// \note The type of the indices is chosen to \c int for efficiency
   /// reasons. Thus the maximum dimension of this implementation is 26
@@ -357 +359 @@
     /// Gives back the index of the given node.
     /// The lower bits of the integer describes the node.
-    int index(Node node) const {
+    static int index(Node node) {
       return Parent::index(node);
     }

lemon/list_graph.h

@@ -325 +325 @@
   ///only in the concept class.
   ///
+  ///This class provides only linear time counting for nodes and arcs.
+  ///
   ///\sa concepts::Digraph
   ///\sa ListGraph
@@ -361 +363 @@
     ///\brief Erase a node from the digraph.
     ///
-    ///This function erases the given node from the digraph.
+    ///This function erases the given node along with its outgoing and
+    ///incoming arcs from the digraph.
+    ///
+    ///\note All iterators referencing the removed node or the connected
+    ///arcs are invalidated, of course.
     void erase(Node n) { Parent::erase(n); }
 
@@ -367 +373 @@
     ///
     ///This function erases the given arc from the digraph.
+    ///
+    ///\note All iterators referencing the removed arc are invalidated,
+    ///of course.
     void erase(Arc a) { Parent::erase(a); }
 
@@ -511 +520 @@
     ///This function erases all nodes and arcs from the digraph.
     ///
+    ///\note All iterators of the digraph are invalidated, of course.
     void clear() {
       Parent::clear();
@@ -1180 +1190 @@
   ///only in the concept class.
   ///
+  ///This class provides only linear time counting for nodes, edges and arcs.
+  ///
   ///\sa concepts::Graph
   ///\sa ListDigraph
@@ -1218 +1230 @@
     ///\brief Erase a node from the graph.
     ///
-    /// This function erases the given node from the graph.
+    /// This function erases the given node along with its incident arcs
+    /// from the graph.
+    ///
+    /// \note All iterators referencing the removed node or the incident
+    /// edges are invalidated, of course.
     void erase(Node n) { Parent::erase(n); }
 
@@ -1224 +1240 @@
     ///
     /// This function erases the given edge from the graph.
+    ///
+    /// \note All iterators referencing the removed edge are invalidated,
+    /// of course.
     void erase(Edge e) { Parent::erase(e); }
     /// Node validity check
@@ -1313 +1332 @@
     ///This function erases all nodes and arcs from the graph.
     ///
+    ///\note All iterators of the graph are invalidated, of course.
     void clear() {
       Parent::clear();

lemon/network_simplex.h

@@ -41 +41 @@
   ///
   /// \ref NetworkSimplex implements the primal Network Simplex algorithm
-  /// for finding a \ref min_cost_flow "minimum cost flow".
+  /// for finding a \ref min_cost_flow "minimum cost flow"
+  /// \ref amo93networkflows, \ref dantzig63linearprog,
+  /// \ref kellyoneill91netsimplex.
   /// This algorithm is a specialized version of the linear programming
   /// simplex method directly for the minimum cost flow problem.

lemon/path.h

@@ -71 +71 @@
     template <typename CPath>
     Path(const CPath& cpath) {
-      copyPath(*this, cpath);
+      pathCopy(cpath, *this);
     }
 
@@ -79 +79 @@
     template <typename CPath>
     Path& operator=(const CPath& cpath) {
-      copyPath(*this, cpath);
+      pathCopy(cpath, *this);
       return *this;
     }
@@ -259 +259 @@
     template <typename CPath>
     SimplePath(const CPath& cpath) {
-      copyPath(*this, cpath);
+      pathCopy(cpath, *this);
     }
 
@@ -268 +268 @@
     template <typename CPath>
     SimplePath& operator=(const CPath& cpath) {
-      copyPath(*this, cpath);
+      pathCopy(cpath, *this);
       return *this;
     }
@@ -438 +438 @@
     template <typename CPath>
     ListPath(const CPath& cpath) : first(0), last(0) {
-      copyPath(*this, cpath);
+      pathCopy(cpath, *this);
     }
 
@@ -454 +454 @@
     template <typename CPath>
     ListPath& operator=(const CPath& cpath) {
-      copyPath(*this, cpath);
+      pathCopy(cpath, *this);
       return *this;
     }
@@ -764 +764 @@
     template <typename CPath>
     StaticPath(const CPath& cpath) : arcs(0) {
-      copyPath(*this, cpath);
+      pathCopy(cpath, *this);
     }
 
@@ -780 +780 @@
     template <typename CPath>
     StaticPath& operator=(const CPath& cpath) {
-      copyPath(*this, cpath);
+      pathCopy(cpath, *this);
       return *this;
     }
@@ -929 +929 @@
     };
 
-    template <typename Target, typename Source,
-              bool buildEnable = BuildTagIndicator<Target>::value>
+    template <typename From, typename To,
+              bool buildEnable = BuildTagIndicator<To>::value>
     struct PathCopySelectorForward {
-      static void copy(Target& target, const Source& source) {
-        target.clear();
-        for (typename Source::ArcIt it(source); it != INVALID; ++it) {
-          target.addBack(it);
+      static void copy(const From& from, To& to) {
+        to.clear();
+        for (typename From::ArcIt it(from); it != INVALID; ++it) {
+          to.addBack(it);
         }
       }
     };
 
-    template <typename Target, typename Source>
-    struct PathCopySelectorForward<Target, Source, true> {
-      static void copy(Target& target, const Source& source) {
-        target.clear();
-        target.build(source);
-      }
-    };
-
-    template <typename Target, typename Source,
-              bool buildEnable = BuildTagIndicator<Target>::value>
+    template <typename From, typename To>
+    struct PathCopySelectorForward<From, To, true> {
+      static void copy(const From& from, To& to) {
+        to.clear();
+        to.build(from);
+      }
+    };
+
+    template <typename From, typename To,
+              bool buildEnable = BuildTagIndicator<To>::value>
     struct PathCopySelectorBackward {
-      static void copy(Target& target, const Source& source) {
-        target.clear();
-        for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
-          target.addFront(it);
+      static void copy(const From& from, To& to) {
+        to.clear();
+        for (typename From::RevArcIt it(from); it != INVALID; ++it) {
+          to.addFront(it);
         }
       }
     };
 
-    template <typename Target, typename Source>
-    struct PathCopySelectorBackward<Target, Source, true> {
-      static void copy(Target& target, const Source& source) {
-        target.clear();
-        target.buildRev(source);
+    template <typename From, typename To>
+    struct PathCopySelectorBackward<From, To, true> {
+      static void copy(const From& from, To& to) {
+        to.clear();
+        to.buildRev(from);
       }
     };
 
     
-    template <typename Target, typename Source,
-              bool revEnable = RevPathTagIndicator<Source>::value>
+    template <typename From, typename To,
+              bool revEnable = RevPathTagIndicator<From>::value>
     struct PathCopySelector {
-      static void copy(Target& target, const Source& source) {
-        PathCopySelectorForward<Target, Source>::copy(target, source);
+      static void copy(const From& from, To& to) {
+        PathCopySelectorForward<From, To>::copy(from, to);
       }      
     };
 
-    template <typename Target, typename Source>
-    struct PathCopySelector<Target, Source, true> {
-      static void copy(Target& target, const Source& source) {
-        PathCopySelectorBackward<Target, Source>::copy(target, source);
+    template <typename From, typename To>
+    struct PathCopySelector<From, To, true> {
+      static void copy(const From& from, To& to) {
+        PathCopySelectorBackward<From, To>::copy(from, to);
       }      
     };
@@ -988 +988 @@
   /// \brief Make a copy of a path.
   ///
-  ///  This function makes a copy of a path.
-  template <typename Target, typename Source>
-  void copyPath(Target& target, const Source& source) {
-    checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
-    _path_bits::PathCopySelector<Target, Source>::copy(target, source);
+  /// This function makes a copy of a path.
+  template <typename From, typename To>
+  void pathCopy(const From& from, To& to) {
+    checkConcept<concepts::PathDumper<typename From::Digraph>, From>();
+    _path_bits::PathCopySelector<From, To>::copy(from, to);
+  }
+
+  /// \brief Deprecated version of \ref pathCopy().
+  ///
+  /// Deprecated version of \ref pathCopy() (only for reverse compatibility).
+  template <typename To, typename From>
+  void copyPath(To& to, const From& from) {
+    pathCopy(from, to);
   }
 
@@ -1016 +1024 @@
   /// \brief The source of a path
   ///
-  /// This function returns the source of the given path.
+  /// This function returns the source node of the given path.
+  /// If the path is empty, then it returns \c INVALID.
   template <typename Digraph, typename Path>
   typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
-    return digraph.source(path.front());
+    return path.empty() ? INVALID : digraph.source(path.front());
   }
 
   /// \brief The target of a path
   ///
-  /// This function returns the target of the given path.
+  /// This function returns the target node of the given path.
+  /// If the path is empty, then it returns \c INVALID.
   template <typename Digraph, typename Path>
   typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
-    return digraph.target(path.back());
+    return path.empty() ? INVALID : digraph.target(path.back());
   }
 

lemon/preflow.h

@@ -103 +103 @@
   /// This class provides an implementation of Goldberg-Tarjan's \e preflow
   /// \e push-relabel algorithm producing a \ref max_flow
-  /// "flow of maximum value" in a digraph.
+  /// "flow of maximum value" in a digraph \ref clrs01algorithms,
+  /// \ref amo93networkflows, \ref goldberg88newapproach.
   /// The preflow algorithms are the fastest known maximum
   /// flow algorithms. The current implementation uses a mixture of the

lemon/smart_graph.h

@@ -195 +195 @@
   ///only in the concept class.
   ///
+  ///This class provides constant time counting for nodes and arcs.
+  ///
   ///\sa concepts::Digraph
   ///\sa SmartGraph
@@ -498 +500 @@
     }
 
-    void next(Node& node) const {
+    static void next(Node& node) {
       --node._id;
     }
@@ -506 +508 @@
     }
 
-    void next(Arc& arc) const {
+    static void next(Arc& arc) {
       --arc._id;
     }
@@ -514 +516 @@
     }
 
-    void next(Edge& arc) const {
+    static void next(Edge& arc) {
       --arc._id;
     }
@@ -620 +622 @@
   /// Most of its member functions and nested classes are documented
   /// only in the concept class.
+  ///
+  /// This class provides constant time counting for nodes, edges and arcs.
   ///
   /// \sa concepts::Graph

scripts/bib2dox.py

@@ -71 +71 @@
 author_rex = re.compile('\s+and\s+')
 rembraces_rex = re.compile('[{}]')
-capitalize_rex = re.compile('({\w*})')
+capitalize_rex = re.compile('({[^}]*})')
 
 # used by bibtexkeywords(data)
@@ -364 +364 @@
             if entrycont.has_key('note') and (entrycont['note'] != ''):
                 entry.append(entrycont['note'] + '.')
+            if entrycont.has_key('url') and (entrycont['url'] != ''):
+                entry.append(entrycont['url'] + '.')
 
             # generate keys for sorting and for the output
@@ -411 +413 @@
                 field = string.lower(field)
                 data =  data_rex.sub('\g<2>', line)
+
+            if field == 'url':
+                data = '\\url{' + data.strip() + '}'
             
             if field in ('author', 'editor'):

test/CMakeLists.txt

@@ -33 +33 @@
   min_cost_arborescence_test
   min_cost_flow_test
+  min_mean_cycle_test
   path_test
   preflow_test

test/Makefile.am

@@ -31 +31 @@
         test/min_cost_arborescence_test \
         test/min_cost_flow_test \
+        test/min_mean_cycle_test \
         test/path_test \
         test/preflow_test \
@@ -79 +80 @@
 test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
 test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
+test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
 test_path_test_SOURCES = test/path_test.cc
 test_preflow_test_SOURCES = test/preflow_test.cc

test/adaptors_test.cc

@@ -1372 +1372 @@
 
   GridGraph::EdgeMap<bool> dir_map(graph);
-  dir_map[graph.right(n1)] = graph.u(graph.right(n1)) == n1;
-  dir_map[graph.up(n1)] = graph.u(graph.up(n1)) != n1;
-  dir_map[graph.left(n4)] = graph.u(graph.left(n4)) != n4;
-  dir_map[graph.down(n4)] = graph.u(graph.down(n4)) != n4;
+  dir_map[graph.right(n1)] = graph.u(graph.right(n1)) != n1;
+  dir_map[graph.up(n1)] = graph.u(graph.up(n1)) == n1;
+  dir_map[graph.left(n4)] = graph.u(graph.left(n4)) == n4;
+  dir_map[graph.down(n4)] = graph.u(graph.down(n4)) == n4;
 
   // Apply several adaptors on the grid graph
-  typedef SplitNodes< ReverseDigraph< const Orienter<
-            const GridGraph, GridGraph::EdgeMap<bool> > > >
-    RevSplitGridGraph;
-  typedef ReverseDigraph<const RevSplitGridGraph> SplitGridGraph;
+  typedef SplitNodes<Orienter< const GridGraph, GridGraph::EdgeMap<bool> > >
+    SplitGridGraph;
   typedef Undirector<const SplitGridGraph> USplitGridGraph;
-  typedef Undirector<const USplitGridGraph> UUSplitGridGraph;
-  checkConcept<concepts::Digraph, RevSplitGridGraph>();
   checkConcept<concepts::Digraph, SplitGridGraph>();
   checkConcept<concepts::Graph, USplitGridGraph>();
-  checkConcept<concepts::Graph, UUSplitGridGraph>();
-
-  RevSplitGridGraph rev_adaptor =
-    splitNodes(reverseDigraph(orienter(graph, dir_map)));
-  SplitGridGraph adaptor = reverseDigraph(rev_adaptor);
+
+  SplitGridGraph adaptor = splitNodes(orienter(graph, dir_map));
   USplitGridGraph uadaptor = undirector(adaptor);
-  UUSplitGridGraph uuadaptor = undirector(uadaptor);
 
   // Check adaptor
@@ -1400 +1392 @@
   checkGraphConArcList(adaptor, 8);
 
-  checkGraphOutArcList(adaptor, rev_adaptor.inNode(n1), 1);
-  checkGraphOutArcList(adaptor, rev_adaptor.outNode(n1), 1);
-  checkGraphOutArcList(adaptor, rev_adaptor.inNode(n2), 2);
-  checkGraphOutArcList(adaptor, rev_adaptor.outNode(n2), 1);
-  checkGraphOutArcList(adaptor, rev_adaptor.inNode(n3), 1);
-  checkGraphOutArcList(adaptor, rev_adaptor.outNode(n3), 1);
-  checkGraphOutArcList(adaptor, rev_adaptor.inNode(n4), 0);
-  checkGraphOutArcList(adaptor, rev_adaptor.outNode(n4), 1);
-
-  checkGraphInArcList(adaptor, rev_adaptor.inNode(n1), 1);
-  checkGraphInArcList(adaptor, rev_adaptor.outNode(n1), 1);
-  checkGraphInArcList(adaptor, rev_adaptor.inNode(n2), 1);
-  checkGraphInArcList(adaptor, rev_adaptor.outNode(n2), 0);
-  checkGraphInArcList(adaptor, rev_adaptor.inNode(n3), 1);
-  checkGraphInArcList(adaptor, rev_adaptor.outNode(n3), 1);
-  checkGraphInArcList(adaptor, rev_adaptor.inNode(n4), 1);
-  checkGraphInArcList(adaptor, rev_adaptor.outNode(n4), 2);
+  checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
+  checkGraphOutArcList(adaptor, adaptor.outNode(n1), 1);
+  checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
+  checkGraphOutArcList(adaptor, adaptor.outNode(n2), 0);
+  checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
+  checkGraphOutArcList(adaptor, adaptor.outNode(n3), 1);
+  checkGraphOutArcList(adaptor, adaptor.inNode(n4), 1);
+  checkGraphOutArcList(adaptor, adaptor.outNode(n4), 2);
+
+  checkGraphInArcList(adaptor, adaptor.inNode(n1), 1);
+  checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
+  checkGraphInArcList(adaptor, adaptor.inNode(n2), 2);
+  checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
+  checkGraphInArcList(adaptor, adaptor.inNode(n3), 1);
+  checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
+  checkGraphInArcList(adaptor, adaptor.inNode(n4), 0);
+  checkGraphInArcList(adaptor, adaptor.outNode(n4), 1);
 
   checkNodeIds(adaptor);
@@ -1439 +1431 @@
   checkGraphArcMap(uadaptor);
 
-  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n1), 2);
-  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n1), 2);
-  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n2), 3);
-  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n2), 1);
-  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n3), 2);
-  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n3), 2);
-  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n4), 1);
-  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n4), 3);
-
-  // Check uuadaptor
-  checkGraphNodeList(uuadaptor, 8);
-  checkGraphEdgeList(uuadaptor, 16);
-  checkGraphArcList(uuadaptor, 32);
-  checkGraphConEdgeList(uuadaptor, 16);
-  checkGraphConArcList(uuadaptor, 32);
-
-  checkNodeIds(uuadaptor);
-  checkEdgeIds(uuadaptor);
-  checkArcIds(uuadaptor);
-
-  checkGraphNodeMap(uuadaptor);
-  checkGraphEdgeMap(uuadaptor);
-  checkGraphArcMap(uuadaptor);
+  checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n1), 2);
+  checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n1), 2);
+  checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n2), 3);
+  checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n2), 1);
+  checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n3), 2);
+  checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n3), 2);
+  checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n4), 1);
+  checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n4), 3);
 }
 

test/bellman_ford_test.cc

@@ -97 +97 @@
     p  = const_bf_test.predMap();
     pp = const_bf_test.path(t);
+    pp = const_bf_test.negativeCycle();
     
     for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
@@ -133 +134 @@
     b  = bf_test.reached(t);
     pp = bf_test.path(t);
+    pp = bf_test.negativeCycle();
   }
 }

test/digraph_test.cc

@@ -20 +20 @@
 #include <lemon/list_graph.h>
 #include <lemon/smart_graph.h>
+#include <lemon/static_graph.h>
 #include <lemon/full_graph.h>
 
@@ -329 +330 @@
     checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
   }
+  { // Checking StaticDigraph
+    checkConcept<Digraph, StaticDigraph>();
+    checkConcept<ClearableDigraphComponent<>, StaticDigraph>();
+  }
   { // Checking FullDigraph
     checkConcept<Digraph, FullDigraph>();
@@ -382 +387 @@
   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
+}
+
+void checkStaticDigraph() {
+  SmartDigraph g;
+  SmartDigraph::NodeMap<StaticDigraph::Node> nref(g);
+  SmartDigraph::ArcMap<StaticDigraph::Arc> aref(g);
+  
+  StaticDigraph G;
+  
+  checkGraphNodeList(G, 0);
+  checkGraphArcList(G, 0);
+
+  G.build(g, nref, aref);
+
+  checkGraphNodeList(G, 0);
+  checkGraphArcList(G, 0);
+
+  SmartDigraph::Node
+    n1 = g.addNode(),
+    n2 = g.addNode(),
+    n3 = g.addNode();
+
+  G.build(g, nref, aref);
+
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 0);
+
+  SmartDigraph::Arc a1 = g.addArc(n1, n2);
+
+  G.build(g, nref, aref);
+
+  check(G.source(aref[a1]) == nref[n1] && G.target(aref[a1]) == nref[n2],
+        "Wrong arc or wrong references");
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 1);
+
+  checkGraphOutArcList(G, nref[n1], 1);
+  checkGraphOutArcList(G, nref[n2], 0);
+  checkGraphOutArcList(G, nref[n3], 0);
+
+  checkGraphInArcList(G, nref[n1], 0);
+  checkGraphInArcList(G, nref[n2], 1);
+  checkGraphInArcList(G, nref[n3], 0);
+
+  checkGraphConArcList(G, 1);
+
+  SmartDigraph::Arc
+    a2 = g.addArc(n2, n1),
+    a3 = g.addArc(n2, n3),
+    a4 = g.addArc(n2, n3);
+
+  digraphCopy(g, G).nodeRef(nref).run();
+
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 4);
+
+  checkGraphOutArcList(G, nref[n1], 1);
+  checkGraphOutArcList(G, nref[n2], 3);
+  checkGraphOutArcList(G, nref[n3], 0);
+
+  checkGraphInArcList(G, nref[n1], 1);
+  checkGraphInArcList(G, nref[n2], 1);
+  checkGraphInArcList(G, nref[n3], 2);
+
+  checkGraphConArcList(G, 4);
+
+  std::vector<std::pair<int,int> > arcs;
+  arcs.push_back(std::make_pair(0,1));
+  arcs.push_back(std::make_pair(0,2));
+  arcs.push_back(std::make_pair(1,3));
+  arcs.push_back(std::make_pair(1,2));
+  arcs.push_back(std::make_pair(3,0));
+  arcs.push_back(std::make_pair(3,3));
+  arcs.push_back(std::make_pair(4,2));
+  arcs.push_back(std::make_pair(4,3));
+  arcs.push_back(std::make_pair(4,1));
+
+  G.build(6, arcs.begin(), arcs.end());
+  
+  checkGraphNodeList(G, 6);
+  checkGraphArcList(G, 9);
+
+  checkGraphOutArcList(G, G.node(0), 2);
+  checkGraphOutArcList(G, G.node(1), 2);
+  checkGraphOutArcList(G, G.node(2), 0);
+  checkGraphOutArcList(G, G.node(3), 2);
+  checkGraphOutArcList(G, G.node(4), 3);
+  checkGraphOutArcList(G, G.node(5), 0);
+
+  checkGraphInArcList(G, G.node(0), 1);
+  checkGraphInArcList(G, G.node(1), 2);
+  checkGraphInArcList(G, G.node(2), 3);
+  checkGraphInArcList(G, G.node(3), 3);
+  checkGraphInArcList(G, G.node(4), 0);
+  checkGraphInArcList(G, G.node(5), 0);
+
+  checkGraphConArcList(G, 9);
+
+  checkNodeIds(G);
+  checkArcIds(G);
+  checkGraphNodeMap(G);
+  checkGraphArcMap(G);
+  
+  int n = G.nodeNum();
+  int m = G.arcNum();
+  check(G.index(G.node(n-1)) == n-1, "Wrong index.");
+  check(G.index(G.arc(m-1)) == m-1, "Wrong index.");
 }
 
@@ -436 +548 @@
     checkDigraphValidity<SmartDigraph>();
   }
+  { // Checking StaticDigraph
+    checkStaticDigraph();
+  }
   { // Checking FullDigraph
     checkFullDigraph(8);

test/test_tools.h

@@ -38 +38 @@
 ///print something like this (and then exits).
 ///\verbatim file_name.cc:123: error: This is obviously false. \endverbatim
-#define check(rc, msg) \
-  if(!(rc)) { \
-    std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
-    abort(); \
-  } else { } \
+#define check(rc, msg)                                                  \
+  {                                                                     \
+    if(!(rc)) {                                                         \
+      std::cerr << __FILE__ ":" << __LINE__ << ": error: "              \
+                << msg << std::endl;                                    \
+      abort();                                                          \
+    } else { }                                                          \
+  }                                                                     \
+    
 
 #endif