r279:6307bbbf285b
Tue, 23 Sep 2008 18:42:49
[Not Reviewed]
0 comments (0 inline)
0
15
2
3
15
49
8
2
20
57
12
12
| 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
| 2 |
* |
|
| 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
|
| 4 |
* |
|
| 5 |
* Copyright (C) 2003-2008 |
|
| 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
| 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
| 8 |
* |
|
| 9 |
* Permission to use, modify and distribute this software is granted |
|
| 10 |
* provided that this copyright notice appears in all copies. For |
|
| 11 |
* precise terms see the accompanying LICENSE file. |
|
| 12 |
* |
|
| 13 |
* This software is provided "AS IS" with no warranty of any kind, |
|
| 14 |
* express or implied, and with no claim as to its suitability for any |
|
| 15 |
* purpose. |
|
| 16 |
* |
|
| 17 |
*/ |
|
| 18 |
|
|
| 19 |
/*! |
|
| 20 |
|
|
| 21 |
\page named-param Named Parameters |
|
| 22 |
|
|
| 23 |
\section named-func-param Named Function Parameters |
|
| 24 |
|
|
| 25 |
Several modern languages provide a convenient way to refer the |
|
| 26 |
function parameters by name also when you call the function. It is |
|
| 27 |
especially comfortable in case of a function having tons of parameters |
|
| 28 |
with natural default values. Sadly, C++ lack this amenity. |
|
| 29 |
|
|
| 30 |
However, with a crafty trick and with some little |
|
| 31 |
inconvenience, it is possible to emulate is. |
|
| 32 |
The example below shows how to do it. |
|
| 33 |
|
|
| 34 |
\code |
|
| 35 |
class namedFn |
|
| 36 |
{
|
|
| 37 |
int _id; |
|
| 38 |
double _val; |
|
| 39 |
int _dim; |
|
| 40 |
|
|
| 41 |
public: |
|
| 42 |
namedFn() : _id(0), _val(1), _dim(2) {}
|
|
| 43 |
namedFn& id(int p) { _id = p ; return *this; }
|
|
| 44 |
namedFn& val(double p) { _val = p ; return *this; }
|
|
| 45 |
namedFn& dim(int p) { _dim = p ; return *this; }
|
|
| 46 |
|
|
| 47 |
run() {
|
|
| 48 |
std::cout << "Here comes the function itself\n" << |
|
| 49 |
<< "With parameters " |
|
| 50 |
<< _id << ", " << _val << ", " << _dim << std::endl; |
|
| 51 |
} |
|
| 52 |
}; |
|
| 53 |
\endcode |
|
| 54 |
|
|
| 55 |
Then you can use it like this. |
|
| 56 |
|
|
| 57 |
\code |
|
| 58 |
namedFn().id(3).val(2).run(); |
|
| 59 |
\endcode |
|
| 60 |
|
|
| 61 |
The trick is obvious, each "named parameter" changes one component of |
|
| 62 |
the underlying class, then gives back a reference to it. Finally, |
|
| 63 |
<tt>run()</tt> executes the algorithm itself. |
|
| 64 |
|
|
| 65 |
\note Although it is a class, namedFn is used pretty much like as it were |
|
| 66 |
a function. That it why we called it namedFn instead of \c NamedFn. |
|
| 67 |
|
|
| 68 |
\note In fact, the final <tt>.run()</tt> could be made unnecessary, |
|
| 69 |
because the algorithm could also be implemented in the destructor of |
|
| 70 |
\c namedFn instead. This however would make it impossible to implement |
|
| 71 |
functions with return values, and would also cause serious problems when |
|
| 72 |
implementing \ref named-templ-func-param "named template parameters". |
|
| 73 |
<b>Therefore, by convention, <tt>.run()</tt> must be used |
|
| 74 |
explicitly to execute a function having named parameters |
|
| 75 |
everywhere in LEMON.</b> |
|
| 76 |
|
|
| 77 |
\section named-templ-func-param Named Function Template Parameters |
|
| 78 |
|
|
| 79 |
A named parameter can also be a template function. The usage is |
|
| 80 |
exactly the same, but the implementation behind is a kind of black |
|
| 81 |
magic and they are the dirtiest part of the LEMON code. |
|
| 82 |
|
|
| 83 |
You will probably never need to know how it works, but if you really |
|
| 84 |
committed, have a look at \ref lemon/graph_to_eps.h for an example. |
|
| 85 |
|
|
| 86 |
\section traits-classes Traits Classes |
|
| 87 |
|
|
| 88 |
A similar game can also be played when defining classes. In this case |
|
| 89 |
the type of the class attributes can be changed. Initially we have to |
|
| 90 |
define a special class called <em>Traits Class</em> defining the |
|
| 91 |
default type of the attributes. Then the types of these attributes can |
|
| 92 |
be changed in the same way as described in the next section. |
|
| 93 |
|
|
| 94 |
See \ref lemon::DijkstraDefaultTraits for an |
|
| 95 |
example how a traits class implementation looks like. |
|
| 96 |
|
|
| 97 |
\section named-templ-param Named Class Template Parameters |
|
| 98 |
|
|
| 99 |
If we would like to change the type of an attribute in a class that |
|
| 100 |
was instantiated by using a traits class as a template parameter, and |
|
| 101 |
the class contains named parameters, we do not have to instantiate again |
|
| 102 |
the class with new traits class, but instead adaptor classes can |
|
| 103 |
be used as shown in the following example. |
|
| 104 |
|
|
| 105 |
\code |
|
| 106 |
Dijkstra<>::SetPredMap<NullMap<Node,Arc> >::Create |
|
| 107 |
\endcode |
|
| 108 |
|
|
| 109 |
It can also be used in conjunction with other named template |
|
| 110 |
parameters in arbitrary order. |
|
| 111 |
|
|
| 112 |
\code |
|
| 113 |
Dijkstra<>::SetDistMap<MyMap>::SetPredMap<NullMap<Node,Arc> >::Create |
|
| 114 |
\endcode |
|
| 115 |
|
|
| 116 |
The result will be an instantiated Dijkstra class, in which the |
|
| 117 |
DistMap and the PredMap is modified. |
|
| 118 |
|
|
| 119 |
*/ |
| 1 |
#! /usr/bin/env python |
|
| 2 |
|
|
| 3 |
import sys |
|
| 4 |
import os |
|
| 5 |
|
|
| 6 |
if len(sys.argv)>1 and sys.argv[1] in ["-h","--help"]: |
|
| 7 |
print """ |
|
| 8 |
This utility just prints the length of the longest path |
|
| 9 |
in the revision graph from revison 0 to the current one. |
|
| 10 |
""" |
|
| 11 |
exit(0) |
|
| 12 |
plist = os.popen("hg parents --template='{rev}\n'").readlines()
|
|
| 13 |
if len(plist)>1: |
|
| 14 |
print "You are in the process of merging" |
|
| 15 |
exit(1) |
|
| 16 |
PAR = int(plist[0]) |
|
| 17 |
|
|
| 18 |
f = os.popen("hg log -r 0:tip --template='{rev} {parents}\n'").readlines()
|
|
| 19 |
REV = -1 |
|
| 20 |
lengths=[] |
|
| 21 |
for l in f: |
|
| 22 |
REV+=1 |
|
| 23 |
s = l.split() |
|
| 24 |
rev = int(s[0]) |
|
| 25 |
if REV != rev: |
|
| 26 |
print "Something is seriously wrong" |
|
| 27 |
exit(1) |
|
| 28 |
if len(s) == 1: |
|
| 29 |
par1 = par2 = rev - 1 |
|
| 30 |
elif len(s) == 2: |
|
| 31 |
par1 = par2 = int(s[1].split(":")[0])
|
|
| 32 |
else: |
|
| 33 |
par1 = int(s[1].split(":")[0])
|
|
| 34 |
par2 = int(s[2].split(":")[0])
|
|
| 35 |
if rev == 0: |
|
| 36 |
lengths.append(0) |
|
| 37 |
else: |
|
| 38 |
lengths.append(max(lengths[par1],lengths[par2])+1) |
|
| 39 |
print lengths[PAR] |
| 1 | 1 |
CMAKE_MINIMUM_REQUIRED(VERSION 2.6) |
| 2 | 2 |
|
| 3 |
#EXECUTE_PROCESS( |
|
| 4 |
# COMMAND hg id -i |
|
| 5 |
# OUTPUT_VARIABLE HG_REVISION |
|
| 6 |
# OUTPUT_STRIP_TRAILING_WHITESPACE) |
|
| 7 |
|
|
| 8 | 3 |
SET(PROJECT_NAME "LEMON") |
| 9 |
SET(PROJECT_VERSION_MAJOR "0") |
|
| 10 |
SET(PROJECT_VERSION_MINOR "99") |
|
| 11 |
SET(PROJECT_VERSION_PATCH "0") |
|
| 12 |
SET(PROJECT_VERSION |
|
| 13 |
|
|
| 4 |
SET(PROJECT_VERSION "hg-tip" CACHE STRING "The version string.") |
|
| 14 | 5 |
|
| 15 | 6 |
PROJECT(${PROJECT_NAME})
|
| 16 | 7 |
|
| 17 | 8 |
SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
|
| 18 | 9 |
|
| 19 | 10 |
INCLUDE(FindDoxygen) |
| 20 | 11 |
INCLUDE(FindGhostscript) |
| 21 | 12 |
|
| 22 | 13 |
ENABLE_TESTING() |
| 23 | 14 |
|
| 24 | 15 |
ADD_SUBDIRECTORY(lemon) |
| 25 | 16 |
ADD_SUBDIRECTORY(demo) |
| 26 | 17 |
ADD_SUBDIRECTORY(doc) |
| 27 | 18 |
ADD_SUBDIRECTORY(test) |
| 28 | 19 |
|
| 29 | 20 |
IF(WIN32) |
| 30 | 21 |
INSTALL(FILES ${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico
|
| 31 | 22 |
DESTINATION bin) |
| 32 | 23 |
ENDIF(WIN32) |
| 33 | 24 |
|
| 34 | 25 |
IF(WIN32) |
| 35 | 26 |
SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
|
| 36 | 27 |
SET(CPACK_PACKAGE_VENDOR |
| 37 | 28 |
"EGRES - Egervary Research Group on Combinatorial Optimization") |
| 38 | 29 |
SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY |
| 39 | 30 |
"LEMON - Library of Efficient Models and Optimization in Networks") |
| 40 | 31 |
SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
|
| 41 | 32 |
|
| 42 |
SET(CPACK_PACKAGE_VERSION_MAJOR ${PROJECT_VERSION_MAJOR})
|
|
| 43 |
SET(CPACK_PACKAGE_VERSION_MINOR ${PROJECT_VERSION_MINOR})
|
|
| 44 |
SET(CPACK_PACKAGE_VERSION_PATCH ${PROJECT_VERSION_PATCH})
|
|
| 45 | 33 |
SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
|
| 46 | 34 |
|
| 47 | 35 |
SET(CPACK_PACKAGE_INSTALL_DIRECTORY |
| 48 |
"${PROJECT_NAME} ${
|
|
| 36 |
"${PROJECT_NAME} ${PROJECT_VERSION}")
|
|
| 49 | 37 |
SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY |
| 50 |
"${PROJECT_NAME} ${
|
|
| 38 |
"${PROJECT_NAME} ${PROJECT_VERSION}")
|
|
| 51 | 39 |
|
| 52 | 40 |
# Variables to generate a component-based installer. |
| 53 | 41 |
#SET(CPACK_COMPONENTS_ALL headers library html_documentation) |
| 54 | 42 |
|
| 55 | 43 |
#SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers") |
| 56 | 44 |
#SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Static library") |
| 57 | 45 |
#SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation") |
| 58 | 46 |
|
| 59 | 47 |
#SET(CPACK_COMPONENT_HEADERS_DESCRIPTION |
| 60 | 48 |
# "C++ header files for use with the LEMON library") |
| 61 | 49 |
#SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION |
| 62 | 50 |
# "Static library used to build programs with LEMON") |
| 63 | 51 |
#SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION |
| 64 | 52 |
# "Doxygen generated documentation") |
| 65 | 53 |
|
| 66 | 54 |
#SET(CPACK_COMPONENT_HEADERS_DEPENDS library) |
| 67 | 55 |
|
| 68 | 56 |
#SET(CPACK_COMPONENT_HEADERS_GROUP "Development") |
| 69 | 57 |
#SET(CPACK_COMPONENT_LIBRARY_GROUP "Development") |
| 70 | 58 |
#SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation") |
| 71 | 59 |
|
| 72 | 60 |
#SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION |
| 73 | 61 |
# "Components needed to develop software using LEMON") |
| 74 | 62 |
#SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION |
| 75 | 63 |
# "Documentation of LEMON") |
| 76 | 64 |
|
| 77 | 65 |
#SET(CPACK_ALL_INSTALL_TYPES Full Developer) |
| 78 | 66 |
|
| 79 | 67 |
#SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full) |
| 80 | 68 |
#SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full) |
| 81 | 69 |
#SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full) |
| 82 | 70 |
|
| 83 | 71 |
SET(CPACK_GENERATOR "NSIS") |
| 84 | 72 |
SET(CPACK_NSIS_MUI_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico")
|
| 85 | 73 |
SET(CPACK_NSIS_MUI_UNIICON "${CMAKE_SOURCE_DIR}/cmake/nsis/uninstall.ico")
|
| 86 | 74 |
#SET(CPACK_PACKAGE_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
|
| 87 | 75 |
SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico") |
| 88 | 76 |
SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
|
| 89 | 77 |
SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu") |
| 90 | 78 |
SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu") |
| 91 | 79 |
SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu") |
| 92 | 80 |
SET(CPACK_NSIS_CREATE_ICONS_EXTRA " |
| 93 | 81 |
CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\doc\\\\index.html\\\" |
| 94 | 82 |
") |
| 95 | 83 |
SET(CPACK_NSIS_DELETE_ICONS_EXTRA " |
| 96 | 84 |
!insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP |
| 97 | 85 |
Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\" |
| 98 | 86 |
") |
| 99 | 87 |
|
| 100 | 88 |
INCLUDE(CPack) |
| 101 | 89 |
ENDIF(WIN32) |
| 1 |
20XX-XX-XX Version 1.0 released |
|
| 2 |
|
|
| 3 |
This is the first stable release of LEMON. Compared to the 0.x |
|
| 4 |
release series, it features a considerably smaller but more |
|
| 5 |
matured set of tools. The API has also completely revised and |
|
| 6 |
changed in several places. |
|
| 7 |
|
|
| 8 |
* The major name changes compared to the 0.x series |
|
| 9 |
* Graph -> Digraph, UGraph -> Graph |
|
| 10 |
* Edge -> Arc, UEdge -> Edge |
|
| 11 |
* source(UEdge)/target(UEdge) -> u(Edge)/v(Edge) |
|
| 12 |
* Other improvements |
|
| 13 |
* Better documentation |
|
| 14 |
* Reviewed and cleaned up codebase |
|
| 15 |
* CMake based build system (along with the autotools based one) |
|
| 16 |
* Contents of the library (ported from 0.x) |
|
| 17 |
* Algorithms |
|
| 18 |
* breadth-first search (bfs.h) |
|
| 19 |
* depth-first search (dfs.h) |
|
| 20 |
* Dijkstra's algorithm (dijkstra.h) |
|
| 21 |
* Kruskal's algorithm (kruskal.h) |
|
| 22 |
* Data structures |
|
| 23 |
* graph data structures (list_graph.h, smart_graph.h) |
|
| 24 |
* path data structures (path.h) |
|
| 25 |
* binary heap data structure (bin_heap.h) |
|
| 26 |
* union-find data structures (unionfind.h) |
|
| 27 |
* miscellaneous property maps (maps.h) |
|
| 28 |
* two dimensional vector and bounding box (dim2.h) |
|
| 29 |
* Concepts |
|
| 30 |
* graph structure concepts (concepts/digraph.h, concepts/graph.h, |
|
| 31 |
concepts/graph_components.h) |
|
| 32 |
* concepts for other structures (concepts/heap.h, concepts/maps.h, |
|
| 33 |
concepts/path.h) |
|
| 34 |
* Tools |
|
| 35 |
* Mersenne twister random number generator (random.h) |
|
| 36 |
* tools for measuring cpu and wall clock time (time_measure.h) |
|
| 37 |
* tools for counting steps and events (counter.h) |
|
| 38 |
* tool for parsing command line arguments (arg_parser.h) |
|
| 39 |
* tool for visualizing graphs (graph_to_eps.h) |
|
| 40 |
* tools for reading and writing data in LEMON Graph Format |
|
| 41 |
(lgf_reader.h, lgf_writer.h) |
|
| 42 |
* tools to handle the anomalies of calculations with |
|
| 43 |
floating point numbers (tolerance.h) |
|
| 44 |
* tools to manage RGB colors (color.h) |
|
| 45 |
* Infrastructure |
|
| 46 |
* extended assertion handling (assert.h) |
|
| 47 |
* exception classes and error handling (error.h) |
|
| 48 |
* concept checking (concept_check.h) |
|
| 49 |
* commonly used mathematical constants (math.h) |
| 1 | 1 |
dnl Process this file with autoconf to produce a configure script. |
| 2 | 2 |
|
| 3 | 3 |
dnl Version information. |
| 4 |
m4_define([lemon_version_number], |
|
| 4 |
m4_define([lemon_version_number], |
|
| 5 |
[m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
|
|
| 6 |
dnl m4_define([lemon_version_number], []) |
|
| 7 |
m4_define([lemon_hg_path], [m4_normalize(esyscmd([./scripts/chg-len.py]))]) |
|
| 5 | 8 |
m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i]))]) |
| 6 |
m4_define([lemon_version], [ifelse(lemon_version_number(), |
|
| 9 |
m4_define([lemon_version], [ifelse(lemon_version_number(), |
|
| 10 |
[], |
|
| 11 |
[lemon_hg_path().lemon_hg_revision()], |
|
| 12 |
[lemon_version_number()])]) |
|
| 7 | 13 |
|
| 8 | 14 |
AC_PREREQ([2.59]) |
| 9 | 15 |
AC_INIT([LEMON], [lemon_version()], [lemon-user@lemon.cs.elte.hu], [lemon]) |
| 10 | 16 |
AC_CONFIG_AUX_DIR([build-aux]) |
| 11 | 17 |
AC_CONFIG_MACRO_DIR([m4]) |
| 12 | 18 |
AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects nostdinc]) |
| 13 | 19 |
AC_CONFIG_SRCDIR([lemon/list_graph.h]) |
| 14 | 20 |
AC_CONFIG_HEADERS([config.h lemon/config.h]) |
| 15 | 21 |
|
| 16 | 22 |
lx_cmdline_cxxflags_set=${CXXFLAGS+set}
|
| 17 | 23 |
|
| 18 | 24 |
dnl Checks for programs. |
| 19 | 25 |
AC_PROG_CXX |
| 20 | 26 |
AC_PROG_CXXCPP |
| 21 | 27 |
AC_PROG_INSTALL |
| 22 | 28 |
AC_DISABLE_SHARED |
| 23 | 29 |
AC_PROG_LIBTOOL |
| 24 | 30 |
|
| 25 | 31 |
AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no]) |
| 26 | 32 |
AC_CHECK_PROG([gs_found],[gs],[yes],[no]) |
| 27 | 33 |
|
| 28 | 34 |
dnl Set custom compiler flags when using g++. |
| 29 | 35 |
if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes; then |
| 30 | 36 |
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" |
| 31 | 37 |
fi |
| 32 | 38 |
|
| 33 | 39 |
dnl Checks for libraries. |
| 34 | 40 |
#LX_CHECK_GLPK |
| 35 | 41 |
#LX_CHECK_CPLEX |
| 36 | 42 |
#LX_CHECK_SOPLEX |
| 37 | 43 |
|
| 38 | 44 |
dnl Disable/enable building the demo programs. |
| 39 | 45 |
AC_ARG_ENABLE([demo], |
| 40 | 46 |
AS_HELP_STRING([--enable-demo], [build the demo programs]) |
| 41 | 47 |
AS_HELP_STRING([--disable-demo], [do not build the demo programs @<:@default@:>@]), |
| 42 | 48 |
[], [enable_demo=no]) |
| 43 | 49 |
AC_MSG_CHECKING([whether to build the demo programs]) |
| 44 | 50 |
if test x"$enable_demo" != x"no"; then |
| 45 | 51 |
AC_MSG_RESULT([yes]) |
| 46 | 52 |
else |
| 47 | 53 |
AC_MSG_RESULT([no]) |
| 48 | 54 |
fi |
| 49 | 55 |
AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"]) |
| 50 | 56 |
|
| 51 | 57 |
dnl Disable/enable building the binary tools. |
| 52 | 58 |
AC_ARG_ENABLE([tools], |
| 53 | 59 |
AS_HELP_STRING([--enable-tools], [build additional tools @<:@default@:>@]) |
| 54 | 60 |
AS_HELP_STRING([--disable-tools], [do not build additional tools]), |
| 55 | 61 |
[], [enable_tools=yes]) |
| 56 | 62 |
AC_MSG_CHECKING([whether to build the additional tools]) |
| 57 | 63 |
if test x"$enable_tools" != x"no"; then |
| 58 | 64 |
AC_MSG_RESULT([yes]) |
| 59 | 65 |
else |
| 60 | 66 |
AC_MSG_RESULT([no]) |
| 61 | 67 |
fi |
| 62 | 68 |
AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"]) |
| 63 | 69 |
|
| 64 | 70 |
dnl Disable/enable building the benchmarks. |
| 65 | 71 |
AC_ARG_ENABLE([benchmark], |
| 66 | 72 |
AS_HELP_STRING([--enable-benchmark], [build the benchmarks]) |
| 67 | 73 |
AS_HELP_STRING([--disable-benchmark], [do not build the benchmarks @<:@default@:>@]), |
| 68 | 74 |
[], [enable_benchmark=no]) |
| 69 | 75 |
AC_MSG_CHECKING([whether to build the benchmarks]) |
| 70 | 76 |
if test x"$enable_benchmark" != x"no"; then |
| 71 | 77 |
AC_MSG_RESULT([yes]) |
| 72 | 78 |
else |
| 73 | 79 |
AC_MSG_RESULT([no]) |
| 74 | 80 |
fi |
| 75 | 81 |
AM_CONDITIONAL([WANT_BENCHMARK], [test x"$enable_benchmark" != x"no"]) |
| 76 | 82 |
|
| 77 | 83 |
dnl Checks for header files. |
| 78 | 84 |
AC_CHECK_HEADERS(limits.h sys/time.h sys/times.h unistd.h) |
| 79 | 85 |
|
| 80 | 86 |
dnl Checks for typedefs, structures, and compiler characteristics. |
| 81 | 87 |
AC_C_CONST |
| 82 | 88 |
AC_C_INLINE |
| 83 | 89 |
AC_TYPE_SIZE_T |
| 84 | 90 |
AC_HEADER_TIME |
| 85 | 91 |
AC_STRUCT_TM |
| 86 | 92 |
|
| 87 | 93 |
dnl Checks for library functions. |
| 88 | 94 |
AC_HEADER_STDC |
| 89 | 95 |
AC_CHECK_FUNCS(gettimeofday times ctime_r) |
| 90 | 96 |
|
| 91 | 97 |
dnl Add dependencies on files generated by configure. |
| 92 | 98 |
AC_SUBST([CONFIG_STATUS_DEPENDENCIES], |
| 93 | 99 |
['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in']) |
| 94 | 100 |
|
| 95 | 101 |
AC_CONFIG_FILES([ |
| 96 | 102 |
Makefile |
| 97 | 103 |
doc/Doxyfile |
| 98 | 104 |
lemon/lemon.pc |
| 99 | 105 |
]) |
| 100 | 106 |
|
| 101 | 107 |
AC_OUTPUT |
| 102 | 108 |
| 1 | 1 |
EXTRA_DIST += \ |
| 2 | 2 |
doc/Doxyfile.in \ |
| 3 | 3 |
doc/coding_style.dox \ |
| 4 | 4 |
doc/dirs.dox \ |
| 5 | 5 |
doc/groups.dox \ |
| 6 | 6 |
doc/lgf.dox \ |
| 7 | 7 |
doc/license.dox \ |
| 8 | 8 |
doc/mainpage.dox \ |
| 9 |
doc/named-param.dox \ |
|
| 9 | 10 |
doc/namespaces.dox \ |
| 10 | 11 |
doc/html \ |
| 11 | 12 |
doc/CMakeLists.txt |
| 12 | 13 |
|
| 13 | 14 |
DOC_EPS_IMAGES18 = \ |
| 14 | 15 |
nodeshape_0.eps \ |
| 15 | 16 |
nodeshape_1.eps \ |
| 16 | 17 |
nodeshape_2.eps \ |
| 17 | 18 |
nodeshape_3.eps \ |
| 18 | 19 |
nodeshape_4.eps |
| 19 | 20 |
|
| 20 | 21 |
DOC_EPS_IMAGES = \ |
| 21 | 22 |
$(DOC_EPS_IMAGES18) |
| 22 | 23 |
|
| 23 | 24 |
DOC_PNG_IMAGES = \ |
| 24 | 25 |
$(DOC_EPS_IMAGES:%.eps=doc/gen-images/%.png) |
| 25 | 26 |
|
| 26 | 27 |
EXTRA_DIST += $(DOC_EPS_IMAGES:%=doc/images/%) |
| 27 | 28 |
|
| 28 | 29 |
doc/html: |
| 29 | 30 |
$(MAKE) $(AM_MAKEFLAGS) html |
| 30 | 31 |
|
| 31 | 32 |
GS_COMMAND=gs -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 |
| 32 | 33 |
|
| 33 | 34 |
$(DOC_EPS_IMAGES18:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps |
| 34 | 35 |
-mkdir doc/gen-images |
| 35 | 36 |
if test ${gs_found} = yes; then \
|
| 36 | 37 |
$(GS_COMMAND) -sDEVICE=pngalpha -r18 -sOutputFile=$@ $<; \ |
| 37 | 38 |
else \ |
| 38 | 39 |
echo; \ |
| 39 | 40 |
echo "Ghostscript not found."; \ |
| 40 | 41 |
echo; \ |
| 41 | 42 |
exit 1; \ |
| 42 | 43 |
fi |
| 43 | 44 |
|
| 44 | 45 |
html-local: $(DOC_PNG_IMAGES) |
| 45 | 46 |
if test ${doxygen_found} = yes; then \
|
| 46 | 47 |
cd doc; \ |
| 47 | 48 |
doxygen Doxyfile; \ |
| 48 | 49 |
cd ..; \ |
| 49 | 50 |
else \ |
| 50 | 51 |
echo; \ |
| 51 | 52 |
echo "Doxygen not found."; \ |
| 52 | 53 |
echo; \ |
| 53 | 54 |
exit 1; \ |
| 54 | 55 |
fi |
| 55 | 56 |
|
| 56 | 57 |
clean-local: |
| 57 | 58 |
-rm -rf doc/html |
| 58 | 59 |
-rm -f doc/doxygen.log |
| 59 | 60 |
-rm -f $(DOC_PNG_IMAGES) |
| 60 | 61 |
-rm -rf doc/gen-images |
| 61 | 62 |
|
| 62 | 63 |
update-external-tags: |
| 63 | 64 |
wget -O doc/libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag && \ |
| 64 | 65 |
mv doc/libstdc++.tag.tmp doc/libstdc++.tag || \ |
| 65 | 66 |
rm doc/libstdc++.tag.tmp |
| 66 | 67 |
|
| 67 | 68 |
install-html-local: doc/html |
| 68 | 69 |
@$(NORMAL_INSTALL) |
| 69 | 70 |
$(mkinstalldirs) $(DESTDIR)$(htmldir)/docs |
| 70 | 71 |
for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
|
| 71 | 72 |
f="`echo $$p | sed -e 's|^.*/||'`"; \ |
| 72 | 73 |
echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f"; \ |
| 73 | 74 |
$(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f; \ |
| 74 | 75 |
done |
| 75 | 76 |
|
| 76 | 77 |
uninstall-local: |
| 77 | 78 |
@$(NORMAL_UNINSTALL) |
| 78 | 79 |
for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
|
| 79 | 80 |
f="`echo $$p | sed -e 's|^.*/||'`"; \ |
| 80 | 81 |
echo " rm -f $(DESTDIR)$(htmldir)/docs/$$f"; \ |
| 81 | 82 |
rm -f $(DESTDIR)$(htmldir)/docs/$$f; \ |
| 82 | 83 |
done |
| 83 | 84 |
|
| 84 | 85 |
.PHONY: update-external-tags |
| 1 | 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
| 2 | 2 |
* |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 | 5 |
* Copyright (C) 2003-2008 |
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 |
#ifndef LEMON_ARG_PARSER |
|
| 20 |
#define LEMON_ARG_PARSER |
|
| 19 |
#ifndef LEMON_ARG_PARSER_H |
|
| 20 |
#define LEMON_ARG_PARSER_H |
|
| 21 | 21 |
|
| 22 | 22 |
#include <vector> |
| 23 | 23 |
#include <map> |
| 24 | 24 |
#include <list> |
| 25 | 25 |
#include <string> |
| 26 | 26 |
#include <iostream> |
| 27 | 27 |
#include <sstream> |
| 28 | 28 |
#include <algorithm> |
| 29 | 29 |
#include <lemon/assert.h> |
| 30 | 30 |
|
| 31 | 31 |
///\ingroup misc |
| 32 | 32 |
///\file |
| 33 | 33 |
///\brief A tool to parse command line arguments. |
| 34 | 34 |
|
| 35 | 35 |
namespace lemon {
|
| 36 | 36 |
|
| 37 | 37 |
///Command line arguments parser |
| 38 | 38 |
|
| 39 | 39 |
///\ingroup misc |
| 40 | 40 |
///Command line arguments parser. |
| 41 | 41 |
/// |
| 42 | 42 |
///For a complete example see the \ref arg_parser_demo.cc demo file. |
| 43 | 43 |
class ArgParser {
|
| 44 | 44 |
|
| 45 | 45 |
static void _showHelp(void *p); |
| 46 | 46 |
protected: |
| 47 | 47 |
|
| 48 | 48 |
int _argc; |
| 49 | 49 |
const char **_argv; |
| 50 | 50 |
|
| 51 | 51 |
enum OptType { UNKNOWN=0, BOOL=1, STRING=2, DOUBLE=3, INTEGER=4, FUNC=5 };
|
| 52 | 52 |
|
| 53 | 53 |
class ParData {
|
| 54 | 54 |
public: |
| 55 | 55 |
union {
|
| 56 | 56 |
bool *bool_p; |
| 57 | 57 |
int *int_p; |
| 58 | 58 |
double *double_p; |
| 59 | 59 |
std::string *string_p; |
| 60 | 60 |
struct {
|
| 61 | 61 |
void (*p)(void *); |
| 62 | 62 |
void *data; |
| 63 | 63 |
} func_p; |
| 64 | 64 |
|
| 65 | 65 |
}; |
| 66 | 66 |
std::string help; |
| 67 | 67 |
bool mandatory; |
| 68 | 68 |
OptType type; |
| 69 | 69 |
bool set; |
| 70 | 70 |
bool ingroup; |
| 71 | 71 |
bool has_syn; |
| 72 | 72 |
bool syn; |
| 73 | 73 |
bool self_delete; |
| 74 | 74 |
ParData() : mandatory(false), type(UNKNOWN), set(false), ingroup(false), |
| 75 | 75 |
has_syn(false), syn(false), self_delete(false) {}
|
| 76 | 76 |
}; |
| 77 | 77 |
|
| 78 | 78 |
typedef std::map<std::string,ParData> Opts; |
| 79 | 79 |
Opts _opts; |
| 80 | 80 |
|
| 81 | 81 |
class GroupData |
| 82 | 82 |
{
|
| 83 | 83 |
public: |
| 84 | 84 |
typedef std::list<std::string> Opts; |
| 85 | 85 |
Opts opts; |
| 86 | 86 |
bool only_one; |
| 87 | 87 |
bool mandatory; |
| 88 | 88 |
GroupData() :only_one(false), mandatory(false) {}
|
| 89 | 89 |
}; |
| 90 | 90 |
|
| 91 | 91 |
typedef std::map<std::string,GroupData> Groups; |
| 92 | 92 |
Groups _groups; |
| 93 | 93 |
|
| 94 | 94 |
struct OtherArg |
| 95 | 95 |
{
|
| 96 | 96 |
std::string name; |
| 97 | 97 |
std::string help; |
| 98 | 98 |
OtherArg(std::string n, std::string h) :name(n), help(h) {}
|
| 99 | 99 |
|
| 100 | 100 |
}; |
| 101 | 101 |
|
| 102 | 102 |
std::vector<OtherArg> _others_help; |
| 103 | 103 |
std::vector<std::string> _file_args; |
| 104 | 104 |
std::string _command_name; |
| 105 | 105 |
|
| 106 | 106 |
|
| 107 | 107 |
private: |
| 108 | 108 |
//Bind a function to an option. |
| 109 | 109 |
|
| 110 | 110 |
//\param name The name of the option. The leading '-' must be omitted. |
| 111 | 111 |
//\param help A help string. |
| 112 | 112 |
//\retval func The function to be called when the option is given. It |
| 113 | 113 |
// must be of type "void f(void *)" |
| 114 | 114 |
//\param data Data to be passed to \c func |
| 115 | 115 |
ArgParser &funcOption(const std::string &name, |
| 116 | 116 |
const std::string &help, |
| ... | ... |
@@ -289,97 +289,97 @@ |
| 289 | 289 |
///Start the parsing process |
| 290 | 290 |
ArgParser &parse(); |
| 291 | 291 |
|
| 292 | 292 |
/// Synonym for parse() |
| 293 | 293 |
ArgParser &run() |
| 294 | 294 |
{
|
| 295 | 295 |
return parse(); |
| 296 | 296 |
} |
| 297 | 297 |
|
| 298 | 298 |
///Give back the command name (the 0th argument) |
| 299 | 299 |
const std::string &commandName() const { return _command_name; }
|
| 300 | 300 |
|
| 301 | 301 |
///Check if an opion has been given to the command. |
| 302 | 302 |
bool given(std::string op) const |
| 303 | 303 |
{
|
| 304 | 304 |
Opts::const_iterator i = _opts.find(op); |
| 305 | 305 |
return i!=_opts.end()?i->second.set:false; |
| 306 | 306 |
} |
| 307 | 307 |
|
| 308 | 308 |
|
| 309 | 309 |
///Magic type for operator[] |
| 310 | 310 |
|
| 311 | 311 |
///This is the type of the return value of ArgParser::operator[](). |
| 312 | 312 |
///It automatically converts to \c int, \c double, \c bool or |
| 313 | 313 |
///\c std::string if the type of the option matches, otherwise it |
| 314 | 314 |
///throws an exception (i.e. it performs runtime type checking). |
| 315 | 315 |
class RefType |
| 316 | 316 |
{
|
| 317 | 317 |
const ArgParser &_parser; |
| 318 | 318 |
std::string _name; |
| 319 | 319 |
public: |
| 320 | 320 |
///\e |
| 321 | 321 |
RefType(const ArgParser &p,const std::string &n) :_parser(p),_name(n) {}
|
| 322 | 322 |
///\e |
| 323 | 323 |
operator bool() |
| 324 | 324 |
{
|
| 325 | 325 |
Opts::const_iterator i = _parser._opts.find(_name); |
| 326 | 326 |
LEMON_ASSERT(i!=_parser._opts.end(), |
| 327 | 327 |
std::string()+"Unkown option: '"+_name+"'"); |
| 328 | 328 |
LEMON_ASSERT(i->second.type==ArgParser::BOOL, |
| 329 | 329 |
std::string()+"'"+_name+"' is a bool option"); |
| 330 | 330 |
return *(i->second.bool_p); |
| 331 | 331 |
} |
| 332 | 332 |
///\e |
| 333 | 333 |
operator std::string() |
| 334 | 334 |
{
|
| 335 | 335 |
Opts::const_iterator i = _parser._opts.find(_name); |
| 336 | 336 |
LEMON_ASSERT(i!=_parser._opts.end(), |
| 337 | 337 |
std::string()+"Unkown option: '"+_name+"'"); |
| 338 | 338 |
LEMON_ASSERT(i->second.type==ArgParser::STRING, |
| 339 | 339 |
std::string()+"'"+_name+"' is a string option"); |
| 340 | 340 |
return *(i->second.string_p); |
| 341 | 341 |
} |
| 342 | 342 |
///\e |
| 343 | 343 |
operator double() |
| 344 | 344 |
{
|
| 345 | 345 |
Opts::const_iterator i = _parser._opts.find(_name); |
| 346 | 346 |
LEMON_ASSERT(i!=_parser._opts.end(), |
| 347 | 347 |
std::string()+"Unkown option: '"+_name+"'"); |
| 348 | 348 |
LEMON_ASSERT(i->second.type==ArgParser::DOUBLE || |
| 349 | 349 |
i->second.type==ArgParser::INTEGER, |
| 350 | 350 |
std::string()+"'"+_name+"' is a floating point option"); |
| 351 | 351 |
return i->second.type==ArgParser::DOUBLE ? |
| 352 | 352 |
*(i->second.double_p) : *(i->second.int_p); |
| 353 | 353 |
} |
| 354 | 354 |
///\e |
| 355 | 355 |
operator int() |
| 356 | 356 |
{
|
| 357 | 357 |
Opts::const_iterator i = _parser._opts.find(_name); |
| 358 | 358 |
LEMON_ASSERT(i!=_parser._opts.end(), |
| 359 | 359 |
std::string()+"Unkown option: '"+_name+"'"); |
| 360 | 360 |
LEMON_ASSERT(i->second.type==ArgParser::INTEGER, |
| 361 | 361 |
std::string()+"'"+_name+"' is an integer option"); |
| 362 | 362 |
return *(i->second.int_p); |
| 363 | 363 |
} |
| 364 | 364 |
|
| 365 | 365 |
}; |
| 366 | 366 |
|
| 367 | 367 |
///Give back the value of an option |
| 368 | 368 |
|
| 369 | 369 |
///Give back the value of an option. |
| 370 | 370 |
///\sa RefType |
| 371 | 371 |
RefType operator[](const std::string &n) const |
| 372 | 372 |
{
|
| 373 | 373 |
return RefType(*this, n); |
| 374 | 374 |
} |
| 375 | 375 |
|
| 376 | 376 |
///Give back the non-option type arguments. |
| 377 | 377 |
|
| 378 | 378 |
///Give back a reference to a vector consisting of the program arguments |
| 379 | 379 |
///not starting with a '-' character. |
| 380 | 380 |
const std::vector<std::string> &files() const { return _file_args; }
|
| 381 | 381 |
|
| 382 | 382 |
}; |
| 383 | 383 |
} |
| 384 | 384 |
|
| 385 |
#endif // |
|
| 385 |
#endif // LEMON_ARG_PARSER_H |
| 1 | 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
| 2 | 2 |
* |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 | 5 |
* Copyright (C) 2003-2008 |
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
#ifndef LEMON_ASSERT_H |
| 20 | 20 |
#define LEMON_ASSERT_H |
| 21 | 21 |
|
| 22 | 22 |
/// \ingroup exceptions |
| 23 | 23 |
/// \file |
| 24 | 24 |
/// \brief Extended assertion handling |
| 25 | 25 |
|
| 26 | 26 |
#include <lemon/error.h> |
| 27 | 27 |
|
| 28 | 28 |
namespace lemon {
|
| 29 | 29 |
|
| 30 |
inline void assert_fail_log(const char *file, int line, const char *function, |
|
| 31 |
const char *message, const char *assertion) |
|
| 30 |
inline void assert_fail_abort(const char *file, int line, |
|
| 31 |
const char *function, const char* message, |
|
| 32 |
const char *assertion) |
|
| 32 | 33 |
{
|
| 33 | 34 |
std::cerr << file << ":" << line << ": "; |
| 34 | 35 |
if (function) |
| 35 | 36 |
std::cerr << function << ": "; |
| 36 | 37 |
std::cerr << message; |
| 37 | 38 |
if (assertion) |
| 38 | 39 |
std::cerr << " (assertion '" << assertion << "' failed)"; |
| 39 | 40 |
std::cerr << std::endl; |
| 40 |
} |
|
| 41 |
|
|
| 42 |
inline void assert_fail_abort(const char *file, int line, |
|
| 43 |
const char *function, const char* message, |
|
| 44 |
const char *assertion) |
|
| 45 |
{
|
|
| 46 |
assert_fail_log(file, line, function, message, assertion); |
|
| 47 | 41 |
std::abort(); |
| 48 | 42 |
} |
| 49 | 43 |
|
| 50 | 44 |
namespace _assert_bits {
|
| 51 | 45 |
|
| 52 | 46 |
|
| 53 | 47 |
inline const char* cstringify(const std::string& str) {
|
| 54 | 48 |
return str.c_str(); |
| 55 | 49 |
} |
| 56 | 50 |
|
| 57 | 51 |
inline const char* cstringify(const char* str) {
|
| 58 | 52 |
return str; |
| 59 | 53 |
} |
| 60 | 54 |
} |
| 61 | 55 |
} |
| 62 | 56 |
|
| 63 | 57 |
#endif // LEMON_ASSERT_H |
| 64 | 58 |
|
| 65 | 59 |
#undef LEMON_ASSERT |
| 66 |
#undef LEMON_FIXME |
|
| 67 | 60 |
#undef LEMON_DEBUG |
| 68 | 61 |
|
| 69 |
#if (defined(LEMON_ASSERT_LOG) ? 1 : 0) + \ |
|
| 70 |
(defined(LEMON_ASSERT_ABORT) ? 1 : 0) + \ |
|
| 62 |
#if (defined(LEMON_ASSERT_ABORT) ? 1 : 0) + \ |
|
| 71 | 63 |
(defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) > 1 |
| 72 | 64 |
#error "LEMON assertion system is not set properly" |
| 73 | 65 |
#endif |
| 74 | 66 |
|
| 75 |
#if ((defined(LEMON_ASSERT_LOG) ? 1 : 0) + \ |
|
| 76 |
(defined(LEMON_ASSERT_ABORT) ? 1 : 0) + \ |
|
| 67 |
#if ((defined(LEMON_ASSERT_ABORT) ? 1 : 0) + \ |
|
| 77 | 68 |
(defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) == 1 || \ |
| 78 | 69 |
defined(LEMON_ENABLE_ASSERTS)) && \ |
| 79 | 70 |
(defined(LEMON_DISABLE_ASSERTS) || \ |
| 80 | 71 |
defined(NDEBUG)) |
| 81 | 72 |
#error "LEMON assertion system is not set properly" |
| 82 | 73 |
#endif |
| 83 | 74 |
|
| 84 | 75 |
|
| 85 |
#if defined LEMON_ASSERT_LOG |
|
| 86 |
# undef LEMON_ASSERT_HANDLER |
|
| 87 |
# define LEMON_ASSERT_HANDLER ::lemon::assert_fail_log |
|
| 88 |
#elif defined LEMON_ASSERT_ABORT |
|
| 76 |
#if defined LEMON_ASSERT_ABORT |
|
| 89 | 77 |
# undef LEMON_ASSERT_HANDLER |
| 90 | 78 |
# define LEMON_ASSERT_HANDLER ::lemon::assert_fail_abort |
| 91 | 79 |
#elif defined LEMON_ASSERT_CUSTOM |
| 92 | 80 |
# undef LEMON_ASSERT_HANDLER |
| 93 | 81 |
# ifndef LEMON_CUSTOM_ASSERT_HANDLER |
| 94 | 82 |
# error "LEMON_CUSTOM_ASSERT_HANDLER is not set" |
| 95 | 83 |
# endif |
| 96 | 84 |
# define LEMON_ASSERT_HANDLER LEMON_CUSTOM_ASSERT_HANDLER |
| 97 | 85 |
#elif defined LEMON_DISABLE_ASSERTS |
| 98 | 86 |
# undef LEMON_ASSERT_HANDLER |
| 99 | 87 |
#elif defined NDEBUG |
| 100 | 88 |
# undef LEMON_ASSERT_HANDLER |
| 101 | 89 |
#else |
| 102 | 90 |
# define LEMON_ASSERT_HANDLER ::lemon::assert_fail_abort |
| 103 | 91 |
#endif |
| 104 | 92 |
|
| 105 | 93 |
#ifndef LEMON_FUNCTION_NAME |
| 106 | 94 |
# if defined __GNUC__ |
| 107 | 95 |
# define LEMON_FUNCTION_NAME (__PRETTY_FUNCTION__) |
| 108 | 96 |
# elif defined _MSC_VER |
| 109 | 97 |
# define LEMON_FUNCTION_NAME (__FUNCSIG__) |
| 98 |
# elif __STDC_VERSION__ >= 199901L |
|
| 99 |
# define LEMON_FUNCTION_NAME (__func__) |
|
| 110 | 100 |
# else |
| 111 |
# define LEMON_FUNCTION_NAME ( |
|
| 101 |
# define LEMON_FUNCTION_NAME ("<unknown>")
|
|
| 112 | 102 |
# endif |
| 113 | 103 |
#endif |
| 114 | 104 |
|
| 115 | 105 |
#ifdef DOXYGEN |
| 116 | 106 |
|
| 117 | 107 |
/// \ingroup exceptions |
| 118 | 108 |
/// |
| 119 | 109 |
/// \brief Macro for assertion with customizable message |
| 120 | 110 |
/// |
| 121 |
/// Macro for assertion with customizable message. \param exp An |
|
| 122 |
/// expression that must be convertible to \c bool. If it is \c |
|
| 123 |
/// false, then an assertion is raised. The concrete behaviour depends |
|
| 124 |
/// on the settings of the assertion system. \param msg A <tt>const |
|
| 125 |
/// char*</tt> parameter, which can be used to provide information |
|
| 126 |
/// about the circumstances of the failed assertion. |
|
| 111 |
/// Macro for assertion with customizable message. |
|
| 112 |
/// \param exp An expression that must be convertible to \c bool. If it is \c |
|
| 113 |
/// false, then an assertion is raised. The concrete behaviour depends on the |
|
| 114 |
/// settings of the assertion system. |
|
| 115 |
/// \param msg A <tt>const char*</tt> parameter, which can be used to provide |
|
| 116 |
/// information about the circumstances of the failed assertion. |
|
| 127 | 117 |
/// |
| 128 | 118 |
/// The assertions are enabled in the default behaviour. |
| 129 | 119 |
/// You can disable them with the following code: |
| 130 | 120 |
/// \code |
| 131 | 121 |
/// #define LEMON_DISABLE_ASSERTS |
| 132 | 122 |
/// \endcode |
| 133 | 123 |
/// or with compilation parameters: |
| 134 | 124 |
/// \code |
| 135 | 125 |
/// g++ -DLEMON_DISABLE_ASSERTS |
| 136 | 126 |
/// make CXXFLAGS='-DLEMON_DISABLE_ASSERTS' |
| 137 | 127 |
/// \endcode |
| 138 | 128 |
/// The checking is also disabled when the standard macro \c NDEBUG is defined. |
| 139 | 129 |
/// |
| 140 |
/// The LEMON assertion system has a wide range of customization |
|
| 141 |
/// properties. As a default behaviour the failed assertion prints a |
|
| 142 |
/// short log message to |
|
| 130 |
/// As a default behaviour the failed assertion prints a short log message to |
|
| 131 |
/// the standard error and aborts the execution. |
|
| 143 | 132 |
/// |
| 144 |
/// The following modes can be used in the assertion system: |
|
| 145 |
/// |
|
| 146 |
/// - \c LEMON_ASSERT_LOG The failed assertion prints a short log |
|
| 147 |
/// message to the standard error and continues the execution. |
|
| 148 |
/// - \c LEMON_ASSERT_ABORT This mode is similar to the \c |
|
| 149 |
/// LEMON_ASSERT_LOG, but it aborts the program. It is the default |
|
| 150 |
/// |
|
| 133 |
/// However, the following modes can be used in the assertion system: |
|
| 134 |
/// - \c LEMON_ASSERT_ABORT The failed assertion prints a short log message to |
|
| 135 |
/// the standard error and aborts the program. It is the default behaviour. |
|
| 151 | 136 |
/// - \c LEMON_ASSERT_CUSTOM The user can define own assertion handler |
| 152 | 137 |
/// function. |
| 153 | 138 |
/// \code |
| 154 | 139 |
/// void custom_assert_handler(const char* file, int line, |
| 155 | 140 |
/// const char* function, const char* message, |
| 156 | 141 |
/// const char* assertion); |
| 157 | 142 |
/// \endcode |
| 158 | 143 |
/// The name of the function should be defined as the \c |
| 159 | 144 |
/// LEMON_CUSTOM_ASSERT_HANDLER macro name. |
| 160 | 145 |
/// \code |
| 161 | 146 |
/// #define LEMON_CUSTOM_ASSERT_HANDLER custom_assert_handler |
| 162 | 147 |
/// \endcode |
| 163 | 148 |
/// Whenever an assertion is occured, the custom assertion |
| 164 | 149 |
/// handler is called with appropiate parameters. |
| 165 | 150 |
/// |
| 166 | 151 |
/// The assertion mode can also be changed within one compilation unit. |
| 167 | 152 |
/// If the macros are redefined with other settings and the |
| 168 | 153 |
/// \ref lemon/assert.h "assert.h" file is reincluded, then the |
| 169 | 154 |
/// behaviour is changed appropiately to the new settings. |
| 170 | 155 |
# define LEMON_ASSERT(exp, msg) \ |
| 171 | 156 |
(static_cast<void> (!!(exp) ? 0 : ( \ |
| 172 | 157 |
LEMON_ASSERT_HANDLER(__FILE__, __LINE__, \ |
| 173 | 158 |
LEMON_FUNCTION_NAME, \ |
| 174 | 159 |
::lemon::_assert_bits::cstringify(msg), #exp), 0))) |
| 175 | 160 |
|
| 176 | 161 |
/// \ingroup exceptions |
| 177 | 162 |
/// |
| 178 |
/// \brief Macro for mark not yet implemented features. |
|
| 179 |
/// |
|
| 180 |
/// Macro for mark not yet implemented features and outstanding bugs. |
|
| 181 |
/// It is close to be the shortcut of the following code: |
|
| 182 |
/// \code |
|
| 183 |
/// LEMON_ASSERT(false, msg); |
|
| 184 |
/// \endcode |
|
| 185 |
/// |
|
| 186 |
/// \see LEMON_ASSERT |
|
| 187 |
# define LEMON_FIXME(msg) \ |
|
| 188 |
(LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME, \ |
|
| 189 |
::lemon::_assert_bits::cstringify(msg), \ |
|
| 190 |
static_cast<const char*>(0))) |
|
| 191 |
|
|
| 192 |
/// \ingroup exceptions |
|
| 193 |
/// |
|
| 194 | 163 |
/// \brief Macro for internal assertions |
| 195 | 164 |
/// |
| 196 | 165 |
/// Macro for internal assertions, it is used in the library to check |
| 197 | 166 |
/// the consistency of results of algorithms, several pre- and |
| 198 | 167 |
/// postconditions and invariants. The checking is disabled by |
| 199 | 168 |
/// default, but it can be turned on with the macro \c |
| 200 | 169 |
/// LEMON_ENABLE_DEBUG. |
| 201 | 170 |
/// \code |
| 202 | 171 |
/// #define LEMON_ENABLE_DEBUG |
| 203 | 172 |
/// \endcode |
| 204 | 173 |
/// or with compilation parameters: |
| 205 | 174 |
/// \code |
| 206 | 175 |
/// g++ -DLEMON_ENABLE_DEBUG |
| 207 | 176 |
/// make CXXFLAGS='-DLEMON_ENABLE_DEBUG' |
| 208 | 177 |
/// \endcode |
| 209 | 178 |
/// |
| 210 | 179 |
/// This macro works like the \c LEMON_ASSERT macro, therefore the |
| 211 | 180 |
/// current behaviour depends on the settings of \c LEMON_ASSERT |
| 212 | 181 |
/// macro. |
| 213 | 182 |
/// |
| 214 | 183 |
/// \see LEMON_ASSERT |
| 215 | 184 |
# define LEMON_DEBUG(exp, msg) \ |
| 216 | 185 |
(static_cast<void> (!!(exp) ? 0 : ( \ |
| 217 | 186 |
LEMON_ASSERT_HANDLER(__FILE__, __LINE__, \ |
| 218 | 187 |
LEMON_FUNCTION_NAME, \ |
| 219 | 188 |
::lemon::_assert_bits::cstringify(msg), #exp), 0))) |
| 220 | 189 |
|
| 221 | 190 |
#else |
| 222 | 191 |
|
| 223 | 192 |
# ifndef LEMON_ASSERT_HANDLER |
| 224 | 193 |
# define LEMON_ASSERT(exp, msg) (static_cast<void>(0)) |
| 225 |
# define LEMON_FIXME(msg) (static_cast<void>(0)) |
|
| 226 | 194 |
# define LEMON_DEBUG(exp, msg) (static_cast<void>(0)) |
| 227 | 195 |
# else |
| 228 | 196 |
# define LEMON_ASSERT(exp, msg) \ |
| 229 | 197 |
(static_cast<void> (!!(exp) ? 0 : ( \ |
| 230 | 198 |
LEMON_ASSERT_HANDLER(__FILE__, __LINE__, \ |
| 231 | 199 |
LEMON_FUNCTION_NAME, \ |
| 232 | 200 |
::lemon::_assert_bits::cstringify(msg), \ |
| 233 | 201 |
#exp), 0))) |
| 234 |
# define LEMON_FIXME(msg) \ |
|
| 235 |
(LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME, \ |
|
| 236 |
::lemon::_assert_bits::cstringify(msg), \ |
|
| 237 |
static_cast<const char*>(0))) |
|
| 238 |
|
|
| 239 | 202 |
# if LEMON_ENABLE_DEBUG |
| 240 | 203 |
# define LEMON_DEBUG(exp, msg) \ |
| 241 | 204 |
(static_cast<void> (!!(exp) ? 0 : ( \ |
| 242 | 205 |
LEMON_ASSERT_HANDLER(__FILE__, __LINE__, \ |
| 243 | 206 |
LEMON_FUNCTION_NAME, \ |
| 244 | 207 |
::lemon::_assert_bits::cstringify(msg), \ |
| 245 | 208 |
#exp), 0))) |
| 246 | 209 |
# else |
| 247 | 210 |
# define LEMON_DEBUG(exp, msg) (static_cast<void>(0)) |
| 248 | 211 |
# endif |
| 249 | 212 |
# endif |
| 250 | 213 |
|
| 251 | 214 |
#endif |
| ... | ... |
@@ -10,239 +10,241 @@ |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
#ifndef LEMON_BITS_ARRAY_MAP_H |
| 20 | 20 |
#define LEMON_BITS_ARRAY_MAP_H |
| 21 | 21 |
|
| 22 | 22 |
#include <memory> |
| 23 | 23 |
|
| 24 | 24 |
#include <lemon/bits/traits.h> |
| 25 | 25 |
#include <lemon/bits/alteration_notifier.h> |
| 26 | 26 |
#include <lemon/concept_check.h> |
| 27 | 27 |
#include <lemon/concepts/maps.h> |
| 28 | 28 |
|
| 29 | 29 |
/// \ingroup graphbits |
| 30 | 30 |
/// \file |
| 31 | 31 |
/// \brief Graph map based on the array storage. |
| 32 | 32 |
|
| 33 | 33 |
namespace lemon {
|
| 34 | 34 |
|
| 35 | 35 |
/// \ingroup graphbits |
| 36 | 36 |
/// |
| 37 | 37 |
/// \brief Graph map based on the array storage. |
| 38 | 38 |
/// |
| 39 | 39 |
/// The ArrayMap template class is graph map structure what |
| 40 | 40 |
/// automatically updates the map when a key is added to or erased from |
| 41 | 41 |
/// the map. This map uses the allocators to implement |
| 42 | 42 |
/// the container functionality. |
| 43 | 43 |
/// |
| 44 | 44 |
/// The template parameters are the Graph the current Item type and |
| 45 | 45 |
/// the Value type of the map. |
| 46 | 46 |
template <typename _Graph, typename _Item, typename _Value> |
| 47 | 47 |
class ArrayMap |
| 48 | 48 |
: public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
|
| 49 | 49 |
public: |
| 50 | 50 |
/// The graph type of the maps. |
| 51 | 51 |
typedef _Graph Graph; |
| 52 | 52 |
/// The item type of the map. |
| 53 | 53 |
typedef _Item Item; |
| 54 | 54 |
/// The reference map tag. |
| 55 | 55 |
typedef True ReferenceMapTag; |
| 56 | 56 |
|
| 57 | 57 |
/// The key type of the maps. |
| 58 | 58 |
typedef _Item Key; |
| 59 | 59 |
/// The value type of the map. |
| 60 | 60 |
typedef _Value Value; |
| 61 | 61 |
|
| 62 | 62 |
/// The const reference type of the map. |
| 63 | 63 |
typedef const _Value& ConstReference; |
| 64 | 64 |
/// The reference type of the map. |
| 65 | 65 |
typedef _Value& Reference; |
| 66 | 66 |
|
| 67 | 67 |
/// The notifier type. |
| 68 | 68 |
typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier; |
| 69 | 69 |
|
| 70 | 70 |
/// The MapBase of the Map which imlements the core regisitry function. |
| 71 | 71 |
typedef typename Notifier::ObserverBase Parent; |
| 72 | 72 |
|
| 73 | 73 |
private: |
| 74 | 74 |
typedef std::allocator<Value> Allocator; |
| 75 | 75 |
|
| 76 | 76 |
public: |
| 77 | 77 |
|
| 78 | 78 |
/// \brief Graph initialized map constructor. |
| 79 | 79 |
/// |
| 80 | 80 |
/// Graph initialized map constructor. |
| 81 | 81 |
explicit ArrayMap(const Graph& graph) {
|
| 82 | 82 |
Parent::attach(graph.notifier(Item())); |
| 83 | 83 |
allocate_memory(); |
| 84 | 84 |
Notifier* nf = Parent::notifier(); |
| 85 | 85 |
Item it; |
| 86 | 86 |
for (nf->first(it); it != INVALID; nf->next(it)) {
|
| 87 | 87 |
int id = nf->id(it);; |
| 88 | 88 |
allocator.construct(&(values[id]), Value()); |
| 89 | 89 |
} |
| 90 | 90 |
} |
| 91 | 91 |
|
| 92 | 92 |
/// \brief Constructor to use default value to initialize the map. |
| 93 | 93 |
/// |
| 94 | 94 |
/// It constructs a map and initialize all of the the map. |
| 95 | 95 |
ArrayMap(const Graph& graph, const Value& value) {
|
| 96 | 96 |
Parent::attach(graph.notifier(Item())); |
| 97 | 97 |
allocate_memory(); |
| 98 | 98 |
Notifier* nf = Parent::notifier(); |
| 99 | 99 |
Item it; |
| 100 | 100 |
for (nf->first(it); it != INVALID; nf->next(it)) {
|
| 101 | 101 |
int id = nf->id(it);; |
| 102 | 102 |
allocator.construct(&(values[id]), value); |
| 103 | 103 |
} |
| 104 | 104 |
} |
| 105 | 105 |
|
| 106 |
private: |
|
| 106 | 107 |
/// \brief Constructor to copy a map of the same map type. |
| 107 | 108 |
/// |
| 108 | 109 |
/// Constructor to copy a map of the same map type. |
| 109 | 110 |
ArrayMap(const ArrayMap& copy) : Parent() {
|
| 110 | 111 |
if (copy.attached()) {
|
| 111 | 112 |
attach(*copy.notifier()); |
| 112 | 113 |
} |
| 113 | 114 |
capacity = copy.capacity; |
| 114 | 115 |
if (capacity == 0) return; |
| 115 | 116 |
values = allocator.allocate(capacity); |
| 116 | 117 |
Notifier* nf = Parent::notifier(); |
| 117 | 118 |
Item it; |
| 118 | 119 |
for (nf->first(it); it != INVALID; nf->next(it)) {
|
| 119 | 120 |
int id = nf->id(it);; |
| 120 | 121 |
allocator.construct(&(values[id]), copy.values[id]); |
| 121 | 122 |
} |
| 122 | 123 |
} |
| 123 | 124 |
|
| 124 | 125 |
/// \brief Assign operator. |
| 125 | 126 |
/// |
| 126 | 127 |
/// This operator assigns for each item in the map the |
| 127 | 128 |
/// value mapped to the same item in the copied map. |
| 128 | 129 |
/// The parameter map should be indiced with the same |
| 129 | 130 |
/// itemset because this assign operator does not change |
| 130 | 131 |
/// the container of the map. |
| 131 | 132 |
ArrayMap& operator=(const ArrayMap& cmap) {
|
| 132 | 133 |
return operator=<ArrayMap>(cmap); |
| 133 | 134 |
} |
| 134 | 135 |
|
| 135 | 136 |
|
| 136 | 137 |
/// \brief Template assign operator. |
| 137 | 138 |
/// |
| 138 | 139 |
/// The given parameter should be conform to the ReadMap |
| 139 | 140 |
/// concecpt and could be indiced by the current item set of |
| 140 | 141 |
/// the NodeMap. In this case the value for each item |
| 141 | 142 |
/// is assigned by the value of the given ReadMap. |
| 142 | 143 |
template <typename CMap> |
| 143 | 144 |
ArrayMap& operator=(const CMap& cmap) {
|
| 144 | 145 |
checkConcept<concepts::ReadMap<Key, _Value>, CMap>(); |
| 145 | 146 |
const typename Parent::Notifier* nf = Parent::notifier(); |
| 146 | 147 |
Item it; |
| 147 | 148 |
for (nf->first(it); it != INVALID; nf->next(it)) {
|
| 148 | 149 |
set(it, cmap[it]); |
| 149 | 150 |
} |
| 150 | 151 |
return *this; |
| 151 | 152 |
} |
| 152 | 153 |
|
| 154 |
public: |
|
| 153 | 155 |
/// \brief The destructor of the map. |
| 154 | 156 |
/// |
| 155 | 157 |
/// The destructor of the map. |
| 156 | 158 |
virtual ~ArrayMap() {
|
| 157 | 159 |
if (attached()) {
|
| 158 | 160 |
clear(); |
| 159 | 161 |
detach(); |
| 160 | 162 |
} |
| 161 | 163 |
} |
| 162 | 164 |
|
| 163 | 165 |
protected: |
| 164 | 166 |
|
| 165 | 167 |
using Parent::attach; |
| 166 | 168 |
using Parent::detach; |
| 167 | 169 |
using Parent::attached; |
| 168 | 170 |
|
| 169 | 171 |
public: |
| 170 | 172 |
|
| 171 | 173 |
/// \brief The subscript operator. |
| 172 | 174 |
/// |
| 173 | 175 |
/// The subscript operator. The map can be subscripted by the |
| 174 | 176 |
/// actual keys of the graph. |
| 175 | 177 |
Value& operator[](const Key& key) {
|
| 176 | 178 |
int id = Parent::notifier()->id(key); |
| 177 | 179 |
return values[id]; |
| 178 | 180 |
} |
| 179 | 181 |
|
| 180 | 182 |
/// \brief The const subscript operator. |
| 181 | 183 |
/// |
| 182 | 184 |
/// The const subscript operator. The map can be subscripted by the |
| 183 | 185 |
/// actual keys of the graph. |
| 184 | 186 |
const Value& operator[](const Key& key) const {
|
| 185 | 187 |
int id = Parent::notifier()->id(key); |
| 186 | 188 |
return values[id]; |
| 187 | 189 |
} |
| 188 | 190 |
|
| 189 | 191 |
/// \brief Setter function of the map. |
| 190 | 192 |
/// |
| 191 | 193 |
/// Setter function of the map. Equivalent with map[key] = val. |
| 192 | 194 |
/// This is a compatibility feature with the not dereferable maps. |
| 193 | 195 |
void set(const Key& key, const Value& val) {
|
| 194 | 196 |
(*this)[key] = val; |
| 195 | 197 |
} |
| 196 | 198 |
|
| 197 | 199 |
protected: |
| 198 | 200 |
|
| 199 | 201 |
/// \brief Adds a new key to the map. |
| 200 | 202 |
/// |
| 201 | 203 |
/// It adds a new key to the map. It called by the observer notifier |
| 202 | 204 |
/// and it overrides the add() member function of the observer base. |
| 203 | 205 |
virtual void add(const Key& key) {
|
| 204 | 206 |
Notifier* nf = Parent::notifier(); |
| 205 | 207 |
int id = nf->id(key); |
| 206 | 208 |
if (id >= capacity) {
|
| 207 | 209 |
int new_capacity = (capacity == 0 ? 1 : capacity); |
| 208 | 210 |
while (new_capacity <= id) {
|
| 209 | 211 |
new_capacity <<= 1; |
| 210 | 212 |
} |
| 211 | 213 |
Value* new_values = allocator.allocate(new_capacity); |
| 212 | 214 |
Item it; |
| 213 | 215 |
for (nf->first(it); it != INVALID; nf->next(it)) {
|
| 214 | 216 |
int jd = nf->id(it);; |
| 215 | 217 |
if (id != jd) {
|
| 216 | 218 |
allocator.construct(&(new_values[jd]), values[jd]); |
| 217 | 219 |
allocator.destroy(&(values[jd])); |
| 218 | 220 |
} |
| 219 | 221 |
} |
| 220 | 222 |
if (capacity != 0) allocator.deallocate(values, capacity); |
| 221 | 223 |
values = new_values; |
| 222 | 224 |
capacity = new_capacity; |
| 223 | 225 |
} |
| 224 | 226 |
allocator.construct(&(values[id]), Value()); |
| 225 | 227 |
} |
| 226 | 228 |
|
| 227 | 229 |
/// \brief Adds more new keys to the map. |
| 228 | 230 |
/// |
| 229 | 231 |
/// It adds more new keys to the map. It called by the observer notifier |
| 230 | 232 |
/// and it overrides the add() member function of the observer base. |
| 231 | 233 |
virtual void add(const std::vector<Key>& keys) {
|
| 232 | 234 |
Notifier* nf = Parent::notifier(); |
| 233 | 235 |
int max_id = -1; |
| 234 | 236 |
for (int i = 0; i < int(keys.size()); ++i) {
|
| 235 | 237 |
int id = nf->id(keys[i]); |
| 236 | 238 |
if (id > max_id) {
|
| 237 | 239 |
max_id = id; |
| 238 | 240 |
} |
| 239 | 241 |
} |
| 240 | 242 |
if (max_id >= capacity) {
|
| 241 | 243 |
int new_capacity = (capacity == 0 ? 1 : capacity); |
| 242 | 244 |
while (new_capacity <= max_id) {
|
| 243 | 245 |
new_capacity <<= 1; |
| 244 | 246 |
} |
| 245 | 247 |
Value* new_values = allocator.allocate(new_capacity); |
| 246 | 248 |
Item it; |
| 247 | 249 |
for (nf->first(it); it != INVALID; nf->next(it)) {
|
| 248 | 250 |
int id = nf->id(it); |
| ... | ... |
@@ -134,216 +134,218 @@ |
| 134 | 134 |
ArcIt& operator++() {
|
| 135 | 135 |
_digraph->next(*this); |
| 136 | 136 |
return *this; |
| 137 | 137 |
} |
| 138 | 138 |
|
| 139 | 139 |
}; |
| 140 | 140 |
|
| 141 | 141 |
|
| 142 | 142 |
class OutArcIt : public Arc {
|
| 143 | 143 |
const Digraph* _digraph; |
| 144 | 144 |
public: |
| 145 | 145 |
|
| 146 | 146 |
OutArcIt() { }
|
| 147 | 147 |
|
| 148 | 148 |
OutArcIt(Invalid i) : Arc(i) { }
|
| 149 | 149 |
|
| 150 | 150 |
OutArcIt(const Digraph& digraph, const Node& node) |
| 151 | 151 |
: _digraph(&digraph) {
|
| 152 | 152 |
_digraph->firstOut(*this, node); |
| 153 | 153 |
} |
| 154 | 154 |
|
| 155 | 155 |
OutArcIt(const Digraph& digraph, const Arc& arc) |
| 156 | 156 |
: Arc(arc), _digraph(&digraph) {}
|
| 157 | 157 |
|
| 158 | 158 |
OutArcIt& operator++() {
|
| 159 | 159 |
_digraph->nextOut(*this); |
| 160 | 160 |
return *this; |
| 161 | 161 |
} |
| 162 | 162 |
|
| 163 | 163 |
}; |
| 164 | 164 |
|
| 165 | 165 |
|
| 166 | 166 |
class InArcIt : public Arc {
|
| 167 | 167 |
const Digraph* _digraph; |
| 168 | 168 |
public: |
| 169 | 169 |
|
| 170 | 170 |
InArcIt() { }
|
| 171 | 171 |
|
| 172 | 172 |
InArcIt(Invalid i) : Arc(i) { }
|
| 173 | 173 |
|
| 174 | 174 |
InArcIt(const Digraph& digraph, const Node& node) |
| 175 | 175 |
: _digraph(&digraph) {
|
| 176 | 176 |
_digraph->firstIn(*this, node); |
| 177 | 177 |
} |
| 178 | 178 |
|
| 179 | 179 |
InArcIt(const Digraph& digraph, const Arc& arc) : |
| 180 | 180 |
Arc(arc), _digraph(&digraph) {}
|
| 181 | 181 |
|
| 182 | 182 |
InArcIt& operator++() {
|
| 183 | 183 |
_digraph->nextIn(*this); |
| 184 | 184 |
return *this; |
| 185 | 185 |
} |
| 186 | 186 |
|
| 187 | 187 |
}; |
| 188 | 188 |
|
| 189 | 189 |
/// \brief Base node of the iterator |
| 190 | 190 |
/// |
| 191 | 191 |
/// Returns the base node (i.e. the source in this case) of the iterator |
| 192 | 192 |
Node baseNode(const OutArcIt &arc) const {
|
| 193 | 193 |
return Parent::source(arc); |
| 194 | 194 |
} |
| 195 | 195 |
/// \brief Running node of the iterator |
| 196 | 196 |
/// |
| 197 | 197 |
/// Returns the running node (i.e. the target in this case) of the |
| 198 | 198 |
/// iterator |
| 199 | 199 |
Node runningNode(const OutArcIt &arc) const {
|
| 200 | 200 |
return Parent::target(arc); |
| 201 | 201 |
} |
| 202 | 202 |
|
| 203 | 203 |
/// \brief Base node of the iterator |
| 204 | 204 |
/// |
| 205 | 205 |
/// Returns the base node (i.e. the target in this case) of the iterator |
| 206 | 206 |
Node baseNode(const InArcIt &arc) const {
|
| 207 | 207 |
return Parent::target(arc); |
| 208 | 208 |
} |
| 209 | 209 |
/// \brief Running node of the iterator |
| 210 | 210 |
/// |
| 211 | 211 |
/// Returns the running node (i.e. the source in this case) of the |
| 212 | 212 |
/// iterator |
| 213 | 213 |
Node runningNode(const InArcIt &arc) const {
|
| 214 | 214 |
return Parent::source(arc); |
| 215 | 215 |
} |
| 216 | 216 |
|
| 217 | 217 |
|
| 218 | 218 |
template <typename _Value> |
| 219 | 219 |
class NodeMap |
| 220 | 220 |
: public MapExtender<DefaultMap<Digraph, Node, _Value> > {
|
| 221 | 221 |
public: |
| 222 | 222 |
typedef DigraphExtender Digraph; |
| 223 | 223 |
typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent; |
| 224 | 224 |
|
| 225 | 225 |
explicit NodeMap(const Digraph& digraph) |
| 226 | 226 |
: Parent(digraph) {}
|
| 227 | 227 |
NodeMap(const Digraph& digraph, const _Value& value) |
| 228 | 228 |
: Parent(digraph, value) {}
|
| 229 | 229 |
|
| 230 |
private: |
|
| 230 | 231 |
NodeMap& operator=(const NodeMap& cmap) {
|
| 231 | 232 |
return operator=<NodeMap>(cmap); |
| 232 | 233 |
} |
| 233 | 234 |
|
| 234 | 235 |
template <typename CMap> |
| 235 | 236 |
NodeMap& operator=(const CMap& cmap) {
|
| 236 | 237 |
Parent::operator=(cmap); |
| 237 | 238 |
return *this; |
| 238 | 239 |
} |
| 239 | 240 |
|
| 240 | 241 |
}; |
| 241 | 242 |
|
| 242 | 243 |
template <typename _Value> |
| 243 | 244 |
class ArcMap |
| 244 | 245 |
: public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
|
| 245 | 246 |
public: |
| 246 | 247 |
typedef DigraphExtender Digraph; |
| 247 | 248 |
typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent; |
| 248 | 249 |
|
| 249 | 250 |
explicit ArcMap(const Digraph& digraph) |
| 250 | 251 |
: Parent(digraph) {}
|
| 251 | 252 |
ArcMap(const Digraph& digraph, const _Value& value) |
| 252 | 253 |
: Parent(digraph, value) {}
|
| 253 | 254 |
|
| 255 |
private: |
|
| 254 | 256 |
ArcMap& operator=(const ArcMap& cmap) {
|
| 255 | 257 |
return operator=<ArcMap>(cmap); |
| 256 | 258 |
} |
| 257 | 259 |
|
| 258 | 260 |
template <typename CMap> |
| 259 | 261 |
ArcMap& operator=(const CMap& cmap) {
|
| 260 | 262 |
Parent::operator=(cmap); |
| 261 | 263 |
return *this; |
| 262 | 264 |
} |
| 263 | 265 |
}; |
| 264 | 266 |
|
| 265 | 267 |
|
| 266 | 268 |
Node addNode() {
|
| 267 | 269 |
Node node = Parent::addNode(); |
| 268 | 270 |
notifier(Node()).add(node); |
| 269 | 271 |
return node; |
| 270 | 272 |
} |
| 271 | 273 |
|
| 272 | 274 |
Arc addArc(const Node& from, const Node& to) {
|
| 273 | 275 |
Arc arc = Parent::addArc(from, to); |
| 274 | 276 |
notifier(Arc()).add(arc); |
| 275 | 277 |
return arc; |
| 276 | 278 |
} |
| 277 | 279 |
|
| 278 | 280 |
void clear() {
|
| 279 | 281 |
notifier(Arc()).clear(); |
| 280 | 282 |
notifier(Node()).clear(); |
| 281 | 283 |
Parent::clear(); |
| 282 | 284 |
} |
| 283 | 285 |
|
| 284 | 286 |
template <typename Digraph, typename NodeRefMap, typename ArcRefMap> |
| 285 | 287 |
void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
|
| 286 | 288 |
Parent::build(digraph, nodeRef, arcRef); |
| 287 | 289 |
notifier(Node()).build(); |
| 288 | 290 |
notifier(Arc()).build(); |
| 289 | 291 |
} |
| 290 | 292 |
|
| 291 | 293 |
void erase(const Node& node) {
|
| 292 | 294 |
Arc arc; |
| 293 | 295 |
Parent::firstOut(arc, node); |
| 294 | 296 |
while (arc != INVALID ) {
|
| 295 | 297 |
erase(arc); |
| 296 | 298 |
Parent::firstOut(arc, node); |
| 297 | 299 |
} |
| 298 | 300 |
|
| 299 | 301 |
Parent::firstIn(arc, node); |
| 300 | 302 |
while (arc != INVALID ) {
|
| 301 | 303 |
erase(arc); |
| 302 | 304 |
Parent::firstIn(arc, node); |
| 303 | 305 |
} |
| 304 | 306 |
|
| 305 | 307 |
notifier(Node()).erase(node); |
| 306 | 308 |
Parent::erase(node); |
| 307 | 309 |
} |
| 308 | 310 |
|
| 309 | 311 |
void erase(const Arc& arc) {
|
| 310 | 312 |
notifier(Arc()).erase(arc); |
| 311 | 313 |
Parent::erase(arc); |
| 312 | 314 |
} |
| 313 | 315 |
|
| 314 | 316 |
DigraphExtender() {
|
| 315 | 317 |
node_notifier.setContainer(*this); |
| 316 | 318 |
arc_notifier.setContainer(*this); |
| 317 | 319 |
} |
| 318 | 320 |
|
| 319 | 321 |
|
| 320 | 322 |
~DigraphExtender() {
|
| 321 | 323 |
arc_notifier.clear(); |
| 322 | 324 |
node_notifier.clear(); |
| 323 | 325 |
} |
| 324 | 326 |
}; |
| 325 | 327 |
|
| 326 | 328 |
/// \ingroup _graphbits |
| 327 | 329 |
/// |
| 328 | 330 |
/// \brief Extender for the Graphs |
| 329 | 331 |
template <typename Base> |
| 330 | 332 |
class GraphExtender : public Base {
|
| 331 | 333 |
public: |
| 332 | 334 |
|
| 333 | 335 |
typedef Base Parent; |
| 334 | 336 |
typedef GraphExtender Graph; |
| 335 | 337 |
|
| 336 | 338 |
typedef True UndirectedTag; |
| 337 | 339 |
|
| 338 | 340 |
typedef typename Parent::Node Node; |
| 339 | 341 |
typedef typename Parent::Arc Arc; |
| 340 | 342 |
typedef typename Parent::Edge Edge; |
| 341 | 343 |
|
| 342 | 344 |
// Graph extension |
| 343 | 345 |
|
| 344 | 346 |
int maxId(Node) const {
|
| 345 | 347 |
return Parent::maxNodeId(); |
| 346 | 348 |
} |
| 347 | 349 |
|
| 348 | 350 |
int maxId(Arc) const {
|
| 349 | 351 |
return Parent::maxArcId(); |
| ... | ... |
@@ -515,235 +517,238 @@ |
| 515 | 517 |
EdgeIt(Invalid i) : Edge(i) { }
|
| 516 | 518 |
|
| 517 | 519 |
explicit EdgeIt(const Graph& graph) : _graph(&graph) {
|
| 518 | 520 |
_graph->first(static_cast<Edge&>(*this)); |
| 519 | 521 |
} |
| 520 | 522 |
|
| 521 | 523 |
EdgeIt(const Graph& graph, const Edge& edge) : |
| 522 | 524 |
Edge(edge), _graph(&graph) { }
|
| 523 | 525 |
|
| 524 | 526 |
EdgeIt& operator++() {
|
| 525 | 527 |
_graph->next(*this); |
| 526 | 528 |
return *this; |
| 527 | 529 |
} |
| 528 | 530 |
|
| 529 | 531 |
}; |
| 530 | 532 |
|
| 531 | 533 |
class IncEdgeIt : public Parent::Edge {
|
| 532 | 534 |
friend class GraphExtender; |
| 533 | 535 |
const Graph* _graph; |
| 534 | 536 |
bool _direction; |
| 535 | 537 |
public: |
| 536 | 538 |
|
| 537 | 539 |
IncEdgeIt() { }
|
| 538 | 540 |
|
| 539 | 541 |
IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
|
| 540 | 542 |
|
| 541 | 543 |
IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
|
| 542 | 544 |
_graph->firstInc(*this, _direction, node); |
| 543 | 545 |
} |
| 544 | 546 |
|
| 545 | 547 |
IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node) |
| 546 | 548 |
: _graph(&graph), Edge(edge) {
|
| 547 | 549 |
_direction = (_graph->source(edge) == node); |
| 548 | 550 |
} |
| 549 | 551 |
|
| 550 | 552 |
IncEdgeIt& operator++() {
|
| 551 | 553 |
_graph->nextInc(*this, _direction); |
| 552 | 554 |
return *this; |
| 553 | 555 |
} |
| 554 | 556 |
}; |
| 555 | 557 |
|
| 556 | 558 |
/// \brief Base node of the iterator |
| 557 | 559 |
/// |
| 558 | 560 |
/// Returns the base node (ie. the source in this case) of the iterator |
| 559 | 561 |
Node baseNode(const OutArcIt &arc) const {
|
| 560 | 562 |
return Parent::source(static_cast<const Arc&>(arc)); |
| 561 | 563 |
} |
| 562 | 564 |
/// \brief Running node of the iterator |
| 563 | 565 |
/// |
| 564 | 566 |
/// Returns the running node (ie. the target in this case) of the |
| 565 | 567 |
/// iterator |
| 566 | 568 |
Node runningNode(const OutArcIt &arc) const {
|
| 567 | 569 |
return Parent::target(static_cast<const Arc&>(arc)); |
| 568 | 570 |
} |
| 569 | 571 |
|
| 570 | 572 |
/// \brief Base node of the iterator |
| 571 | 573 |
/// |
| 572 | 574 |
/// Returns the base node (ie. the target in this case) of the iterator |
| 573 | 575 |
Node baseNode(const InArcIt &arc) const {
|
| 574 | 576 |
return Parent::target(static_cast<const Arc&>(arc)); |
| 575 | 577 |
} |
| 576 | 578 |
/// \brief Running node of the iterator |
| 577 | 579 |
/// |
| 578 | 580 |
/// Returns the running node (ie. the source in this case) of the |
| 579 | 581 |
/// iterator |
| 580 | 582 |
Node runningNode(const InArcIt &arc) const {
|
| 581 | 583 |
return Parent::source(static_cast<const Arc&>(arc)); |
| 582 | 584 |
} |
| 583 | 585 |
|
| 584 | 586 |
/// Base node of the iterator |
| 585 | 587 |
/// |
| 586 | 588 |
/// Returns the base node of the iterator |
| 587 | 589 |
Node baseNode(const IncEdgeIt &edge) const {
|
| 588 | 590 |
return edge._direction ? u(edge) : v(edge); |
| 589 | 591 |
} |
| 590 | 592 |
/// Running node of the iterator |
| 591 | 593 |
/// |
| 592 | 594 |
/// Returns the running node of the iterator |
| 593 | 595 |
Node runningNode(const IncEdgeIt &edge) const {
|
| 594 | 596 |
return edge._direction ? v(edge) : u(edge); |
| 595 | 597 |
} |
| 596 | 598 |
|
| 597 | 599 |
// Mappable extension |
| 598 | 600 |
|
| 599 | 601 |
template <typename _Value> |
| 600 | 602 |
class NodeMap |
| 601 | 603 |
: public MapExtender<DefaultMap<Graph, Node, _Value> > {
|
| 602 | 604 |
public: |
| 603 | 605 |
typedef GraphExtender Graph; |
| 604 | 606 |
typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent; |
| 605 | 607 |
|
| 606 | 608 |
NodeMap(const Graph& graph) |
| 607 | 609 |
: Parent(graph) {}
|
| 608 | 610 |
NodeMap(const Graph& graph, const _Value& value) |
| 609 | 611 |
: Parent(graph, value) {}
|
| 610 | 612 |
|
| 613 |
private: |
|
| 611 | 614 |
NodeMap& operator=(const NodeMap& cmap) {
|
| 612 | 615 |
return operator=<NodeMap>(cmap); |
| 613 | 616 |
} |
| 614 | 617 |
|
| 615 | 618 |
template <typename CMap> |
| 616 | 619 |
NodeMap& operator=(const CMap& cmap) {
|
| 617 | 620 |
Parent::operator=(cmap); |
| 618 | 621 |
return *this; |
| 619 | 622 |
} |
| 620 | 623 |
|
| 621 | 624 |
}; |
| 622 | 625 |
|
| 623 | 626 |
template <typename _Value> |
| 624 | 627 |
class ArcMap |
| 625 | 628 |
: public MapExtender<DefaultMap<Graph, Arc, _Value> > {
|
| 626 | 629 |
public: |
| 627 | 630 |
typedef GraphExtender Graph; |
| 628 | 631 |
typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent; |
| 629 | 632 |
|
| 630 | 633 |
ArcMap(const Graph& graph) |
| 631 | 634 |
: Parent(graph) {}
|
| 632 | 635 |
ArcMap(const Graph& graph, const _Value& value) |
| 633 | 636 |
: Parent(graph, value) {}
|
| 634 | 637 |
|
| 638 |
private: |
|
| 635 | 639 |
ArcMap& operator=(const ArcMap& cmap) {
|
| 636 | 640 |
return operator=<ArcMap>(cmap); |
| 637 | 641 |
} |
| 638 | 642 |
|
| 639 | 643 |
template <typename CMap> |
| 640 | 644 |
ArcMap& operator=(const CMap& cmap) {
|
| 641 | 645 |
Parent::operator=(cmap); |
| 642 | 646 |
return *this; |
| 643 | 647 |
} |
| 644 | 648 |
}; |
| 645 | 649 |
|
| 646 | 650 |
|
| 647 | 651 |
template <typename _Value> |
| 648 | 652 |
class EdgeMap |
| 649 | 653 |
: public MapExtender<DefaultMap<Graph, Edge, _Value> > {
|
| 650 | 654 |
public: |
| 651 | 655 |
typedef GraphExtender Graph; |
| 652 | 656 |
typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; |
| 653 | 657 |
|
| 654 | 658 |
EdgeMap(const Graph& graph) |
| 655 | 659 |
: Parent(graph) {}
|
| 656 | 660 |
|
| 657 | 661 |
EdgeMap(const Graph& graph, const _Value& value) |
| 658 | 662 |
: Parent(graph, value) {}
|
| 659 | 663 |
|
| 664 |
private: |
|
| 660 | 665 |
EdgeMap& operator=(const EdgeMap& cmap) {
|
| 661 | 666 |
return operator=<EdgeMap>(cmap); |
| 662 | 667 |
} |
| 663 | 668 |
|
| 664 | 669 |
template <typename CMap> |
| 665 | 670 |
EdgeMap& operator=(const CMap& cmap) {
|
| 666 | 671 |
Parent::operator=(cmap); |
| 667 | 672 |
return *this; |
| 668 | 673 |
} |
| 669 | 674 |
|
| 670 | 675 |
}; |
| 671 | 676 |
|
| 672 | 677 |
// Alteration extension |
| 673 | 678 |
|
| 674 | 679 |
Node addNode() {
|
| 675 | 680 |
Node node = Parent::addNode(); |
| 676 | 681 |
notifier(Node()).add(node); |
| 677 | 682 |
return node; |
| 678 | 683 |
} |
| 679 | 684 |
|
| 680 | 685 |
Edge addEdge(const Node& from, const Node& to) {
|
| 681 | 686 |
Edge edge = Parent::addEdge(from, to); |
| 682 | 687 |
notifier(Edge()).add(edge); |
| 683 | 688 |
std::vector<Arc> ev; |
| 684 | 689 |
ev.push_back(Parent::direct(edge, true)); |
| 685 | 690 |
ev.push_back(Parent::direct(edge, false)); |
| 686 | 691 |
notifier(Arc()).add(ev); |
| 687 | 692 |
return edge; |
| 688 | 693 |
} |
| 689 | 694 |
|
| 690 | 695 |
void clear() {
|
| 691 | 696 |
notifier(Arc()).clear(); |
| 692 | 697 |
notifier(Edge()).clear(); |
| 693 | 698 |
notifier(Node()).clear(); |
| 694 | 699 |
Parent::clear(); |
| 695 | 700 |
} |
| 696 | 701 |
|
| 697 | 702 |
template <typename Graph, typename NodeRefMap, typename EdgeRefMap> |
| 698 | 703 |
void build(const Graph& graph, NodeRefMap& nodeRef, |
| 699 | 704 |
EdgeRefMap& edgeRef) {
|
| 700 | 705 |
Parent::build(graph, nodeRef, edgeRef); |
| 701 | 706 |
notifier(Node()).build(); |
| 702 | 707 |
notifier(Edge()).build(); |
| 703 | 708 |
notifier(Arc()).build(); |
| 704 | 709 |
} |
| 705 | 710 |
|
| 706 | 711 |
void erase(const Node& node) {
|
| 707 | 712 |
Arc arc; |
| 708 | 713 |
Parent::firstOut(arc, node); |
| 709 | 714 |
while (arc != INVALID ) {
|
| 710 | 715 |
erase(arc); |
| 711 | 716 |
Parent::firstOut(arc, node); |
| 712 | 717 |
} |
| 713 | 718 |
|
| 714 | 719 |
Parent::firstIn(arc, node); |
| 715 | 720 |
while (arc != INVALID ) {
|
| 716 | 721 |
erase(arc); |
| 717 | 722 |
Parent::firstIn(arc, node); |
| 718 | 723 |
} |
| 719 | 724 |
|
| 720 | 725 |
notifier(Node()).erase(node); |
| 721 | 726 |
Parent::erase(node); |
| 722 | 727 |
} |
| 723 | 728 |
|
| 724 | 729 |
void erase(const Edge& edge) {
|
| 725 | 730 |
std::vector<Arc> av; |
| 726 | 731 |
av.push_back(Parent::direct(edge, true)); |
| 727 | 732 |
av.push_back(Parent::direct(edge, false)); |
| 728 | 733 |
notifier(Arc()).erase(av); |
| 729 | 734 |
notifier(Edge()).erase(edge); |
| 730 | 735 |
Parent::erase(edge); |
| 731 | 736 |
} |
| 732 | 737 |
|
| 733 | 738 |
GraphExtender() {
|
| 734 | 739 |
node_notifier.setContainer(*this); |
| 735 | 740 |
arc_notifier.setContainer(*this); |
| 736 | 741 |
edge_notifier.setContainer(*this); |
| 737 | 742 |
} |
| 738 | 743 |
|
| 739 | 744 |
~GraphExtender() {
|
| 740 | 745 |
edge_notifier.clear(); |
| 741 | 746 |
arc_notifier.clear(); |
| 742 | 747 |
node_notifier.clear(); |
| 743 | 748 |
} |
| 744 | 749 |
|
| 745 | 750 |
}; |
| 746 | 751 |
|
| 747 | 752 |
} |
| 748 | 753 |
|
| 749 | 754 |
#endif |
| 1 | 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
| 2 | 2 |
* |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 | 5 |
* Copyright (C) 2003-2008 |
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
#ifndef LEMON_BITS_MAP_EXTENDER_H |
| 20 | 20 |
#define LEMON_BITS_MAP_EXTENDER_H |
| 21 | 21 |
|
| 22 | 22 |
#include <iterator> |
| 23 | 23 |
|
| 24 | 24 |
#include <lemon/bits/traits.h> |
| 25 | 25 |
|
| 26 | 26 |
#include <lemon/concept_check.h> |
| 27 | 27 |
#include <lemon/concepts/maps.h> |
| 28 | 28 |
|
| 29 | 29 |
///\file |
| 30 | 30 |
///\brief Extenders for iterable maps. |
| 31 | 31 |
|
| 32 | 32 |
namespace lemon {
|
| 33 | 33 |
|
| 34 | 34 |
/// \ingroup graphbits |
| 35 | 35 |
/// |
| 36 | 36 |
/// \brief Extender for maps |
| 37 | 37 |
template <typename _Map> |
| 38 | 38 |
class MapExtender : public _Map {
|
| 39 | 39 |
public: |
| 40 | 40 |
|
| 41 | 41 |
typedef _Map Parent; |
| 42 | 42 |
typedef MapExtender Map; |
| 43 | 43 |
|
| 44 | 44 |
|
| 45 | 45 |
typedef typename Parent::Graph Graph; |
| 46 | 46 |
typedef typename Parent::Key Item; |
| 47 | 47 |
|
| 48 | 48 |
typedef typename Parent::Key Key; |
| 49 | 49 |
typedef typename Parent::Value Value; |
| 50 | 50 |
|
| 51 | 51 |
class MapIt; |
| 52 | 52 |
class ConstMapIt; |
| 53 | 53 |
|
| 54 | 54 |
friend class MapIt; |
| 55 | 55 |
friend class ConstMapIt; |
| 56 | 56 |
|
| 57 | 57 |
public: |
| 58 | 58 |
|
| 59 | 59 |
MapExtender(const Graph& graph) |
| 60 | 60 |
: Parent(graph) {}
|
| 61 | 61 |
|
| 62 | 62 |
MapExtender(const Graph& graph, const Value& value) |
| 63 | 63 |
: Parent(graph, value) {}
|
| 64 | 64 |
|
| 65 |
private: |
|
| 65 | 66 |
MapExtender& operator=(const MapExtender& cmap) {
|
| 66 | 67 |
return operator=<MapExtender>(cmap); |
| 67 | 68 |
} |
| 68 | 69 |
|
| 69 | 70 |
template <typename CMap> |
| 70 | 71 |
MapExtender& operator=(const CMap& cmap) {
|
| 71 | 72 |
Parent::operator=(cmap); |
| 72 | 73 |
return *this; |
| 73 | 74 |
} |
| 74 | 75 |
|
| 76 |
public: |
|
| 75 | 77 |
class MapIt : public Item {
|
| 76 | 78 |
public: |
| 77 | 79 |
|
| 78 | 80 |
typedef Item Parent; |
| 79 | 81 |
typedef typename Map::Value Value; |
| 80 | 82 |
|
| 81 | 83 |
MapIt() {}
|
| 82 | 84 |
|
| 83 | 85 |
MapIt(Invalid i) : Parent(i) { }
|
| 84 | 86 |
|
| 85 | 87 |
explicit MapIt(Map& _map) : map(_map) {
|
| 86 | 88 |
map.notifier()->first(*this); |
| 87 | 89 |
} |
| 88 | 90 |
|
| 89 | 91 |
MapIt(const Map& _map, const Item& item) |
| 90 | 92 |
: Parent(item), map(_map) {}
|
| 91 | 93 |
|
| 92 | 94 |
MapIt& operator++() {
|
| 93 | 95 |
map.notifier()->next(*this); |
| 94 | 96 |
return *this; |
| 95 | 97 |
} |
| 96 | 98 |
|
| 97 | 99 |
typename MapTraits<Map>::ConstReturnValue operator*() const {
|
| 98 | 100 |
return map[*this]; |
| 99 | 101 |
} |
| 100 | 102 |
|
| 101 | 103 |
typename MapTraits<Map>::ReturnValue operator*() {
|
| 102 | 104 |
return map[*this]; |
| 103 | 105 |
} |
| 104 | 106 |
|
| 105 | 107 |
void set(const Value& value) {
|
| 106 | 108 |
map.set(*this, value); |
| 107 | 109 |
} |
| 108 | 110 |
|
| 109 | 111 |
protected: |
| 110 | 112 |
Map& map; |
| 111 | 113 |
|
| 112 | 114 |
}; |
| 113 | 115 |
|
| 114 | 116 |
class ConstMapIt : public Item {
|
| 115 | 117 |
public: |
| 116 | 118 |
|
| 117 | 119 |
typedef Item Parent; |
| 118 | 120 |
|
| 119 | 121 |
typedef typename Map::Value Value; |
| 120 | 122 |
|
| 121 | 123 |
ConstMapIt() {}
|
| 122 | 124 |
|
| 123 | 125 |
ConstMapIt(Invalid i) : Parent(i) { }
|
| 124 | 126 |
|
| 125 | 127 |
explicit ConstMapIt(Map& _map) : map(_map) {
|
| 126 | 128 |
map.notifier()->first(*this); |
| 127 | 129 |
} |
| 128 | 130 |
|
| 129 | 131 |
ConstMapIt(const Map& _map, const Item& item) |
| 130 | 132 |
: Parent(item), map(_map) {}
|
| 131 | 133 |
|
| 132 | 134 |
ConstMapIt& operator++() {
|
| 133 | 135 |
map.notifier()->next(*this); |
| 134 | 136 |
return *this; |
| 135 | 137 |
} |
| 136 | 138 |
|
| 137 | 139 |
typename MapTraits<Map>::ConstReturnValue operator*() const {
|
| 138 | 140 |
return map[*this]; |
| 139 | 141 |
} |
| 140 | 142 |
|
| 141 | 143 |
protected: |
| 142 | 144 |
const Map& map; |
| 143 | 145 |
}; |
| 144 | 146 |
|
| 145 | 147 |
class ItemIt : public Item {
|
| 146 | 148 |
public: |
| 147 | 149 |
|
| 148 | 150 |
typedef Item Parent; |
| 149 | 151 |
|
| 150 | 152 |
ItemIt() {}
|
| 151 | 153 |
|
| 152 | 154 |
ItemIt(Invalid i) : Parent(i) { }
|
| 153 | 155 |
|
| 154 | 156 |
explicit ItemIt(Map& _map) : map(_map) {
|
| 155 | 157 |
map.notifier()->first(*this); |
| 156 | 158 |
} |
| 157 | 159 |
|
| 158 | 160 |
ItemIt(const Map& _map, const Item& item) |
| 159 | 161 |
: Parent(item), map(_map) {}
|
| 160 | 162 |
|
| 161 | 163 |
ItemIt& operator++() {
|
| 162 | 164 |
map.notifier()->next(*this); |
| 163 | 165 |
return *this; |
| 164 | 166 |
} |
| 165 | 167 |
|
| 166 | 168 |
protected: |
| 167 | 169 |
const Map& map; |
| 168 | 170 |
|
| 169 | 171 |
}; |
| 170 | 172 |
}; |
| 171 | 173 |
|
| 172 | 174 |
/// \ingroup graphbits |
| 173 | 175 |
/// |
| 174 | 176 |
/// \brief Extender for maps which use a subset of the items. |
| 175 | 177 |
template <typename _Graph, typename _Map> |
| 176 | 178 |
class SubMapExtender : public _Map {
|
| 177 | 179 |
public: |
| 178 | 180 |
|
| 179 | 181 |
typedef _Map Parent; |
| 180 | 182 |
typedef SubMapExtender Map; |
| 181 | 183 |
|
| 182 | 184 |
typedef _Graph Graph; |
| 183 | 185 |
|
| 184 | 186 |
typedef typename Parent::Key Item; |
| 185 | 187 |
|
| 186 | 188 |
typedef typename Parent::Key Key; |
| 187 | 189 |
typedef typename Parent::Value Value; |
| 188 | 190 |
|
| 189 | 191 |
class MapIt; |
| 190 | 192 |
class ConstMapIt; |
| 191 | 193 |
|
| 192 | 194 |
friend class MapIt; |
| 193 | 195 |
friend class ConstMapIt; |
| 194 | 196 |
|
| 195 | 197 |
public: |
| 196 | 198 |
|
| 197 | 199 |
SubMapExtender(const Graph& _graph) |
| 198 | 200 |
: Parent(_graph), graph(_graph) {}
|
| 199 | 201 |
|
| 200 | 202 |
SubMapExtender(const Graph& _graph, const Value& _value) |
| 201 | 203 |
: Parent(_graph, _value), graph(_graph) {}
|
| 202 | 204 |
|
| 205 |
private: |
|
| 203 | 206 |
SubMapExtender& operator=(const SubMapExtender& cmap) {
|
| 204 | 207 |
return operator=<MapExtender>(cmap); |
| 205 | 208 |
} |
| 206 | 209 |
|
| 207 | 210 |
template <typename CMap> |
| 208 | 211 |
SubMapExtender& operator=(const CMap& cmap) {
|
| 209 | 212 |
checkConcept<concepts::ReadMap<Key, Value>, CMap>(); |
| 210 | 213 |
Item it; |
| 211 | 214 |
for (graph.first(it); it != INVALID; graph.next(it)) {
|
| 212 | 215 |
Parent::set(it, cmap[it]); |
| 213 | 216 |
} |
| 214 | 217 |
return *this; |
| 215 | 218 |
} |
| 216 | 219 |
|
| 220 |
public: |
|
| 217 | 221 |
class MapIt : public Item {
|
| 218 | 222 |
public: |
| 219 | 223 |
|
| 220 | 224 |
typedef Item Parent; |
| 221 | 225 |
typedef typename Map::Value Value; |
| 222 | 226 |
|
| 223 | 227 |
MapIt() {}
|
| 224 | 228 |
|
| 225 | 229 |
MapIt(Invalid i) : Parent(i) { }
|
| 226 | 230 |
|
| 227 | 231 |
explicit MapIt(Map& _map) : map(_map) {
|
| 228 | 232 |
map.graph.first(*this); |
| 229 | 233 |
} |
| 230 | 234 |
|
| 231 | 235 |
MapIt(const Map& _map, const Item& item) |
| 232 | 236 |
: Parent(item), map(_map) {}
|
| 233 | 237 |
|
| 234 | 238 |
MapIt& operator++() {
|
| 235 | 239 |
map.graph.next(*this); |
| 236 | 240 |
return *this; |
| 237 | 241 |
} |
| 238 | 242 |
|
| 239 | 243 |
typename MapTraits<Map>::ConstReturnValue operator*() const {
|
| 240 | 244 |
return map[*this]; |
| 241 | 245 |
} |
| 242 | 246 |
|
| 243 | 247 |
typename MapTraits<Map>::ReturnValue operator*() {
|
| 244 | 248 |
return map[*this]; |
| 245 | 249 |
} |
| 246 | 250 |
|
| 247 | 251 |
void set(const Value& value) {
|
| 248 | 252 |
map.set(*this, value); |
| 249 | 253 |
} |
| 250 | 254 |
|
| 251 | 255 |
protected: |
| 252 | 256 |
Map& map; |
| 253 | 257 |
|
| 254 | 258 |
}; |
| 255 | 259 |
|
| 256 | 260 |
class ConstMapIt : public Item {
|
| 257 | 261 |
public: |
| 258 | 262 |
|
| 259 | 263 |
typedef Item Parent; |
| 260 | 264 |
|
| 261 | 265 |
typedef typename Map::Value Value; |
| 262 | 266 |
|
| 263 | 267 |
ConstMapIt() {}
|
| 264 | 268 |
|
| 265 | 269 |
ConstMapIt(Invalid i) : Parent(i) { }
|
| 266 | 270 |
|
| 267 | 271 |
explicit ConstMapIt(Map& _map) : map(_map) {
|
| 268 | 272 |
map.graph.first(*this); |
| 269 | 273 |
} |
| 270 | 274 |
|
| 271 | 275 |
ConstMapIt(const Map& _map, const Item& item) |
| 272 | 276 |
: Parent(item), map(_map) {}
|
| 273 | 277 |
|
| 274 | 278 |
ConstMapIt& operator++() {
|
| 275 | 279 |
map.graph.next(*this); |
| 276 | 280 |
return *this; |
| 277 | 281 |
} |
| 278 | 282 |
|
| 279 | 283 |
typename MapTraits<Map>::ConstReturnValue operator*() const {
|
| 280 | 284 |
return map[*this]; |
| 281 | 285 |
} |
| 282 | 286 |
|
| 283 | 287 |
protected: |
| 284 | 288 |
const Map& map; |
| 285 | 289 |
}; |
| 286 | 290 |
|
| 287 | 291 |
class ItemIt : public Item {
|
| 288 | 292 |
public: |
| 289 | 293 |
|
| 290 | 294 |
typedef Item Parent; |
| 291 | 295 |
|
| 292 | 296 |
ItemIt() {}
|
| 293 | 297 |
|
| 294 | 298 |
ItemIt(Invalid i) : Parent(i) { }
|
| 295 | 299 |
|
| 296 | 300 |
explicit ItemIt(Map& _map) : map(_map) {
|
| 297 | 301 |
map.graph.first(*this); |
| 298 | 302 |
} |
| 299 | 303 |
|
| 300 | 304 |
ItemIt(const Map& _map, const Item& item) |
| 301 | 305 |
: Parent(item), map(_map) {}
|
| 302 | 306 |
|
| 303 | 307 |
ItemIt& operator++() {
|
| 304 | 308 |
map.graph.next(*this); |
| 305 | 309 |
return *this; |
| 306 | 310 |
} |
| 307 | 311 |
|
| 308 | 312 |
protected: |
| 309 | 313 |
const Map& map; |
| 310 | 314 |
|
| 311 | 315 |
}; |
| 312 | 316 |
| ... | ... |
@@ -7,192 +7,193 @@ |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
#ifndef LEMON_BITS_VECTOR_MAP_H |
| 20 | 20 |
#define LEMON_BITS_VECTOR_MAP_H |
| 21 | 21 |
|
| 22 | 22 |
#include <vector> |
| 23 | 23 |
#include <algorithm> |
| 24 | 24 |
|
| 25 | 25 |
#include <lemon/core.h> |
| 26 | 26 |
#include <lemon/bits/alteration_notifier.h> |
| 27 | 27 |
|
| 28 | 28 |
#include <lemon/concept_check.h> |
| 29 | 29 |
#include <lemon/concepts/maps.h> |
| 30 | 30 |
|
| 31 | 31 |
///\ingroup graphbits |
| 32 | 32 |
/// |
| 33 | 33 |
///\file |
| 34 | 34 |
///\brief Vector based graph maps. |
| 35 | 35 |
namespace lemon {
|
| 36 | 36 |
|
| 37 | 37 |
/// \ingroup graphbits |
| 38 | 38 |
/// |
| 39 | 39 |
/// \brief Graph map based on the std::vector storage. |
| 40 | 40 |
/// |
| 41 | 41 |
/// The VectorMap template class is graph map structure what |
| 42 | 42 |
/// automatically updates the map when a key is added to or erased from |
| 43 | 43 |
/// the map. This map type uses the std::vector to store the values. |
| 44 | 44 |
/// |
| 45 | 45 |
/// \tparam _Notifier The AlterationNotifier that will notify this map. |
| 46 | 46 |
/// \tparam _Item The item type of the graph items. |
| 47 | 47 |
/// \tparam _Value The value type of the map. |
| 48 | 48 |
/// \todo Fix the doc: there is _Graph parameter instead of _Notifier. |
| 49 | 49 |
template <typename _Graph, typename _Item, typename _Value> |
| 50 | 50 |
class VectorMap |
| 51 | 51 |
: public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
|
| 52 | 52 |
private: |
| 53 | 53 |
|
| 54 | 54 |
/// The container type of the map. |
| 55 | 55 |
typedef std::vector<_Value> Container; |
| 56 | 56 |
|
| 57 | 57 |
public: |
| 58 | 58 |
|
| 59 | 59 |
/// The graph type of the map. |
| 60 | 60 |
typedef _Graph Graph; |
| 61 | 61 |
/// The item type of the map. |
| 62 | 62 |
typedef _Item Item; |
| 63 | 63 |
/// The reference map tag. |
| 64 | 64 |
typedef True ReferenceMapTag; |
| 65 | 65 |
|
| 66 | 66 |
/// The key type of the map. |
| 67 | 67 |
typedef _Item Key; |
| 68 | 68 |
/// The value type of the map. |
| 69 | 69 |
typedef _Value Value; |
| 70 | 70 |
|
| 71 | 71 |
/// The notifier type. |
| 72 | 72 |
typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier; |
| 73 | 73 |
|
| 74 | 74 |
/// The map type. |
| 75 | 75 |
typedef VectorMap Map; |
| 76 | 76 |
/// The base class of the map. |
| 77 | 77 |
typedef typename Notifier::ObserverBase Parent; |
| 78 | 78 |
|
| 79 | 79 |
/// The reference type of the map; |
| 80 | 80 |
typedef typename Container::reference Reference; |
| 81 | 81 |
/// The const reference type of the map; |
| 82 | 82 |
typedef typename Container::const_reference ConstReference; |
| 83 | 83 |
|
| 84 | 84 |
|
| 85 | 85 |
/// \brief Constructor to attach the new map into the notifier. |
| 86 | 86 |
/// |
| 87 | 87 |
/// It constructs a map and attachs it into the notifier. |
| 88 | 88 |
/// It adds all the items of the graph to the map. |
| 89 | 89 |
VectorMap(const Graph& graph) {
|
| 90 | 90 |
Parent::attach(graph.notifier(Item())); |
| 91 | 91 |
container.resize(Parent::notifier()->maxId() + 1); |
| 92 | 92 |
} |
| 93 | 93 |
|
| 94 | 94 |
/// \brief Constructor uses given value to initialize the map. |
| 95 | 95 |
/// |
| 96 | 96 |
/// It constructs a map uses a given value to initialize the map. |
| 97 | 97 |
/// It adds all the items of the graph to the map. |
| 98 | 98 |
VectorMap(const Graph& graph, const Value& value) {
|
| 99 | 99 |
Parent::attach(graph.notifier(Item())); |
| 100 | 100 |
container.resize(Parent::notifier()->maxId() + 1, value); |
| 101 | 101 |
} |
| 102 | 102 |
|
| 103 |
private: |
|
| 103 | 104 |
/// \brief Copy constructor |
| 104 | 105 |
/// |
| 105 | 106 |
/// Copy constructor. |
| 106 | 107 |
VectorMap(const VectorMap& _copy) : Parent() {
|
| 107 | 108 |
if (_copy.attached()) {
|
| 108 | 109 |
Parent::attach(*_copy.notifier()); |
| 109 | 110 |
container = _copy.container; |
| 110 | 111 |
} |
| 111 | 112 |
} |
| 112 | 113 |
|
| 113 | 114 |
/// \brief Assign operator. |
| 114 | 115 |
/// |
| 115 | 116 |
/// This operator assigns for each item in the map the |
| 116 | 117 |
/// value mapped to the same item in the copied map. |
| 117 | 118 |
/// The parameter map should be indiced with the same |
| 118 | 119 |
/// itemset because this assign operator does not change |
| 119 | 120 |
/// the container of the map. |
| 120 | 121 |
VectorMap& operator=(const VectorMap& cmap) {
|
| 121 | 122 |
return operator=<VectorMap>(cmap); |
| 122 | 123 |
} |
| 123 | 124 |
|
| 124 | 125 |
|
| 125 | 126 |
/// \brief Template assign operator. |
| 126 | 127 |
/// |
| 127 | 128 |
/// The given parameter should be conform to the ReadMap |
| 128 | 129 |
/// concecpt and could be indiced by the current item set of |
| 129 | 130 |
/// the NodeMap. In this case the value for each item |
| 130 | 131 |
/// is assigned by the value of the given ReadMap. |
| 131 | 132 |
template <typename CMap> |
| 132 | 133 |
VectorMap& operator=(const CMap& cmap) {
|
| 133 | 134 |
checkConcept<concepts::ReadMap<Key, _Value>, CMap>(); |
| 134 | 135 |
const typename Parent::Notifier* nf = Parent::notifier(); |
| 135 | 136 |
Item it; |
| 136 | 137 |
for (nf->first(it); it != INVALID; nf->next(it)) {
|
| 137 | 138 |
set(it, cmap[it]); |
| 138 | 139 |
} |
| 139 | 140 |
return *this; |
| 140 | 141 |
} |
| 141 | 142 |
|
| 142 | 143 |
public: |
| 143 | 144 |
|
| 144 | 145 |
/// \brief The subcript operator. |
| 145 | 146 |
/// |
| 146 | 147 |
/// The subscript operator. The map can be subscripted by the |
| 147 | 148 |
/// actual items of the graph. |
| 148 | 149 |
Reference operator[](const Key& key) {
|
| 149 | 150 |
return container[Parent::notifier()->id(key)]; |
| 150 | 151 |
} |
| 151 | 152 |
|
| 152 | 153 |
/// \brief The const subcript operator. |
| 153 | 154 |
/// |
| 154 | 155 |
/// The const subscript operator. The map can be subscripted by the |
| 155 | 156 |
/// actual items of the graph. |
| 156 | 157 |
ConstReference operator[](const Key& key) const {
|
| 157 | 158 |
return container[Parent::notifier()->id(key)]; |
| 158 | 159 |
} |
| 159 | 160 |
|
| 160 | 161 |
|
| 161 | 162 |
/// \brief The setter function of the map. |
| 162 | 163 |
/// |
| 163 | 164 |
/// It the same as operator[](key) = value expression. |
| 164 | 165 |
void set(const Key& key, const Value& value) {
|
| 165 | 166 |
(*this)[key] = value; |
| 166 | 167 |
} |
| 167 | 168 |
|
| 168 | 169 |
protected: |
| 169 | 170 |
|
| 170 | 171 |
/// \brief Adds a new key to the map. |
| 171 | 172 |
/// |
| 172 | 173 |
/// It adds a new key to the map. It called by the observer notifier |
| 173 | 174 |
/// and it overrides the add() member function of the observer base. |
| 174 | 175 |
virtual void add(const Key& key) {
|
| 175 | 176 |
int id = Parent::notifier()->id(key); |
| 176 | 177 |
if (id >= int(container.size())) {
|
| 177 | 178 |
container.resize(id + 1); |
| 178 | 179 |
} |
| 179 | 180 |
} |
| 180 | 181 |
|
| 181 | 182 |
/// \brief Adds more new keys to the map. |
| 182 | 183 |
/// |
| 183 | 184 |
/// It adds more new keys to the map. It called by the observer notifier |
| 184 | 185 |
/// and it overrides the add() member function of the observer base. |
| 185 | 186 |
virtual void add(const std::vector<Key>& keys) {
|
| 186 | 187 |
int max = container.size() - 1; |
| 187 | 188 |
for (int i = 0; i < int(keys.size()); ++i) {
|
| 188 | 189 |
int id = Parent::notifier()->id(keys[i]); |
| 189 | 190 |
if (id >= max) {
|
| 190 | 191 |
max = id; |
| 191 | 192 |
} |
| 192 | 193 |
} |
| 193 | 194 |
container.resize(max + 1); |
| 194 | 195 |
} |
| 195 | 196 |
|
| 196 | 197 |
/// \brief Erase a key from the map. |
| 197 | 198 |
/// |
| 198 | 199 |
/// Erase a key from the map. It called by the observer notifier |
| ... | ... |
@@ -341,145 +341,147 @@ |
| 341 | 341 |
///Gives back the target node of an arc. |
| 342 | 342 |
/// |
| 343 | 343 |
Node target(Arc) const { return INVALID; }
|
| 344 | 344 |
///Gives back the source node of an arc. |
| 345 | 345 |
|
| 346 | 346 |
///Gives back the source node of an arc. |
| 347 | 347 |
/// |
| 348 | 348 |
Node source(Arc) const { return INVALID; }
|
| 349 | 349 |
|
| 350 | 350 |
/// \brief Returns the ID of the node. |
| 351 | 351 |
int id(Node) const { return -1; }
|
| 352 | 352 |
|
| 353 | 353 |
/// \brief Returns the ID of the arc. |
| 354 | 354 |
int id(Arc) const { return -1; }
|
| 355 | 355 |
|
| 356 | 356 |
/// \brief Returns the node with the given ID. |
| 357 | 357 |
/// |
| 358 | 358 |
/// \pre The argument should be a valid node ID in the graph. |
| 359 | 359 |
Node nodeFromId(int) const { return INVALID; }
|
| 360 | 360 |
|
| 361 | 361 |
/// \brief Returns the arc with the given ID. |
| 362 | 362 |
/// |
| 363 | 363 |
/// \pre The argument should be a valid arc ID in the graph. |
| 364 | 364 |
Arc arcFromId(int) const { return INVALID; }
|
| 365 | 365 |
|
| 366 | 366 |
/// \brief Returns an upper bound on the node IDs. |
| 367 | 367 |
int maxNodeId() const { return -1; }
|
| 368 | 368 |
|
| 369 | 369 |
/// \brief Returns an upper bound on the arc IDs. |
| 370 | 370 |
int maxArcId() const { return -1; }
|
| 371 | 371 |
|
| 372 | 372 |
void first(Node&) const {}
|
| 373 | 373 |
void next(Node&) const {}
|
| 374 | 374 |
|
| 375 | 375 |
void first(Arc&) const {}
|
| 376 | 376 |
void next(Arc&) const {}
|
| 377 | 377 |
|
| 378 | 378 |
|
| 379 | 379 |
void firstIn(Arc&, const Node&) const {}
|
| 380 | 380 |
void nextIn(Arc&) const {}
|
| 381 | 381 |
|
| 382 | 382 |
void firstOut(Arc&, const Node&) const {}
|
| 383 | 383 |
void nextOut(Arc&) const {}
|
| 384 | 384 |
|
| 385 | 385 |
// The second parameter is dummy. |
| 386 | 386 |
Node fromId(int, Node) const { return INVALID; }
|
| 387 | 387 |
// The second parameter is dummy. |
| 388 | 388 |
Arc fromId(int, Arc) const { return INVALID; }
|
| 389 | 389 |
|
| 390 | 390 |
// Dummy parameter. |
| 391 | 391 |
int maxId(Node) const { return -1; }
|
| 392 | 392 |
// Dummy parameter. |
| 393 | 393 |
int maxId(Arc) const { return -1; }
|
| 394 | 394 |
|
| 395 | 395 |
/// \brief The base node of the iterator. |
| 396 | 396 |
/// |
| 397 | 397 |
/// Gives back the base node of the iterator. |
| 398 | 398 |
/// It is always the target of the pointed arc. |
| 399 | 399 |
Node baseNode(const InArcIt&) const { return INVALID; }
|
| 400 | 400 |
|
| 401 | 401 |
/// \brief The running node of the iterator. |
| 402 | 402 |
/// |
| 403 | 403 |
/// Gives back the running node of the iterator. |
| 404 | 404 |
/// It is always the source of the pointed arc. |
| 405 | 405 |
Node runningNode(const InArcIt&) const { return INVALID; }
|
| 406 | 406 |
|
| 407 | 407 |
/// \brief The base node of the iterator. |
| 408 | 408 |
/// |
| 409 | 409 |
/// Gives back the base node of the iterator. |
| 410 | 410 |
/// It is always the source of the pointed arc. |
| 411 | 411 |
Node baseNode(const OutArcIt&) const { return INVALID; }
|
| 412 | 412 |
|
| 413 | 413 |
/// \brief The running node of the iterator. |
| 414 | 414 |
/// |
| 415 | 415 |
/// Gives back the running node of the iterator. |
| 416 | 416 |
/// It is always the target of the pointed arc. |
| 417 | 417 |
Node runningNode(const OutArcIt&) const { return INVALID; }
|
| 418 | 418 |
|
| 419 | 419 |
/// \brief The opposite node on the given arc. |
| 420 | 420 |
/// |
| 421 | 421 |
/// Gives back the opposite node on the given arc. |
| 422 | 422 |
Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
|
| 423 | 423 |
|
| 424 | 424 |
/// \brief Read write map of the nodes to type \c T. |
| 425 | 425 |
/// |
| 426 | 426 |
/// ReadWrite map of the nodes to type \c T. |
| 427 | 427 |
/// \sa Reference |
| 428 | 428 |
template<class T> |
| 429 | 429 |
class NodeMap : public ReadWriteMap< Node, T > {
|
| 430 | 430 |
public: |
| 431 | 431 |
|
| 432 | 432 |
///\e |
| 433 | 433 |
NodeMap(const Digraph&) { }
|
| 434 | 434 |
///\e |
| 435 | 435 |
NodeMap(const Digraph&, T) { }
|
| 436 | 436 |
|
| 437 |
private: |
|
| 437 | 438 |
///Copy constructor |
| 438 | 439 |
NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
|
| 439 | 440 |
///Assignment operator |
| 440 | 441 |
template <typename CMap> |
| 441 | 442 |
NodeMap& operator=(const CMap&) {
|
| 442 | 443 |
checkConcept<ReadMap<Node, T>, CMap>(); |
| 443 | 444 |
return *this; |
| 444 | 445 |
} |
| 445 | 446 |
}; |
| 446 | 447 |
|
| 447 | 448 |
/// \brief Read write map of the arcs to type \c T. |
| 448 | 449 |
/// |
| 449 | 450 |
/// Reference map of the arcs to type \c T. |
| 450 | 451 |
/// \sa Reference |
| 451 | 452 |
template<class T> |
| 452 | 453 |
class ArcMap : public ReadWriteMap<Arc,T> {
|
| 453 | 454 |
public: |
| 454 | 455 |
|
| 455 | 456 |
///\e |
| 456 | 457 |
ArcMap(const Digraph&) { }
|
| 457 | 458 |
///\e |
| 458 | 459 |
ArcMap(const Digraph&, T) { }
|
| 460 |
private: |
|
| 459 | 461 |
///Copy constructor |
| 460 | 462 |
ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
|
| 461 | 463 |
///Assignment operator |
| 462 | 464 |
template <typename CMap> |
| 463 | 465 |
ArcMap& operator=(const CMap&) {
|
| 464 | 466 |
checkConcept<ReadMap<Arc, T>, CMap>(); |
| 465 | 467 |
return *this; |
| 466 | 468 |
} |
| 467 | 469 |
}; |
| 468 | 470 |
|
| 469 | 471 |
template <typename _Digraph> |
| 470 | 472 |
struct Constraints {
|
| 471 | 473 |
void constraints() {
|
| 472 | 474 |
checkConcept<IterableDigraphComponent<>, _Digraph>(); |
| 473 | 475 |
checkConcept<IDableDigraphComponent<>, _Digraph>(); |
| 474 | 476 |
checkConcept<MappableDigraphComponent<>, _Digraph>(); |
| 475 | 477 |
} |
| 476 | 478 |
}; |
| 477 | 479 |
|
| 478 | 480 |
}; |
| 479 | 481 |
|
| 480 | 482 |
} //namespace concepts |
| 481 | 483 |
} //namespace lemon |
| 482 | 484 |
|
| 483 | 485 |
|
| 484 | 486 |
|
| 485 | 487 |
#endif // LEMON_CONCEPT_DIGRAPH_H |
| ... | ... |
@@ -419,238 +419,241 @@ |
| 419 | 419 |
/// |
| 420 | 420 |
OutArcIt(const OutArcIt& e) : Arc(e) { }
|
| 421 | 421 |
/// Initialize the iterator to be invalid. |
| 422 | 422 |
|
| 423 | 423 |
/// Initialize the iterator to be invalid. |
| 424 | 424 |
/// |
| 425 | 425 |
OutArcIt(Invalid) { }
|
| 426 | 426 |
/// This constructor sets the iterator to the first outgoing arc. |
| 427 | 427 |
|
| 428 | 428 |
/// This constructor sets the iterator to the first outgoing arc of |
| 429 | 429 |
/// the node. |
| 430 | 430 |
///@param n the node |
| 431 | 431 |
///@param g the graph |
| 432 | 432 |
OutArcIt(const Graph& n, const Node& g) {
|
| 433 | 433 |
ignore_unused_variable_warning(n); |
| 434 | 434 |
ignore_unused_variable_warning(g); |
| 435 | 435 |
} |
| 436 | 436 |
/// Arc -> OutArcIt conversion |
| 437 | 437 |
|
| 438 | 438 |
/// Sets the iterator to the value of the trivial iterator. |
| 439 | 439 |
/// This feature necessitates that each time we |
| 440 | 440 |
/// iterate the arc-set, the iteration order is the same. |
| 441 | 441 |
OutArcIt(const Graph&, const Arc&) { }
|
| 442 | 442 |
///Next outgoing arc |
| 443 | 443 |
|
| 444 | 444 |
/// Assign the iterator to the next |
| 445 | 445 |
/// outgoing arc of the corresponding node. |
| 446 | 446 |
OutArcIt& operator++() { return *this; }
|
| 447 | 447 |
}; |
| 448 | 448 |
|
| 449 | 449 |
/// This iterator goes trough the incoming directed arcs of a node. |
| 450 | 450 |
|
| 451 | 451 |
/// This iterator goes trough the \e incoming arcs of a certain node |
| 452 | 452 |
/// of a graph. |
| 453 | 453 |
/// Its usage is quite simple, for example you can count the number |
| 454 | 454 |
/// of outgoing arcs of a node \c n |
| 455 | 455 |
/// in graph \c g of type \c Graph as follows. |
| 456 | 456 |
///\code |
| 457 | 457 |
/// int count=0; |
| 458 | 458 |
/// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count; |
| 459 | 459 |
///\endcode |
| 460 | 460 |
|
| 461 | 461 |
class InArcIt : public Arc {
|
| 462 | 462 |
public: |
| 463 | 463 |
/// Default constructor |
| 464 | 464 |
|
| 465 | 465 |
/// @warning The default constructor sets the iterator |
| 466 | 466 |
/// to an undefined value. |
| 467 | 467 |
InArcIt() { }
|
| 468 | 468 |
/// Copy constructor. |
| 469 | 469 |
|
| 470 | 470 |
/// Copy constructor. |
| 471 | 471 |
/// |
| 472 | 472 |
InArcIt(const InArcIt& e) : Arc(e) { }
|
| 473 | 473 |
/// Initialize the iterator to be invalid. |
| 474 | 474 |
|
| 475 | 475 |
/// Initialize the iterator to be invalid. |
| 476 | 476 |
/// |
| 477 | 477 |
InArcIt(Invalid) { }
|
| 478 | 478 |
/// This constructor sets the iterator to first incoming arc. |
| 479 | 479 |
|
| 480 | 480 |
/// This constructor set the iterator to the first incoming arc of |
| 481 | 481 |
/// the node. |
| 482 | 482 |
///@param n the node |
| 483 | 483 |
///@param g the graph |
| 484 | 484 |
InArcIt(const Graph& g, const Node& n) {
|
| 485 | 485 |
ignore_unused_variable_warning(n); |
| 486 | 486 |
ignore_unused_variable_warning(g); |
| 487 | 487 |
} |
| 488 | 488 |
/// Arc -> InArcIt conversion |
| 489 | 489 |
|
| 490 | 490 |
/// Sets the iterator to the value of the trivial iterator \c e. |
| 491 | 491 |
/// This feature necessitates that each time we |
| 492 | 492 |
/// iterate the arc-set, the iteration order is the same. |
| 493 | 493 |
InArcIt(const Graph&, const Arc&) { }
|
| 494 | 494 |
/// Next incoming arc |
| 495 | 495 |
|
| 496 | 496 |
/// Assign the iterator to the next inarc of the corresponding node. |
| 497 | 497 |
/// |
| 498 | 498 |
InArcIt& operator++() { return *this; }
|
| 499 | 499 |
}; |
| 500 | 500 |
|
| 501 | 501 |
/// \brief Read write map of the nodes to type \c T. |
| 502 | 502 |
/// |
| 503 | 503 |
/// ReadWrite map of the nodes to type \c T. |
| 504 | 504 |
/// \sa Reference |
| 505 | 505 |
template<class T> |
| 506 | 506 |
class NodeMap : public ReadWriteMap< Node, T > |
| 507 | 507 |
{
|
| 508 | 508 |
public: |
| 509 | 509 |
|
| 510 | 510 |
///\e |
| 511 | 511 |
NodeMap(const Graph&) { }
|
| 512 | 512 |
///\e |
| 513 | 513 |
NodeMap(const Graph&, T) { }
|
| 514 | 514 |
|
| 515 |
private: |
|
| 515 | 516 |
///Copy constructor |
| 516 | 517 |
NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
|
| 517 | 518 |
///Assignment operator |
| 518 | 519 |
template <typename CMap> |
| 519 | 520 |
NodeMap& operator=(const CMap&) {
|
| 520 | 521 |
checkConcept<ReadMap<Node, T>, CMap>(); |
| 521 | 522 |
return *this; |
| 522 | 523 |
} |
| 523 | 524 |
}; |
| 524 | 525 |
|
| 525 | 526 |
/// \brief Read write map of the directed arcs to type \c T. |
| 526 | 527 |
/// |
| 527 | 528 |
/// Reference map of the directed arcs to type \c T. |
| 528 | 529 |
/// \sa Reference |
| 529 | 530 |
template<class T> |
| 530 | 531 |
class ArcMap : public ReadWriteMap<Arc,T> |
| 531 | 532 |
{
|
| 532 | 533 |
public: |
| 533 | 534 |
|
| 534 | 535 |
///\e |
| 535 | 536 |
ArcMap(const Graph&) { }
|
| 536 | 537 |
///\e |
| 537 | 538 |
ArcMap(const Graph&, T) { }
|
| 539 |
private: |
|
| 538 | 540 |
///Copy constructor |
| 539 | 541 |
ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
|
| 540 | 542 |
///Assignment operator |
| 541 | 543 |
template <typename CMap> |
| 542 | 544 |
ArcMap& operator=(const CMap&) {
|
| 543 | 545 |
checkConcept<ReadMap<Arc, T>, CMap>(); |
| 544 | 546 |
return *this; |
| 545 | 547 |
} |
| 546 | 548 |
}; |
| 547 | 549 |
|
| 548 | 550 |
/// Read write map of the edges to type \c T. |
| 549 | 551 |
|
| 550 | 552 |
/// Reference map of the arcs to type \c T. |
| 551 | 553 |
/// \sa Reference |
| 552 | 554 |
template<class T> |
| 553 | 555 |
class EdgeMap : public ReadWriteMap<Edge,T> |
| 554 | 556 |
{
|
| 555 | 557 |
public: |
| 556 | 558 |
|
| 557 | 559 |
///\e |
| 558 | 560 |
EdgeMap(const Graph&) { }
|
| 559 | 561 |
///\e |
| 560 | 562 |
EdgeMap(const Graph&, T) { }
|
| 563 |
private: |
|
| 561 | 564 |
///Copy constructor |
| 562 | 565 |
EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
|
| 563 | 566 |
///Assignment operator |
| 564 | 567 |
template <typename CMap> |
| 565 | 568 |
EdgeMap& operator=(const CMap&) {
|
| 566 | 569 |
checkConcept<ReadMap<Edge, T>, CMap>(); |
| 567 | 570 |
return *this; |
| 568 | 571 |
} |
| 569 | 572 |
}; |
| 570 | 573 |
|
| 571 | 574 |
/// \brief Direct the given edge. |
| 572 | 575 |
/// |
| 573 | 576 |
/// Direct the given edge. The returned arc source |
| 574 | 577 |
/// will be the given node. |
| 575 | 578 |
Arc direct(const Edge&, const Node&) const {
|
| 576 | 579 |
return INVALID; |
| 577 | 580 |
} |
| 578 | 581 |
|
| 579 | 582 |
/// \brief Direct the given edge. |
| 580 | 583 |
/// |
| 581 | 584 |
/// Direct the given edge. The returned arc |
| 582 | 585 |
/// represents the given edge and the direction comes |
| 583 | 586 |
/// from the bool parameter. The source of the edge and |
| 584 | 587 |
/// the directed arc is the same when the given bool is true. |
| 585 | 588 |
Arc direct(const Edge&, bool) const {
|
| 586 | 589 |
return INVALID; |
| 587 | 590 |
} |
| 588 | 591 |
|
| 589 | 592 |
/// \brief Returns true if the arc has default orientation. |
| 590 | 593 |
/// |
| 591 | 594 |
/// Returns whether the given directed arc is same orientation as |
| 592 | 595 |
/// the corresponding edge's default orientation. |
| 593 | 596 |
bool direction(Arc) const { return true; }
|
| 594 | 597 |
|
| 595 | 598 |
/// \brief Returns the opposite directed arc. |
| 596 | 599 |
/// |
| 597 | 600 |
/// Returns the opposite directed arc. |
| 598 | 601 |
Arc oppositeArc(Arc) const { return INVALID; }
|
| 599 | 602 |
|
| 600 | 603 |
/// \brief Opposite node on an arc |
| 601 | 604 |
/// |
| 602 | 605 |
/// \return the opposite of the given Node on the given Edge |
| 603 | 606 |
Node oppositeNode(Node, Edge) const { return INVALID; }
|
| 604 | 607 |
|
| 605 | 608 |
/// \brief First node of the edge. |
| 606 | 609 |
/// |
| 607 | 610 |
/// \return the first node of the given Edge. |
| 608 | 611 |
/// |
| 609 | 612 |
/// Naturally edges don't have direction and thus |
| 610 | 613 |
/// don't have source and target node. But we use these two methods |
| 611 | 614 |
/// to query the two nodes of the arc. The direction of the arc |
| 612 | 615 |
/// which arises this way is called the inherent direction of the |
| 613 | 616 |
/// edge, and is used to define the "default" direction |
| 614 | 617 |
/// of the directed versions of the arcs. |
| 615 | 618 |
/// \sa direction |
| 616 | 619 |
Node u(Edge) const { return INVALID; }
|
| 617 | 620 |
|
| 618 | 621 |
/// \brief Second node of the edge. |
| 619 | 622 |
Node v(Edge) const { return INVALID; }
|
| 620 | 623 |
|
| 621 | 624 |
/// \brief Source node of the directed arc. |
| 622 | 625 |
Node source(Arc) const { return INVALID; }
|
| 623 | 626 |
|
| 624 | 627 |
/// \brief Target node of the directed arc. |
| 625 | 628 |
Node target(Arc) const { return INVALID; }
|
| 626 | 629 |
|
| 627 | 630 |
/// \brief Returns the id of the node. |
| 628 | 631 |
int id(Node) const { return -1; }
|
| 629 | 632 |
|
| 630 | 633 |
/// \brief Returns the id of the edge. |
| 631 | 634 |
int id(Edge) const { return -1; }
|
| 632 | 635 |
|
| 633 | 636 |
/// \brief Returns the id of the arc. |
| 634 | 637 |
int id(Arc) const { return -1; }
|
| 635 | 638 |
|
| 636 | 639 |
/// \brief Returns the node with the given id. |
| 637 | 640 |
/// |
| 638 | 641 |
/// \pre The argument should be a valid node id in the graph. |
| 639 | 642 |
Node nodeFromId(int) const { return INVALID; }
|
| 640 | 643 |
|
| 641 | 644 |
/// \brief Returns the edge with the given id. |
| 642 | 645 |
/// |
| 643 | 646 |
/// \pre The argument should be a valid edge id in the graph. |
| 644 | 647 |
Edge edgeFromId(int) const { return INVALID; }
|
| 645 | 648 |
|
| 646 | 649 |
/// \brief Returns the arc with the given id. |
| 647 | 650 |
/// |
| 648 | 651 |
/// \pre The argument should be a valid arc id in the graph. |
| 649 | 652 |
Arc arcFromId(int) const { return INVALID; }
|
| 650 | 653 |
|
| 651 | 654 |
/// \brief Returns an upper bound on the node IDs. |
| 652 | 655 |
int maxNodeId() const { return -1; }
|
| 653 | 656 |
|
| 654 | 657 |
/// \brief Returns an upper bound on the edge IDs. |
| 655 | 658 |
int maxEdgeId() const { return -1; }
|
| 656 | 659 |
| ... | ... |
@@ -912,402 +912,409 @@ |
| 912 | 912 |
|
| 913 | 913 |
/// \brief Gives back the arc alteration notifier. |
| 914 | 914 |
/// |
| 915 | 915 |
/// Gives back the arc alteration notifier. |
| 916 | 916 |
ArcNotifier& notifier(Arc) const {
|
| 917 | 917 |
return ArcNotifier(); |
| 918 | 918 |
} |
| 919 | 919 |
|
| 920 | 920 |
template <typename _Digraph> |
| 921 | 921 |
struct Constraints {
|
| 922 | 922 |
void constraints() {
|
| 923 | 923 |
checkConcept<Base, _Digraph>(); |
| 924 | 924 |
typename _Digraph::NodeNotifier& nn |
| 925 | 925 |
= digraph.notifier(typename _Digraph::Node()); |
| 926 | 926 |
|
| 927 | 927 |
typename _Digraph::ArcNotifier& en |
| 928 | 928 |
= digraph.notifier(typename _Digraph::Arc()); |
| 929 | 929 |
|
| 930 | 930 |
ignore_unused_variable_warning(nn); |
| 931 | 931 |
ignore_unused_variable_warning(en); |
| 932 | 932 |
} |
| 933 | 933 |
|
| 934 | 934 |
const _Digraph& digraph; |
| 935 | 935 |
|
| 936 | 936 |
}; |
| 937 | 937 |
|
| 938 | 938 |
}; |
| 939 | 939 |
|
| 940 | 940 |
/// \brief An empty alteration notifier undirected graph class. |
| 941 | 941 |
/// |
| 942 | 942 |
/// This class provides beside the core graph features alteration |
| 943 | 943 |
/// notifier interface for the graph structure. This implements |
| 944 | 944 |
/// an observer-notifier pattern for each graph item. More |
| 945 | 945 |
/// obsevers can be registered into the notifier and whenever an |
| 946 | 946 |
/// alteration occured in the graph all the observers will |
| 947 | 947 |
/// notified about it. |
| 948 | 948 |
template <typename _Base = BaseGraphComponent> |
| 949 | 949 |
class AlterableGraphComponent : public AlterableDigraphComponent<_Base> {
|
| 950 | 950 |
public: |
| 951 | 951 |
|
| 952 | 952 |
typedef _Base Base; |
| 953 | 953 |
typedef typename Base::Edge Edge; |
| 954 | 954 |
|
| 955 | 955 |
|
| 956 | 956 |
/// The arc observer registry. |
| 957 | 957 |
typedef AlterationNotifier<AlterableGraphComponent, Edge> |
| 958 | 958 |
EdgeNotifier; |
| 959 | 959 |
|
| 960 | 960 |
/// \brief Gives back the arc alteration notifier. |
| 961 | 961 |
/// |
| 962 | 962 |
/// Gives back the arc alteration notifier. |
| 963 | 963 |
EdgeNotifier& notifier(Edge) const {
|
| 964 | 964 |
return EdgeNotifier(); |
| 965 | 965 |
} |
| 966 | 966 |
|
| 967 | 967 |
template <typename _Graph> |
| 968 | 968 |
struct Constraints {
|
| 969 | 969 |
void constraints() {
|
| 970 | 970 |
checkConcept<AlterableGraphComponent<Base>, _Graph>(); |
| 971 | 971 |
typename _Graph::EdgeNotifier& uen |
| 972 | 972 |
= graph.notifier(typename _Graph::Edge()); |
| 973 | 973 |
ignore_unused_variable_warning(uen); |
| 974 | 974 |
} |
| 975 | 975 |
|
| 976 | 976 |
const _Graph& graph; |
| 977 | 977 |
|
| 978 | 978 |
}; |
| 979 | 979 |
|
| 980 | 980 |
}; |
| 981 | 981 |
|
| 982 | 982 |
/// \brief Class describing the concept of graph maps |
| 983 | 983 |
/// |
| 984 | 984 |
/// This class describes the common interface of the graph maps |
| 985 | 985 |
/// (NodeMap, ArcMap), that is \ref maps-page "maps" which can be used to |
| 986 | 986 |
/// associate data to graph descriptors (nodes or arcs). |
| 987 | 987 |
template <typename _Graph, typename _Item, typename _Value> |
| 988 | 988 |
class GraphMap : public ReadWriteMap<_Item, _Value> {
|
| 989 | 989 |
public: |
| 990 | 990 |
|
| 991 | 991 |
typedef ReadWriteMap<_Item, _Value> Parent; |
| 992 | 992 |
|
| 993 | 993 |
/// The graph type of the map. |
| 994 | 994 |
typedef _Graph Graph; |
| 995 | 995 |
/// The key type of the map. |
| 996 | 996 |
typedef _Item Key; |
| 997 | 997 |
/// The value type of the map. |
| 998 | 998 |
typedef _Value Value; |
| 999 | 999 |
|
| 1000 | 1000 |
/// \brief Construct a new map. |
| 1001 | 1001 |
/// |
| 1002 | 1002 |
/// Construct a new map for the graph. |
| 1003 | 1003 |
explicit GraphMap(const Graph&) {}
|
| 1004 | 1004 |
/// \brief Construct a new map with default value. |
| 1005 | 1005 |
/// |
| 1006 | 1006 |
/// Construct a new map for the graph and initalise the values. |
| 1007 | 1007 |
GraphMap(const Graph&, const Value&) {}
|
| 1008 |
|
|
| 1009 |
private: |
|
| 1008 | 1010 |
/// \brief Copy constructor. |
| 1009 | 1011 |
/// |
| 1010 | 1012 |
/// Copy Constructor. |
| 1011 | 1013 |
GraphMap(const GraphMap&) : Parent() {}
|
| 1012 | 1014 |
|
| 1013 | 1015 |
/// \brief Assign operator. |
| 1014 | 1016 |
/// |
| 1015 | 1017 |
/// Assign operator. It does not mofify the underlying graph, |
| 1016 | 1018 |
/// it just iterates on the current item set and set the map |
| 1017 | 1019 |
/// with the value returned by the assigned map. |
| 1018 | 1020 |
template <typename CMap> |
| 1019 | 1021 |
GraphMap& operator=(const CMap&) {
|
| 1020 | 1022 |
checkConcept<ReadMap<Key, Value>, CMap>(); |
| 1021 | 1023 |
return *this; |
| 1022 | 1024 |
} |
| 1023 | 1025 |
|
| 1026 |
public: |
|
| 1024 | 1027 |
template<typename _Map> |
| 1025 | 1028 |
struct Constraints {
|
| 1026 | 1029 |
void constraints() {
|
| 1027 | 1030 |
checkConcept<ReadWriteMap<Key, Value>, _Map >(); |
| 1028 | 1031 |
// Construction with a graph parameter |
| 1029 | 1032 |
_Map a(g); |
| 1030 | 1033 |
// Constructor with a graph and a default value parameter |
| 1031 | 1034 |
_Map a2(g,t); |
| 1032 | 1035 |
// Copy constructor. |
| 1033 |
_Map b(c); |
|
| 1036 |
// _Map b(c); |
|
| 1034 | 1037 |
|
| 1035 |
ReadMap<Key, Value> cmap; |
|
| 1036 |
b = cmap; |
|
| 1038 |
// ReadMap<Key, Value> cmap; |
|
| 1039 |
// b = cmap; |
|
| 1037 | 1040 |
|
| 1041 |
ignore_unused_variable_warning(a); |
|
| 1038 | 1042 |
ignore_unused_variable_warning(a2); |
| 1039 |
ignore_unused_variable_warning(b); |
|
| 1043 |
// ignore_unused_variable_warning(b); |
|
| 1040 | 1044 |
} |
| 1041 | 1045 |
|
| 1042 | 1046 |
const _Map &c; |
| 1043 | 1047 |
const Graph &g; |
| 1044 | 1048 |
const typename GraphMap::Value &t; |
| 1045 | 1049 |
}; |
| 1046 | 1050 |
|
| 1047 | 1051 |
}; |
| 1048 | 1052 |
|
| 1049 | 1053 |
/// \brief An empty mappable digraph class. |
| 1050 | 1054 |
/// |
| 1051 | 1055 |
/// This class provides beside the core digraph features |
| 1052 | 1056 |
/// map interface for the digraph structure. |
| 1053 | 1057 |
/// This concept is part of the Digraph concept. |
| 1054 | 1058 |
template <typename _Base = BaseDigraphComponent> |
| 1055 | 1059 |
class MappableDigraphComponent : public _Base {
|
| 1056 | 1060 |
public: |
| 1057 | 1061 |
|
| 1058 | 1062 |
typedef _Base Base; |
| 1059 | 1063 |
typedef typename Base::Node Node; |
| 1060 | 1064 |
typedef typename Base::Arc Arc; |
| 1061 | 1065 |
|
| 1062 | 1066 |
typedef MappableDigraphComponent Digraph; |
| 1063 | 1067 |
|
| 1064 | 1068 |
/// \brief ReadWrite map of the nodes. |
| 1065 | 1069 |
/// |
| 1066 | 1070 |
/// ReadWrite map of the nodes. |
| 1067 | 1071 |
/// |
| 1068 | 1072 |
template <typename _Value> |
| 1069 | 1073 |
class NodeMap : public GraphMap<Digraph, Node, _Value> {
|
| 1070 | 1074 |
public: |
| 1071 | 1075 |
typedef GraphMap<MappableDigraphComponent, Node, _Value> Parent; |
| 1072 | 1076 |
|
| 1073 | 1077 |
/// \brief Construct a new map. |
| 1074 | 1078 |
/// |
| 1075 | 1079 |
/// Construct a new map for the digraph. |
| 1076 | 1080 |
explicit NodeMap(const MappableDigraphComponent& digraph) |
| 1077 | 1081 |
: Parent(digraph) {}
|
| 1078 | 1082 |
|
| 1079 | 1083 |
/// \brief Construct a new map with default value. |
| 1080 | 1084 |
/// |
| 1081 | 1085 |
/// Construct a new map for the digraph and initalise the values. |
| 1082 | 1086 |
NodeMap(const MappableDigraphComponent& digraph, const _Value& value) |
| 1083 | 1087 |
: Parent(digraph, value) {}
|
| 1084 | 1088 |
|
| 1089 |
private: |
|
| 1085 | 1090 |
/// \brief Copy constructor. |
| 1086 | 1091 |
/// |
| 1087 | 1092 |
/// Copy Constructor. |
| 1088 | 1093 |
NodeMap(const NodeMap& nm) : Parent(nm) {}
|
| 1089 | 1094 |
|
| 1090 | 1095 |
/// \brief Assign operator. |
| 1091 | 1096 |
/// |
| 1092 | 1097 |
/// Assign operator. |
| 1093 | 1098 |
template <typename CMap> |
| 1094 | 1099 |
NodeMap& operator=(const CMap&) {
|
| 1095 | 1100 |
checkConcept<ReadMap<Node, _Value>, CMap>(); |
| 1096 | 1101 |
return *this; |
| 1097 | 1102 |
} |
| 1098 | 1103 |
|
| 1099 | 1104 |
}; |
| 1100 | 1105 |
|
| 1101 | 1106 |
/// \brief ReadWrite map of the arcs. |
| 1102 | 1107 |
/// |
| 1103 | 1108 |
/// ReadWrite map of the arcs. |
| 1104 | 1109 |
/// |
| 1105 | 1110 |
template <typename _Value> |
| 1106 | 1111 |
class ArcMap : public GraphMap<Digraph, Arc, _Value> {
|
| 1107 | 1112 |
public: |
| 1108 | 1113 |
typedef GraphMap<MappableDigraphComponent, Arc, _Value> Parent; |
| 1109 | 1114 |
|
| 1110 | 1115 |
/// \brief Construct a new map. |
| 1111 | 1116 |
/// |
| 1112 | 1117 |
/// Construct a new map for the digraph. |
| 1113 | 1118 |
explicit ArcMap(const MappableDigraphComponent& digraph) |
| 1114 | 1119 |
: Parent(digraph) {}
|
| 1115 | 1120 |
|
| 1116 | 1121 |
/// \brief Construct a new map with default value. |
| 1117 | 1122 |
/// |
| 1118 | 1123 |
/// Construct a new map for the digraph and initalise the values. |
| 1119 | 1124 |
ArcMap(const MappableDigraphComponent& digraph, const _Value& value) |
| 1120 | 1125 |
: Parent(digraph, value) {}
|
| 1121 | 1126 |
|
| 1127 |
private: |
|
| 1122 | 1128 |
/// \brief Copy constructor. |
| 1123 | 1129 |
/// |
| 1124 | 1130 |
/// Copy Constructor. |
| 1125 | 1131 |
ArcMap(const ArcMap& nm) : Parent(nm) {}
|
| 1126 | 1132 |
|
| 1127 | 1133 |
/// \brief Assign operator. |
| 1128 | 1134 |
/// |
| 1129 | 1135 |
/// Assign operator. |
| 1130 | 1136 |
template <typename CMap> |
| 1131 | 1137 |
ArcMap& operator=(const CMap&) {
|
| 1132 | 1138 |
checkConcept<ReadMap<Arc, _Value>, CMap>(); |
| 1133 | 1139 |
return *this; |
| 1134 | 1140 |
} |
| 1135 | 1141 |
|
| 1136 | 1142 |
}; |
| 1137 | 1143 |
|
| 1138 | 1144 |
|
| 1139 | 1145 |
template <typename _Digraph> |
| 1140 | 1146 |
struct Constraints {
|
| 1141 | 1147 |
|
| 1142 | 1148 |
struct Dummy {
|
| 1143 | 1149 |
int value; |
| 1144 | 1150 |
Dummy() : value(0) {}
|
| 1145 | 1151 |
Dummy(int _v) : value(_v) {}
|
| 1146 | 1152 |
}; |
| 1147 | 1153 |
|
| 1148 | 1154 |
void constraints() {
|
| 1149 | 1155 |
checkConcept<Base, _Digraph>(); |
| 1150 | 1156 |
{ // int map test
|
| 1151 | 1157 |
typedef typename _Digraph::template NodeMap<int> IntNodeMap; |
| 1152 | 1158 |
checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>, |
| 1153 | 1159 |
IntNodeMap >(); |
| 1154 | 1160 |
} { // bool map test
|
| 1155 | 1161 |
typedef typename _Digraph::template NodeMap<bool> BoolNodeMap; |
| 1156 | 1162 |
checkConcept<GraphMap<_Digraph, typename _Digraph::Node, bool>, |
| 1157 | 1163 |
BoolNodeMap >(); |
| 1158 | 1164 |
} { // Dummy map test
|
| 1159 | 1165 |
typedef typename _Digraph::template NodeMap<Dummy> DummyNodeMap; |
| 1160 | 1166 |
checkConcept<GraphMap<_Digraph, typename _Digraph::Node, Dummy>, |
| 1161 | 1167 |
DummyNodeMap >(); |
| 1162 | 1168 |
} |
| 1163 | 1169 |
|
| 1164 | 1170 |
{ // int map test
|
| 1165 | 1171 |
typedef typename _Digraph::template ArcMap<int> IntArcMap; |
| 1166 | 1172 |
checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>, |
| 1167 | 1173 |
IntArcMap >(); |
| 1168 | 1174 |
} { // bool map test
|
| 1169 | 1175 |
typedef typename _Digraph::template ArcMap<bool> BoolArcMap; |
| 1170 | 1176 |
checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>, |
| 1171 | 1177 |
BoolArcMap >(); |
| 1172 | 1178 |
} { // Dummy map test
|
| 1173 | 1179 |
typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap; |
| 1174 | 1180 |
checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>, |
| 1175 | 1181 |
DummyArcMap >(); |
| 1176 | 1182 |
} |
| 1177 | 1183 |
} |
| 1178 | 1184 |
|
| 1179 | 1185 |
_Digraph& digraph; |
| 1180 | 1186 |
}; |
| 1181 | 1187 |
}; |
| 1182 | 1188 |
|
| 1183 | 1189 |
/// \brief An empty mappable base bipartite graph class. |
| 1184 | 1190 |
/// |
| 1185 | 1191 |
/// This class provides beside the core graph features |
| 1186 | 1192 |
/// map interface for the graph structure. |
| 1187 | 1193 |
/// This concept is part of the Graph concept. |
| 1188 | 1194 |
template <typename _Base = BaseGraphComponent> |
| 1189 | 1195 |
class MappableGraphComponent : public MappableDigraphComponent<_Base> {
|
| 1190 | 1196 |
public: |
| 1191 | 1197 |
|
| 1192 | 1198 |
typedef _Base Base; |
| 1193 | 1199 |
typedef typename Base::Edge Edge; |
| 1194 | 1200 |
|
| 1195 | 1201 |
typedef MappableGraphComponent Graph; |
| 1196 | 1202 |
|
| 1197 | 1203 |
/// \brief ReadWrite map of the edges. |
| 1198 | 1204 |
/// |
| 1199 | 1205 |
/// ReadWrite map of the edges. |
| 1200 | 1206 |
/// |
| 1201 | 1207 |
template <typename _Value> |
| 1202 | 1208 |
class EdgeMap : public GraphMap<Graph, Edge, _Value> {
|
| 1203 | 1209 |
public: |
| 1204 | 1210 |
typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent; |
| 1205 | 1211 |
|
| 1206 | 1212 |
/// \brief Construct a new map. |
| 1207 | 1213 |
/// |
| 1208 | 1214 |
/// Construct a new map for the graph. |
| 1209 | 1215 |
explicit EdgeMap(const MappableGraphComponent& graph) |
| 1210 | 1216 |
: Parent(graph) {}
|
| 1211 | 1217 |
|
| 1212 | 1218 |
/// \brief Construct a new map with default value. |
| 1213 | 1219 |
/// |
| 1214 | 1220 |
/// Construct a new map for the graph and initalise the values. |
| 1215 | 1221 |
EdgeMap(const MappableGraphComponent& graph, const _Value& value) |
| 1216 | 1222 |
: Parent(graph, value) {}
|
| 1217 | 1223 |
|
| 1224 |
private: |
|
| 1218 | 1225 |
/// \brief Copy constructor. |
| 1219 | 1226 |
/// |
| 1220 | 1227 |
/// Copy Constructor. |
| 1221 | 1228 |
EdgeMap(const EdgeMap& nm) : Parent(nm) {}
|
| 1222 | 1229 |
|
| 1223 | 1230 |
/// \brief Assign operator. |
| 1224 | 1231 |
/// |
| 1225 | 1232 |
/// Assign operator. |
| 1226 | 1233 |
template <typename CMap> |
| 1227 | 1234 |
EdgeMap& operator=(const CMap&) {
|
| 1228 | 1235 |
checkConcept<ReadMap<Edge, _Value>, CMap>(); |
| 1229 | 1236 |
return *this; |
| 1230 | 1237 |
} |
| 1231 | 1238 |
|
| 1232 | 1239 |
}; |
| 1233 | 1240 |
|
| 1234 | 1241 |
|
| 1235 | 1242 |
template <typename _Graph> |
| 1236 | 1243 |
struct Constraints {
|
| 1237 | 1244 |
|
| 1238 | 1245 |
struct Dummy {
|
| 1239 | 1246 |
int value; |
| 1240 | 1247 |
Dummy() : value(0) {}
|
| 1241 | 1248 |
Dummy(int _v) : value(_v) {}
|
| 1242 | 1249 |
}; |
| 1243 | 1250 |
|
| 1244 | 1251 |
void constraints() {
|
| 1245 | 1252 |
checkConcept<MappableGraphComponent<Base>, _Graph>(); |
| 1246 | 1253 |
|
| 1247 | 1254 |
{ // int map test
|
| 1248 | 1255 |
typedef typename _Graph::template EdgeMap<int> IntEdgeMap; |
| 1249 | 1256 |
checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>, |
| 1250 | 1257 |
IntEdgeMap >(); |
| 1251 | 1258 |
} { // bool map test
|
| 1252 | 1259 |
typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap; |
| 1253 | 1260 |
checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>, |
| 1254 | 1261 |
BoolEdgeMap >(); |
| 1255 | 1262 |
} { // Dummy map test
|
| 1256 | 1263 |
typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap; |
| 1257 | 1264 |
checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>, |
| 1258 | 1265 |
DummyEdgeMap >(); |
| 1259 | 1266 |
} |
| 1260 | 1267 |
} |
| 1261 | 1268 |
|
| 1262 | 1269 |
_Graph& graph; |
| 1263 | 1270 |
}; |
| 1264 | 1271 |
}; |
| 1265 | 1272 |
|
| 1266 | 1273 |
/// \brief An empty extendable digraph class. |
| 1267 | 1274 |
/// |
| 1268 | 1275 |
/// This class provides beside the core digraph features digraph |
| 1269 | 1276 |
/// extendable interface for the digraph structure. The main |
| 1270 | 1277 |
/// difference between the base and this interface is that the |
| 1271 | 1278 |
/// digraph alterations should handled already on this level. |
| 1272 | 1279 |
template <typename _Base = BaseDigraphComponent> |
| 1273 | 1280 |
class ExtendableDigraphComponent : public _Base {
|
| 1274 | 1281 |
public: |
| 1275 | 1282 |
typedef _Base Base; |
| 1276 | 1283 |
|
| 1277 | 1284 |
typedef typename _Base::Node Node; |
| 1278 | 1285 |
typedef typename _Base::Arc Arc; |
| 1279 | 1286 |
|
| 1280 | 1287 |
/// \brief Adds a new node to the digraph. |
| 1281 | 1288 |
/// |
| 1282 | 1289 |
/// Adds a new node to the digraph. |
| 1283 | 1290 |
/// |
| 1284 | 1291 |
Node addNode() {
|
| 1285 | 1292 |
return INVALID; |
| 1286 | 1293 |
} |
| 1287 | 1294 |
|
| 1288 | 1295 |
/// \brief Adds a new arc connects the given two nodes. |
| 1289 | 1296 |
/// |
| 1290 | 1297 |
/// Adds a new arc connects the the given two nodes. |
| 1291 | 1298 |
Arc addArc(const Node&, const Node&) {
|
| 1292 | 1299 |
return INVALID; |
| 1293 | 1300 |
} |
| 1294 | 1301 |
|
| 1295 | 1302 |
template <typename _Digraph> |
| 1296 | 1303 |
struct Constraints {
|
| 1297 | 1304 |
void constraints() {
|
| 1298 | 1305 |
checkConcept<Base, _Digraph>(); |
| 1299 | 1306 |
typename _Digraph::Node node_a, node_b; |
| 1300 | 1307 |
node_a = digraph.addNode(); |
| 1301 | 1308 |
node_b = digraph.addNode(); |
| 1302 | 1309 |
typename _Digraph::Arc arc; |
| 1303 | 1310 |
arc = digraph.addArc(node_a, node_b); |
| 1304 | 1311 |
} |
| 1305 | 1312 |
|
| 1306 | 1313 |
_Digraph& digraph; |
| 1307 | 1314 |
}; |
| 1308 | 1315 |
}; |
| 1309 | 1316 |
|
| 1310 | 1317 |
/// \brief An empty extendable base undirected graph class. |
| 1311 | 1318 |
/// |
| 1312 | 1319 |
/// This class provides beside the core undirected graph features |
| 1313 | 1320 |
/// core undircted graph extend interface for the graph structure. |
| 1 | 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
| 2 | 2 |
* |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 | 5 |
* Copyright (C) 2003-2008 |
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
#include <iostream> |
| 20 | 20 |
|
| 21 | 21 |
#include <lemon/error.h> |
| 22 | 22 |
#include "test_tools.h" |
| 23 | 23 |
|
| 24 | 24 |
using namespace lemon; |
| 25 | 25 |
|
| 26 | 26 |
#ifdef LEMON_ENABLE_ASSERTS |
| 27 | 27 |
#undef LEMON_ENABLE_ASSERTS |
| 28 | 28 |
#endif |
| 29 | 29 |
|
| 30 | 30 |
#ifdef LEMON_DISABLE_ASSERTS |
| 31 | 31 |
#undef LEMON_DISABLE_ASSERTS |
| 32 | 32 |
#endif |
| 33 | 33 |
|
| 34 | 34 |
#ifdef NDEBUG |
| 35 | 35 |
#undef NDEBUG |
| 36 | 36 |
#endif |
| 37 | 37 |
|
| 38 | 38 |
//checking disabled asserts |
| 39 | 39 |
#define LEMON_DISABLE_ASSERTS |
| 40 | 40 |
#include <lemon/assert.h> |
| 41 | 41 |
|
| 42 | 42 |
void no_assertion_text_disable() {
|
| 43 | 43 |
LEMON_ASSERT(true, "This is a fault message"); |
| 44 | 44 |
} |
| 45 | 45 |
|
| 46 | 46 |
void assertion_text_disable() {
|
| 47 | 47 |
LEMON_ASSERT(false, "This is a fault message"); |
| 48 | 48 |
} |
| 49 | 49 |
|
| 50 |
void fixme_disable() {
|
|
| 51 |
LEMON_FIXME("fixme_disable() is fixme!");
|
|
| 52 |
} |
|
| 53 |
|
|
| 54 | 50 |
void check_assertion_disable() {
|
| 55 | 51 |
no_assertion_text_disable(); |
| 56 | 52 |
assertion_text_disable(); |
| 57 |
fixme_disable(); |
|
| 58 | 53 |
} |
| 59 | 54 |
#undef LEMON_DISABLE_ASSERTS |
| 60 | 55 |
|
| 61 | 56 |
//checking custom assert handler |
| 62 | 57 |
#define LEMON_ASSERT_CUSTOM |
| 63 | 58 |
|
| 64 | 59 |
static int cnt = 0; |
| 65 | 60 |
void my_assert_handler(const char*, int, const char*, |
| 66 | 61 |
const char*, const char*) {
|
| 67 | 62 |
++cnt; |
| 68 | 63 |
} |
| 69 | 64 |
|
| 70 | 65 |
#define LEMON_CUSTOM_ASSERT_HANDLER my_assert_handler |
| 71 | 66 |
#include <lemon/assert.h> |
| 72 | 67 |
|
| 73 | 68 |
void no_assertion_text_custom() {
|
| 74 | 69 |
LEMON_ASSERT(true, "This is a fault message"); |
| 75 | 70 |
} |
| 76 | 71 |
|
| 77 | 72 |
void assertion_text_custom() {
|
| 78 | 73 |
LEMON_ASSERT(false, "This is a fault message"); |
| 79 | 74 |
} |
| 80 | 75 |
|
| 81 |
void fixme_custom() {
|
|
| 82 |
LEMON_FIXME("fixme_custom() is fixme!");
|
|
| 83 |
} |
|
| 84 |
|
|
| 85 | 76 |
void check_assertion_custom() {
|
| 86 | 77 |
no_assertion_text_custom(); |
| 87 | 78 |
assertion_text_custom(); |
| 88 |
fixme_custom(); |
|
| 89 |
check(cnt == 2, "The custom assert handler does not work"); |
|
| 79 |
check(cnt == 1, "The custom assert handler does not work"); |
|
| 90 | 80 |
} |
| 91 | 81 |
|
| 92 | 82 |
#undef LEMON_ASSERT_CUSTOM |
| 93 | 83 |
|
| 94 | 84 |
|
| 95 | 85 |
int main() {
|
| 96 | 86 |
check_assertion_disable(); |
| 97 | 87 |
check_assertion_custom(); |
| 98 | 88 |
|
| 99 | 89 |
return 0; |
| 100 | 90 |
} |
| ... | ... |
@@ -119,166 +119,166 @@ |
| 119 | 119 |
template <class Graph> |
| 120 | 120 |
void checkGraphConArcList(const Graph &G, int cnt) {
|
| 121 | 121 |
int i = 0; |
| 122 | 122 |
for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
|
| 123 | 123 |
for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
|
| 124 | 124 |
for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) {
|
| 125 | 125 |
check(G.source(a) == u, "Wrong iterator."); |
| 126 | 126 |
check(G.target(a) == v, "Wrong iterator."); |
| 127 | 127 |
++i; |
| 128 | 128 |
} |
| 129 | 129 |
} |
| 130 | 130 |
} |
| 131 | 131 |
check(cnt == i, "Wrong iterator."); |
| 132 | 132 |
} |
| 133 | 133 |
|
| 134 | 134 |
template <class Graph> |
| 135 | 135 |
void checkGraphConEdgeList(const Graph &G, int cnt) {
|
| 136 | 136 |
int i = 0; |
| 137 | 137 |
for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
|
| 138 | 138 |
for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
|
| 139 | 139 |
for (ConEdgeIt<Graph> e(G, u, v); e != INVALID; ++e) {
|
| 140 | 140 |
check((G.u(e) == u && G.v(e) == v) || |
| 141 | 141 |
(G.u(e) == v && G.v(e) == u), "Wrong iterator."); |
| 142 | 142 |
i += u == v ? 2 : 1; |
| 143 | 143 |
} |
| 144 | 144 |
} |
| 145 | 145 |
} |
| 146 | 146 |
check(2 * cnt == i, "Wrong iterator."); |
| 147 | 147 |
} |
| 148 | 148 |
|
| 149 | 149 |
template <typename Graph> |
| 150 | 150 |
void checkArcDirections(const Graph& G) {
|
| 151 | 151 |
for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
|
| 152 | 152 |
check(G.source(a) == G.target(G.oppositeArc(a)), "Wrong direction"); |
| 153 | 153 |
check(G.target(a) == G.source(G.oppositeArc(a)), "Wrong direction"); |
| 154 | 154 |
check(G.direct(a, G.direction(a)) == a, "Wrong direction"); |
| 155 | 155 |
} |
| 156 | 156 |
} |
| 157 | 157 |
|
| 158 | 158 |
template <typename Graph> |
| 159 | 159 |
void checkNodeIds(const Graph& G) {
|
| 160 | 160 |
std::set<int> values; |
| 161 | 161 |
for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
|
| 162 | 162 |
check(G.nodeFromId(G.id(n)) == n, "Wrong id"); |
| 163 | 163 |
check(values.find(G.id(n)) == values.end(), "Wrong id"); |
| 164 | 164 |
check(G.id(n) <= G.maxNodeId(), "Wrong maximum id"); |
| 165 | 165 |
values.insert(G.id(n)); |
| 166 | 166 |
} |
| 167 | 167 |
} |
| 168 | 168 |
|
| 169 | 169 |
template <typename Graph> |
| 170 | 170 |
void checkArcIds(const Graph& G) {
|
| 171 | 171 |
std::set<int> values; |
| 172 | 172 |
for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
|
| 173 | 173 |
check(G.arcFromId(G.id(a)) == a, "Wrong id"); |
| 174 | 174 |
check(values.find(G.id(a)) == values.end(), "Wrong id"); |
| 175 | 175 |
check(G.id(a) <= G.maxArcId(), "Wrong maximum id"); |
| 176 | 176 |
values.insert(G.id(a)); |
| 177 | 177 |
} |
| 178 | 178 |
} |
| 179 | 179 |
|
| 180 | 180 |
template <typename Graph> |
| 181 | 181 |
void checkEdgeIds(const Graph& G) {
|
| 182 | 182 |
std::set<int> values; |
| 183 | 183 |
for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
|
| 184 | 184 |
check(G.edgeFromId(G.id(e)) == e, "Wrong id"); |
| 185 | 185 |
check(values.find(G.id(e)) == values.end(), "Wrong id"); |
| 186 | 186 |
check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id"); |
| 187 | 187 |
values.insert(G.id(e)); |
| 188 | 188 |
} |
| 189 | 189 |
} |
| 190 | 190 |
|
| 191 | 191 |
template <typename Graph> |
| 192 | 192 |
void checkGraphNodeMap(const Graph& G) {
|
| 193 | 193 |
typedef typename Graph::Node Node; |
| 194 | 194 |
typedef typename Graph::NodeIt NodeIt; |
| 195 | 195 |
|
| 196 | 196 |
typedef typename Graph::template NodeMap<int> IntNodeMap; |
| 197 | 197 |
IntNodeMap map(G, 42); |
| 198 | 198 |
for (NodeIt it(G); it != INVALID; ++it) {
|
| 199 | 199 |
check(map[it] == 42, "Wrong map constructor."); |
| 200 | 200 |
} |
| 201 | 201 |
int s = 0; |
| 202 | 202 |
for (NodeIt it(G); it != INVALID; ++it) {
|
| 203 | 203 |
map[it] = 0; |
| 204 | 204 |
check(map[it] == 0, "Wrong operator[]."); |
| 205 | 205 |
map.set(it, s); |
| 206 | 206 |
check(map[it] == s, "Wrong set."); |
| 207 | 207 |
++s; |
| 208 | 208 |
} |
| 209 | 209 |
s = s * (s - 1) / 2; |
| 210 | 210 |
for (NodeIt it(G); it != INVALID; ++it) {
|
| 211 | 211 |
s -= map[it]; |
| 212 | 212 |
} |
| 213 | 213 |
check(s == 0, "Wrong sum."); |
| 214 | 214 |
|
| 215 |
map = constMap<Node>(12); |
|
| 216 |
for (NodeIt it(G); it != INVALID; ++it) {
|
|
| 217 |
check(map[it] == 12, "Wrong operator[]."); |
|
| 218 |
} |
|
| 215 |
// map = constMap<Node>(12); |
|
| 216 |
// for (NodeIt it(G); it != INVALID; ++it) {
|
|
| 217 |
// check(map[it] == 12, "Wrong operator[]."); |
|
| 218 |
// } |
|
| 219 | 219 |
} |
| 220 | 220 |
|
| 221 | 221 |
template <typename Graph> |
| 222 | 222 |
void checkGraphArcMap(const Graph& G) {
|
| 223 | 223 |
typedef typename Graph::Arc Arc; |
| 224 | 224 |
typedef typename Graph::ArcIt ArcIt; |
| 225 | 225 |
|
| 226 | 226 |
typedef typename Graph::template ArcMap<int> IntArcMap; |
| 227 | 227 |
IntArcMap map(G, 42); |
| 228 | 228 |
for (ArcIt it(G); it != INVALID; ++it) {
|
| 229 | 229 |
check(map[it] == 42, "Wrong map constructor."); |
| 230 | 230 |
} |
| 231 | 231 |
int s = 0; |
| 232 | 232 |
for (ArcIt it(G); it != INVALID; ++it) {
|
| 233 | 233 |
map[it] = 0; |
| 234 | 234 |
check(map[it] == 0, "Wrong operator[]."); |
| 235 | 235 |
map.set(it, s); |
| 236 | 236 |
check(map[it] == s, "Wrong set."); |
| 237 | 237 |
++s; |
| 238 | 238 |
} |
| 239 | 239 |
s = s * (s - 1) / 2; |
| 240 | 240 |
for (ArcIt it(G); it != INVALID; ++it) {
|
| 241 | 241 |
s -= map[it]; |
| 242 | 242 |
} |
| 243 | 243 |
check(s == 0, "Wrong sum."); |
| 244 | 244 |
|
| 245 |
map = constMap<Arc>(12); |
|
| 246 |
for (ArcIt it(G); it != INVALID; ++it) {
|
|
| 247 |
check(map[it] == 12, "Wrong operator[]."); |
|
| 248 |
} |
|
| 245 |
// map = constMap<Arc>(12); |
|
| 246 |
// for (ArcIt it(G); it != INVALID; ++it) {
|
|
| 247 |
// check(map[it] == 12, "Wrong operator[]."); |
|
| 248 |
// } |
|
| 249 | 249 |
} |
| 250 | 250 |
|
| 251 | 251 |
template <typename Graph> |
| 252 | 252 |
void checkGraphEdgeMap(const Graph& G) {
|
| 253 | 253 |
typedef typename Graph::Edge Edge; |
| 254 | 254 |
typedef typename Graph::EdgeIt EdgeIt; |
| 255 | 255 |
|
| 256 | 256 |
typedef typename Graph::template EdgeMap<int> IntEdgeMap; |
| 257 | 257 |
IntEdgeMap map(G, 42); |
| 258 | 258 |
for (EdgeIt it(G); it != INVALID; ++it) {
|
| 259 | 259 |
check(map[it] == 42, "Wrong map constructor."); |
| 260 | 260 |
} |
| 261 | 261 |
int s = 0; |
| 262 | 262 |
for (EdgeIt it(G); it != INVALID; ++it) {
|
| 263 | 263 |
map[it] = 0; |
| 264 | 264 |
check(map[it] == 0, "Wrong operator[]."); |
| 265 | 265 |
map.set(it, s); |
| 266 | 266 |
check(map[it] == s, "Wrong set."); |
| 267 | 267 |
++s; |
| 268 | 268 |
} |
| 269 | 269 |
s = s * (s - 1) / 2; |
| 270 | 270 |
for (EdgeIt it(G); it != INVALID; ++it) {
|
| 271 | 271 |
s -= map[it]; |
| 272 | 272 |
} |
| 273 | 273 |
check(s == 0, "Wrong sum."); |
| 274 | 274 |
|
| 275 |
map = constMap<Edge>(12); |
|
| 276 |
for (EdgeIt it(G); it != INVALID; ++it) {
|
|
| 277 |
check(map[it] == 12, "Wrong operator[]."); |
|
| 278 |
} |
|
| 275 |
// map = constMap<Edge>(12); |
|
| 276 |
// for (EdgeIt it(G); it != INVALID; ++it) {
|
|
| 277 |
// check(map[it] == 12, "Wrong operator[]."); |
|
| 278 |
// } |
|
| 279 | 279 |
} |
| 280 | 280 |
|
| 281 | 281 |
|
| 282 | 282 |
} //namespace lemon |
| 283 | 283 |
|
| 284 | 284 |
#endif |
0 comments (0 inline)