Index: .hgignore
===================================================================
--- .hgignore (revision 400)
+++ .hgignore (revision 298)
@@ -37,5 +37,4 @@
^objs.*/.*
^test/[a-z_]*$
-^tools/[a-z-_]*$
^demo/.*_demo$
^build/.*
Index: .hgtags
===================================================================
--- .hgtags (revision 334)
+++ .hgtags (revision 334)
@@ -0,0 +1,1 @@
+58f1a3144134042f6367fceb7eb29ee8a094d843 r1.0
Index: Makefile.am
===================================================================
--- Makefile.am (revision 375)
+++ Makefile.am (revision 321)
@@ -1,5 +1,3 @@
ACLOCAL_AMFLAGS = -I m4
-
-AM_CXXFLAGS = $(WARNINGCXXFLAGS)
AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
Index: configure.ac
===================================================================
--- configure.ac (revision 375)
+++ configure.ac (revision 310)
@@ -19,4 +19,6 @@
AC_CONFIG_SRCDIR([lemon/list_graph.h])
AC_CONFIG_HEADERS([config.h lemon/config.h])
+
+lx_cmdline_cxxflags_set=${CXXFLAGS+set}
dnl Do compilation tests using the C++ compiler.
@@ -45,8 +47,7 @@
dnl Set custom compiler flags when using g++.
-if test "$GXX" = yes -a "$ICC" = no; then
- WARNINGCXXFLAGS="-Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
+if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes -a "$ICC" = no; then
+ CXXFLAGS="$CXXFLAGS -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
fi
-AC_SUBST([WARNINGCXXFLAGS])
dnl Checks for libraries.
@@ -113,5 +114,5 @@
echo
echo C++ compiler.................. : $CXX
-echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
+echo C++ compiles flags............ : $CXXFLAGS
echo
#echo GLPK support.................. : $lx_glpk_found
Index: doc/CMakeLists.txt
===================================================================
--- doc/CMakeLists.txt (revision 347)
+++ doc/CMakeLists.txt (revision 225)
@@ -14,5 +14,4 @@
COMMAND rm -rf gen-images
COMMAND mkdir gen-images
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
Index: doc/Doxyfile.in
===================================================================
--- doc/Doxyfile.in (revision 379)
+++ doc/Doxyfile.in (revision 316)
@@ -67,5 +67,5 @@
ENABLED_SECTIONS =
MAX_INITIALIZER_LINES = 5
-SHOW_USED_FILES = NO
+SHOW_USED_FILES = YES
SHOW_DIRECTORIES = YES
SHOW_FILES = YES
Index: doc/Makefile.am
===================================================================
--- doc/Makefile.am (revision 349)
+++ doc/Makefile.am (revision 317)
@@ -15,5 +15,4 @@
DOC_EPS_IMAGES18 = \
- grid_graph.eps \
nodeshape_0.eps \
nodeshape_1.eps \
Index: doc/groups.dox
===================================================================
--- doc/groups.dox (revision 403)
+++ doc/groups.dox (revision 330)
@@ -41,16 +41,4 @@
some graph features like arc/edge or node deletion.
-Alteration of standard containers need a very limited number of
-operations, these together satisfy the everyday requirements.
-In the case of graph structures, different operations are needed which do
-not alter the physical graph, but gives another view. If some nodes or
-arcs have to be hidden or the reverse oriented graph have to be used, then
-this is the case. It also may happen that in a flow implementation
-the residual graph can be accessed by another algorithm, or a node-set
-is to be shrunk for another algorithm.
-LEMON also provides a variety of graphs for these requirements called
-\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
-in conjunction with other graph representations.
-
You are free to use the graph structure that fit your requirements
the best, most graph algorithms and auxiliary data structures can be used
@@ -58,14 +46,4 @@
See also: \ref graph_concepts "Graph Structure Concepts".
-*/
-
-/**
-@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
-@ingroup graphs
-\brief Graph types between real graphs and graph adaptors.
-
-This group describes 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.
*/
@@ -156,12 +134,4 @@
/**
-@defgroup matrices Matrices
-@ingroup datas
-\brief Two dimensional data storages implemented in LEMON.
-
-This group describes two dimensional data storages implemented in LEMON.
-*/
-
-/**
@defgroup paths Path Structures
@ingroup datas
@@ -215,140 +185,4 @@
/**
-@defgroup max_flow Maximum Flow Algorithms
-@ingroup algs
-\brief Algorithms for finding maximum flows.
-
-This group describes the algorithms for finding maximum flows and
-feasible circulations.
-
-The maximum flow problem is to find a flow between a single source and
-a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
-directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
-function and given \f$s, t \in V\f$ source and target node. The
-maximum flow is the \f$f_a\f$ solution of the next optimization problem:
-
-\f[ 0 \le f_a \le c_a \f]
-\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
-\qquad \forall u \in V \setminus \{s,t\}\f]
-\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
-
-LEMON contains several algorithms for solving maximum flow problems:
-- \ref lemon::EdmondsKarp "Edmonds-Karp"
-- \ref lemon::Preflow "Goldberg's Preflow algorithm"
-- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
-- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
-
-In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
-fastest method to compute the maximum flow. All impelementations
-provides functions to query the minimum cut, which is the dual linear
-programming problem of the maximum flow.
-*/
-
-/**
-@defgroup min_cost_flow Minimum Cost Flow Algorithms
-@ingroup algs
-
-\brief Algorithms for finding minimum cost flows and circulations.
-
-This group describes the algorithms for finding minimum cost flows and
-circulations.
-*/
-
-/**
-@defgroup min_cut Minimum Cut Algorithms
-@ingroup algs
-
-\brief Algorithms for finding minimum cut in graphs.
-
-This group describes the algorithms for finding minimum cut in graphs.
-
-The minimum cut problem is to find a non-empty and non-complete
-\f$X\f$ subset of the vertices with minimum overall capacity on
-outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
-\f$c_a: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}c_{uv}\f]
-
-LEMON contains several algorithms related to minimum cut problems:
-
-- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
- in directed graphs
-- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
- calculate minimum cut in undirected graphs
-- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
- pairs minimum cut in undirected graphs
-
-If you want to find minimum cut just between two distinict nodes,
-please see the \ref max_flow "Maximum Flow page".
-*/
-
-/**
-@defgroup graph_prop Connectivity and Other Graph Properties
-@ingroup algs
-\brief Algorithms for discovering the graph properties
-
-This group describes 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 planar Planarity Embedding and Drawing
-@ingroup algs
-\brief Algorithms for planarity checking, embedding and drawing
-
-This group describes the algorithms for planarity checking,
-embedding and drawing.
-
-\image html planar.png
-\image latex planar.eps "Plane graph" width=\textwidth
-*/
-
-/**
-@defgroup matching Matching Algorithms
-@ingroup algs
-\brief Algorithms for finding matchings in graphs and bipartite graphs.
-
-This group contains algorithm objects and functions to calculate
-matchings in graphs and bipartite graphs. The general matching problem is
-finding a subset of the arcs which does not shares common endpoints.
-
-There are several different algorithms for calculate matchings in
-graphs. The matching problems in bipartite graphs are generally
-easier than in general graphs. The goal of the matching optimization
-can be the finding maximum cardinality, maximum weight or minimum cost
-matching. The search can be constrained to find perfect or
-maximum cardinality matching.
-
-LEMON contains the next algorithms:
-- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
- augmenting path algorithm for calculate maximum cardinality matching in
- bipartite graphs
-- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
- algorithm for calculate maximum cardinality matching in bipartite graphs
-- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
- Successive shortest path algorithm for calculate maximum weighted matching
- and maximum weighted bipartite matching in bipartite graph
-- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
- Successive shortest path algorithm for calculate minimum cost maximum
- matching in bipartite graph
-- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
- for calculate maximum cardinality matching in general graph
-- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
- shrinking algorithm for calculate maximum weighted matching in general
- graph
-- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
- Edmond's blossom shrinking algorithm for calculate maximum weighted
- perfect matching in general graph
-
-\image html bipartite_matching.png
-\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
-*/
-
-/**
@defgroup spantree Minimum Spanning Tree Algorithms
@ingroup algs
@@ -360,58 +194,4 @@
/**
-@defgroup auxalg Auxiliary Algorithms
-@ingroup algs
-\brief Auxiliary algorithms implemented in LEMON.
-
-This group describes some algorithms implemented in LEMON
-in order to make it easier to implement complex algorithms.
-*/
-
-/**
-@defgroup approx Approximation Algorithms
-@ingroup algs
-\brief Approximation algorithms.
-
-This group describes the approximation and heuristic algorithms
-implemented in LEMON.
-*/
-
-/**
-@defgroup gen_opt_group General Optimization Tools
-\brief This group describes some general optimization frameworks
-implemented in LEMON.
-
-This group describes 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 describes Lp and Mip solver interfaces for LEMON. The
-various LP solvers could be used in the same manner with this
-interface.
-*/
-
-/**
-@defgroup lp_utils Tools for Lp and Mip Solvers
-@ingroup lp_group
-\brief Helper tools to the Lp and Mip solvers.
-
-This group adds some helper tools to general optimization framework
-implemented in LEMON.
-*/
-
-/**
-@defgroup metah Metaheuristics
-@ingroup gen_opt_group
-\brief Metaheuristics for LEMON library.
-
-This group describes some metaheuristic optimization tools.
-*/
-
-/**
@defgroup utils Tools and Utilities
\brief Tools and utilities for programming in LEMON
@@ -459,11 +239,11 @@
This group describes the tools for importing and exporting graphs
-and graph related data. Now it supports the \ref lgf-format
-"LEMON Graph Format", the \c DIMACS format and the encapsulated
+and graph related data. Now it supports the LEMON format
+and the encapsulated postscript (EPS) format.
postscript (EPS) format.
*/
/**
-@defgroup lemon_io LEMON Graph Format
+@defgroup lemon_io LEMON Input-Output
@ingroup io_group
\brief Reading and writing LEMON Graph Format.
@@ -480,20 +260,4 @@
This group describes general \c EPS drawing methods and special
graph exporting tools.
-*/
-
-/**
-@defgroup dimacs_group DIMACS format
-@ingroup io_group
-\brief Read and write files in DIMACS format
-
-Tools to read a digraph from or write it to a file in DIMACS format data.
-*/
-
-/**
-@defgroup nauty_group NAUTY Format
-@ingroup io_group
-\brief Read \e Nauty format
-
-Tool to read graphs from \e Nauty format data.
*/
@@ -540,5 +304,5 @@
@ingroup concept
\brief Skeleton and concept checking classes for maps
-
+
This group describes the skeletons and concept checking classes of maps.
*/
@@ -555,12 +319,2 @@
build the library.
*/
-
-/**
-@defgroup tools Standalone utility applications
-
-Some utility applications are listed here.
-
-The standard compilation procedure (./configure;make) will compile
-them, as well.
-*/
-
Index: c/images/grid_graph.eps
===================================================================
--- doc/images/grid_graph.eps (revision 347)
+++ (revision )
@@ -1,286 +1,0 @@
-%!PS-Adobe-2.0 EPSF-2.0
-%%Title: Grid undirected graph
-%%Copyright: (C) 2006 LEMON Project
-%%Creator: LEMON, graphToEps()
-%%CreationDate: Fri Sep 29 11:55:56 2006
-%%BoundingBox: 0 0 985 1144
-%%EndComments
-/lb { setlinewidth setrgbcolor newpath moveto
- 4 2 roll 1 index 1 index curveto stroke } bind def
-/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
-/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
-/sq { newpath 2 index 1 index add 2 index 2 index add moveto
- 2 index 1 index sub 2 index 2 index add lineto
- 2 index 1 index sub 2 index 2 index sub lineto
- 2 index 1 index add 2 index 2 index sub lineto
- closepath pop pop pop} bind def
-/di { newpath 2 index 1 index add 2 index moveto
- 2 index 2 index 2 index add lineto
- 2 index 1 index sub 2 index lineto
- 2 index 2 index 2 index sub lineto
- closepath pop pop pop} bind def
-/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
- setrgbcolor 1.1 div c fill
- } bind def
-/arrl 1 def
-/arrw 0.3 def
-/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
-/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
- /w exch def /len exch def
- newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
- len w sub arrl sub dx dy lrl
- arrw dy dx neg lrl
- dx arrl w add mul dy w 2 div arrw add mul sub
- dy arrl w add mul dx w 2 div arrw add mul add rlineto
- dx arrl w add mul neg dy w 2 div arrw add mul sub
- dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
- arrw dy dx neg lrl
- len w sub arrl sub neg dx dy lrl
- closepath fill } bind def
-/cshow { 2 index 2 index moveto dup stringwidth pop
- neg 2 div fosi .35 mul neg rmoveto show pop pop} def
-
-gsave
-2 2 scale
-50 40 translate
-5.5000 5.5000 scale
-% 1.14018 1.14018 translate
-%Edges:
-gsave
-70 80 70 90 0 0 0 0.5000 l
-70 70 70 80 0 0 0 0.5000 l
-70 60 70 70 0 0 0 0.5000 l
-70 50 70 60 0 0 0 0.5000 l
-70 40 70 50 0 0 0 0.5000 l
-70 30 70 40 0 0 0 0.5000 l
-70 20 70 30 0 0 0 0.5000 l
-70 10 70 20 0 0 0 0.5000 l
-70 0 70 10 0 0 0 0.5000 l
-60 80 60 90 0 0 0 0.5000 l
-60 70 60 80 0 0 0 0.5000 l
-60 60 60 70 0 0 0 0.5000 l
-60 50 60 60 0 0 0 0.5000 l
-60 40 60 50 0 0 0 0.5000 l
-60 30 60 40 0 0 0 0.5000 l
-60 20 60 30 0 0 0 0.5000 l
-60 10 60 20 0 0 0 0.5000 l
-60 0 60 10 0 0 0 0.5000 l
-50 80 50 90 0 0 0 0.5000 l
-50 70 50 80 0 0 0 0.5000 l
-50 60 50 70 0 0 0 0.5000 l
-50 50 50 60 0 0 0 0.5000 l
-50 40 50 50 0 0 0 0.5000 l
-50 30 50 40 0 0 0 0.5000 l
-50 20 50 30 0 0 0 0.5000 l
-50 10 50 20 0 0 0 0.5000 l
-50 0 50 10 0 0 0 0.5000 l
-40 80 40 90 0 0 0 0.5000 l
-40 70 40 80 0 0 0 0.5000 l
-40 60 40 70 0 0 0 0.5000 l
-40 50 40 60 0 0 0 0.5000 l
-40 40 40 50 0 0 0 0.5000 l
-40 30 40 40 0 0 0 0.5000 l
-40 20 40 30 0 0 0 0.5000 l
-40 10 40 20 0 0 0 0.5000 l
-40 0 40 10 0 0 0 0.5000 l
-30 80 30 90 0 0 0 0.5000 l
-30 70 30 80 0 0 0 0.5000 l
-30 60 30 70 0 0 0 0.5000 l
-30 50 30 60 0 0 0 0.5000 l
-30 40 30 50 0 0 0 0.5000 l
-30 30 30 40 0 0 0 0.5000 l
-30 20 30 30 0 0 0 0.5000 l
-30 10 30 20 0 0 0 0.5000 l
-30 0 30 10 0 0 0 0.5000 l
-20 80 20 90 0 0 0 0.5000 l
-20 70 20 80 0 0 0 0.5000 l
-20 60 20 70 0 0 0 0.5000 l
-20 50 20 60 0 0 0 0.5000 l
-20 40 20 50 0 0 0 0.5000 l
-20 30 20 40 0 0 0 0.5000 l
-20 20 20 30 0 0 0 0.5000 l
-20 10 20 20 0 0 0 0.5000 l
-20 0 20 10 0 0 0 0.5000 l
-10 80 10 90 0 0 0 0.5000 l
-10 70 10 80 0 0 0 0.5000 l
-10 60 10 70 0 0 0 0.5000 l
-10 50 10 60 0 0 0 0.5000 l
-10 40 10 50 0 0 0 0.5000 l
-10 30 10 40 0 0 0 0.5000 l
-10 20 10 30 0 0 0 0.5000 l
-10 10 10 20 0 0 0 0.5000 l
-10 0 10 10 0 0 0 0.5000 l
-0 80 0 90 0 0 0 0.5000 l
-0 70 0 80 0 0 0 0.5000 l
-0 60 0 70 0 0 0 0.5000 l
-0 50 0 60 0 0 0 0.5000 l
-0 40 0 50 0 0 0 0.5000 l
-0 30 0 40 0 0 0 0.5000 l
-0 20 0 30 0 0 0 0.5000 l
-0 10 0 20 0 0 0 0.5000 l
-0 0 0 10 0 0 0 0.5000 l
-60 90 70 90 0 0 0 0.5000 l
-60 80 70 80 0 0 0 0.5000 l
-60 70 70 70 0 0 0 0.5000 l
-60 60 70 60 0 0 0 0.5000 l
-60 50 70 50 0 0 0 0.5000 l
-60 40 70 40 0 0 0 0.5000 l
-60 30 70 30 0 0 0 0.5000 l
-60 20 70 20 0 0 0 0.5000 l
-60 10 70 10 0 0 0 0.5000 l
-60 0 70 0 0 0 0 0.5000 l
-50 90 60 90 0 0 0 0.5000 l
-50 80 60 80 0 0 0 0.5000 l
-50 70 60 70 0 0 0 0.5000 l
-50 60 60 60 0 0 0 0.5000 l
-50 50 60 50 0 0 0 0.5000 l
-50 40 60 40 0 0 0 0.5000 l
-50 30 60 30 0 0 0 0.5000 l
-50 20 60 20 0 0 0 0.5000 l
-50 10 60 10 0 0 0 0.5000 l
-50 0 60 0 0 0 0 0.5000 l
-40 90 50 90 0 0 0 0.5000 l
-40 80 50 80 0 0 0 0.5000 l
-40 70 50 70 0 0 0 0.5000 l
-40 60 50 60 0 0 0 0.5000 l
-40 50 50 50 0 0 0 0.5000 l
-40 40 50 40 0 0 0 0.5000 l
-40 30 50 30 0 0 0 0.5000 l
-40 20 50 20 0 0 0 0.5000 l
-40 10 50 10 0 0 0 0.5000 l
-40 0 50 0 0 0 0 0.5000 l
-30 90 40 90 0 0 0 0.5000 l
-30 80 40 80 0 0 0 0.5000 l
-30 70 40 70 0 0 0 0.5000 l
-30 60 40 60 0 0 0 0.5000 l
-30 50 40 50 0 0 0 0.5000 l
-30 40 40 40 0 0 0 0.5000 l
-30 30 40 30 0 0 0 0.5000 l
-30 20 40 20 0 0 0 0.5000 l
-30 10 40 10 0 0 0 0.5000 l
-30 0 40 0 0 0 0 0.5000 l
-20 90 30 90 0 0 0 0.5000 l
-20 80 30 80 0 0 0 0.5000 l
-20 70 30 70 0 0 0 0.5000 l
-20 60 30 60 0 0 0 0.5000 l
-20 50 30 50 0 0 0 0.5000 l
-20 40 30 40 0 0 0 0.5000 l
-20 30 30 30 0 0 0 0.5000 l
-20 20 30 20 0 0 0 0.5000 l
-20 10 30 10 0 0 0 0.5000 l
-20 0 30 0 0 0 0 0.5000 l
-10 90 20 90 0 0 0 0.5000 l
-10 80 20 80 0 0 0 0.5000 l
-10 70 20 70 0 0 0 0.5000 l
-10 60 20 60 0 0 0 0.5000 l
-10 50 20 50 0 0 0 0.5000 l
-10 40 20 40 0 0 0 0.5000 l
-10 30 20 30 0 0 0 0.5000 l
-10 20 20 20 0 0 0 0.5000 l
-10 10 20 10 0 0 0 0.5000 l
-10 0 20 0 0 0 0 0.5000 l
-0 90 10 90 0 0 0 0.5000 l
-0 80 10 80 0 0 0 0.5000 l
-0 70 10 70 0 0 0 0.5000 l
-0 60 10 60 0 0 0 0.5000 l
-0 50 10 50 0 0 0 0.5000 l
-0 40 10 40 0 0 0 0.5000 l
-0 30 10 30 0 0 0 0.5000 l
-0 20 10 20 0 0 0 0.5000 l
-0 10 10 10 0 0 0 0.5000 l
-0 0 10 0 0 0 0 0.5000 l
-grestore
-%Nodes:
-gsave
-70 90 1.4000 0 0 0 nc
-70 80 1.4000 1 1 1 nc
-70 70 1.4000 1 1 1 nc
-70 60 1.4000 1 1 1 nc
-70 50 1.4000 1 1 1 nc
-70 40 1.4000 1 1 1 nc
-70 30 1.4000 1 1 1 nc
-70 20 1.4000 1 1 1 nc
-70 10 1.4000 1 1 1 nc
-70 0 1.4000 0 0 0 nc
-60 90 1.4000 1 1 1 nc
-60 80 1.4000 1 1 1 nc
-60 70 1.4000 1 1 1 nc
-60 60 1.4000 1 1 1 nc
-60 50 1.4000 1 1 1 nc
-60 40 1.4000 1 1 1 nc
-60 30 1.4000 1 1 1 nc
-60 20 1.4000 1 1 1 nc
-60 10 1.4000 1 1 1 nc
-60 0 1.4000 1 1 1 nc
-50 90 1.4000 1 1 1 nc
-50 80 1.4000 1 1 1 nc
-50 70 1.4000 1 1 1 nc
-50 60 1.4000 1 1 1 nc
-50 50 1.4000 1 1 1 nc
-50 40 1.4000 1 1 1 nc
-50 30 1.4000 1 1 1 nc
-50 20 1.4000 1 1 1 nc
-50 10 1.4000 1 1 1 nc
-50 0 1.4000 1 1 1 nc
-40 90 1.4000 1 1 1 nc
-40 80 1.4000 1 1 1 nc
-40 70 1.4000 1 1 1 nc
-40 60 1.4000 1 1 1 nc
-40 50 1.4000 1 1 1 nc
-40 40 1.4000 1 1 1 nc
-40 30 1.4000 1 1 1 nc
-40 20 1.4000 1 1 1 nc
-40 10 1.4000 1 1 1 nc
-40 0 1.4000 1 1 1 nc
-30 90 1.4000 1 1 1 nc
-30 80 1.4000 1 1 1 nc
-30 70 1.4000 1 1 1 nc
-30 60 1.4000 1 1 1 nc
-30 50 1.4000 1 1 1 nc
-30 40 1.4000 1 1 1 nc
-30 30 1.4000 1 1 1 nc
-30 20 1.4000 1 1 1 nc
-30 10 1.4000 1 1 1 nc
-30 0 1.4000 1 1 1 nc
-20 90 1.4000 1 1 1 nc
-20 80 1.4000 1 1 1 nc
-20 70 1.4000 1 1 1 nc
-20 60 1.4000 1 1 1 nc
-20 50 1.4000 1 1 1 nc
-20 40 1.4000 1 1 1 nc
-20 30 1.4000 1 1 1 nc
-20 20 1.4000 1 1 1 nc
-20 10 1.4000 1 1 1 nc
-20 0 1.4000 1 1 1 nc
-10 90 1.4000 1 1 1 nc
-10 80 1.4000 1 1 1 nc
-10 70 1.4000 1 1 1 nc
-10 60 1.4000 1 1 1 nc
-10 50 1.4000 1 1 1 nc
-10 40 1.4000 1 1 1 nc
-10 30 1.4000 1 1 1 nc
-10 20 1.4000 1 1 1 nc
-10 10 1.4000 1 1 1 nc
-10 0 1.4000 1 1 1 nc
-0 90 1.4000 0 0 0 nc
-0 80 1.4000 1 1 1 nc
-0 70 1.4000 1 1 1 nc
-0 60 1.4000 1 1 1 nc
-0 50 1.4000 1 1 1 nc
-0 40 1.4000 1 1 1 nc
-0 30 1.4000 1 1 1 nc
-0 20 1.4000 1 1 1 nc
-0 10 1.4000 1 1 1 nc
-0 0 1.4000 0 0 0 nc
-grestore
-gsave
-/fosi 3.5 def
-(Helvetica) findfont fosi scalefont setfont
-0 0 0 setrgbcolor
-0 95 ((0,height-1)) cshow
-67 95 ((width-1,height-1)) cshow
-0 -5 ((0,0)) cshow
-70 -5 ((width-1,0)) cshow
-grestore
-grestore
-showpage
Index: doc/mainpage.dox
===================================================================
--- doc/mainpage.dox (revision 314)
+++ doc/mainpage.dox (revision 332)
@@ -42,15 +42,4 @@
\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 page that tells you
-\ref getstart "How to start using LEMON".
-
-If you
-want to see how LEMON works, see
-some \ref demoprograms "demo programs".
-
If you know what you are looking for then try to find it under the
Modules
Index: doc/migration.dox
===================================================================
--- doc/migration.dox (revision 355)
+++ doc/migration.dox (revision 314)
@@ -26,5 +26,5 @@
Many of these changes adjusted automatically by the
-lemon-0.x-to-1.x.sh tool. Those requiring manual
+script/lemon-0.x-to-1.x.sh tool. Those requiring manual
update are typeset boldface.
@@ -54,9 +54,7 @@
\warning
-The lemon-0.x-to-1.x.sh script replaces the words \c graph,
-\c ugraph, \c edge and \c uedge in your own identifiers and in
-strings, comments etc. as well as in all LEMON specific identifiers.
-So use the script carefully and make a backup copy of your source files
-before applying the script to them.
+The script/lemon-0.x-to-1.x.sh tool replaces all instances of
+the words \c graph, \c digraph, \c edge and \c arc, so it replaces them
+in strings, comments etc. as well as in all identifiers.
\section migration-lgf LGF tools
Index: lemon/Makefile.am
===================================================================
--- lemon/Makefile.am (revision 419)
+++ lemon/Makefile.am (revision 259)
@@ -13,5 +13,5 @@
lemon/random.cc
-#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) $(AM_CXXFLAGS)
+#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
@@ -21,5 +21,4 @@
lemon/bfs.h \
lemon/bin_heap.h \
- lemon/circulation.h \
lemon/color.h \
lemon/concept_check.h \
@@ -29,11 +28,6 @@
lemon/dijkstra.h \
lemon/dim2.h \
- lemon/dimacs.h \
- lemon/elevator.h \
lemon/error.h \
- lemon/full_graph.h \
lemon/graph_to_eps.h \
- lemon/grid_graph.h \
- lemon/hypercube_graph.h \
lemon/kruskal.h \
lemon/lgf_reader.h \
@@ -42,11 +36,7 @@
lemon/maps.h \
lemon/math.h \
- lemon/max_matching.h \
- lemon/nauty_reader.h \
lemon/path.h \
- lemon/preflow.h \
lemon/random.h \
lemon/smart_graph.h \
- lemon/suurballe.h \
lemon/time_measure.h \
lemon/tolerance.h \
Index: lemon/bfs.h
===================================================================
--- lemon/bfs.h (revision 341)
+++ lemon/bfs.h (revision 301)
@@ -52,5 +52,5 @@
///Instantiates a PredMap.
- ///This function instantiates a PredMap.
+ ///This function instantiates a PredMap.
///\param g is the digraph, to which we would like to define the
///PredMap.
@@ -81,5 +81,6 @@
///The type of the map that indicates which nodes are reached.
- ///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ ///The type of the map that indicates which nodes are reached.
+ ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap ReachedMap;
///Instantiates a ReachedMap.
Index: lemon/bits/alteration_notifier.h
===================================================================
--- lemon/bits/alteration_notifier.h (revision 373)
+++ lemon/bits/alteration_notifier.h (revision 314)
@@ -36,60 +36,59 @@
// a container.
//
- // The simple graphs can be refered as two containers: a node container
- // and an edge container. But they do not store values directly, they
- // are just key continars for more value containers, which are the
- // node and edge maps.
- //
- // The node and edge sets of the graphs can be changed as we add or erase
+ // The simple graph's can be refered as two containers, one node container
+ // and one edge container. But they are not standard containers they
+ // does not store values directly they are just key continars for more
+ // value containers which are the node and edge maps.
+ //
+ // The graph's node and edge sets can be changed as we add or erase
// nodes and edges in the graph. LEMON would like to handle easily
// that the node and edge maps should contain values for all nodes or
// edges. If we want to check on every indicing if the map contains
// the current indicing key that cause a drawback in the performance
- // in the library. We use another solution: we notify all maps about
+ // in the library. We use another solution we notify all maps about
// an alteration in the graph, which cause only drawback on the
// alteration of the graph.
//
- // This class provides an interface to a node or edge container.
- // The first() and next() member functions make possible
- // to iterate on the keys of the container.
- // The id() function returns an integer id for each key.
- // The maxId() function gives back an upper bound of the ids.
+ // This class provides an interface to the container. The \e first() and \e
+ // next() member functions make possible to iterate on the keys of the
+ // container. The \e id() function returns an integer id for each key.
+ // The \e maxId() function gives back an upper bound of the ids.
//
// For the proper functonality of this class, we should notify it
- // about each alteration in the container. The alterations have four type:
- // add(), erase(), build() and clear(). The add() and
- // erase() signal that only one or few items added or erased to or
- // from the graph. If all items are erased from the graph or if a new graph
- // is built from an empty graph, then it can be signaled with the
+ // about each alteration in the container. The alterations have four type
+ // as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
+ // \e erase() signals that only one or few items added or erased to or
+ // from the graph. If all items are erased from the graph or from an empty
+ // graph a new graph is builded then it can be signaled with the
// clear() and build() members. Important rule that if we erase items
- // from graphs we should first signal the alteration and after that erase
+ // from graph we should first signal the alteration and after that erase
// them from the container, on the other way on item addition we should
// first extend the container and just after that signal the alteration.
//
// The alteration can be observed with a class inherited from the
- // ObserverBase nested class. The signals can be handled with
+ // \e ObserverBase nested class. The signals can be handled with
// overriding the virtual functions defined in the base class. The
// observer base can be attached to the notifier with the
- // attach() member and can be detached with detach() function. The
+ // \e attach() member and can be detached with detach() function. The
// alteration handlers should not call any function which signals
// an other alteration in the same notifier and should not
// detach any observer from the notifier.
//
- // Alteration observers try to be exception safe. If an add() or
- // a clear() function throws an exception then the remaining
+ // Alteration observers try to be exception safe. If an \e add() or
+ // a \e clear() function throws an exception then the remaining
// observeres will not be notified and the fulfilled additions will
- // be rolled back by calling the erase() or clear() functions.
- // Hence erase() and clear() should not throw exception.
- // Actullay, they can throw only \ref ImmediateDetach exception,
- // which detach the observer from the notifier.
- //
- // There are some cases, when the alteration observing is not completly
+ // be rolled back by calling the \e erase() or \e clear()
+ // functions. Thence the \e erase() and \e clear() should not throw
+ // exception. Actullay, it can be throw only \ref ImmediateDetach
+ // exception which detach the observer from the notifier.
+ //
+ // There are some place when the alteration observing is not completly
// reliable. If we want to carry out the node degree in the graph
- // as in the \ref InDegMap and we use the reverseArc(), then it cause
+ // as in the \ref InDegMap and we use the reverseEdge that cause
// unreliable functionality. Because the alteration observing signals
- // only erasing and adding but not the reversing, it will stores bad
- // degrees. Apart form that the subgraph adaptors cannot even signal
- // the alterations because just a setting in the filter map can modify
- // the graph and this cannot be watched in any way.
+ // only erasing and adding but not the reversing it will stores bad
+ // degrees. The sub graph adaptors cannot signal the alterations because
+ // just a setting in the filter map can modify the graph and this cannot
+ // be watched in any way.
//
// \param _Container The container which is observed.
@@ -105,11 +104,11 @@
typedef _Item Item;
- // \brief Exception which can be called from clear() and
- // erase().
- //
- // From the clear() and erase() function only this
+ // \brief Exception which can be called from \e clear() and
+ // \e erase().
+ //
+ // From the \e clear() and \e erase() function only this
// exception is allowed to throw. The exception immediatly
// detaches the current observer from the notifier. Because the
- // clear() and erase() should not throw other exceptions
+ // \e clear() and \e erase() should not throw other exceptions
// it can be used to invalidate the observer.
struct ImmediateDetach {};
@@ -123,5 +122,6 @@
// The observer interface contains some pure virtual functions
// to override. The add() and erase() functions are
- // to notify the oberver when one item is added or erased.
+ // to notify the oberver when one item is added or
+ // erased.
//
// The build() and clear() members are to notify the observer
Index: lemon/bits/array_map.h
===================================================================
--- lemon/bits/array_map.h (revision 373)
+++ lemon/bits/array_map.h (revision 314)
@@ -37,9 +37,10 @@
// \brief Graph map based on the array storage.
//
- // The ArrayMap template class is graph map structure that automatically
- // updates the map when a key is added to or erased from the graph.
- // This map uses the allocators to implement the container functionality.
+ // The ArrayMap template class is graph map structure what
+ // automatically updates the map when a key is added to or erased from
+ // the map. This map uses the allocators to implement
+ // the container functionality.
//
- // The template parameters are the Graph, the current Item type and
+ // The template parameters are the Graph the current Item type and
// the Value type of the map.
template
@@ -47,12 +48,12 @@
: public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
public:
- // The graph type.
+ // The graph type of the maps.
typedef _Graph Graph;
- // The item type.
+ // The item type of the map.
typedef _Item Item;
// The reference map tag.
typedef True ReferenceMapTag;
- // The key type of the map.
+ // The key type of the maps.
typedef _Item Key;
// The value type of the map.
@@ -200,5 +201,5 @@
// \brief Adds a new key to the map.
//
- // It adds a new key to the map. It is called by the observer notifier
+ // It adds a new key to the map. It called by the observer notifier
// and it overrides the add() member function of the observer base.
virtual void add(const Key& key) {
@@ -228,5 +229,5 @@
// \brief Adds more new keys to the map.
//
- // It adds more new keys to the map. It is called by the observer notifier
+ // It adds more new keys to the map. It called by the observer notifier
// and it overrides the add() member function of the observer base.
virtual void add(const std::vector& keys) {
@@ -272,5 +273,5 @@
// \brief Erase a key from the map.
//
- // Erase a key from the map. It is called by the observer notifier
+ // Erase a key from the map. It called by the observer notifier
// and it overrides the erase() member function of the observer base.
virtual void erase(const Key& key) {
@@ -281,5 +282,5 @@
// \brief Erase more keys from the map.
//
- // Erase more keys from the map. It is called by the observer notifier
+ // Erase more keys from the map. It called by the observer notifier
// and it overrides the erase() member function of the observer base.
virtual void erase(const std::vector& keys) {
@@ -290,7 +291,7 @@
}
- // \brief Builds the map.
- //
- // It builds the map. It is called by the observer notifier
+ // \brief Buildes the map.
+ //
+ // It buildes the map. It called by the observer notifier
// and it overrides the build() member function of the observer base.
virtual void build() {
@@ -306,5 +307,5 @@
// \brief Clear the map.
//
- // It erase all items from the map. It is called by the observer notifier
+ // It erase all items from the map. It called by the observer notifier
// and it overrides the clear() member function of the observer base.
virtual void clear() {
Index: lemon/bits/base_extender.h
===================================================================
--- lemon/bits/base_extender.h (revision 373)
+++ lemon/bits/base_extender.h (revision 314)
@@ -31,5 +31,5 @@
//\ingroup digraphbits
//\file
-//\brief Extenders for the graph types
+//\brief Extenders for the digraph types
namespace lemon {
Index: lemon/bits/graph_extender.h
===================================================================
--- lemon/bits/graph_extender.h (revision 373)
+++ lemon/bits/graph_extender.h (revision 314)
@@ -30,10 +30,10 @@
//\ingroup graphbits
//\file
-//\brief Extenders for the graph types
+//\brief Extenders for the digraph types
namespace lemon {
// \ingroup graphbits
//
- // \brief Extender for the digraph implementations
+ // \brief Extender for the Digraphs
template
class DigraphExtender : public Base {
Index: lemon/bits/traits.h
===================================================================
--- lemon/bits/traits.h (revision 372)
+++ lemon/bits/traits.h (revision 314)
@@ -219,17 +219,4 @@
template
- struct ArcNumTagIndicator {
- static const bool value = false;
- };
-
- template
- struct ArcNumTagIndicator<
- Graph,
- typename enable_if::type
- > {
- static const bool value = true;
- };
-
- template
struct EdgeNumTagIndicator {
static const bool value = false;
@@ -245,17 +232,4 @@
template
- struct FindArcTagIndicator {
- static const bool value = false;
- };
-
- template
- struct FindArcTagIndicator<
- Graph,
- typename enable_if::type
- > {
- static const bool value = true;
- };
-
- template
struct FindEdgeTagIndicator {
static const bool value = false;
Index: lemon/bits/vector_map.h
===================================================================
--- lemon/bits/vector_map.h (revision 373)
+++ lemon/bits/vector_map.h (revision 314)
@@ -39,7 +39,7 @@
// \brief Graph map based on the std::vector storage.
//
- // The VectorMap template class is graph map structure that automatically
- // updates the map when a key is added to or erased from the graph.
- // This map type uses std::vector to store the values.
+ // The VectorMap template class is graph map structure what
+ // automatically updates the map when a key is added to or erased from
+ // the map. This map type uses the std::vector to store the values.
//
// \tparam _Graph The graph this map is attached to.
@@ -170,5 +170,5 @@
// \brief Adds a new key to the map.
//
- // It adds a new key to the map. It is called by the observer notifier
+ // It adds a new key to the map. It called by the observer notifier
// and it overrides the add() member function of the observer base.
virtual void add(const Key& key) {
@@ -181,5 +181,5 @@
// \brief Adds more new keys to the map.
//
- // It adds more new keys to the map. It is called by the observer notifier
+ // It adds more new keys to the map. It called by the observer notifier
// and it overrides the add() member function of the observer base.
virtual void add(const std::vector& keys) {
@@ -196,5 +196,5 @@
// \brief Erase a key from the map.
//
- // Erase a key from the map. It is called by the observer notifier
+ // Erase a key from the map. It called by the observer notifier
// and it overrides the erase() member function of the observer base.
virtual void erase(const Key& key) {
@@ -204,5 +204,5 @@
// \brief Erase more keys from the map.
//
- // It erases more keys from the map. It is called by the observer notifier
+ // Erase more keys from the map. It called by the observer notifier
// and it overrides the erase() member function of the observer base.
virtual void erase(const std::vector& keys) {
@@ -212,7 +212,7 @@
}
- // \brief Build the map.
- //
- // It builds the map. It is called by the observer notifier
+ // \brief Buildes the map.
+ //
+ // It buildes the map. It called by the observer notifier
// and it overrides the build() member function of the observer base.
virtual void build() {
@@ -224,5 +224,5 @@
// \brief Clear the map.
//
- // It erases all items from the map. It is called by the observer notifier
+ // It erase all items from the map. It called by the observer notifier
// and it overrides the clear() member function of the observer base.
virtual void clear() {
Index: mon/circulation.h
===================================================================
--- lemon/circulation.h (revision 417)
+++ (revision )
@@ -1,755 +1,0 @@
-/* -*- 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_CIRCULATION_H
-#define LEMON_CIRCULATION_H
-
-#include
-#include
-
-///\ingroup max_flow
-///\file
-///\brief Push-relabel algorithm for finding a feasible circulation.
-///
-namespace lemon {
-
- /// \brief Default traits class of Circulation class.
- ///
- /// Default traits class of Circulation class.
- /// \tparam _Diraph Digraph type.
- /// \tparam _LCapMap Lower bound capacity map type.
- /// \tparam _UCapMap Upper bound capacity map type.
- /// \tparam _DeltaMap Delta map type.
- template
- struct CirculationDefaultTraits {
-
- /// \brief The type of the digraph the algorithm runs on.
- typedef _Diraph Digraph;
-
- /// \brief The type of the map that stores the circulation lower
- /// bound.
- ///
- /// The type of the map that stores the circulation lower bound.
- /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
- typedef _LCapMap LCapMap;
-
- /// \brief The type of the map that stores the circulation upper
- /// bound.
- ///
- /// The type of the map that stores the circulation upper bound.
- /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
- typedef _UCapMap UCapMap;
-
- /// \brief The type of the map that stores the lower bound for
- /// the supply of the nodes.
- ///
- /// The type of the map that stores the lower bound for the supply
- /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
- /// concept.
- typedef _DeltaMap DeltaMap;
-
- /// \brief The type of the flow values.
- typedef typename DeltaMap::Value Value;
-
- /// \brief The type of the map that stores the flow values.
- ///
- /// The type of the map that stores the flow values.
- /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
- typedef typename Digraph::template ArcMap FlowMap;
-
- /// \brief Instantiates a FlowMap.
- ///
- /// This function instantiates a \ref FlowMap.
- /// \param digraph The digraph, to which we would like to define
- /// the flow map.
- static FlowMap* createFlowMap(const Digraph& digraph) {
- return new FlowMap(digraph);
- }
-
- /// \brief The elevator type used by the algorithm.
- ///
- /// The elevator type used by the algorithm.
- ///
- /// \sa Elevator
- /// \sa LinkedElevator
- typedef lemon::Elevator Elevator;
-
- /// \brief Instantiates an Elevator.
- ///
- /// This function instantiates an \ref Elevator.
- /// \param digraph The digraph, to which we would like to define
- /// the elevator.
- /// \param max_level The maximum level of the elevator.
- static Elevator* createElevator(const Digraph& digraph, int max_level) {
- return new Elevator(digraph, max_level);
- }
-
- /// \brief The tolerance used by the algorithm
- ///
- /// The tolerance used by the algorithm to handle inexact computation.
- typedef lemon::Tolerance Tolerance;
-
- };
-
- /**
- \brief Push-relabel algorithm for the network circulation problem.
-
- \ingroup max_flow
- This class implements a push-relabel algorithm for the network
- circulation problem.
- It is to find a feasible circulation when lower and upper bounds
- are given for the flow values on the arcs and lower bounds
- are given for the supply values of the nodes.
-
- The exact formulation of this problem is the following.
- Let \f$G=(V,A)\f$ be a digraph,
- \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$,
- \f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation
- \f$f: A\rightarrow\mathbf{R}^+_0\f$ so that
- \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a)
- \geq delta(v) \quad \forall v\in V, \f]
- \f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f]
- \note \f$delta(v)\f$ specifies a lower bound for the supply of node
- \f$v\f$. It can be either positive or negative, however note that
- \f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to
- have a feasible solution.
-
- \note A special case of this problem is when
- \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$
- will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.
- Thus a feasible solution for the
- \ref min_cost_flow "minimum cost flow" problem can be calculated
- in this way.
-
- \tparam _Digraph The type of the digraph the algorithm runs on.
- \tparam _LCapMap The type of the lower bound capacity map. The default
- map type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap".
- \tparam _UCapMap The type of the upper bound capacity map. The default
- map type is \c _LCapMap.
- \tparam _DeltaMap The type of the map that stores the lower bound
- for the supply of the nodes. The default map type is
- \c _Digraph::ArcMap<_UCapMap::Value>.
- */
-#ifdef DOXYGEN
-template< typename _Digraph,
- typename _LCapMap,
- typename _UCapMap,
- typename _DeltaMap,
- typename _Traits >
-#else
-template< typename _Digraph,
- typename _LCapMap = typename _Digraph::template ArcMap,
- typename _UCapMap = _LCapMap,
- typename _DeltaMap = typename _Digraph::
- template NodeMap,
- typename _Traits=CirculationDefaultTraits<_Digraph, _LCapMap,
- _UCapMap, _DeltaMap> >
-#endif
- class Circulation {
- public:
-
- ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
- typedef _Traits Traits;
- ///The type of the digraph the algorithm runs on.
- typedef typename Traits::Digraph Digraph;
- ///The type of the flow values.
- typedef typename Traits::Value Value;
-
- /// The type of the lower bound capacity map.
- typedef typename Traits::LCapMap LCapMap;
- /// The type of the upper bound capacity map.
- typedef typename Traits::UCapMap UCapMap;
- /// \brief The type of the map that stores the lower bound for
- /// the supply of the nodes.
- typedef typename Traits::DeltaMap DeltaMap;
- ///The type of the flow map.
- typedef typename Traits::FlowMap FlowMap;
-
- ///The type of the elevator.
- typedef typename Traits::Elevator Elevator;
- ///The type of the tolerance.
- typedef typename Traits::Tolerance Tolerance;
-
- private:
-
- TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
-
- const Digraph &_g;
- int _node_num;
-
- const LCapMap *_lo;
- const UCapMap *_up;
- const DeltaMap *_delta;
-
- FlowMap *_flow;
- bool _local_flow;
-
- Elevator* _level;
- bool _local_level;
-
- typedef typename Digraph::template NodeMap ExcessMap;
- ExcessMap* _excess;
-
- Tolerance _tol;
- int _el;
-
- public:
-
- typedef Circulation Create;
-
- ///\name Named Template Parameters
-
- ///@{
-
- template
- struct SetFlowMapTraits : public Traits {
- typedef _FlowMap FlowMap;
- static FlowMap *createFlowMap(const Digraph&) {
- LEMON_ASSERT(false, "FlowMap is not initialized");
- return 0; // ignore warnings
- }
- };
-
- /// \brief \ref named-templ-param "Named parameter" for setting
- /// FlowMap type
- ///
- /// \ref named-templ-param "Named parameter" for setting FlowMap
- /// type.
- template
- struct SetFlowMap
- : public Circulation > {
- typedef Circulation > Create;
- };
-
- template
- struct SetElevatorTraits : public Traits {
- typedef _Elevator Elevator;
- static Elevator *createElevator(const Digraph&, int) {
- LEMON_ASSERT(false, "Elevator is not initialized");
- return 0; // ignore warnings
- }
- };
-
- /// \brief \ref named-templ-param "Named parameter" for setting
- /// Elevator type
- ///
- /// \ref named-templ-param "Named parameter" for setting Elevator
- /// type. If this named parameter is used, then an external
- /// elevator object must be passed to the algorithm using the
- /// \ref elevator(Elevator&) "elevator()" function before calling
- /// \ref run() or \ref init().
- /// \sa SetStandardElevator
- template
- struct SetElevator
- : public Circulation > {
- typedef Circulation > Create;
- };
-
- template
- struct SetStandardElevatorTraits : public Traits {
- typedef _Elevator Elevator;
- static Elevator *createElevator(const Digraph& digraph, int max_level) {
- return new Elevator(digraph, max_level);
- }
- };
-
- /// \brief \ref named-templ-param "Named parameter" for setting
- /// Elevator type with automatic allocation
- ///
- /// \ref named-templ-param "Named parameter" for setting Elevator
- /// type with automatic allocation.
- /// The Elevator should have standard constructor interface to be
- /// able to automatically created by the algorithm (i.e. the
- /// digraph and the maximum level should be passed to it).
- /// However an external elevator object could also be passed to the
- /// algorithm with the \ref elevator(Elevator&) "elevator()" function
- /// before calling \ref run() or \ref init().
- /// \sa SetElevator
- template
- struct SetStandardElevator
- : public Circulation > {
- typedef Circulation > Create;
- };
-
- /// @}
-
- protected:
-
- Circulation() {}
-
- public:
-
- /// The constructor of the class.
-
- /// The constructor of the class.
- /// \param g The digraph the algorithm runs on.
- /// \param lo The lower bound capacity of the arcs.
- /// \param up The upper bound capacity of the arcs.
- /// \param delta The lower bound for the supply of the nodes.
- Circulation(const Digraph &g,const LCapMap &lo,
- const UCapMap &up,const DeltaMap &delta)
- : _g(g), _node_num(),
- _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false),
- _level(0), _local_level(false), _excess(0), _el() {}
-
- /// Destructor.
- ~Circulation() {
- destroyStructures();
- }
-
-
- private:
-
- void createStructures() {
- _node_num = _el = countNodes(_g);
-
- if (!_flow) {
- _flow = Traits::createFlowMap(_g);
- _local_flow = true;
- }
- if (!_level) {
- _level = Traits::createElevator(_g, _node_num);
- _local_level = true;
- }
- if (!_excess) {
- _excess = new ExcessMap(_g);
- }
- }
-
- void destroyStructures() {
- if (_local_flow) {
- delete _flow;
- }
- if (_local_level) {
- delete _level;
- }
- if (_excess) {
- delete _excess;
- }
- }
-
- public:
-
- /// Sets the lower bound capacity map.
-
- /// Sets the lower bound capacity map.
- /// \return (*this)
- Circulation& lowerCapMap(const LCapMap& map) {
- _lo = ↦
- return *this;
- }
-
- /// Sets the upper bound capacity map.
-
- /// Sets the upper bound capacity map.
- /// \return (*this)
- Circulation& upperCapMap(const LCapMap& map) {
- _up = ↦
- return *this;
- }
-
- /// Sets the lower bound map for the supply of the nodes.
-
- /// Sets the lower bound map for the supply of the nodes.
- /// \return (*this)
- Circulation& deltaMap(const DeltaMap& map) {
- _delta = ↦
- return *this;
- }
-
- /// \brief Sets the flow map.
- ///
- /// Sets the flow map.
- /// If you don't use this function before calling \ref run() or
- /// \ref init(), an instance will be allocated automatically.
- /// The destructor deallocates this automatically allocated map,
- /// of course.
- /// \return (*this)
- Circulation& flowMap(FlowMap& map) {
- if (_local_flow) {
- delete _flow;
- _local_flow = false;
- }
- _flow = ↦
- return *this;
- }
-
- /// \brief Sets the elevator used by algorithm.
- ///
- /// Sets the elevator used by algorithm.
- /// If you don't use this function before calling \ref run() or
- /// \ref init(), an instance will be allocated automatically.
- /// The destructor deallocates this automatically allocated elevator,
- /// of course.
- /// \return (*this)
- Circulation& elevator(Elevator& elevator) {
- if (_local_level) {
- delete _level;
- _local_level = false;
- }
- _level = &elevator;
- return *this;
- }
-
- /// \brief Returns a const reference to the elevator.
- ///
- /// Returns a const reference to the elevator.
- ///
- /// \pre Either \ref run() or \ref init() must be called before
- /// using this function.
- const Elevator& elevator() {
- return *_level;
- }
-
- /// \brief Sets the tolerance used by algorithm.
- ///
- /// Sets the tolerance used by algorithm.
- Circulation& tolerance(const Tolerance& tolerance) const {
- _tol = tolerance;
- return *this;
- }
-
- /// \brief Returns a const reference to the tolerance.
- ///
- /// Returns a const reference to the tolerance.
- const Tolerance& tolerance() const {
- return tolerance;
- }
-
- /// \name Execution Control
- /// The simplest way to execute the algorithm is to call \ref run().\n
- /// If you need more control on the initial solution or the execution,
- /// first you have to call one of the \ref init() functions, then
- /// the \ref start() function.
-
- ///@{
-
- /// Initializes the internal data structures.
-
- /// Initializes the internal data structures and sets all flow values
- /// to the lower bound.
- void init()
- {
- createStructures();
-
- for(NodeIt n(_g);n!=INVALID;++n) {
- _excess->set(n, (*_delta)[n]);
- }
-
- for (ArcIt e(_g);e!=INVALID;++e) {
- _flow->set(e, (*_lo)[e]);
- _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]);
- _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]);
- }
-
- // global relabeling tested, but in general case it provides
- // worse performance for random digraphs
- _level->initStart();
- for(NodeIt n(_g);n!=INVALID;++n)
- _level->initAddItem(n);
- _level->initFinish();
- for(NodeIt n(_g);n!=INVALID;++n)
- if(_tol.positive((*_excess)[n]))
- _level->activate(n);
- }
-
- /// Initializes the internal data structures using a greedy approach.
-
- /// Initializes the internal data structures using a greedy approach
- /// to construct the initial solution.
- void greedyInit()
- {
- createStructures();
-
- for(NodeIt n(_g);n!=INVALID;++n) {
- _excess->set(n, (*_delta)[n]);
- }
-
- for (ArcIt e(_g);e!=INVALID;++e) {
- if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
- _flow->set(e, (*_up)[e]);
- _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]);
- _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]);
- } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
- _flow->set(e, (*_lo)[e]);
- _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]);
- _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]);
- } else {
- Value fc = -(*_excess)[_g.target(e)];
- _flow->set(e, fc);
- _excess->set(_g.target(e), 0);
- _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc);
- }
- }
-
- _level->initStart();
- for(NodeIt n(_g);n!=INVALID;++n)
- _level->initAddItem(n);
- _level->initFinish();
- for(NodeIt n(_g);n!=INVALID;++n)
- if(_tol.positive((*_excess)[n]))
- _level->activate(n);
- }
-
- ///Executes the algorithm
-
- ///This function executes the algorithm.
- ///
- ///\return \c true if a feasible circulation is found.
- ///
- ///\sa barrier()
- ///\sa barrierMap()
- bool start()
- {
-
- Node act;
- Node bact=INVALID;
- Node last_activated=INVALID;
- while((act=_level->highestActive())!=INVALID) {
- int actlevel=(*_level)[act];
- int mlevel=_node_num;
- Value exc=(*_excess)[act];
-
- for(OutArcIt e(_g,act);e!=INVALID; ++e) {
- Node v = _g.target(e);
- Value fc=(*_up)[e]-(*_flow)[e];
- if(!_tol.positive(fc)) continue;
- if((*_level)[v]set(e, (*_flow)[e] + exc);
- _excess->set(v, (*_excess)[v] + exc);
- if(!_level->active(v) && _tol.positive((*_excess)[v]))
- _level->activate(v);
- _excess->set(act,0);
- _level->deactivate(act);
- goto next_l;
- }
- else {
- _flow->set(e, (*_up)[e]);
- _excess->set(v, (*_excess)[v] + fc);
- if(!_level->active(v) && _tol.positive((*_excess)[v]))
- _level->activate(v);
- exc-=fc;
- }
- }
- else if((*_level)[v]set(e, (*_flow)[e] - exc);
- _excess->set(v, (*_excess)[v] + exc);
- if(!_level->active(v) && _tol.positive((*_excess)[v]))
- _level->activate(v);
- _excess->set(act,0);
- _level->deactivate(act);
- goto next_l;
- }
- else {
- _flow->set(e, (*_lo)[e]);
- _excess->set(v, (*_excess)[v] + fc);
- if(!_level->active(v) && _tol.positive((*_excess)[v]))
- _level->activate(v);
- exc-=fc;
- }
- }
- else if((*_level)[v]set(act, exc);
- if(!_tol.positive(exc)) _level->deactivate(act);
- else if(mlevel==_node_num) {
- _level->liftHighestActiveToTop();
- _el = _node_num;
- return false;
- }
- else {
- _level->liftHighestActive(mlevel+1);
- if(_level->onLevel(actlevel)==0) {
- _el = actlevel;
- return false;
- }
- }
- next_l:
- ;
- }
- return true;
- }
-
- /// Runs the algorithm.
-
- /// This function runs the algorithm.
- ///
- /// \return \c true if a feasible circulation is found.
- ///
- /// \note Apart from the return value, c.run() is just a shortcut of
- /// the following code.
- /// \code
- /// c.greedyInit();
- /// c.start();
- /// \endcode
- bool run() {
- greedyInit();
- return start();
- }
-
- /// @}
-
- /// \name Query Functions
- /// The results of the circulation algorithm can be obtained using
- /// these functions.\n
- /// Either \ref run() or \ref start() should be called before
- /// using them.
-
- ///@{
-
- /// \brief Returns the flow on the given arc.
- ///
- /// Returns the flow on the given arc.
- ///
- /// \pre Either \ref run() or \ref init() must be called before
- /// using this function.
- Value flow(const Arc& arc) const {
- return (*_flow)[arc];
- }
-
- /// \brief Returns a const reference to the flow map.
- ///
- /// Returns a const reference to the arc map storing the found flow.
- ///
- /// \pre Either \ref run() or \ref init() must be called before
- /// using this function.
- const FlowMap& flowMap() {
- return *_flow;
- }
-
- /**
- \brief Returns \c true if the given node is in a barrier.
-
- Barrier is a set \e B of nodes for which
-
- \f[ \sum_{a\in\delta_{out}(B)} upper(a) -
- \sum_{a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f]
-
- holds. The existence of a set with this property prooves that a
- feasible circualtion cannot exist.
-
- This function returns \c true if the given node is in the found
- barrier. If a feasible circulation is found, the function
- gives back \c false for every node.
-
- \pre Either \ref run() or \ref init() must be called before
- using this function.
-
- \sa barrierMap()
- \sa checkBarrier()
- */
- bool barrier(const Node& node)
- {
- return (*_level)[node] >= _el;
- }
-
- /// \brief Gives back a barrier.
- ///
- /// This function sets \c bar to the characteristic vector of the
- /// found barrier. \c bar should be a \ref concepts::WriteMap "writable"
- /// node map with \c bool (or convertible) value type.
- ///
- /// If a feasible circulation is found, the function gives back an
- /// empty set, so \c bar[v] will be \c false for all nodes \c v.
- ///
- /// \note This function calls \ref barrier() for each node,
- /// so it runs in \f$O(n)\f$ time.
- ///
- /// \pre Either \ref run() or \ref init() must be called before
- /// using this function.
- ///
- /// \sa barrier()
- /// \sa checkBarrier()
- template
- void barrierMap(BarrierMap &bar)
- {
- for(NodeIt n(_g);n!=INVALID;++n)
- bar.set(n, (*_level)[n] >= _el);
- }
-
- /// @}
-
- /// \name Checker Functions
- /// The feasibility of the results can be checked using
- /// these functions.\n
- /// Either \ref run() or \ref start() should be called before
- /// using them.
-
- ///@{
-
- ///Check if the found flow is a feasible circulation
-
- ///Check if the found flow is a feasible circulation,
- ///
- bool checkFlow() {
- for(ArcIt e(_g);e!=INVALID;++e)
- if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
- for(NodeIt n(_g);n!=INVALID;++n)
- {
- Value dif=-(*_delta)[n];
- for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
- for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
- if(_tol.negative(dif)) return false;
- }
- return true;
- }
-
- ///Check whether or not the last execution provides a barrier
-
- ///Check whether or not the last execution provides a barrier.
- ///\sa barrier()
- ///\sa barrierMap()
- bool checkBarrier()
- {
- Value delta=0;
- for(NodeIt n(_g);n!=INVALID;++n)
- if(barrier(n))
- delta-=(*_delta)[n];
- for(ArcIt e(_g);e!=INVALID;++e)
- {
- Node s=_g.source(e);
- Node t=_g.target(e);
- if(barrier(s)&&!barrier(t)) delta+=(*_up)[e];
- else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e];
- }
- return _tol.negative(delta);
- }
-
- /// @}
-
- };
-
-}
-
-#endif
Index: mon/dimacs.h
===================================================================
--- lemon/dimacs.h (revision 403)
+++ (revision )
@@ -1,357 +1,0 @@
-/* -*- 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_DIMACS_H
-#define LEMON_DIMACS_H
-
-#include
-#include
-#include
-#include
-#include
-
-/// \ingroup dimacs_group
-/// \file
-/// \brief DIMACS file format reader.
-
-namespace lemon {
-
- /// \addtogroup dimacs_group
- /// @{
-
- /// DIMACS file type descriptor.
- struct DimacsDescriptor
- {
- ///File type enum
- enum Type
- {
- NONE, MIN, MAX, SP, MAT
- };
- ///The file type
- Type type;
- ///The number of nodes in the graph
- int nodeNum;
- ///The number of edges in the graph
- int edgeNum;
- int lineShift;
- /// Constructor. Sets the type to NONE.
- DimacsDescriptor() : type(NONE) {}
- };
-
- ///Discover the type of a DIMACS file
-
- ///It starts seeking the begining of the file for the problem type
- ///and size info. The found data is returned in a special struct
- ///that can be evaluated and passed to the appropriate reader
- ///function.
- DimacsDescriptor dimacsType(std::istream& is)
- {
- DimacsDescriptor r;
- std::string problem,str;
- char c;
- r.lineShift=0;
- while (is >> c)
- switch(c)
- {
- case 'p':
- if(is >> problem >> r.nodeNum >> r.edgeNum)
- {
- getline(is, str);
- r.lineShift++;
- if(problem=="min") r.type=DimacsDescriptor::MIN;
- else if(problem=="max") r.type=DimacsDescriptor::MAX;
- else if(problem=="sp") r.type=DimacsDescriptor::SP;
- else if(problem=="mat") r.type=DimacsDescriptor::MAT;
- else throw FormatError("Unknown problem type");
- return r;
- }
- else
- {
- throw FormatError("Missing or wrong problem type declaration.");
- }
- break;
- case 'c':
- getline(is, str);
- r.lineShift++;
- break;
- default:
- throw FormatError("Unknown DIMACS declaration.");
- }
- throw FormatError("Missing problem type declaration.");
- }
-
-
-
- /// DIMACS minimum cost flow reader function.
- ///
- /// This function reads a minimum cost flow instance from DIMACS format,
- /// i.e. from a DIMACS file having a line starting with
- /// \code
- /// p min
- /// \endcode
- /// At the beginning, \c g is cleared by \c g.clear(). The supply
- /// amount of the nodes are written to \c supply (signed). The
- /// lower bounds, capacities and costs of the arcs are written to
- /// \c lower, \c capacity and \c cost.
- ///
- /// If the file type was previously evaluated by dimacsType(), then
- /// the descriptor struct should be given by the \c dest parameter.
- template
- void readDimacsMin(std::istream& is,
- Digraph &g,
- LowerMap& lower,
- CapacityMap& capacity,
- CostMap& cost,
- SupplyMap& supply,
- DimacsDescriptor desc=DimacsDescriptor())
- {
- g.clear();
- std::vector nodes;
- typename Digraph::Arc e;
- std::string problem, str;
- char c;
- int i, j;
- if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
- if(desc.type!=DimacsDescriptor::MIN)
- throw FormatError("Problem type mismatch");
-
- nodes.resize(desc.nodeNum + 1);
- for (int k = 1; k <= desc.nodeNum; ++k) {
- nodes[k] = g.addNode();
- supply.set(nodes[k], 0);
- }
-
- typename SupplyMap::Value sup;
- typename CapacityMap::Value low;
- typename CapacityMap::Value cap;
- typename CostMap::Value co;
- while (is >> c) {
- switch (c) {
- case 'c': // comment line
- getline(is, str);
- break;
- case 'n': // node definition line
- is >> i >> sup;
- getline(is, str);
- supply.set(nodes[i], sup);
- break;
- case 'a': // arc (arc) definition line
- is >> i >> j >> low >> cap >> co;
- getline(is, str);
- e = g.addArc(nodes[i], nodes[j]);
- lower.set(e, low);
- if (cap >= 0)
- capacity.set(e, cap);
- else
- capacity.set(e, -1);
- cost.set(e, co);
- break;
- }
- }
- }
-
- template
- void _readDimacs(std::istream& is,
- Digraph &g,
- CapacityMap& capacity,
- typename Digraph::Node &s,
- typename Digraph::Node &t,
- DimacsDescriptor desc=DimacsDescriptor()) {
- g.clear();
- s=t=INVALID;
- std::vector nodes;
- typename Digraph::Arc e;
- char c, d;
- int i, j;
- typename CapacityMap::Value _cap;
- std::string str;
- nodes.resize(desc.nodeNum + 1);
- for (int k = 1; k <= desc.nodeNum; ++k) {
- nodes[k] = g.addNode();
- }
-
- while (is >> c) {
- switch (c) {
- case 'c': // comment line
- getline(is, str);
- break;
- case 'n': // node definition line
- if (desc.type==DimacsDescriptor::SP) { // shortest path problem
- is >> i;
- getline(is, str);
- s = nodes[i];
- }
- if (desc.type==DimacsDescriptor::MAX) { // max flow problem
- is >> i >> d;
- getline(is, str);
- if (d == 's') s = nodes[i];
- if (d == 't') t = nodes[i];
- }
- break;
- case 'a': // arc (arc) definition line
- if (desc.type==DimacsDescriptor::SP ||
- desc.type==DimacsDescriptor::MAX) {
- is >> i >> j >> _cap;
- getline(is, str);
- e = g.addArc(nodes[i], nodes[j]);
- capacity.set(e, _cap);
- } else {
- is >> i >> j;
- getline(is, str);
- g.addArc(nodes[i], nodes[j]);
- }
- break;
- }
- }
- }
-
- /// DIMACS maximum flow reader function.
- ///
- /// This function reads a maximum flow instance from DIMACS format,
- /// i.e. from a DIMACS file having a line starting with
- /// \code
- /// p max
- /// \endcode
- /// At the beginning, \c g is cleared by \c g.clear(). The arc
- /// capacities are written to \c capacity and \c s and \c t are
- /// set to the source and the target nodes.
- ///
- /// If the file type was previously evaluated by dimacsType(), then
- /// the descriptor struct should be given by the \c dest parameter.
- template
- void readDimacsMax(std::istream& is,
- Digraph &g,
- CapacityMap& capacity,
- typename Digraph::Node &s,
- typename Digraph::Node &t,
- DimacsDescriptor desc=DimacsDescriptor()) {
- if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
- if(desc.type!=DimacsDescriptor::MAX)
- throw FormatError("Problem type mismatch");
- _readDimacs(is,g,capacity,s,t,desc);
- }
-
- /// DIMACS shortest path reader function.
- ///
- /// This function reads a shortest path instance from DIMACS format,
- /// i.e. from a DIMACS file having a line starting with
- /// \code
- /// p sp
- /// \endcode
- /// At the beginning, \c g is cleared by \c g.clear(). The arc
- /// lengths are written to \c length and \c s is set to the
- /// source node.
- ///
- /// If the file type was previously evaluated by dimacsType(), then
- /// the descriptor struct should be given by the \c dest parameter.
- template
- void readDimacsSp(std::istream& is,
- Digraph &g,
- LengthMap& length,
- typename Digraph::Node &s,
- DimacsDescriptor desc=DimacsDescriptor()) {
- typename Digraph::Node t;
- if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
- if(desc.type!=DimacsDescriptor::SP)
- throw FormatError("Problem type mismatch");
- _readDimacs(is, g, length, s, t,desc);
- }
-
- /// DIMACS capacitated digraph reader function.
- ///
- /// This function reads an arc capacitated digraph instance from
- /// DIMACS 'mat' or 'sp' format.
- /// At the beginning, \c g is cleared by \c g.clear()
- /// and the arc capacities/lengths are written to \c capacity.
- ///
- /// If the file type was previously evaluated by dimacsType(), then
- /// the descriptor struct should be given by the \c dest parameter.
- template
- void readDimacsCap(std::istream& is,
- Digraph &g,
- CapacityMap& capacity,
- DimacsDescriptor desc=DimacsDescriptor()) {
- typename Digraph::Node u,v;
- if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
- if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
- throw FormatError("Problem type mismatch");
- _readDimacs(is, g, capacity, u, v, desc);
- }
-
- /// DIMACS plain digraph reader function.
- ///
- /// This function reads a digraph without any designated nodes and
- /// maps from DIMACS format, i.e. from DIMACS files having a line
- /// starting with
- /// \code
- /// p mat
- /// \endcode
- /// At the beginning, \c g is cleared by \c g.clear().
- ///
- /// If the file type was previously evaluated by dimacsType(), then
- /// the descriptor struct should be given by the \c dest parameter.
- template
- void readDimacsMat(std::istream& is, Digraph &g,
- DimacsDescriptor desc=DimacsDescriptor()) {
- typename Digraph::Node u,v;
- NullMap n;
- if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
- if(desc.type!=DimacsDescriptor::MAT)
- throw FormatError("Problem type mismatch");
- _readDimacs(is, g, n, u, v, desc);
- }
-
- /// DIMACS plain digraph writer function.
- ///
- /// This function writes a digraph without any designated nodes and
- /// maps into DIMACS format, i.e. into DIMACS file having a line
- /// starting with
- /// \code
- /// p mat
- /// \endcode
- /// If \c comment is not empty, then it will be printed in the first line
- /// prefixed by 'c'.
- template
- void writeDimacsMat(std::ostream& os, const Digraph &g,
- std::string comment="") {
- typedef typename Digraph::NodeIt NodeIt;
- typedef typename Digraph::ArcIt ArcIt;
-
- if(!comment.empty())
- os << "c " << comment << std::endl;
- os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
-
- typename Digraph::template NodeMap nodes(g);
- int i = 1;
- for(NodeIt v(g); v != INVALID; ++v) {
- nodes.set(v, i);
- ++i;
- }
- for(ArcIt e(g); e != INVALID; ++e) {
- os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
- << std::endl;
- }
- }
-
- /// @}
-
-} //namespace lemon
-
-#endif //LEMON_DIMACS_H
Index: mon/elevator.h
===================================================================
--- lemon/elevator.h (revision 398)
+++ (revision )
@@ -1,981 +1,0 @@
-/* -*- 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_ELEVATOR_H
-#define LEMON_ELEVATOR_H
-
-///\ingroup auxdat
-///\file
-///\brief Elevator class
-///
-///Elevator class implements an efficient data structure
-///for labeling items in push-relabel type algorithms.
-///
-
-#include
-
-namespace lemon {
-
- ///Class for handling "labels" in push-relabel type algorithms.
-
- ///A class for handling "labels" in push-relabel type algorithms.
- ///
- ///\ingroup auxdat
- ///Using this class you can assign "labels" (nonnegative integer numbers)
- ///to the edges or nodes of a graph, manipulate and query them through
- ///operations typically arising in "push-relabel" type algorithms.
- ///
- ///Each item is either \em active or not, and you can also choose a
- ///highest level active item.
- ///
- ///\sa LinkedElevator
- ///
- ///\param Graph Type of the underlying graph.
- ///\param Item Type of the items the data is assigned to (Graph::Node,
- ///Graph::Arc, Graph::Edge).
- template
- class Elevator
- {
- public:
-
- typedef Item Key;
- typedef int Value;
-
- private:
-
- typedef Item *Vit;
- typedef typename ItemSetTraits::template Map::Type VitMap;
- typedef typename ItemSetTraits::template Map::Type IntMap;
-
- const Graph &_g;
- int _max_level;
- int _item_num;
- VitMap _where;
- IntMap _level;
- std::vector- _items;
- std::vector _first;
- std::vector _last_active;
-
- int _highest_active;
-
- void copy(Item i, Vit p)
- {
- _where.set(*p=i,p);
- }
- void copy(Vit s, Vit p)
- {
- if(s!=p)
- {
- Item i=*s;
- *p=i;
- _where.set(i,p);
- }
- }
- void swap(Vit i, Vit j)
- {
- Item ti=*i;
- Vit ct = _where[ti];
- _where.set(ti,_where[*i=*j]);
- _where.set(*j,ct);
- *j=ti;
- }
-
- public:
-
- ///Constructor with given maximum level.
-
- ///Constructor with given maximum level.
- ///
- ///\param graph The underlying graph.
- ///\param max_level The maximum allowed level.
- ///Set the range of the possible labels to [0..max_level].
- Elevator(const Graph &graph,int max_level) :
- _g(graph),
- _max_level(max_level),
- _item_num(_max_level),
- _where(graph),
- _level(graph,0),
- _items(_max_level),
- _first(_max_level+2),
- _last_active(_max_level+2),
- _highest_active(-1) {}
- ///Constructor.
-
- ///Constructor.
- ///
- ///\param graph The underlying graph.
- ///Set the range of the possible labels to [0..max_level],
- ///where \c max_level is equal to the number of labeled items in the graph.
- Elevator(const Graph &graph) :
- _g(graph),
- _max_level(countItems(graph)),
- _item_num(_max_level),
- _where(graph),
- _level(graph,0),
- _items(_max_level),
- _first(_max_level+2),
- _last_active(_max_level+2),
- _highest_active(-1)
- {
- }
-
- ///Activate item \c i.
-
- ///Activate item \c i.
- ///\pre Item \c i shouldn't be active before.
- void activate(Item i)
- {
- const int l=_level[i];
- swap(_where[i],++_last_active[l]);
- if(l>_highest_active) _highest_active=l;
- }
-
- ///Deactivate item \c i.
-
- ///Deactivate item \c i.
- ///\pre Item \c i must be active before.
- void deactivate(Item i)
- {
- swap(_where[i],_last_active[_level[i]]--);
- while(_highest_active>=0 &&
- _last_active[_highest_active]<_first[_highest_active])
- _highest_active--;
- }
-
- ///Query whether item \c i is active
- bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
-
- ///Return the level of item \c i.
- int operator[](Item i) const { return _level[i]; }
-
- ///Return the number of items on level \c l.
- int onLevel(int l) const
- {
- return _first[l+1]-_first[l];
- }
- ///Return true if level \c l is empty.
- bool emptyLevel(int l) const
- {
- return _first[l+1]-_first[l]==0;
- }
- ///Return the number of items above level \c l.
- int aboveLevel(int l) const
- {
- return _first[_max_level+1]-_first[l+1];
- }
- ///Return the number of active items on level \c l.
- int activesOnLevel(int l) const
- {
- return _last_active[l]-_first[l]+1;
- }
- ///Return true if there is no active item on level \c l.
- bool activeFree(int l) const
- {
- return _last_active[l]<_first[l];
- }
- ///Return the maximum allowed level.
- int maxLevel() const
- {
- return _max_level;
- }
-
- ///\name Highest Active Item
- ///Functions for working with the highest level
- ///active item.
-
- ///@{
-
- ///Return a highest level active item.
-
- ///Return a highest level active item or INVALID if there is no active
- ///item.
- Item highestActive() const
- {
- return _highest_active>=0?*_last_active[_highest_active]:INVALID;
- }
-
- ///Return the highest active level.
-
- ///Return the level of the highest active item or -1 if there is no active
- ///item.
- int highestActiveLevel() const
- {
- return _highest_active;
- }
-
- ///Lift the highest active item by one.
-
- ///Lift the item returned by highestActive() by one.
- ///
- void liftHighestActive()
- {
- Item it = *_last_active[_highest_active];
- _level.set(it,_level[it]+1);
- swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
- --_first[++_highest_active];
- }
-
- ///Lift the highest active item to the given level.
-
- ///Lift the item returned by highestActive() to level \c new_level.
- ///
- ///\warning \c new_level must be strictly higher
- ///than the current level.
- ///
- void liftHighestActive(int new_level)
- {
- const Item li = *_last_active[_highest_active];
-
- copy(--_first[_highest_active+1],_last_active[_highest_active]--);
- for(int l=_highest_active+1;l=0 &&
- _last_active[_highest_active]<_first[_highest_active])
- _highest_active--;
- }
-
- ///@}
-
- ///\name Active Item on Certain Level
- ///Functions for working with the active items.
-
- ///@{
-
- ///Return an active item on level \c l.
-
- ///Return an active item on level \c l or \ref INVALID if there is no such
- ///an item. (\c l must be from the range [0...\c max_level].
- Item activeOn(int l) const
- {
- return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
- }
-
- ///Lift the active item returned by \c activeOn(level) by one.
-
- ///Lift the active item returned by \ref activeOn() "activeOn(level)"
- ///by one.
- Item liftActiveOn(int level)
- {
- Item it =*_last_active[level];
- _level.set(it,_level[it]+1);
- swap(_last_active[level]--, --_first[level+1]);
- if (level+1>_highest_active) ++_highest_active;
- }
-
- ///Lift the active item returned by \c activeOn(level) to the given level.
-
- ///Lift the active item returned by \ref activeOn() "activeOn(level)"
- ///to the given level.
- void liftActiveOn(int level, int new_level)
- {
- const Item ai = *_last_active[level];
-
- copy(--_first[level+1], _last_active[level]--);
- for(int l=level+1;l_highest_active) _highest_active=new_level;
- }
-
- ///Lift the active item returned by \c activeOn(level) to the top level.
-
- ///Lift the active item returned by \ref activeOn() "activeOn(level)"
- ///to the top level and deactivate it.
- void liftActiveToTop(int level)
- {
- const Item ai = *_last_active[level];
-
- copy(--_first[level+1],_last_active[level]--);
- for(int l=level+1;l<_max_level;l++)
- {
- copy(_last_active[l],_first[l]);
- copy(--_first[l+1], _last_active[l]--);
- }
- copy(ai,_first[_max_level]);
- --_last_active[_max_level];
- _level.set(ai,_max_level);
-
- if (_highest_active==level) {
- while(_highest_active>=0 &&
- _last_active[_highest_active]<_first[_highest_active])
- _highest_active--;
- }
- }
-
- ///@}
-
- ///Lift an active item to a higher level.
-
- ///Lift an active item to a higher level.
- ///\param i The item to be lifted. It must be active.
- ///\param new_level The new level of \c i. It must be strictly higher
- ///than the current level.
- ///
- void lift(Item i, int new_level)
- {
- const int lo = _level[i];
- const Vit w = _where[i];
-
- copy(_last_active[lo],w);
- copy(--_first[lo+1],_last_active[lo]--);
- for(int l=lo+1;l_highest_active) _highest_active=new_level;
- }
-
- ///Move an inactive item to the top but one level (in a dirty way).
-
- ///This function moves an inactive item from the top level to the top
- ///but one level (in a dirty way).
- ///\warning It makes the underlying datastructure corrupt, so use it
- ///only if you really know what it is for.
- ///\pre The item is on the top level.
- void dirtyTopButOne(Item i) {
- _level.set(i,_max_level - 1);
- }
-
- ///Lift all items on and above the given level to the top level.
-
- ///This function lifts all items on and above level \c l to the top
- ///level and deactivates them.
- void liftToTop(int l)
- {
- const Vit f=_first[l];
- const Vit tl=_first[_max_level];
- for(Vit i=f;i!=tl;++i)
- _level.set(*i,_max_level);
- for(int i=l;i<=_max_level;i++)
- {
- _first[i]=f;
- _last_active[i]=f-1;
- }
- for(_highest_active=l-1;
- _highest_active>=0 &&
- _last_active[_highest_active]<_first[_highest_active];
- _highest_active--) ;
- }
-
- private:
- int _init_lev;
- Vit _init_num;
-
- public:
-
- ///\name Initialization
- ///Using these functions you can initialize the levels of the items.
- ///\n
- ///The initialization must be started with calling \c initStart().
- ///Then the items should be listed level by level starting with the
- ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
- ///Finally \c initFinish() must be called.
- ///The items not listed are put on the highest level.
- ///@{
-
- ///Start the initialization process.
- void initStart()
- {
- _init_lev=0;
- _init_num=&_items[0];
- _first[0]=&_items[0];
- _last_active[0]=&_items[0]-1;
- Vit n=&_items[0];
- for(typename ItemSetTraits::ItemIt i(_g);i!=INVALID;++i)
- {
- *n=i;
- _where.set(i,n);
- _level.set(i,_max_level);
- ++n;
- }
- }
-
- ///Add an item to the current level.
- void initAddItem(Item i)
- {
- swap(_where[i],_init_num);
- _level.set(i,_init_lev);
- ++_init_num;
- }
-
- ///Start a new level.
-
- ///Start a new level.
- ///It shouldn't be used before the items on level 0 are listed.
- void initNewLevel()
- {
- _init_lev++;
- _first[_init_lev]=_init_num;
- _last_active[_init_lev]=_init_num-1;
- }
-
- ///Finalize the initialization process.
- void initFinish()
- {
- for(_init_lev++;_init_lev<=_max_level;_init_lev++)
- {
- _first[_init_lev]=_init_num;
- _last_active[_init_lev]=_init_num-1;
- }
- _first[_max_level+1]=&_items[0]+_item_num;
- _last_active[_max_level+1]=&_items[0]+_item_num-1;
- _highest_active = -1;
- }
-
- ///@}
-
- };
-
- ///Class for handling "labels" in push-relabel type algorithms.
-
- ///A class for handling "labels" in push-relabel type algorithms.
- ///
- ///\ingroup auxdat
- ///Using this class you can assign "labels" (nonnegative integer numbers)
- ///to the edges or nodes of a graph, manipulate and query them through
- ///operations typically arising in "push-relabel" type algorithms.
- ///
- ///Each item is either \em active or not, and you can also choose a
- ///highest level active item.
- ///
- ///\sa Elevator
- ///
- ///\param Graph Type of the underlying graph.
- ///\param Item Type of the items the data is assigned to (Graph::Node,
- ///Graph::Arc, Graph::Edge).
- template
- class LinkedElevator {
- public:
-
- typedef Item Key;
- typedef int Value;
-
- private:
-
- typedef typename ItemSetTraits::
- template Map
- ::Type ItemMap;
- typedef typename ItemSetTraits::
- template Map::Type IntMap;
- typedef typename ItemSetTraits::
- template Map::Type BoolMap;
-
- const Graph &_graph;
- int _max_level;
- int _item_num;
- std::vector
- _first, _last;
- ItemMap _prev, _next;
- int _highest_active;
- IntMap _level;
- BoolMap _active;
-
- public:
- ///Constructor with given maximum level.
-
- ///Constructor with given maximum level.
- ///
- ///\param graph The underlying graph.
- ///\param max_level The maximum allowed level.
- ///Set the range of the possible labels to [0..max_level].
- LinkedElevator(const Graph& graph, int max_level)
- : _graph(graph), _max_level(max_level), _item_num(_max_level),
- _first(_max_level + 1), _last(_max_level + 1),
- _prev(graph), _next(graph),
- _highest_active(-1), _level(graph), _active(graph) {}
-
- ///Constructor.
-
- ///Constructor.
- ///
- ///\param graph The underlying graph.
- ///Set the range of the possible labels to [0..max_level],
- ///where \c max_level is equal to the number of labeled items in the graph.
- LinkedElevator(const Graph& graph)
- : _graph(graph), _max_level(countItems(graph)),
- _item_num(_max_level),
- _first(_max_level + 1), _last(_max_level + 1),
- _prev(graph, INVALID), _next(graph, INVALID),
- _highest_active(-1), _level(graph), _active(graph) {}
-
-
- ///Activate item \c i.
-
- ///Activate item \c i.
- ///\pre Item \c i shouldn't be active before.
- void activate(Item i) {
- _active.set(i, true);
-
- int level = _level[i];
- if (level > _highest_active) {
- _highest_active = level;
- }
-
- if (_prev[i] == INVALID || _active[_prev[i]]) return;
- //unlace
- _next.set(_prev[i], _next[i]);
- if (_next[i] != INVALID) {
- _prev.set(_next[i], _prev[i]);
- } else {
- _last[level] = _prev[i];
- }
- //lace
- _next.set(i, _first[level]);
- _prev.set(_first[level], i);
- _prev.set(i, INVALID);
- _first[level] = i;
-
- }
-
- ///Deactivate item \c i.
-
- ///Deactivate item \c i.
- ///\pre Item \c i must be active before.
- void deactivate(Item i) {
- _active.set(i, false);
- int level = _level[i];
-
- if (_next[i] == INVALID || !_active[_next[i]])
- goto find_highest_level;
-
- //unlace
- _prev.set(_next[i], _prev[i]);
- if (_prev[i] != INVALID) {
- _next.set(_prev[i], _next[i]);
- } else {
- _first[_level[i]] = _next[i];
- }
- //lace
- _prev.set(i, _last[level]);
- _next.set(_last[level], i);
- _next.set(i, INVALID);
- _last[level] = i;
-
- find_highest_level:
- if (level == _highest_active) {
- while (_highest_active >= 0 && activeFree(_highest_active))
- --_highest_active;
- }
- }
-
- ///Query whether item \c i is active
- bool active(Item i) const { return _active[i]; }
-
- ///Return the level of item \c i.
- int operator[](Item i) const { return _level[i]; }
-
- ///Return the number of items on level \c l.
- int onLevel(int l) const {
- int num = 0;
- Item n = _first[l];
- while (n != INVALID) {
- ++num;
- n = _next[n];
- }
- return num;
- }
-
- ///Return true if the level is empty.
- bool emptyLevel(int l) const {
- return _first[l] == INVALID;
- }
-
- ///Return the number of items above level \c l.
- int aboveLevel(int l) const {
- int num = 0;
- for (int level = l + 1; level < _max_level; ++level)
- num += onLevel(level);
- return num;
- }
-
- ///Return the number of active items on level \c l.
- int activesOnLevel(int l) const {
- int num = 0;
- Item n = _first[l];
- while (n != INVALID && _active[n]) {
- ++num;
- n = _next[n];
- }
- return num;
- }
-
- ///Return true if there is no active item on level \c l.
- bool activeFree(int l) const {
- return _first[l] == INVALID || !_active[_first[l]];
- }
-
- ///Return the maximum allowed level.
- int maxLevel() const {
- return _max_level;
- }
-
- ///\name Highest Active Item
- ///Functions for working with the highest level
- ///active item.
-
- ///@{
-
- ///Return a highest level active item.
-
- ///Return a highest level active item or INVALID if there is no active
- ///item.
- Item highestActive() const {
- return _highest_active >= 0 ? _first[_highest_active] : INVALID;
- }
-
- ///Return the highest active level.
-
- ///Return the level of the highest active item or -1 if there is no active
- ///item.
- int highestActiveLevel() const {
- return _highest_active;
- }
-
- ///Lift the highest active item by one.
-
- ///Lift the item returned by highestActive() by one.
- ///
- void liftHighestActive() {
- Item i = _first[_highest_active];
- if (_next[i] != INVALID) {
- _prev.set(_next[i], INVALID);
- _first[_highest_active] = _next[i];
- } else {
- _first[_highest_active] = INVALID;
- _last[_highest_active] = INVALID;
- }
- _level.set(i, ++_highest_active);
- if (_first[_highest_active] == INVALID) {
- _first[_highest_active] = i;
- _last[_highest_active] = i;
- _prev.set(i, INVALID);
- _next.set(i, INVALID);
- } else {
- _prev.set(_first[_highest_active], i);
- _next.set(i, _first[_highest_active]);
- _first[_highest_active] = i;
- }
- }
-
- ///Lift the highest active item to the given level.
-
- ///Lift the item returned by highestActive() to level \c new_level.
- ///
- ///\warning \c new_level must be strictly higher
- ///than the current level.
- ///
- void liftHighestActive(int new_level) {
- Item i = _first[_highest_active];
- if (_next[i] != INVALID) {
- _prev.set(_next[i], INVALID);
- _first[_highest_active] = _next[i];
- } else {
- _first[_highest_active] = INVALID;
- _last[_highest_active] = INVALID;
- }
- _level.set(i, _highest_active = new_level);
- if (_first[_highest_active] == INVALID) {
- _first[_highest_active] = _last[_highest_active] = i;
- _prev.set(i, INVALID);
- _next.set(i, INVALID);
- } else {
- _prev.set(_first[_highest_active], i);
- _next.set(i, _first[_highest_active]);
- _first[_highest_active] = i;
- }
- }
-
- ///Lift the highest active item to the top level.
-
- ///Lift the item returned by highestActive() to the top level and
- ///deactivate it.
- void liftHighestActiveToTop() {
- Item i = _first[_highest_active];
- _level.set(i, _max_level);
- if (_next[i] != INVALID) {
- _prev.set(_next[i], INVALID);
- _first[_highest_active] = _next[i];
- } else {
- _first[_highest_active] = INVALID;
- _last[_highest_active] = INVALID;
- }
- while (_highest_active >= 0 && activeFree(_highest_active))
- --_highest_active;
- }
-
- ///@}
-
- ///\name Active Item on Certain Level
- ///Functions for working with the active items.
-
- ///@{
-
- ///Return an active item on level \c l.
-
- ///Return an active item on level \c l or \ref INVALID if there is no such
- ///an item. (\c l must be from the range [0...\c max_level].
- Item activeOn(int l) const
- {
- return _active[_first[l]] ? _first[l] : INVALID;
- }
-
- ///Lift the active item returned by \c activeOn(l) by one.
-
- ///Lift the active item returned by \ref activeOn() "activeOn(l)"
- ///by one.
- Item liftActiveOn(int l)
- {
- Item i = _first[l];
- if (_next[i] != INVALID) {
- _prev.set(_next[i], INVALID);
- _first[l] = _next[i];
- } else {
- _first[l] = INVALID;
- _last[l] = INVALID;
- }
- _level.set(i, ++l);
- if (_first[l] == INVALID) {
- _first[l] = _last[l] = i;
- _prev.set(i, INVALID);
- _next.set(i, INVALID);
- } else {
- _prev.set(_first[l], i);
- _next.set(i, _first[l]);
- _first[l] = i;
- }
- if (_highest_active < l) {
- _highest_active = l;
- }
- }
-
- ///Lift the active item returned by \c activeOn(l) to the given level.
-
- ///Lift the active item returned by \ref activeOn() "activeOn(l)"
- ///to the given level.
- void liftActiveOn(int l, int new_level)
- {
- Item i = _first[l];
- if (_next[i] != INVALID) {
- _prev.set(_next[i], INVALID);
- _first[l] = _next[i];
- } else {
- _first[l] = INVALID;
- _last[l] = INVALID;
- }
- _level.set(i, l = new_level);
- if (_first[l] == INVALID) {
- _first[l] = _last[l] = i;
- _prev.set(i, INVALID);
- _next.set(i, INVALID);
- } else {
- _prev.set(_first[l], i);
- _next.set(i, _first[l]);
- _first[l] = i;
- }
- if (_highest_active < l) {
- _highest_active = l;
- }
- }
-
- ///Lift the active item returned by \c activeOn(l) to the top level.
-
- ///Lift the active item returned by \ref activeOn() "activeOn(l)"
- ///to the top level and deactivate it.
- void liftActiveToTop(int l)
- {
- Item i = _first[l];
- if (_next[i] != INVALID) {
- _prev.set(_next[i], INVALID);
- _first[l] = _next[i];
- } else {
- _first[l] = INVALID;
- _last[l] = INVALID;
- }
- _level.set(i, _max_level);
- if (l == _highest_active) {
- while (_highest_active >= 0 && activeFree(_highest_active))
- --_highest_active;
- }
- }
-
- ///@}
-
- /// \brief Lift an active item to a higher level.
- ///
- /// Lift an active item to a higher level.
- /// \param i The item to be lifted. It must be active.
- /// \param new_level The new level of \c i. It must be strictly higher
- /// than the current level.
- ///
- void lift(Item i, int new_level) {
- if (_next[i] != INVALID) {
- _prev.set(_next[i], _prev[i]);
- } else {
- _last[new_level] = _prev[i];
- }
- if (_prev[i] != INVALID) {
- _next.set(_prev[i], _next[i]);
- } else {
- _first[new_level] = _next[i];
- }
- _level.set(i, new_level);
- if (_first[new_level] == INVALID) {
- _first[new_level] = _last[new_level] = i;
- _prev.set(i, INVALID);
- _next.set(i, INVALID);
- } else {
- _prev.set(_first[new_level], i);
- _next.set(i, _first[new_level]);
- _first[new_level] = i;
- }
- if (_highest_active < new_level) {
- _highest_active = new_level;
- }
- }
-
- ///Move an inactive item to the top but one level (in a dirty way).
-
- ///This function moves an inactive item from the top level to the top
- ///but one level (in a dirty way).
- ///\warning It makes the underlying datastructure corrupt, so use it
- ///only if you really know what it is for.
- ///\pre The item is on the top level.
- void dirtyTopButOne(Item i) {
- _level.set(i, _max_level - 1);
- }
-
- ///Lift all items on and above the given level to the top level.
-
- ///This function lifts all items on and above level \c l to the top
- ///level and deactivates them.
- void liftToTop(int l) {
- for (int i = l + 1; _first[i] != INVALID; ++i) {
- Item n = _first[i];
- while (n != INVALID) {
- _level.set(n, _max_level);
- n = _next[n];
- }
- _first[i] = INVALID;
- _last[i] = INVALID;
- }
- if (_highest_active > l - 1) {
- _highest_active = l - 1;
- while (_highest_active >= 0 && activeFree(_highest_active))
- --_highest_active;
- }
- }
-
- private:
-
- int _init_level;
-
- public:
-
- ///\name Initialization
- ///Using these functions you can initialize the levels of the items.
- ///\n
- ///The initialization must be started with calling \c initStart().
- ///Then the items should be listed level by level starting with the
- ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
- ///Finally \c initFinish() must be called.
- ///The items not listed are put on the highest level.
- ///@{
-
- ///Start the initialization process.
- void initStart() {
-
- for (int i = 0; i <= _max_level; ++i) {
- _first[i] = _last[i] = INVALID;
- }
- _init_level = 0;
- for(typename ItemSetTraits::ItemIt i(_graph);
- i != INVALID; ++i) {
- _level.set(i, _max_level);
- _active.set(i, false);
- }
- }
-
- ///Add an item to the current level.
- void initAddItem(Item i) {
- _level.set(i, _init_level);
- if (_last[_init_level] == INVALID) {
- _first[_init_level] = i;
- _last[_init_level] = i;
- _prev.set(i, INVALID);
- _next.set(i, INVALID);
- } else {
- _prev.set(i, _last[_init_level]);
- _next.set(i, INVALID);
- _next.set(_last[_init_level], i);
- _last[_init_level] = i;
- }
- }
-
- ///Start a new level.
-
- ///Start a new level.
- ///It shouldn't be used before the items on level 0 are listed.
- void initNewLevel() {
- ++_init_level;
- }
-
- ///Finalize the initialization process.
- void initFinish() {
- _highest_active = -1;
- }
-
- ///@}
-
- };
-
-
-} //END OF NAMESPACE LEMON
-
-#endif
-
Index: mon/full_graph.h
===================================================================
--- lemon/full_graph.h (revision 372)
+++ (revision )
@@ -1,614 +1,0 @@
-/* -*- 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_FULL_GRAPH_H
-#define LEMON_FULL_GRAPH_H
-
-#include
-#include
-
-///\ingroup graphs
-///\file
-///\brief FullGraph and FullDigraph classes.
-
-namespace lemon {
-
- class FullDigraphBase {
- public:
-
- typedef FullDigraphBase Graph;
-
- class Node;
- class Arc;
-
- protected:
-
- int _node_num;
- int _arc_num;
-
- FullDigraphBase() {}
-
- void construct(int n) { _node_num = n; _arc_num = n * n; }
-
- public:
-
- typedef True NodeNumTag;
- typedef True ArcNumTag;
-
- Node operator()(int ix) const { return Node(ix); }
- int index(const Node& node) const { return node._id; }
-
- Arc arc(const Node& s, const Node& t) const {
- return Arc(s._id * _node_num + t._id);
- }
-
- int nodeNum() const { return _node_num; }
- int arcNum() const { return _arc_num; }
-
- int maxNodeId() const { return _node_num - 1; }
- int maxArcId() const { return _arc_num - 1; }
-
- Node source(Arc arc) const { return arc._id / _node_num; }
- Node target(Arc arc) const { return arc._id % _node_num; }
-
- static int id(Node node) { return node._id; }
- static int id(Arc arc) { return arc._id; }
-
- static Node nodeFromId(int id) { return Node(id);}
- static Arc arcFromId(int id) { return Arc(id);}
-
- typedef True FindArcTag;
-
- Arc findArc(Node s, Node t, Arc prev = INVALID) const {
- return prev == INVALID ? arc(s, t) : INVALID;
- }
-
- class Node {
- friend class FullDigraphBase;
-
- protected:
- int _id;
- Node(int id) : _id(id) {}
- public:
- Node() {}
- Node (Invalid) : _id(-1) {}
- bool operator==(const Node node) const {return _id == node._id;}
- bool operator!=(const Node node) const {return _id != node._id;}
- bool operator<(const Node node) const {return _id < node._id;}
- };
-
- class Arc {
- friend class FullDigraphBase;
-
- protected:
- int _id; // _node_num * source + target;
-
- Arc(int id) : _id(id) {}
-
- public:
- Arc() { }
- Arc (Invalid) { _id = -1; }
- bool operator==(const Arc arc) const {return _id == arc._id;}
- bool operator!=(const Arc arc) const {return _id != arc._id;}
- bool operator<(const Arc arc) const {return _id < arc._id;}
- };
-
- void first(Node& node) const {
- node._id = _node_num - 1;
- }
-
- static void next(Node& node) {
- --node._id;
- }
-
- void first(Arc& arc) const {
- arc._id = _arc_num - 1;
- }
-
- static void next(Arc& arc) {
- --arc._id;
- }
-
- void firstOut(Arc& arc, const Node& node) const {
- arc._id = (node._id + 1) * _node_num - 1;
- }
-
- void nextOut(Arc& arc) const {
- if (arc._id % _node_num == 0) arc._id = 0;
- --arc._id;
- }
-
- void firstIn(Arc& arc, const Node& node) const {
- arc._id = _arc_num + node._id - _node_num;
- }
-
- void nextIn(Arc& arc) const {
- arc._id -= _node_num;
- if (arc._id < 0) arc._id = -1;
- }
-
- };
-
- typedef DigraphExtender ExtendedFullDigraphBase;
-
- /// \ingroup graphs
- ///
- /// \brief A full digraph class.
- ///
- /// This is a simple and fast directed full graph implementation.
- /// From each node go arcs to each node (including the source node),
- /// therefore the number of the arcs in the digraph is the square of
- /// the node number. This digraph type is completely static, so you
- /// can neither add nor delete either arcs or nodes, and it needs
- /// constant space in memory.
- ///
- /// This class conforms to the \ref concepts::Digraph "Digraph" concept
- /// and it also has an important extra feature that its maps are
- /// real \ref concepts::ReferenceMap "reference map"s.
- ///
- /// The \c FullDigraph and \c FullGraph classes are very similar,
- /// but there are two differences. While this class conforms only
- /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
- /// class conforms to the \ref concepts::Graph "Graph" concept,
- /// moreover \c FullGraph does not contain a loop arc for each
- /// node as \c FullDigraph does.
- ///
- /// \sa FullGraph
- class FullDigraph : public ExtendedFullDigraphBase {
- public:
-
- typedef ExtendedFullDigraphBase Parent;
-
- /// \brief Constructor
- FullDigraph() { construct(0); }
-
- /// \brief Constructor
- ///
- /// Constructor.
- /// \param n The number of the nodes.
- FullDigraph(int n) { construct(n); }
-
- /// \brief Resizes the digraph
- ///
- /// Resizes the digraph. The function will fully destroy and
- /// rebuild the digraph. This cause that the maps of the digraph will
- /// reallocated automatically and the previous values will be lost.
- void resize(int n) {
- Parent::notifier(Arc()).clear();
- Parent::notifier(Node()).clear();
- construct(n);
- Parent::notifier(Node()).build();
- Parent::notifier(Arc()).build();
- }
-
- /// \brief Returns the node with the given index.
- ///
- /// Returns the node with the given index. Since it is a static
- /// digraph its nodes can be indexed with integers from the range
- /// [0..nodeNum()-1].
- /// \sa index()
- Node operator()(int ix) const { return Parent::operator()(ix); }
-
- /// \brief Returns the index of the given node.
- ///
- /// Returns the index of the given node. Since it is a static
- /// digraph its nodes can be indexed with integers from the range
- /// [0..nodeNum()-1].
- /// \sa operator()
- int index(const Node& node) const { return Parent::index(node); }
-
- /// \brief Returns the arc connecting the given nodes.
- ///
- /// Returns the arc connecting the given nodes.
- Arc arc(const Node& u, const Node& v) const {
- return Parent::arc(u, v);
- }
-
- /// \brief Number of nodes.
- int nodeNum() const { return Parent::nodeNum(); }
- /// \brief Number of arcs.
- int arcNum() const { return Parent::arcNum(); }
- };
-
-
- class FullGraphBase {
- int _node_num;
- int _edge_num;
- public:
-
- typedef FullGraphBase Graph;
-
- class Node;
- class Arc;
- class Edge;
-
- protected:
-
- FullGraphBase() {}
-
- void construct(int n) { _node_num = n; _edge_num = n * (n - 1) / 2; }
-
- int _uid(int e) const {
- int u = e / _node_num;
- int v = e % _node_num;
- return u < v ? u : _node_num - 2 - u;
- }
-
- int _vid(int e) const {
- int u = e / _node_num;
- int v = e % _node_num;
- return u < v ? v : _node_num - 1 - v;
- }
-
- void _uvid(int e, int& u, int& v) const {
- u = e / _node_num;
- v = e % _node_num;
- if (u >= v) {
- u = _node_num - 2 - u;
- v = _node_num - 1 - v;
- }
- }
-
- void _stid(int a, int& s, int& t) const {
- if ((a & 1) == 1) {
- _uvid(a >> 1, s, t);
- } else {
- _uvid(a >> 1, t, s);
- }
- }
-
- int _eid(int u, int v) const {
- if (u < (_node_num - 1) / 2) {
- return u * _node_num + v;
- } else {
- return (_node_num - 1 - u) * _node_num - v - 1;
- }
- }
-
- public:
-
- Node operator()(int ix) const { return Node(ix); }
- int index(const Node& node) const { return node._id; }
-
- Edge edge(const Node& u, const Node& v) const {
- if (u._id < v._id) {
- return Edge(_eid(u._id, v._id));
- } else if (u._id != v._id) {
- return Edge(_eid(v._id, u._id));
- } else {
- return INVALID;
- }
- }
-
- Arc arc(const Node& s, const Node& t) const {
- if (s._id < t._id) {
- return Arc((_eid(s._id, t._id) << 1) | 1);
- } else if (s._id != t._id) {
- return Arc(_eid(t._id, s._id) << 1);
- } else {
- return INVALID;
- }
- }
-
- typedef True NodeNumTag;
- typedef True ArcNumTag;
- typedef True EdgeNumTag;
-
- int nodeNum() const { return _node_num; }
- int arcNum() const { return 2 * _edge_num; }
- int edgeNum() const { return _edge_num; }
-
- static int id(Node node) { return node._id; }
- static int id(Arc arc) { return arc._id; }
- static int id(Edge edge) { return edge._id; }
-
- int maxNodeId() const { return _node_num-1; }
- int maxArcId() const { return 2 * _edge_num-1; }
- int maxEdgeId() const { return _edge_num-1; }
-
- static Node nodeFromId(int id) { return Node(id);}
- static Arc arcFromId(int id) { return Arc(id);}
- static Edge edgeFromId(int id) { return Edge(id);}
-
- Node u(Edge edge) const {
- return Node(_uid(edge._id));
- }
-
- Node v(Edge edge) const {
- return Node(_vid(edge._id));
- }
-
- Node source(Arc arc) const {
- return Node((arc._id & 1) == 1 ?
- _uid(arc._id >> 1) : _vid(arc._id >> 1));
- }
-
- Node target(Arc arc) const {
- return Node((arc._id & 1) == 1 ?
- _vid(arc._id >> 1) : _uid(arc._id >> 1));
- }
-
- typedef True FindEdgeTag;
- typedef True FindArcTag;
-
- Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
- return prev != INVALID ? INVALID : edge(u, v);
- }
-
- Arc findArc(Node s, Node t, Arc prev = INVALID) const {
- return prev != INVALID ? INVALID : arc(s, t);
- }
-
- class Node {
- friend class FullGraphBase;
-
- protected:
- int _id;
- Node(int id) : _id(id) {}
- public:
- Node() {}
- Node (Invalid) { _id = -1; }
- bool operator==(const Node node) const {return _id == node._id;}
- bool operator!=(const Node node) const {return _id != node._id;}
- bool operator<(const Node node) const {return _id < node._id;}
- };
-
- class Edge {
- friend class FullGraphBase;
- friend class Arc;
-
- protected:
- int _id;
-
- Edge(int id) : _id(id) {}
-
- public:
- Edge() { }
- Edge (Invalid) { _id = -1; }
-
- bool operator==(const Edge edge) const {return _id == edge._id;}
- bool operator!=(const Edge edge) const {return _id != edge._id;}
- bool operator<(const Edge edge) const {return _id < edge._id;}
- };
-
- class Arc {
- friend class FullGraphBase;
-
- protected:
- int _id;
-
- Arc(int id) : _id(id) {}
-
- public:
- Arc() { }
- Arc (Invalid) { _id = -1; }
-
- operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -1); }
-
- bool operator==(const Arc arc) const {return _id == arc._id;}
- bool operator!=(const Arc arc) const {return _id != arc._id;}
- bool operator<(const Arc arc) const {return _id < arc._id;}
- };
-
- static bool direction(Arc arc) {
- return (arc._id & 1) == 1;
- }
-
- static Arc direct(Edge edge, bool dir) {
- return Arc((edge._id << 1) | (dir ? 1 : 0));
- }
-
- void first(Node& node) const {
- node._id = _node_num - 1;
- }
-
- static void next(Node& node) {
- --node._id;
- }
-
- void first(Arc& arc) const {
- arc._id = (_edge_num << 1) - 1;
- }
-
- static void next(Arc& arc) {
- --arc._id;
- }
-
- void first(Edge& edge) const {
- edge._id = _edge_num - 1;
- }
-
- static void next(Edge& edge) {
- --edge._id;
- }
-
- void firstOut(Arc& arc, const Node& node) const {
- int s = node._id, t = _node_num - 1;
- if (s < t) {
- arc._id = (_eid(s, t) << 1) | 1;
- } else {
- --t;
- arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
- }
- }
-
- void nextOut(Arc& arc) const {
- int s, t;
- _stid(arc._id, s, t);
- --t;
- if (s < t) {
- arc._id = (_eid(s, t) << 1) | 1;
- } else {
- if (s == t) --t;
- arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
- }
- }
-
- void firstIn(Arc& arc, const Node& node) const {
- int s = _node_num - 1, t = node._id;
- if (s > t) {
- arc._id = (_eid(t, s) << 1);
- } else {
- --s;
- arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
- }
- }
-
- void nextIn(Arc& arc) const {
- int s, t;
- _stid(arc._id, s, t);
- --s;
- if (s > t) {
- arc._id = (_eid(t, s) << 1);
- } else {
- if (s == t) --s;
- arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
- }
- }
-
- void firstInc(Edge& edge, bool& dir, const Node& node) const {
- int u = node._id, v = _node_num - 1;
- if (u < v) {
- edge._id = _eid(u, v);
- dir = true;
- } else {
- --v;
- edge._id = (v != -1 ? _eid(v, u) : -1);
- dir = false;
- }
- }
-
- void nextInc(Edge& edge, bool& dir) const {
- int u, v;
- if (dir) {
- _uvid(edge._id, u, v);
- --v;
- if (u < v) {
- edge._id = _eid(u, v);
- } else {
- --v;
- edge._id = (v != -1 ? _eid(v, u) : -1);
- dir = false;
- }
- } else {
- _uvid(edge._id, v, u);
- --v;
- edge._id = (v != -1 ? _eid(v, u) : -1);
- }
- }
-
- };
-
- typedef GraphExtender ExtendedFullGraphBase;
-
- /// \ingroup graphs
- ///
- /// \brief An undirected full graph class.
- ///
- /// This is a simple and fast undirected full graph
- /// implementation. From each node go edge to each other node,
- /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
- /// This graph type is completely static, so you can neither
- /// add nor delete either edges or nodes, and it needs constant
- /// space in memory.
- ///
- /// This class conforms to the \ref concepts::Graph "Graph" concept
- /// and it also has an important extra feature that its maps are
- /// real \ref concepts::ReferenceMap "reference map"s.
- ///
- /// The \c FullGraph and \c FullDigraph classes are very similar,
- /// but there are two differences. While the \c FullDigraph class
- /// conforms only to the \ref concepts::Digraph "Digraph" concept,
- /// this class conforms to the \ref concepts::Graph "Graph" concept,
- /// moreover \c FullGraph does not contain a loop arc for each
- /// node as \c FullDigraph does.
- ///
- /// \sa FullDigraph
- class FullGraph : public ExtendedFullGraphBase {
- public:
-
- typedef ExtendedFullGraphBase Parent;
-
- /// \brief Constructor
- FullGraph() { construct(0); }
-
- /// \brief Constructor
- ///
- /// Constructor.
- /// \param n The number of the nodes.
- FullGraph(int n) { construct(n); }
-
- /// \brief Resizes the graph
- ///
- /// Resizes the graph. The function will fully destroy and
- /// rebuild the graph. This cause that the maps of the graph will
- /// reallocated automatically and the previous values will be lost.
- void resize(int n) {
- Parent::notifier(Arc()).clear();
- Parent::notifier(Edge()).clear();
- Parent::notifier(Node()).clear();
- construct(n);
- Parent::notifier(Node()).build();
- Parent::notifier(Edge()).build();
- Parent::notifier(Arc()).build();
- }
-
- /// \brief Returns the node with the given index.
- ///
- /// Returns the node with the given index. Since it is a static
- /// graph its nodes can be indexed with integers from the range
- /// [0..nodeNum()-1].
- /// \sa index()
- Node operator()(int ix) const { return Parent::operator()(ix); }
-
- /// \brief Returns the index of the given node.
- ///
- /// Returns the index of the given node. Since it is a static
- /// graph its nodes can be indexed with integers from the range
- /// [0..nodeNum()-1].
- /// \sa operator()
- int index(const Node& node) const { return Parent::index(node); }
-
- /// \brief Returns the arc connecting the given nodes.
- ///
- /// Returns the arc connecting the given nodes.
- Arc arc(const Node& s, const Node& t) const {
- return Parent::arc(s, t);
- }
-
- /// \brief Returns the edge connects the given nodes.
- ///
- /// Returns the edge connects the given nodes.
- Edge edge(const Node& u, const Node& v) const {
- return Parent::edge(u, v);
- }
-
- /// \brief Number of nodes.
- int nodeNum() const { return Parent::nodeNum(); }
- /// \brief Number of arcs.
- int arcNum() const { return Parent::arcNum(); }
- /// \brief Number of edges.
- int edgeNum() const { return Parent::edgeNum(); }
-
- };
-
-
-} //namespace lemon
-
-
-#endif //LEMON_FULL_GRAPH_H
Index: mon/grid_graph.h
===================================================================
--- lemon/grid_graph.h (revision 372)
+++ (revision )
@@ -1,705 +1,0 @@
-/* -*- 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 GRID_GRAPH_H
-#define GRID_GRAPH_H
-
-#include
-#include
-#include
-#include
-
-///\ingroup graphs
-///\file
-///\brief GridGraph class.
-
-namespace lemon {
-
- class GridGraphBase {
-
- public:
-
- typedef GridGraphBase Graph;
-
- class Node;
- class Edge;
- class Arc;
-
- public:
-
- GridGraphBase() {}
-
- protected:
-
- void construct(int width, int height) {
- _width = width; _height = height;
- _node_num = width * height;
- _edge_num = 2 * _node_num - width - height;
- _edge_limit = _node_num - _width;
- }
-
- public:
-
- Node operator()(int i, int j) const {
- LEMON_DEBUG(0 <= i && i < _width &&
- 0 <= j && j < _height, "Index out of range");
- return Node(i + j * _width);
- }
-
- int col(Node n) const {
- return n._id % _width;
- }
-
- int row(Node n) const {
- return n._id / _width;
- }
-
- dim2::Point pos(Node n) const {
- return dim2::Point(col(n), row(n));
- }
-
- int width() const {
- return _width;
- }
-
- int height() const {
- return _height;
- }
-
- typedef True NodeNumTag;
- typedef True EdgeNumTag;
- typedef True ArcNumTag;
-
- int nodeNum() const { return _node_num; }
- int edgeNum() const { return _edge_num; }
- int arcNum() const { return 2 * _edge_num; }
-
- Node u(Edge edge) const {
- if (edge._id < _edge_limit) {
- return edge._id;
- } else {
- return (edge._id - _edge_limit) % (_width - 1) +
- (edge._id - _edge_limit) / (_width - 1) * _width;
- }
- }
-
- Node v(Edge edge) const {
- if (edge._id < _edge_limit) {
- return edge._id + _width;
- } else {
- return (edge._id - _edge_limit) % (_width - 1) +
- (edge._id - _edge_limit) / (_width - 1) * _width + 1;
- }
- }
-
- Node source(Arc arc) const {
- return (arc._id & 1) == 1 ? u(arc) : v(arc);
- }
-
- Node target(Arc arc) const {
- return (arc._id & 1) == 1 ? v(arc) : u(arc);
- }
-
- static int id(Node node) { return node._id; }
- static int id(Edge edge) { return edge._id; }
- static int id(Arc arc) { return arc._id; }
-
- int maxNodeId() const { return _node_num - 1; }
- int maxEdgeId() const { return _edge_num - 1; }
- int maxArcId() const { return 2 * _edge_num - 1; }
-
- static Node nodeFromId(int id) { return Node(id);}
- static Edge edgeFromId(int id) { return Edge(id);}
- static Arc arcFromId(int id) { return Arc(id);}
-
- typedef True FindEdgeTag;
- typedef True FindArcTag;
-
- Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
- if (prev != INVALID) return INVALID;
- if (v._id > u._id) {
- if (v._id - u._id == _width)
- return Edge(u._id);
- if (v._id - u._id == 1 && u._id % _width < _width - 1) {
- return Edge(u._id / _width * (_width - 1) +
- u._id % _width + _edge_limit);
- }
- } else {
- if (u._id - v._id == _width)
- return Edge(v._id);
- if (u._id - v._id == 1 && v._id % _width < _width - 1) {
- return Edge(v._id / _width * (_width - 1) +
- v._id % _width + _edge_limit);
- }
- }
- return INVALID;
- }
-
- Arc findArc(Node u, Node v, Arc prev = INVALID) const {
- if (prev != INVALID) return INVALID;
- if (v._id > u._id) {
- if (v._id - u._id == _width)
- return Arc((u._id << 1) | 1);
- if (v._id - u._id == 1 && u._id % _width < _width - 1) {
- return Arc(((u._id / _width * (_width - 1) +
- u._id % _width + _edge_limit) << 1) | 1);
- }
- } else {
- if (u._id - v._id == _width)
- return Arc(v._id << 1);
- if (u._id - v._id == 1 && v._id % _width < _width - 1) {
- return Arc((v._id / _width * (_width - 1) +
- v._id % _width + _edge_limit) << 1);
- }
- }
- return INVALID;
- }
-
- class Node {
- friend class GridGraphBase;
-
- protected:
- int _id;
- Node(int id) : _id(id) {}
- public:
- Node() {}
- Node (Invalid) : _id(-1) {}
- bool operator==(const Node node) const {return _id == node._id;}
- bool operator!=(const Node node) const {return _id != node._id;}
- bool operator<(const Node node) const {return _id < node._id;}
- };
-
- class Edge {
- friend class GridGraphBase;
- friend class Arc;
-
- protected:
- int _id;
-
- Edge(int id) : _id(id) {}
-
- public:
- Edge() {}
- Edge (Invalid) : _id(-1) {}
- bool operator==(const Edge edge) const {return _id == edge._id;}
- bool operator!=(const Edge edge) const {return _id != edge._id;}
- bool operator<(const Edge edge) const {return _id < edge._id;}
- };
-
- class Arc {
- friend class GridGraphBase;
-
- protected:
- int _id;
-
- Arc(int id) : _id(id) {}
-
- public:
- Arc() {}
- Arc (Invalid) : _id(-1) {}
- operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
- bool operator==(const Arc arc) const {return _id == arc._id;}
- bool operator!=(const Arc arc) const {return _id != arc._id;}
- bool operator<(const Arc arc) const {return _id < arc._id;}
- };
-
- static bool direction(Arc arc) {
- return (arc._id & 1) == 1;
- }
-
- static Arc direct(Edge edge, bool dir) {
- return Arc((edge._id << 1) | (dir ? 1 : 0));
- }
-
- void first(Node& node) const {
- node._id = _node_num - 1;
- }
-
- static void next(Node& node) {
- --node._id;
- }
-
- void first(Edge& edge) const {
- edge._id = _edge_num - 1;
- }
-
- static void next(Edge& edge) {
- --edge._id;
- }
-
- void first(Arc& arc) const {
- arc._id = 2 * _edge_num - 1;
- }
-
- static void next(Arc& arc) {
- --arc._id;
- }
-
- void firstOut(Arc& arc, const Node& node) const {
- if (node._id % _width < _width - 1) {
- arc._id = (_edge_limit + node._id % _width +
- (node._id / _width) * (_width - 1)) << 1 | 1;
- return;
- }
- if (node._id < _node_num - _width) {
- arc._id = node._id << 1 | 1;
- return;
- }
- if (node._id % _width > 0) {
- arc._id = (_edge_limit + node._id % _width +
- (node._id / _width) * (_width - 1) - 1) << 1;
- return;
- }
- if (node._id >= _width) {
- arc._id = (node._id - _width) << 1;
- return;
- }
- arc._id = -1;
- }
-
- void nextOut(Arc& arc) const {
- int nid = arc._id >> 1;
- if ((arc._id & 1) == 1) {
- if (nid >= _edge_limit) {
- nid = (nid - _edge_limit) % (_width - 1) +
- (nid - _edge_limit) / (_width - 1) * _width;
- if (nid < _node_num - _width) {
- arc._id = nid << 1 | 1;
- return;
- }
- }
- if (nid % _width > 0) {
- arc._id = (_edge_limit + nid % _width +
- (nid / _width) * (_width - 1) - 1) << 1;
- return;
- }
- if (nid >= _width) {
- arc._id = (nid - _width) << 1;
- return;
- }
- } else {
- if (nid >= _edge_limit) {
- nid = (nid - _edge_limit) % (_width - 1) +
- (nid - _edge_limit) / (_width - 1) * _width + 1;
- if (nid >= _width) {
- arc._id = (nid - _width) << 1;
- return;
- }
- }
- }
- arc._id = -1;
- }
-
- void firstIn(Arc& arc, const Node& node) const {
- if (node._id % _width < _width - 1) {
- arc._id = (_edge_limit + node._id % _width +
- (node._id / _width) * (_width - 1)) << 1;
- return;
- }
- if (node._id < _node_num - _width) {
- arc._id = node._id << 1;
- return;
- }
- if (node._id % _width > 0) {
- arc._id = (_edge_limit + node._id % _width +
- (node._id / _width) * (_width - 1) - 1) << 1 | 1;
- return;
- }
- if (node._id >= _width) {
- arc._id = (node._id - _width) << 1 | 1;
- return;
- }
- arc._id = -1;
- }
-
- void nextIn(Arc& arc) const {
- int nid = arc._id >> 1;
- if ((arc._id & 1) == 0) {
- if (nid >= _edge_limit) {
- nid = (nid - _edge_limit) % (_width - 1) +
- (nid - _edge_limit) / (_width - 1) * _width;
- if (nid < _node_num - _width) {
- arc._id = nid << 1;
- return;
- }
- }
- if (nid % _width > 0) {
- arc._id = (_edge_limit + nid % _width +
- (nid / _width) * (_width - 1) - 1) << 1 | 1;
- return;
- }
- if (nid >= _width) {
- arc._id = (nid - _width) << 1 | 1;
- return;
- }
- } else {
- if (nid >= _edge_limit) {
- nid = (nid - _edge_limit) % (_width - 1) +
- (nid - _edge_limit) / (_width - 1) * _width + 1;
- if (nid >= _width) {
- arc._id = (nid - _width) << 1 | 1;
- return;
- }
- }
- }
- arc._id = -1;
- }
-
- void firstInc(Edge& edge, bool& dir, const Node& node) const {
- if (node._id % _width < _width - 1) {
- edge._id = _edge_limit + node._id % _width +
- (node._id / _width) * (_width - 1);
- dir = true;
- return;
- }
- if (node._id < _node_num - _width) {
- edge._id = node._id;
- dir = true;
- return;
- }
- if (node._id % _width > 0) {
- edge._id = _edge_limit + node._id % _width +
- (node._id / _width) * (_width - 1) - 1;
- dir = false;
- return;
- }
- if (node._id >= _width) {
- edge._id = node._id - _width;
- dir = false;
- return;
- }
- edge._id = -1;
- dir = true;
- }
-
- void nextInc(Edge& edge, bool& dir) const {
- int nid = edge._id;
- if (dir) {
- if (nid >= _edge_limit) {
- nid = (nid - _edge_limit) % (_width - 1) +
- (nid - _edge_limit) / (_width - 1) * _width;
- if (nid < _node_num - _width) {
- edge._id = nid;
- return;
- }
- }
- if (nid % _width > 0) {
- edge._id = _edge_limit + nid % _width +
- (nid / _width) * (_width - 1) - 1;
- dir = false;
- return;
- }
- if (nid >= _width) {
- edge._id = nid - _width;
- dir = false;
- return;
- }
- } else {
- if (nid >= _edge_limit) {
- nid = (nid - _edge_limit) % (_width - 1) +
- (nid - _edge_limit) / (_width - 1) * _width + 1;
- if (nid >= _width) {
- edge._id = nid - _width;
- return;
- }
- }
- }
- edge._id = -1;
- dir = true;
- }
-
- Arc right(Node n) const {
- if (n._id % _width < _width - 1) {
- return Arc(((_edge_limit + n._id % _width +
- (n._id / _width) * (_width - 1)) << 1) | 1);
- } else {
- return INVALID;
- }
- }
-
- Arc left(Node n) const {
- if (n._id % _width > 0) {
- return Arc((_edge_limit + n._id % _width +
- (n._id / _width) * (_width - 1) - 1) << 1);
- } else {
- return INVALID;
- }
- }
-
- Arc up(Node n) const {
- if (n._id < _edge_limit) {
- return Arc((n._id << 1) | 1);
- } else {
- return INVALID;
- }
- }
-
- Arc down(Node n) const {
- if (n._id >= _width) {
- return Arc((n._id - _width) << 1);
- } else {
- return INVALID;
- }
- }
-
- private:
- int _width, _height;
- int _node_num, _edge_num;
- int _edge_limit;
- };
-
-
- typedef GraphExtender ExtendedGridGraphBase;
-
- /// \ingroup graphs
- ///
- /// \brief Grid graph class
- ///
- /// This class implements a special graph type. The nodes of the
- /// graph can be indexed by two integer \c (i,j) value where \c i is
- /// in the \c [0..width()-1] range and j is in the \c
- /// [0..height()-1] range. Two nodes are connected in the graph if
- /// the indexes differ exactly on one position and exactly one is
- /// the difference. The nodes of the graph can be indexed by position
- /// with the \c operator()() function. The positions of the nodes can be
- /// get with \c pos(), \c col() and \c row() members. The outgoing
- /// arcs can be retrieved with the \c right(), \c up(), \c left()
- /// and \c down() functions, where the bottom-left corner is the
- /// origin.
- ///
- /// \image html grid_graph.png
- /// \image latex grid_graph.eps "Grid graph" width=\textwidth
- ///
- /// A short example about the basic usage:
- ///\code
- /// GridGraph graph(rows, cols);
- /// GridGraph::NodeMap val(graph);
- /// for (int i = 0; i < graph.width(); ++i) {
- /// for (int j = 0; j < graph.height(); ++j) {
- /// val[graph(i, j)] = i + j;
- /// }
- /// }
- ///\endcode
- ///
- /// This graph type is fully conform to the \ref concepts::Graph
- /// "Graph" concept, and it also has an important extra feature
- /// that its maps are real \ref concepts::ReferenceMap
- /// "reference map"s.
- class GridGraph : public ExtendedGridGraphBase {
- public:
-
- typedef ExtendedGridGraphBase Parent;
-
- /// \brief Map to get the indices of the nodes as dim2::Point.
- ///
- /// Map to get the indices of the nodes as dim2::Point.
- class IndexMap {
- public:
- /// \brief The key type of the map
- typedef GridGraph::Node Key;
- /// \brief The value type of the map
- typedef dim2::Point Value;
-
- /// \brief Constructor
- ///
- /// Constructor
- IndexMap(const GridGraph& graph) : _graph(graph) {}
-
- /// \brief The subscript operator
- ///
- /// The subscript operator.
- Value operator[](Key key) const {
- return _graph.pos(key);
- }
-
- private:
- const GridGraph& _graph;
- };
-
- /// \brief Map to get the column of the nodes.
- ///
- /// Map to get the column of the nodes.
- class ColMap {
- public:
- /// \brief The key type of the map
- typedef GridGraph::Node Key;
- /// \brief The value type of the map
- typedef int Value;
-
- /// \brief Constructor
- ///
- /// Constructor
- ColMap(const GridGraph& graph) : _graph(graph) {}
-
- /// \brief The subscript operator
- ///
- /// The subscript operator.
- Value operator[](Key key) const {
- return _graph.col(key);
- }
-
- private:
- const GridGraph& _graph;
- };
-
- /// \brief Map to get the row of the nodes.
- ///
- /// Map to get the row of the nodes.
- class RowMap {
- public:
- /// \brief The key type of the map
- typedef GridGraph::Node Key;
- /// \brief The value type of the map
- typedef int Value;
-
- /// \brief Constructor
- ///
- /// Constructor
- RowMap(const GridGraph& graph) : _graph(graph) {}
-
- /// \brief The subscript operator
- ///
- /// The subscript operator.
- Value operator[](Key key) const {
- return _graph.row(key);
- }
-
- private:
- const GridGraph& _graph;
- };
-
- /// \brief Constructor
- ///
- /// Construct a grid graph with given size.
- GridGraph(int width, int height) { construct(width, height); }
-
- /// \brief Resize the graph
- ///
- /// Resize the graph. The function will fully destroy and rebuild
- /// the graph. This cause that the maps of the graph will
- /// reallocated automatically and the previous values will be
- /// lost.
- void resize(int width, int height) {
- Parent::notifier(Arc()).clear();
- Parent::notifier(Edge()).clear();
- Parent::notifier(Node()).clear();
- construct(width, height);
- Parent::notifier(Node()).build();
- Parent::notifier(Edge()).build();
- Parent::notifier(Arc()).build();
- }
-
- /// \brief The node on the given position.
- ///
- /// Gives back the node on the given position.
- Node operator()(int i, int j) const {
- return Parent::operator()(i, j);
- }
-
- /// \brief Gives back the column index of the node.
- ///
- /// Gives back the column index of the node.
- int col(Node n) const {
- return Parent::col(n);
- }
-
- /// \brief Gives back the row index of the node.
- ///
- /// Gives back the row index of the node.
- int row(Node n) const {
- return Parent::row(n);
- }
-
- /// \brief Gives back the position of the node.
- ///
- /// Gives back the position of the node, ie. the (col,row) pair.
- dim2::Point pos(Node n) const {
- return Parent::pos(n);
- }
-
- /// \brief Gives back the number of the columns.
- ///
- /// Gives back the number of the columns.
- int width() const {
- return Parent::width();
- }
-
- /// \brief Gives back the number of the rows.
- ///
- /// Gives back the number of the rows.
- int height() const {
- return Parent::height();
- }
-
- /// \brief Gives back the arc goes right from the node.
- ///
- /// Gives back the arc goes right from the node. If there is not
- /// outgoing arc then it gives back INVALID.
- Arc right(Node n) const {
- return Parent::right(n);
- }
-
- /// \brief Gives back the arc goes left from the node.
- ///
- /// Gives back the arc goes left from the node. If there is not
- /// outgoing arc then it gives back INVALID.
- Arc left(Node n) const {
- return Parent::left(n);
- }
-
- /// \brief Gives back the arc goes up from the node.
- ///
- /// Gives back the arc goes up from the node. If there is not
- /// outgoing arc then it gives back INVALID.
- Arc up(Node n) const {
- return Parent::up(n);
- }
-
- /// \brief Gives back the arc goes down from the node.
- ///
- /// Gives back the arc goes down from the node. If there is not
- /// outgoing arc then it gives back INVALID.
- Arc down(Node n) const {
- return Parent::down(n);
- }
-
- /// \brief Index map of the grid graph
- ///
- /// Just returns an IndexMap for the grid graph.
- IndexMap indexMap() const {
- return IndexMap(*this);
- }
-
- /// \brief Row map of the grid graph
- ///
- /// Just returns a RowMap for the grid graph.
- RowMap rowMap() const {
- return RowMap(*this);
- }
-
- /// \brief Column map of the grid graph
- ///
- /// Just returns a ColMap for the grid graph.
- ColMap colMap() const {
- return ColMap(*this);
- }
-
- };
-
-}
-#endif
Index: mon/hypercube_graph.h
===================================================================
--- lemon/hypercube_graph.h (revision 385)
+++ (revision )
@@ -1,440 +1,0 @@
-/* -*- 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 HYPERCUBE_GRAPH_H
-#define HYPERCUBE_GRAPH_H
-
-#include
-#include
-#include
-#include
-
-///\ingroup graphs
-///\file
-///\brief HypercubeGraph class.
-
-namespace lemon {
-
- class HypercubeGraphBase {
-
- public:
-
- typedef HypercubeGraphBase Graph;
-
- class Node;
- class Edge;
- class Arc;
-
- public:
-
- HypercubeGraphBase() {}
-
- protected:
-
- void construct(int dim) {
- LEMON_ASSERT(dim >= 1, "The number of dimensions must be at least 1.");
- _dim = dim;
- _node_num = 1 << dim;
- _edge_num = dim * (1 << (dim-1));
- }
-
- public:
-
- typedef True NodeNumTag;
- typedef True EdgeNumTag;
- typedef True ArcNumTag;
-
- int nodeNum() const { return _node_num; }
- int edgeNum() const { return _edge_num; }
- int arcNum() const { return 2 * _edge_num; }
-
- int maxNodeId() const { return _node_num - 1; }
- int maxEdgeId() const { return _edge_num - 1; }
- int maxArcId() const { return 2 * _edge_num - 1; }
-
- static Node nodeFromId(int id) { return Node(id); }
- static Edge edgeFromId(int id) { return Edge(id); }
- static Arc arcFromId(int id) { return Arc(id); }
-
- static int id(Node node) { return node._id; }
- static int id(Edge edge) { return edge._id; }
- static int id(Arc arc) { return arc._id; }
-
- Node u(Edge edge) const {
- int base = edge._id & ((1 << (_dim-1)) - 1);
- int k = edge._id >> (_dim-1);
- return ((base >> k) << (k+1)) | (base & ((1 << k) - 1));
- }
-
- Node v(Edge edge) const {
- int base = edge._id & ((1 << (_dim-1)) - 1);
- int k = edge._id >> (_dim-1);
- return ((base >> k) << (k+1)) | (base & ((1 << k) - 1)) | (1 << k);
- }
-
- Node source(Arc arc) const {
- return (arc._id & 1) == 1 ? u(arc) : v(arc);
- }
-
- Node target(Arc arc) const {
- return (arc._id & 1) == 1 ? v(arc) : u(arc);
- }
-
- typedef True FindEdgeTag;
- typedef True FindArcTag;
-
- Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
- if (prev != INVALID) return INVALID;
- int d = u._id ^ v._id;
- int k = 0;
- if (d == 0) return INVALID;
- for ( ; (d & 1) == 0; d >>= 1) ++k;
- if (d >> 1 != 0) return INVALID;
- return (k << (_dim-1)) | ((u._id >> (k+1)) << k) |
- (u._id & ((1 << k) - 1));
- }
-
- Arc findArc(Node u, Node v, Arc prev = INVALID) const {
- Edge edge = findEdge(u, v, prev);
- if (edge == INVALID) return INVALID;
- int k = edge._id >> (_dim-1);
- return ((u._id >> k) & 1) == 1 ? edge._id << 1 : (edge._id << 1) | 1;
- }
-
- class Node {
- friend class HypercubeGraphBase;
-
- protected:
- int _id;
- Node(int id) : _id(id) {}
- public:
- Node() {}
- Node (Invalid) : _id(-1) {}
- bool operator==(const Node node) const {return _id == node._id;}
- bool operator!=(const Node node) const {return _id != node._id;}
- bool operator<(const Node node) const {return _id < node._id;}
- };
-
- class Edge {
- friend class HypercubeGraphBase;
- friend class Arc;
-
- protected:
- int _id;
-
- Edge(int id) : _id(id) {}
-
- public:
- Edge() {}
- Edge (Invalid) : _id(-1) {}
- bool operator==(const Edge edge) const {return _id == edge._id;}
- bool operator!=(const Edge edge) const {return _id != edge._id;}
- bool operator<(const Edge edge) const {return _id < edge._id;}
- };
-
- class Arc {
- friend class HypercubeGraphBase;
-
- protected:
- int _id;
-
- Arc(int id) : _id(id) {}
-
- public:
- Arc() {}
- Arc (Invalid) : _id(-1) {}
- operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
- bool operator==(const Arc arc) const {return _id == arc._id;}
- bool operator!=(const Arc arc) const {return _id != arc._id;}
- bool operator<(const Arc arc) const {return _id < arc._id;}
- };
-
- void first(Node& node) const {
- node._id = _node_num - 1;
- }
-
- static void next(Node& node) {
- --node._id;
- }
-
- void first(Edge& edge) const {
- edge._id = _edge_num - 1;
- }
-
- static void next(Edge& edge) {
- --edge._id;
- }
-
- void first(Arc& arc) const {
- arc._id = 2 * _edge_num - 1;
- }
-
- static void next(Arc& arc) {
- --arc._id;
- }
-
- void firstInc(Edge& edge, bool& dir, const Node& node) const {
- edge._id = node._id >> 1;
- dir = (node._id & 1) == 0;
- }
-
- void nextInc(Edge& edge, bool& dir) const {
- Node n = dir ? u(edge) : v(edge);
- int k = (edge._id >> (_dim-1)) + 1;
- if (k < _dim) {
- edge._id = (k << (_dim-1)) |
- ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1));
- dir = ((n._id >> k) & 1) == 0;
- } else {
- edge._id = -1;
- dir = true;
- }
- }
-
- void firstOut(Arc& arc, const Node& node) const {
- arc._id = ((node._id >> 1) << 1) | (~node._id & 1);
- }
-
- void nextOut(Arc& arc) const {
- Node n = (arc._id & 1) == 1 ? u(arc) : v(arc);
- int k = (arc._id >> _dim) + 1;
- if (k < _dim) {
- arc._id = (k << (_dim-1)) |
- ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1));
- arc._id = (arc._id << 1) | (~(n._id >> k) & 1);
- } else {
- arc._id = -1;
- }
- }
-
- void firstIn(Arc& arc, const Node& node) const {
- arc._id = ((node._id >> 1) << 1) | (node._id & 1);
- }
-
- void nextIn(Arc& arc) const {
- Node n = (arc._id & 1) == 1 ? v(arc) : u(arc);
- int k = (arc._id >> _dim) + 1;
- if (k < _dim) {
- arc._id = (k << (_dim-1)) |
- ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1));
- arc._id = (arc._id << 1) | ((n._id >> k) & 1);
- } else {
- arc._id = -1;
- }
- }
-
- static bool direction(Arc arc) {
- return (arc._id & 1) == 1;
- }
-
- static Arc direct(Edge edge, bool dir) {
- return Arc((edge._id << 1) | (dir ? 1 : 0));
- }
-
- int dimension() const {
- return _dim;
- }
-
- bool projection(Node node, int n) const {
- return static_cast(node._id & (1 << n));
- }
-
- int dimension(Edge edge) const {
- return edge._id >> (_dim-1);
- }
-
- int dimension(Arc arc) const {
- return arc._id >> _dim;
- }
-
- int index(Node node) const {
- return node._id;
- }
-
- Node operator()(int ix) const {
- return Node(ix);
- }
-
- private:
- int _dim;
- int _node_num, _edge_num;
- };
-
-
- typedef GraphExtender ExtendedHypercubeGraphBase;
-
- /// \ingroup graphs
- ///
- /// \brief Hypercube graph class
- ///
- /// This class implements a special graph type. The nodes of the graph
- /// are indiced with integers with at most \c dim binary digits.
- /// Two nodes are connected in the graph if and only if their indices
- /// differ only on one position in the binary form.
- ///
- /// \note The type of the indices is chosen to \c int for efficiency
- /// reasons. Thus the maximum dimension of this implementation is 26
- /// (assuming that the size of \c int is 32 bit).
- ///
- /// This graph type is fully conform to the \ref concepts::Graph
- /// "Graph" concept, and it also has an important extra feature
- /// that its maps are real \ref concepts::ReferenceMap
- /// "reference map"s.
- class HypercubeGraph : public ExtendedHypercubeGraphBase {
- public:
-
- typedef ExtendedHypercubeGraphBase Parent;
-
- /// \brief Constructs a hypercube graph with \c dim dimensions.
- ///
- /// Constructs a hypercube graph with \c dim dimensions.
- HypercubeGraph(int dim) { construct(dim); }
-
- /// \brief The number of dimensions.
- ///
- /// Gives back the number of dimensions.
- int dimension() const {
- return Parent::dimension();
- }
-
- /// \brief Returns \c true if the n'th bit of the node is one.
- ///
- /// Returns \c true if the n'th bit of the node is one.
- bool projection(Node node, int n) const {
- return Parent::projection(node, n);
- }
-
- /// \brief The dimension id of an edge.
- ///
- /// Gives back the dimension id of the given edge.
- /// It is in the [0..dim-1] range.
- int dimension(Edge edge) const {
- return Parent::dimension(edge);
- }
-
- /// \brief The dimension id of an arc.
- ///
- /// Gives back the dimension id of the given arc.
- /// It is in the [0..dim-1] range.
- int dimension(Arc arc) const {
- return Parent::dimension(arc);
- }
-
- /// \brief The index of a node.
- ///
- /// Gives back the index of the given node.
- /// The lower bits of the integer describes the node.
- int index(Node node) const {
- return Parent::index(node);
- }
-
- /// \brief Gives back a node by its index.
- ///
- /// Gives back a node by its index.
- Node operator()(int ix) const {
- return Parent::operator()(ix);
- }
-
- /// \brief Number of nodes.
- int nodeNum() const { return Parent::nodeNum(); }
- /// \brief Number of edges.
- int edgeNum() const { return Parent::edgeNum(); }
- /// \brief Number of arcs.
- int arcNum() const { return Parent::arcNum(); }
-
- /// \brief Linear combination map.
- ///
- /// This map makes possible to give back a linear combination
- /// for each node. It works like the \c std::accumulate function,
- /// so it accumulates the \c bf binary function with the \c fv first
- /// value. The map accumulates only on that positions (dimensions)
- /// where the index of the node is one. The values that have to be
- /// accumulated should be given by the \c begin and \c end iterators
- /// and the length of this range should be equal to the dimension
- /// number of the graph.
- ///
- ///\code
- /// const int DIM = 3;
- /// HypercubeGraph graph(DIM);
- /// dim2::Point base[DIM];
- /// for (int k = 0; k < DIM; ++k) {
- /// base[k].x = rnd();
- /// base[k].y = rnd();
- /// }
- /// HypercubeGraph::HyperMap >
- /// pos(graph, base, base + DIM, dim2::Point(0.0, 0.0));
- ///\endcode
- ///
- /// \see HypercubeGraph
- template >
- class HyperMap {
- public:
-
- /// \brief The key type of the map
- typedef Node Key;
- /// \brief The value type of the map
- typedef T Value;
-
- /// \brief Constructor for HyperMap.
- ///
- /// Construct a HyperMap for the given graph. The values that have
- /// to be accumulated should be given by the \c begin and \c end
- /// iterators and the length of this range should be equal to the
- /// dimension number of the graph.
- ///
- /// This map accumulates the \c bf binary function with the \c fv
- /// first value on that positions (dimensions) where the index of
- /// the node is one.
- template
- HyperMap(const Graph& graph, It begin, It end,
- T fv = 0, const BF& bf = BF())
- : _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf)
- {
- LEMON_ASSERT(_values.size() == graph.dimension(),
- "Wrong size of range");
- }
-
- /// \brief The partial accumulated value.
- ///
- /// Gives back the partial accumulated value.
- Value operator[](const Key& k) const {
- Value val = _first_value;
- int id = _graph.index(k);
- int n = 0;
- while (id != 0) {
- if (id & 1) {
- val = _bin_func(val, _values[n]);
- }
- id >>= 1;
- ++n;
- }
- return val;
- }
-
- private:
- const Graph& _graph;
- std::vector _values;
- T _first_value;
- BF _bin_func;
- };
-
- };
-
-}
-
-#endif
Index: lemon/list_graph.h
===================================================================
--- lemon/list_graph.h (revision 341)
+++ lemon/list_graph.h (revision 313)
@@ -841,6 +841,6 @@
public:
- operator Edge() const {
- return id != -1 ? edgeFromId(id / 2) : INVALID;
+ operator Edge() const {
+ return id != -1 ? edgeFromId(id / 2) : INVALID;
}
Index: lemon/maps.h
===================================================================
--- lemon/maps.h (revision 314)
+++ lemon/maps.h (revision 327)
@@ -1856,405 +1856,4 @@
InverseMap inverse() const { return InverseMap(*_graph);}
- };
-
-
- /// \brief General invertable graph-map type.
-
- /// This type provides simple invertable graph-maps.
- /// The InvertableMap wraps an arbitrary ReadWriteMap
- /// and if a key is set to a new value then store it
- /// in the inverse map.
- ///
- /// The values of the map can be accessed
- /// with stl compatible forward iterator.
- ///
- /// \tparam _Graph The graph type.
- /// \tparam _Item The item type of the graph.
- /// \tparam _Value The value type of the map.
- ///
- /// \see IterableValueMap
- template
- class InvertableMap
- : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
- private:
-
- typedef typename ItemSetTraits<_Graph, _Item>::
- template Map<_Value>::Type Map;
- typedef _Graph Graph;
-
- typedef std::map<_Value, _Item> Container;
- Container _inv_map;
-
- public:
-
- /// The key type of InvertableMap (Node, Arc, Edge).
- typedef typename Map::Key Key;
- /// The value type of the InvertableMap.
- typedef typename Map::Value Value;
-
- /// \brief Constructor.
- ///
- /// Construct a new InvertableMap for the graph.
- ///
- explicit InvertableMap(const Graph& graph) : Map(graph) {}
-
- /// \brief Forward iterator for values.
- ///
- /// This iterator is an stl compatible forward
- /// iterator on the values of the map. The values can
- /// be accessed in the [beginValue, endValue) range.
- ///
- class ValueIterator
- : public std::iterator {
- friend class InvertableMap;
- private:
- ValueIterator(typename Container::const_iterator _it)
- : it(_it) {}
- public:
-
- ValueIterator() {}
-
- ValueIterator& operator++() { ++it; return *this; }
- ValueIterator operator++(int) {
- ValueIterator tmp(*this);
- operator++();
- return tmp;
- }
-
- const Value& operator*() const { return it->first; }
- const Value* operator->() const { return &(it->first); }
-
- bool operator==(ValueIterator jt) const { return it == jt.it; }
- bool operator!=(ValueIterator jt) const { return it != jt.it; }
-
- private:
- typename Container::const_iterator it;
- };
-
- /// \brief Returns an iterator to the first value.
- ///
- /// Returns an stl compatible iterator to the
- /// first value of the map. The values of the
- /// map can be accessed in the [beginValue, endValue)
- /// range.
- ValueIterator beginValue() const {
- return ValueIterator(_inv_map.begin());
- }
-
- /// \brief Returns an iterator after the last value.
- ///
- /// Returns an stl compatible iterator after the
- /// last value of the map. The values of the
- /// map can be accessed in the [beginValue, endValue)
- /// range.
- ValueIterator endValue() const {
- return ValueIterator(_inv_map.end());
- }
-
- /// \brief The setter function of the map.
- ///
- /// Sets the mapped value.
- void set(const Key& key, const Value& val) {
- Value oldval = Map::operator[](key);
- typename Container::iterator it = _inv_map.find(oldval);
- if (it != _inv_map.end() && it->second == key) {
- _inv_map.erase(it);
- }
- _inv_map.insert(make_pair(val, key));
- Map::set(key, val);
- }
-
- /// \brief The getter function of the map.
- ///
- /// It gives back the value associated with the key.
- typename MapTraits