LEMON/LEMON-official Changeset - r844:c01a98ce01fd

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r844:c01a98ce01fd

« 712:e652b6
« 843:189760

845:06f816 »

r844:c01a98ce01fd

Tue, 12 May 2009 13:09:55

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge

1 21 2

merge 1.1

2 files changed with 1229 insertions and 1055 deletions:

doc/min_cost_flow.dox

153

test/connectivity_test.cc

297

CMakeLists.txt

NEWS

README

doc/Makefile.am

doc/groups.dox

doc/mainpage.dox

lemon/Makefile.am

lemon/adaptors.h

lemon/concepts/graph.h

lemon/connectivity.h

323

245

lemon/edge_set.h

lemon/euler.h

lemon/glpk.h

lemon/lemon.pc.in

lemon/matching.h

lemon/network_simplex.h

180

105

scripts/unify-sources.sh

test/CMakeLists.txt

test/Makefile.am

test/min_cost_flow_test.cc

105

tools/lgf-gen.cc

lemon/bits/base_extender.h

495

↑ Collapse diff ↑

doc/min_cost_flow.dox

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		namespace lemon {
 		/**
 		\page min_cost_flow Minimum Cost Flow Problem
 		\section mcf_def Definition (GEQ form)
 		The \e minimum \e cost \e flow \e problem is to find a feasible flow of
 		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.
 		Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
 		\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and
 		upper bounds for the flow values on the arcs, for which
 		\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
 		\f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow
 		on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the
 		signed supply values of the nodes.
 		If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
 		supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
 		\f$-sup(u)\f$ demand.
 		A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution
 		of the following optimization problem.
 		\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
 		zero or negative in order to have a feasible solution (since the sum
 		of the expressions on the left-hand side of the inequalities is zero).
 		It means that the total demand must be greater or equal to the total
 		supply and all the supplies have to be carried out from the supply nodes,
 		but there could be demands that are not satisfied.
 		If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
 		constraints have to be satisfied with equality, i.e. all demands
 		have to be satisfied and all supplies have to be used.
 		\section mcf_algs Algorithms
 		LEMON contains several algorithms for solving this problem, for more
 		information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms".
 		A feasible solution for this problem can be found using \ref Circulation.
 		\section mcf_dual Dual Solution
 		The dual solution of the minimum cost flow problem is represented by
 		node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.
 		An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal
 		if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials
 		the following \e complementary \e slackness optimality conditions hold.
 		 - For all \f$uv\in A\f$ arcs:
 		   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
 		   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
 		   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
 		 - For all \f$u\in V\f$ nodes:
 		   - \f$\pi(u)<=0\f$;
 		   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
 		     then \f$\pi(u)=0\f$.
 		Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
 		\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
 		\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
 		All algorithms provide dual solution (node potentials), as well,
 		if an optimal flow is found.
 		\section mcf_eq Equality Form
 		The above \ref mcf_def "definition" is actually more general than the
 		usual formulation of the minimum cost flow problem, in which strict
 		equalities are required in the supply/demand contraints.
 		\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		However if the sum of the supply values is zero, then these two problems
 		are equivalent.
 		The \ref min_cost_flow_algs "algorithms" in LEMON support the general
 		form, so if you need the equality form, you have to ensure this additional
 		contraint manually.
 		\section mcf_leq Opposite Inequalites (LEQ Form)
 		Another possible definition of the minimum cost flow problem is
 		when there are <em>"less or equal"</em> (LEQ) supply/demand constraints,
 		instead of the <em>"greater or equal"</em> (GEQ) constraints.
 		\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		It means that the total demand must be less or equal to the
 		total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
 		positive) and all the demands have to be satisfied, but there
 		could be supplies that are not carried out from the supply
 		nodes.
 		The equality form is also a special case of this form, of course.
 		You could easily transform this case to the \ref mcf_def "GEQ form"
 		of the problem by reversing the direction of the arcs and taking the
 		negative of the supply values (e.g. using \ref ReverseDigraph and
 		\ref NegMap adaptors).
 		However \ref NetworkSimplex algorithm also supports this form directly
 		for the sake of convenience.
 		Note that the optimality conditions for this supply constraint type are
 		slightly differ from the conditions that are discussed for the GEQ form,
 		namely the potentials have to be non-negative instead of non-positive.
 		An \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem
 		is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$
 		node potentials the following conditions hold.
 		 - For all \f$uv\in A\f$ arcs:
 		   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
 		   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
 		   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
 		 - For all \f$u\in V\f$ nodes:
 		   - \f$\pi(u)>=0\f$;
 		   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
 		     then \f$\pi(u)=0\f$.
 		*/
+		}

test/connectivity_test.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#include <lemon/connectivity.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/adaptors.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		int main()
+		{
 		  typedef ListDigraph Digraph;
 		  typedef Undirector<Digraph> Graph;
+		  {
 		    Digraph d;
 		    Digraph::NodeMap<int> order(d);
 		    Graph g(d);
 		    check(stronglyConnected(d), "The empty digraph is strongly connected");
 		    check(countStronglyConnectedComponents(d) == 0,
 		          "The empty digraph has 0 strongly connected component");
 		    check(connected(g), "The empty graph is connected");
 		    check(countConnectedComponents(g) == 0,
 		          "The empty graph has 0 connected component");
 		    check(biNodeConnected(g), "The empty graph is bi-node-connected");
 		    check(countBiNodeConnectedComponents(g) == 0,
 		          "The empty graph has 0 bi-node-connected component");
 		    check(biEdgeConnected(g), "The empty graph is bi-edge-connected");
 		    check(countBiEdgeConnectedComponents(g) == 0,
 		          "The empty graph has 0 bi-edge-connected component");
 		    check(dag(d), "The empty digraph is DAG.");
 		    check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");
 		    check(loopFree(d), "The empty digraph is loop-free.");
 		    check(parallelFree(d), "The empty digraph is parallel-free.");
 		    check(simpleGraph(d), "The empty digraph is simple.");
 		    check(acyclic(g), "The empty graph is acyclic.");
 		    check(tree(g), "The empty graph is tree.");
 		    check(bipartite(g), "The empty graph is bipartite.");
 		    check(loopFree(g), "The empty graph is loop-free.");
 		    check(parallelFree(g), "The empty graph is parallel-free.");
 		    check(simpleGraph(g), "The empty graph is simple.");
+		  }
+		  {
 		    Digraph d;
 		    Digraph::NodeMap<int> order(d);
 		    Graph g(d);
 		    Digraph::Node n = d.addNode();
 		    check(stronglyConnected(d), "This digraph is strongly connected");
 		    check(countStronglyConnectedComponents(d) == 1,
 		          "This digraph has 1 strongly connected component");
 		    check(connected(g), "This graph is connected");
 		    check(countConnectedComponents(g) == 1,
 		          "This graph has 1 connected component");
 		    check(biNodeConnected(g), "This graph is bi-node-connected");
 		    check(countBiNodeConnectedComponents(g) == 0,
 		          "This graph has 0 bi-node-connected component");
 		    check(biEdgeConnected(g), "This graph is bi-edge-connected");
 		    check(countBiEdgeConnectedComponents(g) == 1,
 		          "This graph has 1 bi-edge-connected component");
 		    check(dag(d), "This digraph is DAG.");
 		    check(checkedTopologicalSort(d, order), "This digraph is DAG.");
 		    check(loopFree(d), "This digraph is loop-free.");
 		    check(parallelFree(d), "This digraph is parallel-free.");
 		    check(simpleGraph(d), "This digraph is simple.");
 		    check(acyclic(g), "This graph is acyclic.");
 		    check(tree(g), "This graph is tree.");
 		    check(bipartite(g), "This graph is bipartite.");
 		    check(loopFree(g), "This graph is loop-free.");
 		    check(parallelFree(g), "This graph is parallel-free.");
 		    check(simpleGraph(g), "This graph is simple.");
+		  }
+		  {
 		    Digraph d;
 		    Digraph::NodeMap<int> order(d);
 		    Graph g(d);
 		    Digraph::Node n1 = d.addNode();
 		    Digraph::Node n2 = d.addNode();
 		    Digraph::Node n3 = d.addNode();
 		    Digraph::Node n4 = d.addNode();
 		    Digraph::Node n5 = d.addNode();
 		    Digraph::Node n6 = d.addNode();
 		    d.addArc(n1, n3);
 		    d.addArc(n3, n2);
 		    d.addArc(n2, n1);
 		    d.addArc(n4, n2);
 		    d.addArc(n4, n3);
 		    d.addArc(n5, n6);
 		    d.addArc(n6, n5);
 		    check(!stronglyConnected(d), "This digraph is not strongly connected");
 		    check(countStronglyConnectedComponents(d) == 3,
 		          "This digraph has 3 strongly connected components");
 		    check(!connected(g), "This graph is not connected");
 		    check(countConnectedComponents(g) == 2,
 		          "This graph has 2 connected components");
 		    check(!dag(d), "This digraph is not DAG.");
 		    check(!checkedTopologicalSort(d, order), "This digraph is not DAG.");
 		    check(loopFree(d), "This digraph is loop-free.");
 		    check(parallelFree(d), "This digraph is parallel-free.");
 		    check(simpleGraph(d), "This digraph is simple.");
 		    check(!acyclic(g), "This graph is not acyclic.");
 		    check(!tree(g), "This graph is not tree.");
 		    check(!bipartite(g), "This graph is not bipartite.");
 		    check(loopFree(g), "This graph is loop-free.");
 		    check(!parallelFree(g), "This graph is not parallel-free.");
 		    check(!simpleGraph(g), "This graph is not simple.");
 		    d.addArc(n3, n3);
 		    check(!loopFree(d), "This digraph is not loop-free.");
 		    check(!loopFree(g), "This graph is not loop-free.");
 		    check(!simpleGraph(d), "This digraph is not simple.");
 		    d.addArc(n3, n2);
 		    check(!parallelFree(d), "This digraph is not parallel-free.");
+		  }
+		  {
 		    Digraph d;
 		    Digraph::ArcMap<bool> cutarcs(d, false);
 		    Graph g(d);
 		    Digraph::Node n1 = d.addNode();
 		    Digraph::Node n2 = d.addNode();
 		    Digraph::Node n3 = d.addNode();
 		    Digraph::Node n4 = d.addNode();
 		    Digraph::Node n5 = d.addNode();
 		    Digraph::Node n6 = d.addNode();
 		    Digraph::Node n7 = d.addNode();
 		    Digraph::Node n8 = d.addNode();
 		    d.addArc(n1, n2);
 		    d.addArc(n5, n1);
 		    d.addArc(n2, n8);
 		    d.addArc(n8, n5);
 		    d.addArc(n6, n4);
 		    d.addArc(n4, n6);
 		    d.addArc(n2, n5);
 		    d.addArc(n1, n8);
 		    d.addArc(n6, n7);
 		    d.addArc(n7, n6);
 		    check(!stronglyConnected(d), "This digraph is not strongly connected");
 		    check(countStronglyConnectedComponents(d) == 3,
 		          "This digraph has 3 strongly connected components");
 		    Digraph::NodeMap<int> scomp1(d);
 		    check(stronglyConnectedComponents(d, scomp1) == 3,
 		          "This digraph has 3 strongly connected components");
 		    check(scomp1[n1] != scomp1[n3] && scomp1[n1] != scomp1[n4] &&
 		          scomp1[n3] != scomp1[n4], "Wrong stronglyConnectedComponents()");
 		    check(scomp1[n1] == scomp1[n2] && scomp1[n1] == scomp1[n5] &&
 		          scomp1[n1] == scomp1[n8], "Wrong stronglyConnectedComponents()");
 		    check(scomp1[n4] == scomp1[n6] && scomp1[n4] == scomp1[n7],
 		          "Wrong stronglyConnectedComponents()");
 		    Digraph::ArcMap<bool> scut1(d, false);
 		    check(stronglyConnectedCutArcs(d, scut1) == 0,
 		          "This digraph has 0 strongly connected cut arc.");
 		    for (Digraph::ArcIt a(d); a != INVALID; ++a) {
 		      check(!scut1[a], "Wrong stronglyConnectedCutArcs()");
+		    }
 		    check(!connected(g), "This graph is not connected");
 		    check(countConnectedComponents(g) == 3,
 		          "This graph has 3 connected components");
 		    Graph::NodeMap<int> comp(g);
 		    check(connectedComponents(g, comp) == 3,
 		          "This graph has 3 connected components");
 		    check(comp[n1] != comp[n3] && comp[n1] != comp[n4] &&
 		          comp[n3] != comp[n4], "Wrong connectedComponents()");
 		    check(comp[n1] == comp[n2] && comp[n1] == comp[n5] &&
 		          comp[n1] == comp[n8], "Wrong connectedComponents()");
 		    check(comp[n4] == comp[n6] && comp[n4] == comp[n7],
 		          "Wrong connectedComponents()");
 		    cutarcs[d.addArc(n3, n1)] = true;
 		    cutarcs[d.addArc(n3, n5)] = true;
 		    cutarcs[d.addArc(n3, n8)] = true;
 		    cutarcs[d.addArc(n8, n6)] = true;
 		    cutarcs[d.addArc(n8, n7)] = true;
 		    check(!stronglyConnected(d), "This digraph is not strongly connected");
 		    check(countStronglyConnectedComponents(d) == 3,
 		          "This digraph has 3 strongly connected components");
 		    Digraph::NodeMap<int> scomp2(d);
 		    check(stronglyConnectedComponents(d, scomp2) == 3,
 		          "This digraph has 3 strongly connected components");
 		    check(scomp2[n3] == 0, "Wrong stronglyConnectedComponents()");
 		    check(scomp2[n1] == 1 && scomp2[n2] == 1 && scomp2[n5] == 1 &&
 		          scomp2[n8] == 1, "Wrong stronglyConnectedComponents()");
 		    check(scomp2[n4] == 2 && scomp2[n6] == 2 && scomp2[n7] == 2,
 		          "Wrong stronglyConnectedComponents()");
 		    Digraph::ArcMap<bool> scut2(d, false);
 		    check(stronglyConnectedCutArcs(d, scut2) == 5,
 		          "This digraph has 5 strongly connected cut arcs.");
 		    for (Digraph::ArcIt a(d); a != INVALID; ++a) {
 		      check(scut2[a] == cutarcs[a], "Wrong stronglyConnectedCutArcs()");
+		    }
+		  }
+		  {
 		    // DAG example for topological sort from the book New Algorithms
 		    // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)
 		    Digraph d;
 		    Digraph::NodeMap<int> order(d);
 		    Digraph::Node belt = d.addNode();
 		    Digraph::Node trousers = d.addNode();
 		    Digraph::Node necktie = d.addNode();
 		    Digraph::Node coat = d.addNode();
 		    Digraph::Node socks = d.addNode();
 		    Digraph::Node shirt = d.addNode();
 		    Digraph::Node shoe = d.addNode();
 		    Digraph::Node watch = d.addNode();
 		    Digraph::Node pants = d.addNode();
 		    d.addArc(socks, shoe);
 		    d.addArc(pants, shoe);
 		    d.addArc(pants, trousers);
 		    d.addArc(trousers, shoe);
 		    d.addArc(trousers, belt);
 		    d.addArc(belt, coat);
 		    d.addArc(shirt, belt);
 		    d.addArc(shirt, necktie);
 		    d.addArc(necktie, coat);
 		    check(dag(d), "This digraph is DAG.");
 		    topologicalSort(d, order);
 		    for (Digraph::ArcIt a(d); a != INVALID; ++a) {
 		      check(order[d.source(a)] < order[d.target(a)],
 		            "Wrong topologicalSort()");
+		    }
+		  }
+		  {
 		    ListGraph g;
 		    ListGraph::NodeMap<bool> map(g);
 		    ListGraph::Node n1 = g.addNode();
 		    ListGraph::Node n2 = g.addNode();
 		    ListGraph::Node n3 = g.addNode();
 		    ListGraph::Node n4 = g.addNode();
 		    ListGraph::Node n5 = g.addNode();
 		    ListGraph::Node n6 = g.addNode();
 		    ListGraph::Node n7 = g.addNode();
 		    g.addEdge(n1, n3);
 		    g.addEdge(n1, n4);
 		    g.addEdge(n2, n5);
 		    g.addEdge(n3, n6);
 		    g.addEdge(n4, n6);
 		    g.addEdge(n4, n7);
 		    g.addEdge(n5, n7);
 		    check(bipartite(g), "This graph is bipartite");
 		    check(bipartitePartitions(g, map), "This graph is bipartite");
 		    check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
 		          "Wrong bipartitePartitions()");
 		    check(map[n3] == map[n4] && map[n3] == map[n5],
 		          "Wrong bipartitePartitions()");
+		  }
 		  return 0;
+		}

CMakeLists.txt

Show inline comments

 		CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
 		IF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
 		  INCLUDE(${CMAKE_SOURCE_DIR}/cmake/version.cmake)
 		ELSE(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
 		  SET(PROJECT_NAME "LEMON")
 		  SET(PROJECT_VERSION "hg-tip" CACHE STRING "LEMON version string.")
 		ENDIF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
 		PROJECT(${PROJECT_NAME})
 		SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
 		INCLUDE(FindDoxygen)
 		INCLUDE(FindGhostscript)
 		FIND_PACKAGE(GLPK 4.33)
 		FIND_PACKAGE(CPLEX)
 		FIND_PACKAGE(COIN)
 		IF(MSVC)
 		  SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} /wd4250 /wd4355 /wd4800 /wd4996")
 		# Suppressed warnings:
 		# C4250: 'class1' : inherits 'class2::member' via dominance
 		# C4355: 'this' : used in base member initializer list
 		# C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
 		# C4996: 'function': was declared deprecated
 		ENDIF(MSVC)
 		INCLUDE(CheckTypeSize)
 		CHECK_TYPE_SIZE("long long" LEMON_LONG_LONG)
 		ENABLE_TESTING()
 		ADD_SUBDIRECTORY(lemon)
 		IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
 		  ADD_SUBDIRECTORY(demo)
 		  ADD_SUBDIRECTORY(tools)
 		  ADD_SUBDIRECTORY(doc)
 		  ADD_SUBDIRECTORY(test)
 		ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
 		IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
 		  IF(WIN32)
 		    SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
 		    SET(CPACK_PACKAGE_VENDOR "EGRES")
 		    SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
-		      "LEMON - Library of Efficient Models and Optimization in Networks")
+		      "LEMON - Library for Efficient Modeling and Optimization in Networks")
 		    SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
 		    SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
 		    SET(CPACK_PACKAGE_INSTALL_DIRECTORY
 		      "${PROJECT_NAME} ${PROJECT_VERSION}")
 		    SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
 		      "${PROJECT_NAME} ${PROJECT_VERSION}")
 		    SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
 		    SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
 		    SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
 		    SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
 		    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
 		    SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
 		      "C++ header files")
 		    SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
 		      "DLL and import library")
 		    SET(CPACK_COMPONENT_BIN_DESCRIPTION
 		      "Command line utilities")
 		    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
 		      "Doxygen generated documentation")
 		    SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
 		    SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
 		    SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
 		    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
 		    SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
 		      "Components needed to develop software using LEMON")
 		    SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
 		      "Documentation of LEMON")
 		    SET(CPACK_ALL_INSTALL_TYPES Full Developer)
 		    SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
 		    SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
 		    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
 		    SET(CPACK_GENERATOR "NSIS")
 		    SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
 		    SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
 		    #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
 		    SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
 		    SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")

NEWS

Show inline comments

 -05-13 Version 1.1 released
 		        This is the second stable release of the 1.x series. It
 		        features a better coverage of the tools available in the 0.x
 		        series, a thoroughly reworked LP/MIP interface plus various
 		        improvements in the existing tools.
 		        * Much improved M$ Windows support
 		          * Various improvements in the CMAKE build system
 		          * Compilation warnings are fixed/suppressed
 		        * Support IBM xlC compiler
 		        * New algorithms
 		          * Connectivity related algorithms (#61)
 		          * Euler walks (#65)
 		          * Preflow push-relabel max. flow algorithm (#176)
 		          * Circulation algorithm (push-relabel based) (#175)
 		          * Suurballe algorithm (#47)
 		          * Gomory-Hu algorithm (#66)
 		          * Hao-Orlin algorithm (#58)
 		          * Edmond's maximum cardinality and weighted matching algorithms
 		            in general graphs (#48,#265)
 		          * Minimum cost arborescence/branching (#60)
 		          * Network Simplex min. cost flow algorithm (#234)
 		        * New data structures
 		          * Full graph structure (#57)
 		          * Grid graph structure (#57)
 		          * Hypercube graph structure (#57)
 		          * Graph adaptors (#67)
 		          * ArcSet and EdgeSet classes (#67)
 		          * Elevator class (#174)
 		        * Other new tools
 		          * LP/MIP interface (#44)
 		            * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC
 		          * Reader for the Nauty file format (#55)
 		          * DIMACS readers (#167)
 		          * Radix sort algorithms (#72)
 		          * RangeIdMap and CrossRefMap (#160)
 		        * New command line tools
 		          * DIMACS to LGF converter (#182)
 		          * lgf-gen - a graph generator (#45)
 		          * DIMACS solver utility (#226)
 		        * Other code improvements
 		          * Lognormal distribution added to Random (#102)
 		          * Better (i.e. O(1) time) item counting in SmartGraph (#3)
 		          * The standard maps of graphs are guaranteed to be
 		            reference maps (#190)
 		        * Miscellaneous
 		          * Various doc improvements
 		          * Improved 0.x -> 1.x converter script
 		        * Several bugfixes (compared to release 1.0):
 		          #170: Bugfix SmartDigraph::split()
 		          #171: Bugfix in SmartGraph::restoreSnapshot()
 		          #172: Extended test cases for graphs and digraphs
 		          #173: Bugfix in Random
 		                * operator()s always return a double now
 		                * the faulty real<Num>(Num) and real<Num>(Num,Num)
 		                  have been removed
 		          #187: Remove DijkstraWidestPathOperationTraits
 		          #61:  Bugfix in DfsVisit
 		          #193: Bugfix in GraphReader::skipSection()
 		          #195: Bugfix in ConEdgeIt()
 		          #197: Bugfix in heap unionfind
 		                * This bug affects Edmond's general matching algorithms
 		          #207: Fix 'make install' without 'make html' using CMAKE
 		          #208: Suppress or fix VS2008 compilation warnings
 		          ----: Update the LEMON icon
 		          ----: Enable the component-based installer
 		                (in installers made by CPACK)
 		          ----: Set the proper version for CMAKE in the tarballs
 		                (made by autotools)
 		          ----: Minor clarification in the LICENSE file
 		          ----: Add missing unistd.h include to time_measure.h
 		          #204: Compilation bug fixed in graph_to_eps.h with VS2005
 		          #214,#215: windows.h should never be included by lemon headers
 		          #230: Build systems check the availability of 'long long' type
 		          #229: Default implementation of Tolerance<> is used for integer types
 		          #211,#212: Various fixes for compiling on AIX
 		          ----: Improvements in CMAKE config
 		                - docs is installed in share/doc/
 		                - detects newer versions of Ghostscript
 		          #239: Fix missing 'inline' specifier in time_measure.h
 		          #274,#280: Install lemon/config.h
 		          #275: Prefix macro names with LEMON_ in lemon/config.h
 		          ----: Small script for making the release tarballs added
 		          ----: Minor improvement in unify-sources.sh (a76f55d7d397)
 -03-27 LEMON joins to the COIN-OR initiative
 		        COIN-OR (Computational Infrastructure for Operations Research,
 		        http://www.coin-or.org) project is an initiative to spur the
 		        development of open-source software for the operations research
 		        community.
 -10-13 Version 1.0 released
 			This is the first stable release of LEMON. Compared to the 0.x
 			release series, it features a considerably smaller but more
 			matured set of tools. The API has also completely revised and
 			changed in several places.
 			* The major name changes compared to the 0.x series (see the
 		          Migration Guide in the doc for more details)
 		          * Graph -> Digraph, UGraph -> Graph
 		          * Edge -> Arc, UEdge -> Edge
 			  * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
 			* Other improvements
 			  * Better documentation
 			  * Reviewed and cleaned up codebase
 			  * CMake based build system (along with the autotools based one)
 			* Contents of the library (ported from 0.x)
 			  * Algorithms
 		       	    * breadth-first search (bfs.h)
 		       	    * depth-first search (dfs.h)
 		       	    * Dijkstra's algorithm (dijkstra.h)
 		       	    * Kruskal's algorithm (kruskal.h)
 		    	  * Data structures
 		       	    * graph data structures (list_graph.h, smart_graph.h)
 		       	    * path data structures (path.h)
 		       	    * binary heap data structure (bin_heap.h)
 		       	    * union-find data structures (unionfind.h)
 		       	    * miscellaneous property maps (maps.h)
 		       	    * two dimensional vector and bounding box (dim2.h)
 		          * Concepts
 		       	    * graph structure concepts (concepts/digraph.h, concepts/graph.h,
 		              concepts/graph_components.h)
 		       	    * concepts for other structures (concepts/heap.h, concepts/maps.h,
 			      concepts/path.h)
 		    	  * Tools
 		       	    * Mersenne twister random number generator (random.h)
 		       	    * tools for measuring cpu and wall clock time (time_measure.h)
 		       	    * tools for counting steps and events (counter.h)
 		       	    * tool for parsing command line arguments (arg_parser.h)
 		       	    * tool for visualizing graphs (graph_to_eps.h)
 		       	    * tools for reading and writing data in LEMON Graph Format

README

Show inline comments

 		==================================================================
 		LEMON - a Library of Efficient Models and Optimization in Networks
 		==================================================================
+		=====================================================================
 		LEMON - a Library for Efficient Modeling and Optimization in Networks
 		=====================================================================
 		LEMON is an open source library written in C++. It provides
 		easy-to-use implementations of common data structures and algorithms
 		in the area of optimization and helps implementing new ones. The main
 		focus is on graphs and graph algorithms, thus it is especially
 		suitable for solving design and optimization problems of
 		telecommunication networks. To achieve wide usability its data
 		structures and algorithms provide generic interfaces.
 		Contents
 		========
 		LICENSE
 		   Copying, distribution and modification conditions and terms.
 		INSTALL
 		   General building and installation instructions.
 		lemon/
 		   Source code of LEMON library.
 		doc/
 		   Documentation of LEMON. The starting page is doc/html/index.html.
 		demo/
 		   Some example programs to make you easier to get familiar with LEMON.
 		test/
 		   Programs to check the integrity and correctness of LEMON.
 		tools/
 		   Various utilities related to LEMON.

doc/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			doc/Doxyfile.in \
 			doc/DoxygenLayout.xml \
 			doc/coding_style.dox \
 			doc/dirs.dox \
 			doc/groups.dox \
 			doc/lgf.dox \
 			doc/license.dox \
 			doc/mainpage.dox \
 			doc/migration.dox \
 			doc/min_cost_flow.dox \
 			doc/named-param.dox \
 			doc/namespaces.dox \
 			doc/html \
 			doc/CMakeLists.txt
 		DOC_EPS_IMAGES18 = \
 			grid_graph.eps \
 			nodeshape_0.eps \
 			nodeshape_1.eps \
 			nodeshape_2.eps \
 			nodeshape_3.eps \
 			nodeshape_4.eps
 		DOC_EPS_IMAGES27 = \
 			bipartite_matching.eps \
 			bipartite_partitions.eps \
 			connected_components.eps \
 			edge_biconnected_components.eps \
 			node_biconnected_components.eps \
 			strongly_connected_components.eps
 		DOC_EPS_IMAGES = \
 			$(DOC_EPS_IMAGES18) \
 			$(DOC_EPS_IMAGES27)
 		DOC_PNG_IMAGES = \
 			$(DOC_EPS_IMAGES:%.eps=doc/gen-images/%.png)
 		EXTRA_DIST += $(DOC_EPS_IMAGES:%=doc/images/%)
 		doc/html:
 			$(MAKE) $(AM_MAKEFLAGS) html
 		GS_COMMAND=gs -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4
 		$(DOC_EPS_IMAGES18:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps
 			-mkdir doc/gen-images
 			if test ${gs_found} = yes; then \
 			  $(GS_COMMAND) -sDEVICE=pngalpha -r18 -sOutputFile=$@ $<; \
 			else \
 			  echo; \
 			  echo "Ghostscript not found."; \
 			  echo; \
 			  exit 1; \
 			fi
 		$(DOC_EPS_IMAGES27:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps
 			-mkdir doc/gen-images

doc/groups.dox

Show inline comments

@@ -93,106 +93,96 @@
 		considering a new orientation, then an adaptor is worthwhile to use.
 		To come back to the reverse oriented graph, in this situation
 		\code
 		template<typename Digraph> class ReverseDigraph;
 		\endcode
 		template class can be used. The code looks as follows
 		\code
 		ListDigraph g;
 		ReverseDigraph<ListDigraph> rg(g);
 		int result = algorithm(rg);
 		\endcode
 		During running the algorithm, the original digraph \c g is untouched.
 		This techniques give rise to an elegant code, and based on stable
 		graph adaptors, complex algorithms can be implemented easily.
 		In flow, circulation and matching problems, the residual
 		graph is of particular importance. Combining an adaptor implementing
 		this with shortest path algorithms or minimum mean cycle algorithms,
 		a range of weighted and cardinality optimization algorithms can be
 		obtained. For other examples, the interested user is referred to the
 		detailed documentation of particular adaptors.
 		The behavior of graph adaptors can be very different. Some of them keep
 		capabilities of the original graph while in other cases this would be
 		meaningless. This means that the concepts that they meet depend
 		on the graph adaptor, and the wrapped graph.
 		For example, if an arc of a reversed digraph is deleted, this is carried
 		out by deleting the corresponding arc of the original digraph, thus the
 		adaptor modifies the original digraph.
 		However in case of a residual digraph, this operation has no sense.
 		Let us stand one more example here to simplify your work.
 		ReverseDigraph has constructor
 		\code
 		ReverseDigraph(Digraph& digraph);
 		\endcode
 		This means that in a situation, when a <tt>const %ListDigraph&</tt>
 		reference to a graph is given, then it have to be instantiated with
 		<tt>Digraph=const %ListDigraph</tt>.
 		\code
 		int algorithm1(const ListDigraph& g) {
 		  ReverseDigraph<const ListDigraph> rg(g);
 		  return algorithm2(rg);
+		}
 		\endcode
 		*/
 		/**
 		@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
 		@ingroup graphs
 		\brief Graph types between real graphs and graph adaptors.
 		This group contains some graph types between real graphs and graph adaptors.
 		These classes wrap graphs to give new functionality as the adaptors do it.
 		On the other hand they are not light-weight structures as the adaptors.
 		*/
 		/**
 		@defgroup maps Maps
 		@ingroup datas
 		\brief Map structures implemented in LEMON.
 		This group contains the map structures implemented in LEMON.
 		LEMON provides several special purpose maps and map adaptors that e.g. combine
 		new maps from existing ones.
 		<b>See also:</b> \ref map_concepts "Map Concepts".
 		*/
 		/**
 		@defgroup graph_maps Graph Maps
 		@ingroup maps
 		\brief Special graph-related maps.
 		This group contains maps that are specifically designed to assign
 		values to the nodes and arcs/edges of graphs.
 		If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
 		\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
 		*/
 		/**
 		\defgroup map_adaptors Map Adaptors
 		\ingroup maps
 		\brief Tools to create new maps from existing ones
 		This group contains map adaptors that are used to create "implicit"
 		maps from other maps.
 		Most of them are \ref concepts::ReadMap "read-only maps".
 		They can make arithmetic and logical operations between one or two maps
 		(negation, shifting, addition, multiplication, logical 'and', 'or',
 		'not' etc.) or e.g. convert a map to another one of different Value type.
 		The typical usage of this classes is passing implicit maps to
 		algorithms.  If a function type algorithm is called then the function
 		type map adaptors can be used comfortable. For example let's see the
 		usage of map adaptors with the \c graphToEps() function.
 		\code
 		  Color nodeColor(int deg) {
 		    if (deg >= 2) {
 		      return Color(0.5, 0.0, 0.5);
 		    } else if (deg == 1) {
 		      return Color(1.0, 0.5, 1.0);
 		    } else {
@@ -270,264 +260,193 @@
 		*/
 		/**
 		@defgroup search Graph Search
 		@ingroup algs
 		\brief Common graph search algorithms.
 		This group contains the common graph search algorithms, namely
 		\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
 		*/
 		/**
 		@defgroup shortest_path Shortest Path Algorithms
 		@ingroup algs
 		\brief Algorithms for finding shortest paths.
 		This group contains the algorithms for finding shortest paths in digraphs.
 		 - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
 		   source node when all arc lengths are non-negative.
 		 - \ref Suurballe A successive shortest path algorithm for finding
 		   arc-disjoint paths between two nodes having minimum total length.
 		*/
 		/**
 		@defgroup max_flow Maximum Flow Algorithms
 		@ingroup algs
 		\brief Algorithms for finding maximum flows.
 		This group contains the algorithms for finding maximum flows and
 		feasible circulations.
 		The \e maximum \e flow \e problem is to find a flow of maximum value between
 		a single source and a single target. Formally, there is a \f$G=(V,A)\f$
 		digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
 		\f$s, t \in V\f$ source and target nodes.
 		A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
 		following optimization problem.
 		\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
 		\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
 		    \quad \forall u\in V\setminus\{s,t\} \f]
 		\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
 		\ref Preflow implements the preflow push-relabel algorithm of Goldberg and
 		Tarjan for solving this problem. It also provides functions to query the
 		minimum cut, which is the dual problem of maximum flow.
 		\ref Circulation is a preflow push-relabel algorithm implemented directly
 		for finding feasible circulations, which is a somewhat different problem,
 		but it is strongly related to maximum flow.
 		For more information, see \ref Circulation.
 		*/
 		/**
-		@defgroup min_cost_flow Minimum Cost Flow Algorithms
+		@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cost flows and circulations.
 		This group contains the algorithms for finding minimum cost flows and
 		circulations.
 		The \e minimum \e cost \e flow \e problem is to find a feasible flow of
 		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.
 		Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,
 		\f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and
 		upper bounds for the flow values on the arcs, for which
 		\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
 		\f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow
 		on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
 		signed supply values of the nodes.
 		If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
 		supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
 		\f$-sup(u)\f$ demand.
 		A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution
 		of the following optimization problem.
 		\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
 		zero or negative in order to have a feasible solution (since the sum
 		of the expressions on the left-hand side of the inequalities is zero).
 		It means that the total demand must be greater or equal to the total
 		supply and all the supplies have to be carried out from the supply nodes,
 		but there could be demands that are not satisfied.
 		If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
 		constraints have to be satisfied with equality, i.e. all demands
 		have to be satisfied and all supplies have to be used.
 		If you need the opposite inequalities in the supply/demand constraints
 		(i.e. the total demand is less than the total supply and all the demands
 		have to be satisfied while there could be supplies that are not used),
 		then you could easily transform the problem to the above form by reversing
 		the direction of the arcs and taking the negative of the supply values
 		(e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
 		However \ref NetworkSimplex algorithm also supports this form directly
 		for the sake of convenience.
 		A feasible solution for this problem can be found using \ref Circulation.
 		Note that the above formulation is actually more general than the usual
 		definition of the minimum cost flow problem, in which strict equalities
 		are required in the supply/demand contraints, i.e.
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
 		    sup(u) \quad \forall u\in V. \f]
 		However if the sum of the supply values is zero, then these two problems
 		are equivalent. So if you need the equality form, you have to ensure this
 		additional contraint for the algorithms.
 		The dual solution of the minimum cost flow problem is represented by node
 		potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
 		An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem
 		is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
 		node potentials the following \e complementary \e slackness optimality
 		conditions hold.
 		 - For all \f$uv\in A\f$ arcs:
 		   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
 		   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
 		   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
 		 - For all \f$u\in V\f$ nodes:
 		   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
 		     then \f$\pi(u)=0\f$.
 		Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
 		\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
 		\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
 		circulations. For more information about this problem and its dual
 		solution see \ref min_cost_flow "Minimum Cost Flow Problem".
 		\ref NetworkSimplex is an efficient implementation of the primal Network
 		Simplex algorithm for finding minimum cost flows. It also provides dual
 		solution (node potentials), if an optimal flow is found.
 		*/
 		/**
 		@defgroup min_cut Minimum Cut Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cut in graphs.
 		This group contains the algorithms for finding minimum cut in graphs.
 		The \e minimum \e cut \e problem is to find a non-empty and non-complete
 		\f$X\f$ subset of the nodes with minimum overall capacity on
 		outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
 		\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
 		cut is the \f$X\f$ solution of the next optimization problem:
 		\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
 		    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
 		LEMON contains several algorithms related to minimum cut problems:
 		- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
 		  in directed graphs.
 		- \ref GomoryHu "Gomory-Hu tree computation" for calculating
 		  all-pairs minimum cut in undirected graphs.
 		If you want to find minimum cut just between two distinict nodes,
 		see the \ref max_flow "maximum flow problem".
 		*/
 		/**
 		@defgroup graph_properties Connectivity and Other Graph Properties
 		@ingroup algs
 		\brief Algorithms for discovering the graph properties
 		This group contains the algorithms for discovering the graph properties
 		like connectivity, bipartiteness, euler property, simplicity etc.
 		\image html edge_biconnected_components.png
 		\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
 		*/
 		/**
 		@defgroup matching Matching Algorithms
 		@ingroup algs
 		\brief Algorithms for finding matchings in graphs and bipartite graphs.
 		This group contains the algorithms for calculating matchings in graphs.
 		The general matching problem is finding a subset of the edges for which
 		each node has at most one incident edge.
 		There are several different algorithms for calculate matchings in
 		graphs. The goal of the matching optimization
 		can be finding maximum cardinality, maximum weight or minimum cost
 		matching. The search can be constrained to find perfect or
 		maximum cardinality matching.
 		The matching algorithms implemented in LEMON:
 		- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum cardinality matching in general graphs.
 		- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum weighted matching in general graphs.
 		- \ref MaxWeightedPerfectMatching
 		  Edmond's blossom shrinking algorithm for calculating maximum weighted
 		  perfect matching in general graphs.
 		\image html bipartite_matching.png
 		\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
 		*/
 		/**
 		@defgroup spantree Minimum Spanning Tree Algorithms
 		@ingroup algs
-		\brief Algorithms for finding a minimum cost spanning tree in a graph.
+		\brief Algorithms for finding minimum cost spanning trees and arborescences.
 		This group contains the algorithms for finding a minimum cost spanning
 		tree in a graph.
 		This group contains the algorithms for finding minimum cost spanning
 		trees and arborescences.
 		*/
 		/**
 		@defgroup auxalg Auxiliary Algorithms
 		@ingroup algs
 		\brief Auxiliary algorithms implemented in LEMON.
 		This group contains some algorithms implemented in LEMON
 		in order to make it easier to implement complex algorithms.
 		*/
 		/**
 		@defgroup gen_opt_group General Optimization Tools
 		\brief This group contains some general optimization frameworks
 		implemented in LEMON.
 		This group contains some general optimization frameworks
 		implemented in LEMON.
 		*/
 		/**
 		@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.
 		*/
 		/**
 		@defgroup utils Tools and Utilities
 		\brief Tools and utilities for programming in LEMON
 		Tools and utilities for programming in LEMON.
 		*/
 		/**
 		@defgroup gutils Basic Graph Utilities
 		@ingroup utils
 		\brief Simple basic graph utilities.
 		This group contains some simple basic graph utilities.
 		*/
 		/**
 		@defgroup misc Miscellaneous Tools
 		@ingroup utils

doc/mainpage.dox

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		/**
 		\mainpage LEMON Documentation
 		\section intro Introduction
 		\subsection whatis What is LEMON
 		LEMON stands for
 		<b>L</b>ibrary of <b>E</b>fficient <b>M</b>odels
 		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 is an <a class="el" href="http://opensource.org/">open&nbsp;source</a>
 		project.
 		You are free to use it in your commercial or
 		non-commercial applications under very permissive
 		\ref license "license terms".
 		</b>
 		\subsection howtoread How to read the documentation
 		If you want to get a quick start and see the most important features then
 		take a look at our \ref quicktour
 		"Quick Tour to LEMON" which will guide you along.
-		If you already feel like using our library, see the
+		If you would like to get to know the library, see
 		<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
 		If you know what you are looking for then try to find it under the
+		If you know what you are looking for, then try to find it under the
 		<a class="el" href="modules.html">Modules</a> section.
 		If you are a user of the old (0.x) series of LEMON, please check out the
 		\ref migration "Migration Guide" for the backward incompatibilities.
 		*/

lemon/Makefile.am

Show inline comments

@@ -66,69 +66,68 @@
 			lemon/connectivity.h \
 			lemon/counter.h \
 			lemon/core.h \
 			lemon/cplex.h \
 			lemon/dfs.h \
 			lemon/dijkstra.h \
 			lemon/dim2.h \
 			lemon/dimacs.h \
 			lemon/edge_set.h \
 			lemon/elevator.h \
 			lemon/error.h \
 			lemon/euler.h \
 			lemon/full_graph.h \
 			lemon/glpk.h \
 			lemon/gomory_hu.h \
 			lemon/graph_to_eps.h \
 			lemon/grid_graph.h \
 			lemon/hypercube_graph.h \
 			lemon/kruskal.h \
 			lemon/hao_orlin.h \
 			lemon/lgf_reader.h \
 			lemon/lgf_writer.h \
 			lemon/list_graph.h \
 			lemon/lp.h \
 			lemon/lp_base.h \
 			lemon/lp_skeleton.h \
 			lemon/list_graph.h \
 			lemon/maps.h \
 			lemon/matching.h \
 			lemon/math.h \
 			lemon/min_cost_arborescence.h \
 			lemon/nauty_reader.h \
 			lemon/network_simplex.h \
 			lemon/path.h \
 			lemon/preflow.h \
 			lemon/radix_sort.h \
 			lemon/random.h \
 			lemon/smart_graph.h \
 			lemon/soplex.h \
 			lemon/suurballe.h \
 			lemon/time_measure.h \
 			lemon/tolerance.h \
 			lemon/unionfind.h \
 			lemon/bits/windows.h
 		bits_HEADERS += \
 			lemon/bits/alteration_notifier.h \
 			lemon/bits/array_map.h \
 			lemon/bits/base_extender.h \
 			lemon/bits/bezier.h \
 			lemon/bits/default_map.h \
 			lemon/bits/edge_set_extender.h \
 			lemon/bits/enable_if.h \
 			lemon/bits/graph_adaptor_extender.h \
 			lemon/bits/graph_extender.h \
 			lemon/bits/map_extender.h \
 			lemon/bits/path_dump.h \
 			lemon/bits/solver_bits.h \
 			lemon/bits/traits.h \
 			lemon/bits/variant.h \
 			lemon/bits/vector_map.h
 		concept_HEADERS += \
 			lemon/concepts/digraph.h \
 			lemon/concepts/graph.h \
 			lemon/concepts/graph_components.h \
 			lemon/concepts/heap.h \
 			lemon/concepts/maps.h \
 			lemon/concepts/path.h

lemon/adaptors.h

Show inline comments

@@ -1794,242 +1794,239 @@
 		    /// This function returns the status of the given edge.
 		    /// It is \c true if the given edge is enabled (i.e. not hidden).
 		    bool status(const Edge& e) const { return Parent::status(e); }
 		    /// \brief Disables the given edge
 		    ///
 		    /// This function disables the given edge in the subgraph,
 		    /// so the iteration jumps over it.
 		    /// It is the same as \ref status() "status(e, false)".
 		    void disable(const Edge& e) const { Parent::status(e, false); }
 		    /// \brief Enables the given edge
 		    ///
 		    /// This function enables the given edge in the subgraph.
 		    /// It is the same as \ref status() "status(e, true)".
 		    void enable(const Edge& e) const { Parent::status(e, true); }
 		  };
 		  /// \brief Returns a read-only FilterEdges adaptor
 		  ///
 		  /// This function just returns a read-only \ref FilterEdges adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates FilterEdges
 		  template<typename GR, typename EF>
 		  FilterEdges<const GR, EF>
 		  filterEdges(const GR& graph, EF& edge_filter) {
 		    return FilterEdges<const GR, EF>(graph, edge_filter);
+		  }
 		  template<typename GR, typename EF>
 		  FilterEdges<const GR, const EF>
 		  filterEdges(const GR& graph, const EF& edge_filter) {
 		    return FilterEdges<const GR, const EF>(graph, edge_filter);
+		  }
 		  template <typename DGR>
 		  class UndirectorBase {
 		  public:
 		    typedef DGR Digraph;
 		    typedef UndirectorBase Adaptor;
 		    typedef True UndirectedTag;
 		    typedef typename Digraph::Arc Edge;
 		    typedef typename Digraph::Node Node;
-		    class Arc : public Edge {
 		    class Arc {
 		      friend class UndirectorBase;
 		    protected:
 		      Edge _edge;
 		      bool _forward;
 		      Arc(const Edge& edge, bool forward) :
 		        Edge(edge), _forward(forward) {}
 		      Arc(const Edge& edge, bool forward)
 		        : _edge(edge), _forward(forward) {}
 		    public:
 		      Arc() {}
-		      Arc(Invalid) : Edge(INVALID), _forward(true) {}
+		      Arc(Invalid) : _edge(INVALID), _forward(true) {}
 		      operator const Edge&() const { return _edge; }
 		      bool operator==(const Arc &other) const {
 		        return _forward == other._forward &&
 		          static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
 		        return _forward == other._forward && _edge == other._edge;
+		      }
 		      bool operator!=(const Arc &other) const {
 		        return _forward != other._forward ||
 		          static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
 		        return _forward != other._forward || _edge != other._edge;
+		      }
 		      bool operator<(const Arc &other) const {
 		        return _forward < other._forward ||
 		          (_forward == other._forward &&
 		           static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
 		          (_forward == other._forward && _edge < other._edge);
+		      }
 		    };
 		    void first(Node& n) const {
 		      _digraph->first(n);
+		    }
 		    void next(Node& n) const {
 		      _digraph->next(n);
+		    }
 		    void first(Arc& a) const {
 		      _digraph->first(a);
+		      _digraph->first(a._edge);
 		      a._forward = true;
+		    }
 		    void next(Arc& a) const {
 		      if (a._forward) {
 		        a._forward = false;
 		      } else {
 		        _digraph->next(a);
+		        _digraph->next(a._edge);
 		        a._forward = true;
+		      }
+		    }
 		    void first(Edge& e) const {
 		      _digraph->first(e);
+		    }
 		    void next(Edge& e) const {
 		      _digraph->next(e);
+		    }
 		    void firstOut(Arc& a, const Node& n) const {
 		      _digraph->firstIn(a, n);
 		      if( static_cast<const Edge&>(a) != INVALID ) {
 		      _digraph->firstIn(a._edge, n);
 		      if (a._edge != INVALID ) {
 		        a._forward = false;
 		      } else {
 		        _digraph->firstOut(a, n);
+		        _digraph->firstOut(a._edge, n);
 		        a._forward = true;
+		      }
+		    }
 		    void nextOut(Arc &a) const {
 		      if (!a._forward) {
 		        Node n = _digraph->target(a);
 		        _digraph->nextIn(a);
 		        if (static_cast<const Edge&>(a) == INVALID ) {
 		          _digraph->firstOut(a, n);
 		        Node n = _digraph->target(a._edge);
 		        _digraph->nextIn(a._edge);
 		        if (a._edge == INVALID) {
 		          _digraph->firstOut(a._edge, n);
 		          a._forward = true;
+		        }
+		      }
 		      else {
 		        _digraph->nextOut(a);
+		        _digraph->nextOut(a._edge);
+		      }
+		    }
 		    void firstIn(Arc &a, const Node &n) const {
 		      _digraph->firstOut(a, n);
 		      if (static_cast<const Edge&>(a) != INVALID ) {
 		      _digraph->firstOut(a._edge, n);
 		      if (a._edge != INVALID ) {
 		        a._forward = false;
 		      } else {
 		        _digraph->firstIn(a, n);
+		        _digraph->firstIn(a._edge, n);
 		        a._forward = true;
+		      }
+		    }
 		    void nextIn(Arc &a) const {
 		      if (!a._forward) {
 		        Node n = _digraph->source(a);
 		        _digraph->nextOut(a);
 		        if( static_cast<const Edge&>(a) == INVALID ) {
 		          _digraph->firstIn(a, n);
 		        Node n = _digraph->source(a._edge);
 		        _digraph->nextOut(a._edge);
 		        if (a._edge == INVALID ) {
 		          _digraph->firstIn(a._edge, n);
 		          a._forward = true;
+		        }
+		      }
 		      else {
 		        _digraph->nextIn(a);
+		        _digraph->nextIn(a._edge);
+		      }
+		    }
 		    void firstInc(Edge &e, bool &d, const Node &n) const {
 		      d = true;
 		      _digraph->firstOut(e, n);
 		      if (e != INVALID) return;
 		      d = false;
 		      _digraph->firstIn(e, n);
+		    }
 		    void nextInc(Edge &e, bool &d) const {
 		      if (d) {
 		        Node s = _digraph->source(e);
 		        _digraph->nextOut(e);
 		        if (e != INVALID) return;
 		        d = false;
 		        _digraph->firstIn(e, s);
 		      } else {
 		        _digraph->nextIn(e);
+		      }
+		    }
 		    Node u(const Edge& e) const {
 		      return _digraph->source(e);
+		    }
 		    Node v(const Edge& e) const {
 		      return _digraph->target(e);
+		    }
 		    Node source(const Arc &a) const {
 		      return a._forward ? _digraph->source(a) : _digraph->target(a);
+		      return a._forward ? _digraph->source(a._edge) : _digraph->target(a._edge);
+		    }
 		    Node target(const Arc &a) const {
 		      return a._forward ? _digraph->target(a) : _digraph->source(a);
+		      return a._forward ? _digraph->target(a._edge) : _digraph->source(a._edge);
+		    }
 		    static Arc direct(const Edge &e, bool d) {
 		      return Arc(e, d);
+		    }
 		    Arc direct(const Edge &e, const Node& n) const {
 		      return Arc(e, _digraph->source(e) == n);
+		    }
 		    static bool direction(const Arc &a) { return a._forward; }
 		    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
 		    Arc arcFromId(int ix) const {
 		      return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
+		    }
 		    Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
 		    int id(const Node &n) const { return _digraph->id(n); }
 		    int id(const Arc &a) const {
 		      return  (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
+		    }
 		    int id(const Edge &e) const { return _digraph->id(e); }
 		    int maxNodeId() const { return _digraph->maxNodeId(); }
 		    int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
 		    int maxEdgeId() const { return _digraph->maxArcId(); }
 		    Node addNode() { return _digraph->addNode(); }
 		    Edge addEdge(const Node& u, const Node& v) {
 		      return _digraph->addArc(u, v);
+		    }
 		    void erase(const Node& i) { _digraph->erase(i); }
 		    void erase(const Edge& i) { _digraph->erase(i); }
 		    void clear() { _digraph->clear(); }
 		    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
 		    int nodeNum() const { return _digraph->nodeNum(); }
 		    typedef ArcNumTagIndicator<Digraph> ArcNumTag;
 		    int arcNum() const { return 2 * _digraph->arcNum(); }
 		    typedef ArcNumTag EdgeNumTag;
 		    int edgeNum() const { return _digraph->arcNum(); }
 		    typedef FindArcTagIndicator<Digraph> FindArcTag;
 		    Arc findArc(Node s, Node t, Arc p = INVALID) const {
 		      if (p == INVALID) {
 		        Edge arc = _digraph->findArc(s, t);
 		        if (arc != INVALID) return direct(arc, true);
 		        arc = _digraph->findArc(t, s);
 		        if (arc != INVALID) return direct(arc, false);
 		      } else if (direction(p)) {
 		        Edge arc = _digraph->findArc(s, t, p);
 		        if (arc != INVALID) return direct(arc, true);

lemon/concepts/graph.h

Show inline comments

@@ -265,135 +265,137 @@
 		      ///
 		      /// Its usage is quite simple, for example you can compute the
 		      /// degree (i.e. count the number of incident arcs of a node \c n
 		      /// in graph \c g of type \c Graph as follows.
 		      ///
 		      ///\code
 		      /// int count=0;
 		      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class IncEdgeIt : public Edge {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        IncEdgeIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        IncEdgeIt(Invalid) { }
 		        /// This constructor sets the iterator to first incident arc.
 		        /// This constructor set the iterator to the first incident arc of
 		        /// the node.
 		        IncEdgeIt(const Graph&, const Node&) { }
 		        /// Edge -> IncEdgeIt conversion
 		        /// Sets the iterator to the value of the trivial iterator \c e.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        IncEdgeIt(const Graph&, const Edge&) { }
 		        /// Next incident arc
 		        /// Assign the iterator to the next incident arc
 		        /// of the corresponding node.
 		        IncEdgeIt& operator++() { return *this; }
 		      };
 		      /// The directed arc type.
 		      /// The directed arc type. It can be converted to the
 		      /// edge or it should be inherited from the undirected
 		      /// arc.
 		      class Arc : public Edge {
 		      /// edge.
 		      class Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        Arc() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
-		        Arc(const Arc& e) : Edge(e) { }
 		        Arc(const Arc&) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        Arc(Invalid) { }
 		        /// Equality operator
 		        /// Two iterators are equal if and only if they point to the
 		        /// same object or both are invalid.
 		        bool operator==(Arc) const { return true; }
 		        /// Inequality operator
 		        /// \sa operator==(Arc n)
 		        ///
 		        bool operator!=(Arc) const { return true; }
 		        /// Artificial ordering operator.
 		        /// To allow the use of graph descriptors as key type in std::map or
 		        /// similar associative container we require this.
 		        ///
 		        /// \note This operator only have to define some strict ordering of
 		        /// the items; this order has nothing to do with the iteration
 		        /// ordering of the items.
 		        bool operator<(Arc) const { return false; }
 		        /// Converison to Edge
 		        operator Edge() const { return Edge(); }
 		      };
 		      /// This iterator goes through each directed arc.
 		      /// This iterator goes through each arc of a graph.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of arcs in a graph \c g of type \c Graph as follows:
 		      ///\code
 		      /// int count=0;
 		      /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class ArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        ArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        ArcIt(const ArcIt& e) : Arc(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        ArcIt(Invalid) { }
 		        /// This constructor sets the iterator to the first arc.
 		        /// This constructor sets the iterator to the first arc of \c g.
 		        ///@param g the graph
 		        ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
 		        /// Arc -> ArcIt conversion
 		        /// Sets the iterator to the value of the trivial iterator \c e.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        ArcIt(const Graph&, const Arc&) { }
 		        ///Next arc
 		        /// Assign the iterator to the next arc.
 		        ArcIt& operator++() { return *this; }
 		      };
 		      /// This iterator goes trough the outgoing directed arcs of a node.
 		      /// This iterator goes trough the \e outgoing arcs of a certain node
 		      /// of a graph.

lemon/connectivity.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_CONNECTIVITY_H
 		#define LEMON_CONNECTIVITY_H
 		#include <lemon/dfs.h>
 		#include <lemon/bfs.h>
 		#include <lemon/core.h>
 		#include <lemon/maps.h>
 		#include <lemon/adaptors.h>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/concepts/graph.h>
 		#include <lemon/concept_check.h>
 		#include <stack>
 		#include <functional>
 		/// \ingroup graph_properties
 		/// \file
 		/// \brief Connectivity algorithms
 		///
 		/// Connectivity algorithms
 		namespace lemon {
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Check whether the given undirected graph is connected.
+		  /// \brief Check whether an undirected graph is connected.
 		  ///
 		  /// Check whether the given undirected graph is connected.
 		  /// \param graph The undirected graph.
-		  /// \return \c true when there is path between any two nodes in the graph.
+		  /// This function checks whether the given undirected graph is connected,
 		  /// i.e. there is a path between any two nodes in the graph.
 		  ///
 		  /// \return \c true if the graph is connected.
 		  /// \note By definition, the empty graph is connected.
 		  ///
 		  /// \see countConnectedComponents(), connectedComponents()
 		  /// \see stronglyConnected()
 		  template <typename Graph>
 		  bool connected(const Graph& graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    if (NodeIt(graph) == INVALID) return true;
 		    Dfs<Graph> dfs(graph);
 		    dfs.run(NodeIt(graph));
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        return false;
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Count the number of connected components of an undirected graph
 		  ///
-		  /// Count the number of connected components of an undirected graph
+		  /// This function counts the number of connected components of the given
 		  /// undirected graph.
 		  ///
 		  /// \param graph The graph. It must be undirected.
 		  /// \return The number of components
 		  /// The connected components are the classes of an equivalence relation
 		  /// on the nodes of an undirected graph. Two nodes are in the same class
 		  /// if they are connected with a path.
 		  ///
 		  /// \return The number of connected components.
 		  /// \note By definition, the empty graph consists
 		  /// of zero connected components.
 		  ///
 		  /// \see connected(), connectedComponents()
 		  template <typename Graph>
 		  int countConnectedComponents(const Graph &graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::Arc Arc;
 		    typedef NullMap<Node, Arc> PredMap;
 		    typedef NullMap<Node, int> DistMap;
 		    int compNum = 0;
 		    typename Bfs<Graph>::
 		      template SetPredMap<PredMap>::
 		      template SetDistMap<DistMap>::
 		      Create bfs(graph);
 		    PredMap predMap;
 		    bfs.predMap(predMap);
 		    DistMap distMap;
 		    bfs.distMap(distMap);
 		    bfs.init();
 		    for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
 		      if (!bfs.reached(n)) {
 		        bfs.addSource(n);
 		        bfs.start();
 		        ++compNum;
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Find the connected components of an undirected graph
 		  ///
-		  /// Find the connected components of an undirected graph.
+		  /// This function finds the connected components of the given undirected
 		  /// graph.
 		  ///
 		  /// The connected components are the classes of an equivalence relation
 		  /// on the nodes of an undirected graph. Two nodes are in the same class
 		  /// if they are connected with a path.
 		  ///
 		  /// \image html connected_components.png
 		  /// \image latex connected_components.eps "Connected components" width=\textwidth
 		  ///
-		  /// \param graph The graph. It must be undirected.
+		  /// \param graph The undirected graph.
 		  /// \retval compMap A writable node map. The values will be set from 0 to
 		  /// the number of the connected components minus one. Each values of the map
 		  /// will be set exactly once, the values of a certain component will be
 		  /// the number of the connected components minus one. Each value of the map
 		  /// will be set exactly once, and the values of a certain component will be
 		  /// set continuously.
 		  /// \return The number of components
+		  /// \return The number of connected components.
 		  /// \note By definition, the empty graph consists
 		  /// of zero connected components.
 		  ///
 		  /// \see connected(), countConnectedComponents()
 		  template <class Graph, class NodeMap>
 		  int connectedComponents(const Graph &graph, NodeMap &compMap) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::Arc Arc;
 		    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
 		    typedef NullMap<Node, Arc> PredMap;
 		    typedef NullMap<Node, int> DistMap;
 		    int compNum = 0;
 		    typename Bfs<Graph>::
 		      template SetPredMap<PredMap>::
 		      template SetDistMap<DistMap>::
 		      Create bfs(graph);
 		    PredMap predMap;
 		    bfs.predMap(predMap);
 		    DistMap distMap;
 		    bfs.distMap(distMap);
 		    bfs.init();
 		    for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
 		      if(!bfs.reached(n)) {
 		        bfs.addSource(n);
 		        while (!bfs.emptyQueue()) {
 		          compMap.set(bfs.nextNode(), compNum);
 		          bfs.processNextNode();
+		        }
 		        ++compNum;
+		      }
+		    }
 		    return compNum;
+		  }
 		  namespace _connectivity_bits {
 		    template <typename Digraph, typename Iterator >
 		    struct LeaveOrderVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      LeaveOrderVisitor(Iterator it) : _it(it) {}
 		      void leave(const Node& node) {
 		        *(_it++) = node;
+		      }
@@ -186,337 +205,354 @@
+		      }
 		    private:
 		      Map& _map;
 		      Value& _value;
 		    };
 		    template <typename Digraph, typename ArcMap>
 		    struct StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc Arc;
 		      StronglyConnectedCutArcsVisitor(const Digraph& digraph,
 		                                      ArcMap& cutMap,
 		                                      int& cutNum)
 		        : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
 		          _compMap(digraph, -1), _num(-1) {
+		      }
 		      void start(const Node&) {
 		        ++_num;
+		      }
 		      void reach(const Node& node) {
 		        _compMap.set(node, _num);
+		      }
 		      void examine(const Arc& arc) {
 		         if (_compMap[_digraph.source(arc)] !=
 		             _compMap[_digraph.target(arc)]) {
 		           _cutMap.set(arc, true);
 		           ++_cutNum;
+		         }
+		      }
 		    private:
 		      const Digraph& _digraph;
 		      ArcMap& _cutMap;
 		      int& _cutNum;
 		      typename Digraph::template NodeMap<int> _compMap;
 		      int _num;
 		    };
+		  }
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Check whether the given directed graph is strongly connected.
+		  /// \brief Check whether a directed graph is strongly connected.
 		  ///
 		  /// Check whether the given directed graph is strongly connected. The
 		  /// graph is strongly connected when any two nodes of the graph are
 		  /// This function checks whether the given directed graph is strongly
 		  /// connected, i.e. any two nodes of the digraph are
 		  /// connected with directed paths in both direction.
 		  /// \return \c false when the graph is not strongly connected.
 		  /// \see connected
 		  ///
-		  /// \note By definition, the empty graph is strongly connected.
+		  /// \return \c true if the digraph is strongly connected.
 		  /// \note By definition, the empty digraph is strongly connected.
 		  ///
 		  /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
 		  /// \see connected()
 		  template <typename Digraph>
 		  bool stronglyConnected(const Digraph& digraph) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typename Digraph::Node source = NodeIt(digraph);
 		    if (source == INVALID) return true;
 		    using namespace _connectivity_bits;
 		    typedef DfsVisitor<Digraph> Visitor;
 		    Visitor visitor;
 		    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
 		    dfs.init();
 		    dfs.addSource(source);
 		    dfs.start();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        return false;
+		      }
+		    }
 		    typedef ReverseDigraph<const Digraph> RDigraph;
 		    typedef typename RDigraph::NodeIt RNodeIt;
 		    RDigraph rdigraph(digraph);
-		    typedef DfsVisitor<Digraph> RVisitor;
+		    typedef DfsVisitor<RDigraph> RVisitor;
 		    RVisitor rvisitor;
 		    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
 		    rdfs.init();
 		    rdfs.addSource(source);
 		    rdfs.start();
 		    for (RNodeIt it(rdigraph); it != INVALID; ++it) {
 		      if (!rdfs.reached(it)) {
 		        return false;
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Count the strongly connected components of a directed graph
+		  /// \brief Count the number of strongly connected components of a
 		  /// directed graph
 		  ///
-		  /// Count the strongly connected components of a directed graph.
+		  /// This function counts the number of strongly connected components of
 		  /// the given directed graph.
 		  ///
 		  /// The strongly connected components are the classes of an
-		  /// equivalence relation on the nodes of the graph. Two nodes are in
+		  /// equivalence relation on the nodes of a digraph. Two nodes are in
 		  /// the same class if they are connected with directed paths in both
 		  /// direction.
 		  ///
 		  /// \param digraph The graph.
 		  /// \return The number of components
-		  /// \note By definition, the empty graph has zero
+		  /// \return The number of strongly connected components.
 		  /// \note By definition, the empty digraph has zero
 		  /// strongly connected components.
 		  ///
 		  /// \see stronglyConnected(), stronglyConnectedComponents()
 		  template <typename Digraph>
 		  int countStronglyConnectedComponents(const Digraph& digraph) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    using namespace _connectivity_bits;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::ArcIt ArcIt;
 		    typedef std::vector<Node> Container;
 		    typedef typename Container::iterator Iterator;
 		    Container nodes(countNodes(digraph));
 		    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
 		    Visitor visitor(nodes.begin());
 		    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
 		    dfs.init();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    typedef typename Container::reverse_iterator RIterator;
 		    typedef ReverseDigraph<const Digraph> RDigraph;
 		    RDigraph rdigraph(digraph);
 		    typedef DfsVisitor<Digraph> RVisitor;
 		    RVisitor rvisitor;
 		    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
 		    int compNum = 0;
 		    rdfs.init();
 		    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
 		      if (!rdfs.reached(*it)) {
 		        rdfs.addSource(*it);
 		        rdfs.start();
 		        ++compNum;
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Find the strongly connected components of a directed graph
 		  ///
 		  /// Find the strongly connected components of a directed graph.  The
 		  /// strongly connected components are the classes of an equivalence
 		  /// relation on the nodes of the graph. Two nodes are in
 		  /// relationship when there are directed paths between them in both
 		  /// direction. In addition, the numbering of components will satisfy
 		  /// that there is no arc going from a higher numbered component to
-		  /// a lower.
+		  /// This function finds the strongly connected components of the given
 		  /// directed graph. In addition, the numbering of the components will
 		  /// satisfy that there is no arc going from a higher numbered component
 		  /// to a lower one (i.e. it provides a topological order of the components).
 		  ///
 		  /// The strongly connected components are the classes of an
 		  /// equivalence relation on the nodes of a digraph. Two nodes are in
 		  /// the same class if they are connected with directed paths in both
 		  /// direction.
 		  ///
 		  /// \image html strongly_connected_components.png
 		  /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
 		  ///
 		  /// \param digraph The digraph.
 		  /// \retval compMap A writable node map. The values will be set from 0 to
 		  /// the number of the strongly connected components minus one. Each value
 		  /// of the map will be set exactly once, the values of a certain component
 		  /// will be set continuously.
-		  /// \return The number of components
+		  /// of the map will be set exactly once, and the values of a certain
 		  /// component will be set continuously.
 		  /// \return The number of strongly connected components.
 		  /// \note By definition, the empty digraph has zero
 		  /// strongly connected components.
 		  ///
 		  /// \see stronglyConnected(), countStronglyConnectedComponents()
 		  template <typename Digraph, typename NodeMap>
 		  int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
 		    using namespace _connectivity_bits;
 		    typedef std::vector<Node> Container;
 		    typedef typename Container::iterator Iterator;
 		    Container nodes(countNodes(digraph));
 		    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
 		    Visitor visitor(nodes.begin());
 		    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
 		    dfs.init();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    typedef typename Container::reverse_iterator RIterator;
 		    typedef ReverseDigraph<const Digraph> RDigraph;
 		    RDigraph rdigraph(digraph);
 		    int compNum = 0;
 		    typedef FillMapVisitor<RDigraph, NodeMap> RVisitor;
 		    RVisitor rvisitor(compMap, compNum);
 		    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
 		    rdfs.init();
 		    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
 		      if (!rdfs.reached(*it)) {
 		        rdfs.addSource(*it);
 		        rdfs.start();
 		        ++compNum;
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Find the cut arcs of the strongly connected components.
 		  ///
 		  /// Find the cut arcs of the strongly connected components.
 		  /// The strongly connected components are the classes of an equivalence
 		  /// relation on the nodes of the graph. Two nodes are in relationship
 		  /// when there are directed paths between them in both direction.
 		  /// This function finds the cut arcs of the strongly connected components
 		  /// of the given digraph.
 		  ///
 		  /// The strongly connected components are the classes of an
 		  /// equivalence relation on the nodes of a digraph. Two nodes are in
 		  /// the same class if they are connected with directed paths in both
 		  /// direction.
 		  /// The strongly connected components are separated by the cut arcs.
 		  ///
 		  /// \param graph The graph.
 		  /// \retval cutMap A writable node map. The values will be set true when the
-		  /// arc is a cut arc.
+		  /// \param digraph The digraph.
 		  /// \retval cutMap A writable arc map. The values will be set to \c true
 		  /// for the cut arcs (exactly once for each cut arc), and will not be
 		  /// changed for other arcs.
 		  /// \return The number of cut arcs.
 		  ///
-		  /// \return The number of cut arcs
+		  /// \see stronglyConnected(), stronglyConnectedComponents()
 		  template <typename Digraph, typename ArcMap>
-		  int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {
+		  int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
 		    using namespace _connectivity_bits;
 		    typedef std::vector<Node> Container;
 		    typedef typename Container::iterator Iterator;
-		    Container nodes(countNodes(graph));
+		    Container nodes(countNodes(digraph));
 		    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
 		    Visitor visitor(nodes.begin());
-		    DfsVisit<Digraph, Visitor> dfs(graph, visitor);
+		    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
 		    dfs.init();
-		    for (NodeIt it(graph); it != INVALID; ++it) {
+		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    typedef typename Container::reverse_iterator RIterator;
 		    typedef ReverseDigraph<const Digraph> RDigraph;
-		    RDigraph rgraph(graph);
+		    RDigraph rdigraph(digraph);
 		    int cutNum = 0;
 		    typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
-		    RVisitor rvisitor(rgraph, cutMap, cutNum);
+		    RVisitor rvisitor(rdigraph, cutMap, cutNum);
-		    DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
+		    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
 		    rdfs.init();
 		    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
 		      if (!rdfs.reached(*it)) {
 		        rdfs.addSource(*it);
 		        rdfs.start();
+		      }
+		    }
 		    return cutNum;
+		  }
 		  namespace _connectivity_bits {
 		    template <typename Digraph>
 		    class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Edge Edge;
 		      CountBiNodeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
 		        : _graph(graph), _compNum(compNum),
 		          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
 		      void start(const Node& node) {
 		        _predMap.set(node, INVALID);
+		      }
 		      void reach(const Node& node) {
 		        _numMap.set(node, _num);
 		        _retMap.set(node, _num);
 		        ++_num;
+		      }
 		      void discover(const Arc& edge) {
 		        _predMap.set(_graph.target(edge), _graph.source(edge));
+		      }
 		      void examine(const Arc& edge) {
 		        if (_graph.source(edge) == _graph.target(edge) &&
 		            _graph.direction(edge)) {
 		          ++_compNum;
 		          return;
+		        }
 		        if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
 		          return;
+		        }
 		        if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
@@ -661,203 +697,219 @@
+		        }
 		        if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
 		        if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
+		        }
+		      }
 		      void backtrack(const Arc& edge) {
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
 		        if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
 		          if (_predMap[_graph.source(edge)] != INVALID) {
 		            if (!_cutMap[_graph.source(edge)]) {
 		              _cutMap.set(_graph.source(edge), true);
 		              ++_cutNum;
+		            }
 		          } else if (rootCut) {
 		            if (!_cutMap[_graph.source(edge)]) {
 		              _cutMap.set(_graph.source(edge), true);
 		              ++_cutNum;
+		            }
 		          } else {
 		            rootCut = true;
+		          }
+		        }
+		      }
 		    private:
 		      const Digraph& _graph;
 		      NodeMap& _cutMap;
 		      int& _cutNum;
 		      typename Digraph::template NodeMap<int> _numMap;
 		      typename Digraph::template NodeMap<int> _retMap;
 		      typename Digraph::template NodeMap<Node> _predMap;
 		      std::stack<Edge> _edgeStack;
 		      int _num;
 		      bool rootCut;
 		    };
+		  }
 		  template <typename Graph>
 		  int countBiNodeConnectedComponents(const Graph& graph);
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Checks the graph is bi-node-connected.
+		  /// \brief Check whether an undirected graph is bi-node-connected.
 		  ///
 		  /// This function checks that the undirected graph is bi-node-connected
 		  /// graph. The graph is bi-node-connected if any two undirected edge is
-		  /// on same circle.
+		  /// This function checks whether the given undirected graph is
 		  /// bi-node-connected, i.e. any two edges are on same circle.
 		  ///
 		  /// \param graph The graph.
 		  /// \return \c true when the graph bi-node-connected.
 		  /// \return \c true if the graph bi-node-connected.
 		  /// \note By definition, the empty graph is bi-node-connected.
 		  ///
 		  /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
 		  template <typename Graph>
 		  bool biNodeConnected(const Graph& graph) {
 		    return countBiNodeConnectedComponents(graph) <= 1;
+		  }
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Count the biconnected components.
+		  /// \brief Count the number of bi-node-connected components of an
 		  /// undirected graph.
 		  ///
 		  /// This function finds the bi-node-connected components in an undirected
 		  /// graph. The biconnected components are the classes of an equivalence
 		  /// relation on the undirected edges. Two undirected edge is in relationship
 		  /// when they are on same circle.
 		  /// This function counts the number of bi-node-connected components of
 		  /// the given undirected graph.
 		  ///
 		  /// \param graph The graph.
 		  /// \return The number of components.
 		  /// The bi-node-connected components are the classes of an equivalence
 		  /// relation on the edges of a undirected graph. Two edges are in the
 		  /// same class if they are on same circle.
 		  ///
 		  /// \return The number of bi-node-connected components.
 		  ///
 		  /// \see biNodeConnected(), biNodeConnectedComponents()
 		  template <typename Graph>
 		  int countBiNodeConnectedComponents(const Graph& graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    using namespace _connectivity_bits;
 		    typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
 		    int compNum = 0;
 		    Visitor visitor(graph, compNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Find the bi-node-connected components.
+		  /// \brief Find the bi-node-connected components of an undirected graph.
 		  ///
 		  /// This function finds the bi-node-connected components in an undirected
 		  /// graph. The bi-node-connected components are the classes of an equivalence
 		  /// relation on the undirected edges. Two undirected edge are in relationship
 		  /// when they are on same circle.
 		  /// This function finds the bi-node-connected components of the given
 		  /// undirected graph.
 		  ///
 		  /// The bi-node-connected components are the classes of an equivalence
 		  /// relation on the edges of a undirected graph. Two edges are in the
 		  /// same class if they are on same circle.
 		  ///
 		  /// \image html node_biconnected_components.png
 		  /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
 		  ///
 		  /// \param graph The graph.
 		  /// \retval compMap A writable uedge map. The values will be set from 0
 		  /// to the number of the biconnected components minus one. Each values
 		  /// of the map will be set exactly once, the values of a certain component
 		  /// will be set continuously.
 		  /// \return The number of components.
 		  /// \param graph The undirected graph.
 		  /// \retval compMap A writable edge map. The values will be set from 0
 		  /// to the number of the bi-node-connected components minus one. Each
 		  /// value of the map will be set exactly once, and the values of a
 		  /// certain component will be set continuously.
 		  /// \return The number of bi-node-connected components.
 		  ///
 		  /// \see biNodeConnected(), countBiNodeConnectedComponents()
 		  template <typename Graph, typename EdgeMap>
 		  int biNodeConnectedComponents(const Graph& graph,
 		                                EdgeMap& compMap) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::Edge Edge;
 		    checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
 		    using namespace _connectivity_bits;
 		    typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
 		    int compNum = 0;
 		    Visitor visitor(graph, compMap, compNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Find the bi-node-connected cut nodes.
+		  /// \brief Find the bi-node-connected cut nodes in an undirected graph.
 		  ///
 		  /// This function finds the bi-node-connected cut nodes in an undirected
 		  /// graph. The bi-node-connected components are the classes of an equivalence
 		  /// relation on the undirected edges. Two undirected edges are in
 		  /// relationship when they are on same circle. The biconnected components
-		  /// are separted by nodes which are the cut nodes of the components.
+		  /// This function finds the bi-node-connected cut nodes in the given
 		  /// undirected graph.
 		  ///
 		  /// \param graph The graph.
 		  /// \retval cutMap A writable edge map. The values will be set true when
-		  /// the node separate two or more components.
+		  /// The bi-node-connected components are the classes of an equivalence
 		  /// relation on the edges of a undirected graph. Two edges are in the
 		  /// same class if they are on same circle.
 		  /// The bi-node-connected components are separted by the cut nodes of
 		  /// the components.
 		  ///
 		  /// \param graph The undirected graph.
 		  /// \retval cutMap A writable node map. The values will be set to
 		  /// \c true for the nodes that separate two or more components
 		  /// (exactly once for each cut node), and will not be changed for
 		  /// other nodes.
 		  /// \return The number of the cut nodes.
 		  ///
 		  /// \see biNodeConnected(), biNodeConnectedComponents()
 		  template <typename Graph, typename NodeMap>
 		  int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		    checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
 		    using namespace _connectivity_bits;
 		    typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
 		    int cutNum = 0;
 		    Visitor visitor(graph, cutMap, cutNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return cutNum;
+		  }
 		  namespace _connectivity_bits {
 		    template <typename Digraph>
 		    class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Edge Edge;
 		      CountBiEdgeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
 		        : _graph(graph), _compNum(compNum),
 		          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
 		      void start(const Node& node) {
 		        _predMap.set(node, INVALID);
+		      }
 		      void reach(const Node& node) {
 		        _numMap.set(node, _num);
 		        _retMap.set(node, _num);
 		        ++_num;
+		      }
@@ -986,602 +1038,628 @@
 		        ++_num;
+		      }
 		      void leave(const Node& node) {
 		        if (_numMap[node] <= _retMap[node]) {
 		          if (_predMap[node] != INVALID) {
 		            _cutMap.set(_predMap[node], true);
 		            ++_cutNum;
+		          }
+		        }
+		      }
 		      void discover(const Arc& edge) {
 		        _predMap.set(_graph.target(edge), edge);
+		      }
 		      void examine(const Arc& edge) {
 		        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
 		          return;
+		        }
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
+		      }
 		      void backtrack(const Arc& edge) {
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
+		      }
 		    private:
 		      const Digraph& _graph;
 		      ArcMap& _cutMap;
 		      int& _cutNum;
 		      typename Digraph::template NodeMap<int> _numMap;
 		      typename Digraph::template NodeMap<int> _retMap;
 		      typename Digraph::template NodeMap<Arc> _predMap;
 		      int _num;
 		    };
+		  }
 		  template <typename Graph>
 		  int countBiEdgeConnectedComponents(const Graph& graph);
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Checks that the graph is bi-edge-connected.
+		  /// \brief Check whether an undirected graph is bi-edge-connected.
 		  ///
 		  /// This function checks that the graph is bi-edge-connected. The undirected
 		  /// graph is bi-edge-connected when any two nodes are connected with two
-		  /// edge-disjoint paths.
+		  /// This function checks whether the given undirected graph is
 		  /// bi-edge-connected, i.e. any two nodes are connected with at least
 		  /// two edge-disjoint paths.
 		  ///
 		  /// \param graph The undirected graph.
 		  /// \return The number of components.
 		  /// \return \c true if the graph is bi-edge-connected.
 		  /// \note By definition, the empty graph is bi-edge-connected.
 		  ///
 		  /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
 		  template <typename Graph>
 		  bool biEdgeConnected(const Graph& graph) {
 		    return countBiEdgeConnectedComponents(graph) <= 1;
+		  }
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Count the bi-edge-connected components.
+		  /// \brief Count the number of bi-edge-connected components of an
 		  /// undirected graph.
 		  ///
 		  /// This function count the bi-edge-connected components in an undirected
 		  /// graph. The bi-edge-connected components are the classes of an equivalence
 		  /// relation on the nodes. Two nodes are in relationship when they are
 		  /// connected with at least two edge-disjoint paths.
 		  /// This function counts the number of bi-edge-connected components of
 		  /// the given undirected graph.
 		  ///
 		  /// \param graph The undirected graph.
 		  /// \return The number of components.
 		  /// The bi-edge-connected components are the classes of an equivalence
 		  /// relation on the nodes of an undirected graph. Two nodes are in the
 		  /// same class if they are connected with at least two edge-disjoint
 		  /// paths.
 		  ///
 		  /// \return The number of bi-edge-connected components.
 		  ///
 		  /// \see biEdgeConnected(), biEdgeConnectedComponents()
 		  template <typename Graph>
 		  int countBiEdgeConnectedComponents(const Graph& graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    using namespace _connectivity_bits;
 		    typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
 		    int compNum = 0;
 		    Visitor visitor(graph, compNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Find the bi-edge-connected components.
+		  /// \brief Find the bi-edge-connected components of an undirected graph.
 		  ///
 		  /// This function finds the bi-edge-connected components in an undirected
 		  /// graph. The bi-edge-connected components are the classes of an equivalence
 		  /// relation on the nodes. Two nodes are in relationship when they are
 		  /// connected at least two edge-disjoint paths.
 		  /// This function finds the bi-edge-connected components of the given
 		  /// undirected graph.
 		  ///
 		  /// The bi-edge-connected components are the classes of an equivalence
 		  /// relation on the nodes of an undirected graph. Two nodes are in the
 		  /// same class if they are connected with at least two edge-disjoint
 		  /// paths.
 		  ///
 		  /// \image html edge_biconnected_components.png
 		  /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
 		  ///
 		  /// \param graph The graph.
+		  /// \param graph The undirected graph.
 		  /// \retval compMap A writable node map. The values will be set from 0 to
 		  /// the number of the biconnected components minus one. Each values
 		  /// of the map will be set exactly once, the values of a certain component
 		  /// will be set continuously.
 		  /// \return The number of components.
 		  /// the number of the bi-edge-connected components minus one. Each value
 		  /// of the map will be set exactly once, and the values of a certain
 		  /// component will be set continuously.
 		  /// \return The number of bi-edge-connected components.
 		  ///
 		  /// \see biEdgeConnected(), countBiEdgeConnectedComponents()
 		  template <typename Graph, typename NodeMap>
 		  int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::Node Node;
 		    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
 		    using namespace _connectivity_bits;
 		    typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
 		    int compNum = 0;
 		    Visitor visitor(graph, compMap, compNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Find the bi-edge-connected cut edges.
+		  /// \brief Find the bi-edge-connected cut edges in an undirected graph.
 		  ///
 		  /// This function finds the bi-edge-connected components in an undirected
 		  /// graph. The bi-edge-connected components are the classes of an equivalence
 		  /// relation on the nodes. Two nodes are in relationship when they are
 		  /// connected with at least two edge-disjoint paths. The bi-edge-connected
 		  /// components are separted by edges which are the cut edges of the
 		  /// components.
 		  /// This function finds the bi-edge-connected cut edges in the given
 		  /// undirected graph.
 		  ///
 		  /// \param graph The graph.
 		  /// \retval cutMap A writable node map. The values will be set true when the
-		  /// edge is a cut edge.
+		  /// The bi-edge-connected components are the classes of an equivalence
 		  /// relation on the nodes of an undirected graph. Two nodes are in the
 		  /// same class if they are connected with at least two edge-disjoint
 		  /// paths.
 		  /// The bi-edge-connected components are separted by the cut edges of
 		  /// the components.
 		  ///
 		  /// \param graph The undirected graph.
 		  /// \retval cutMap A writable edge map. The values will be set to \c true
 		  /// for the cut edges (exactly once for each cut edge), and will not be
 		  /// changed for other edges.
 		  /// \return The number of cut edges.
 		  ///
 		  /// \see biEdgeConnected(), biEdgeConnectedComponents()
 		  template <typename Graph, typename EdgeMap>
 		  int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::Edge Edge;
 		    checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
 		    using namespace _connectivity_bits;
 		    typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
 		    int cutNum = 0;
 		    Visitor visitor(graph, cutMap, cutNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return cutNum;
+		  }
 		  namespace _connectivity_bits {
 		    template <typename Digraph, typename IntNodeMap>
 		    class TopologicalSortVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc edge;
 		      TopologicalSortVisitor(IntNodeMap& order, int num)
 		        : _order(order), _num(num) {}
 		      void leave(const Node& node) {
 		        _order.set(node, --_num);
+		      }
 		    private:
 		      IntNodeMap& _order;
 		      int _num;
 		    };
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Check whether a digraph is DAG.
 		  ///
 		  /// This function checks whether the given digraph is DAG, i.e.
 		  /// \e Directed \e Acyclic \e Graph.
 		  /// \return \c true if there is no directed cycle in the digraph.
 		  /// \see acyclic()
 		  template <typename Digraph>
 		  bool dag(const Digraph& digraph) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
 		      Create dfs(digraph);
 		    ProcessedMap processed(digraph);
 		    dfs.processedMap(processed);
 		    dfs.init();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        while (!dfs.emptyQueue()) {
 		          Arc arc = dfs.nextArc();
 		          Node target = digraph.target(arc);
 		          if (dfs.reached(target) && !processed[target]) {
 		            return false;
+		          }
 		          dfs.processNextArc();
+		        }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Sort the nodes of a DAG into topolgical order.
 		  ///
-		  /// Sort the nodes of a DAG into topolgical order.
+		  /// This function sorts the nodes of the given acyclic digraph (DAG)
 		  /// into topolgical order.
 		  ///
-		  /// \param graph The graph. It must be directed and acyclic.
+		  /// \param digraph The digraph, which must be DAG.
 		  /// \retval order A writable node map. The values will be set from 0 to
 		  /// the number of the nodes in the graph minus one. Each values of the map
 		  /// will be set exactly once, the values  will be set descending order.
 		  /// the number of the nodes in the digraph minus one. Each value of the
 		  /// map will be set exactly once, and the values will be set descending
 		  /// order.
 		  ///
 		  /// \see checkedTopologicalSort
 		  /// \see dag
 		  /// \see dag(), checkedTopologicalSort()
 		  template <typename Digraph, typename NodeMap>
-		  void topologicalSort(const Digraph& graph, NodeMap& order) {
+		  void topologicalSort(const Digraph& digraph, NodeMap& order) {
 		    using namespace _connectivity_bits;
 		    checkConcept<concepts::Digraph, Digraph>();
 		    checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    TopologicalSortVisitor<Digraph, NodeMap>
-		      visitor(order, countNodes(graph));
+		      visitor(order, countNodes(digraph));
 		    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
-		      dfs(graph, visitor);
+		      dfs(digraph, visitor);
 		    dfs.init();
-		    for (NodeIt it(graph); it != INVALID; ++it) {
+		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Sort the nodes of a DAG into topolgical order.
 		  ///
 		  /// Sort the nodes of a DAG into topolgical order. It also checks
 		  /// that the given graph is DAG.
 		  /// This function sorts the nodes of the given acyclic digraph (DAG)
 		  /// into topolgical order and also checks whether the given digraph
 		  /// is DAG.
 		  ///
 		  /// \param digraph The graph. It must be directed and acyclic.
 		  /// \retval order A readable - writable node map. The values will be set
 		  /// from 0 to the number of the nodes in the graph minus one. Each values
 		  /// of the map will be set exactly once, the values will be set descending
 		  /// order.
 		  /// \return \c false when the graph is not DAG.
 		  /// \param digraph The digraph.
 		  /// \retval order A readable and writable node map. The values will be
 		  /// set from 0 to the number of the nodes in the digraph minus one.
 		  /// Each value of the map will be set exactly once, and the values will
 		  /// be set descending order.
 		  /// \return \c false if the digraph is not DAG.
 		  ///
 		  /// \see topologicalSort
 		  /// \see dag
 		  /// \see dag(), topologicalSort()
 		  template <typename Digraph, typename NodeMap>
 		  bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
 		    using namespace _connectivity_bits;
 		    checkConcept<concepts::Digraph, Digraph>();
 		    checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,
 		      NodeMap>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      order.set(it, -1);
+		    }
 		    TopologicalSortVisitor<Digraph, NodeMap>
 		      visitor(order, countNodes(digraph));
 		    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
 		      dfs(digraph, visitor);
 		    dfs.init();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        while (!dfs.emptyQueue()) {
 		           Arc arc = dfs.nextArc();
 		           Node target = digraph.target(arc);
 		           if (dfs.reached(target) && order[target] == -1) {
 		             return false;
+		           }
 		           dfs.processNextArc();
+		         }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Check that the given directed graph is a DAG.
+		  /// \brief Check whether an undirected graph is acyclic.
 		  ///
 		  /// Check that the given directed graph is a DAG. The DAG is
 		  /// an Directed Acyclic Digraph.
 		  /// \return \c false when the graph is not DAG.
 		  /// \see acyclic
 		  template <typename Digraph>
 		  bool dag(const Digraph& digraph) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
 		      Create dfs(digraph);
 		    ProcessedMap processed(digraph);
 		    dfs.processedMap(processed);
 		    dfs.init();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        while (!dfs.emptyQueue()) {
 		          Arc edge = dfs.nextArc();
 		          Node target = digraph.target(edge);
 		          if (dfs.reached(target) && !processed[target]) {
 		            return false;
+		          }
 		          dfs.processNextArc();
+		        }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Check that the given undirected graph is acyclic.
 		  ///
 		  /// Check that the given undirected graph acyclic.
 		  /// \param graph The undirected graph.
 		  /// \return \c true when there is no circle in the graph.
 		  /// \see dag
 		  /// This function checks whether the given undirected graph is acyclic.
 		  /// \return \c true if there is no cycle in the graph.
 		  /// \see dag()
 		  template <typename Graph>
 		  bool acyclic(const Graph& graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::Arc Arc;
 		    Dfs<Graph> dfs(graph);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        while (!dfs.emptyQueue()) {
 		          Arc edge = dfs.nextArc();
 		          Node source = graph.source(edge);
-		          Node target = graph.target(edge);
+		          Arc arc = dfs.nextArc();
 		          Node source = graph.source(arc);
 		          Node target = graph.target(arc);
 		          if (dfs.reached(target) &&
-		              dfs.predArc(source) != graph.oppositeArc(edge)) {
+		              dfs.predArc(source) != graph.oppositeArc(arc)) {
 		            return false;
+		          }
 		          dfs.processNextArc();
+		        }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Check that the given undirected graph is tree.
+		  /// \brief Check whether an undirected graph is tree.
 		  ///
 		  /// Check that the given undirected graph is tree.
 		  /// \param graph The undirected graph.
-		  /// \return \c true when the graph is acyclic and connected.
+		  /// This function checks whether the given undirected graph is tree.
 		  /// \return \c true if the graph is acyclic and connected.
 		  /// \see acyclic(), connected()
 		  template <typename Graph>
 		  bool tree(const Graph& graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::Arc Arc;
 		    if (NodeIt(graph) == INVALID) return true;
 		    Dfs<Graph> dfs(graph);
 		    dfs.init();
 		    dfs.addSource(NodeIt(graph));
 		    while (!dfs.emptyQueue()) {
 		      Arc edge = dfs.nextArc();
 		      Node source = graph.source(edge);
-		      Node target = graph.target(edge);
+		      Arc arc = dfs.nextArc();
 		      Node source = graph.source(arc);
 		      Node target = graph.target(arc);
 		      if (dfs.reached(target) &&
-		          dfs.predArc(source) != graph.oppositeArc(edge)) {
+		          dfs.predArc(source) != graph.oppositeArc(arc)) {
 		        return false;
+		      }
 		      dfs.processNextArc();
+		    }
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        return false;
+		      }
+		    }
 		    return true;
+		  }
 		  namespace _connectivity_bits {
 		    template <typename Digraph>
 		    class BipartiteVisitor : public BfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Node Node;
 		      BipartiteVisitor(const Digraph& graph, bool& bipartite)
 		        : _graph(graph), _part(graph), _bipartite(bipartite) {}
 		      void start(const Node& node) {
 		        _part[node] = true;
+		      }
 		      void discover(const Arc& edge) {
 		        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
+		      }
 		      void examine(const Arc& edge) {
 		        _bipartite = _bipartite &&
 		          _part[_graph.target(edge)] != _part[_graph.source(edge)];
+		      }
 		    private:
 		      const Digraph& _graph;
 		      typename Digraph::template NodeMap<bool> _part;
 		      bool& _bipartite;
 		    };
 		    template <typename Digraph, typename PartMap>
 		    class BipartitePartitionsVisitor : public BfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Node Node;
 		      BipartitePartitionsVisitor(const Digraph& graph,
 		                                 PartMap& part, bool& bipartite)
 		        : _graph(graph), _part(part), _bipartite(bipartite) {}
 		      void start(const Node& node) {
 		        _part.set(node, true);
+		      }
 		      void discover(const Arc& edge) {
 		        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
+		      }
 		      void examine(const Arc& edge) {
 		        _bipartite = _bipartite &&
 		          _part[_graph.target(edge)] != _part[_graph.source(edge)];
+		      }
 		    private:
 		      const Digraph& _graph;
 		      PartMap& _part;
 		      bool& _bipartite;
 		    };
+		  }
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Check if the given undirected graph is bipartite or not
+		  /// \brief Check whether an undirected graph is bipartite.
 		  ///
 		  /// The function checks if the given undirected \c graph graph is bipartite
 		  /// or not. The \ref Bfs algorithm is used to calculate the result.
 		  /// \param graph The undirected graph.
 		  /// \return \c true if \c graph is bipartite, \c false otherwise.
-		  /// \sa bipartitePartitions
+		  /// The function checks whether the given undirected graph is bipartite.
 		  /// \return \c true if the graph is bipartite.
 		  ///
 		  /// \see bipartitePartitions()
 		  template<typename Graph>
-		  inline bool bipartite(const Graph &graph){
 		  bool bipartite(const Graph &graph){
 		    using namespace _connectivity_bits;
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::ArcIt ArcIt;
 		    bool bipartite = true;
 		    BipartiteVisitor<Graph>
 		      visitor(graph, bipartite);
 		    BfsVisit<Graph, BipartiteVisitor<Graph> >
 		      bfs(graph, visitor);
 		    bfs.init();
 		    for(NodeIt it(graph); it != INVALID; ++it) {
 		      if(!bfs.reached(it)){
 		        bfs.addSource(it);
 		        while (!bfs.emptyQueue()) {
 		          bfs.processNextNode();
 		          if (!bipartite) return false;
+		        }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Check if the given undirected graph is bipartite or not
+		  /// \brief Find the bipartite partitions of an undirected graph.
 		  ///
 		  /// The function checks if the given undirected graph is bipartite
 		  /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
 		  /// During the execution, the \c partMap will be set as the two
 		  /// partitions of the graph.
 		  /// This function checks whether the given undirected graph is bipartite
 		  /// and gives back the bipartite partitions.
 		  ///
 		  /// \image html bipartite_partitions.png
 		  /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
 		  ///
 		  /// \param graph The undirected graph.
 		  /// \retval partMap A writable bool map of nodes. It will be set as the
 		  /// two partitions of the graph.
-		  /// \return \c true if \c graph is bipartite, \c false otherwise.
+		  /// \retval partMap A writable node map of \c bool (or convertible) value
 		  /// type. The values will be set to \c true for one component and
 		  /// \c false for the other one.
 		  /// \return \c true if the graph is bipartite, \c false otherwise.
 		  ///
 		  /// \see bipartite()
 		  template<typename Graph, typename NodeMap>
-		  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
 		  bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
 		    using namespace _connectivity_bits;
 		    checkConcept<concepts::Graph, Graph>();
 		    checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::ArcIt ArcIt;
 		    bool bipartite = true;
 		    BipartitePartitionsVisitor<Graph, NodeMap>
 		      visitor(graph, partMap, bipartite);
 		    BfsVisit<Graph, BipartitePartitionsVisitor<Graph, NodeMap> >
 		      bfs(graph, visitor);
 		    bfs.init();
 		    for(NodeIt it(graph); it != INVALID; ++it) {
 		      if(!bfs.reached(it)){
 		        bfs.addSource(it);
 		        while (!bfs.emptyQueue()) {
 		          bfs.processNextNode();
 		          if (!bipartite) return false;
+		        }
+		      }
+		    }
 		    return true;
+		  }
-		  /// \brief Returns true when there are not loop edges in the graph.
+		  /// \ingroup graph_properties
 		  ///
 		  /// Returns true when there are not loop edges in the graph.
 		  template <typename Digraph>
 		  bool loopFree(const Digraph& digraph) {
 		    for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {
-		      if (digraph.source(it) == digraph.target(it)) return false;
+		  /// \brief Check whether the given graph contains no loop arcs/edges.
 		  ///
 		  /// This function returns \c true if there are no loop arcs/edges in
 		  /// the given graph. It works for both directed and undirected graphs.
 		  template <typename Graph>
 		  bool loopFree(const Graph& graph) {
 		    for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {
 		      if (graph.source(it) == graph.target(it)) return false;
+		    }
 		    return true;
+		  }
-		  /// \brief Returns true when there are not parallel edges in the graph.
+		  /// \ingroup graph_properties
 		  ///
 		  /// Returns true when there are not parallel edges in the graph.
 		  template <typename Digraph>
 		  bool parallelFree(const Digraph& digraph) {
 		    typename Digraph::template NodeMap<bool> reached(digraph, false);
 		    for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
 		      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
 		        if (reached[digraph.target(a)]) return false;
 		        reached.set(digraph.target(a), true);
 		  /// \brief Check whether the given graph contains no parallel arcs/edges.
 		  ///
 		  /// This function returns \c true if there are no parallel arcs/edges in
 		  /// the given graph. It works for both directed and undirected graphs.
 		  template <typename Graph>
 		  bool parallelFree(const Graph& graph) {
 		    typename Graph::template NodeMap<int> reached(graph, 0);
 		    int cnt = 1;
 		    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
 		      for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
 		        if (reached[graph.target(a)] == cnt) return false;
 		        reached[graph.target(a)] = cnt;
+		      }
 		      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
 		        reached.set(digraph.target(a), false);
+		      }
+		      ++cnt;
+		    }
 		    return true;
+		  }
 		  /// \brief Returns true when there are not loop edges and parallel
 		  /// edges in the graph.
 		  /// \ingroup graph_properties
 		  ///
 		  /// Returns true when there are not loop edges and parallel edges in
 		  /// the graph.
 		  template <typename Digraph>
 		  bool simpleDigraph(const Digraph& digraph) {
 		    typename Digraph::template NodeMap<bool> reached(digraph, false);
 		    for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
 		      reached.set(n, true);
 		      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
 		        if (reached[digraph.target(a)]) return false;
 		        reached.set(digraph.target(a), true);
 		  /// \brief Check whether the given graph is simple.
 		  ///
 		  /// This function returns \c true if the given graph is simple, i.e.
 		  /// it contains no loop arcs/edges and no parallel arcs/edges.
 		  /// The function works for both directed and undirected graphs.
 		  /// \see loopFree(), parallelFree()
 		  template <typename Graph>
 		  bool simpleGraph(const Graph& graph) {
 		    typename Graph::template NodeMap<int> reached(graph, 0);
 		    int cnt = 1;
 		    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
 		      reached[n] = cnt;
 		      for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
 		        if (reached[graph.target(a)] == cnt) return false;
 		        reached[graph.target(a)] = cnt;
+		      }
 		      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
 		        reached.set(digraph.target(a), false);
+		      }
 		      reached.set(n, false);
 		      ++cnt;
+		    }
 		    return true;
+		  }
 		} //namespace lemon
 		#endif //LEMON_CONNECTIVITY_H

lemon/edge_set.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_EDGE_SET_H
 		#define LEMON_EDGE_SET_H
 		#include <lemon/core.h>
 		#include <lemon/bits/edge_set_extender.h>
-		/// \ingroup semi_adaptors
+		/// \ingroup graphs
 		/// \file
 		/// \brief ArcSet and EdgeSet classes.
 		///
 		/// Graphs which use another graph's node-set as own.
 		namespace lemon {
 		  template <typename GR>
 		  class ListArcSetBase {
 		  public:
 		    typedef typename GR::Node Node;
 		    typedef typename GR::NodeIt NodeIt;
 		  protected:
 		    struct NodeT {
 		      int first_out, first_in;
 		      NodeT() : first_out(-1), first_in(-1) {}
 		    };
 		    typedef typename ItemSetTraits<GR, Node>::
 		    template Map<NodeT>::Type NodesImplBase;
 		    NodesImplBase* _nodes;
 		    struct ArcT {
 		      Node source, target;
 		      int next_out, next_in;
 		      int prev_out, prev_in;
 		      ArcT() : prev_out(-1), prev_in(-1) {}
 		    };
 		    std::vector<ArcT> arcs;
 		    int first_arc;
 		    int first_free_arc;
 		    const GR* _graph;
 		    void initalize(const GR& graph, NodesImplBase& nodes) {
 		      _graph = &graph;
 		      _nodes = &nodes;
+		    }
 		  public:
 		    class Arc {
 		      friend class ListArcSetBase<GR>;
@@ -185,97 +185,97 @@
 		    void nextIn(Arc& arc) const {
 		      arc.id = arcs[arc.id].next_in;
+		    }
 		    int id(const Node& node) const { return _graph->id(node); }
 		    int id(const Arc& arc) const { return arc.id; }
 		    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
 		    Arc arcFromId(int ix) const { return Arc(ix); }
 		    int maxNodeId() const { return _graph->maxNodeId(); };
 		    int maxArcId() const { return arcs.size() - 1; }
 		    Node source(const Arc& arc) const { return arcs[arc.id].source;}
 		    Node target(const Arc& arc) const { return arcs[arc.id].target;}
 		    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const {
 		      return _graph->notifier(Node());
+		    }
 		    template <typename V>
 		    class NodeMap : public GR::template NodeMap<V> {
 		      typedef typename GR::template NodeMap<V> Parent;
 		    public:
 		      explicit NodeMap(const ListArcSetBase<GR>& arcset)
 		        : Parent(*arcset._graph) {}
 		      NodeMap(const ListArcSetBase<GR>& arcset, const V& value)
 		        : Parent(*arcset._graph, value) {}
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
-		  /// \ingroup semi_adaptors
+		  /// \ingroup graphs
 		  ///
 		  /// \brief Digraph using a node set of another digraph or graph and
 		  /// an own arc set.
 		  ///
 		  /// This structure can be used to establish another directed graph
 		  /// over a node set of an existing one. This class uses the same
 		  /// Node type as the underlying graph, and each valid node of the
 		  /// original graph is valid in this arc set, therefore the node
 		  /// objects of the original graph can be used directly with this
 		  /// class. The node handling functions (id handling, observing, and
 		  /// iterators) works equivalently as in the original graph.
 		  ///
 		  /// This implementation is based on doubly-linked lists, from each
 		  /// node the outgoing and the incoming arcs make up lists, therefore
 		  /// one arc can be erased in constant time. It also makes possible,
 		  /// that node can be removed from the underlying graph, in this case
 		  /// all arcs incident to the given node is erased from the arc set.
 		  ///
 		  /// \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> > {
 		    typedef ArcSetExtender<ListArcSetBase<GR> > Parent;
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::NodesImplBase NodesImplBase;
 		    void eraseNode(const Node& node) {
 		      Arc arc;
 		      Parent::firstOut(arc, node);
 		      while (arc != INVALID ) {
 		        erase(arc);
 		        Parent::firstOut(arc, node);
+		      }
 		      Parent::firstIn(arc, node);
 		      while (arc != INVALID ) {
 		        erase(arc);
 		        Parent::firstIn(arc, node);
@@ -609,97 +609,97 @@
 		    static int id(Arc e) { return e.id; }
 		    static int id(Edge e) { return e.id; }
 		    Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
 		    static Arc arcFromId(int id) { return Arc(id);}
 		    static Edge edgeFromId(int id) { return Edge(id);}
 		    int maxNodeId() const { return _graph->maxNodeId(); };
 		    int maxEdgeId() const { return arcs.size() / 2 - 1; }
 		    int maxArcId() const { return arcs.size()-1; }
 		    Node source(Arc e) const { return arcs[e.id ^ 1].target; }
 		    Node target(Arc e) const { return arcs[e.id].target; }
 		    Node u(Edge e) const { return arcs[2 * e.id].target; }
 		    Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
 		    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const {
 		      return _graph->notifier(Node());
+		    }
 		    template <typename V>
 		    class NodeMap : public GR::template NodeMap<V> {
 		      typedef typename GR::template NodeMap<V> Parent;
 		    public:
 		      explicit NodeMap(const ListEdgeSetBase<GR>& arcset)
 		        : Parent(*arcset._graph) {}
 		      NodeMap(const ListEdgeSetBase<GR>& arcset, const V& value)
 		        : Parent(*arcset._graph, value) {}
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
-		  /// \ingroup semi_adaptors
+		  /// \ingroup graphs
 		  ///
 		  /// \brief Graph using a node set of another digraph or graph and an
 		  /// own edge set.
 		  ///
 		  /// This structure can be used to establish another graph over a
 		  /// node set of an existing one. This class uses the same Node type
 		  /// as the underlying graph, and each valid node of the original
 		  /// graph is valid in this arc set, therefore the node objects of
 		  /// the original graph can be used directly with this class. The
 		  /// node handling functions (id handling, observing, and iterators)
 		  /// works equivalently as in the original graph.
 		  ///
 		  /// This implementation is based on doubly-linked lists, from each
 		  /// node the incident edges make up lists, therefore one edge can be
 		  /// erased in constant time. It also makes possible, that node can
 		  /// be removed from the underlying graph, in this case all edges
 		  /// incident to the given node is erased from the arc set.
 		  ///
 		  /// \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>
 		  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
 		    typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::Edge Edge;
 		    typedef typename Parent::NodesImplBase NodesImplBase;
 		    void eraseNode(const Node& node) {
 		      Arc arc;
 		      Parent::firstOut(arc, node);
 		      while (arc != INVALID ) {
 		        erase(arc);
 		        Parent::firstOut(arc, node);
+		      }
+		    }
 		    void clearNodes() {
@@ -868,97 +868,97 @@
 		    void nextIn(Arc& arc) const {
 		      arc.id = arcs[arc.id].next_in;
+		    }
 		    int id(const Node& node) const { return _graph->id(node); }
 		    int id(const Arc& arc) const { return arc.id; }
 		    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
 		    Arc arcFromId(int ix) const { return Arc(ix); }
 		    int maxNodeId() const { return _graph->maxNodeId(); };
 		    int maxArcId() const { return arcs.size() - 1; }
 		    Node source(const Arc& arc) const { return arcs[arc.id].source;}
 		    Node target(const Arc& arc) const { return arcs[arc.id].target;}
 		    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const {
 		      return _graph->notifier(Node());
+		    }
 		    template <typename V>
 		    class NodeMap : public GR::template NodeMap<V> {
 		      typedef typename GR::template NodeMap<V> Parent;
 		    public:
 		      explicit NodeMap(const SmartArcSetBase<GR>& arcset)
 		        : Parent(*arcset._graph) { }
 		      NodeMap(const SmartArcSetBase<GR>& arcset, const V& value)
 		        : Parent(*arcset._graph, value) { }
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
-		  /// \ingroup semi_adaptors
+		  /// \ingroup graphs
 		  ///
 		  /// \brief Digraph using a node set of another digraph or graph and
 		  /// an own arc set.
 		  ///
 		  /// This structure can be used to establish another directed graph
 		  /// over a node set of an existing one. This class uses the same
 		  /// Node type as the underlying graph, and each valid node of the
 		  /// original graph is valid in this arc set, therefore the node
 		  /// objects of the original graph can be used directly with this
 		  /// class. The node handling functions (id handling, observing, and
 		  /// iterators) works equivalently as in the original graph.
 		  ///
 		  /// \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 implementation is slightly faster than the \c ListArcSet,
 		  /// because it uses continuous storage for arcs and it uses just
 		  /// single-linked lists for enumerate outgoing and incoming
 		  /// arcs. Therefore the arcs cannot be erased from the arc sets.
 		  ///
 		  /// \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> > {
 		    typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		  protected:
 		    typedef typename Parent::NodesImplBase NodesImplBase;
 		    void eraseNode(const Node& node) {
 		      if (typename Parent::InArcIt(*this, node) == INVALID &&
 		          typename Parent::OutArcIt(*this, node) == INVALID) {
 		        return;
+		      }
 		      throw typename NodesImplBase::Notifier::ImmediateDetach();
@@ -1212,97 +1212,97 @@
 		    static int id(Arc arc) { return arc.id; }
 		    static int id(Edge arc) { return arc.id; }
 		    Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
 		    static Arc arcFromId(int id) { return Arc(id); }
 		    static Edge edgeFromId(int id) { return Edge(id);}
 		    int maxNodeId() const { return _graph->maxNodeId(); };
 		    int maxArcId() const { return arcs.size() - 1; }
 		    int maxEdgeId() const { return arcs.size() / 2 - 1; }
 		    Node source(Arc e) const { return arcs[e.id ^ 1].target; }
 		    Node target(Arc e) const { return arcs[e.id].target; }
 		    Node u(Edge e) const { return arcs[2 * e.id].target; }
 		    Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
 		    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const {
 		      return _graph->notifier(Node());
+		    }
 		    template <typename V>
 		    class NodeMap : public GR::template NodeMap<V> {
 		      typedef typename GR::template NodeMap<V> Parent;
 		    public:
 		      explicit NodeMap(const SmartEdgeSetBase<GR>& arcset)
 		        : Parent(*arcset._graph) { }
 		      NodeMap(const SmartEdgeSetBase<GR>& arcset, const V& value)
 		        : Parent(*arcset._graph, value) { }
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
-		  /// \ingroup semi_adaptors
+		  /// \ingroup graphs
 		  ///
 		  /// \brief Graph using a node set of another digraph or graph and an
 		  /// own edge set.
 		  ///
 		  /// This structure can be used to establish another graph over a
 		  /// node set of an existing one. This class uses the same Node type
 		  /// as the underlying graph, and each valid node of the original
 		  /// graph is valid in this arc set, therefore the node objects of
 		  /// the original graph can be used directly with this class. The
 		  /// node handling functions (id handling, observing, and iterators)
 		  /// works equivalently as in the original graph.
 		  ///
 		  /// \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 implementation is slightly faster than the \c ListEdgeSet,
 		  /// because it uses continuous storage for edges and it uses just
 		  /// single-linked lists for enumerate incident edges. Therefore the
 		  /// edges cannot be erased from the edge sets.
 		  ///
 		  /// \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> > {
 		    typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::Edge Edge;
 		  protected:
 		    typedef typename Parent::NodesImplBase NodesImplBase;
 		    void eraseNode(const Node& node) {
 		      if (typename Parent::IncEdgeIt(*this, node) == INVALID) {
 		        return;
+		      }
 		      throw typename NodesImplBase::Notifier::ImmediateDetach();

lemon/euler.h

Show inline comments

@@ -199,89 +199,89 @@
+		    }
 		    ///Arc conversion
 		    operator Arc() const { return euler.empty()?INVALID:euler.front(); }
 		    ///Edge conversion
 		    operator Edge() const { return euler.empty()?INVALID:euler.front(); }
 		    ///Compare with \c INVALID
 		    bool operator==(Invalid) const { return euler.empty(); }
 		    ///Compare with \c INVALID
 		    bool operator!=(Invalid) const { return !euler.empty(); }
 		    ///Next arc of the tour
 		    ///Next arc of the tour
 		    ///
 		    EulerIt &operator++() {
 		      Node s=g.target(euler.front());
 		      euler.pop_front();
 		      typename std::list<Arc>::iterator next=euler.begin();
 		      while(narc[s]!=INVALID) {
 		        while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s];
 		        if(narc[s]==INVALID) break;
 		        else {
 		          euler.insert(next,narc[s]);
 		          visited[narc[s]]=true;
 		          Node n=g.target(narc[s]);
 		          ++narc[s];
 		          s=n;
+		        }
+		      }
 		      return *this;
+		    }
 		    ///Postfix incrementation
 		    /// Postfix incrementation.
 		    ///
 		    ///\warning This incrementation returns an \c Arc (which converts to
 		    ///an \c Edge), not an \ref EulerIt, as one may expect.
 		    Arc operator++(int)
+		    {
 		      Arc e=*this;
 		      ++(*this);
 		      return e;
+		    }
 		  };
-		  ///Check if the given graph is \e Eulerian
 		  ///Check if the given graph is Eulerian
 		  /// \ingroup graph_properties
-		  ///This function checks if the given graph is \e Eulerian.
 		  ///This function checks if the given graph is Eulerian.
 		  ///It works for both directed and undirected graphs.
 		  ///
 		  ///By definition, a digraph is called \e Eulerian if
 		  ///and only if it is connected and the number of incoming and outgoing
 		  ///arcs are the same for each node.
 		  ///Similarly, an undirected graph is called \e Eulerian if
 		  ///and only if it is connected and the number of incident edges is even
 		  ///for each node.
 		  ///
 		  ///\note There are (di)graphs that are not Eulerian, but still have an
 		  /// Euler tour, since they may contain isolated nodes.
 		  ///
 		  ///\sa DiEulerIt, EulerIt
 		  template<typename GR>
 		#ifdef DOXYGEN
 		  bool
 		#else
 		  typename enable_if<UndirectedTagIndicator<GR>,bool>::type
 		  eulerian(const GR &g)
+		  {
 		    for(typename GR::NodeIt n(g);n!=INVALID;++n)
 		      if(countIncEdges(g,n)%2) return false;
 		    return connected(g);
+		  }
 		  template<class GR>
 		  typename disable_if<UndirectedTagIndicator<GR>,bool>::type
 		#endif
 		  eulerian(const GR &g)
+		  {
 		    for(typename GR::NodeIt n(g);n!=INVALID;++n)
 		      if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
 		    return connected(undirector(g));
+		  }
+		}
 		#endif

lemon/glpk.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_GLPK_H
 		#define LEMON_GLPK_H
 		///\file
 		///\brief Header of the LEMON-GLPK lp solver interface.
 		///\ingroup lp_group
 		#include <lemon/lp_base.h>
 		// forward declaration
-		#ifndef _GLP_PROB
+		#if !defined _GLP_PROB && !defined GLP_PROB
 		#define _GLP_PROB
-		typedef struct { double _prob; } glp_prob;
+		#define GLP_PROB
 		typedef struct { double _opaque_prob; } glp_prob;
 		/* LP/MIP problem object */
 		#endif
 		namespace lemon {
 		  /// \brief Base interface for the GLPK LP and MIP solver
 		  ///
 		  /// This class implements the common interface of the GLPK LP and MIP solver.
 		  /// \ingroup lp_group
 		  class GlpkBase : virtual public LpBase {
 		  protected:
 		    typedef glp_prob LPX;
 		    glp_prob* lp;
 		    GlpkBase();
 		    GlpkBase(const GlpkBase&);
 		    virtual ~GlpkBase();
 		  protected:
 		    virtual int _addCol();
 		    virtual int _addRow();
 		    virtual void _eraseCol(int i);
 		    virtual void _eraseRow(int i);
 		    virtual void _eraseColId(int i);
 		    virtual void _eraseRowId(int i);
 		    virtual void _getColName(int col, std::string& name) const;
 		    virtual void _setColName(int col, const std::string& name);
 		    virtual int _colByName(const std::string& name) const;
 		    virtual void _getRowName(int row, std::string& name) const;
 		    virtual void _setRowName(int row, const std::string& name);
 		    virtual int _rowByName(const std::string& name) const;
 		    virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e);
 		    virtual void _getRowCoeffs(int i, InsertIterator b) const;
 		    virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e);
 		    virtual void _getColCoeffs(int i, InsertIterator b) const;
 		    virtual void _setCoeff(int row, int col, Value value);
 		    virtual Value _getCoeff(int row, int col) const;

lemon/lemon.pc.in

Show inline comments

 		prefix=@prefix@
 		exec_prefix=@exec_prefix@
 		libdir=@libdir@
 		includedir=@includedir@
 		Name: @PACKAGE_NAME@
-		Description: Library of Efficient Models and Optimization in Networks
+		Description: Library for Efficient Modeling and Optimization in Networks
 		Version: @PACKAGE_VERSION@
 		Libs: -L${libdir} -lemon @GLPK_LIBS@ @CPLEX_LIBS@ @SOPLEX_LIBS@ @CLP_LIBS@ @CBC_LIBS@
 		Cflags: -I${includedir}

lemon/matching.h

Show inline comments

@@ -454,116 +454,116 @@
 		            if ((*_matching)[v] == INVALID && v != n) {
 		              (*_matching)[n] = a;
 		              (*_status)[n] = MATCHED;
 		              (*_matching)[v] = _graph.oppositeArc(a);
 		              (*_status)[v] = MATCHED;
 		              break;
+		            }
+		          }
+		        }
+		      }
+		    }
 		    /// \brief Initialize the matching from a map.
 		    ///
 		    /// This function initializes the matching from a \c bool valued edge
 		    /// map. This map should have the property that there are no two incident
 		    /// edges with \c true value, i.e. it really contains a matching.
 		    /// \return \c true if the map contains a matching.
 		    template <typename MatchingMap>
 		    bool matchingInit(const MatchingMap& matching) {
 		      createStructures();
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        (*_matching)[n] = INVALID;
 		        (*_status)[n] = UNMATCHED;
+		      }
 		      for(EdgeIt e(_graph); e!=INVALID; ++e) {
 		        if (matching[e]) {
 		          Node u = _graph.u(e);
 		          if ((*_matching)[u] != INVALID) return false;
 		          (*_matching)[u] = _graph.direct(e, true);
 		          (*_status)[u] = MATCHED;
 		          Node v = _graph.v(e);
 		          if ((*_matching)[v] != INVALID) return false;
 		          (*_matching)[v] = _graph.direct(e, false);
 		          (*_status)[v] = MATCHED;
+		        }
+		      }
 		      return true;
+		    }
 		    /// \brief Start Edmonds' algorithm
 		    ///
 		    /// This function runs the original Edmonds' algorithm.
 		    ///
-		    /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be
+		    /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
 		    /// called before using this function.
 		    void startSparse() {
 		      for(NodeIt n(_graph); n != INVALID; ++n) {
 		        if ((*_status)[n] == UNMATCHED) {
 		          (*_blossom_rep)[_blossom_set->insert(n)] = n;
 		          _tree_set->insert(n);
 		          (*_status)[n] = EVEN;
 		          processSparse(n);
+		        }
+		      }
+		    }
 		    /// \brief Start Edmonds' algorithm with a heuristic improvement
 		    /// for dense graphs
 		    ///
 		    /// This function runs Edmonds' algorithm with a heuristic of postponing
 		    /// shrinks, therefore resulting in a faster algorithm for dense graphs.
 		    ///
-		    /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be
+		    /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
 		    /// called before using this function.
 		    void startDense() {
 		      for(NodeIt n(_graph); n != INVALID; ++n) {
 		        if ((*_status)[n] == UNMATCHED) {
 		          (*_blossom_rep)[_blossom_set->insert(n)] = n;
 		          _tree_set->insert(n);
 		          (*_status)[n] = EVEN;
 		          processDense(n);
+		        }
+		      }
+		    }
 		    /// \brief Run Edmonds' algorithm
 		    ///
 		    /// This function runs Edmonds' algorithm. An additional heuristic of
 		    /// postponing shrinks is used for relatively dense graphs
 		    /// (for which <tt>m>=2*n</tt> holds).
 		    void run() {
 		      if (countEdges(_graph) < 2 * countNodes(_graph)) {
 		        greedyInit();
 		        startSparse();
 		      } else {
 		        init();
 		        startDense();
+		      }
+		    }
 		    /// @}
 		    /// \name Primal Solution
 		    /// Functions to get the primal solution, i.e. the maximum matching.
 		    /// @{
 		    /// \brief Return the size (cardinality) of the matching.
 		    ///
 		    /// This function returns the size (cardinality) of the current matching.
 		    /// After run() it returns the size of the maximum matching in the graph.
 		    int matchingSize() const {
 		      int size = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        if ((*_matching)[n] != INVALID) {
 		          ++size;
+		        }
+		      }
 		      return size / 2;
+		    }

lemon/network_simplex.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_NETWORK_SIMPLEX_H
 		#define LEMON_NETWORK_SIMPLEX_H
-		/// \ingroup min_cost_flow
+		/// \ingroup min_cost_flow_algs
 		///
 		/// \file
 		/// \brief Network Simplex algorithm for finding a minimum cost flow.
 		#include <vector>
 		#include <limits>
 		#include <algorithm>
 		#include <lemon/core.h>
 		#include <lemon/math.h>
 		namespace lemon {
-		  /// \addtogroup min_cost_flow
+		  /// \addtogroup min_cost_flow_algs
 		  /// @{
 		  /// \brief Implementation of the primal Network Simplex algorithm
 		  /// for finding a \ref min_cost_flow "minimum cost flow".
 		  ///
 		  /// \ref NetworkSimplex implements the primal Network Simplex algorithm
 		  /// for finding a \ref min_cost_flow "minimum cost flow".
 		  /// This algorithm is a specialized version of the linear programming
 		  /// simplex method directly for the minimum cost flow problem.
 		  /// It is one of the most efficient solution methods.
 		  ///
 		  /// In general this class is the fastest implementation available
 		  /// in LEMON for the minimum cost flow problem.
 		  /// Moreover it supports both directions of the supply/demand inequality
 		  /// constraints. For more information see \ref SupplyType.
 		  ///
 		  /// Most of the parameters of the problem (except for the digraph)
 		  /// can be given using separate functions, and the algorithm can be
 		  /// executed using the \ref run() function. If some parameters are not
 		  /// specified, then default values will be used.
 		  ///
 		  /// \tparam GR The digraph type the algorithm runs on.
 		  /// \tparam V The value type used for flow amounts, capacity bounds
 		  /// and supply values in the algorithm. By default it is \c int.
 		  /// \tparam C The value type used for costs and potentials in the
 		  /// algorithm. By default it is the same as \c V.
 		  ///
 		  /// \warning Both value types must be signed and all input data must
 		  /// be integer.
 		  ///
 		  /// \note %NetworkSimplex provides five different pivot rule
 		  /// implementations, from which the most efficient one is used
 		  /// by default. For more information see \ref PivotRule.
 		  template <typename GR, typename V = int, typename C = V>
 		  class NetworkSimplex
+		  {
 		  public:
 		    /// The type of the flow amounts, capacity bounds and supply values
 		    typedef V Value;
 		    /// The type of the arc costs
 		    typedef C Cost;
 		  public:
 		    /// \brief Problem type constants for the \c run() function.
 		    ///
 		    /// Enum type containing the problem type constants that can be
 		    /// returned by the \ref run() function of the algorithm.
 		    enum ProblemType {
 		      /// The problem has no feasible solution (flow).
 		      INFEASIBLE,
 		      /// The problem has optimal solution (i.e. it is feasible and
 		      /// bounded), and the algorithm has found optimal flow and node
 		      /// potentials (primal and dual solutions).
 		      OPTIMAL,
 		      /// The objective function of the problem is unbounded, i.e.
 		      /// there is a directed cycle having negative total cost and
 		      /// infinite upper bound.
 		      UNBOUNDED
 		    };
 		    /// \brief Constants for selecting the type of the supply constraints.
 		    ///
 		    /// Enum type containing constants for selecting the supply type,
 		    /// i.e. the direction of the inequalities in the supply/demand
 		    /// constraints of the \ref min_cost_flow "minimum cost flow problem".
 		    ///
 		    /// The default supply type is \c GEQ, since this form is supported
 		    /// by other minimum cost flow algorithms and the \ref Circulation
 		    /// algorithm, as well.
 		    /// The \c LEQ problem type can be selected using the \ref supplyType()
 		    /// function.
 		    ///
-		    /// Note that the equality form is a special case of both supply types.
+		    /// The default supply type is \c GEQ, the \c LEQ type can be
 		    /// selected using \ref supplyType().
 		    /// The equality form is a special case of both supply types.
 		    enum SupplyType {
 		      /// This option means that there are <em>"greater or equal"</em>
 		      /// supply/demand constraints in the definition, i.e. the exact
 		      /// formulation of the problem is the following.
 		      /**
 		          \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		          \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
 		              sup(u) \quad \forall u\in V \f]
 		          \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		      */
 		      /// It means that the total demand must be greater or equal to the
 		      /// total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
 		      /// negative) and all the supplies have to be carried out from
 		      /// the supply nodes, but there could be demands that are not
-		      /// satisfied.
+		      /// supply/demand constraints in the definition of the problem.
 		      GEQ,
 		      /// It is just an alias for the \c GEQ option.
 		      CARRY_SUPPLIES = GEQ,
 		      /// This option means that there are <em>"less or equal"</em>
 		      /// supply/demand constraints in the definition, i.e. the exact
 		      /// formulation of the problem is the following.
 		      /**
 		          \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		          \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
 		              sup(u) \quad \forall u\in V \f]
 		          \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		      */
 		      /// It means that the total demand must be less or equal to the
 		      /// total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
 		      /// positive) and all the demands have to be satisfied, but there
 		      /// could be supplies that are not carried out from the supply
 		      /// nodes.
 		      LEQ,
 		      /// It is just an alias for the \c LEQ option.
 		      SATISFY_DEMANDS = LEQ
 		      /// supply/demand constraints in the definition of the problem.
 		      LEQ
 		    };
 		    /// \brief Constants for selecting the pivot rule.
 		    ///
 		    /// Enum type containing constants for selecting the pivot rule for
 		    /// the \ref run() function.
 		    ///
 		    /// \ref NetworkSimplex provides five different pivot rule
 		    /// implementations that significantly affect the running time
 		    /// of the algorithm.
 		    /// By default \ref BLOCK_SEARCH "Block Search" is used, which
 		    /// proved to be the most efficient and the most robust on various
 		    /// test inputs according to our benchmark tests.
 		    /// However another pivot rule can be selected using the \ref run()
 		    /// function with the proper parameter.
 		    enum PivotRule {
 		      /// The First Eligible pivot rule.
 		      /// The next eligible arc is selected in a wraparound fashion
 		      /// in every iteration.
 		      FIRST_ELIGIBLE,
 		      /// The Best Eligible pivot rule.
 		      /// The best eligible arc is selected in every iteration.
 		      BEST_ELIGIBLE,
 		      /// The Block Search pivot rule.
 		      /// A specified number of arcs are examined in every iteration
 		      /// in a wraparound fashion and the best eligible arc is selected
 		      /// from this block.
 		      BLOCK_SEARCH,
 		      /// The Candidate List pivot rule.
 		      /// In a major iteration a candidate list is built from eligible arcs
 		      /// in a wraparound fashion and in the following minor iterations
 		      /// the best eligible arc is selected from this list.
 		      CANDIDATE_LIST,
 		      /// The Altering Candidate List pivot rule.
 		      /// It is a modified version of the Candidate List method.
 		      /// It keeps only the several best eligible arcs from the former
 		      /// candidate list and extends this list in every iteration.
 		      ALTERING_LIST
 		    };
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef std::vector<Arc> ArcVector;
 		    typedef std::vector<Node> NodeVector;
 		    typedef std::vector<int> IntVector;
 		    typedef std::vector<bool> BoolVector;
 		    typedef std::vector<Value> ValueVector;
 		    typedef std::vector<Cost> CostVector;
 		    // State constants for arcs
 		    enum ArcStateEnum {
 		      STATE_UPPER = -1,
 		      STATE_TREE  =  0,
 		      STATE_LOWER =  1
 		    };
 		  private:
 		    // Data related to the underlying digraph
 		    const GR &_graph;
 		    int _node_num;
 		    int _arc_num;
 		    int _all_arc_num;
 		    int _search_arc_num;
 		    // Parameters of the problem
 		    bool _have_lower;
 		    SupplyType _stype;
 		    Value _sum_supply;
 		    // Data structures for storing the digraph
 		    IntNodeMap _node_id;
 		    IntArcMap _arc_id;
 		    IntVector _source;
 		    IntVector _target;
 		    // Node and arc data
 		    ValueVector _lower;
 		    ValueVector _upper;
 		    ValueVector _cap;
 		    CostVector _cost;
 		    ValueVector _supply;
 		    ValueVector _flow;
 		    CostVector _pi;
 		    // Data for storing the spanning tree structure
 		    IntVector _parent;
 		    IntVector _pred;
 		    IntVector _thread;
 		    IntVector _rev_thread;
 		    IntVector _succ_num;
 		    IntVector _last_succ;
 		    IntVector _dirty_revs;
 		    BoolVector _forward;
 		    IntVector _state;
 		    int _root;
 		    // Temporary data used in the current pivot iteration
 		    int in_arc, join, u_in, v_in, u_out, v_out;
 		    int first, second, right, last;
 		    int stem, par_stem, new_stem;
 		    Value delta;
 		  public:
 		    /// \brief Constant for infinite upper bounds (capacities).
 		    ///
 		    /// Constant for infinite upper bounds (capacities).
 		    /// It is \c std::numeric_limits<Value>::infinity() if available,
 		    /// \c std::numeric_limits<Value>::max() otherwise.
 		    const Value INF;
 		  private:
 		    // Implementation of the First Eligible pivot rule
 		    class FirstEligiblePivotRule
+		    {
 		    private:
 		      // References to the NetworkSimplex class
 		      const IntVector  &_source;
 		      const IntVector  &_target;
 		      const CostVector &_cost;
 		      const IntVector  &_state;
 		      const CostVector &_pi;
 		      int &_in_arc;
-		      int _arc_num;
+		      int _search_arc_num;
 		      // Pivot rule data
 		      int _next_arc;
 		    public:
 		      // Constructor
 		      FirstEligiblePivotRule(NetworkSimplex &ns) :
 		        _source(ns._source), _target(ns._target),
 		        _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-		        _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
+		        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
 		        _next_arc(0)
 		      {}
 		      // Find next entering arc
 		      bool findEnteringArc() {
 		        Cost c;
-		        for (int e = _next_arc; e < _arc_num; ++e) {
+		        for (int e = _next_arc; e < _search_arc_num; ++e) {
 		          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (c < 0) {
 		            _in_arc = e;
 		            _next_arc = e + 1;
 		            return true;
+		          }
+		        }
 		        for (int e = 0; e < _next_arc; ++e) {
 		          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (c < 0) {
 		            _in_arc = e;
 		            _next_arc = e + 1;
 		            return true;
+		          }
+		        }
 		        return false;
+		      }
 		    }; //class FirstEligiblePivotRule
 		    // Implementation of the Best Eligible pivot rule
 		    class BestEligiblePivotRule
+		    {
 		    private:
 		      // References to the NetworkSimplex class
 		      const IntVector  &_source;
 		      const IntVector  &_target;
 		      const CostVector &_cost;
 		      const IntVector  &_state;
 		      const CostVector &_pi;
 		      int &_in_arc;
-		      int _arc_num;
+		      int _search_arc_num;
 		    public:
 		      // Constructor
 		      BestEligiblePivotRule(NetworkSimplex &ns) :
 		        _source(ns._source), _target(ns._target),
 		        _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-		        _in_arc(ns.in_arc), _arc_num(ns._arc_num)
+		        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num)
 		      {}
 		      // Find next entering arc
 		      bool findEnteringArc() {
 		        Cost c, min = 0;
-		        for (int e = 0; e < _arc_num; ++e) {
+		        for (int e = 0; e < _search_arc_num; ++e) {
 		          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (c < min) {
 		            min = c;
 		            _in_arc = e;
+		          }
+		        }
 		        return min < 0;
+		      }
 		    }; //class BestEligiblePivotRule
 		    // Implementation of the Block Search pivot rule
 		    class BlockSearchPivotRule
+		    {
 		    private:
 		      // References to the NetworkSimplex class
 		      const IntVector  &_source;
 		      const IntVector  &_target;
 		      const CostVector &_cost;
 		      const IntVector  &_state;
 		      const CostVector &_pi;
 		      int &_in_arc;
-		      int _arc_num;
+		      int _search_arc_num;
 		      // Pivot rule data
 		      int _block_size;
 		      int _next_arc;
 		    public:
 		      // Constructor
 		      BlockSearchPivotRule(NetworkSimplex &ns) :
 		        _source(ns._source), _target(ns._target),
 		        _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-		        _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
+		        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
 		        _next_arc(0)
+		      {
 		        // The main parameters of the pivot rule
-		        const double BLOCK_SIZE_FACTOR = 2.0;
+		        const double BLOCK_SIZE_FACTOR = 0.5;
 		        const int MIN_BLOCK_SIZE = 10;
 		        _block_size = std::max( int(BLOCK_SIZE_FACTOR *
-		                                    std::sqrt(double(_arc_num))),
+		                                    std::sqrt(double(_search_arc_num))),
 		                                MIN_BLOCK_SIZE );
+		      }
 		      // Find next entering arc
 		      bool findEnteringArc() {
 		        Cost c, min = 0;
 		        int cnt = _block_size;
 		        int e, min_arc = _next_arc;
-		        for (e = _next_arc; e < _arc_num; ++e) {
+		        for (e = _next_arc; e < _search_arc_num; ++e) {
 		          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (c < min) {
 		            min = c;
 		            min_arc = e;
+		          }
 		          if (--cnt == 0) {
 		            if (min < 0) break;
 		            cnt = _block_size;
+		          }
+		        }
 		        if (min == 0 || cnt > 0) {
 		          for (e = 0; e < _next_arc; ++e) {
 		            c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		            if (c < min) {
 		              min = c;
 		              min_arc = e;
+		            }
 		            if (--cnt == 0) {
 		              if (min < 0) break;
 		              cnt = _block_size;
+		            }
+		          }
+		        }
 		        if (min >= 0) return false;
 		        _in_arc = min_arc;
 		        _next_arc = e;
 		        return true;
+		      }
 		    }; //class BlockSearchPivotRule
 		    // Implementation of the Candidate List pivot rule
 		    class CandidateListPivotRule
+		    {
 		    private:
 		      // References to the NetworkSimplex class
 		      const IntVector  &_source;
 		      const IntVector  &_target;
 		      const CostVector &_cost;
 		      const IntVector  &_state;
 		      const CostVector &_pi;
 		      int &_in_arc;
-		      int _arc_num;
+		      int _search_arc_num;
 		      // Pivot rule data
 		      IntVector _candidates;
 		      int _list_length, _minor_limit;
 		      int _curr_length, _minor_count;
 		      int _next_arc;
 		    public:
 		      /// Constructor
 		      CandidateListPivotRule(NetworkSimplex &ns) :
 		        _source(ns._source), _target(ns._target),
 		        _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-		        _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
+		        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
 		        _next_arc(0)
+		      {
 		        // The main parameters of the pivot rule
 		        const double LIST_LENGTH_FACTOR = 1.0;
 		        const int MIN_LIST_LENGTH = 10;
 		        const double MINOR_LIMIT_FACTOR = 0.1;
 		        const int MIN_MINOR_LIMIT = 3;
 		        _list_length = std::max( int(LIST_LENGTH_FACTOR *
-		                                     std::sqrt(double(_arc_num))),
+		                                     std::sqrt(double(_search_arc_num))),
 		                                 MIN_LIST_LENGTH );
 		        _minor_limit = std::max( int(MINOR_LIMIT_FACTOR * _list_length),
 		                                 MIN_MINOR_LIMIT );
 		        _curr_length = _minor_count = 0;
 		        _candidates.resize(_list_length);
+		      }
 		      /// Find next entering arc
 		      bool findEnteringArc() {
 		        Cost min, c;
 		        int e, min_arc = _next_arc;
 		        if (_curr_length > 0 && _minor_count < _minor_limit) {
 		          // Minor iteration: select the best eligible arc from the
 		          // current candidate list
 		          ++_minor_count;
 		          min = 0;
 		          for (int i = 0; i < _curr_length; ++i) {
 		            e = _candidates[i];
 		            c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		            if (c < min) {
 		              min = c;
 		              min_arc = e;
+		            }
 		            if (c >= 0) {
 		              _candidates[i--] = _candidates[--_curr_length];
+		            }
+		          }
 		          if (min < 0) {
 		            _in_arc = min_arc;
 		            return true;
+		          }
+		        }
 		        // Major iteration: build a new candidate list
 		        min = 0;
 		        _curr_length = 0;
-		        for (e = _next_arc; e < _arc_num; ++e) {
+		        for (e = _next_arc; e < _search_arc_num; ++e) {
 		          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (c < 0) {
 		            _candidates[_curr_length++] = e;
 		            if (c < min) {
 		              min = c;
 		              min_arc = e;
+		            }
 		            if (_curr_length == _list_length) break;
+		          }
+		        }
 		        if (_curr_length < _list_length) {
 		          for (e = 0; e < _next_arc; ++e) {
 		            c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		            if (c < 0) {
 		              _candidates[_curr_length++] = e;
 		              if (c < min) {
 		                min = c;
 		                min_arc = e;
+		              }
 		              if (_curr_length == _list_length) break;
+		            }
+		          }
+		        }
 		        if (_curr_length == 0) return false;
 		        _minor_count = 1;
 		        _in_arc = min_arc;
 		        _next_arc = e;
 		        return true;
+		      }
 		    }; //class CandidateListPivotRule
 		    // Implementation of the Altering Candidate List pivot rule
 		    class AlteringListPivotRule
+		    {
 		    private:
 		      // References to the NetworkSimplex class
 		      const IntVector  &_source;
 		      const IntVector  &_target;
 		      const CostVector &_cost;
 		      const IntVector  &_state;
 		      const CostVector &_pi;
 		      int &_in_arc;
-		      int _arc_num;
+		      int _search_arc_num;
 		      // Pivot rule data
 		      int _block_size, _head_length, _curr_length;
 		      int _next_arc;
 		      IntVector _candidates;
 		      CostVector _cand_cost;
 		      // Functor class to compare arcs during sort of the candidate list
 		      class SortFunc
+		      {
 		      private:
 		        const CostVector &_map;
 		      public:
 		        SortFunc(const CostVector &map) : _map(map) {}
 		        bool operator()(int left, int right) {
 		          return _map[left] > _map[right];
+		        }
 		      };
 		      SortFunc _sort_func;
 		    public:
 		      // Constructor
 		      AlteringListPivotRule(NetworkSimplex &ns) :
 		        _source(ns._source), _target(ns._target),
 		        _cost(ns._cost), _state(ns._state), _pi(ns._pi),
 		        _in_arc(ns.in_arc), _arc_num(ns._arc_num),
 		        _next_arc(0), _cand_cost(ns._arc_num), _sort_func(_cand_cost)
 		        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
 		        _next_arc(0), _cand_cost(ns._search_arc_num), _sort_func(_cand_cost)
+		      {
 		        // The main parameters of the pivot rule
 		        const double BLOCK_SIZE_FACTOR = 1.5;
 		        const int MIN_BLOCK_SIZE = 10;
 		        const double HEAD_LENGTH_FACTOR = 0.1;
 		        const int MIN_HEAD_LENGTH = 3;
 		        _block_size = std::max( int(BLOCK_SIZE_FACTOR *
-		                                    std::sqrt(double(_arc_num))),
+		                                    std::sqrt(double(_search_arc_num))),
 		                                MIN_BLOCK_SIZE );
 		        _head_length = std::max( int(HEAD_LENGTH_FACTOR * _block_size),
 		                                 MIN_HEAD_LENGTH );
 		        _candidates.resize(_head_length + _block_size);
 		        _curr_length = 0;
+		      }
 		      // Find next entering arc
 		      bool findEnteringArc() {
 		        // Check the current candidate list
 		        int e;
 		        for (int i = 0; i < _curr_length; ++i) {
 		          e = _candidates[i];
 		          _cand_cost[e] = _state[e] *
 		            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (_cand_cost[e] >= 0) {
 		            _candidates[i--] = _candidates[--_curr_length];
+		          }
+		        }
 		        // Extend the list
 		        int cnt = _block_size;
 		        int last_arc = 0;
 		        int limit = _head_length;
-		        for (int e = _next_arc; e < _arc_num; ++e) {
+		        for (int e = _next_arc; e < _search_arc_num; ++e) {
 		          _cand_cost[e] = _state[e] *
 		            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (_cand_cost[e] < 0) {
 		            _candidates[_curr_length++] = e;
 		            last_arc = e;
+		          }
 		          if (--cnt == 0) {
 		            if (_curr_length > limit) break;
 		            limit = 0;
 		            cnt = _block_size;
+		          }
+		        }
 		        if (_curr_length <= limit) {
 		          for (int e = 0; e < _next_arc; ++e) {
 		            _cand_cost[e] = _state[e] *
 		              (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		            if (_cand_cost[e] < 0) {
 		              _candidates[_curr_length++] = e;
 		              last_arc = e;
+		            }
 		            if (--cnt == 0) {
 		              if (_curr_length > limit) break;
 		              limit = 0;
 		              cnt = _block_size;
+		            }
+		          }
+		        }
 		        if (_curr_length == 0) return false;
 		        _next_arc = last_arc + 1;
 		        // Make heap of the candidate list (approximating a partial sort)
 		        make_heap( _candidates.begin(), _candidates.begin() + _curr_length,
 		                   _sort_func );
 		        // Pop the first element of the heap
 		        _in_arc = _candidates[0];
 		        pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
 		                  _sort_func );
 		        _curr_length = std::min(_head_length, _curr_length - 1);
 		        return true;
+		      }
 		    }; //class AlteringListPivotRule
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// The constructor of the class.
 		    ///
 		    /// \param graph The digraph the algorithm runs on.
 		    NetworkSimplex(const GR& graph) :
 		      _graph(graph), _node_id(graph), _arc_id(graph),
 		      INF(std::numeric_limits<Value>::has_infinity ?
 		          std::numeric_limits<Value>::infinity() :
 		          std::numeric_limits<Value>::max())
+		    {
 		      // Check the value types
 		      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
 		        "The flow type of NetworkSimplex must be signed");
 		      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
 		        "The cost type of NetworkSimplex must be signed");
 		      // Resize vectors
 		      _node_num = countNodes(_graph);
 		      _arc_num = countArcs(_graph);
 		      int all_node_num = _node_num + 1;
-		      int all_arc_num = _arc_num + _node_num;
+		      int max_arc_num = _arc_num + 2 * _node_num;
 		      _source.resize(all_arc_num);
 		      _target.resize(all_arc_num);
 		      _source.resize(max_arc_num);
 		      _target.resize(max_arc_num);
 		      _lower.resize(all_arc_num);
 		      _upper.resize(all_arc_num);
 		      _cap.resize(all_arc_num);
 		      _cost.resize(all_arc_num);
 		      _lower.resize(_arc_num);
 		      _upper.resize(_arc_num);
 		      _cap.resize(max_arc_num);
 		      _cost.resize(max_arc_num);
 		      _supply.resize(all_node_num);
-		      _flow.resize(all_arc_num);
+		      _flow.resize(max_arc_num);
 		      _pi.resize(all_node_num);
 		      _parent.resize(all_node_num);
 		      _pred.resize(all_node_num);
 		      _forward.resize(all_node_num);
 		      _thread.resize(all_node_num);
 		      _rev_thread.resize(all_node_num);
 		      _succ_num.resize(all_node_num);
 		      _last_succ.resize(all_node_num);
-		      _state.resize(all_arc_num);
+		      _state.resize(max_arc_num);
 		      // Copy the graph (store the arcs in a mixed order)
 		      int i = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _node_id[n] = i;
+		      }
 		      int k = std::max(int(std::sqrt(double(_arc_num))), 10);
 		      i = 0;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _arc_id[a] = i;
 		        _source[i] = _node_id[_graph.source(a)];
 		        _target[i] = _node_id[_graph.target(a)];
 		        if ((i += k) >= _arc_num) i = (i % k) + 1;
+		      }
 		      // Initialize maps
 		      for (int i = 0; i != _node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      for (int i = 0; i != _arc_num; ++i) {
 		        _lower[i] = 0;
 		        _upper[i] = INF;
 		        _cost[i] = 1;
+		      }
 		      _have_lower = false;
 		      _stype = GEQ;
+		    }
 		    /// \name Parameters
 		    /// The parameters of the algorithm can be specified using these
 		    /// functions.
 		    /// @{
 		    /// \brief Set the lower bounds on the arcs.
 		    ///
 		    /// This function sets the lower bounds on the arcs.
 		    /// If it is not used before calling \ref run(), the lower bounds
 		    /// will be set to zero on all arcs.
 		    ///
 		    /// \param map An arc map storing the lower bounds.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template <typename LowerMap>
 		    NetworkSimplex& lowerMap(const LowerMap& map) {
 		      _have_lower = true;
@@ -1024,143 +995,235 @@
 		    /// The \c Cost type of the algorithm must be convertible to the
 		    /// \c Value type of the map.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename PotentialMap>
 		    void potentialMap(PotentialMap &map) const {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        map.set(n, _pi[_node_id[n]]);
+		      }
+		    }
 		    /// @}
 		  private:
 		    // Initialize internal data structures
 		    bool init() {
 		      if (_node_num == 0) return false;
 		      // Check the sum of supply values
 		      _sum_supply = 0;
 		      for (int i = 0; i != _node_num; ++i) {
 		        _sum_supply += _supply[i];
+		      }
 		      if ( !((_stype == GEQ && _sum_supply <= 0) ||
 		             (_stype == LEQ && _sum_supply >= 0)) ) return false;
 		      // Remove non-zero lower bounds
 		      if (_have_lower) {
 		        for (int i = 0; i != _arc_num; ++i) {
 		          Value c = _lower[i];
 		          if (c >= 0) {
 		            _cap[i] = _upper[i] < INF ? _upper[i] - c : INF;
 		          } else {
 		            _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;
+		          }
 		          _supply[_source[i]] -= c;
 		          _supply[_target[i]] += c;
+		        }
 		      } else {
 		        for (int i = 0; i != _arc_num; ++i) {
 		          _cap[i] = _upper[i];
+		        }
+		      }
 		      // Initialize artifical cost
 		      Cost ART_COST;
 		      if (std::numeric_limits<Cost>::is_exact) {
-		        ART_COST = std::numeric_limits<Cost>::max() / 4 + 1;
+		        ART_COST = std::numeric_limits<Cost>::max() / 2 + 1;
 		      } else {
 		        ART_COST = std::numeric_limits<Cost>::min();
 		        for (int i = 0; i != _arc_num; ++i) {
 		          if (_cost[i] > ART_COST) ART_COST = _cost[i];
+		        }
 		        ART_COST = (ART_COST + 1) * _node_num;
+		      }
 		      // Initialize arc maps
 		      for (int i = 0; i != _arc_num; ++i) {
 		        _flow[i] = 0;
 		        _state[i] = STATE_LOWER;
+		      }
 		      // Set data for the artificial root node
 		      _root = _node_num;
 		      _parent[_root] = -1;
 		      _pred[_root] = -1;
 		      _thread[_root] = 0;
 		      _rev_thread[0] = _root;
 		      _succ_num[_root] = _node_num + 1;
 		      _last_succ[_root] = _root - 1;
 		      _supply[_root] = -_sum_supply;
-		      _pi[_root] = _sum_supply < 0 ? -ART_COST : ART_COST;
 		      _pi[_root] = 0;
 		      // Add artificial arcs and initialize the spanning tree data structure
 		      for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
 		        _parent[u] = _root;
 		        _pred[u] = e;
 		        _thread[u] = u + 1;
 		        _rev_thread[u + 1] = u;
 		        _succ_num[u] = 1;
 		        _last_succ[u] = u;
 		        _cost[e] = ART_COST;
 		        _cap[e] = INF;
 		        _state[e] = STATE_TREE;
 		        if (_supply[u] > 0 || (_supply[u] == 0 && _sum_supply <= 0)) {
 		          _flow[e] = _supply[u];
 		          _forward[u] = true;
 		          _pi[u] = -ART_COST + _pi[_root];
 		        } else {
 		          _flow[e] = -_supply[u];
 		          _forward[u] = false;
 		          _pi[u] = ART_COST + _pi[_root];
 		      if (_sum_supply == 0) {
 		        // EQ supply constraints
 		        _search_arc_num = _arc_num;
 		        _all_arc_num = _arc_num + _node_num;
 		        for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
 		          _parent[u] = _root;
 		          _pred[u] = e;
 		          _thread[u] = u + 1;
 		          _rev_thread[u + 1] = u;
 		          _succ_num[u] = 1;
 		          _last_succ[u] = u;
 		          _cap[e] = INF;
 		          _state[e] = STATE_TREE;
 		          if (_supply[u] >= 0) {
 		            _forward[u] = true;
 		            _pi[u] = 0;
 		            _source[e] = u;
 		            _target[e] = _root;
 		            _flow[e] = _supply[u];
 		            _cost[e] = 0;
 		          } else {
 		            _forward[u] = false;
 		            _pi[u] = ART_COST;
 		            _source[e] = _root;
 		            _target[e] = u;
 		            _flow[e] = -_supply[u];
 		            _cost[e] = ART_COST;
+		          }
+		        }
+		      }
 		      else if (_sum_supply > 0) {
 		        // LEQ supply constraints
 		        _search_arc_num = _arc_num + _node_num;
 		        int f = _arc_num + _node_num;
 		        for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
 		          _parent[u] = _root;
 		          _thread[u] = u + 1;
 		          _rev_thread[u + 1] = u;
 		          _succ_num[u] = 1;
 		          _last_succ[u] = u;
 		          if (_supply[u] >= 0) {
 		            _forward[u] = true;
 		            _pi[u] = 0;
 		            _pred[u] = e;
 		            _source[e] = u;
 		            _target[e] = _root;
 		            _cap[e] = INF;
 		            _flow[e] = _supply[u];
 		            _cost[e] = 0;
 		            _state[e] = STATE_TREE;
 		          } else {
 		            _forward[u] = false;
 		            _pi[u] = ART_COST;
 		            _pred[u] = f;
 		            _source[f] = _root;
 		            _target[f] = u;
 		            _cap[f] = INF;
 		            _flow[f] = -_supply[u];
 		            _cost[f] = ART_COST;
 		            _state[f] = STATE_TREE;
 		            _source[e] = u;
 		            _target[e] = _root;
 		            _cap[e] = INF;
 		            _flow[e] = 0;
 		            _cost[e] = 0;
 		            _state[e] = STATE_LOWER;
 		            ++f;
+		          }
+		        }
 		        _all_arc_num = f;
+		      }
 		      else {
 		        // GEQ supply constraints
 		        _search_arc_num = _arc_num + _node_num;
 		        int f = _arc_num + _node_num;
 		        for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
 		          _parent[u] = _root;
 		          _thread[u] = u + 1;
 		          _rev_thread[u + 1] = u;
 		          _succ_num[u] = 1;
 		          _last_succ[u] = u;
 		          if (_supply[u] <= 0) {
 		            _forward[u] = false;
 		            _pi[u] = 0;
 		            _pred[u] = e;
 		            _source[e] = _root;
 		            _target[e] = u;
 		            _cap[e] = INF;
 		            _flow[e] = -_supply[u];
 		            _cost[e] = 0;
 		            _state[e] = STATE_TREE;
 		          } else {
 		            _forward[u] = true;
 		            _pi[u] = -ART_COST;
 		            _pred[u] = f;
 		            _source[f] = u;
 		            _target[f] = _root;
 		            _cap[f] = INF;
 		            _flow[f] = _supply[u];
 		            _state[f] = STATE_TREE;
 		            _cost[f] = ART_COST;
 		            _source[e] = _root;
 		            _target[e] = u;
 		            _cap[e] = INF;
 		            _flow[e] = 0;
 		            _cost[e] = 0;
 		            _state[e] = STATE_LOWER;
 		            ++f;
+		          }
+		        }
 		        _all_arc_num = f;
+		      }
 		      return true;
+		    }
 		    // Find the join node
 		    void findJoinNode() {
 		      int u = _source[in_arc];
 		      int v = _target[in_arc];
 		      while (u != v) {
 		        if (_succ_num[u] < _succ_num[v]) {
 		          u = _parent[u];
 		        } else {
 		          v = _parent[v];
+		        }
+		      }
 		      join = u;
+		    }
 		    // Find the leaving arc of the cycle and returns true if the
 		    // leaving arc is not the same as the entering arc
 		    bool findLeavingArc() {
 		      // Initialize first and second nodes according to the direction
 		      // of the cycle
 		      if (_state[in_arc] == STATE_LOWER) {
 		        first  = _source[in_arc];
 		        second = _target[in_arc];
 		      } else {
 		        first  = _target[in_arc];
 		        second = _source[in_arc];
+		      }
 		      delta = _cap[in_arc];
 		      int result = 0;
 		      Value d;
 		      int e;
 		      // Search the cycle along the path form the first node to the root
 		      for (int u = first; u != join; u = _parent[u]) {
 		        e = _pred[u];
 		        d = _forward[u] ?
 		          _flow[e] : (_cap[e] == INF ? INF : _cap[e] - _flow[e]);
 		        if (d < delta) {
 		          delta = d;
 		          u_out = u;
 		          result = 1;
+		        }
+		      }
 		      // Search the cycle along the path form the second node to the root
 		      for (int u = second; u != join; u = _parent[u]) {
@@ -1329,86 +1392,98 @@
 		    // Update potentials
 		    void updatePotential() {
 		      Cost sigma = _forward[u_in] ?
 		        _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] :
 		        _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]];
 		      // Update potentials in the subtree, which has been moved
 		      int end = _thread[_last_succ[u_in]];
 		      for (int u = u_in; u != end; u = _thread[u]) {
 		        _pi[u] += sigma;
+		      }
+		    }
 		    // Execute the algorithm
 		    ProblemType start(PivotRule pivot_rule) {
 		      // Select the pivot rule implementation
 		      switch (pivot_rule) {
 		        case FIRST_ELIGIBLE:
 		          return start<FirstEligiblePivotRule>();
 		        case BEST_ELIGIBLE:
 		          return start<BestEligiblePivotRule>();
 		        case BLOCK_SEARCH:
 		          return start<BlockSearchPivotRule>();
 		        case CANDIDATE_LIST:
 		          return start<CandidateListPivotRule>();
 		        case ALTERING_LIST:
 		          return start<AlteringListPivotRule>();
+		      }
 		      return INFEASIBLE; // avoid warning
+		    }
 		    template <typename PivotRuleImpl>
 		    ProblemType start() {
 		      PivotRuleImpl pivot(*this);
 		      // Execute the Network Simplex algorithm
 		      while (pivot.findEnteringArc()) {
 		        findJoinNode();
 		        bool change = findLeavingArc();
 		        if (delta >= INF) return UNBOUNDED;
 		        changeFlow(change);
 		        if (change) {
 		          updateTreeStructure();
 		          updatePotential();
+		        }
+		      }
 		      // Check feasibility
 		      if (_sum_supply < 0) {
 		        for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
 		          if (_supply[u] >= 0 && _flow[e] != 0) return INFEASIBLE;
+		        }
+		      }
 		      else if (_sum_supply > 0) {
 		        for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
 		          if (_supply[u] <= 0 && _flow[e] != 0) return INFEASIBLE;
+		        }
+		      }
 		      else {
 		        for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
 		          if (_flow[e] != 0) return INFEASIBLE;
+		        }
 		      for (int e = _search_arc_num; e != _all_arc_num; ++e) {
 		        if (_flow[e] != 0) return INFEASIBLE;
+		      }
 		      // Transform the solution and the supply map to the original form
 		      if (_have_lower) {
 		        for (int i = 0; i != _arc_num; ++i) {
 		          Value c = _lower[i];
 		          if (c != 0) {
 		            _flow[i] += c;
 		            _supply[_source[i]] += c;
 		            _supply[_target[i]] -= c;
+		          }
+		        }
+		      }
 		      // Shift potentials to meet the requirements of the GEQ/LEQ type
 		      // optimality conditions
 		      if (_sum_supply == 0) {
 		        if (_stype == GEQ) {
 		          Cost max_pot = std::numeric_limits<Cost>::min();
 		          for (int i = 0; i != _node_num; ++i) {
 		            if (_pi[i] > max_pot) max_pot = _pi[i];
+		          }
 		          if (max_pot > 0) {
 		            for (int i = 0; i != _node_num; ++i)
 		              _pi[i] -= max_pot;
+		          }
 		        } else {
 		          Cost min_pot = std::numeric_limits<Cost>::max();
 		          for (int i = 0; i != _node_num; ++i) {
 		            if (_pi[i] < min_pot) min_pot = _pi[i];
+		          }
 		          if (min_pot < 0) {
 		            for (int i = 0; i != _node_num; ++i)
 		              _pi[i] -= min_pot;
+		          }
+		        }
+		      }
 		      return OPTIMAL;
+		    }
 		  }; //class NetworkSimplex
 		  ///@}
 		} //namespace lemon
 		#endif //LEMON_NETWORK_SIMPLEX_H

scripts/unify-sources.sh

Show inline comments

 		#!/bin/bash
 		YEAR=`date +%Y`
 		HGROOT=`hg root`
 		function hg_year() {
 		    if [ -n "$(hg st $1)" ]; then
 		        echo $YEAR
 		    else
 		        hg log -l 1 --template='{date|isodate}\n' $1 |
 		        cut -d '-' -f 1
 		    fi
+		}
 		# file enumaration modes
 		function all_files() {
 		    hg status -a -m -c |
 		    cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' |
 		    while read file; do echo $HGROOT/$file; done
+		}
 		function modified_files() {
 		    hg status -a -m |
 		    cut -d ' ' -f 2 | grep -E  '(\.(cc|h|dox)$|Makefile\.am$)' |
 		    while read file; do echo $HGROOT/$file; done
+		}
 		function changed_files() {
+		    {
 		        if [ -n "$HG_PARENT1" ]
 		        then
 		            hg status --rev $HG_PARENT1:$HG_NODE -a -m
 		        fi
 		        if [ -n "$HG_PARENT2" ]
 		        then
 		            hg status --rev $HG_PARENT2:$HG_NODE -a -m
 		        fi
 		    } | cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' |
 		    sort | uniq |
 		    while read file; do echo $HGROOT/$file; done
+		}
 		function given_files() {
 		    for file in $GIVEN_FILES
 		    do
 			echo $file
 		    done
+		}
 		# actions
 		function update_action() {
 		    if ! diff -q $1 $2 >/dev/null
 		    then
 			echo -n " [$3 updated]"
 			rm $2
 			mv $1 $2
 			CHANGED=YES
 		    fi

test/CMakeLists.txt

Show inline comments

 		INCLUDE_DIRECTORIES(
 		  ${PROJECT_SOURCE_DIR}
 		  ${PROJECT_BINARY_DIR}
+		)
 		LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon)
 		SET(TESTS
 		  adaptors_test
 		  bfs_test
 		  circulation_test
 		  connectivity_test
 		  counter_test
 		  dfs_test
 		  digraph_test
 		  dijkstra_test
 		  dim_test
 		  edge_set_test
 		  error_test
 		  euler_test
 		  gomory_hu_test
 		  graph_copy_test
 		  graph_test
 		  graph_utils_test
 		  hao_orlin_test
 		  heap_test
 		  kruskal_test
 		  maps_test
 		  matching_test
 		  min_cost_arborescence_test
 		  min_cost_flow_test
 		  path_test
 		  preflow_test
 		  radix_sort_test
 		  random_test
 		  suurballe_test
 		  time_measure_test
 		  unionfind_test)
 		IF(LEMON_HAVE_LP)
 		  ADD_EXECUTABLE(lp_test lp_test.cc)
 		  SET(LP_TEST_LIBS lemon)
 		  IF(LEMON_HAVE_GLPK)
 		    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${GLPK_LIBRARIES})
 		  ENDIF(LEMON_HAVE_GLPK)
 		  IF(LEMON_HAVE_CPLEX)
 		    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${CPLEX_LIBRARIES})
 		  ENDIF(LEMON_HAVE_CPLEX)
 		  IF(LEMON_HAVE_CLP)
 		    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${COIN_CLP_LIBRARIES})
 		  ENDIF(LEMON_HAVE_CLP)
 		  TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS})
 		  ADD_TEST(lp_test lp_test)
 		  IF(WIN32 AND LEMON_HAVE_GLPK)
 		    GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)
 		    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
 		    ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
 		      COMMAND cmake -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}
 		      COMMAND cmake -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}

test/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			test/CMakeLists.txt
 		noinst_HEADERS += \
 			test/graph_test.h \
 			test/test_tools.h
 		check_PROGRAMS += \
 			test/adaptors_test \
 			test/bfs_test \
 			test/circulation_test \
 			test/connectivity_test \
 			test/counter_test \
 			test/dfs_test \
 			test/digraph_test \
 			test/dijkstra_test \
 			test/dim_test \
 			test/edge_set_test \
 			test/error_test \
 			test/euler_test \
 			test/gomory_hu_test \
 			test/graph_copy_test \
 			test/graph_test \
 			test/graph_utils_test \
 			test/hao_orlin_test \
 			test/heap_test \
 			test/kruskal_test \
 			test/maps_test \
 			test/matching_test \
 			test/min_cost_arborescence_test \
 			test/min_cost_flow_test \
 			test/path_test \
 			test/preflow_test \
 			test/radix_sort_test \
 			test/random_test \
 			test/suurballe_test \
 			test/test_tools_fail \
 			test/test_tools_pass \
 			test/time_measure_test \
 			test/unionfind_test
 		test_test_tools_pass_DEPENDENCIES = demo
 		if HAVE_LP
 		check_PROGRAMS += test/lp_test
 		endif HAVE_LP
 		if HAVE_MIP
 		check_PROGRAMS += test/mip_test
 		endif HAVE_MIP
 		TESTS += $(check_PROGRAMS)
 		XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
 		test_adaptors_test_SOURCES = test/adaptors_test.cc
 		test_bfs_test_SOURCES = test/bfs_test.cc
 		test_circulation_test_SOURCES = test/circulation_test.cc
 		test_counter_test_SOURCES = test/counter_test.cc
 		test_connectivity_test_SOURCES = test/connectivity_test.cc
 		test_dfs_test_SOURCES = test/dfs_test.cc
 		test_digraph_test_SOURCES = test/digraph_test.cc
 		test_dijkstra_test_SOURCES = test/dijkstra_test.cc
 		test_dim_test_SOURCES = test/dim_test.cc
 		test_edge_set_test_SOURCES = test/edge_set_test.cc
 		test_error_test_SOURCES = test/error_test.cc
 		test_euler_test_SOURCES = test/euler_test.cc
 		test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc
 		test_graph_copy_test_SOURCES = test/graph_copy_test.cc
 		test_graph_test_SOURCES = test/graph_test.cc
 		test_graph_utils_test_SOURCES = test/graph_utils_test.cc
 		test_heap_test_SOURCES = test/heap_test.cc
 		test_kruskal_test_SOURCES = test/kruskal_test.cc
 		test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
 		test_lp_test_SOURCES = test/lp_test.cc
 		test_maps_test_SOURCES = test/maps_test.cc
 		test_mip_test_SOURCES = test/mip_test.cc
 		test_matching_test_SOURCES = test/matching_test.cc
 		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_path_test_SOURCES = test/path_test.cc
 		test_preflow_test_SOURCES = test/preflow_test.cc
 		test_radix_sort_test_SOURCES = test/radix_sort_test.cc
 		test_suurballe_test_SOURCES = test/suurballe_test.cc
 		test_random_test_SOURCES = test/random_test.cc
 		test_test_tools_fail_SOURCES = test/test_tools_fail.cc
 		test_test_tools_pass_SOURCES = test/test_tools_pass.cc
 		test_time_measure_test_SOURCES = test/time_measure_test.cc
 		test_unionfind_test_SOURCES = test/unionfind_test.cc

test/min_cost_flow_test.cc

Show inline comments

@@ -129,262 +129,319 @@
 		    const Node &n;
 		    const Arc &a;
 		    const Value &k;
 		    FlowMap fm;
 		    PotMap pm;
 		    bool b;
 		    double x;
 		    typename MCF::Value v;
 		    typename MCF::Cost c;
 		  };
 		};
 		// Check the feasibility of the given flow (primal soluiton)
 		template < typename GR, typename LM, typename UM,
 		           typename SM, typename FM >
 		bool checkFlow( const GR& gr, const LM& lower, const UM& upper,
 		                const SM& supply, const FM& flow,
 		                SupplyType type = EQ )
+		{
 		  TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		  for (ArcIt e(gr); e != INVALID; ++e) {
 		    if (flow[e] < lower[e] || flow[e] > upper[e]) return false;
+		  }
 		  for (NodeIt n(gr); n != INVALID; ++n) {
 		    typename SM::Value sum = 0;
 		    for (OutArcIt e(gr, n); e != INVALID; ++e)
 		      sum += flow[e];
 		    for (InArcIt e(gr, n); e != INVALID; ++e)
 		      sum -= flow[e];
 		    bool b = (type ==  EQ && sum == supply[n]) ||
 		             (type == GEQ && sum >= supply[n]) ||
 		             (type == LEQ && sum <= supply[n]);
 		    if (!b) return false;
+		  }
 		  return true;
+		}
 		// Check the feasibility of the given potentials (dual soluiton)
 		// using the "Complementary Slackness" optimality condition
 		template < typename GR, typename LM, typename UM,
 		           typename CM, typename SM, typename FM, typename PM >
 		bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
 		                     const CM& cost, const SM& supply, const FM& flow,
 		                     const PM& pi )
+		                     const PM& pi, SupplyType type )
+		{
 		  TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		  bool opt = true;
 		  for (ArcIt e(gr); opt && e != INVALID; ++e) {
 		    typename CM::Value red_cost =
 		      cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
 		    opt = red_cost == 0 ||
 		          (red_cost > 0 && flow[e] == lower[e]) ||
 		          (red_cost < 0 && flow[e] == upper[e]);
+		  }
 		  for (NodeIt n(gr); opt && n != INVALID; ++n) {
 		    typename SM::Value sum = 0;
 		    for (OutArcIt e(gr, n); e != INVALID; ++e)
 		      sum += flow[e];
 		    for (InArcIt e(gr, n); e != INVALID; ++e)
 		      sum -= flow[e];
-		    opt = (sum == supply[n]) || (pi[n] == 0);
+		    if (type != LEQ) {
 		      opt = (pi[n] <= 0) && (sum == supply[n] || pi[n] == 0);
 		    } else {
 		      opt = (pi[n] >= 0) && (sum == supply[n] || pi[n] == 0);
+		    }
+		  }
 		  return opt;
+		}
 		// Check whether the dual cost is equal to the primal cost
 		template < typename GR, typename LM, typename UM,
 		           typename CM, typename SM, typename PM >
 		bool checkDualCost( const GR& gr, const LM& lower, const UM& upper,
 		                    const CM& cost, const SM& supply, const PM& pi,
 		                    typename CM::Value total )
+		{
 		  TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		  typename CM::Value dual_cost = 0;
 		  SM red_supply(gr);
 		  for (NodeIt n(gr); n != INVALID; ++n) {
 		    red_supply[n] = supply[n];
+		  }
 		  for (ArcIt a(gr); a != INVALID; ++a) {
 		    if (lower[a] != 0) {
 		      dual_cost += lower[a] * cost[a];
 		      red_supply[gr.source(a)] -= lower[a];
 		      red_supply[gr.target(a)] += lower[a];
+		    }
+		  }
 		  for (NodeIt n(gr); n != INVALID; ++n) {
 		    dual_cost -= red_supply[n] * pi[n];
+		  }
 		  for (ArcIt a(gr); a != INVALID; ++a) {
 		    typename CM::Value red_cost =
 		      cost[a] + pi[gr.source(a)] - pi[gr.target(a)];
 		    dual_cost -= (upper[a] - lower[a]) * std::max(-red_cost, 0);
+		  }
 		  return dual_cost == total;
+		}
 		// Run a minimum cost flow algorithm and check the results
 		template < typename MCF, typename GR,
 		           typename LM, typename UM,
 		           typename CM, typename SM,
 		           typename PT >
 		void checkMcf( const MCF& mcf, PT mcf_result,
 		               const GR& gr, const LM& lower, const UM& upper,
 		               const CM& cost, const SM& supply,
 		               PT result, bool optimal, typename CM::Value total,
 		               const std::string &test_id = "",
 		               SupplyType type = EQ )
+		{
 		  check(mcf_result == result, "Wrong result " + test_id);
 		  if (optimal) {
 		    typename GR::template ArcMap<typename SM::Value> flow(gr);
 		    typename GR::template NodeMap<typename CM::Value> pi(gr);
 		    mcf.flowMap(flow);
 		    mcf.potentialMap(pi);
 		    check(checkFlow(gr, lower, upper, supply, flow, type),
 		          "The flow is not feasible " + test_id);
 		    check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
 		    check(checkPotential(gr, lower, upper, cost, supply, flow, pi),
+		    check(checkPotential(gr, lower, upper, cost, supply, flow, pi, type),
 		          "Wrong potentials " + test_id);
 		    check(checkDualCost(gr, lower, upper, cost, supply, pi, total),
 		          "Wrong dual cost " + test_id);
+		  }
+		}
 		int main()
+		{
 		  // Check the interfaces
+		  {
 		    typedef concepts::Digraph GR;
 		    checkConcept< McfClassConcept<GR, int, int>,
 		                  NetworkSimplex<GR> >();
 		    checkConcept< McfClassConcept<GR, double, double>,
 		                  NetworkSimplex<GR, double> >();
 		    checkConcept< McfClassConcept<GR, int, double>,
 		                  NetworkSimplex<GR, int, double> >();
+		  }
 		  // Run various MCF tests
 		  typedef ListDigraph Digraph;
 		  DIGRAPH_TYPEDEFS(ListDigraph);
 		  // Read the test digraph
 		  Digraph gr;
 		  Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
 		  Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
 		  ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
 		  Node v, w;
 		  std::istringstream input(test_lgf);
 		  DigraphReader<Digraph>(gr, input)
 		    .arcMap("cost", c)
 		    .arcMap("cap", u)
 		    .arcMap("low1", l1)
 		    .arcMap("low2", l2)
 		    .arcMap("low3", l3)
 		    .nodeMap("sup1", s1)
 		    .nodeMap("sup2", s2)
 		    .nodeMap("sup3", s3)
 		    .nodeMap("sup4", s4)
 		    .nodeMap("sup5", s5)
 		    .nodeMap("sup6", s6)
 		    .node("source", v)
 		    .node("target", w)
 		    .run();
 		  // Build a test digraph for testing negative costs
 		  Digraph ngr;
 		  Node n1 = ngr.addNode();
 		  Node n2 = ngr.addNode();
 		  Node n3 = ngr.addNode();
 		  Node n4 = ngr.addNode();
 		  Node n5 = ngr.addNode();
 		  Node n6 = ngr.addNode();
-		  Node n7 = ngr.addNode();
+		  // Build test digraphs with negative costs
 		  Digraph neg_gr;
 		  Node n1 = neg_gr.addNode();
 		  Node n2 = neg_gr.addNode();
 		  Node n3 = neg_gr.addNode();
 		  Node n4 = neg_gr.addNode();
 		  Node n5 = neg_gr.addNode();
 		  Node n6 = neg_gr.addNode();
 		  Node n7 = neg_gr.addNode();
 		  Arc a1 = ngr.addArc(n1, n2);
 		  Arc a2 = ngr.addArc(n1, n3);
 		  Arc a3 = ngr.addArc(n2, n4);
 		  Arc a4 = ngr.addArc(n3, n4);
 		  Arc a5 = ngr.addArc(n3, n2);
 		  Arc a6 = ngr.addArc(n5, n3);
 		  Arc a7 = ngr.addArc(n5, n6);
 		  Arc a8 = ngr.addArc(n6, n7);
-		  Arc a9 = ngr.addArc(n7, n5);
+		  Arc a1 = neg_gr.addArc(n1, n2);
 		  Arc a2 = neg_gr.addArc(n1, n3);
 		  Arc a3 = neg_gr.addArc(n2, n4);
 		  Arc a4 = neg_gr.addArc(n3, n4);
 		  Arc a5 = neg_gr.addArc(n3, n2);
 		  Arc a6 = neg_gr.addArc(n5, n3);
 		  Arc a7 = neg_gr.addArc(n5, n6);
 		  Arc a8 = neg_gr.addArc(n6, n7);
 		  Arc a9 = neg_gr.addArc(n7, n5);
 		  Digraph::ArcMap<int> nc(ngr), nl1(ngr, 0), nl2(ngr, 0);
 		  ConstMap<Arc, int> nu1(std::numeric_limits<int>::max()), nu2(5000);
-		  Digraph::NodeMap<int> ns(ngr, 0);
+		  Digraph::ArcMap<int> neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0);
 		  ConstMap<Arc, int> neg_u1(std::numeric_limits<int>::max()), neg_u2(5000);
 		  Digraph::NodeMap<int> neg_s(neg_gr, 0);
 		  nl2[a7] =  1000;
 		  nl2[a8] = -1000;
 		  neg_l2[a7] =  1000;
 		  neg_l2[a8] = -1000;
 		  ns[n1] =  100;
 		  ns[n4] = -100;
 		  neg_s[n1] =  100;
 		  neg_s[n4] = -100;
 		  nc[a1] =  100;
 		  nc[a2] =   30;
 		  nc[a3] =   20;
 		  nc[a4] =   80;
 		  nc[a5] =   50;
 		  nc[a6] =   10;
 		  nc[a7] =   80;
 		  nc[a8] =   30;
-		  nc[a9] = -120;
+		  neg_c[a1] =  100;
 		  neg_c[a2] =   30;
 		  neg_c[a3] =   20;
 		  neg_c[a4] =   80;
 		  neg_c[a5] =   50;
 		  neg_c[a6] =   10;
 		  neg_c[a7] =   80;
 		  neg_c[a8] =   30;
 		  neg_c[a9] = -120;
 		  Digraph negs_gr;
 		  Digraph::NodeMap<int> negs_s(negs_gr);
 		  Digraph::ArcMap<int> negs_c(negs_gr);
 		  ConstMap<Arc, int> negs_l(0), negs_u(1000);
 		  n1 = negs_gr.addNode();
 		  n2 = negs_gr.addNode();
 		  negs_s[n1] = 100;
 		  negs_s[n2] = -300;
 		  negs_c[negs_gr.addArc(n1, n2)] = -1;
 		  // A. Test NetworkSimplex with the default pivot rule
+		  {
 		    NetworkSimplex<Digraph> mcf(gr);
 		    // Check the equality form
 		    mcf.upperMap(u).costMap(c);
 		    checkMcf(mcf, mcf.supplyMap(s1).run(),
 		             gr, l1, u, c, s1, mcf.OPTIMAL, true,   5240, "#A1");
 		    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
 		             gr, l1, u, c, s2, mcf.OPTIMAL, true,   7620, "#A2");
 		    mcf.lowerMap(l2);
 		    checkMcf(mcf, mcf.supplyMap(s1).run(),
 		             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#A3");
 		    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
 		             gr, l2, u, c, s2, mcf.OPTIMAL, true,   8010, "#A4");
 		    mcf.reset();
 		    checkMcf(mcf, mcf.supplyMap(s1).run(),
 		             gr, l1, cu, cc, s1, mcf.OPTIMAL, true,   74, "#A5");
 		    checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),
 		             gr, l2, cu, cc, s2, mcf.OPTIMAL, true,   94, "#A6");
 		    mcf.reset();
 		    checkMcf(mcf, mcf.run(),
 		             gr, l1, cu, cc, s3, mcf.OPTIMAL, true,    0, "#A7");
 		    checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(),
 		             gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8");
 		    mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);
 		    checkMcf(mcf, mcf.run(),
 		             gr, l3, u, c, s4, mcf.OPTIMAL, true,   6360, "#A9");
 		    // Check the GEQ form
 		    mcf.reset().upperMap(u).costMap(c).supplyMap(s5);
 		    checkMcf(mcf, mcf.run(),
 		             gr, l1, u, c, s5, mcf.OPTIMAL, true,   3530, "#A10", GEQ);
 		    mcf.supplyType(mcf.GEQ);
 		    checkMcf(mcf, mcf.lowerMap(l2).run(),
 		             gr, l2, u, c, s5, mcf.OPTIMAL, true,   4540, "#A11", GEQ);
-		    mcf.supplyType(mcf.CARRY_SUPPLIES).supplyMap(s6);
 		    mcf.supplyMap(s6);
 		    checkMcf(mcf, mcf.run(),
 		             gr, l2, u, c, s6, mcf.INFEASIBLE, false,  0, "#A12", GEQ);
 		    // Check the LEQ form
 		    mcf.reset().supplyType(mcf.LEQ);
 		    mcf.upperMap(u).costMap(c).supplyMap(s6);
 		    checkMcf(mcf, mcf.run(),
 		             gr, l1, u, c, s6, mcf.OPTIMAL, true,   5080, "#A13", LEQ);
 		    checkMcf(mcf, mcf.lowerMap(l2).run(),
 		             gr, l2, u, c, s6, mcf.OPTIMAL, true,   5930, "#A14", LEQ);
-		    mcf.supplyType(mcf.SATISFY_DEMANDS).supplyMap(s5);
 		    mcf.supplyMap(s5);
 		    checkMcf(mcf, mcf.run(),
 		             gr, l2, u, c, s5, mcf.INFEASIBLE, false,  0, "#A15", LEQ);
 		    // Check negative costs
 		    NetworkSimplex<Digraph> nmcf(ngr);
 		    nmcf.lowerMap(nl1).costMap(nc).supplyMap(ns);
 		    checkMcf(nmcf, nmcf.run(),
 		      ngr, nl1, nu1, nc, ns, nmcf.UNBOUNDED, false,    0, "#A16");
 		    checkMcf(nmcf, nmcf.upperMap(nu2).run(),
 		      ngr, nl1, nu2, nc, ns, nmcf.OPTIMAL, true,  -40000, "#A17");
 		    nmcf.reset().lowerMap(nl2).costMap(nc).supplyMap(ns);
 		    checkMcf(nmcf, nmcf.run(),
-		      ngr, nl2, nu1, nc, ns, nmcf.UNBOUNDED, false,    0, "#A18");
+		    NetworkSimplex<Digraph> neg_mcf(neg_gr);
 		    neg_mcf.lowerMap(neg_l1).costMap(neg_c).supplyMap(neg_s);
 		    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u1,
 		      neg_c, neg_s, neg_mcf.UNBOUNDED, false,    0, "#A16");
 		    neg_mcf.upperMap(neg_u2);
 		    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u2,
 		      neg_c, neg_s, neg_mcf.OPTIMAL, true,  -40000, "#A17");
 		    neg_mcf.reset().lowerMap(neg_l2).costMap(neg_c).supplyMap(neg_s);
 		    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1,
 		      neg_c, neg_s, neg_mcf.UNBOUNDED, false,    0, "#A18");
 		    NetworkSimplex<Digraph> negs_mcf(negs_gr);
 		    negs_mcf.costMap(negs_c).supplyMap(negs_s);
 		    checkMcf(negs_mcf, negs_mcf.run(), negs_gr, negs_l, negs_u,
 		      negs_c, negs_s, negs_mcf.OPTIMAL, true, -300, "#A19", GEQ);
+		  }
 		  // B. Test NetworkSimplex with each pivot rule
+		  {
 		    NetworkSimplex<Digraph> mcf(gr);
 		    mcf.supplyMap(s1).costMap(c).upperMap(u).lowerMap(l2);
 		    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
 		             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B1");
 		    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
 		             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B2");
 		    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
 		             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B3");
 		    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
 		             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B4");
 		    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
 		             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B5");
+		  }
 		  return 0;
+		}

tools/lgf-gen.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		/// \ingroup tools
 		/// \file
-		/// \brief Special plane digraph generator.
+		/// \brief Special plane graph generator.
 		///
 		/// Graph generator application for various types of plane graphs.
 		///
 		/// See
 		/// \code
 		///   lgf-gen --help
 		/// \endcode
-		/// for more info on the usage.
+		/// for more information on the usage.
 		#include <algorithm>
 		#include <set>
 		#include <ctime>
 		#include <lemon/list_graph.h>
 		#include <lemon/random.h>
 		#include <lemon/dim2.h>
 		#include <lemon/bfs.h>
 		#include <lemon/counter.h>
 		#include <lemon/suurballe.h>
 		#include <lemon/graph_to_eps.h>
 		#include <lemon/lgf_writer.h>
 		#include <lemon/arg_parser.h>
 		#include <lemon/euler.h>
 		#include <lemon/math.h>
 		#include <lemon/kruskal.h>
 		#include <lemon/time_measure.h>
 		using namespace lemon;
 		typedef dim2::Point<double> Point;
 		GRAPH_TYPEDEFS(ListGraph);
 		bool progress=true;
 		int N;
 		// int girth;
 		ListGraph g;
 		std::vector<Node> nodes;
 		ListGraph::NodeMap<Point> coords(g);
 		double totalLen(){
 		  double tlen=0;
 		  for(EdgeIt e(g);e!=INVALID;++e)
 		    tlen+=std::sqrt((coords[g.v(e)]-coords[g.u(e)]).normSquare());
 		  return tlen;
+		}
 		int tsp_impr_num=0;
 		const double EPSILON=1e-8;
 		bool tsp_improve(Node u, Node v)
+		{
 		  double luv=std::sqrt((coords[v]-coords[u]).normSquare());
@@ -641,118 +641,119 @@
 		      Node n1=g.oppositeNode(n2,e);
 		      Node n3=g.oppositeNode(n2,f);
 		      if(countIncEdges(g,n2)>2)
+		        {
 		//           std::cout << "Remove an Arc" << std::endl;
 		          Arc ff=enext[f];
 		          g.erase(e);
 		          g.erase(f);
 		          if(n1!=n3)
+		            {
 		              Arc ne=g.direct(g.addEdge(n1,n3),n1);
 		              enext[p]=ne;
 		              enext[ne]=ff;
 		              ednum--;
+		            }
 		          else {
 		            enext[p]=ff;
 		            ednum-=2;
+		          }
+		        }
+		    }
 		  std::cout << "Total arc length (tour) : " << totalLen() << std::endl;
 		  std::cout << "2-opt the tour..." << std::endl;
 		  tsp_improve();
 		  std::cout << "Total arc length (2-opt tour) : " << totalLen() << std::endl;
+		}
 		int main(int argc,const char **argv)
+		{
 		  ArgParser ap(argc,argv);
 		//   bool eps;
 		  bool disc_d, square_d, gauss_d;
 		//   bool tsp_a,two_a,tree_a;
 		  int num_of_cities=1;
 		  double area=1;
 		  N=100;
 		//   girth=10;
 		  std::string ndist("disc");
 		  ap.refOption("n", "Number of nodes (default is 100)", N)
 		    .intOption("g", "Girth parameter (default is 10)", 10)
 		    .refOption("cities", "Number of cities (default is 1)", num_of_cities)
 		    .refOption("area", "Full relative area of the cities (default is 1)", area)
-		    .refOption("disc", "Nodes are evenly distributed on a unit disc (default)",disc_d)
 		    .refOption("disc", "Nodes are evenly distributed on a unit disc (default)",
 		               disc_d)
 		    .optionGroup("dist", "disc")
-		    .refOption("square", "Nodes are evenly distributed on a unit square", square_d)
 		    .refOption("square", "Nodes are evenly distributed on a unit square",
 		               square_d)
 		    .optionGroup("dist", "square")
 		    .refOption("gauss",
 		            "Nodes are located according to a two-dim gauss distribution",
-		            gauss_d)
+		    .refOption("gauss", "Nodes are located according to a two-dim Gauss "
 		               "distribution", gauss_d)
 		    .optionGroup("dist", "gauss")
 		//     .mandatoryGroup("dist")
 		    .onlyOneGroup("dist")
 		    .boolOption("eps", "Also generate .eps output (prefix.eps)")
 		    .boolOption("nonodes", "Draw the edges only in the generated .eps")
 		    .boolOption("dir", "Directed digraph is generated (each arcs are replaced by two directed ones)")
 		    .boolOption("2con", "Create a two connected planar digraph")
 		    .boolOption("eps", "Also generate .eps output (<prefix>.eps)")
 		    .boolOption("nonodes", "Draw only the edges in the generated .eps output")
 		    .boolOption("dir", "Directed graph is generated (each edge is replaced by "
 		                "two directed arcs)")
 		    .boolOption("2con", "Create a two connected planar graph")
 		    .optionGroup("alg","2con")
 		    .boolOption("tree", "Create a min. cost spanning tree")
 		    .optionGroup("alg","tree")
 		    .boolOption("tsp", "Create a TSP tour")
 		    .optionGroup("alg","tsp")
 		    .boolOption("tsp2", "Create a TSP tour (tree based)")
 		    .optionGroup("alg","tsp2")
-		    .boolOption("dela", "Delaunay triangulation digraph")
+		    .boolOption("dela", "Delaunay triangulation graph")
 		    .optionGroup("alg","dela")
 		    .onlyOneGroup("alg")
 		    .boolOption("rand", "Use time seed for random number generator")
 		    .optionGroup("rand", "rand")
 		    .intOption("seed", "Random seed", -1)
 		    .optionGroup("rand", "seed")
 		    .onlyOneGroup("rand")
 		    .other("[prefix]","Prefix of the output files. Default is 'lgf-gen-out'")
 		    .run();
 		  if (ap["rand"]) {
 		    int seed = int(time(0));
 		    std::cout << "Random number seed: " << seed << std::endl;
 		    rnd = Random(seed);
+		  }
 		  if (ap.given("seed")) {
 		    int seed = ap["seed"];
 		    std::cout << "Random number seed: " << seed << std::endl;
 		    rnd = Random(seed);
+		  }
 		  std::string prefix;
 		  switch(ap.files().size())
+		    {
 		    case 0:
 		      prefix="lgf-gen-out";
 		      break;
 		    case 1:
 		      prefix=ap.files()[0];
 		      break;
 		    default:
 		      std::cerr << "\nAt most one prefix can be given\n\n";
 		      exit(1);
+		    }
 		  double sum_sizes=0;
 		  std::vector<double> sizes;
 		  std::vector<double> cum_sizes;
 		  for(int s=0;s<num_of_cities;s++)
+		    {
 		      //         sum_sizes+=rnd.exponential();
 		      double d=rnd();
 		      sum_sizes+=d;
 		      sizes.push_back(d);
 		      cum_sizes.push_back(sum_sizes);
+		    }
 		  int i=0;
 		  for(int s=0;s<num_of_cities;s++)

lemon/bits/base_extender.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_BASE_EXTENDER_H
 		#define LEMON_BITS_BASE_EXTENDER_H
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/bits/map_extender.h>
 		#include <lemon/bits/default_map.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		//\ingroup digraphbits
 		//\file
 		//\brief Extenders for the graph types
 		namespace lemon {
 		  // \ingroup digraphbits
 		  //
 		  // \brief BaseDigraph to BaseGraph extender
 		  template <typename Base>
 		  class UndirDigraphExtender : public Base {
 		    typedef Base Parent;
 		  public:
 		    typedef typename Parent::Arc Edge;
 		    typedef typename Parent::Node Node;
 		    typedef True UndirectedTag;
 		    class Arc : public Edge {
 		      friend class UndirDigraphExtender;
 		    protected:
 		      bool forward;
 		      Arc(const Edge &ue, bool _forward) :
 		        Edge(ue), forward(_forward) {}
 		    public:
 		      Arc() {}
 		      // Invalid arc constructor
 		      Arc(Invalid i) : Edge(i), forward(true) {}
 		      bool operator==(const Arc &that) const {
 		        return forward==that.forward && Edge(*this)==Edge(that);
+		      }
 		      bool operator!=(const Arc &that) const {
 		        return forward!=that.forward || Edge(*this)!=Edge(that);
+		      }
 		      bool operator<(const Arc &that) const {
 		        return forward<that.forward ||
 		          (!(that.forward<forward) && Edge(*this)<Edge(that));
+		      }
 		    };
 		    // First node of the edge
 		    Node u(const Edge &e) const {
 		      return Parent::source(e);
+		    }
 		    // Source of the given arc
 		    Node source(const Arc &e) const {
 		      return e.forward ? Parent::source(e) : Parent::target(e);
+		    }
 		    // Second node of the edge
 		    Node v(const Edge &e) const {
 		      return Parent::target(e);
+		    }
 		    // Target of the given arc
 		    Node target(const Arc &e) const {
 		      return e.forward ? Parent::target(e) : Parent::source(e);
+		    }
 		    // \brief Directed arc from an edge.
 		    //
 		    // Returns a directed arc corresponding to the specified edge.
 		    // If the given bool is true, the first node of the given edge and
 		    // the source node of the returned arc are the same.
 		    static Arc direct(const Edge &e, bool d) {
 		      return Arc(e, d);
+		    }
 		    // Returns whether the given directed arc has the same orientation
 		    // as the corresponding edge.
 		    static bool direction(const Arc &a) { return a.forward; }
 		    using Parent::first;
 		    using Parent::next;
 		    void first(Arc &e) const {
 		      Parent::first(e);
 		      e.forward=true;
+		    }
 		    void next(Arc &e) const {
 		      if( e.forward ) {
 		        e.forward = false;
+		      }
 		      else {
 		        Parent::next(e);
 		        e.forward = true;
+		      }
+		    }
 		    void firstOut(Arc &e, const Node &n) const {
 		      Parent::firstIn(e,n);
 		      if( Edge(e) != INVALID ) {
 		        e.forward = false;
+		      }
 		      else {
 		        Parent::firstOut(e,n);
 		        e.forward = true;
+		      }
+		    }
 		    void nextOut(Arc &e) const {
 		      if( ! e.forward ) {
 		        Node n = Parent::target(e);
 		        Parent::nextIn(e);
 		        if( Edge(e) == INVALID ) {
 		          Parent::firstOut(e, n);
 		          e.forward = true;
+		        }
+		      }
 		      else {
 		        Parent::nextOut(e);
+		      }
+		    }
 		    void firstIn(Arc &e, const Node &n) const {
 		      Parent::firstOut(e,n);
 		      if( Edge(e) != INVALID ) {
 		        e.forward = false;
+		      }
 		      else {
 		        Parent::firstIn(e,n);
 		        e.forward = true;
+		      }
+		    }
 		    void nextIn(Arc &e) const {
 		      if( ! e.forward ) {
 		        Node n = Parent::source(e);
 		        Parent::nextOut(e);
 		        if( Edge(e) == INVALID ) {
 		          Parent::firstIn(e, n);
 		          e.forward = true;
+		        }
+		      }
 		      else {
 		        Parent::nextIn(e);
+		      }
+		    }
 		    void firstInc(Edge &e, bool &d, const Node &n) const {
 		      d = true;
 		      Parent::firstOut(e, n);
 		      if (e != INVALID) return;
 		      d = false;
 		      Parent::firstIn(e, n);
+		    }
 		    void nextInc(Edge &e, bool &d) const {
 		      if (d) {
 		        Node s = Parent::source(e);
 		        Parent::nextOut(e);
 		        if (e != INVALID) return;
 		        d = false;
 		        Parent::firstIn(e, s);
 		      } else {
 		        Parent::nextIn(e);
+		      }
+		    }
 		    Node nodeFromId(int ix) const {
 		      return Parent::nodeFromId(ix);
+		    }
 		    Arc arcFromId(int ix) const {
 		      return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));
+		    }
 		    Edge edgeFromId(int ix) const {
 		      return Parent::arcFromId(ix);
+		    }
 		    int id(const Node &n) const {
 		      return Parent::id(n);
+		    }
 		    int id(const Edge &e) const {
 		      return Parent::id(e);
+		    }
 		    int id(const Arc &e) const {
 		      return 2 * Parent::id(e) + int(e.forward);
+		    }
 		    int maxNodeId() const {
 		      return Parent::maxNodeId();
+		    }
 		    int maxArcId() const {
 		      return 2 * Parent::maxArcId() + 1;
+		    }
 		    int maxEdgeId() const {
 		      return Parent::maxArcId();
+		    }
 		    int arcNum() const {
 		      return 2 * Parent::arcNum();
+		    }
 		    int edgeNum() const {
 		      return Parent::arcNum();
+		    }
 		    Arc findArc(Node s, Node t, Arc p = INVALID) const {
 		      if (p == INVALID) {
 		        Edge arc = Parent::findArc(s, t);
 		        if (arc != INVALID) return direct(arc, true);
 		        arc = Parent::findArc(t, s);
 		        if (arc != INVALID) return direct(arc, false);
 		      } else if (direction(p)) {
 		        Edge arc = Parent::findArc(s, t, p);
 		        if (arc != INVALID) return direct(arc, true);
 		        arc = Parent::findArc(t, s);
 		        if (arc != INVALID) return direct(arc, false);
 		      } else {
 		        Edge arc = Parent::findArc(t, s, p);
 		        if (arc != INVALID) return direct(arc, false);
+		      }
 		      return INVALID;
+		    }
 		    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
 		      if (s != t) {
 		        if (p == INVALID) {
 		          Edge arc = Parent::findArc(s, t);
 		          if (arc != INVALID) return arc;
 		          arc = Parent::findArc(t, s);
 		          if (arc != INVALID) return arc;
 		        } else if (Parent::s(p) == s) {
 		          Edge arc = Parent::findArc(s, t, p);
 		          if (arc != INVALID) return arc;
 		          arc = Parent::findArc(t, s);
 		          if (arc != INVALID) return arc;
 		        } else {
 		          Edge arc = Parent::findArc(t, s, p);
 		          if (arc != INVALID) return arc;
+		        }
 		      } else {
 		        return Parent::findArc(s, t, p);
+		      }
 		      return INVALID;
+		    }
 		  };
 		  template <typename Base>
 		  class BidirBpGraphExtender : public Base {
 		    typedef Base Parent;
 		  public:
 		    typedef BidirBpGraphExtender Digraph;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Edge Edge;
 		    using Parent::first;
 		    using Parent::next;
 		    using Parent::id;
 		    class Red : public Node {
 		      friend class BidirBpGraphExtender;
 		    public:
 		      Red() {}
 		      Red(const Node& node) : Node(node) {
 		        LEMON_DEBUG(Parent::red(node) || node == INVALID,
 		                    typename Parent::NodeSetError());
+		      }
 		      Red& operator=(const Node& node) {
 		        LEMON_DEBUG(Parent::red(node) || node == INVALID,
 		                    typename Parent::NodeSetError());
 		        Node::operator=(node);
 		        return *this;
+		      }
 		      Red(Invalid) : Node(INVALID) {}
 		      Red& operator=(Invalid) {
 		        Node::operator=(INVALID);
 		        return *this;
+		      }
 		    };
 		    void first(Red& node) const {
 		      Parent::firstRed(static_cast<Node&>(node));
+		    }
 		    void next(Red& node) const {
 		      Parent::nextRed(static_cast<Node&>(node));
+		    }
 		    int id(const Red& node) const {
 		      return Parent::redId(node);
+		    }
 		    class Blue : public Node {
 		      friend class BidirBpGraphExtender;
 		    public:
 		      Blue() {}
 		      Blue(const Node& node) : Node(node) {
 		        LEMON_DEBUG(Parent::blue(node) || node == INVALID,
 		                    typename Parent::NodeSetError());
+		      }
 		      Blue& operator=(const Node& node) {
 		        LEMON_DEBUG(Parent::blue(node) || node == INVALID,
 		                    typename Parent::NodeSetError());
 		        Node::operator=(node);
 		        return *this;
+		      }
 		      Blue(Invalid) : Node(INVALID) {}
 		      Blue& operator=(Invalid) {
 		        Node::operator=(INVALID);
 		        return *this;
+		      }
 		    };
 		    void first(Blue& node) const {
 		      Parent::firstBlue(static_cast<Node&>(node));
+		    }
 		    void next(Blue& node) const {
 		      Parent::nextBlue(static_cast<Node&>(node));
+		    }
 		    int id(const Blue& node) const {
 		      return Parent::redId(node);
+		    }
 		    Node source(const Edge& arc) const {
 		      return red(arc);
+		    }
 		    Node target(const Edge& arc) const {
 		      return blue(arc);
+		    }
 		    void firstInc(Edge& arc, bool& dir, const Node& node) const {
 		      if (Parent::red(node)) {
 		        Parent::firstFromRed(arc, node);
 		        dir = true;
 		      } else {
 		        Parent::firstFromBlue(arc, node);
 		        dir = static_cast<Edge&>(arc) == INVALID;
+		      }
+		    }
 		    void nextInc(Edge& arc, bool& dir) const {
 		      if (dir) {
 		        Parent::nextFromRed(arc);
 		      } else {
 		        Parent::nextFromBlue(arc);
 		        if (arc == INVALID) dir = true;
+		      }
+		    }
 		    class Arc : public Edge {
 		      friend class BidirBpGraphExtender;
 		    protected:
 		      bool forward;
 		      Arc(const Edge& arc, bool _forward)
 		        : Edge(arc), forward(_forward) {}
 		    public:
 		      Arc() {}
 		      Arc (Invalid) : Edge(INVALID), forward(true) {}
 		      bool operator==(const Arc& i) const {
 		        return Edge::operator==(i) && forward == i.forward;
+		      }
 		      bool operator!=(const Arc& i) const {
 		        return Edge::operator!=(i) || forward != i.forward;
+		      }
 		      bool operator<(const Arc& i) const {
 		        return Edge::operator<(i) ||
 		          (!(i.forward<forward) && Edge(*this)<Edge(i));
+		      }
 		    };
 		    void first(Arc& arc) const {
 		      Parent::first(static_cast<Edge&>(arc));
 		      arc.forward = true;
+		    }
 		    void next(Arc& arc) const {
 		      if (!arc.forward) {
 		        Parent::next(static_cast<Edge&>(arc));
+		      }
 		      arc.forward = !arc.forward;
+		    }
 		    void firstOut(Arc& arc, const Node& node) const {
 		      if (Parent::red(node)) {
 		        Parent::firstFromRed(arc, node);
 		        arc.forward = true;
 		      } else {
 		        Parent::firstFromBlue(arc, node);
 		        arc.forward = static_cast<Edge&>(arc) == INVALID;
+		      }
+		    }
 		    void nextOut(Arc& arc) const {
 		      if (arc.forward) {
 		        Parent::nextFromRed(arc);
 		      } else {
 		        Parent::nextFromBlue(arc);
 		        arc.forward = static_cast<Edge&>(arc) == INVALID;
+		      }
+		    }
 		    void firstIn(Arc& arc, const Node& node) const {
 		      if (Parent::blue(node)) {
 		        Parent::firstFromBlue(arc, node);
 		        arc.forward = true;
 		      } else {
 		        Parent::firstFromRed(arc, node);
 		        arc.forward = static_cast<Edge&>(arc) == INVALID;
+		      }
+		    }
 		    void nextIn(Arc& arc) const {
 		      if (arc.forward) {
 		        Parent::nextFromBlue(arc);
 		      } else {
 		        Parent::nextFromRed(arc);
 		        arc.forward = static_cast<Edge&>(arc) == INVALID;
+		      }
+		    }
 		    Node source(const Arc& arc) const {
 		      return arc.forward ? Parent::red(arc) : Parent::blue(arc);
+		    }
 		    Node target(const Arc& arc) const {
 		      return arc.forward ? Parent::blue(arc) : Parent::red(arc);
+		    }
 		    int id(const Arc& arc) const {
 		      return (Parent::id(static_cast<const Edge&>(arc)) << 1) +
 		        (arc.forward ? 0 : 1);
+		    }
 		    Arc arcFromId(int ix) const {
 		      return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0);
+		    }
 		    int maxArcId() const {
 		      return (Parent::maxEdgeId() << 1) + 1;
+		    }
 		    bool direction(const Arc& arc) const {
 		      return arc.forward;
+		    }
 		    Arc direct(const Edge& arc, bool dir) const {
 		      return Arc(arc, dir);
+		    }
 		    int arcNum() const {
 		      return 2 * Parent::edgeNum();
+		    }
 		    int edgeNum() const {
 		      return Parent::edgeNum();
+		    }
 		  };
+		}
 		#endif

0 comments (0 inline)

RhodeCode

Login to your account