COIN-OR::LEMON - Graph Library

Changes in / [1064:fc3854d936f7:1065:490d89913a17] in lemon-main


Ignore:
Files:
15 added
2 deleted
42 edited

Legend:

Unmodified
Added
Removed
  • doc/CMakeLists.txt

    r983 r1053  
    55
    66SET(LEMON_DOC_SOURCE_BROWSER "NO" CACHE STRING "Include source into the doc (YES/NO).")
     7SET(LEMON_DOC_USE_MATHJAX "NO" CACHE STRING "Use MathJax to display math formulae (YES/NO).")
     8SET(LEMON_DOC_MATHJAX_RELPATH "http://www.mathjax.org/mathjax" CACHE STRING "MathJax library location.")
    79
    810CONFIGURE_FILE(
     
    3335    COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images
    3436    COMMAND ${CMAKE_COMMAND} -E make_directory gen-images
    35     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
    36     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
    37     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
    38     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
    39     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
    40     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
    41     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
    42     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
    43     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
    44     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
    45     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
    46     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
    47     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
    48     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
     37    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r20 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
     38    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/adaptors2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/adaptors2.eps
     39    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
     40    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
     41    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
     42    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
     43    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
     44    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
     45    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
     46    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r40 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
     47    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.eps
     48    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
     49    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
     50    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
     51    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
     52    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
    4953    COMMAND ${CMAKE_COMMAND} -E remove_directory html
    50     COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
    5154    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    5255    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
     
    7376IF(WGET_FOUND)
    7477ADD_CUSTOM_TARGET(update-external-tags
    75   COMMAND ${CMAKE_COMMAND} -E make_directory dl
    76   # COMMAND ${CMAKE_COMMAND} -E copy libstdc++.tag dl
    77   COMMAND ${WGET_EXECUTABLE} wget -P dl -N libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag
    78   COMMAND ${CMAKE_COMMAND} -E rename dl/libstdc++.tag libstdc++.tag
    79   COMMAND ${CMAKE_COMMAND} -E remove dl/libstdc++.tag
    80   COMMAND ${CMAKE_COMMAND} -E remove_directory dl
     78  COMMAND ${WGET_EXECUTABLE} -N http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag
    8179  WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
    8280  )
  • doc/Doxyfile.in

    r966 r1053  
    7878FILE_VERSION_FILTER    =
    7979LAYOUT_FILE            = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
     80CITE_BIB_FILES         = "@abs_top_srcdir@/doc/references.bib"
    8081#---------------------------------------------------------------------------
    8182# configuration options related to warning and progress messages
     
    183184FORMULA_FONTSIZE       = 10
    184185FORMULA_TRANSPARENT    = YES
    185 USE_MATHJAX            = NO
    186 MATHJAX_RELPATH        = http://www.mathjax.org/mathjax
     186USE_MATHJAX            = @LEMON_DOC_USE_MATHJAX@
     187MATHJAX_RELPATH        = @LEMON_DOC_MATHJAX_RELPATH@
    187188SEARCHENGINE           = YES
    188189SERVER_BASED_SEARCH    = NO
  • doc/groups.dox

    r1003 r1053  
    113113detailed documentation of particular adaptors.
    114114
     115Since the adaptor classes conform to the \ref graph_concepts "graph concepts",
     116an adaptor can even be applied to another one.
     117The following image illustrates a situation when a \ref SubDigraph adaptor
     118is applied on a digraph and \ref Undirector is applied on the subgraph.
     119
     120\image html adaptors2.png
     121\image latex adaptors2.eps "Using graph adaptors" width=\textwidth
     122
    115123The behavior of graph adaptors can be very different. Some of them keep
    116124capabilities of the original graph while in other cases this would be
     
    310318This group contains the common graph search algorithms, namely
    311319\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
    312 \ref clrs01algorithms.
     320\cite clrs01algorithms.
    313321*/
    314322
     
    319327
    320328This group contains the algorithms for finding shortest paths in digraphs
    321 \ref clrs01algorithms.
     329\cite clrs01algorithms.
    322330
    323331 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    341349
    342350This group contains the algorithms for finding minimum cost spanning
    343 trees and arborescences \ref clrs01algorithms.
     351trees and arborescences \cite clrs01algorithms.
    344352*/
    345353
     
    350358
    351359This group contains the algorithms for finding maximum flows and
    352 feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
     360feasible circulations \cite clrs01algorithms, \cite amo93networkflows.
    353361
    354362The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    366374LEMON contains several algorithms for solving maximum flow problems:
    367375- \ref EdmondsKarp Edmonds-Karp algorithm
    368   \ref edmondskarp72theoretical.
     376  \cite edmondskarp72theoretical.
    369377- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
    370   \ref goldberg88newapproach.
     378  \cite goldberg88newapproach.
    371379- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
    372   \ref dinic70algorithm, \ref sleator83dynamic.
     380  \cite dinic70algorithm, \cite sleator83dynamic.
    373381- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
    374   \ref goldberg88newapproach, \ref sleator83dynamic.
     382  \cite goldberg88newapproach, \cite sleator83dynamic.
    375383
    376384In most cases the \ref Preflow algorithm provides the
     
    392400
    393401This group contains the algorithms for finding minimum cost flows and
    394 circulations \ref amo93networkflows. For more information about this
    395 problem and its dual solution, see \ref min_cost_flow
     402circulations \cite amo93networkflows. For more information about this
     403problem and its dual solution, see: \ref min_cost_flow
    396404"Minimum Cost Flow Problem".
    397405
    398406LEMON contains several algorithms for this problem.
    399407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    400    pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
     408   pivot strategies \cite dantzig63linearprog, \cite kellyoneill91netsimplex.
    401409 - \ref CostScaling Cost Scaling algorithm based on push/augment and
    402    relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
    403    \ref bunnagel98efficient.
     410   relabel operations \cite goldberg90approximation, \cite goldberg97efficient,
     411   \cite bunnagel98efficient.
    404412 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
    405    shortest path method \ref edmondskarp72theoretical.
     413   shortest path method \cite edmondskarp72theoretical.
    406414 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
    407    strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
     415   strongly polynomial \cite klein67primal, \cite goldberg89cyclecanceling.
    408416
    409417In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
     
    421429which is capable of handling real-valued arc costs (other numerical
    422430data are required to be integer).
     431
     432For more details about these implementations and for a comprehensive
     433experimental study, see the paper \cite KiralyKovacs12MCF.
     434It also compares these codes to other publicly available
     435minimum cost flow solvers.
    423436*/
    424437
     
    459472
    460473This group contains the algorithms for finding minimum mean cycles
    461 \ref amo93networkflows, \ref karp78characterization.
     474\cite amo93networkflows, \cite karp78characterization.
    462475
    463476The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     
    475488
    476489LEMON contains three algorithms for solving the minimum mean cycle problem:
    477 - \ref KarpMmc Karp's original algorithm \ref karp78characterization.
     490- \ref KarpMmc Karp's original algorithm \cite karp78characterization.
    478491- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
    479   version of Karp's algorithm \ref hartmann93finding.
     492  version of Karp's algorithm \cite hartmann93finding.
    480493- \ref HowardMmc Howard's policy iteration algorithm
    481   \ref dasdan98minmeancycle, \ref dasdan04experimental.
     494  \cite dasdan98minmeancycle, \cite dasdan04experimental.
    482495
    483496In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
     
    485498time is exponential.
    486499Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
    487 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
    488 typically faster due to the applied early termination scheme.
     500run in time O(ne) and use space O(n<sup>2</sup>+e).
    489501*/
    490502
     
    559571\image latex planar.eps "Plane graph" width=\textwidth
    560572*/
     573 
     574/**
     575@defgroup tsp Traveling Salesman Problem
     576@ingroup algs
     577\brief Algorithms for the symmetric traveling salesman problem
     578
     579This group contains basic heuristic algorithms for the the symmetric
     580\e traveling \e salesman \e problem (TSP).
     581Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
     582the problem is to find a shortest possible tour that visits each node exactly
     583once (i.e. the minimum cost Hamiltonian cycle).
     584
     585These TSP algorithms are intended to be used with a \e metric \e cost
     586\e function, i.e. the edge costs should satisfy the triangle inequality.
     587Otherwise the algorithms could yield worse results.
     588
     589LEMON provides five well-known heuristics for solving symmetric TSP:
     590 - \ref NearestNeighborTsp Neareast neighbor algorithm
     591 - \ref GreedyTsp Greedy algorithm
     592 - \ref InsertionTsp Insertion heuristic (with four selection methods)
     593 - \ref ChristofidesTsp Christofides algorithm
     594 - \ref Opt2Tsp 2-opt algorithm
     595
     596\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
     597solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
     598
     599\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
     600approximation factor: 3/2.
     601
     602\ref Opt2Tsp usually provides the best results in practice, but
     603it is the slowest method. It can also be used to improve given tours,
     604for example, the results of other algorithms.
     605
     606\image html tsp.png
     607\image latex tsp.eps "Traveling salesman problem" width=\textwidth
     608*/
    561609
    562610/**
     
    600648high-level interface.
    601649
    602 The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
    603 \ref cplex, \ref soplex.
     650The currently supported solvers are \cite glpk, \cite clp, \cite cbc,
     651\cite cplex, \cite soplex.
    604652*/
    605653
     
    688736This group contains general \c EPS drawing methods and special
    689737graph exporting tools.
     738
     739\image html graph_to_eps.png
    690740*/
    691741
  • doc/images/bipartite_partitions.eps

    r587 r1045  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Tue Nov 15 16:51:43 2005
     3%%CreationDate: Fri Mar  8 00:18:43 2013
    44%%BoundingBox: 0 0 842 596
    55%%EndComments
     
    5454%Edges:
    5555gsave
    56 513.857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 2 lb
    57 513.857 -446.322 575.52 -315.655 637.183 -184.989 0 0 0 2 lb
    58 393.468 566.711 494.771 434.577 596.074 302.442 0 0 0 2 lb
    59 393.468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 2 lb
    60 393.468 566.711 251.056 450.726 108.644 334.741 0 0 0 2 lb
    61 869.153 52.8539 732.613 177.648 596.074 302.442 0 0 0 2 lb
    62 869.153 52.8539 753.168 -66.0676 637.183 -184.989 0 0 0 2 lb
    63 -82.2171 593.138 -91.0261 346.487 -99.8351 99.8351 0 0 0 2 lb
    64 -663.61 546.157 -753.168 394.936 -842.726 243.715 0 0 0 2 lb
    65 -663.61 546.157 -574.052 437.513 -484.494 328.869 0 0 0 2 lb
    66 -1077.63 161.498 -960.178 202.606 -842.726 243.715 0 0 0 2 lb
    67 -1077.63 161.498 -968.987 66.0674 -860.344 -29.3633 0 0 0 2 lb
    68 -1177.47 -234.906 -1029.18 -381.722 -880.898 -528.539 0 0 0 2 lb
    69 -1177.47 -234.906 -1018.91 -132.135 -860.344 -29.3633 0 0 0 2 lb
    70 -880.898 -528.539 -744.359 -387.595 -607.82 -246.651 0 0 0 2 lb
    71 -499.175 -499.175 -355.295 -475.685 -211.415 -452.194 0 0 0 2 lb
    72 -499.175 -499.175 -553.498 -372.913 -607.82 -246.651 0 0 0 2 lb
    73 -499.175 -499.175 -386.587 -315.087 -274 -131 0 0 0 2 lb
    74 79.2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 2 lb
    75 637.183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 2 lb
    76 205.543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 2 lb
    77 399.34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 2 lb
    78 399.34 88.0898 253.992 211.415 108.644 334.741 0 0 0 2 lb
    79 -842.726 243.715 -471.281 171.775 -99.8351 99.8351 0 0 0 2 lb
    80 -842.726 243.715 -558.363 56.3575 -274 -131 0 0 0 2 lb
    81 -860.344 -29.3633 -734.082 -138.007 -607.82 -246.651 0 0 0 2 lb
    82 -211.415 -452.194 -45.513 -290.696 120.389 -129.198 0 0 0 2 lb
    83 -99.8351 99.8351 4.40445 217.288 108.644 334.741 0 0 0 2 lb
    84 -99.8351 99.8351 -292.165 214.352 -484.494 328.869 0 0 0 2 lb
    85 120.389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 2 lb
     56513.857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 7.00153 lb
     57513.857 -446.322 575.52 -315.656 637.183 -184.989 0 0 0 7.00153 lb
     58393.468 566.711 494.771 434.577 596.074 302.442 0 0 0 7.00153 lb
     59393.468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 7.00153 lb
     60393.468 566.711 251.056 450.726 108.644 334.741 0 0 0 7.00153 lb
     61869.153 52.8539 732.613 177.648 596.074 302.442 0 0 0 7.00153 lb
     62869.153 52.8539 753.168 -66.0676 637.183 -184.989 0 0 0 7.00153 lb
     63-82.2171 593.138 -91.0261 346.487 -99.8351 99.8351 0 0 0 7.00153 lb
     64-663.61 546.157 -753.168 394.936 -842.726 243.715 0 0 0 7.00153 lb
     65-663.61 546.157 -574.052 437.513 -484.494 328.869 0 0 0 7.00153 lb
     66-1077.63 161.498 -960.178 202.606 -842.726 243.715 0 0 0 7.00153 lb
     67-1077.63 161.498 -968.987 66.0674 -860.344 -29.3633 0 0 0 7.00153 lb
     68-1177.47 -234.906 -1029.18 -381.722 -880.898 -528.539 0 0 0 7.00153 lb
     69-1177.47 -234.906 -1018.91 -132.135 -860.344 -29.3633 0 0 0 7.00153 lb
     70-880.898 -528.539 -744.359 -387.595 -607.82 -246.651 0 0 0 7.00153 lb
     71-499.175 -499.175 -355.295 -475.685 -211.415 -452.194 0 0 0 7.00153 lb
     72-499.175 -499.175 -553.498 -372.913 -607.82 -246.651 0 0 0 7.00153 lb
     73-499.175 -499.175 -386.587 -315.087 -274 -131 0 0 0 7.00153 lb
     7479.2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 7.00153 lb
     75637.183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 7.00153 lb
     76205.543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 7.00153 lb
     77399.34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 7.00153 lb
     78399.34 88.0898 253.992 211.415 108.644 334.741 0 0 0 7.00153 lb
     79-842.726 243.715 -471.281 171.775 -99.8351 99.8351 0 0 0 7.00153 lb
     80-842.726 243.715 -558.363 56.3575 -274 -131 0 0 0 7.00153 lb
     81-860.344 -29.3633 -734.082 -138.007 -607.82 -246.651 0 0 0 7.00153 lb
     82-211.415 -452.194 -45.513 -290.696 120.389 -129.198 0 0 0 7.00153 lb
     83-99.8351 99.8351 4.40445 217.288 108.644 334.741 0 0 0 7.00153 lb
     84-99.8351 99.8351 -292.165 214.352 -484.494 328.869 0 0 0 7.00153 lb
     85120.389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 7.00153 lb
    8686grestore
    8787%Nodes:
    8888gsave
    89 -274 -131 20 1 0 0 nc
    90 -607.82 -246.651 20 1 0 0 nc
    91 -484.494 328.869 20 0 0 1 nc
    92 108.644 334.741 20 0 0 1 nc
    93 120.389 -129.198 20 0 0 1 nc
    94 -99.8351 99.8351 20 1 0 0 nc
    95 -211.415 -452.194 20 1 0 0 nc
    96 -860.344 -29.3633 20 0 0 1 nc
    97 -842.726 243.715 20 0 0 1 nc
    98 399.34 88.0898 20 1 0 0 nc
    99 205.543 -322.996 20 1 0 0 nc
    100 637.183 -184.989 20 0 0 1 nc
    101 79.2808 -528.539 20 0 0 1 nc
    102 -499.175 -499.175 20 0 0 1 nc
    103 -880.898 -528.539 20 0 0 1 nc
    104 -1177.47 -234.906 20 1 0 0 nc
    105 -1077.63 161.498 20 1 0 0 nc
    106 -663.61 546.157 20 1 0 0 nc
    107 -82.2171 593.138 20 0 0 1 nc
    108 596.074 302.442 20 0 0 1 nc
    109 869.153 52.8539 20 1 0 0 nc
    110 393.468 566.711 20 1 0 0 nc
    111 513.857 -446.322 20 1 0 0 nc
     89-274 -131 23.3384 1 0 0 nc
     90-607.82 -246.651 23.3384 1 0 0 nc
     91-484.494 328.869 23.3384 0 0 1 nc
     92108.644 334.741 23.3384 0 0 1 nc
     93120.389 -129.198 23.3384 0 0 1 nc
     94-99.8351 99.8351 23.3384 1 0 0 nc
     95-211.415 -452.194 23.3384 1 0 0 nc
     96-860.344 -29.3633 23.3384 0 0 1 nc
     97-842.726 243.715 23.3384 0 0 1 nc
     98399.34 88.0898 23.3384 1 0 0 nc
     99205.543 -322.996 23.3384 1 0 0 nc
     100637.183 -184.989 23.3384 0 0 1 nc
     10179.2808 -528.539 23.3384 0 0 1 nc
     102-499.175 -499.175 23.3384 0 0 1 nc
     103-880.898 -528.539 23.3384 0 0 1 nc
     104-1177.47 -234.906 23.3384 1 0 0 nc
     105-1077.63 161.498 23.3384 1 0 0 nc
     106-663.61 546.157 23.3384 1 0 0 nc
     107-82.2171 593.138 23.3384 0 0 1 nc
     108596.074 302.442 23.3384 0 0 1 nc
     109869.153 52.8539 23.3384 1 0 0 nc
     110393.468 566.711 23.3384 1 0 0 nc
     111513.857 -446.322 23.3384 1 0 0 nc
    112112grestore
    113113grestore
  • doc/images/connected_components.eps

    r587 r1045  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Fri Nov  4 13:47:12 2005
     3%%CreationDate: Fri Mar  8 00:18:43 2013
    44%%BoundingBox: 0 0 842 596
    55%%EndComments
     
    5454%Edges:
    5555gsave
    56 574.035 177.301 622.149 225.748 670.264 274.195 0 0 0 2 lb
    57 694.579 115.483 682.421 194.839 670.264 274.195 0 0 0 2 lb
    58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 0 2 lb
    59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 0 2 lb
    60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 0 2 lb
    61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 0 2 lb
    62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 0 2 lb
    63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 0 2 lb
    64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 0 2 lb
    65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 0 2 lb
    66 366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 0 2 lb
    67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 0 2 lb
    68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 0 2 lb
    69 277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 0 2 lb
    70 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0 0 2 lb
    71 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0 2 lb
    72 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0 2 lb
    73 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0 2 lb
    74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0 0 2 lb
    75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 0 2 lb
    76 986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 0 2 lb
    77 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0 0 0 2 lb
    78 422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 0 2 lb
    79 422.945 521.129 376.371 417.911 329.797 314.692 0 0 0 2 lb
    80 422.945 521.129 474.554 276.928 526.164 32.7279 0 0 0 2 lb
    81 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 0 2 lb
    82 329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 0 2 lb
    83 -67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 0 2 lb
    84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 0 2 lb
    85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 0 2 lb
    86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 0 2 lb
    87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 0 2 lb
    88 415.393 -289.516 173.71 -318.468 -67.9734 -347.42 0 0 0 2 lb
    89 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 0 2 lb
    90 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 0 2 lb
    91 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 0 2 lb
    92 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 0 2 lb
    93 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 0 2 lb
    94 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 0 2 lb
    95 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 0 2 lb
    96 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 0 2 lb
    97 116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 0 2 lb
    98 -262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 0 2 lb
    99 -262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 0 2 lb
    100 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 0 2 lb
    101 -180.397 245.045 -142.256 345.099 -132.697 451.748 0 0 0 2 lb
    102 -180.397 245.045 -170.838 351.694 -132.697 451.748 0 0 0 2 lb
    103 -416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 0 2 lb
    104 -416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 0 2 lb
    105 -132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 0 2 lb
    106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 0 2 lb
    107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 0 2 lb
    108 588.113 544.499 756.39 476.923 924.667 409.347 0 0 0 2 lb
    109 -689.204 -237.261 -614.799 -102.648 -567.302 43.6423 0 0 0 2 lb
    110 -689.204 -237.261 -641.707 -90.9706 -567.302 43.6423 0 0 0 2 lb
     56574.035 177.301 622.149 225.748 670.264 274.195 0 0 0 6.25356 lb
     57694.579 115.483 682.421 194.839 670.264 274.195 0 0 0 6.25356 lb
     58280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 0 6.25356 lb
     59280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 0 6.25356 lb
     60212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 0 6.25356 lb
     61286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 0 6.25356 lb
     62286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 0 6.25356 lb
     63438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 0 6.25356 lb
     64438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 0 6.25356 lb
     65397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 0 6.25356 lb
     66366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 0 6.25356 lb
     67271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 0 6.25356 lb
     68271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 0 6.25356 lb
     69277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 0 6.25356 lb
     70-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0 0 6.25356 lb
     71-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0 6.25356 lb
     72-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0 6.25356 lb
     73-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0 6.25356 lb
     74906.312 201.403 946.592 42.798 986.873 -115.807 0 0 0 6.25356 lb
     75906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 0 6.25356 lb
     76986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 0 6.25356 lb
     77-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0 0 0 6.25356 lb
     78422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 0 6.25356 lb
     79422.945 521.129 376.371 417.911 329.797 314.692 0 0 0 6.25356 lb
     80422.945 521.129 474.554 276.928 526.164 32.7279 0 0 0 6.25356 lb
     81-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 0 6.25356 lb
     82329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 0 6.25356 lb
     83-67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 0 6.25356 lb
     84762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 0 6.25356 lb
     85762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 0 6.25356 lb
     86526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 0 6.25356 lb
     87730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 0 6.25356 lb
     88415.393 -289.516 173.71 -318.468 -67.9734 -347.42 0 0 0 6.25356 lb
     89-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 0 6.25356 lb
     90-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 0 6.25356 lb
     91-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 0 6.25356 lb
     92-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 0 6.25356 lb
     93-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 0 6.25356 lb
     94-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 0 6.25356 lb
     95-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 0 6.25356 lb
     96-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 0 6.25356 lb
     97116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 0 6.25356 lb
     98-262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 0 6.25356 lb
     99-262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 0 6.25356 lb
     100-13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 0 6.25356 lb
     101-180.397 245.045 -113.509 338.465 -132.697 451.748 0 0 0 6.25356 lb
     102-180.397 245.045 -199.585 358.328 -132.697 451.748 0 0 0 6.25356 lb
     103-416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 0 6.25356 lb
     104-416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 0 6.25356 lb
     105-132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 0 6.25356 lb
     106670.264 274.195 629.188 409.347 588.113 544.499 0 0 0 6.25356 lb
     107670.264 274.195 797.466 341.771 924.667 409.347 0 0 0 6.25356 lb
     108588.113 544.499 756.39 476.923 924.667 409.347 0 0 0 6.25356 lb
     109-689.204 -237.261 -587.735 -114.393 -567.302 43.6423 0 0 0 6.25356 lb
     110-689.204 -237.261 -668.771 -79.2259 -567.302 43.6423 0 0 0 6.25356 lb
    111111grestore
    112112%Nodes:
    113113gsave
    114 -567.302 43.6423 20 0 0 0 nc
    115 -689.204 -237.261 20 0 0 0 nc
    116 924.667 409.347 20 1 0 0 nc
    117 588.113 544.499 20 1 0 0 nc
    118 670.264 274.195 20 1 0 0 nc
    119 -371.2 568.349 20 0 1 0 nc
    120 -132.697 451.748 20 0 1 0 nc
    121 -416.25 345.746 20 0 1 0 nc
    122 -180.397 245.045 20 0 1 0 nc
    123 -13.4452 133.743 20 0 1 0 nc
    124 -262.548 107.243 20 0 1 0 nc
    125 201.208 38.3422 20 0 1 0 nc
    126 116.407 -173.66 20 0 1 0 nc
    127 -26.6953 -19.9585 20 0 1 0 nc
    128 -539.894 -262.64 20 0 0 1 nc
    129 -323.543 -433.964 20 0 0 1 nc
    130 -309.657 -57.9033 20 0 0 1 nc
    131 -67.9734 -347.42 20 0 0 1 nc
    132 415.393 -289.516 20 0 0 1 nc
    133 730.084 -307.139 20 0 0 1 nc
    134 526.164 32.7279 20 0 0 1 nc
    135 762.812 -17.6227 20 0 0 1 nc
    136 -67.9734 319.727 20 0 0 1 nc
    137 329.797 314.692 20 0 0 1 nc
    138 -5.03507 561.41 20 0 0 1 nc
    139 422.945 521.129 20 0 0 1 nc
    140 -470.779 158.605 20 0 0 1 nc
    141 986.873 -115.807 20 0 0 1 nc
    142 906.312 201.403 20 0 0 1 nc
    143 -767.847 113.289 20 0 0 1 nc
    144 -579.033 445.603 20 0 0 1 nc
    145 -840.856 -246.718 20 0 0 1 nc
    146 206.221 -205.967 20 1 1 0 nc
    147 277.311 -252.33 20 1 1 0 nc
    148 271.13 -175.058 20 1 1 0 nc
    149 366.947 -110.15 20 1 1 0 nc
    150 397.855 -196.694 20 1 1 0 nc
    151 438.037 -88.514 20 1 1 0 nc
    152 286.584 -48.3327 20 1 1 0 nc
    153 212.403 -23.6057 20 1 1 0 nc
    154 280.402 10.3938 20 1 1 0 nc
    155 694.579 115.483 20 1 0 0 nc
    156 574.035 177.301 20 1 0 0 nc
     114-567.302 43.6423 20.8452 0 0 0 nc
     115-689.204 -237.261 20.8452 0 0 0 nc
     116924.667 409.347 20.8452 1 0 0 nc
     117588.113 544.499 20.8452 1 0 0 nc
     118670.264 274.195 20.8452 1 0 0 nc
     119-371.2 568.349 20.8452 0 1 0 nc
     120-132.697 451.748 20.8452 0 1 0 nc
     121-416.25 345.746 20.8452 0 1 0 nc
     122-180.397 245.045 20.8452 0 1 0 nc
     123-13.4452 133.743 20.8452 0 1 0 nc
     124-262.548 107.243 20.8452 0 1 0 nc
     125201.208 38.3422 20.8452 0 1 0 nc
     126116.407 -173.66 20.8452 0 1 0 nc
     127-26.6953 -19.9585 20.8452 0 1 0 nc
     128-539.894 -262.64 20.8452 0 0 1 nc
     129-323.543 -433.964 20.8452 0 0 1 nc
     130-309.657 -57.9033 20.8452 0 0 1 nc
     131-67.9734 -347.42 20.8452 0 0 1 nc
     132415.393 -289.516 20.8452 0 0 1 nc
     133730.084 -307.139 20.8452 0 0 1 nc
     134526.164 32.7279 20.8452 0 0 1 nc
     135762.812 -17.6227 20.8452 0 0 1 nc
     136-67.9734 319.727 20.8452 0 0 1 nc
     137329.797 314.692 20.8452 0 0 1 nc
     138-5.03507 561.41 20.8452 0 0 1 nc
     139422.945 521.129 20.8452 0 0 1 nc
     140-470.779 158.605 20.8452 0 0 1 nc
     141986.873 -115.807 20.8452 0 0 1 nc
     142906.312 201.403 20.8452 0 0 1 nc
     143-767.847 113.289 20.8452 0 0 1 nc
     144-579.033 445.603 20.8452 0 0 1 nc
     145-840.856 -246.718 20.8452 0 0 1 nc
     146206.221 -205.967 20.8452 1 1 0 nc
     147277.311 -252.33 20.8452 1 1 0 nc
     148271.13 -175.058 20.8452 1 1 0 nc
     149366.947 -110.15 20.8452 1 1 0 nc
     150397.855 -196.694 20.8452 1 1 0 nc
     151438.037 -88.514 20.8452 1 1 0 nc
     152286.584 -48.3327 20.8452 1 1 0 nc
     153212.403 -23.6057 20.8452 1 1 0 nc
     154280.402 10.3938 20.8452 1 1 0 nc
     155694.579 115.483 20.8452 1 0 0 nc
     156574.035 177.301 20.8452 1 0 0 nc
    157157grestore
    158158grestore
  • doc/images/edge_biconnected_components.eps

    r587 r1045  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Fri Nov  4 13:47:12 2005
     3%%CreationDate: Fri Mar  8 00:18:43 2013
    44%%BoundingBox: 0 0 842 596
    55%%EndComments
     
    5454%Edges:
    5555gsave
    56 574.035 177.301 622.149 225.748 670.264 274.195 1 0 0 2 lb
    57 694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 2 lb
    58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 2 lb
    59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 2 lb
    60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 2 lb
    61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 2 lb
    62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 2 lb
    63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 2 lb
    64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 2 lb
    65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 2 lb
    66 366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 2 lb
    67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 2 lb
    68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 2 lb
    69 277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 1 2 lb
    70 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 1 0 0 2 lb
    71 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 1 2 lb
    72 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 1 2 lb
    73 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 1 2 lb
    74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0 1 2 lb
    75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 2 lb
    76 986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 1 2 lb
    77 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 1 0 0 2 lb
    78 422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 2 lb
    79 422.945 521.129 376.371 417.911 329.797 314.692 0 0 1 2 lb
    80 422.945 521.129 474.554 276.928 526.164 32.7279 0 0 1 2 lb
    81 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 1 2 lb
    82 329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 1 2 lb
    83 -67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 1 2 lb
    84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 2 lb
    85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 2 lb
    86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 2 lb
    87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 2 lb
    88 415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0 0 2 lb
    89 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 1 2 lb
    90 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 1 2 lb
    91 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 1 2 lb
    92 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 1 2 lb
    93 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 1 2 lb
    94 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 1 2 lb
    95 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 1 2 lb
    96 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 1 2 lb
    97 116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 1 2 lb
    98 -262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 1 2 lb
    99 -262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 1 2 lb
    100 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 1 2 lb
    101 -180.397 245.045 -142.256 345.099 -132.697 451.748 0 0 1 2 lb
    102 -180.397 245.045 -170.838 351.694 -132.697 451.748 0 0 1 2 lb
    103 -416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 1 2 lb
    104 -416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 1 2 lb
    105 -132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 1 2 lb
    106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 2 lb
    107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 2 lb
    108 588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 2 lb
    109 -689.204 -237.261 -614.799 -102.648 -567.302 43.6423 0 0 1 2 lb
    110 -689.204 -237.261 -641.707 -90.9706 -567.302 43.6423 0 0 1 2 lb
     56574.035 177.301 622.149 225.748 670.264 274.195 1 0 0 6.25356 lb
     57694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 6.25356 lb
     58280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 6.25356 lb
     59280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 6.25356 lb
     60212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 6.25356 lb
     61286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 6.25356 lb
     62286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 6.25356 lb
     63438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 6.25356 lb
     64438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 6.25356 lb
     65397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 6.25356 lb
     66366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 6.25356 lb
     67271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 6.25356 lb
     68271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 6.25356 lb
     69277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 1 6.25356 lb
     70-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 1 0 0 6.25356 lb
     71-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 1 6.25356 lb
     72-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 1 6.25356 lb
     73-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 1 6.25356 lb
     74906.312 201.403 946.592 42.798 986.873 -115.807 0 0 1 6.25356 lb
     75906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 6.25356 lb
     76986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 1 6.25356 lb
     77-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 1 0 0 6.25356 lb
     78422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 6.25356 lb
     79422.945 521.129 376.371 417.911 329.797 314.692 0 0 1 6.25356 lb
     80422.945 521.129 474.554 276.928 526.164 32.7279 0 0 1 6.25356 lb
     81-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 1 6.25356 lb
     82329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 1 6.25356 lb
     83-67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 1 6.25356 lb
     84762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 6.25356 lb
     85762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 6.25356 lb
     86526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 6.25356 lb
     87730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 6.25356 lb
     88415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0 0 6.25356 lb
     89-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 1 6.25356 lb
     90-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 1 6.25356 lb
     91-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 1 6.25356 lb
     92-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 1 6.25356 lb
     93-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 1 6.25356 lb
     94-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 1 6.25356 lb
     95-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 1 6.25356 lb
     96-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 1 6.25356 lb
     97116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 1 6.25356 lb
     98-262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 1 6.25356 lb
     99-262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 1 6.25356 lb
     100-13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 1 6.25356 lb
     101-180.397 245.045 -113.509 338.465 -132.697 451.748 0 0 1 6.25356 lb
     102-180.397 245.045 -199.585 358.328 -132.697 451.748 0 0 1 6.25356 lb
     103-416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 1 6.25356 lb
     104-416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 1 6.25356 lb
     105-132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 1 6.25356 lb
     106670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 6.25356 lb
     107670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 6.25356 lb
     108588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 6.25356 lb
     109-689.204 -237.261 -587.735 -114.393 -567.302 43.6423 0 0 1 6.25356 lb
     110-689.204 -237.261 -668.771 -79.2259 -567.302 43.6423 0 0 1 6.25356 lb
    111111grestore
    112112%Nodes:
    113113gsave
    114 -567.302 43.6423 20 0 0 0 nc
    115 -689.204 -237.261 20 0 0 0 nc
    116 924.667 409.347 20 0 0 1 nc
    117 588.113 544.499 20 0 0 1 nc
    118 670.264 274.195 20 0 0 1 nc
    119 -371.2 568.349 20 1 1 0 nc
    120 -132.697 451.748 20 1 1 0 nc
    121 -416.25 345.746 20 1 1 0 nc
    122 -180.397 245.045 20 1 1 0 nc
    123 -13.4452 133.743 20 1 1 0 nc
    124 -262.548 107.243 20 1 1 0 nc
    125 201.208 38.3422 20 1 1 0 nc
    126 116.407 -173.66 20 1 1 0 nc
    127 -26.6953 -19.9585 20 1 1 0 nc
    128 -539.894 -262.64 20 0 0.5 0 nc
    129 -323.543 -433.964 20 0 0.5 0 nc
    130 -309.657 -57.9033 20 0 0.5 0 nc
    131 -67.9734 -347.42 20 0 0.5 0 nc
    132 415.393 -289.516 20 0.5 0 0 nc
    133 730.084 -307.139 20 0.5 0 0 nc
    134 526.164 32.7279 20 0.5 0 0 nc
    135 762.812 -17.6227 20 0.5 0 0 nc
    136 -67.9734 319.727 20 0.5 0 0 nc
    137 329.797 314.692 20 0.5 0 0 nc
    138 -5.03507 561.41 20 0.5 0 0 nc
    139 422.945 521.129 20 0.5 0 0 nc
    140 -470.779 158.605 20 0 1 1 nc
    141 986.873 -115.807 20 0.5 0 0 nc
    142 906.312 201.403 20 0.5 0 0 nc
    143 -767.847 113.289 20 0 1 1 nc
    144 -579.033 445.603 20 0 1 1 nc
    145 -840.856 -246.718 20 1 0 1 nc
    146 206.221 -205.967 20 0 0 0.5 nc
    147 277.311 -252.33 20 0 0 0.5 nc
    148 271.13 -175.058 20 0 0 0.5 nc
    149 366.947 -110.15 20 0 0 0.5 nc
    150 397.855 -196.694 20 0 0 0.5 nc
    151 438.037 -88.514 20 0 0 0.5 nc
    152 286.584 -48.3327 20 0 0 0.5 nc
    153 212.403 -23.6057 20 0 0 0.5 nc
    154 280.402 10.3938 20 0 0 0.5 nc
    155 694.579 115.483 20 1 0 0 nc
    156 574.035 177.301 20 0 1 0 nc
     114-567.302 43.6423 20.8452 0 0 0 nc
     115-689.204 -237.261 20.8452 0 0 0 nc
     116924.667 409.347 20.8452 0 0 1 nc
     117588.113 544.499 20.8452 0 0 1 nc
     118670.264 274.195 20.8452 0 0 1 nc
     119-371.2 568.349 20.8452 1 1 0 nc
     120-132.697 451.748 20.8452 1 1 0 nc
     121-416.25 345.746 20.8452 1 1 0 nc
     122-180.397 245.045 20.8452 1 1 0 nc
     123-13.4452 133.743 20.8452 1 1 0 nc
     124-262.548 107.243 20.8452 1 1 0 nc
     125201.208 38.3422 20.8452 1 1 0 nc
     126116.407 -173.66 20.8452 1 1 0 nc
     127-26.6953 -19.9585 20.8452 1 1 0 nc
     128-539.894 -262.64 20.8452 0 0.5 0 nc
     129-323.543 -433.964 20.8452 0 0.5 0 nc
     130-309.657 -57.9033 20.8452 0 0.5 0 nc
     131-67.9734 -347.42 20.8452 0 0.5 0 nc
     132415.393 -289.516 20.8452 0.5 0 0 nc
     133730.084 -307.139 20.8452 0.5 0 0 nc
     134526.164 32.7279 20.8452 0.5 0 0 nc
     135762.812 -17.6227 20.8452 0.5 0 0 nc
     136-67.9734 319.727 20.8452 0.5 0 0 nc
     137329.797 314.692 20.8452 0.5 0 0 nc
     138-5.03507 561.41 20.8452 0.5 0 0 nc
     139422.945 521.129 20.8452 0.5 0 0 nc
     140-470.779 158.605 20.8452 0 1 1 nc
     141986.873 -115.807 20.8452 0.5 0 0 nc
     142906.312 201.403 20.8452 0.5 0 0 nc
     143-767.847 113.289 20.8452 0 1 1 nc
     144-579.033 445.603 20.8452 0 1 1 nc
     145-840.856 -246.718 20.8452 1 0 1 nc
     146206.221 -205.967 20.8452 0 0 0.5 nc
     147277.311 -252.33 20.8452 0 0 0.5 nc
     148271.13 -175.058 20.8452 0 0 0.5 nc
     149366.947 -110.15 20.8452 0 0 0.5 nc
     150397.855 -196.694 20.8452 0 0 0.5 nc
     151438.037 -88.514 20.8452 0 0 0.5 nc
     152286.584 -48.3327 20.8452 0 0 0.5 nc
     153212.403 -23.6057 20.8452 0 0 0.5 nc
     154280.402 10.3938 20.8452 0 0 0.5 nc
     155694.579 115.483 20.8452 1 0 0 nc
     156574.035 177.301 20.8452 0 1 0 nc
    157157grestore
    158158grestore
  • doc/images/node_biconnected_components.eps

    r587 r1045  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Fri Nov  4 13:47:12 2005
     3%%CreationDate: Fri Mar  8 00:18:43 2013
    44%%BoundingBox: 0 0 842 596
    55%%EndComments
     
    5454%Edges:
    5555gsave
    56 574.035 177.301 622.149 225.748 670.264 274.195 0 1 0 5 lb
    57 694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 5 lb
    58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 5 lb
    59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 5 lb
    60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 5 lb
    61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 5 lb
    62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 5 lb
    63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 5 lb
    64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 5 lb
    65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 5 lb
    66 366.947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 5 lb
    67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 5 lb
    68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 5 lb
    69 277.311 -252.33 241.766 -229.149 206.221 -205.967 0.5 1 1 5 lb
    70 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0.5 0 5 lb
    71 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0.5 5 lb
    72 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0.5 5 lb
    73 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0.5 5 lb
    74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 5 lb
    75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 5 lb
    76 986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0.5 0.5 5 lb
    77 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0.5 0.5 0 5 lb
    78 422.945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 5 lb
    79 422.945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 5 lb
    80 422.945 521.129 474.554 276.928 526.164 32.7279 0.5 0 0.5 5 lb
    81 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0.5 0 0.5 5 lb
    82 329.797 314.692 130.912 317.209 -67.9734 319.727 0.5 0 0.5 5 lb
    83 -67.9734 319.727 229.095 176.227 526.164 32.7279 0.5 0 0.5 5 lb
    84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 5 lb
    85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 5 lb
    86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 5 lb
    87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 5 lb
    88 415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0.5 0.5 5 lb
    89 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0.5 1 0.5 5 lb
    90 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0.5 1 0.5 5 lb
    91 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0.5 1 0.5 5 lb
    92 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0.5 1 0.5 5 lb
    93 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 1 1 0 5 lb
    94 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 1 1 0 5 lb
    95 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 1 0 1 5 lb
    96 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 1 0 1 5 lb
    97 116.407 -173.66 158.808 -67.6589 201.208 38.3422 1 1 0 5 lb
    98 -262.548 107.243 -137.997 120.493 -13.4452 133.743 1 0 1 5 lb
    99 -262.548 107.243 -221.472 176.144 -180.397 245.045 1 0 1 5 lb
    100 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 1 0 1 5 lb
    101 -180.397 245.045 -140.307 344.649 -132.697 451.748 0 1 1 5 lb
    102 -180.397 245.045 -172.787 352.144 -132.697 451.748 0 1 1 5 lb
    103 -416.25 345.746 -274.474 398.747 -132.697 451.748 0.5 0 0 5 lb
    104 -416.25 345.746 -393.725 457.048 -371.2 568.349 0.5 0 0 5 lb
    105 -132.697 451.748 -251.948 510.048 -371.2 568.349 0.5 0 0 5 lb
    106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 5 lb
    107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 5 lb
    108 588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 5 lb
    109 -689.204 -237.261 -612.964 -103.444 -567.302 43.6423 0 0 0 5 lb
    110 -689.204 -237.261 -643.542 -90.1744 -567.302 43.6423 0 0 0 5 lb
     56574.035 177.301 622.149 225.748 670.264 274.195 0 1 0 6.25356 lb
     57694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 6.25356 lb
     58280.402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 6.25356 lb
     59280.402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 6.25356 lb
     60212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 6.25356 lb
     61286.584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 6.25356 lb
     62286.584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 6.25356 lb
     63438.037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 6.25356 lb
     64438.037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 6.25356 lb
     65397.855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 6.25356 lb
     66366.947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 6.25356 lb
     67271.13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 6.25356 lb
     68271.13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 6.25356 lb
     69277.311 -252.33 241.766 -229.149 206.221 -205.967 0.5 1 1 6.25356 lb
     70-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0.5 0 6.25356 lb
     71-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0.5 6.25356 lb
     72-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0.5 6.25356 lb
     73-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0.5 6.25356 lb
     74906.312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 6.25356 lb
     75906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 6.25356 lb
     76986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0.5 0.5 6.25356 lb
     77-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0.5 0.5 0 6.25356 lb
     78422.945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 6.25356 lb
     79422.945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 6.25356 lb
     80422.945 521.129 474.554 276.928 526.164 32.7279 0.5 0 0.5 6.25356 lb
     81-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0.5 0 0.5 6.25356 lb
     82329.797 314.692 130.912 317.209 -67.9734 319.727 0.5 0 0.5 6.25356 lb
     83-67.9734 319.727 229.095 176.227 526.164 32.7279 0.5 0 0.5 6.25356 lb
     84762.812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 6.25356 lb
     85762.812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 6.25356 lb
     86526.164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 6.25356 lb
     87730.084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 6.25356 lb
     88415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0.5 0.5 6.25356 lb
     89-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0.5 1 0.5 6.25356 lb
     90-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0.5 1 0.5 6.25356 lb
     91-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0.5 1 0.5 6.25356 lb
     92-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0.5 1 0.5 6.25356 lb
     93-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 1 1 0 6.25356 lb
     94-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 1 1 0 6.25356 lb
     95-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 1 0 1 6.25356 lb
     96-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 1 0 1 6.25356 lb
     97116.407 -173.66 158.808 -67.6589 201.208 38.3422 1 1 0 6.25356 lb
     98-262.548 107.243 -137.997 120.493 -13.4452 133.743 1 0 1 6.25356 lb
     99-262.548 107.243 -221.472 176.144 -180.397 245.045 1 0 1 6.25356 lb
     100-13.4452 133.743 -96.9211 189.394 -180.397 245.045 1 0 1 6.25356 lb
     101-180.397 245.045 -113.509 338.465 -132.697 451.748 0 1 1 6.25356 lb
     102-180.397 245.045 -199.585 358.328 -132.697 451.748 0 1 1 6.25356 lb
     103-416.25 345.746 -274.474 398.747 -132.697 451.748 0.5 0 0 6.25356 lb
     104-416.25 345.746 -393.725 457.048 -371.2 568.349 0.5 0 0 6.25356 lb
     105-132.697 451.748 -251.948 510.048 -371.2 568.349 0.5 0 0 6.25356 lb
     106670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 6.25356 lb
     107670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 6.25356 lb
     108588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 6.25356 lb
     109-689.204 -237.261 -587.735 -114.393 -567.302 43.6423 0 0 0 6.25356 lb
     110-689.204 -237.261 -668.771 -79.2259 -567.302 43.6423 0 0 0 6.25356 lb
    111111grestore
    112112%Nodes:
    113113gsave
    114 -567.302 43.6423 20 0 0 1 nc
    115 -689.204 -237.261 20 0 0 1 nc
    116 924.667 409.347 20 0 0 1 nc
    117 588.113 544.499 20 0 0 1 nc
    118 670.264 274.195 20 1 0 0 nc
    119 -371.2 568.349 20 0 0 1 nc
    120 -132.697 451.748 20 1 0 0 nc
    121 -416.25 345.746 20 0 0 1 nc
    122 -180.397 245.045 20 1 0 0 nc
    123 -13.4452 133.743 20 0 0 1 nc
    124 -262.548 107.243 20 0 0 1 nc
    125 201.208 38.3422 20 0 0 1 nc
    126 116.407 -173.66 20 0 0 1 nc
    127 -26.6953 -19.9585 20 1 0 0 nc
    128 -539.894 -262.64 20 0 0 1 nc
    129 -323.543 -433.964 20 0 0 1 nc
    130 -309.657 -57.9033 20 1 0 0 nc
    131 -67.9734 -347.42 20 1 0 0 nc
    132 415.393 -289.516 20 1 0 0 nc
    133 730.084 -307.139 20 0 0 1 nc
    134 526.164 32.7279 20 1 0 0 nc
    135 762.812 -17.6227 20 1 0 0 nc
    136 -67.9734 319.727 20 0 0 1 nc
    137 329.797 314.692 20 0 0 1 nc
    138 -5.03507 561.41 20 0 0 1 nc
    139 422.945 521.129 20 0 0 1 nc
    140 -470.779 158.605 20 1 0 0 nc
    141 986.873 -115.807 20 0 0 1 nc
    142 906.312 201.403 20 0 0 1 nc
    143 -767.847 113.289 20 1 0 0 nc
    144 -579.033 445.603 20 0 0 1 nc
    145 -840.856 -246.718 20 0 0 1 nc
    146 206.221 -205.967 20 0 0 1 nc
    147 277.311 -252.33 20 0 0 1 nc
    148 271.13 -175.058 20 1 0 0 nc
    149 366.947 -110.15 20 1 0 0 nc
    150 397.855 -196.694 20 0 0 1 nc
    151 438.037 -88.514 20 0 0 1 nc
    152 286.584 -48.3327 20 1 0 0 nc
    153 212.403 -23.6057 20 0 0 1 nc
    154 280.402 10.3938 20 0 0 1 nc
    155 694.579 115.483 20 0 0 1 nc
    156 574.035 177.301 20 0 0 1 nc
     114-567.302 43.6423 20.8452 0 0 1 nc
     115-689.204 -237.261 20.8452 0 0 1 nc
     116924.667 409.347 20.8452 0 0 1 nc
     117588.113 544.499 20.8452 0 0 1 nc
     118670.264 274.195 20.8452 1 0 0 nc
     119-371.2 568.349 20.8452 0 0 1 nc
     120-132.697 451.748 20.8452 1 0 0 nc
     121-416.25 345.746 20.8452 0 0 1 nc
     122-180.397 245.045 20.8452 1 0 0 nc
     123-13.4452 133.743 20.8452 0 0 1 nc
     124-262.548 107.243 20.8452 0 0 1 nc
     125201.208 38.3422 20.8452 0 0 1 nc
     126116.407 -173.66 20.8452 0 0 1 nc
     127-26.6953 -19.9585 20.8452 1 0 0 nc
     128-539.894 -262.64 20.8452 0 0 1 nc
     129-323.543 -433.964 20.8452 0 0 1 nc
     130-309.657 -57.9033 20.8452 1 0 0 nc
     131-67.9734 -347.42 20.8452 1 0 0 nc
     132415.393 -289.516 20.8452 1 0 0 nc
     133730.084 -307.139 20.8452 0 0 1 nc
     134526.164 32.7279 20.8452 1 0 0 nc
     135762.812 -17.6227 20.8452 1 0 0 nc
     136-67.9734 319.727 20.8452 0 0 1 nc
     137329.797 314.692 20.8452 0 0 1 nc
     138-5.03507 561.41 20.8452 0 0 1 nc
     139422.945 521.129 20.8452 0 0 1 nc
     140-470.779 158.605 20.8452 1 0 0 nc
     141986.873 -115.807 20.8452 0 0 1 nc
     142906.312 201.403 20.8452 0 0 1 nc
     143-767.847 113.289 20.8452 1 0 0 nc
     144-579.033 445.603 20.8452 0 0 1 nc
     145-840.856 -246.718 20.8452 0 0 1 nc
     146206.221 -205.967 20.8452 0 0 1 nc
     147277.311 -252.33 20.8452 0 0 1 nc
     148271.13 -175.058 20.8452 1 0 0 nc
     149366.947 -110.15 20.8452 1 0 0 nc
     150397.855 -196.694 20.8452 0 0 1 nc
     151438.037 -88.514 20.8452 0 0 1 nc
     152286.584 -48.3327 20.8452 1 0 0 nc
     153212.403 -23.6057 20.8452 0 0 1 nc
     154280.402 10.3938 20.8452 0 0 1 nc
     155694.579 115.483 20.8452 0 0 1 nc
     156574.035 177.301 20.8452 0 0 1 nc
    157157grestore
    158158grestore
  • doc/images/strongly_connected_components.eps

    r587 r1045  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Fri Nov  4 13:47:12 2005
     3%%CreationDate: Fri Mar  8 00:22:15 2013
    44%%BoundingBox: 0 0 842 596
    55%%EndComments
     
    5454%Edges:
    5555gsave
    56 2 setlinewidth 0 0 1 setrgbcolor newpath
     564.56973 setlinewidth 0 0 1 setrgbcolor newpath
    5757218.178 27.2723 moveto
    58 192.373 -40.1551 188.622 -49.9556 169.228 -100.631 curveto stroke
    59 newpath 164.939 -111.838 moveto 165.492 -99.2013 lineto 172.964 -102.061 lineto closepath fill
    60 2 setlinewidth 0 0 1 setrgbcolor newpath
     58195.849 -31.0725 190.033 -46.2697 176.306 -82.1369 curveto stroke
     59newpath 163.235 -116.291 moveto 165.206 -77.8889 lineto 187.405 -86.3849 lineto closepath fill
     604.56973 setlinewidth 0 0 1 setrgbcolor newpath
    616144.8044 15.5841 moveto
    62 119.293 20.6059 129.775 21.3125 186.25 25.1199 curveto stroke
    63 newpath 198.223 25.927 moveto 186.519 21.1289 lineto 185.981 29.1108 lineto closepath fill
    64 2 setlinewidth 1 0 0 setrgbcolor newpath
     62109.705 19.9594 126.016 21.0591 166.493 23.7879 curveto stroke
     63newpath 202.98 26.2477 moveto 167.292 11.9299 lineto 165.694 35.6458 lineto closepath fill
     644.56973 setlinewidth 1 0 0 setrgbcolor newpath
    6565218.178 27.2723 moveto
    66 285.395 -87.4449 290.763 -96.6058 348.102 -194.464 curveto stroke
    67 newpath 354.169 -204.818 moveto 344.651 -196.487 lineto 351.554 -192.442 lineto closepath fill
    68 2 setlinewidth 0 0 1 setrgbcolor newpath
     66281.264 -80.3935 289.87 -95.0808 338.092 -177.379 curveto stroke
     67newpath 356.579 -208.932 moveto 327.837 -183.388 lineto 348.346 -171.371 lineto closepath fill
     684.56973 setlinewidth 0 0 1 setrgbcolor newpath
    6969157.79 -130.517 moveto
    70 108.71 -67.0521 102.27 -58.7243 64.3804 -9.72954 curveto stroke
    71 newpath 57.0394 -0.236898 moveto 67.5446 -7.28254 lineto 61.2162 -12.1765 lineto closepath fill
    72 2 setlinewidth 1 0 0 setrgbcolor newpath
     70114.446 -74.4692 104.358 -61.4239 76.4943 -25.394 curveto stroke
     71newpath 54.1228 3.53455 moveto 85.8959 -18.1234 lineto 67.0928 -32.6646 lineto closepath fill
     724.56973 setlinewidth 1 0 0 setrgbcolor newpath
    7373-105.193 -261.035 moveto
    74 -35.6576 -132.801 -30.5923 -123.459 29.5506 -12.5464 curveto stroke
    75 newpath 35.2708 -1.99743 moveto 33.0669 -14.4531 lineto 26.0343 -10.6397 lineto closepath fill
    76 2 setlinewidth 0 0 1 setrgbcolor newpath
     74-39.4801 -139.85 -31.344 -124.846 20.1113 -29.9539 curveto stroke
     75newpath 37.5434 2.19358 moveto 30.559 -35.6192 lineto 9.66361 -24.2886 lineto closepath fill
     764.56973 setlinewidth 0 0 1 setrgbcolor newpath
    7777-465.576 -42.8564 moveto
    78 -559.078 -25.5413 -569.47 -23.6169 -644.498 -9.72286 curveto stroke
    79 newpath -656.297 -7.5378 moveto -643.77 -5.78973 lineto -645.226 -13.656 lineto closepath fill
    80 2 setlinewidth 0 0 1 setrgbcolor newpath
     78-550.335 -27.1603 -566.8 -24.1113 -625.027 -13.3286 curveto stroke
     79newpath -660.985 -6.66971 moveto -622.863 -1.64245 lineto -627.191 -25.0148 lineto closepath fill
     804.56973 setlinewidth 0 0 1 setrgbcolor newpath
    8181-574.666 -153.893 moveto
    82 -528.842 -107.252 -521.515 -99.794 -488.002 -65.683 curveto stroke
    83 newpath -479.592 -57.123 moveto -485.149 -68.4863 lineto -490.856 -62.8797 lineto closepath fill
    84 2 setlinewidth 1 0 0 setrgbcolor newpath
     82-535.911 -114.447 -524.692 -103.027 -501.88 -79.8085 curveto stroke
     83newpath -476.251 -53.7222 moveto -493.402 -88.1377 lineto -510.358 -71.4793 lineto closepath fill
     844.56973 setlinewidth 1 0 0 setrgbcolor newpath
    8585-490.901 120.777 moveto
    86 -480.122 51.1328 -478.519 40.7713 -470.47 -11.2329 curveto stroke
    87 newpath -468.635 -23.0917 moveto -474.423 -11.8447 lineto -466.517 -10.6212 lineto closepath fill
    88 2 setlinewidth 0 0 1 setrgbcolor newpath
     86-481.623 60.8277 -479.143 44.8049 -473.499 8.33636 curveto stroke
     87newpath -467.906 -27.8032 moveto -485.244 6.51862 lineto -461.754 10.1541 lineto closepath fill
     884.56973 setlinewidth 0 0 1 setrgbcolor newpath
    8989-675.963 -3.89604 moveto
    90 -632.116 -68.8235 -626.228 -77.5422 -592.575 -127.374 curveto stroke
    91 newpath -585.859 -137.319 moveto -595.89 -129.612 lineto -589.26 -125.135 lineto closepath fill
    92 2 setlinewidth 0 0 1 setrgbcolor newpath
     90-637.405 -60.9909 -628.201 -74.6206 -603.658 -110.963 curveto stroke
     91newpath -583.191 -141.27 moveto -613.507 -117.615 lineto -593.808 -104.312 lineto closepath fill
     924.56973 setlinewidth 0 0 1 setrgbcolor newpath
    9393-490.901 120.777 moveto
    94 -435.445 215.844 -430.107 224.995 -384.3 303.522 curveto stroke
    95 newpath -378.253 313.887 moveto -380.845 301.507 lineto -387.755 305.537 lineto closepath fill
    96 2 setlinewidth 0 0 1 setrgbcolor newpath
     94-439.75 208.465 -431.238 223.057 -394.278 286.417 curveto stroke
     95newpath -375.851 318.006 moveto -384.012 280.429 lineto -404.543 292.406 lineto closepath fill
     964.56973 setlinewidth 0 0 1 setrgbcolor newpath
    9797-266.879 114.933 moveto
    98 -367.067 117.547 -377.642 117.822 -458.912 119.943 curveto stroke
    99 newpath -470.908 120.255 moveto -458.807 123.941 lineto -459.016 115.944 lineto closepath fill
    100 2 setlinewidth 0 0 1 setrgbcolor newpath
     98-358.311 117.318 -375.109 117.756 -439.117 119.426 curveto stroke
     99newpath -475.674 120.38 moveto -438.807 131.307 lineto -439.426 107.545 lineto closepath fill
     1004.56973 setlinewidth 0 0 1 setrgbcolor newpath
    101101-368.176 331.163 moveto
    102 -322.511 233.685 -318.018 224.095 -280.454 143.911 curveto stroke
    103 newpath -275.364 133.044 moveto -284.076 142.214 lineto -276.832 145.608 lineto closepath fill
    104 2 setlinewidth 1 0 0 setrgbcolor newpath
     102-326.156 241.466 -318.997 226.186 -288.855 161.843 curveto stroke
     103newpath -273.341 128.727 moveto -299.617 156.801 lineto -278.092 166.885 lineto closepath fill
     1044.56973 setlinewidth 1 0 0 setrgbcolor newpath
    105105-266.879 114.933 moveto
    106 -224.004 235.52 -220.448 245.52 -184.094 347.765 curveto stroke
    107 newpath -180.074 359.072 moveto -180.325 346.425 lineto -187.863 349.105 lineto closepath fill
    108 2 setlinewidth 0 0 1 setrgbcolor newpath
     106-226.764 227.755 -221.069 243.774 -190.728 329.107 curveto stroke
     107newpath -178.477 363.564 moveto -179.53 325.126 lineto -201.926 333.089 lineto closepath fill
     1084.56973 setlinewidth 0 0 1 setrgbcolor newpath
    109109-251.294 -335.059 moveto
    110 -189.25 -303.624 -179.902 -298.887 -133.738 -275.498 curveto stroke
    111 newpath -123.034 -270.074 moveto -131.93 -279.066 lineto -135.546 -271.93 lineto closepath fill
    112 2 setlinewidth 0 0 1 setrgbcolor newpath
     110-198.044 -308.079 -183.61 -300.766 -151.402 -284.448 curveto stroke
     111newpath -118.781 -267.92 moveto -146.031 -295.049 lineto -156.774 -273.846 lineto closepath fill
     1124.56973 setlinewidth 0 0 1 setrgbcolor newpath
    113113-389.604 -136.361 moveto
    114 -327.15 -226.083 -321.098 -234.777 -269.576 -308.795 curveto stroke
    115 newpath -262.72 -318.644 moveto -272.859 -311.081 lineto -266.293 -306.51 lineto closepath fill
    116 2 setlinewidth 1 0 0 setrgbcolor newpath
     114-332.039 -219.059 -322.392 -232.919 -280.889 -292.543 curveto stroke
     115newpath -259.996 -322.557 moveto -290.643 -299.333 lineto -271.134 -285.753 lineto closepath fill
     1164.56973 setlinewidth 1 0 0 setrgbcolor newpath
    1171175.84406 175.322 moveto
    118 -76.0754 267.926 -83.1051 275.873 -152.172 353.948 curveto stroke
    119 newpath -160.122 362.936 moveto -149.176 356.598 lineto -155.168 351.298 lineto closepath fill
    120 2 setlinewidth 0 0 1 setrgbcolor newpath
     118-70.5724 261.706 -81.8227 274.423 -139.051 339.116 curveto stroke
     119newpath -163.281 366.507 moveto -130.149 346.991 lineto -147.953 331.242 lineto closepath fill
     1204.56973 setlinewidth 0 0 1 setrgbcolor newpath
    121121169.478 311.683 moveto
    122 96.8003 251.119 88.6819 244.353 30.4273 195.808 curveto stroke
    123 newpath 21.2086 188.126 moveto 27.8666 198.881 lineto 32.988 192.735 lineto closepath fill
    124 2 setlinewidth 0 0 1 setrgbcolor newpath
     122103.641 256.819 90.7821 246.103 45.6398 208.485 curveto stroke
     123newpath 17.546 185.074 moveto 38.0313 217.615 lineto 53.2483 199.355 lineto closepath fill
     1244.56973 setlinewidth 0 0 1 setrgbcolor newpath
    125125342.851 111.037 moveto
    126 263.766 202.563 256.831 210.589 190.4 287.47 curveto stroke
    127 newpath 182.554 296.55 moveto 193.427 290.085 lineto 187.373 284.855 lineto closepath fill
    128 2 setlinewidth 0 0 1 setrgbcolor newpath
     126269.224 196.246 258.132 209.083 203.347 272.486 curveto stroke
     127newpath 179.437 300.157 moveto 212.34 280.257 lineto 194.354 264.716 lineto closepath fill
     1284.56973 setlinewidth 0 0 1 setrgbcolor newpath
    1291295.84406 175.322 moveto
    130 163.16 145.314 173.605 143.321 311.418 117.033 curveto stroke
    131 newpath 323.205 114.784 moveto 310.668 113.104 lineto 312.167 120.962 lineto closepath fill
    132 2 setlinewidth 0 0 1 setrgbcolor newpath
     130155.419 146.79 172.221 143.585 291.966 120.743 curveto stroke
     131newpath 327.888 113.891 moveto 289.739 109.069 lineto 294.193 132.418 lineto closepath fill
     1324.56973 setlinewidth 0 0 1 setrgbcolor newpath
    133133342.851 111.037 moveto
    134 497.255 2.58683 505.964 -3.53033 643.932 -100.436 curveto stroke
    135 newpath 653.752 -107.334 moveto 641.633 -103.71 lineto 646.231 -97.163 lineto closepath fill
    136 2 setlinewidth 0 0 1 setrgbcolor newpath
     134490.978 6.99574 505.015 -2.86383 627.727 -89.0547 curveto stroke
     135newpath 657.653 -110.074 moveto 620.896 -98.7802 lineto 634.558 -79.3291 lineto closepath fill
     1364.56973 setlinewidth 0 0 1 setrgbcolor newpath
    137137364.28 -222.074 moveto
    138 354.298 -66.9063 353.616 -56.2971 344.905 79.1029 curveto stroke
    139 newpath 344.135 91.0781 moveto 348.897 79.3597 lineto 340.914 78.8461 lineto closepath fill
    140 2 setlinewidth 0 0 1 setrgbcolor newpath
     138354.807 -74.8128 353.709 -57.7536 346.177 59.3416 curveto stroke
     139newpath 343.829 95.836 moveto 358.037 60.1045 lineto 334.316 58.5786 lineto closepath fill
     1404.56973 setlinewidth 0 0 1 setrgbcolor newpath
    141141670.118 -118.829 moveto
    142 528.037 -166.793 517.967 -170.192 394.599 -211.839 curveto stroke
    143 newpath 383.229 -215.677 moveto 393.32 -208.049 lineto 395.878 -215.629 lineto closepath fill
    144 2 setlinewidth 1 0 0 setrgbcolor newpath
     142535.595 -164.241 519.412 -169.704 413.361 -205.505 curveto stroke
     143newpath 378.712 -217.202 moveto 409.559 -194.245 lineto 417.162 -216.766 lineto closepath fill
     1444.56973 setlinewidth 1 0 0 setrgbcolor newpath
    145145-105.193 -261.035 moveto
    146 118.401 -242.479 129.015 -241.598 332.39 -224.721 curveto stroke
    147 newpath 344.348 -223.728 moveto 332.72 -228.707 lineto 332.059 -220.734 lineto closepath fill
    148 2 setlinewidth 0 0 1 setrgbcolor newpath
     146110.939 -243.099 128.069 -241.677 312.655 -226.358 curveto stroke
     147newpath 349.1 -223.334 moveto 313.638 -238.202 lineto 311.672 -214.514 lineto closepath fill
     1484.56973 setlinewidth 0 0 1 setrgbcolor newpath
    149149-105.193 -261.035 moveto
    150 -160.867 -161.176 -166.028 -151.918 -212.336 -68.858 curveto stroke
    151 newpath -218.179 -58.3769 moveto -208.842 -66.9102 lineto -215.829 -70.8058 lineto closepath fill
    152 2 setlinewidth 0 0 1 setrgbcolor newpath
     150-156.746 -168.566 -164.987 -153.784 -202.693 -86.1539 curveto stroke
     151newpath -220.5 -54.2129 moveto -192.312 -80.3665 lineto -213.073 -91.9413 lineto closepath fill
     1524.56973 setlinewidth 0 0 1 setrgbcolor newpath
    153153-227.918 -40.9084 moveto
    154 -298.35 -82.4884 -307.42 -87.8432 -362.048 -120.093 curveto stroke
    155 newpath -372.381 -126.193 moveto -364.081 -116.648 lineto -360.014 -123.537 lineto closepath fill
     154-290.327 -77.7521 -304.558 -86.1532 -344.995 -110.026 curveto stroke
     155newpath -376.487 -128.617 moveto -351.037 -99.7914 lineto -338.953 -120.26 lineto closepath fill
    156156grestore
    157157%Nodes:
    158158gsave
    159 -389.604 -136.361 20 0 1 0 nc
    160 -227.918 -40.9084 20 0 1 0 nc
    161 -105.193 -261.035 20 0 1 0 nc
    162 364.28 -222.074 20 1 1 0 nc
    163 670.118 -118.829 20 1 1 0 nc
    164 342.851 111.037 20 1 1 0 nc
    165 5.84406 175.322 20 1 1 0 nc
    166 169.478 311.683 20 1 1 0 nc
    167 -173.374 377.916 20 1 0 1 nc
    168 -251.294 -335.059 20 0 1 0 nc
    169 -266.879 114.933 20 0 0 0 nc
    170 -368.176 331.163 20 0 0 0 nc
    171 -490.901 120.777 20 0 0 0 nc
    172 -574.666 -153.893 20 1 0 0 nc
    173 -675.963 -3.89604 20 1 0 0 nc
    174 -465.576 -42.8564 20 1 0 0 nc
    175 44.8044 15.5841 20 0 0 1 nc
    176 157.79 -130.517 20 0 0 1 nc
    177 218.178 27.2723 20 0 0 1 nc
     159-389.604 -136.361 15.2324 0 1 0 nc
     160-227.918 -40.9084 15.2324 0 1 0 nc
     161-105.193 -261.035 15.2324 0 1 0 nc
     162364.28 -222.074 15.2324 1 1 0 nc
     163670.118 -118.829 15.2324 1 1 0 nc
     164342.851 111.037 15.2324 1 1 0 nc
     1655.84406 175.322 15.2324 1 1 0 nc
     166169.478 311.683 15.2324 1 1 0 nc
     167-173.374 377.916 15.2324 1 0 1 nc
     168-251.294 -335.059 15.2324 0 1 0 nc
     169-266.879 114.933 15.2324 0 0 0 nc
     170-368.176 331.163 15.2324 0 0 0 nc
     171-490.901 120.777 15.2324 0 0 0 nc
     172-574.666 -153.893 15.2324 1 0 0 nc
     173-675.963 -3.89604 15.2324 1 0 0 nc
     174-465.576 -42.8564 15.2324 1 0 0 nc
     17544.8044 15.5841 15.2324 0 0 1 nc
     176157.79 -130.517 15.2324 0 0 1 nc
     177218.178 27.2723 15.2324 0 0 1 nc
    178178grestore
    179179grestore
  • doc/lgf.dox

    r950 r1024  
    6464\endcode
    6565
    66 The \c \@arcs section is very similar to the \c \@nodes section, it
    67 again starts with a header line describing the names of the maps, but
    68 the \c "label" map is not obligatory here. The following lines
    69 describe the arcs. The first two tokens of each line are the source
    70 and the target node of the arc, respectively, then come the map
     66The \e LGF files can also contain bipartite graphs, in this case a
     67\c @red_nodes and a \c @blue_nodes sections describe the node set of the
     68graph. If a map is in both of these sections, then it can be used as a
     69regular node map.
     70
     71\code
     72 @red_nodes
     73 label  only_red_map   name
     74 1      "cherry"       "John"
     75 2      "Santa Claus"  "Jack"
     76 3      "blood"        "Jason"
     77 @blue_nodes
     78 label  name
     79 4      "Elisabeth"
     80 5      "Eve"
     81\endcode
     82
     83The \c \@arcs section is very similar to the \c \@nodes section,
     84it again starts with a header line describing the names of the maps,
     85but the \c "label" map is not obligatory here. The following lines
     86describe the arcs. The first two tokens of each line are
     87the source and the target node of the arc, respectively, then come the map
    7188values. The source and target tokens must be node labels.
    7289
  • doc/mainpage.dox.in

    r930 r1053  
    2626It is a C++ template library providing efficient implementations of common
    2727data structures and algorithms with focus on combinatorial optimization
    28 tasks connected mainly with graphs and networks.
     28tasks connected mainly with graphs and networks \cite DezsoJuttnerKovacs11Lemon.
    2929
    3030<b>
     
    3838The project is maintained by the
    3939<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
    40 Combinatorial Optimization</a> \ref egres
     40Combinatorial Optimization</a> \cite egres
    4141at the Operations Research Department of the
    4242<a href="http://www.elte.hu/en/">E&ouml;tv&ouml;s Lor&aacute;nd University</a>,
    4343Budapest, Hungary.
    4444LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
    45 initiative \ref coinor.
     45initiative \cite coinor.
    4646
    4747\section howtoread How to Read the Documentation
  • doc/min_cost_flow.dox

    r1002 r1053  
    2727minimum total cost from a set of supply nodes to a set of demand nodes
    2828in a network with capacity constraints (lower and upper bounds)
    29 and arc costs \ref amo93networkflows.
     29and arc costs \cite amo93networkflows.
    3030
    3131Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
  • doc/references.bib

    r1002 r1051  
    2020                  {O}perations {R}esearch},
    2121  url =          {http://www.coin-or.org/}
     22}
     23
     24
     25%%%%% Papers related to LEMON %%%%%
     26
     27@article{DezsoJuttnerKovacs11Lemon,
     28  author =       {B. Dezs{\H o} and A. J\"uttner and P. Kov\'acs},
     29  title =        {{LEMON} -- an open source {C++} graph template library},
     30  journal =      {Electronic Notes in Theoretical Computer Science},
     31  volume =       {264},
     32  pages =        {23--45},
     33  year =         {2011},
     34  note =         {Proc. 2nd Workshop on Generative Technologies}
     35}
     36
     37@article{KiralyKovacs12MCF,
     38  author =       {Z. Kir\'aly and P. Kov\'acs},
     39  title =        {Efficient implementations of minimum-cost flow algorithms},
     40  journal =      {Acta Universitatis Sapientiae, Informatica},
     41  year =         {2012},
     42  volume =       {4},
     43  pages =        {67--118}
    2244}
    2345
  • lemon/base.cc

    r477 r1054  
    2222#include<lemon/tolerance.h>
    2323#include<lemon/core.h>
     24#include<lemon/time_measure.h>
    2425namespace lemon {
    2526
     
    3233#endif
    3334
     35  TimeStamp::Format TimeStamp::_format = TimeStamp::NORMAL;
     36
    3437} //namespace lemon
  • lemon/bits/graph_extender.h

    r998 r1027  
    747747  };
    748748
     749  // \ingroup _graphbits
     750  //
     751  // \brief Extender for the BpGraphs
     752  template <typename Base>
     753  class BpGraphExtender : public Base {
     754    typedef Base Parent;
     755
     756  public:
     757
     758    typedef BpGraphExtender BpGraph;
     759
     760    typedef True UndirectedTag;
     761
     762    typedef typename Parent::Node Node;
     763    typedef typename Parent::RedNode RedNode;
     764    typedef typename Parent::BlueNode BlueNode;
     765    typedef typename Parent::Arc Arc;
     766    typedef typename Parent::Edge Edge;
     767
     768    // BpGraph extension
     769
     770    using Parent::first;
     771    using Parent::next;
     772    using Parent::id;
     773
     774    int maxId(Node) const {
     775      return Parent::maxNodeId();
     776    }
     777
     778    int maxId(RedNode) const {
     779      return Parent::maxRedId();
     780    }
     781
     782    int maxId(BlueNode) const {
     783      return Parent::maxBlueId();
     784    }
     785
     786    int maxId(Arc) const {
     787      return Parent::maxArcId();
     788    }
     789
     790    int maxId(Edge) const {
     791      return Parent::maxEdgeId();
     792    }
     793
     794    static Node fromId(int id, Node) {
     795      return Parent::nodeFromId(id);
     796    }
     797
     798    static Arc fromId(int id, Arc) {
     799      return Parent::arcFromId(id);
     800    }
     801
     802    static Edge fromId(int id, Edge) {
     803      return Parent::edgeFromId(id);
     804    }
     805
     806    Node u(Edge e) const { return this->redNode(e); }
     807    Node v(Edge e) const { return this->blueNode(e); }
     808
     809    Node oppositeNode(const Node &n, const Edge &e) const {
     810      if( n == u(e))
     811        return v(e);
     812      else if( n == v(e))
     813        return u(e);
     814      else
     815        return INVALID;
     816    }
     817
     818    Arc oppositeArc(const Arc &arc) const {
     819      return Parent::direct(arc, !Parent::direction(arc));
     820    }
     821
     822    using Parent::direct;
     823    Arc direct(const Edge &edge, const Node &node) const {
     824      return Parent::direct(edge, Parent::redNode(edge) == node);
     825    }
     826
     827    RedNode asRedNode(const Node& node) const {
     828      if (node == INVALID || Parent::blue(node)) {
     829        return INVALID;
     830      } else {
     831        return Parent::asRedNodeUnsafe(node);
     832      }
     833    }
     834
     835    BlueNode asBlueNode(const Node& node) const {
     836      if (node == INVALID || Parent::red(node)) {
     837        return INVALID;
     838      } else {
     839        return Parent::asBlueNodeUnsafe(node);
     840      }
     841    }
     842
     843    // Alterable extension
     844
     845    typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier;
     846    typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier;
     847    typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier;
     848    typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier;
     849    typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier;
     850
     851
     852  protected:
     853
     854    mutable NodeNotifier node_notifier;
     855    mutable RedNodeNotifier red_node_notifier;
     856    mutable BlueNodeNotifier blue_node_notifier;
     857    mutable ArcNotifier arc_notifier;
     858    mutable EdgeNotifier edge_notifier;
     859
     860  public:
     861
     862    NodeNotifier& notifier(Node) const {
     863      return node_notifier;
     864    }
     865
     866    RedNodeNotifier& notifier(RedNode) const {
     867      return red_node_notifier;
     868    }
     869
     870    BlueNodeNotifier& notifier(BlueNode) const {
     871      return blue_node_notifier;
     872    }
     873
     874    ArcNotifier& notifier(Arc) const {
     875      return arc_notifier;
     876    }
     877
     878    EdgeNotifier& notifier(Edge) const {
     879      return edge_notifier;
     880    }
     881
     882
     883
     884    class NodeIt : public Node {
     885      const BpGraph* _graph;
     886    public:
     887
     888      NodeIt() {}
     889
     890      NodeIt(Invalid i) : Node(i) { }
     891
     892      explicit NodeIt(const BpGraph& graph) : _graph(&graph) {
     893        _graph->first(static_cast<Node&>(*this));
     894      }
     895
     896      NodeIt(const BpGraph& graph, const Node& node)
     897        : Node(node), _graph(&graph) {}
     898
     899      NodeIt& operator++() {
     900        _graph->next(*this);
     901        return *this;
     902      }
     903
     904    };
     905
     906    class RedNodeIt : public RedNode {
     907      const BpGraph* _graph;
     908    public:
     909
     910      RedNodeIt() {}
     911
     912      RedNodeIt(Invalid i) : RedNode(i) { }
     913
     914      explicit RedNodeIt(const BpGraph& graph) : _graph(&graph) {
     915        _graph->first(static_cast<RedNode&>(*this));
     916      }
     917
     918      RedNodeIt(const BpGraph& graph, const RedNode& node)
     919        : RedNode(node), _graph(&graph) {}
     920
     921      RedNodeIt& operator++() {
     922        _graph->next(static_cast<RedNode&>(*this));
     923        return *this;
     924      }
     925
     926    };
     927
     928    class BlueNodeIt : public BlueNode {
     929      const BpGraph* _graph;
     930    public:
     931
     932      BlueNodeIt() {}
     933
     934      BlueNodeIt(Invalid i) : BlueNode(i) { }
     935
     936      explicit BlueNodeIt(const BpGraph& graph) : _graph(&graph) {
     937        _graph->first(static_cast<BlueNode&>(*this));
     938      }
     939
     940      BlueNodeIt(const BpGraph& graph, const BlueNode& node)
     941        : BlueNode(node), _graph(&graph) {}
     942
     943      BlueNodeIt& operator++() {
     944        _graph->next(static_cast<BlueNode&>(*this));
     945        return *this;
     946      }
     947
     948    };
     949
     950
     951    class ArcIt : public Arc {
     952      const BpGraph* _graph;
     953    public:
     954
     955      ArcIt() { }
     956
     957      ArcIt(Invalid i) : Arc(i) { }
     958
     959      explicit ArcIt(const BpGraph& graph) : _graph(&graph) {
     960        _graph->first(static_cast<Arc&>(*this));
     961      }
     962
     963      ArcIt(const BpGraph& graph, const Arc& arc) :
     964        Arc(arc), _graph(&graph) { }
     965
     966      ArcIt& operator++() {
     967        _graph->next(*this);
     968        return *this;
     969      }
     970
     971    };
     972
     973
     974    class OutArcIt : public Arc {
     975      const BpGraph* _graph;
     976    public:
     977
     978      OutArcIt() { }
     979
     980      OutArcIt(Invalid i) : Arc(i) { }
     981
     982      OutArcIt(const BpGraph& graph, const Node& node)
     983        : _graph(&graph) {
     984        _graph->firstOut(*this, node);
     985      }
     986
     987      OutArcIt(const BpGraph& graph, const Arc& arc)
     988        : Arc(arc), _graph(&graph) {}
     989
     990      OutArcIt& operator++() {
     991        _graph->nextOut(*this);
     992        return *this;
     993      }
     994
     995    };
     996
     997
     998    class InArcIt : public Arc {
     999      const BpGraph* _graph;
     1000    public:
     1001
     1002      InArcIt() { }
     1003
     1004      InArcIt(Invalid i) : Arc(i) { }
     1005
     1006      InArcIt(const BpGraph& graph, const Node& node)
     1007        : _graph(&graph) {
     1008        _graph->firstIn(*this, node);
     1009      }
     1010
     1011      InArcIt(const BpGraph& graph, const Arc& arc) :
     1012        Arc(arc), _graph(&graph) {}
     1013
     1014      InArcIt& operator++() {
     1015        _graph->nextIn(*this);
     1016        return *this;
     1017      }
     1018
     1019    };
     1020
     1021
     1022    class EdgeIt : public Parent::Edge {
     1023      const BpGraph* _graph;
     1024    public:
     1025
     1026      EdgeIt() { }
     1027
     1028      EdgeIt(Invalid i) : Edge(i) { }
     1029
     1030      explicit EdgeIt(const BpGraph& graph) : _graph(&graph) {
     1031        _graph->first(static_cast<Edge&>(*this));
     1032      }
     1033
     1034      EdgeIt(const BpGraph& graph, const Edge& edge) :
     1035        Edge(edge), _graph(&graph) { }
     1036
     1037      EdgeIt& operator++() {
     1038        _graph->next(*this);
     1039        return *this;
     1040      }
     1041
     1042    };
     1043
     1044    class IncEdgeIt : public Parent::Edge {
     1045      friend class BpGraphExtender;
     1046      const BpGraph* _graph;
     1047      bool _direction;
     1048    public:
     1049
     1050      IncEdgeIt() { }
     1051
     1052      IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
     1053
     1054      IncEdgeIt(const BpGraph& graph, const Node &node) : _graph(&graph) {
     1055        _graph->firstInc(*this, _direction, node);
     1056      }
     1057
     1058      IncEdgeIt(const BpGraph& graph, const Edge &edge, const Node &node)
     1059        : _graph(&graph), Edge(edge) {
     1060        _direction = (_graph->source(edge) == node);
     1061      }
     1062
     1063      IncEdgeIt& operator++() {
     1064        _graph->nextInc(*this, _direction);
     1065        return *this;
     1066      }
     1067    };
     1068
     1069    // \brief Base node of the iterator
     1070    //
     1071    // Returns the base node (ie. the source in this case) of the iterator
     1072    Node baseNode(const OutArcIt &arc) const {
     1073      return Parent::source(static_cast<const Arc&>(arc));
     1074    }
     1075    // \brief Running node of the iterator
     1076    //
     1077    // Returns the running node (ie. the target in this case) of the
     1078    // iterator
     1079    Node runningNode(const OutArcIt &arc) const {
     1080      return Parent::target(static_cast<const Arc&>(arc));
     1081    }
     1082
     1083    // \brief Base node of the iterator
     1084    //
     1085    // Returns the base node (ie. the target in this case) of the iterator
     1086    Node baseNode(const InArcIt &arc) const {
     1087      return Parent::target(static_cast<const Arc&>(arc));
     1088    }
     1089    // \brief Running node of the iterator
     1090    //
     1091    // Returns the running node (ie. the source in this case) of the
     1092    // iterator
     1093    Node runningNode(const InArcIt &arc) const {
     1094      return Parent::source(static_cast<const Arc&>(arc));
     1095    }
     1096
     1097    // Base node of the iterator
     1098    //
     1099    // Returns the base node of the iterator
     1100    Node baseNode(const IncEdgeIt &edge) const {
     1101      return edge._direction ? this->u(edge) : this->v(edge);
     1102    }
     1103    // Running node of the iterator
     1104    //
     1105    // Returns the running node of the iterator
     1106    Node runningNode(const IncEdgeIt &edge) const {
     1107      return edge._direction ? this->v(edge) : this->u(edge);
     1108    }
     1109
     1110    // Mappable extension
     1111
     1112    template <typename _Value>
     1113    class NodeMap
     1114      : public MapExtender<DefaultMap<BpGraph, Node, _Value> > {
     1115      typedef MapExtender<DefaultMap<BpGraph, Node, _Value> > Parent;
     1116
     1117    public:
     1118      explicit NodeMap(const BpGraph& bpgraph)
     1119        : Parent(bpgraph) {}
     1120      NodeMap(const BpGraph& bpgraph, const _Value& value)
     1121        : Parent(bpgraph, value) {}
     1122
     1123    private:
     1124      NodeMap& operator=(const NodeMap& cmap) {
     1125        return operator=<NodeMap>(cmap);
     1126      }
     1127
     1128      template <typename CMap>
     1129      NodeMap& operator=(const CMap& cmap) {
     1130        Parent::operator=(cmap);
     1131        return *this;
     1132      }
     1133
     1134    };
     1135
     1136    template <typename _Value>
     1137    class RedNodeMap
     1138      : public MapExtender<DefaultMap<BpGraph, RedNode, _Value> > {
     1139      typedef MapExtender<DefaultMap<BpGraph, RedNode, _Value> > Parent;
     1140
     1141    public:
     1142      explicit RedNodeMap(const BpGraph& bpgraph)
     1143        : Parent(bpgraph) {}
     1144      RedNodeMap(const BpGraph& bpgraph, const _Value& value)
     1145        : Parent(bpgraph, value) {}
     1146
     1147    private:
     1148      RedNodeMap& operator=(const RedNodeMap& cmap) {
     1149        return operator=<RedNodeMap>(cmap);
     1150      }
     1151
     1152      template <typename CMap>
     1153      RedNodeMap& operator=(const CMap& cmap) {
     1154        Parent::operator=(cmap);
     1155        return *this;
     1156      }
     1157
     1158    };
     1159
     1160    template <typename _Value>
     1161    class BlueNodeMap
     1162      : public MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > {
     1163      typedef MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > Parent;
     1164
     1165    public:
     1166      explicit BlueNodeMap(const BpGraph& bpgraph)
     1167        : Parent(bpgraph) {}
     1168      BlueNodeMap(const BpGraph& bpgraph, const _Value& value)
     1169        : Parent(bpgraph, value) {}
     1170
     1171    private:
     1172      BlueNodeMap& operator=(const BlueNodeMap& cmap) {
     1173        return operator=<BlueNodeMap>(cmap);
     1174      }
     1175
     1176      template <typename CMap>
     1177      BlueNodeMap& operator=(const CMap& cmap) {
     1178        Parent::operator=(cmap);
     1179        return *this;
     1180      }
     1181
     1182    };
     1183
     1184    template <typename _Value>
     1185    class ArcMap
     1186      : public MapExtender<DefaultMap<BpGraph, Arc, _Value> > {
     1187      typedef MapExtender<DefaultMap<BpGraph, Arc, _Value> > Parent;
     1188
     1189    public:
     1190      explicit ArcMap(const BpGraph& graph)
     1191        : Parent(graph) {}
     1192      ArcMap(const BpGraph& graph, const _Value& value)
     1193        : Parent(graph, value) {}
     1194
     1195    private:
     1196      ArcMap& operator=(const ArcMap& cmap) {
     1197        return operator=<ArcMap>(cmap);
     1198      }
     1199
     1200      template <typename CMap>
     1201      ArcMap& operator=(const CMap& cmap) {
     1202        Parent::operator=(cmap);
     1203        return *this;
     1204      }
     1205    };
     1206
     1207
     1208    template <typename _Value>
     1209    class EdgeMap
     1210      : public MapExtender<DefaultMap<BpGraph, Edge, _Value> > {
     1211      typedef MapExtender<DefaultMap<BpGraph, Edge, _Value> > Parent;
     1212
     1213    public:
     1214      explicit EdgeMap(const BpGraph& graph)
     1215        : Parent(graph) {}
     1216
     1217      EdgeMap(const BpGraph& graph, const _Value& value)
     1218        : Parent(graph, value) {}
     1219
     1220    private:
     1221      EdgeMap& operator=(const EdgeMap& cmap) {
     1222        return operator=<EdgeMap>(cmap);
     1223      }
     1224
     1225      template <typename CMap>
     1226      EdgeMap& operator=(const CMap& cmap) {
     1227        Parent::operator=(cmap);
     1228        return *this;
     1229      }
     1230
     1231    };
     1232
     1233    // Alteration extension
     1234
     1235    RedNode addRedNode() {
     1236      RedNode node = Parent::addRedNode();
     1237      notifier(RedNode()).add(node);
     1238      notifier(Node()).add(node);
     1239      return node;
     1240    }
     1241
     1242    BlueNode addBlueNode() {
     1243      BlueNode node = Parent::addBlueNode();
     1244      notifier(BlueNode()).add(node);
     1245      notifier(Node()).add(node);
     1246      return node;
     1247    }
     1248
     1249    Edge addEdge(const RedNode& from, const BlueNode& to) {
     1250      Edge edge = Parent::addEdge(from, to);
     1251      notifier(Edge()).add(edge);
     1252      std::vector<Arc> av;
     1253      av.push_back(Parent::direct(edge, true));
     1254      av.push_back(Parent::direct(edge, false));
     1255      notifier(Arc()).add(av);
     1256      return edge;
     1257    }
     1258
     1259    void clear() {
     1260      notifier(Arc()).clear();
     1261      notifier(Edge()).clear();
     1262      notifier(Node()).clear();
     1263      notifier(BlueNode()).clear();
     1264      notifier(RedNode()).clear();
     1265      Parent::clear();
     1266    }
     1267
     1268    template <typename BpGraph, typename NodeRefMap, typename EdgeRefMap>
     1269    void build(const BpGraph& graph, NodeRefMap& nodeRef,
     1270               EdgeRefMap& edgeRef) {
     1271      Parent::build(graph, nodeRef, edgeRef);
     1272      notifier(RedNode()).build();
     1273      notifier(BlueNode()).build();
     1274      notifier(Node()).build();
     1275      notifier(Edge()).build();
     1276      notifier(Arc()).build();
     1277    }
     1278
     1279    void erase(const Node& node) {
     1280      Arc arc;
     1281      Parent::firstOut(arc, node);
     1282      while (arc != INVALID ) {
     1283        erase(arc);
     1284        Parent::firstOut(arc, node);
     1285      }
     1286
     1287      Parent::firstIn(arc, node);
     1288      while (arc != INVALID ) {
     1289        erase(arc);
     1290        Parent::firstIn(arc, node);
     1291      }
     1292
     1293      if (Parent::red(node)) {
     1294        notifier(RedNode()).erase(this->asRedNodeUnsafe(node));
     1295      } else {
     1296        notifier(BlueNode()).erase(this->asBlueNodeUnsafe(node));
     1297      }
     1298
     1299      notifier(Node()).erase(node);
     1300      Parent::erase(node);
     1301    }
     1302
     1303    void erase(const Edge& edge) {
     1304      std::vector<Arc> av;
     1305      av.push_back(Parent::direct(edge, true));
     1306      av.push_back(Parent::direct(edge, false));
     1307      notifier(Arc()).erase(av);
     1308      notifier(Edge()).erase(edge);
     1309      Parent::erase(edge);
     1310    }
     1311
     1312    BpGraphExtender() {
     1313      red_node_notifier.setContainer(*this);
     1314      blue_node_notifier.setContainer(*this);
     1315      node_notifier.setContainer(*this);
     1316      arc_notifier.setContainer(*this);
     1317      edge_notifier.setContainer(*this);
     1318    }
     1319
     1320    ~BpGraphExtender() {
     1321      edge_notifier.clear();
     1322      arc_notifier.clear();
     1323      node_notifier.clear();
     1324      blue_node_notifier.clear();
     1325      red_node_notifier.clear();
     1326    }
     1327
     1328  };
     1329
    7491330}
    7501331
  • lemon/bits/traits.h

    r616 r1026  
    149149        : Parent(_digraph, _value) {}
    150150    };
     151
     152  };
     153
     154  template <typename GR, typename Enable = void>
     155  struct RedNodeNotifierIndicator {
     156    typedef InvalidType Type;
     157  };
     158  template <typename GR>
     159  struct RedNodeNotifierIndicator<
     160    GR,
     161    typename enable_if<typename GR::RedNodeNotifier::Notifier, void>::type
     162  > {
     163    typedef typename GR::RedNodeNotifier Type;
     164  };
     165
     166  template <typename GR>
     167  class ItemSetTraits<GR, typename GR::RedNode> {
     168  public:
     169
     170    typedef GR BpGraph;
     171    typedef GR Graph;
     172    typedef GR Digraph;
     173
     174    typedef typename GR::RedNode Item;
     175    typedef typename GR::RedNodeIt ItemIt;
     176
     177    typedef typename RedNodeNotifierIndicator<GR>::Type ItemNotifier;
     178
     179    template <typename V>
     180    class Map : public GR::template RedNodeMap<V> {
     181      typedef typename GR::template RedNodeMap<V> Parent;
     182
     183    public:
     184      typedef typename GR::template RedNodeMap<V> Type;
     185      typedef typename Parent::Value Value;
     186
     187      Map(const GR& _bpgraph) : Parent(_bpgraph) {}
     188      Map(const GR& _bpgraph, const Value& _value)
     189        : Parent(_bpgraph, _value) {}
     190
     191     };
     192
     193  };
     194
     195  template <typename GR, typename Enable = void>
     196  struct BlueNodeNotifierIndicator {
     197    typedef InvalidType Type;
     198  };
     199  template <typename GR>
     200  struct BlueNodeNotifierIndicator<
     201    GR,
     202    typename enable_if<typename GR::BlueNodeNotifier::Notifier, void>::type
     203  > {
     204    typedef typename GR::BlueNodeNotifier Type;
     205  };
     206
     207  template <typename GR>
     208  class ItemSetTraits<GR, typename GR::BlueNode> {
     209  public:
     210
     211    typedef GR BpGraph;
     212    typedef GR Graph;
     213    typedef GR Digraph;
     214
     215    typedef typename GR::BlueNode Item;
     216    typedef typename GR::BlueNodeIt ItemIt;
     217
     218    typedef typename BlueNodeNotifierIndicator<GR>::Type ItemNotifier;
     219
     220    template <typename V>
     221    class Map : public GR::template BlueNodeMap<V> {
     222      typedef typename GR::template BlueNodeMap<V> Parent;
     223
     224    public:
     225      typedef typename GR::template BlueNodeMap<V> Type;
     226      typedef typename Parent::Value Value;
     227
     228      Map(const GR& _bpgraph) : Parent(_bpgraph) {}
     229      Map(const GR& _bpgraph, const Value& _value)
     230        : Parent(_bpgraph, _value) {}
     231
     232     };
    151233
    152234  };
  • lemon/capacity_scaling.h

    r1004 r1053  
    6767  /// \ref CapacityScaling implements the capacity scaling version
    6868  /// of the successive shortest path algorithm for finding a
    69   /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
    70   /// \ref edmondskarp72theoretical. It is an efficient dual
    71   /// solution method.
     69  /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows,
     70  /// \cite edmondskarp72theoretical. It is an efficient dual
     71  /// solution method, which runs in polynomial time
     72  /// \f$O(e\log U (n+e)\log n)\f$, where <i>U</i> denotes the maximum
     73  /// of node supply and arc capacity values.
    7274  ///
    7375  /// This algorithm is typically slower than \ref CostScaling and
  • lemon/concepts/digraph.h

    r877 r1049  
    410410      /// \brief The base node of the iterator.
    411411      ///
    412       /// Returns the base node of the given incomming arc iterator
     412      /// Returns the base node of the given incoming arc iterator
    413413      /// (i.e. the target node of the corresponding arc).
    414414      Node baseNode(InArcIt) const { return INVALID; }
     
    416416      /// \brief The running node of the iterator.
    417417      ///
    418       /// Returns the running node of the given incomming arc iterator
     418      /// Returns the running node of the given incoming arc iterator
    419419      /// (i.e. the source node of the corresponding arc).
    420420      Node runningNode(InArcIt) const { return INVALID; }
  • lemon/concepts/graph.h

    r877 r1049  
    7373    class Graph {
    7474    private:
    75       /// Graphs are \e not copy constructible. Use DigraphCopy instead.
     75      /// Graphs are \e not copy constructible. Use GraphCopy instead.
    7676      Graph(const Graph&) {}
    7777      /// \brief Assignment of a graph to another one is \e not allowed.
    78       /// Use DigraphCopy instead.
     78      /// Use GraphCopy instead.
    7979      void operator=(const Graph&) {}
    8080
     
    758758      /// \brief The base node of the iterator.
    759759      ///
    760       /// Returns the base node of the given incomming arc iterator
     760      /// Returns the base node of the given incoming arc iterator
    761761      /// (i.e. the target node of the corresponding arc).
    762762      Node baseNode(InArcIt) const { return INVALID; }
     
    764764      /// \brief The running node of the iterator.
    765765      ///
    766       /// Returns the running node of the given incomming arc iterator
     766      /// Returns the running node of the given incoming arc iterator
    767767      /// (i.e. the source node of the corresponding arc).
    768768      Node runningNode(InArcIt) const { return INVALID; }
  • lemon/concepts/graph_components.h

    r1010 r1049  
    300300    };
    301301
     302    /// \brief Base skeleton class for undirected bipartite graphs.
     303    ///
     304    /// This class describes the base interface of undirected
     305    /// bipartite graph types.  All bipartite graph %concepts have to
     306    /// conform to this class.  It extends the interface of \ref
     307    /// BaseGraphComponent with an \c Edge type and functions to get
     308    /// the end nodes of edges, to convert from arcs to edges and to
     309    /// get both direction of edges.
     310    class BaseBpGraphComponent : public BaseGraphComponent {
     311    public:
     312
     313      typedef BaseBpGraphComponent BpGraph;
     314
     315      typedef BaseDigraphComponent::Node Node;
     316      typedef BaseDigraphComponent::Arc Arc;
     317
     318      /// \brief Class to represent red nodes.
     319      ///
     320      /// This class represents the red nodes of the graph. The red
     321      /// nodes can also be used as normal nodes.
     322      class RedNode : public Node {
     323        typedef Node Parent;
     324
     325      public:
     326        /// \brief Default constructor.
     327        ///
     328        /// Default constructor.
     329        /// \warning The default constructor is not required to set
     330        /// the item to some well-defined value. So you should consider it
     331        /// as uninitialized.
     332        RedNode() {}
     333
     334        /// \brief Copy constructor.
     335        ///
     336        /// Copy constructor.
     337        RedNode(const RedNode &) : Parent() {}
     338
     339        /// \brief Constructor for conversion from \c INVALID.
     340        ///
     341        /// Constructor for conversion from \c INVALID.
     342        /// It initializes the item to be invalid.
     343        /// \sa Invalid for more details.
     344        RedNode(Invalid) {}
     345      };
     346
     347      /// \brief Class to represent blue nodes.
     348      ///
     349      /// This class represents the blue nodes of the graph. The blue
     350      /// nodes can also be used as normal nodes.
     351      class BlueNode : public Node {
     352        typedef Node Parent;
     353
     354      public:
     355        /// \brief Default constructor.
     356        ///
     357        /// Default constructor.
     358        /// \warning The default constructor is not required to set
     359        /// the item to some well-defined value. So you should consider it
     360        /// as uninitialized.
     361        BlueNode() {}
     362
     363        /// \brief Copy constructor.
     364        ///
     365        /// Copy constructor.
     366        BlueNode(const BlueNode &) : Parent() {}
     367
     368        /// \brief Constructor for conversion from \c INVALID.
     369        ///
     370        /// Constructor for conversion from \c INVALID.
     371        /// It initializes the item to be invalid.
     372        /// \sa Invalid for more details.
     373        BlueNode(Invalid) {}
     374
     375        /// \brief Constructor for conversion from a node.
     376        ///
     377        /// Constructor for conversion from a node. The conversion can
     378        /// be invalid, since the Node can be member of the red
     379        /// set.
     380        BlueNode(const Node&) {}
     381      };
     382
     383      /// \brief Gives back %true for red nodes.
     384      ///
     385      /// Gives back %true for red nodes.
     386      bool red(const Node&) const { return true; }
     387
     388      /// \brief Gives back %true for blue nodes.
     389      ///
     390      /// Gives back %true for blue nodes.
     391      bool blue(const Node&) const { return true; }
     392
     393      /// \brief Gives back the red end node of the edge.
     394      ///
     395      /// Gives back the red end node of the edge.
     396      RedNode redNode(const Edge&) const { return RedNode(); }
     397
     398      /// \brief Gives back the blue end node of the edge.
     399      ///
     400      /// Gives back the blue end node of the edge.
     401      BlueNode blueNode(const Edge&) const { return BlueNode(); }
     402
     403      /// \brief Converts the node to red node object.
     404      ///
     405      /// This function converts unsafely the node to red node
     406      /// object. It should be called only if the node is from the red
     407      /// partition or INVALID.
     408      RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
     409
     410      /// \brief Converts the node to blue node object.
     411      ///
     412      /// This function converts unsafely the node to blue node
     413      /// object. It should be called only if the node is from the red
     414      /// partition or INVALID.
     415      BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
     416
     417      /// \brief Converts the node to red node object.
     418      ///
     419      /// This function converts safely the node to red node
     420      /// object. If the node is not from the red partition, then it
     421      /// returns INVALID.
     422      RedNode asRedNode(const Node&) const { return RedNode(); }
     423
     424      /// \brief Converts the node to blue node object.
     425      ///
     426      /// This function converts unsafely the node to blue node
     427      /// object. If the node is not from the blue partition, then it
     428      /// returns INVALID.
     429      BlueNode asBlueNode(const Node&) const { return BlueNode(); }
     430
     431      template <typename _BpGraph>
     432      struct Constraints {
     433        typedef typename _BpGraph::Node Node;
     434        typedef typename _BpGraph::RedNode RedNode;
     435        typedef typename _BpGraph::BlueNode BlueNode;
     436        typedef typename _BpGraph::Arc Arc;
     437        typedef typename _BpGraph::Edge Edge;
     438
     439        void constraints() {
     440          checkConcept<BaseGraphComponent, _BpGraph>();
     441          checkConcept<GraphItem<'n'>, RedNode>();
     442          checkConcept<GraphItem<'n'>, BlueNode>();
     443          {
     444            Node n;
     445            RedNode rn;
     446            BlueNode bn;
     447            Node rnan = rn;
     448            Node bnan = bn;
     449            Edge e;
     450            bool b;
     451            b = bpgraph.red(rnan);
     452            b = bpgraph.blue(bnan);
     453            rn = bpgraph.redNode(e);
     454            bn = bpgraph.blueNode(e);
     455            rn = bpgraph.asRedNodeUnsafe(rnan);
     456            bn = bpgraph.asBlueNodeUnsafe(bnan);
     457            rn = bpgraph.asRedNode(rnan);
     458            bn = bpgraph.asBlueNode(bnan);
     459            ignore_unused_variable_warning(b);
     460          }
     461        }
     462
     463        const _BpGraph& bpgraph;
     464      };
     465
     466    };
     467
    302468    /// \brief Skeleton class for \e idable directed graphs.
    303469    ///
     
    432598    };
    433599
     600    /// \brief Skeleton class for \e idable undirected bipartite graphs.
     601    ///
     602    /// This class describes the interface of \e idable undirected
     603    /// bipartite graphs. It extends \ref IDableGraphComponent with
     604    /// the core ID functions of undirected bipartite graphs. Beside
     605    /// the regular node ids, this class also provides ids within the
     606    /// the red and blue sets of the nodes. This concept is part of
     607    /// the BpGraph concept.
     608    template <typename BAS = BaseBpGraphComponent>
     609    class IDableBpGraphComponent : public IDableGraphComponent<BAS> {
     610    public:
     611
     612      typedef BAS Base;
     613      typedef IDableGraphComponent<BAS> Parent;
     614      typedef typename Base::Node Node;
     615      typedef typename Base::RedNode RedNode;
     616      typedef typename Base::BlueNode BlueNode;
     617
     618      using Parent::id;
     619
     620      /// \brief Return a unique integer id for the given node in the red set.
     621      ///
     622      /// Return a unique integer id for the given node in the red set.
     623      int id(const RedNode&) const { return -1; }
     624
     625      /// \brief Return a unique integer id for the given node in the blue set.
     626      ///
     627      /// Return a unique integer id for the given node in the blue set.
     628      int id(const BlueNode&) const { return -1; }
     629
     630      /// \brief Return an integer greater or equal to the maximum
     631      /// node id in the red set.
     632      ///
     633      /// Return an integer greater or equal to the maximum
     634      /// node id in the red set.
     635      int maxRedId() const { return -1; }
     636
     637      /// \brief Return an integer greater or equal to the maximum
     638      /// node id in the blue set.
     639      ///
     640      /// Return an integer greater or equal to the maximum
     641      /// node id in the blue set.
     642      int maxBlueId() const { return -1; }
     643
     644      template <typename _BpGraph>
     645      struct Constraints {
     646
     647        void constraints() {
     648          checkConcept<IDableGraphComponent<Base>, _BpGraph>();
     649          typename _BpGraph::Node node;
     650          typename _BpGraph::RedNode red;
     651          typename _BpGraph::BlueNode blue;
     652          int rid = bpgraph.id(red);
     653          int bid = bpgraph.id(blue);
     654          rid = bpgraph.maxRedId();
     655          bid = bpgraph.maxBlueId();
     656          ignore_unused_variable_warning(rid);
     657          ignore_unused_variable_warning(bid);
     658        }
     659
     660        const _BpGraph& bpgraph;
     661      };
     662    };
     663
    434664    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
    435665    ///
     
    646876      void next(Arc&) const {}
    647877
    648       /// \brief Return the first arc incomming to the given node.
    649       ///
    650       /// This function gives back the first arc incomming to the
     878      /// \brief Return the first arc incoming to the given node.
     879      ///
     880      /// This function gives back the first arc incoming to the
    651881      /// given node.
    652882      void firstIn(Arc&, const Node&) const {}
    653883
    654       /// \brief Return the next arc incomming to the given node.
    655       ///
    656       /// This function gives back the next arc incomming to the
     884      /// \brief Return the next arc incoming to the given node.
     885      ///
     886      /// This function gives back the next arc incoming to the
    657887      /// given node.
    658888      void nextIn(Arc&) const {}
     
    9051135    };
    9061136
     1137    /// \brief Skeleton class for iterable undirected bipartite graphs.
     1138    ///
     1139    /// This class describes the interface of iterable undirected
     1140    /// bipartite graphs. It extends \ref IterableGraphComponent with
     1141    /// the core iterable interface of undirected bipartite graphs.
     1142    /// This concept is part of the BpGraph concept.
     1143    template <typename BAS = BaseBpGraphComponent>
     1144    class IterableBpGraphComponent : public IterableGraphComponent<BAS> {
     1145    public:
     1146
     1147      typedef BAS Base;
     1148      typedef typename Base::Node Node;
     1149      typedef typename Base::RedNode RedNode;
     1150      typedef typename Base::BlueNode BlueNode;
     1151      typedef typename Base::Arc Arc;
     1152      typedef typename Base::Edge Edge;
     1153     
     1154      typedef IterableBpGraphComponent BpGraph;
     1155
     1156      using IterableGraphComponent<BAS>::first;
     1157      using IterableGraphComponent<BAS>::next;
     1158
     1159      /// \name Base Iteration
     1160      ///
     1161      /// This interface provides functions for iteration on red and blue nodes.
     1162      ///
     1163      /// @{
     1164
     1165      /// \brief Return the first red node.
     1166      ///
     1167      /// This function gives back the first red node in the iteration order.
     1168      void first(RedNode&) const {}
     1169
     1170      /// \brief Return the next red node.
     1171      ///
     1172      /// This function gives back the next red node in the iteration order.
     1173      void next(RedNode&) const {}
     1174
     1175      /// \brief Return the first blue node.
     1176      ///
     1177      /// This function gives back the first blue node in the iteration order.
     1178      void first(BlueNode&) const {}
     1179
     1180      /// \brief Return the next blue node.
     1181      ///
     1182      /// This function gives back the next blue node in the iteration order.
     1183      void next(BlueNode&) const {}
     1184
     1185
     1186      /// @}
     1187
     1188      /// \name Class Based Iteration
     1189      ///
     1190      /// This interface provides iterator classes for red and blue nodes.
     1191      ///
     1192      /// @{
     1193
     1194      /// \brief This iterator goes through each red node.
     1195      ///
     1196      /// This iterator goes through each red node.
     1197      typedef GraphItemIt<BpGraph, RedNode> RedNodeIt;
     1198
     1199      /// \brief This iterator goes through each blue node.
     1200      ///
     1201      /// This iterator goes through each blue node.
     1202      typedef GraphItemIt<BpGraph, BlueNode> BlueNodeIt;
     1203
     1204      /// @}
     1205
     1206      template <typename _BpGraph>
     1207      struct Constraints {
     1208        void constraints() {
     1209          checkConcept<IterableGraphComponent<Base>, _BpGraph>();
     1210
     1211          typename _BpGraph::RedNode rn(INVALID);
     1212          bpgraph.first(rn);
     1213          bpgraph.next(rn);
     1214          typename _BpGraph::BlueNode bn(INVALID);
     1215          bpgraph.first(bn);
     1216          bpgraph.next(bn);
     1217
     1218          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::RedNode>,
     1219            typename _BpGraph::RedNodeIt>();
     1220          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::BlueNode>,
     1221            typename _BpGraph::BlueNodeIt>();
     1222        }
     1223
     1224        const _BpGraph& bpgraph;
     1225      };
     1226    };
     1227
    9071228    /// \brief Skeleton class for alterable directed graphs.
    9081229    ///
     
    9301251      ArcNotifier;
    9311252
     1253      mutable NodeNotifier node_notifier;
     1254      mutable ArcNotifier arc_notifier;
     1255
    9321256      /// \brief Return the node alteration notifier.
    9331257      ///
    9341258      /// This function gives back the node alteration notifier.
    9351259      NodeNotifier& notifier(Node) const {
    936          return NodeNotifier();
     1260        return node_notifier;
    9371261      }
    9381262
     
    9411265      /// This function gives back the arc alteration notifier.
    9421266      ArcNotifier& notifier(Arc) const {
    943         return ArcNotifier();
     1267        return arc_notifier;
    9441268      }
    9451269
     
    9771301
    9781302      typedef BAS Base;
     1303      typedef AlterableDigraphComponent<Base> Parent;
    9791304      typedef typename Base::Edge Edge;
    9801305
     
    9841309      EdgeNotifier;
    9851310
     1311      mutable EdgeNotifier edge_notifier;
     1312
     1313      using Parent::notifier;
     1314
    9861315      /// \brief Return the edge alteration notifier.
    9871316      ///
    9881317      /// This function gives back the edge alteration notifier.
    9891318      EdgeNotifier& notifier(Edge) const {
    990         return EdgeNotifier();
     1319        return edge_notifier;
    9911320      }
    9921321
     
    10021331        const _Graph& graph;
    10031332        Constraints() {}
     1333      };
     1334    };
     1335
     1336    /// \brief Skeleton class for alterable undirected bipartite graphs.
     1337    ///
     1338    /// This class describes the interface of alterable undirected
     1339    /// bipartite graphs. It extends \ref AlterableGraphComponent with
     1340    /// the alteration notifier interface of bipartite graphs. It
     1341    /// implements an observer-notifier pattern for the red and blue
     1342    /// nodes. More obsevers can be registered into the notifier and
     1343    /// whenever an alteration occured in the graph all the observers
     1344    /// will be notified about it.
     1345    template <typename BAS = BaseBpGraphComponent>
     1346    class AlterableBpGraphComponent : public AlterableGraphComponent<BAS> {
     1347    public:
     1348
     1349      typedef BAS Base;
     1350      typedef AlterableGraphComponent<Base> Parent;
     1351      typedef typename Base::RedNode RedNode;
     1352      typedef typename Base::BlueNode BlueNode;
     1353
     1354
     1355      /// Red node alteration notifier class.
     1356      typedef AlterationNotifier<AlterableBpGraphComponent, RedNode>
     1357      RedNodeNotifier;
     1358
     1359      /// Blue node alteration notifier class.
     1360      typedef AlterationNotifier<AlterableBpGraphComponent, BlueNode>
     1361      BlueNodeNotifier;
     1362
     1363      mutable RedNodeNotifier red_node_notifier;
     1364      mutable BlueNodeNotifier blue_node_notifier;
     1365
     1366      using Parent::notifier;
     1367
     1368      /// \brief Return the red node alteration notifier.
     1369      ///
     1370      /// This function gives back the red node alteration notifier.
     1371      RedNodeNotifier& notifier(RedNode) const {
     1372        return red_node_notifier;
     1373      }
     1374
     1375      /// \brief Return the blue node alteration notifier.
     1376      ///
     1377      /// This function gives back the blue node alteration notifier.
     1378      BlueNodeNotifier& notifier(BlueNode) const {
     1379        return blue_node_notifier;
     1380      }
     1381
     1382      template <typename _BpGraph>
     1383      struct Constraints {
     1384        void constraints() {
     1385          checkConcept<AlterableGraphComponent<Base>, _BpGraph>();
     1386          typename _BpGraph::RedNodeNotifier& rnn
     1387            = bpgraph.notifier(typename _BpGraph::RedNode());
     1388          typename _BpGraph::BlueNodeNotifier& bnn
     1389            = bpgraph.notifier(typename _BpGraph::BlueNode());
     1390          ignore_unused_variable_warning(rnn);
     1391          ignore_unused_variable_warning(bnn);
     1392        }
     1393
     1394        const _BpGraph& bpgraph;
    10041395      };
    10051396    };
     
    13081699    };
    13091700
     1701    /// \brief Skeleton class for mappable undirected bipartite graphs.
     1702    ///
     1703    /// This class describes the interface of mappable undirected
     1704    /// bipartite graphs.  It extends \ref MappableGraphComponent with
     1705    /// the standard graph map class for red and blue nodes (\c
     1706    /// RedNodeMap and BlueNodeMap). This concept is part of the
     1707    /// BpGraph concept.
     1708    template <typename BAS = BaseBpGraphComponent>
     1709    class MappableBpGraphComponent : public MappableGraphComponent<BAS>  {
     1710    public:
     1711
     1712      typedef BAS Base;
     1713      typedef typename Base::Node Node;
     1714
     1715      typedef MappableBpGraphComponent BpGraph;
     1716
     1717      /// \brief Standard graph map for the red nodes.
     1718      ///
     1719      /// Standard graph map for the red nodes.
     1720      /// It conforms to the ReferenceMap concept.
     1721      template <typename V>
     1722      class RedNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> {
     1723        typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
     1724
     1725      public:
     1726        /// \brief Construct a new map.
     1727        ///
     1728        /// Construct a new map for the graph.
     1729        explicit RedNodeMap(const MappableBpGraphComponent& graph)
     1730          : Parent(graph) {}
     1731
     1732        /// \brief Construct a new map with default value.
     1733        ///
     1734        /// Construct a new map for the graph and initalize the values.
     1735        RedNodeMap(const MappableBpGraphComponent& graph, const V& value)
     1736          : Parent(graph, value) {}
     1737
     1738      private:
     1739        /// \brief Copy constructor.
     1740        ///
     1741        /// Copy Constructor.
     1742        RedNodeMap(const RedNodeMap& nm) : Parent(nm) {}
     1743
     1744        /// \brief Assignment operator.
     1745        ///
     1746        /// Assignment operator.
     1747        template <typename CMap>
     1748        RedNodeMap& operator=(const CMap&) {
     1749          checkConcept<ReadMap<Node, V>, CMap>();
     1750          return *this;
     1751        }
     1752
     1753      };
     1754
     1755      /// \brief Standard graph map for the blue nodes.
     1756      ///
     1757      /// Standard graph map for the blue nodes.
     1758      /// It conforms to the ReferenceMap concept.
     1759      template <typename V>
     1760      class BlueNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> {
     1761        typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
     1762
     1763      public:
     1764        /// \brief Construct a new map.
     1765        ///
     1766        /// Construct a new map for the graph.
     1767        explicit BlueNodeMap(const MappableBpGraphComponent& graph)
     1768          : Parent(graph) {}
     1769
     1770        /// \brief Construct a new map with default value.
     1771        ///
     1772        /// Construct a new map for the graph and initalize the values.
     1773        BlueNodeMap(const MappableBpGraphComponent& graph, const V& value)
     1774          : Parent(graph, value) {}
     1775
     1776      private:
     1777        /// \brief Copy constructor.
     1778        ///
     1779        /// Copy Constructor.
     1780        BlueNodeMap(const BlueNodeMap& nm) : Parent(nm) {}
     1781
     1782        /// \brief Assignment operator.
     1783        ///
     1784        /// Assignment operator.
     1785        template <typename CMap>
     1786        BlueNodeMap& operator=(const CMap&) {
     1787          checkConcept<ReadMap<Node, V>, CMap>();
     1788          return *this;
     1789        }
     1790
     1791      };
     1792
     1793
     1794      template <typename _BpGraph>
     1795      struct Constraints {
     1796
     1797        struct Dummy {
     1798          int value;
     1799          Dummy() : value(0) {}
     1800          Dummy(int _v) : value(_v) {}
     1801        };
     1802
     1803        void constraints() {
     1804          checkConcept<MappableGraphComponent<Base>, _BpGraph>();
     1805
     1806          { // int map test
     1807            typedef typename _BpGraph::template RedNodeMap<int>
     1808              IntRedNodeMap;
     1809            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, int>,
     1810              IntRedNodeMap >();
     1811          } { // bool map test
     1812            typedef typename _BpGraph::template RedNodeMap<bool>
     1813              BoolRedNodeMap;
     1814            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, bool>,
     1815              BoolRedNodeMap >();
     1816          } { // Dummy map test
     1817            typedef typename _BpGraph::template RedNodeMap<Dummy>
     1818              DummyRedNodeMap;
     1819            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, Dummy>,
     1820              DummyRedNodeMap >();
     1821          }
     1822
     1823          { // int map test
     1824            typedef typename _BpGraph::template BlueNodeMap<int>
     1825              IntBlueNodeMap;
     1826            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, int>,
     1827              IntBlueNodeMap >();
     1828          } { // bool map test
     1829            typedef typename _BpGraph::template BlueNodeMap<bool>
     1830              BoolBlueNodeMap;
     1831            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, bool>,
     1832              BoolBlueNodeMap >();
     1833          } { // Dummy map test
     1834            typedef typename _BpGraph::template BlueNodeMap<Dummy>
     1835              DummyBlueNodeMap;
     1836            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, Dummy>,
     1837              DummyBlueNodeMap >();
     1838          }
     1839        }
     1840
     1841        const _BpGraph& bpgraph;
     1842      };
     1843    };
     1844
    13101845    /// \brief Skeleton class for extendable directed graphs.
    13111846    ///
     
    13981933    };
    13991934
     1935    /// \brief Skeleton class for extendable undirected bipartite graphs.
     1936    ///
     1937    /// This class describes the interface of extendable undirected
     1938    /// bipartite graphs. It extends \ref BaseGraphComponent with
     1939    /// functions for adding nodes and edges to the graph. This
     1940    /// concept requires \ref AlterableBpGraphComponent.
     1941    template <typename BAS = BaseBpGraphComponent>
     1942    class ExtendableBpGraphComponent : public BAS {
     1943    public:
     1944
     1945      typedef BAS Base;
     1946      typedef typename Base::Node Node;
     1947      typedef typename Base::RedNode RedNode;
     1948      typedef typename Base::BlueNode BlueNode;
     1949      typedef typename Base::Edge Edge;
     1950
     1951      /// \brief Add a new red node to the digraph.
     1952      ///
     1953      /// This function adds a red new node to the digraph.
     1954      RedNode addRedNode() {
     1955        return INVALID;
     1956      }
     1957
     1958      /// \brief Add a new blue node to the digraph.
     1959      ///
     1960      /// This function adds a blue new node to the digraph.
     1961      BlueNode addBlueNode() {
     1962        return INVALID;
     1963      }
     1964
     1965      /// \brief Add a new edge connecting the given two nodes.
     1966      ///
     1967      /// This function adds a new edge connecting the given two nodes
     1968      /// of the graph. The first node has to be a red node, and the
     1969      /// second one a blue node.
     1970      Edge addEdge(const RedNode&, const BlueNode&) {
     1971        return INVALID;
     1972      }
     1973      Edge addEdge(const BlueNode&, const RedNode&) {
     1974        return INVALID;
     1975      }
     1976
     1977      template <typename _BpGraph>
     1978      struct Constraints {
     1979        void constraints() {
     1980          checkConcept<Base, _BpGraph>();
     1981          typename _BpGraph::RedNode red_node;
     1982          typename _BpGraph::BlueNode blue_node;
     1983          red_node = bpgraph.addRedNode();
     1984          blue_node = bpgraph.addBlueNode();
     1985          typename _BpGraph::Edge edge;
     1986          edge = bpgraph.addEdge(red_node, blue_node);
     1987          edge = bpgraph.addEdge(blue_node, red_node);
     1988        }
     1989
     1990        _BpGraph& bpgraph;
     1991      };
     1992    };
     1993
    14001994    /// \brief Skeleton class for erasable directed graphs.
    14011995    ///
     
    14782072    };
    14792073
     2074    /// \brief Skeleton class for erasable undirected graphs.
     2075    ///
     2076    /// This class describes the interface of erasable undirected
     2077    /// bipartite graphs. It extends \ref BaseBpGraphComponent with
     2078    /// functions for removing nodes and edges from the graph. This
     2079    /// concept requires \ref AlterableBpGraphComponent.
     2080    template <typename BAS = BaseBpGraphComponent>
     2081    class ErasableBpGraphComponent : public ErasableGraphComponent<BAS> {};
     2082
    14802083    /// \brief Skeleton class for clearable directed graphs.
    14812084    ///
     
    15142117    /// This concept requires \ref AlterableGraphComponent.
    15152118    template <typename BAS = BaseGraphComponent>
    1516     class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
    1517     public:
    1518 
    1519       typedef BAS Base;
    1520 
    1521       /// \brief Erase all nodes and edges from the graph.
    1522       ///
    1523       /// This function erases all nodes and edges from the graph.
    1524       void clear() {}
    1525 
    1526       template <typename _Graph>
    1527       struct Constraints {
    1528         void constraints() {
    1529           checkConcept<Base, _Graph>();
    1530           graph.clear();
    1531         }
    1532 
    1533         _Graph& graph;
    1534         Constraints() {}
    1535       };
    1536     };
     2119    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {};
     2120
     2121    /// \brief Skeleton class for clearable undirected biparite graphs.
     2122    ///
     2123    /// This class describes the interface of clearable undirected
     2124    /// bipartite graphs. It extends \ref BaseBpGraphComponent with a
     2125    /// function for clearing the graph.  This concept requires \ref
     2126    /// AlterableBpGraphComponent.
     2127    template <typename BAS = BaseBpGraphComponent>
     2128    class ClearableBpGraphComponent : public ClearableGraphComponent<BAS> {};
    15372129
    15382130  }
  • lemon/core.h

    r1000 r1027  
    149149  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
    150150
     151  ///Create convenience typedefs for the bipartite graph types and iterators
     152
     153  ///This \c \#define creates the same convenient type definitions as
     154  ///defined by \ref GRAPH_TYPEDEFS(BpGraph) and ten more, namely it
     155  ///creates \c RedNode, \c RedNodeIt, \c BoolRedNodeMap,
     156  ///\c IntRedNodeMap, \c DoubleRedNodeMap, \c BlueNode, \c BlueNodeIt,
     157  ///\c BoolBlueNodeMap, \c IntBlueNodeMap, \c DoubleBlueNodeMap.
     158  ///
     159  ///\note If the graph type is a dependent type, ie. the graph type depend
     160  ///on a template parameter, then use \c TEMPLATE_BPGRAPH_TYPEDEFS()
     161  ///macro.
     162#define BPGRAPH_TYPEDEFS(BpGraph)                                       \
     163  GRAPH_TYPEDEFS(BpGraph);                                              \
     164  typedef BpGraph::RedNode RedNode;                                     \
     165  typedef BpGraph::RedNodeIt RedNodeIt;                                 \
     166  typedef BpGraph::RedNodeMap<bool> BoolRedNodeMap;                     \
     167  typedef BpGraph::RedNodeMap<int> IntRedNodeMap;                       \
     168  typedef BpGraph::RedNodeMap<double> DoubleRedNodeMap;                 \
     169  typedef BpGraph::BlueNode BlueNode;                                   \
     170  typedef BpGraph::BlueNodeIt BlueNodeIt;                               \
     171  typedef BpGraph::BlueNodeMap<bool> BoolBlueNodeMap;                   \
     172  typedef BpGraph::BlueNodeMap<int> IntBlueNodeMap;                     \
     173  typedef BpGraph::BlueNodeMap<double> DoubleBlueNodeMap
     174
     175  ///Create convenience typedefs for the bipartite graph types and iterators
     176
     177  ///\see BPGRAPH_TYPEDEFS
     178  ///
     179  ///\note Use this macro, if the graph type is a dependent type,
     180  ///ie. the graph type depend on a template parameter.
     181#define TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph)                                  \
     182  TEMPLATE_GRAPH_TYPEDEFS(BpGraph);                                         \
     183  typedef typename BpGraph::RedNode RedNode;                                \
     184  typedef typename BpGraph::RedNodeIt RedNodeIt;                            \
     185  typedef typename BpGraph::template RedNodeMap<bool> BoolRedNodeMap;       \
     186  typedef typename BpGraph::template RedNodeMap<int> IntRedNodeMap;         \
     187  typedef typename BpGraph::template RedNodeMap<double> DoubleRedNodeMap;   \
     188  typedef typename BpGraph::BlueNode BlueNode;                              \
     189  typedef typename BpGraph::BlueNodeIt BlueNodeIt;                          \
     190  typedef typename BpGraph::template BlueNodeMap<bool> BoolBlueNodeMap;     \
     191  typedef typename BpGraph::template BlueNodeMap<int> IntBlueNodeMap;       \
     192  typedef typename BpGraph::template BlueNodeMap<double> DoubleBlueNodeMap
     193
    151194  /// \brief Function to count the items in a graph.
    152195  ///
     
    200243  }
    201244
     245  namespace _graph_utils_bits {
     246   
     247    template <typename Graph, typename Enable = void>
     248    struct CountRedNodesSelector {
     249      static int count(const Graph &g) {
     250        return countItems<Graph, typename Graph::RedNode>(g);
     251      }
     252    };
     253
     254    template <typename Graph>
     255    struct CountRedNodesSelector<
     256      Graph, typename
     257      enable_if<typename Graph::NodeNumTag, void>::type>
     258    {
     259      static int count(const Graph &g) {
     260        return g.redNum();
     261      }
     262    };   
     263  }
     264
     265  /// \brief Function to count the red nodes in the graph.
     266  ///
     267  /// This function counts the red nodes in the graph.
     268  /// The complexity of the function is O(n) but for some
     269  /// graph structures it is specialized to run in O(1).
     270  ///
     271  /// If the graph contains a \e redNum() member function and a
     272  /// \e NodeNumTag tag then this function calls directly the member
     273  /// function to query the cardinality of the node set.
     274  template <typename Graph>
     275  inline int countRedNodes(const Graph& g) {
     276    return _graph_utils_bits::CountRedNodesSelector<Graph>::count(g);
     277  }
     278
     279  namespace _graph_utils_bits {
     280   
     281    template <typename Graph, typename Enable = void>
     282    struct CountBlueNodesSelector {
     283      static int count(const Graph &g) {
     284        return countItems<Graph, typename Graph::BlueNode>(g);
     285      }
     286    };
     287
     288    template <typename Graph>
     289    struct CountBlueNodesSelector<
     290      Graph, typename
     291      enable_if<typename Graph::NodeNumTag, void>::type>
     292    {
     293      static int count(const Graph &g) {
     294        return g.blueNum();
     295      }
     296    };   
     297  }
     298
     299  /// \brief Function to count the blue nodes in the graph.
     300  ///
     301  /// This function counts the blue nodes in the graph.
     302  /// The complexity of the function is O(n) but for some
     303  /// graph structures it is specialized to run in O(1).
     304  ///
     305  /// If the graph contains a \e blueNum() member function and a
     306  /// \e NodeNumTag tag then this function calls directly the member
     307  /// function to query the cardinality of the node set.
     308  template <typename Graph>
     309  inline int countBlueNodes(const Graph& g) {
     310    return _graph_utils_bits::CountBlueNodesSelector<Graph>::count(g);
     311  }
     312
    202313  // Arc counting:
    203314
     
    441552      template <typename From, typename NodeRefMap, typename EdgeRefMap>
    442553      static void copy(const From& from, Graph &to,
    443                        NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
     554                       NodeRefMap& nodeRefMap,
     555                       EdgeRefMap& edgeRefMap) {
    444556        to.build(from, nodeRefMap, edgeRefMap);
     557      }
     558    };
     559
     560    template <typename BpGraph, typename Enable = void>
     561    struct BpGraphCopySelector {
     562      template <typename From, typename RedNodeRefMap,
     563                typename BlueNodeRefMap, typename EdgeRefMap>
     564      static void copy(const From& from, BpGraph &to,
     565                       RedNodeRefMap& redNodeRefMap,
     566                       BlueNodeRefMap& blueNodeRefMap,
     567                       EdgeRefMap& edgeRefMap) {
     568        to.clear();
     569        for (typename From::RedNodeIt it(from); it != INVALID; ++it) {
     570          redNodeRefMap[it] = to.addRedNode();
     571        }
     572        for (typename From::BlueNodeIt it(from); it != INVALID; ++it) {
     573          blueNodeRefMap[it] = to.addBlueNode();
     574        }
     575        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
     576          edgeRefMap[it] = to.addEdge(redNodeRefMap[from.redNode(it)],
     577                                      blueNodeRefMap[from.blueNode(it)]);
     578        }
     579      }
     580    };
     581
     582    template <typename BpGraph>
     583    struct BpGraphCopySelector<
     584      BpGraph,
     585      typename enable_if<typename BpGraph::BuildTag, void>::type>
     586    {
     587      template <typename From, typename RedNodeRefMap,
     588                typename BlueNodeRefMap, typename EdgeRefMap>
     589      static void copy(const From& from, BpGraph &to,
     590                       RedNodeRefMap& redNodeRefMap,
     591                       BlueNodeRefMap& blueNodeRefMap,
     592                       EdgeRefMap& edgeRefMap) {
     593        to.build(from, redNodeRefMap, blueNodeRefMap, edgeRefMap);
    445594      }
    446595    };
     
    9901139  graphCopy(const From& from, To& to) {
    9911140    return GraphCopy<From, To>(from, to);
     1141  }
     1142
     1143  /// \brief Class to copy a bipartite graph.
     1144  ///
     1145  /// Class to copy a bipartite graph to another graph (duplicate a
     1146  /// graph). The simplest way of using it is through the
     1147  /// \c bpGraphCopy() function.
     1148  ///
     1149  /// This class not only make a copy of a bipartite graph, but it can
     1150  /// create references and cross references between the nodes, edges
     1151  /// and arcs of the two graphs, and it can copy maps for using with
     1152  /// the newly created graph.
     1153  ///
     1154  /// To make a copy from a graph, first an instance of BpGraphCopy
     1155  /// should be created, then the data belongs to the graph should
     1156  /// assigned to copy. In the end, the \c run() member should be
     1157  /// called.
     1158  ///
     1159  /// The next code copies a graph with several data:
     1160  ///\code
     1161  ///  BpGraphCopy<OrigBpGraph, NewBpGraph> cg(orig_graph, new_graph);
     1162  ///  // Create references for the nodes
     1163  ///  OrigBpGraph::NodeMap<NewBpGraph::Node> nr(orig_graph);
     1164  ///  cg.nodeRef(nr);
     1165  ///  // Create cross references (inverse) for the edges
     1166  ///  NewBpGraph::EdgeMap<OrigBpGraph::Edge> ecr(new_graph);
     1167  ///  cg.edgeCrossRef(ecr);
     1168  ///  // Copy a red node map
     1169  ///  OrigBpGraph::RedNodeMap<double> ormap(orig_graph);
     1170  ///  NewBpGraph::RedNodeMap<double> nrmap(new_graph);
     1171  ///  cg.redNodeMap(ormap, nrmap);
     1172  ///  // Copy a node
     1173  ///  OrigBpGraph::Node on;
     1174  ///  NewBpGraph::Node nn;
     1175  ///  cg.node(on, nn);
     1176  ///  // Execute copying
     1177  ///  cg.run();
     1178  ///\endcode
     1179  template <typename From, typename To>
     1180  class BpGraphCopy {
     1181  private:
     1182
     1183    typedef typename From::Node Node;
     1184    typedef typename From::RedNode RedNode;
     1185    typedef typename From::BlueNode BlueNode;
     1186    typedef typename From::NodeIt NodeIt;
     1187    typedef typename From::Arc Arc;
     1188    typedef typename From::ArcIt ArcIt;
     1189    typedef typename From::Edge Edge;
     1190    typedef typename From::EdgeIt EdgeIt;
     1191
     1192    typedef typename To::Node TNode;
     1193    typedef typename To::RedNode TRedNode;
     1194    typedef typename To::BlueNode TBlueNode;
     1195    typedef typename To::Arc TArc;
     1196    typedef typename To::Edge TEdge;
     1197
     1198    typedef typename From::template RedNodeMap<TRedNode> RedNodeRefMap;
     1199    typedef typename From::template BlueNodeMap<TBlueNode> BlueNodeRefMap;
     1200    typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
     1201
     1202    struct NodeRefMap {
     1203      NodeRefMap(const From& from, const RedNodeRefMap& red_node_ref,
     1204                 const BlueNodeRefMap& blue_node_ref)
     1205        : _from(from), _red_node_ref(red_node_ref),
     1206          _blue_node_ref(blue_node_ref) {}
     1207
     1208      typedef typename From::Node Key;
     1209      typedef typename To::Node Value;
     1210
     1211      Value operator[](const Key& key) const {
     1212        if (_from.red(key)) {
     1213          return _red_node_ref[_from.asRedNodeUnsafe(key)];
     1214        } else {
     1215          return _blue_node_ref[_from.asBlueNodeUnsafe(key)];
     1216        }
     1217      }
     1218
     1219      const From& _from;
     1220      const RedNodeRefMap& _red_node_ref;
     1221      const BlueNodeRefMap& _blue_node_ref;
     1222    };
     1223
     1224    struct ArcRefMap {
     1225      ArcRefMap(const From& from, const To& to, const EdgeRefMap& edge_ref)
     1226        : _from(from), _to(to), _edge_ref(edge_ref) {}
     1227
     1228      typedef typename From::Arc Key;
     1229      typedef typename To::Arc Value;
     1230
     1231      Value operator[](const Key& key) const {
     1232        return _to.direct(_edge_ref[key], _from.direction(key));
     1233      }
     1234
     1235      const From& _from;
     1236      const To& _to;
     1237      const EdgeRefMap& _edge_ref;
     1238    };
     1239
     1240  public:
     1241
     1242    /// \brief Constructor of BpGraphCopy.
     1243    ///
     1244    /// Constructor of BpGraphCopy for copying the content of the
     1245    /// \c from graph into the \c to graph.
     1246    BpGraphCopy(const From& from, To& to)
     1247      : _from(from), _to(to) {}
     1248
     1249    /// \brief Destructor of BpGraphCopy
     1250    ///
     1251    /// Destructor of BpGraphCopy.
     1252    ~BpGraphCopy() {
     1253      for (int i = 0; i < int(_node_maps.size()); ++i) {
     1254        delete _node_maps[i];
     1255      }
     1256      for (int i = 0; i < int(_red_maps.size()); ++i) {
     1257        delete _red_maps[i];
     1258      }
     1259      for (int i = 0; i < int(_blue_maps.size()); ++i) {
     1260        delete _blue_maps[i];
     1261      }
     1262      for (int i = 0; i < int(_arc_maps.size()); ++i) {
     1263        delete _arc_maps[i];
     1264      }
     1265      for (int i = 0; i < int(_edge_maps.size()); ++i) {
     1266        delete _edge_maps[i];
     1267      }
     1268    }
     1269
     1270    /// \brief Copy the node references into the given map.
     1271    ///
     1272    /// This function copies the node references into the given map.
     1273    /// The parameter should be a map, whose key type is the Node type of
     1274    /// the source graph, while the value type is the Node type of the
     1275    /// destination graph.
     1276    template <typename NodeRef>
     1277    BpGraphCopy& nodeRef(NodeRef& map) {
     1278      _node_maps.push_back(new _core_bits::RefCopy<From, Node,
     1279                           NodeRefMap, NodeRef>(map));
     1280      return *this;
     1281    }
     1282
     1283    /// \brief Copy the node cross references into the given map.
     1284    ///
     1285    /// This function copies the node cross references (reverse references)
     1286    /// into the given map. The parameter should be a map, whose key type
     1287    /// is the Node type of the destination graph, while the value type is
     1288    /// the Node type of the source graph.
     1289    template <typename NodeCrossRef>
     1290    BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {
     1291      _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
     1292                           NodeRefMap, NodeCrossRef>(map));
     1293      return *this;
     1294    }
     1295
     1296    /// \brief Make a copy of the given node map.
     1297    ///
     1298    /// This function makes a copy of the given node map for the newly
     1299    /// created graph.
     1300    /// The key type of the new map \c tmap should be the Node type of the
     1301    /// destination graph, and the key type of the original map \c map
     1302    /// should be the Node type of the source graph.
     1303    template <typename FromMap, typename ToMap>
     1304    BpGraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
     1305      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
     1306                           NodeRefMap, FromMap, ToMap>(map, tmap));
     1307      return *this;
     1308    }
     1309
     1310    /// \brief Make a copy of the given node.
     1311    ///
     1312    /// This function makes a copy of the given node.
     1313    BpGraphCopy& node(const Node& node, TNode& tnode) {
     1314      _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
     1315                           NodeRefMap, TNode>(node, tnode));
     1316      return *this;
     1317    }
     1318
     1319    /// \brief Copy the red node references into the given map.
     1320    ///
     1321    /// This function copies the red node references into the given
     1322    /// map.  The parameter should be a map, whose key type is the
     1323    /// Node type of the source graph with the red item set, while the
     1324    /// value type is the Node type of the destination graph.
     1325    template <typename RedRef>
     1326    BpGraphCopy& redRef(RedRef& map) {
     1327      _red_maps.push_back(new _core_bits::RefCopy<From, RedNode,
     1328                          RedNodeRefMap, RedRef>(map));
     1329      return *this;
     1330    }
     1331
     1332    /// \brief Copy the red node cross references into the given map.
     1333    ///
     1334    /// This function copies the red node cross references (reverse
     1335    /// references) into the given map. The parameter should be a map,
     1336    /// whose key type is the Node type of the destination graph with
     1337    /// the red item set, while the value type is the Node type of the
     1338    /// source graph.
     1339    template <typename RedCrossRef>
     1340    BpGraphCopy& redCrossRef(RedCrossRef& map) {
     1341      _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode,
     1342                          RedNodeRefMap, RedCrossRef>(map));
     1343      return *this;
     1344    }
     1345
     1346    /// \brief Make a copy of the given red node map.
     1347    ///
     1348    /// This function makes a copy of the given red node map for the newly
     1349    /// created graph.
     1350    /// The key type of the new map \c tmap should be the Node type of
     1351    /// the destination graph with the red items, and the key type of
     1352    /// the original map \c map should be the Node type of the source
     1353    /// graph.
     1354    template <typename FromMap, typename ToMap>
     1355    BpGraphCopy& redNodeMap(const FromMap& map, ToMap& tmap) {
     1356      _red_maps.push_back(new _core_bits::MapCopy<From, RedNode,
     1357                          RedNodeRefMap, FromMap, ToMap>(map, tmap));
     1358      return *this;
     1359    }
     1360
     1361    /// \brief Make a copy of the given red node.
     1362    ///
     1363    /// This function makes a copy of the given red node.
     1364    BpGraphCopy& redNode(const RedNode& node, TRedNode& tnode) {
     1365      _red_maps.push_back(new _core_bits::ItemCopy<From, RedNode,
     1366                          RedNodeRefMap, TRedNode>(node, tnode));
     1367      return *this;
     1368    }
     1369
     1370    /// \brief Copy the blue node references into the given map.
     1371    ///
     1372    /// This function copies the blue node references into the given
     1373    /// map.  The parameter should be a map, whose key type is the
     1374    /// Node type of the source graph with the blue item set, while the
     1375    /// value type is the Node type of the destination graph.
     1376    template <typename BlueRef>
     1377    BpGraphCopy& blueRef(BlueRef& map) {
     1378      _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode,
     1379                           BlueNodeRefMap, BlueRef>(map));
     1380      return *this;
     1381    }
     1382
     1383    /// \brief Copy the blue node cross references into the given map.
     1384    ///
     1385    /// This function copies the blue node cross references (reverse
     1386    /// references) into the given map. The parameter should be a map,
     1387    /// whose key type is the Node type of the destination graph with
     1388    /// the blue item set, while the value type is the Node type of the
     1389    /// source graph.
     1390    template <typename BlueCrossRef>
     1391    BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
     1392      _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode,
     1393                           BlueNodeRefMap, BlueCrossRef>(map));
     1394      return *this;
     1395    }
     1396
     1397    /// \brief Make a copy of the given blue node map.
     1398    ///
     1399    /// This function makes a copy of the given blue node map for the newly
     1400    /// created graph.
     1401    /// The key type of the new map \c tmap should be the Node type of
     1402    /// the destination graph with the blue items, and the key type of
     1403    /// the original map \c map should be the Node type of the source
     1404    /// graph.
     1405    template <typename FromMap, typename ToMap>
     1406    BpGraphCopy& blueNodeMap(const FromMap& map, ToMap& tmap) {
     1407      _blue_maps.push_back(new _core_bits::MapCopy<From, BlueNode,
     1408                           BlueNodeRefMap, FromMap, ToMap>(map, tmap));
     1409      return *this;
     1410    }
     1411
     1412    /// \brief Make a copy of the given blue node.
     1413    ///
     1414    /// This function makes a copy of the given blue node.
     1415    BpGraphCopy& blueNode(const BlueNode& node, TBlueNode& tnode) {
     1416      _blue_maps.push_back(new _core_bits::ItemCopy<From, BlueNode,
     1417                           BlueNodeRefMap, TBlueNode>(node, tnode));
     1418      return *this;
     1419    }
     1420
     1421    /// \brief Copy the arc references into the given map.
     1422    ///
     1423    /// This function copies the arc references into the given map.
     1424    /// The parameter should be a map, whose key type is the Arc type of
     1425    /// the source graph, while the value type is the Arc type of the
     1426    /// destination graph.
     1427    template <typename ArcRef>
     1428    BpGraphCopy& arcRef(ArcRef& map) {
     1429      _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
     1430                          ArcRefMap, ArcRef>(map));
     1431      return *this;
     1432    }
     1433
     1434    /// \brief Copy the arc cross references into the given map.
     1435    ///
     1436    /// This function copies the arc cross references (reverse references)
     1437    /// into the given map. The parameter should be a map, whose key type
     1438    /// is the Arc type of the destination graph, while the value type is
     1439    /// the Arc type of the source graph.
     1440    template <typename ArcCrossRef>
     1441    BpGraphCopy& arcCrossRef(ArcCrossRef& map) {
     1442      _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
     1443                          ArcRefMap, ArcCrossRef>(map));
     1444      return *this;
     1445    }
     1446
     1447    /// \brief Make a copy of the given arc map.
     1448    ///
     1449    /// This function makes a copy of the given arc map for the newly
     1450    /// created graph.
     1451    /// The key type of the new map \c tmap should be the Arc type of the
     1452    /// destination graph, and the key type of the original map \c map
     1453    /// should be the Arc type of the source graph.
     1454    template <typename FromMap, typename ToMap>
     1455    BpGraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
     1456      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
     1457                          ArcRefMap, FromMap, ToMap>(map, tmap));
     1458      return *this;
     1459    }
     1460
     1461    /// \brief Make a copy of the given arc.
     1462    ///
     1463    /// This function makes a copy of the given arc.
     1464    BpGraphCopy& arc(const Arc& arc, TArc& tarc) {
     1465      _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
     1466                          ArcRefMap, TArc>(arc, tarc));
     1467      return *this;
     1468    }
     1469
     1470    /// \brief Copy the edge references into the given map.
     1471    ///
     1472    /// This function copies the edge references into the given map.
     1473    /// The parameter should be a map, whose key type is the Edge type of
     1474    /// the source graph, while the value type is the Edge type of the
     1475    /// destination graph.
     1476    template <typename EdgeRef>
     1477    BpGraphCopy& edgeRef(EdgeRef& map) {
     1478      _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
     1479                           EdgeRefMap, EdgeRef>(map));
     1480      return *this;
     1481    }
     1482
     1483    /// \brief Copy the edge cross references into the given map.
     1484    ///
     1485    /// This function copies the edge cross references (reverse references)
     1486    /// into the given map. The parameter should be a map, whose key type
     1487    /// is the Edge type of the destination graph, while the value type is
     1488    /// the Edge type of the source graph.
     1489    template <typename EdgeCrossRef>
     1490    BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
     1491      _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
     1492                           Edge, EdgeRefMap, EdgeCrossRef>(map));
     1493      return *this;
     1494    }
     1495
     1496    /// \brief Make a copy of the given edge map.
     1497    ///
     1498    /// This function makes a copy of the given edge map for the newly
     1499    /// created graph.
     1500    /// The key type of the new map \c tmap should be the Edge type of the
     1501    /// destination graph, and the key type of the original map \c map
     1502    /// should be the Edge type of the source graph.
     1503    template <typename FromMap, typename ToMap>
     1504    BpGraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
     1505      _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
     1506                           EdgeRefMap, FromMap, ToMap>(map, tmap));
     1507      return *this;
     1508    }
     1509
     1510    /// \brief Make a copy of the given edge.
     1511    ///
     1512    /// This function makes a copy of the given edge.
     1513    BpGraphCopy& edge(const Edge& edge, TEdge& tedge) {
     1514      _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
     1515                           EdgeRefMap, TEdge>(edge, tedge));
     1516      return *this;
     1517    }
     1518
     1519    /// \brief Execute copying.
     1520    ///
     1521    /// This function executes the copying of the graph along with the
     1522    /// copying of the assigned data.
     1523    void run() {
     1524      RedNodeRefMap redNodeRefMap(_from);
     1525      BlueNodeRefMap blueNodeRefMap(_from);
     1526      NodeRefMap nodeRefMap(_from, redNodeRefMap, blueNodeRefMap);
     1527      EdgeRefMap edgeRefMap(_from);
     1528      ArcRefMap arcRefMap(_from, _to, edgeRefMap);
     1529      _core_bits::BpGraphCopySelector<To>::
     1530        copy(_from, _to, redNodeRefMap, blueNodeRefMap, edgeRefMap);
     1531      for (int i = 0; i < int(_node_maps.size()); ++i) {
     1532        _node_maps[i]->copy(_from, nodeRefMap);
     1533      }
     1534      for (int i = 0; i < int(_red_maps.size()); ++i) {
     1535        _red_maps[i]->copy(_from, redNodeRefMap);
     1536      }
     1537      for (int i = 0; i < int(_blue_maps.size()); ++i) {
     1538        _blue_maps[i]->copy(_from, blueNodeRefMap);
     1539      }
     1540      for (int i = 0; i < int(_edge_maps.size()); ++i) {
     1541        _edge_maps[i]->copy(_from, edgeRefMap);
     1542      }
     1543      for (int i = 0; i < int(_arc_maps.size()); ++i) {
     1544        _arc_maps[i]->copy(_from, arcRefMap);
     1545      }
     1546    }
     1547
     1548  private:
     1549
     1550    const From& _from;
     1551    To& _to;
     1552
     1553    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
     1554      _node_maps;
     1555
     1556    std::vector<_core_bits::MapCopyBase<From, RedNode, RedNodeRefMap>* >
     1557      _red_maps;
     1558
     1559    std::vector<_core_bits::MapCopyBase<From, BlueNode, BlueNodeRefMap>* >
     1560      _blue_maps;
     1561
     1562    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
     1563      _arc_maps;
     1564
     1565    std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
     1566      _edge_maps;
     1567
     1568  };
     1569
     1570  /// \brief Copy a graph to another graph.
     1571  ///
     1572  /// This function copies a graph to another graph.
     1573  /// The complete usage of it is detailed in the BpGraphCopy class,
     1574  /// but a short example shows a basic work:
     1575  ///\code
     1576  /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
     1577  ///\endcode
     1578  ///
     1579  /// After the copy the \c nr map will contain the mapping from the
     1580  /// nodes of the \c from graph to the nodes of the \c to graph and
     1581  /// \c ecr will contain the mapping from the edges of the \c to graph
     1582  /// to the edges of the \c from graph.
     1583  ///
     1584  /// \see BpGraphCopy
     1585  template <typename From, typename To>
     1586  BpGraphCopy<From, To>
     1587  bpGraphCopy(const From& from, To& to) {
     1588    return BpGraphCopy<From, To>(from, to);
    9921589  }
    9931590
     
    12581855    /// The Digraph type
    12591856    typedef GR Digraph;
    1260 
     1857   
    12611858  protected:
    12621859
  • lemon/cost_scaling.h

    r1003 r1053  
    9292  /// \ref CostScaling implements a cost scaling algorithm that performs
    9393  /// push/augment and relabel operations for finding a \ref min_cost_flow
    94   /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
    95   /// \ref goldberg97efficient, \ref bunnagel98efficient.
     94  /// "minimum cost flow" \cite amo93networkflows, \cite goldberg90approximation,
     95  /// \cite goldberg97efficient, \cite bunnagel98efficient.
    9696  /// It is a highly efficient primal-dual solution method, which
    9797  /// can be viewed as the generalization of the \ref Preflow
    9898  /// "preflow push-relabel" algorithm for the maximum flow problem.
     99  /// It is a polynomial algorithm, its running time complexity is
     100  /// \f$O(n^2e\log(nK))\f$, where <i>K</i> denotes the maximum arc cost.
    99101  ///
    100102  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
     
    12701272          _buckets[r] = _bucket_next[u];
    12711273
    1272           // Search the incomming arcs of u
     1274          // Search the incoming arcs of u
    12731275          LargeCost pi_u = _pi[u];
    12741276          int last_out = _first_out[u+1];
  • lemon/cycle_canceling.h

    r1013 r1053  
    4848  /// \ref CycleCanceling implements three different cycle-canceling
    4949  /// algorithms for finding a \ref min_cost_flow "minimum cost flow"
    50   /// \ref amo93networkflows, \ref klein67primal,
    51   /// \ref goldberg89cyclecanceling.
     50  /// \cite amo93networkflows, \cite klein67primal,
     51  /// \cite goldberg89cyclecanceling.
    5252  /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
    5353  /// "Cancel-and-Tighten" algorithm, thus it is the default method.
    54   /// It runs in strongly polynomial time, but in practice, it is typically
    55   /// orders of magnitude slower than the scaling algorithms and
    56   /// \ref NetworkSimplex.
     54  /// It runs in strongly polynomial time O(n<sup>2</sup>e<sup>2</sup>log(n)),
     55  /// but in practice, it is typically orders of magnitude slower than
     56  /// the scaling algorithms and \ref NetworkSimplex.
    5757  /// (For more information, see \ref min_cost_flow_algs "the module page".)
    5858  ///
     
    132132      /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
    133133      /// well-known strongly polynomial method
    134       /// \ref goldberg89cyclecanceling. It improves along a
     134      /// \cite goldberg89cyclecanceling. It improves along a
    135135      /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
    136136      /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)).
     
    138138      /// The "Cancel-and-Tighten" algorithm, which can be viewed as an
    139139      /// improved version of the previous method
    140       /// \ref goldberg89cyclecanceling.
     140      /// \cite goldberg89cyclecanceling.
    141141      /// It is faster both in theory and in practice, its running time
    142142      /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).
  • lemon/full_graph.h

    r877 r1025  
    622622  };
    623623
     624  class FullBpGraphBase {
     625
     626  protected:
     627
     628    int _red_num, _blue_num;
     629    int _node_num, _edge_num;
     630
     631  public:
     632
     633    typedef FullBpGraphBase Graph;
     634
     635    class Node;
     636    class Arc;
     637    class Edge;
     638
     639    class Node {
     640      friend class FullBpGraphBase;
     641    protected:
     642
     643      int _id;
     644      explicit Node(int id) { _id = id;}
     645
     646    public:
     647      Node() {}
     648      Node (Invalid) { _id = -1; }
     649      bool operator==(const Node& node) const {return _id == node._id;}
     650      bool operator!=(const Node& node) const {return _id != node._id;}
     651      bool operator<(const Node& node) const {return _id < node._id;}
     652    };
     653
     654    class RedNode : public Node {
     655      friend class FullBpGraphBase;
     656    protected:
     657
     658      explicit RedNode(int pid) : Node(pid) {}
     659
     660    public:
     661      RedNode() {}
     662      RedNode(const RedNode& node) : Node(node) {}
     663      RedNode(Invalid) : Node(INVALID){}
     664    };
     665
     666    class BlueNode : public Node {
     667      friend class FullBpGraphBase;
     668    protected:
     669
     670      explicit BlueNode(int pid) : Node(pid) {}
     671
     672    public:
     673      BlueNode() {}
     674      BlueNode(const BlueNode& node) : Node(node) {}
     675      BlueNode(Invalid) : Node(INVALID){}
     676    };
     677
     678    class Edge {
     679      friend class FullBpGraphBase;
     680    protected:
     681
     682      int _id;
     683      explicit Edge(int id) { _id = id;}
     684
     685    public:
     686      Edge() {}
     687      Edge (Invalid) { _id = -1; }
     688      bool operator==(const Edge& arc) const {return _id == arc._id;}
     689      bool operator!=(const Edge& arc) const {return _id != arc._id;}
     690      bool operator<(const Edge& arc) const {return _id < arc._id;}
     691    };
     692
     693    class Arc {
     694      friend class FullBpGraphBase;
     695    protected:
     696
     697      int _id;
     698      explicit Arc(int id) { _id = id;}
     699
     700    public:
     701      operator Edge() const {
     702        return _id != -1 ? edgeFromId(_id / 2) : INVALID;
     703      }
     704
     705      Arc() {}
     706      Arc (Invalid) { _id = -1; }
     707      bool operator==(const Arc& arc) const {return _id == arc._id;}
     708      bool operator!=(const Arc& arc) const {return _id != arc._id;}
     709      bool operator<(const Arc& arc) const {return _id < arc._id;}
     710    };
     711
     712
     713  protected:
     714
     715    FullBpGraphBase()
     716      : _red_num(0), _blue_num(0), _node_num(0), _edge_num(0) {}
     717
     718    void construct(int redNum, int blueNum) {
     719      _red_num = redNum; _blue_num = blueNum;
     720      _node_num = redNum + blueNum; _edge_num = redNum * blueNum;
     721    }
     722
     723  public:
     724
     725    typedef True NodeNumTag;
     726    typedef True EdgeNumTag;
     727    typedef True ArcNumTag;
     728
     729    int nodeNum() const { return _node_num; }
     730    int redNum() const { return _red_num; }
     731    int blueNum() const { return _blue_num; }
     732    int edgeNum() const { return _edge_num; }
     733    int arcNum() const { return 2 * _edge_num; }
     734
     735    int maxNodeId() const { return _node_num - 1; }
     736    int maxRedId() const { return _red_num - 1; }
     737    int maxBlueId() const { return _blue_num - 1; }
     738    int maxEdgeId() const { return _edge_num - 1; }
     739    int maxArcId() const { return 2 * _edge_num - 1; }
     740
     741    bool red(Node n) const { return n._id < _red_num; }
     742    bool blue(Node n) const { return n._id >= _red_num; }
     743
     744    static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
     745    static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
     746
     747    Node source(Arc a) const {
     748      if (a._id & 1) {
     749        return Node((a._id >> 1) % _red_num);
     750      } else {
     751        return Node((a._id >> 1) / _red_num + _red_num);
     752      }
     753    }
     754    Node target(Arc a) const {
     755      if (a._id & 1) {
     756        return Node((a._id >> 1) / _red_num + _red_num);
     757      } else {
     758        return Node((a._id >> 1) % _red_num);
     759      }
     760    }
     761
     762    RedNode redNode(Edge e) const {
     763      return RedNode(e._id % _red_num);
     764    }
     765    BlueNode blueNode(Edge e) const {
     766      return BlueNode(e._id / _red_num + _red_num);
     767    }
     768
     769    static bool direction(Arc a) {
     770      return (a._id & 1) == 1;
     771    }
     772
     773    static Arc direct(Edge e, bool d) {
     774      return Arc(e._id * 2 + (d ? 1 : 0));
     775    }
     776
     777    void first(Node& node) const {
     778      node._id = _node_num - 1;
     779    }
     780
     781    static void next(Node& node) {
     782      --node._id;
     783    }
     784
     785    void first(RedNode& node) const {
     786      node._id = _red_num - 1;
     787    }
     788
     789    static void next(RedNode& node) {
     790      --node._id;
     791    }
     792
     793    void first(BlueNode& node) const {
     794      if (_red_num == _node_num) node._id = -1;
     795      else node._id = _node_num - 1;
     796    }
     797
     798    void next(BlueNode& node) const {
     799      if (node._id == _red_num) node._id = -1;
     800      else --node._id;
     801    }
     802
     803    void first(Arc& arc) const {
     804      arc._id = 2 * _edge_num - 1;
     805    }
     806
     807    static void next(Arc& arc) {
     808      --arc._id;
     809    }
     810
     811    void first(Edge& arc) const {
     812      arc._id = _edge_num - 1;
     813    }
     814
     815    static void next(Edge& arc) {
     816      --arc._id;
     817    }
     818
     819    void firstOut(Arc &a, const Node& v) const {
     820      if (v._id < _red_num) {
     821        a._id = 2 * (v._id + _red_num * (_blue_num - 1)) + 1;
     822      } else {
     823        a._id = 2 * (_red_num - 1 + _red_num * (v._id - _red_num));
     824      }
     825    }
     826    void nextOut(Arc &a) const {
     827      if (a._id & 1) {
     828        a._id -= 2 * _red_num;
     829        if (a._id < 0) a._id = -1;
     830      } else {
     831        if (a._id % (2 * _red_num) == 0) a._id = -1;
     832        else a._id -= 2;
     833      }
     834    }
     835
     836    void firstIn(Arc &a, const Node& v) const {
     837      if (v._id < _red_num) {
     838        a._id = 2 * (v._id + _red_num * (_blue_num - 1));
     839      } else {
     840        a._id = 2 * (_red_num - 1 + _red_num * (v._id - _red_num)) + 1;
     841      }
     842    }
     843    void nextIn(Arc &a) const {
     844      if (a._id & 1) {
     845        if (a._id % (2 * _red_num) == 1) a._id = -1;
     846        else a._id -= 2;
     847      } else {
     848        a._id -= 2 * _red_num;
     849        if (a._id < 0) a._id = -1;
     850      }
     851    }
     852
     853    void firstInc(Edge &e, bool& d, const Node& v) const {
     854      if (v._id < _red_num) {
     855        d = true;
     856        e._id = v._id + _red_num * (_blue_num - 1);
     857      } else {
     858        d = false;
     859        e._id = _red_num - 1 + _red_num * (v._id - _red_num);
     860      }
     861    }
     862    void nextInc(Edge &e, bool& d) const {
     863      if (d) {
     864        e._id -= _red_num;
     865        if (e._id < 0) e._id = -1;
     866      } else {
     867        if (e._id % _red_num == 0) e._id = -1;
     868        else --e._id;
     869      }
     870    }
     871
     872    static int id(const Node& v) { return v._id; }
     873    int id(const RedNode& v) const { return v._id; }
     874    int id(const BlueNode& v) const { return v._id - _red_num; }
     875    static int id(Arc e) { return e._id; }
     876    static int id(Edge e) { return e._id; }
     877   
     878    static Node nodeFromId(int id) { return Node(id);}
     879    static Arc arcFromId(int id) { return Arc(id);}
     880    static Edge edgeFromId(int id) { return Edge(id);}
     881
     882    bool valid(Node n) const {
     883      return n._id >= 0 && n._id < _node_num;
     884    }
     885    bool valid(Arc a) const {
     886      return a._id >= 0 && a._id < 2 * _edge_num;
     887    }
     888    bool valid(Edge e) const {
     889      return e._id >= 0 && e._id < _edge_num;
     890    }
     891
     892    RedNode redNode(int index) const {
     893      return RedNode(index);
     894    }
     895
     896    int index(RedNode n) const {
     897      return n._id;
     898    }
     899
     900    BlueNode blueNode(int index) const {
     901      return BlueNode(index + _red_num);
     902    }
     903
     904    int index(BlueNode n) const {
     905      return n._id - _red_num;
     906    }
     907       
     908    void clear() {
     909      _red_num = 0; _blue_num = 0;
     910      _node_num = 0; _edge_num = 0;
     911    }
     912
     913    Edge edge(const Node& u, const Node& v) const {
     914      if (u._id < _red_num) {
     915        if (v._id < _red_num) {
     916          return Edge(-1);
     917        } else {
     918          return Edge(u._id + _red_num * (v._id - _red_num));
     919        }
     920      } else {
     921        if (v._id < _red_num) {
     922          return Edge(v._id + _red_num * (u._id - _red_num));
     923        } else {
     924          return Edge(-1);
     925        }
     926      }
     927    }
     928
     929    Arc arc(const Node& u, const Node& v) const {
     930      if (u._id < _red_num) {
     931        if (v._id < _red_num) {
     932          return Arc(-1);
     933        } else {
     934          return Arc(2 * (u._id + _red_num * (v._id - _red_num)) + 1);
     935        }
     936      } else {
     937        if (v._id < _red_num) {
     938          return Arc(2 * (v._id + _red_num * (u._id - _red_num)));
     939        } else {
     940          return Arc(-1);
     941        }
     942      }
     943    }
     944
     945    typedef True FindEdgeTag;
     946    typedef True FindArcTag;
     947
     948    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
     949      return prev != INVALID ? INVALID : edge(u, v);
     950    }
     951
     952    Arc findArc(Node s, Node t, Arc prev = INVALID) const {
     953      return prev != INVALID ? INVALID : arc(s, t);
     954    }
     955
     956  };
     957
     958  typedef BpGraphExtender<FullBpGraphBase> ExtendedFullBpGraphBase;
     959
     960  /// \ingroup graphs
     961  ///
     962  /// \brief An undirected full bipartite graph class.
     963  ///
     964  /// FullBpGraph is a simple and fast implmenetation of undirected
     965  /// full bipartite graphs. It contains an edge between every
     966  /// red-blue pairs of nodes, therefore the number of edges is
     967  /// <tt>nr*nb</tt>.  This class is completely static and it needs
     968  /// constant memory space.  Thus you can neither add nor delete
     969  /// nodes or edges, however the structure can be resized using
     970  /// resize().
     971  ///
     972  /// This type fully conforms to the \ref concepts::BpGraph "BpGraph concept".
     973  /// Most of its member functions and nested classes are documented
     974  /// only in the concept class.
     975  ///
     976  /// This class provides constant time counting for nodes, edges and arcs.
     977  ///
     978  /// \sa FullGraph
     979  class FullBpGraph : public ExtendedFullBpGraphBase {
     980  public:
     981
     982    typedef ExtendedFullBpGraphBase Parent;
     983
     984    /// \brief Default constructor.
     985    ///
     986    /// Default constructor. The number of nodes and edges will be zero.
     987    FullBpGraph() { construct(0, 0); }
     988
     989    /// \brief Constructor
     990    ///
     991    /// Constructor.
     992    /// \param redNum The number of the red nodes.
     993    /// \param blueNum The number of the blue nodes.
     994    FullBpGraph(int redNum, int blueNum) { construct(redNum, blueNum); }
     995
     996    /// \brief Resizes the graph
     997    ///
     998    /// This function resizes the graph. It fully destroys and
     999    /// rebuilds the structure, therefore the maps of the graph will be
     1000    /// reallocated automatically and the previous values will be lost.
     1001    void resize(int redNum, int blueNum) {
     1002      Parent::notifier(Arc()).clear();
     1003      Parent::notifier(Edge()).clear();
     1004      Parent::notifier(Node()).clear();
     1005      Parent::notifier(BlueNode()).clear();
     1006      Parent::notifier(RedNode()).clear();
     1007      construct(redNum, blueNum);
     1008      Parent::notifier(RedNode()).build();
     1009      Parent::notifier(BlueNode()).build();
     1010      Parent::notifier(Node()).build();
     1011      Parent::notifier(Edge()).build();
     1012      Parent::notifier(Arc()).build();
     1013    }
     1014
     1015    using Parent::redNode;
     1016    using Parent::blueNode;
     1017
     1018    /// \brief Returns the red node with the given index.
     1019    ///
     1020    /// Returns the red node with the given index. Since this
     1021    /// structure is completely static, the red nodes can be indexed
     1022    /// with integers from the range <tt>[0..redNum()-1]</tt>.
     1023    /// \sa redIndex()
     1024    RedNode redNode(int index) const { return Parent::redNode(index); }
     1025
     1026    /// \brief Returns the index of the given red node.
     1027    ///
     1028    /// Returns the index of the given red node. Since this structure
     1029    /// is completely static, the red nodes can be indexed with
     1030    /// integers from the range <tt>[0..redNum()-1]</tt>.
     1031    ///
     1032    /// \sa operator()()
     1033    int index(RedNode node) const { return Parent::index(node); }
     1034
     1035    /// \brief Returns the blue node with the given index.
     1036    ///
     1037    /// Returns the blue node with the given index. Since this
     1038    /// structure is completely static, the blue nodes can be indexed
     1039    /// with integers from the range <tt>[0..blueNum()-1]</tt>.
     1040    /// \sa blueIndex()
     1041    BlueNode blueNode(int index) const { return Parent::blueNode(index); }
     1042
     1043    /// \brief Returns the index of the given blue node.
     1044    ///
     1045    /// Returns the index of the given blue node. Since this structure
     1046    /// is completely static, the blue nodes can be indexed with
     1047    /// integers from the range <tt>[0..blueNum()-1]</tt>.
     1048    ///
     1049    /// \sa operator()()
     1050    int index(BlueNode node) const { return Parent::index(node); }
     1051
     1052    /// \brief Returns the edge which connects the given nodes.
     1053    ///
     1054    /// Returns the edge which connects the given nodes.
     1055    Edge edge(const Node& u, const Node& v) const {
     1056      return Parent::edge(u, v);
     1057    }
     1058
     1059    /// \brief Returns the arc which connects the given nodes.
     1060    ///
     1061    /// Returns the arc which connects the given nodes.
     1062    Arc arc(const Node& u, const Node& v) const {
     1063      return Parent::arc(u, v);
     1064    }
     1065
     1066    /// \brief Number of nodes.
     1067    int nodeNum() const { return Parent::nodeNum(); }
     1068    /// \brief Number of red nodes.
     1069    int redNum() const { return Parent::redNum(); }
     1070    /// \brief Number of blue nodes.
     1071    int blueNum() const { return Parent::blueNum(); }
     1072    /// \brief Number of arcs.
     1073    int arcNum() const { return Parent::arcNum(); }
     1074    /// \brief Number of edges.
     1075    int edgeNum() const { return Parent::edgeNum(); }
     1076  };
     1077
    6241078
    6251079} //namespace lemon
  • lemon/grosso_locatelli_pullan_mc.h

    r918 r1053  
    4141  /// \ref GrossoLocatelliPullanMc implements the iterated local search
    4242  /// algorithm of Grosso, Locatelli, and Pullan for solving the \e maximum
    43   /// \e clique \e problem \ref grosso08maxclique.
     43  /// \e clique \e problem \cite grosso08maxclique.
    4444  /// It is to find the largest complete subgraph (\e clique) in an
    4545  /// undirected graph, i.e., the largest set of nodes where each
  • lemon/hartmann_orlin_mmc.h

    r1002 r1053  
    9999  /// This class implements the Hartmann-Orlin algorithm for finding
    100100  /// a directed cycle of minimum mean cost in a digraph
    101   /// \ref hartmann93finding, \ref dasdan98minmeancycle.
    102   /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm,
    103   /// it applies an efficient early termination scheme.
    104   /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
     101  /// \cite hartmann93finding, \cite dasdan98minmeancycle.
     102  /// This method is based on \ref KarpMmc "Karp"'s original algorithm, but
     103  /// applies an early termination scheme. It makes the algorithm
     104  /// significantly faster for some problem instances, but slower for others.
     105  /// The algorithm runs in time O(ne) and uses space O(n<sup>2</sup>+e).
    105106  ///
    106107  /// \tparam GR The type of the digraph the algorithm runs on.
     
    275276    ///
    276277    /// If you don't call this function before calling \ref run() or
    277     /// \ref findCycleMean(), it will allocate a local \ref Path "path"
    278     /// structure. The destuctor deallocates this automatically
     278    /// \ref findCycleMean(), a local \ref Path "path" structure
     279    /// will be allocated. The destuctor deallocates this automatically
    279280    /// allocated object, of course.
    280281    ///
  • lemon/howard_mmc.h

    r1012 r1053  
    9999  /// This class implements Howard's policy iteration algorithm for finding
    100100  /// a directed cycle of minimum mean cost in a digraph
    101   /// \ref dasdan98minmeancycle, \ref dasdan04experimental.
     101  /// \cite dasdan98minmeancycle, \cite dasdan04experimental.
    102102  /// This class provides the most efficient algorithm for the
    103103  /// minimum mean cycle problem, though the best known theoretical
     
    283283    ///
    284284    /// If you don't call this function before calling \ref run() or
    285     /// \ref findCycleMean(), it will allocate a local \ref Path "path"
    286     /// structure. The destuctor deallocates this automatically
     285    /// \ref findCycleMean(), a local \ref Path "path" structure
     286    /// will be allocated. The destuctor deallocates this automatically
    287287    /// allocated object, of course.
    288288    ///
  • lemon/karp_mmc.h

    r1002 r1053  
    9999  /// This class implements Karp's algorithm for finding a directed
    100100  /// cycle of minimum mean cost in a digraph
    101   /// \ref karp78characterization, \ref dasdan98minmeancycle.
     101  /// \cite karp78characterization, \cite dasdan98minmeancycle.
    102102  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
    103103  ///
     
    271271    ///
    272272    /// If you don't call this function before calling \ref run() or
    273     /// \ref findCycleMean(), it will allocate a local \ref Path "path"
    274     /// structure. The destuctor deallocates this automatically
     273    /// \ref findCycleMean(), a local \ref Path "path" structure
     274    /// will be allocated. The destuctor deallocates this automatically
    275275    /// allocated object, of course.
    276276    ///
  • lemon/lgf_reader.h

    r966 r1030  
    155155    };
    156156
    157     template <typename Value>
     157    template <typename Value,
     158              typename Map = std::map<std::string, Value> >
    158159    struct MapLookUpConverter {
    159       const std::map<std::string, Value>& _map;
    160 
    161       MapLookUpConverter(const std::map<std::string, Value>& map)
     160      const Map& _map;
     161
     162      MapLookUpConverter(const Map& map)
    162163        : _map(map) {}
    163164
    164165      Value operator()(const std::string& str) {
    165         typename std::map<std::string, Value>::const_iterator it =
    166           _map.find(str);
     166        typename Map::const_iterator it = _map.find(str);
    167167        if (it == _map.end()) {
    168168          std::ostringstream msg;
     
    171171        }
    172172        return it->second;
     173      }
     174    };
     175
     176    template <typename Value,
     177              typename Map1 = std::map<std::string, Value>,
     178              typename Map2 = std::map<std::string, Value> >
     179    struct DoubleMapLookUpConverter {
     180      const Map1& _map1;
     181      const Map2& _map2;
     182
     183      DoubleMapLookUpConverter(const Map1& map1, const Map2& map2)
     184        : _map1(map1), _map2(map2) {}
     185
     186      Value operator()(const std::string& str) {
     187        typename Map1::const_iterator it1 = _map1.find(str);
     188        typename Map2::const_iterator it2 = _map2.find(str);
     189        if (it1 == _map1.end()) {
     190          if (it2 == _map2.end()) {
     191            std::ostringstream msg;
     192            msg << "Item not found: " << str;
     193            throw FormatError(msg.str());
     194          } else {
     195            return it2->second;
     196          }
     197        } else {
     198          if (it2 == _map2.end()) {
     199            return it1->second;
     200          } else {
     201            std::ostringstream msg;
     202            msg << "Item is ambigous: " << str;
     203            throw FormatError(msg.str());
     204          }
     205        }
    173206      }
    174207    };
     
    21292162  }
    21302163
     2164  template <typename BGR>
     2165  class BpGraphReader;
     2166
     2167  template <typename TBGR>
     2168  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is = std::cin);
     2169  template <typename TBGR>
     2170  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const std::string& fn);
     2171  template <typename TBGR>
     2172  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char *fn);
     2173
     2174  /// \ingroup lemon_io
     2175  ///
     2176  /// \brief \ref lgf-format "LGF" reader for bipartite graphs
     2177  ///
     2178  /// This utility reads an \ref lgf-format "LGF" file.
     2179  ///
     2180  /// It can be used almost the same way as \c GraphReader, but it
     2181  /// reads the red and blue nodes from separate sections, and these
     2182  /// sections can contain different set of maps.
     2183  ///
     2184  /// The red and blue node maps are read from the corresponding
     2185  /// sections. If a map is defined with the same name in both of
     2186  /// these sections, then it can be read as a node map.
     2187  template <typename BGR>
     2188  class BpGraphReader {
     2189  public:
     2190
     2191    typedef BGR Graph;
     2192
     2193  private:
     2194
     2195    TEMPLATE_BPGRAPH_TYPEDEFS(BGR);
     2196
     2197    std::istream* _is;
     2198    bool local_is;
     2199    std::string _filename;
     2200
     2201    BGR& _graph;
     2202
     2203    std::string _nodes_caption;
     2204    std::string _edges_caption;
     2205    std::string _attributes_caption;
     2206
     2207    typedef std::map<std::string, RedNode> RedNodeIndex;
     2208    RedNodeIndex _red_node_index;
     2209    typedef std::map<std::string, BlueNode> BlueNodeIndex;
     2210    BlueNodeIndex _blue_node_index;
     2211    typedef std::map<std::string, Edge> EdgeIndex;
     2212    EdgeIndex _edge_index;
     2213
     2214    typedef std::vector<std::pair<std::string,
     2215      _reader_bits::MapStorageBase<RedNode>*> > RedNodeMaps;
     2216    RedNodeMaps _red_node_maps;
     2217    typedef std::vector<std::pair<std::string,
     2218      _reader_bits::MapStorageBase<BlueNode>*> > BlueNodeMaps;
     2219    BlueNodeMaps _blue_node_maps;
     2220
     2221    typedef std::vector<std::pair<std::string,
     2222      _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
     2223    EdgeMaps _edge_maps;
     2224
     2225    typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
     2226      Attributes;
     2227    Attributes _attributes;
     2228
     2229    bool _use_nodes;
     2230    bool _use_edges;
     2231
     2232    bool _skip_nodes;
     2233    bool _skip_edges;
     2234
     2235    int line_num;
     2236    std::istringstream line;
     2237
     2238  public:
     2239
     2240    /// \brief Constructor
     2241    ///
     2242    /// Construct an undirected graph reader, which reads from the given
     2243    /// input stream.
     2244    BpGraphReader(BGR& graph, std::istream& is = std::cin)
     2245      : _is(&is), local_is(false), _graph(graph),
     2246        _use_nodes(false), _use_edges(false),
     2247        _skip_nodes(false), _skip_edges(false) {}
     2248
     2249    /// \brief Constructor
     2250    ///
     2251    /// Construct an undirected graph reader, which reads from the given
     2252    /// file.
     2253    BpGraphReader(BGR& graph, const std::string& fn)
     2254      : _is(new std::ifstream(fn.c_str())), local_is(true),
     2255        _filename(fn), _graph(graph),
     2256        _use_nodes(false), _use_edges(false),
     2257        _skip_nodes(false), _skip_edges(false) {
     2258      if (!(*_is)) {
     2259        delete _is;
     2260        throw IoError("Cannot open file", fn);
     2261      }
     2262    }
     2263
     2264    /// \brief Constructor
     2265    ///
     2266    /// Construct an undirected graph reader, which reads from the given
     2267    /// file.
     2268    BpGraphReader(BGR& graph, const char* fn)
     2269      : _is(new std::ifstream(fn)), local_is(true),
     2270        _filename(fn), _graph(graph),
     2271        _use_nodes(false), _use_edges(false),
     2272        _skip_nodes(false), _skip_edges(false) {
     2273      if (!(*_is)) {
     2274        delete _is;
     2275        throw IoError("Cannot open file", fn);
     2276      }
     2277    }
     2278
     2279    /// \brief Destructor
     2280    ~BpGraphReader() {
     2281      for (typename RedNodeMaps::iterator it = _red_node_maps.begin();
     2282           it != _red_node_maps.end(); ++it) {
     2283        delete it->second;
     2284      }
     2285
     2286      for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin();
     2287           it != _blue_node_maps.end(); ++it) {
     2288        delete it->second;
     2289      }
     2290
     2291      for (typename EdgeMaps::iterator it = _edge_maps.begin();
     2292           it != _edge_maps.end(); ++it) {
     2293        delete it->second;
     2294      }
     2295
     2296      for (typename Attributes::iterator it = _attributes.begin();
     2297           it != _attributes.end(); ++it) {
     2298        delete it->second;
     2299      }
     2300
     2301      if (local_is) {
     2302        delete _is;
     2303      }
     2304
     2305    }
     2306
     2307  private:
     2308    template <typename TBGR>
     2309    friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is);
     2310    template <typename TBGR>
     2311    friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph,
     2312                                             const std::string& fn);
     2313    template <typename TBGR>
     2314    friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char *fn);
     2315
     2316    BpGraphReader(BpGraphReader& other)
     2317      : _is(other._is), local_is(other.local_is), _graph(other._graph),
     2318        _use_nodes(other._use_nodes), _use_edges(other._use_edges),
     2319        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
     2320
     2321      other._is = 0;
     2322      other.local_is = false;
     2323
     2324      _red_node_index.swap(other._red_node_index);
     2325      _blue_node_index.swap(other._blue_node_index);
     2326      _edge_index.swap(other._edge_index);
     2327
     2328      _red_node_maps.swap(other._red_node_maps);
     2329      _blue_node_maps.swap(other._blue_node_maps);
     2330      _edge_maps.swap(other._edge_maps);
     2331      _attributes.swap(other._attributes);
     2332
     2333      _nodes_caption = other._nodes_caption;
     2334      _edges_caption = other._edges_caption;
     2335      _attributes_caption = other._attributes_caption;
     2336
     2337    }
     2338
     2339    BpGraphReader& operator=(const BpGraphReader&);
     2340
     2341  public:
     2342
     2343    /// \name Reading Rules
     2344    /// @{
     2345
     2346    /// \brief Node map reading rule
     2347    ///
     2348    /// Add a node map reading rule to the reader.
     2349    template <typename Map>
     2350    BpGraphReader& nodeMap(const std::string& caption, Map& map) {
     2351      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
     2352      _reader_bits::MapStorageBase<RedNode>* red_storage =
     2353        new _reader_bits::MapStorage<RedNode, Map>(map);
     2354      _red_node_maps.push_back(std::make_pair(caption, red_storage));
     2355      _reader_bits::MapStorageBase<BlueNode>* blue_storage =
     2356        new _reader_bits::MapStorage<BlueNode, Map>(map);
     2357      _blue_node_maps.push_back(std::make_pair(caption, blue_storage));
     2358      return *this;
     2359    }
     2360
     2361    /// \brief Node map reading rule
     2362    ///
     2363    /// Add a node map reading rule with specialized converter to the
     2364    /// reader.
     2365    template <typename Map, typename Converter>
     2366    BpGraphReader& nodeMap(const std::string& caption, Map& map,
     2367                           const Converter& converter = Converter()) {
     2368      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
     2369      _reader_bits::MapStorageBase<RedNode>* red_storage =
     2370        new _reader_bits::MapStorage<RedNode, Map, Converter>(map, converter);
     2371      _red_node_maps.push_back(std::make_pair(caption, red_storage));
     2372      _reader_bits::MapStorageBase<BlueNode>* blue_storage =
     2373        new _reader_bits::MapStorage<BlueNode, Map, Converter>(map, converter);
     2374      _blue_node_maps.push_back(std::make_pair(caption, blue_storage));
     2375      return *this;
     2376    }
     2377
     2378    /// Add a red node map reading rule to the reader.
     2379    template <typename Map>
     2380    BpGraphReader& redNodeMap(const std::string& caption, Map& map) {
     2381      checkConcept<concepts::WriteMap<RedNode, typename Map::Value>, Map>();
     2382      _reader_bits::MapStorageBase<RedNode>* storage =
     2383        new _reader_bits::MapStorage<RedNode, Map>(map);
     2384      _red_node_maps.push_back(std::make_pair(caption, storage));
     2385      return *this;
     2386    }
     2387
     2388    /// \brief Red node map reading rule
     2389    ///
     2390    /// Add a red node map node reading rule with specialized converter to
     2391    /// the reader.
     2392    template <typename Map, typename Converter>
     2393    BpGraphReader& redNodeMap(const std::string& caption, Map& map,
     2394                              const Converter& converter = Converter()) {
     2395      checkConcept<concepts::WriteMap<RedNode, typename Map::Value>, Map>();
     2396      _reader_bits::MapStorageBase<RedNode>* storage =
     2397        new _reader_bits::MapStorage<RedNode, Map, Converter>(map, converter);
     2398      _red_node_maps.push_back(std::make_pair(caption, storage));
     2399      return *this;
     2400    }
     2401
     2402    /// Add a blue node map reading rule to the reader.
     2403    template <typename Map>
     2404    BpGraphReader& blueNodeMap(const std::string& caption, Map& map) {
     2405      checkConcept<concepts::WriteMap<BlueNode, typename Map::Value>, Map>();
     2406      _reader_bits::MapStorageBase<BlueNode>* storage =
     2407        new _reader_bits::MapStorage<BlueNode, Map>(map);
     2408      _blue_node_maps.push_back(std::make_pair(caption, storage));
     2409      return *this;
     2410    }
     2411
     2412    /// \brief Blue node map reading rule
     2413    ///
     2414    /// Add a blue node map reading rule with specialized converter to
     2415    /// the reader.
     2416    template <typename Map, typename Converter>
     2417    BpGraphReader& blueNodeMap(const std::string& caption, Map& map,
     2418                               const Converter& converter = Converter()) {
     2419      checkConcept<concepts::WriteMap<BlueNode, typename Map::Value>, Map>();
     2420      _reader_bits::MapStorageBase<BlueNode>* storage =
     2421        new _reader_bits::MapStorage<BlueNode, Map, Converter>(map, converter);
     2422      _blue_node_maps.push_back(std::make_pair(caption, storage));
     2423      return *this;
     2424    }
     2425
     2426    /// \brief Edge map reading rule
     2427    ///
     2428    /// Add an edge map reading rule to the reader.
     2429    template <typename Map>
     2430    BpGraphReader& edgeMap(const std::string& caption, Map& map) {
     2431      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
     2432      _reader_bits::MapStorageBase<Edge>* storage =
     2433        new _reader_bits::MapStorage<Edge, Map>(map);
     2434      _edge_maps.push_back(std::make_pair(caption, storage));
     2435      return *this;
     2436    }
     2437
     2438    /// \brief Edge map reading rule
     2439    ///
     2440    /// Add an edge map reading rule with specialized converter to the
     2441    /// reader.
     2442    template <typename Map, typename Converter>
     2443    BpGraphReader& edgeMap(const std::string& caption, Map& map,
     2444                          const Converter& converter = Converter()) {
     2445      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
     2446      _reader_bits::MapStorageBase<Edge>* storage =
     2447        new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
     2448      _edge_maps.push_back(std::make_pair(caption, storage));
     2449      return *this;
     2450    }
     2451
     2452    /// \brief Arc map reading rule
     2453    ///
     2454    /// Add an arc map reading rule to the reader.
     2455    template <typename Map>
     2456    BpGraphReader& arcMap(const std::string& caption, Map& map) {
     2457      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
     2458      _reader_bits::MapStorageBase<Edge>* forward_storage =
     2459        new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
     2460      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
     2461      _reader_bits::MapStorageBase<Edge>* backward_storage =
     2462        new _reader_bits::GraphArcMapStorage<BGR, false, Map>(_graph, map);
     2463      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
     2464      return *this;
     2465    }
     2466
     2467    /// \brief Arc map reading rule
     2468    ///
     2469    /// Add an arc map reading rule with specialized converter to the
     2470    /// reader.
     2471    template <typename Map, typename Converter>
     2472    BpGraphReader& arcMap(const std::string& caption, Map& map,
     2473                          const Converter& converter = Converter()) {
     2474      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
     2475      _reader_bits::MapStorageBase<Edge>* forward_storage =
     2476        new _reader_bits::GraphArcMapStorage<BGR, true, Map, Converter>
     2477        (_graph, map, converter);
     2478      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
     2479      _reader_bits::MapStorageBase<Edge>* backward_storage =
     2480        new _reader_bits::GraphArcMapStorage<BGR, false, Map, Converter>
     2481        (_graph, map, converter);
     2482      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
     2483      return *this;
     2484    }
     2485
     2486    /// \brief Attribute reading rule
     2487    ///
     2488    /// Add an attribute reading rule to the reader.
     2489    template <typename Value>
     2490    BpGraphReader& attribute(const std::string& caption, Value& value) {
     2491      _reader_bits::ValueStorageBase* storage =
     2492        new _reader_bits::ValueStorage<Value>(value);
     2493      _attributes.insert(std::make_pair(caption, storage));
     2494      return *this;
     2495    }
     2496
     2497    /// \brief Attribute reading rule
     2498    ///
     2499    /// Add an attribute reading rule with specialized converter to the
     2500    /// reader.
     2501    template <typename Value, typename Converter>
     2502    BpGraphReader& attribute(const std::string& caption, Value& value,
     2503                             const Converter& converter = Converter()) {
     2504      _reader_bits::ValueStorageBase* storage =
     2505        new _reader_bits::ValueStorage<Value, Converter>(value, converter);
     2506      _attributes.insert(std::make_pair(caption, storage));
     2507      return *this;
     2508    }
     2509
     2510    /// \brief Node reading rule
     2511    ///
     2512    /// Add a node reading rule to reader.
     2513    BpGraphReader& node(const std::string& caption, Node& node) {
     2514      typedef _reader_bits::DoubleMapLookUpConverter<
     2515        Node, RedNodeIndex, BlueNodeIndex> Converter;
     2516      Converter converter(_red_node_index, _blue_node_index);
     2517      _reader_bits::ValueStorageBase* storage =
     2518        new _reader_bits::ValueStorage<Node, Converter>(node, converter);
     2519      _attributes.insert(std::make_pair(caption, storage));
     2520      return *this;
     2521    }
     2522
     2523    /// \brief Red node reading rule
     2524    ///
     2525    /// Add a red node reading rule to reader.
     2526    BpGraphReader& redNode(const std::string& caption, RedNode& node) {
     2527      typedef _reader_bits::MapLookUpConverter<RedNode> Converter;
     2528      Converter converter(_red_node_index);
     2529      _reader_bits::ValueStorageBase* storage =
     2530        new _reader_bits::ValueStorage<RedNode, Converter>(node, converter);
     2531      _attributes.insert(std::make_pair(caption, storage));
     2532      return *this;
     2533    }
     2534
     2535    /// \brief Blue node reading rule
     2536    ///
     2537    /// Add a blue node reading rule to reader.
     2538    BpGraphReader& blueNode(const std::string& caption, BlueNode& node) {
     2539      typedef _reader_bits::MapLookUpConverter<BlueNode> Converter;
     2540      Converter converter(_blue_node_index);
     2541      _reader_bits::ValueStorageBase* storage =
     2542        new _reader_bits::ValueStorage<BlueNode, Converter>(node, converter);
     2543      _attributes.insert(std::make_pair(caption, storage));
     2544      return *this;
     2545    }
     2546
     2547    /// \brief Edge reading rule
     2548    ///
     2549    /// Add an edge reading rule to reader.
     2550    BpGraphReader& edge(const std::string& caption, Edge& edge) {
     2551      typedef _reader_bits::MapLookUpConverter<Edge> Converter;
     2552      Converter converter(_edge_index);
     2553      _reader_bits::ValueStorageBase* storage =
     2554        new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
     2555      _attributes.insert(std::make_pair(caption, storage));
     2556      return *this;
     2557    }
     2558
     2559    /// \brief Arc reading rule
     2560    ///
     2561    /// Add an arc reading rule to reader.
     2562    BpGraphReader& arc(const std::string& caption, Arc& arc) {
     2563      typedef _reader_bits::GraphArcLookUpConverter<BGR> Converter;
     2564      Converter converter(_graph, _edge_index);
     2565      _reader_bits::ValueStorageBase* storage =
     2566        new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
     2567      _attributes.insert(std::make_pair(caption, storage));
     2568      return *this;
     2569    }
     2570
     2571    /// @}
     2572
     2573    /// \name Select Section by Name
     2574    /// @{
     2575
     2576    /// \brief Set \c \@nodes section to be read
     2577    ///
     2578    /// Set \c \@nodes section to be read.
     2579    BpGraphReader& nodes(const std::string& caption) {
     2580      _nodes_caption = caption;
     2581      return *this;
     2582    }
     2583
     2584    /// \brief Set \c \@edges section to be read
     2585    ///
     2586    /// Set \c \@edges section to be read.
     2587    BpGraphReader& edges(const std::string& caption) {
     2588      _edges_caption = caption;
     2589      return *this;
     2590    }
     2591
     2592    /// \brief Set \c \@attributes section to be read
     2593    ///
     2594    /// Set \c \@attributes section to be read.
     2595    BpGraphReader& attributes(const std::string& caption) {
     2596      _attributes_caption = caption;
     2597      return *this;
     2598    }
     2599
     2600    /// @}
     2601
     2602    /// \name Using Previously Constructed Node or Edge Set
     2603    /// @{
     2604
     2605    /// \brief Use previously constructed node set
     2606    ///
     2607    /// Use previously constructed node set, and specify the node
     2608    /// label map.
     2609    template <typename Map>
     2610    BpGraphReader& useNodes(const Map& map) {
     2611      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
     2612      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
     2613      _use_nodes = true;
     2614      _writer_bits::DefaultConverter<typename Map::Value> converter;
     2615      for (RedNodeIt n(_graph); n != INVALID; ++n) {
     2616        _red_node_index.insert(std::make_pair(converter(map[n]), n));
     2617      }
     2618      for (BlueNodeIt n(_graph); n != INVALID; ++n) {
     2619        _blue_node_index.insert(std::make_pair(converter(map[n]), n));
     2620      }
     2621      return *this;
     2622    }
     2623
     2624    /// \brief Use previously constructed node set
     2625    ///
     2626    /// Use previously constructed node set, and specify the node
     2627    /// label map and a functor which converts the label map values to
     2628    /// \c std::string.
     2629    template <typename Map, typename Converter>
     2630    BpGraphReader& useNodes(const Map& map,
     2631                            const Converter& converter = Converter()) {
     2632      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
     2633      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
     2634      _use_nodes = true;
     2635      for (RedNodeIt n(_graph); n != INVALID; ++n) {
     2636        _red_node_index.insert(std::make_pair(converter(map[n]), n));
     2637      }
     2638      for (BlueNodeIt n(_graph); n != INVALID; ++n) {     
     2639        _blue_node_index.insert(std::make_pair(converter(map[n]), n));
     2640      }
     2641      return *this;
     2642    }
     2643
     2644    /// \brief Use previously constructed edge set
     2645    ///
     2646    /// Use previously constructed edge set, and specify the edge
     2647    /// label map.
     2648    template <typename Map>
     2649    BpGraphReader& useEdges(const Map& map) {
     2650      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
     2651      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
     2652      _use_edges = true;
     2653      _writer_bits::DefaultConverter<typename Map::Value> converter;
     2654      for (EdgeIt a(_graph); a != INVALID; ++a) {
     2655        _edge_index.insert(std::make_pair(converter(map[a]), a));
     2656      }
     2657      return *this;
     2658    }
     2659
     2660    /// \brief Use previously constructed edge set
     2661    ///
     2662    /// Use previously constructed edge set, and specify the edge
     2663    /// label map and a functor which converts the label map values to
     2664    /// \c std::string.
     2665    template <typename Map, typename Converter>
     2666    BpGraphReader& useEdges(const Map& map,
     2667                            const Converter& converter = Converter()) {
     2668      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
     2669      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
     2670      _use_edges = true;
     2671      for (EdgeIt a(_graph); a != INVALID; ++a) {
     2672        _edge_index.insert(std::make_pair(converter(map[a]), a));
     2673      }
     2674      return *this;
     2675    }
     2676
     2677    /// \brief Skip the reading of node section
     2678    ///
     2679    /// Omit the reading of the node section. This implies that each node
     2680    /// map reading rule will be abandoned, and the nodes of the graph
     2681    /// will not be constructed, which usually cause that the edge set
     2682    /// could not be read due to lack of node name
     2683    /// could not be read due to lack of node name resolving.
     2684    /// Therefore \c skipEdges() function should also be used, or
     2685    /// \c useNodes() should be used to specify the label of the nodes.
     2686    BpGraphReader& skipNodes() {
     2687      LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
     2688      _skip_nodes = true;
     2689      return *this;
     2690    }
     2691
     2692    /// \brief Skip the reading of edge section
     2693    ///
     2694    /// Omit the reading of the edge section. This implies that each edge
     2695    /// map reading rule will be abandoned, and the edges of the graph
     2696    /// will not be constructed.
     2697    BpGraphReader& skipEdges() {
     2698      LEMON_ASSERT(!_skip_edges, "Skip edges already set");
     2699      _skip_edges = true;
     2700      return *this;
     2701    }
     2702
     2703    /// @}
     2704
     2705  private:
     2706
     2707    bool readLine() {
     2708      std::string str;
     2709      while(++line_num, std::getline(*_is, str)) {
     2710        line.clear(); line.str(str);
     2711        char c;
     2712        if (line >> std::ws >> c && c != '#') {
     2713          line.putback(c);
     2714          return true;
     2715        }
     2716      }
     2717      return false;
     2718    }
     2719
     2720    bool readSuccess() {
     2721      return static_cast<bool>(*_is);
     2722    }
     2723
     2724    void skipSection() {
     2725      char c;
     2726      while (readSuccess() && line >> c && c != '@') {
     2727        readLine();
     2728      }
     2729      if (readSuccess()) {
     2730        line.putback(c);
     2731      }
     2732    }
     2733
     2734    void readRedNodes() {
     2735
     2736      std::vector<int> map_index(_red_node_maps.size());
     2737      int map_num, label_index;
     2738
     2739      char c;
     2740      if (!readLine() || !(line >> c) || c == '@') {
     2741        if (readSuccess() && line) line.putback(c);
     2742        if (!_red_node_maps.empty())
     2743          throw FormatError("Cannot find map names");
     2744        return;
     2745      }
     2746      line.putback(c);
     2747
     2748      {
     2749        std::map<std::string, int> maps;
     2750
     2751        std::string map;
     2752        int index = 0;
     2753        while (_reader_bits::readToken(line, map)) {
     2754          if (maps.find(map) != maps.end()) {
     2755            std::ostringstream msg;
     2756            msg << "Multiple occurence of red node map: " << map;
     2757            throw FormatError(msg.str());
     2758          }
     2759          maps.insert(std::make_pair(map, index));
     2760          ++index;
     2761        }
     2762
     2763        for (int i = 0; i < static_cast<int>(_red_node_maps.size()); ++i) {
     2764          std::map<std::string, int>::iterator jt =
     2765            maps.find(_red_node_maps[i].first);
     2766          if (jt == maps.end()) {
     2767            std::ostringstream msg;
     2768            msg << "Map not found: " << _red_node_maps[i].first;
     2769            throw FormatError(msg.str());
     2770          }
     2771          map_index[i] = jt->second;
     2772        }
     2773
     2774        {
     2775          std::map<std::string, int>::iterator jt = maps.find("label");
     2776          if (jt != maps.end()) {
     2777            label_index = jt->second;
     2778          } else {
     2779            label_index = -1;
     2780          }
     2781        }
     2782        map_num = maps.size();
     2783      }
     2784
     2785      while (readLine() && line >> c && c != '@') {
     2786        line.putback(c);
     2787
     2788        std::vector<std::string> tokens(map_num);
     2789        for (int i = 0; i < map_num; ++i) {
     2790          if (!_reader_bits::readToken(line, tokens[i])) {
     2791            std::ostringstream msg;
     2792            msg << "Column not found (" << i + 1 << ")";
     2793            throw FormatError(msg.str());
     2794          }
     2795        }
     2796        if (line >> std::ws >> c)
     2797          throw FormatError("Extra character at the end of line");
     2798
     2799        RedNode n;
     2800        if (!_use_nodes) {
     2801          n = _graph.addRedNode();
     2802          if (label_index != -1)
     2803            _red_node_index.insert(std::make_pair(tokens[label_index], n));
     2804        } else {
     2805          if (label_index == -1)
     2806            throw FormatError("Label map not found");
     2807          typename std::map<std::string, RedNode>::iterator it =
     2808            _red_node_index.find(tokens[label_index]);
     2809          if (it == _red_node_index.end()) {
     2810            std::ostringstream msg;
     2811            msg << "Node with label not found: " << tokens[label_index];
     2812            throw FormatError(msg.str());
     2813          }
     2814          n = it->second;
     2815        }
     2816
     2817        for (int i = 0; i < static_cast<int>(_red_node_maps.size()); ++i) {
     2818          _red_node_maps[i].second->set(n, tokens[map_index[i]]);
     2819        }
     2820
     2821      }
     2822      if (readSuccess()) {
     2823        line.putback(c);
     2824      }
     2825    }
     2826
     2827    void readBlueNodes() {
     2828
     2829      std::vector<int> map_index(_blue_node_maps.size());
     2830      int map_num, label_index;
     2831
     2832      char c;
     2833      if (!readLine() || !(line >> c) || c == '@') {
     2834        if (readSuccess() && line) line.putback(c);
     2835        if (!_blue_node_maps.empty())
     2836          throw FormatError("Cannot find map names");
     2837        return;
     2838      }
     2839      line.putback(c);
     2840
     2841      {
     2842        std::map<std::string, int> maps;
     2843
     2844        std::string map;
     2845        int index = 0;
     2846        while (_reader_bits::readToken(line, map)) {
     2847          if (maps.find(map) != maps.end()) {
     2848            std::ostringstream msg;
     2849            msg << "Multiple occurence of blue node map: " << map;
     2850            throw FormatError(msg.str());
     2851          }
     2852          maps.insert(std::make_pair(map, index));
     2853          ++index;
     2854        }
     2855
     2856        for (int i = 0; i < static_cast<int>(_blue_node_maps.size()); ++i) {
     2857          std::map<std::string, int>::iterator jt =
     2858            maps.find(_blue_node_maps[i].first);
     2859          if (jt == maps.end()) {
     2860            std::ostringstream msg;
     2861            msg << "Map not found: " << _blue_node_maps[i].first;
     2862            throw FormatError(msg.str());
     2863          }
     2864          map_index[i] = jt->second;
     2865        }
     2866
     2867        {
     2868          std::map<std::string, int>::iterator jt = maps.find("label");
     2869          if (jt != maps.end()) {
     2870            label_index = jt->second;
     2871          } else {
     2872            label_index = -1;
     2873          }
     2874        }
     2875        map_num = maps.size();
     2876      }
     2877
     2878      while (readLine() && line >> c && c != '@') {
     2879        line.putback(c);
     2880
     2881        std::vector<std::string> tokens(map_num);
     2882        for (int i = 0; i < map_num; ++i) {
     2883          if (!_reader_bits::readToken(line, tokens[i])) {
     2884            std::ostringstream msg;
     2885            msg << "Column not found (" << i + 1 << ")";
     2886            throw FormatError(msg.str());
     2887          }
     2888        }
     2889        if (line >> std::ws >> c)
     2890          throw FormatError("Extra character at the end of line");
     2891
     2892        BlueNode n;
     2893        if (!_use_nodes) {
     2894          n = _graph.addBlueNode();
     2895          if (label_index != -1)
     2896            _blue_node_index.insert(std::make_pair(tokens[label_index], n));
     2897        } else {
     2898          if (label_index == -1)
     2899            throw FormatError("Label map not found");
     2900          typename std::map<std::string, BlueNode>::iterator it =
     2901            _blue_node_index.find(tokens[label_index]);
     2902          if (it == _blue_node_index.end()) {
     2903            std::ostringstream msg;
     2904            msg << "Node with label not found: " << tokens[label_index];
     2905            throw FormatError(msg.str());
     2906          }
     2907          n = it->second;
     2908        }
     2909
     2910        for (int i = 0; i < static_cast<int>(_blue_node_maps.size()); ++i) {
     2911          _blue_node_maps[i].second->set(n, tokens[map_index[i]]);
     2912        }
     2913
     2914      }
     2915      if (readSuccess()) {
     2916        line.putback(c);
     2917      }
     2918    }
     2919
     2920    void readEdges() {
     2921
     2922      std::vector<int> map_index(_edge_maps.size());
     2923      int map_num, label_index;
     2924
     2925      char c;
     2926      if (!readLine() || !(line >> c) || c == '@') {
     2927        if (readSuccess() && line) line.putback(c);
     2928        if (!_edge_maps.empty())
     2929          throw FormatError("Cannot find map names");
     2930        return;
     2931      }
     2932      line.putback(c);
     2933
     2934      {
     2935        std::map<std::string, int> maps;
     2936
     2937        std::string map;
     2938        int index = 0;
     2939        while (_reader_bits::readToken(line, map)) {
     2940          if (maps.find(map) != maps.end()) {
     2941            std::ostringstream msg;
     2942            msg << "Multiple occurence of edge map: " << map;
     2943            throw FormatError(msg.str());
     2944          }
     2945          maps.insert(std::make_pair(map, index));
     2946          ++index;
     2947        }
     2948
     2949        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
     2950          std::map<std::string, int>::iterator jt =
     2951            maps.find(_edge_maps[i].first);
     2952          if (jt == maps.end()) {
     2953            std::ostringstream msg;
     2954            msg << "Map not found: " << _edge_maps[i].first;
     2955            throw FormatError(msg.str());
     2956          }
     2957          map_index[i] = jt->second;
     2958        }
     2959
     2960        {
     2961          std::map<std::string, int>::iterator jt = maps.find("label");
     2962          if (jt != maps.end()) {
     2963            label_index = jt->second;
     2964          } else {
     2965            label_index = -1;
     2966          }
     2967        }
     2968        map_num = maps.size();
     2969      }
     2970
     2971      while (readLine() && line >> c && c != '@') {
     2972        line.putback(c);
     2973
     2974        std::string source_token;
     2975        std::string target_token;
     2976
     2977        if (!_reader_bits::readToken(line, source_token))
     2978          throw FormatError("Red node not found");
     2979
     2980        if (!_reader_bits::readToken(line, target_token))
     2981          throw FormatError("Blue node not found");
     2982
     2983        std::vector<std::string> tokens(map_num);
     2984        for (int i = 0; i < map_num; ++i) {
     2985          if (!_reader_bits::readToken(line, tokens[i])) {
     2986            std::ostringstream msg;
     2987            msg << "Column not found (" << i + 1 << ")";
     2988            throw FormatError(msg.str());
     2989          }
     2990        }
     2991        if (line >> std::ws >> c)
     2992          throw FormatError("Extra character at the end of line");
     2993
     2994        Edge e;
     2995        if (!_use_edges) {
     2996          typename RedNodeIndex::iterator rit =
     2997            _red_node_index.find(source_token);
     2998          if (rit == _red_node_index.end()) {
     2999            std::ostringstream msg;
     3000            msg << "Item not found: " << source_token;
     3001            throw FormatError(msg.str());
     3002          }
     3003          RedNode source = rit->second;
     3004          typename BlueNodeIndex::iterator it =
     3005            _blue_node_index.find(target_token);
     3006          if (it == _blue_node_index.end()) {
     3007            std::ostringstream msg;
     3008            msg << "Item not found: " << target_token;
     3009            throw FormatError(msg.str());
     3010          }
     3011          BlueNode target = it->second;
     3012
     3013          // It is checked that source is red and
     3014          // target is blue, so this should be safe:
     3015          e = _graph.addEdge(source, target);
     3016          if (label_index != -1)
     3017            _edge_index.insert(std::make_pair(tokens[label_index], e));
     3018        } else {
     3019          if (label_index == -1)
     3020            throw FormatError("Label map not found");
     3021          typename std::map<std::string, Edge>::iterator it =
     3022            _edge_index.find(tokens[label_index]);
     3023          if (it == _edge_index.end()) {
     3024            std::ostringstream msg;
     3025            msg << "Edge with label not found: " << tokens[label_index];
     3026            throw FormatError(msg.str());
     3027          }
     3028          e = it->second;
     3029        }
     3030
     3031        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
     3032          _edge_maps[i].second->set(e, tokens[map_index[i]]);
     3033        }
     3034
     3035      }
     3036      if (readSuccess()) {
     3037        line.putback(c);
     3038      }
     3039    }
     3040
     3041    void readAttributes() {
     3042
     3043      std::set<std::string> read_attr;
     3044
     3045      char c;
     3046      while (readLine() && line >> c && c != '@') {
     3047        line.putback(c);
     3048
     3049        std::string attr, token;
     3050        if (!_reader_bits::readToken(line, attr))
     3051          throw FormatError("Attribute name not found");
     3052        if (!_reader_bits::readToken(line, token))
     3053          throw FormatError("Attribute value not found");
     3054        if (line >> c)
     3055          throw FormatError("Extra character at the end of line");
     3056
     3057        {
     3058          std::set<std::string>::iterator it = read_attr.find(attr);
     3059          if (it != read_attr.end()) {
     3060            std::ostringstream msg;
     3061            msg << "Multiple occurence of attribute: " << attr;
     3062            throw FormatError(msg.str());
     3063          }
     3064          read_attr.insert(attr);
     3065        }
     3066
     3067        {
     3068          typename Attributes::iterator it = _attributes.lower_bound(attr);
     3069          while (it != _attributes.end() && it->first == attr) {
     3070            it->second->set(token);
     3071            ++it;
     3072          }
     3073        }
     3074
     3075      }
     3076      if (readSuccess()) {
     3077        line.putback(c);
     3078      }
     3079      for (typename Attributes::iterator it = _attributes.begin();
     3080           it != _attributes.end(); ++it) {
     3081        if (read_attr.find(it->first) == read_attr.end()) {
     3082          std::ostringstream msg;
     3083          msg << "Attribute not found: " << it->first;
     3084          throw FormatError(msg.str());
     3085        }
     3086      }
     3087    }
     3088
     3089  public:
     3090
     3091    /// \name Execution of the Reader
     3092    /// @{
     3093
     3094    /// \brief Start the batch processing
     3095    ///
     3096    /// This function starts the batch processing
     3097    void run() {
     3098
     3099      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
     3100
     3101      bool red_nodes_done = _skip_nodes;
     3102      bool blue_nodes_done = _skip_nodes;
     3103      bool edges_done = _skip_edges;
     3104      bool attributes_done = false;
     3105
     3106      line_num = 0;
     3107      readLine();
     3108      skipSection();
     3109
     3110      while (readSuccess()) {
     3111        try {
     3112          char c;
     3113          std::string section, caption;
     3114          line >> c;
     3115          _reader_bits::readToken(line, section);
     3116          _reader_bits::readToken(line, caption);
     3117
     3118          if (line >> c)
     3119            throw FormatError("Extra character at the end of line");
     3120
     3121          if (section == "red_nodes" && !red_nodes_done) {
     3122            if (_nodes_caption.empty() || _nodes_caption == caption) {
     3123              readRedNodes();
     3124              red_nodes_done = true;
     3125            }
     3126          } else if (section == "blue_nodes" && !blue_nodes_done) {
     3127            if (_nodes_caption.empty() || _nodes_caption == caption) {
     3128              readBlueNodes();
     3129              blue_nodes_done = true;
     3130            }
     3131          } else if ((section == "edges" || section == "arcs") &&
     3132                     !edges_done) {
     3133            if (_edges_caption.empty() || _edges_caption == caption) {
     3134              readEdges();
     3135              edges_done = true;
     3136            }
     3137          } else if (section == "attributes" && !attributes_done) {
     3138            if (_attributes_caption.empty() || _attributes_caption == caption) {
     3139              readAttributes();
     3140              attributes_done = true;
     3141            }
     3142          } else {
     3143            readLine();
     3144            skipSection();
     3145          }
     3146        } catch (FormatError& error) {
     3147          error.line(line_num);
     3148          error.file(_filename);
     3149          throw;
     3150        }
     3151      }
     3152
     3153      if (!red_nodes_done) {
     3154        throw FormatError("Section @red_nodes not found");
     3155      }
     3156
     3157      if (!blue_nodes_done) {
     3158        throw FormatError("Section @blue_nodes not found");
     3159      }
     3160
     3161      if (!edges_done) {
     3162        throw FormatError("Section @edges not found");
     3163      }
     3164
     3165      if (!attributes_done && !_attributes.empty()) {
     3166        throw FormatError("Section @attributes not found");
     3167      }
     3168
     3169    }
     3170
     3171    /// @}
     3172
     3173  };
     3174
     3175  /// \ingroup lemon_io
     3176  ///
     3177  /// \brief Return a \ref BpGraphReader class
     3178  ///
     3179  /// This function just returns a \ref BpGraphReader class.
     3180  ///
     3181  /// With this function a graph can be read from an
     3182  /// \ref lgf-format "LGF" file or input stream with several maps and
     3183  /// attributes. For example, there is bipartite weighted matching problem
     3184  /// on a graph, i.e. a graph with a \e weight map on the edges. This
     3185  /// graph can be read with the following code:
     3186  ///
     3187  ///\code
     3188  ///ListBpGraph graph;
     3189  ///ListBpGraph::EdgeMap<int> weight(graph);
     3190  ///bpGraphReader(graph, std::cin).
     3191  ///  edgeMap("weight", weight).
     3192  ///  run();
     3193  ///\endcode
     3194  ///
     3195  /// For a complete documentation, please see the \ref BpGraphReader
     3196  /// class documentation.
     3197  /// \warning Don't forget to put the \ref BpGraphReader::run() "run()"
     3198  /// to the end of the parameter list.
     3199  /// \relates BpGraphReader
     3200  /// \sa bpGraphReader(TBGR& graph, const std::string& fn)
     3201  /// \sa bpGraphReader(TBGR& graph, const char* fn)
     3202  template <typename TBGR>
     3203  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is) {
     3204    BpGraphReader<TBGR> tmp(graph, is);
     3205    return tmp;
     3206  }
     3207
     3208  /// \brief Return a \ref BpGraphReader class
     3209  ///
     3210  /// This function just returns a \ref BpGraphReader class.
     3211  /// \relates BpGraphReader
     3212  /// \sa bpGraphReader(TBGR& graph, std::istream& is)
     3213  template <typename TBGR>
     3214  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const std::string& fn) {
     3215    BpGraphReader<TBGR> tmp(graph, fn);
     3216    return tmp;
     3217  }
     3218
     3219  /// \brief Return a \ref BpGraphReader class
     3220  ///
     3221  /// This function just returns a \ref BpGraphReader class.
     3222  /// \relates BpGraphReader
     3223  /// \sa bpGraphReader(TBGR& graph, std::istream& is)
     3224  template <typename TBGR>
     3225  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char* fn) {
     3226    BpGraphReader<TBGR> tmp(graph, fn);
     3227    return tmp;
     3228  }
     3229
    21313230  class SectionReader;
    21323231
  • lemon/lgf_writer.h

    r877 r1030  
    186186      ValueStorage(const Value& value, const Converter& converter = Converter())
    187187        : _value(value), _converter(converter) {}
    188 
     188     
    189189      virtual std::string get() {
    190190        return _converter(_value);
     
    192192    };
    193193
    194     template <typename Value>
     194    template <typename Value,
     195              typename Map = std::map<Value, std::string> >
    195196    struct MapLookUpConverter {
    196       const std::map<Value, std::string>& _map;
    197 
    198       MapLookUpConverter(const std::map<Value, std::string>& map)
     197      const Map& _map;
     198
     199      MapLookUpConverter(const Map& map)
    199200        : _map(map) {}
    200201
    201       std::string operator()(const Value& str) {
    202         typename std::map<Value, std::string>::const_iterator it =
    203           _map.find(str);
     202      std::string operator()(const Value& value) {
     203        typename Map::const_iterator it = _map.find(value);
    204204        if (it == _map.end()) {
    205205          throw FormatError("Item not found");
    206206        }
    207207        return it->second;
     208      }
     209    };
     210
     211    template <typename Value,
     212              typename Map1 = std::map<Value, std::string>,
     213              typename Map2 = std::map<Value, std::string> >
     214    struct DoubleMapLookUpConverter {
     215      const Map1& _map1;
     216      const Map2& _map2;
     217
     218      DoubleMapLookUpConverter(const Map1& map1, const Map2& map2)
     219        : _map1(map1), _map2(map2) {}
     220
     221      std::string operator()(const Value& value) {
     222        typename Map1::const_iterator it1 = _map1.find(value);
     223        typename Map1::const_iterator it2 = _map2.find(value);
     224        if (it1 == _map1.end()) {
     225          if (it2 == _map2.end()) {
     226            throw FormatError("Item not found");
     227          } else {
     228            return it2->second;
     229          }
     230        } else {
     231          if (it2 == _map2.end()) {
     232            return it1->second;
     233          } else {
     234            throw FormatError("Item is ambigous");
     235          }
     236        }
    208237      }
    209238    };
     
    9871016  /// \ingroup lemon_io
    9881017  ///
    989   /// \brief \ref lgf-format "LGF" writer for directed graphs
     1018  /// \brief \ref lgf-format "LGF" writer for undirected graphs
    9901019  ///
    9911020  /// This utility writes an \ref lgf-format "LGF" file.
     
    10431072    /// \brief Constructor
    10441073    ///
    1045     /// Construct a directed graph writer, which writes to the given
    1046     /// output stream.
     1074    /// Construct an undirected graph writer, which writes to the
     1075    /// given output stream.
    10471076    GraphWriter(const GR& graph, std::ostream& os = std::cout)
    10481077      : _os(&os), local_os(false), _graph(graph),
     
    10511080    /// \brief Constructor
    10521081    ///
    1053     /// Construct a directed graph writer, which writes to the given
     1082    /// Construct a undirected graph writer, which writes to the given
    10541083    /// output file.
    10551084    GraphWriter(const GR& graph, const std::string& fn)
     
    10641093    /// \brief Constructor
    10651094    ///
    1066     /// Construct a directed graph writer, which writes to the given
     1095    /// Construct a undirected graph writer, which writes to the given
    10671096    /// output file.
    10681097    GraphWriter(const GR& graph, const char* fn)
     
    12901319    }
    12911320
    1292     /// \brief Add an additional caption to the \c \@arcs section
    1293     ///
    1294     /// Add an additional caption to the \c \@arcs section.
     1321    /// \brief Add an additional caption to the \c \@edges section
     1322    ///
     1323    /// Add an additional caption to the \c \@edges section.
    12951324    GraphWriter& edges(const std::string& caption) {
    12961325      _edges_caption = caption;
     
    16061635  GraphWriter<TGR> graphWriter(const TGR& graph, const char* fn) {
    16071636    GraphWriter<TGR> tmp(graph, fn);
     1637    return tmp;
     1638  }
     1639
     1640  template <typename BGR>
     1641  class BpGraphWriter;
     1642
     1643  template <typename TBGR>
     1644  BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph,
     1645                                    std::ostream& os = std::cout);
     1646  template <typename TBGR>
     1647  BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, const std::string& fn);
     1648  template <typename TBGR>
     1649  BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, const char* fn);
     1650
     1651  /// \ingroup lemon_io
     1652  ///
     1653  /// \brief \ref lgf-format "LGF" writer for undirected bipartite graphs
     1654  ///
     1655  /// This utility writes an \ref lgf-format "LGF" file.
     1656  ///
     1657  /// It can be used almost the same way as \c GraphWriter, but it
     1658  /// reads the red and blue nodes from separate sections, and these
     1659  /// sections can contain different set of maps.
     1660  ///
     1661  /// The red and blue node maps are written to the corresponding
     1662  /// sections. The node maps are written to both of these sections
     1663  /// with the same map name.
     1664  template <typename BGR>
     1665  class BpGraphWriter {
     1666  public:
     1667
     1668    typedef BGR BpGraph;
     1669    TEMPLATE_BPGRAPH_TYPEDEFS(BGR);
     1670
     1671  private:
     1672
     1673
     1674    std::ostream* _os;
     1675    bool local_os;
     1676
     1677    const BGR& _graph;
     1678
     1679    std::string _nodes_caption;
     1680    std::string _edges_caption;
     1681    std::string _attributes_caption;
     1682
     1683    typedef std::map<Node, std::string> RedNodeIndex;
     1684    RedNodeIndex _red_node_index;
     1685    typedef std::map<Node, std::string> BlueNodeIndex;
     1686    BlueNodeIndex _blue_node_index;
     1687    typedef std::map<Edge, std::string> EdgeIndex;
     1688    EdgeIndex _edge_index;
     1689
     1690    typedef std::vector<std::pair<std::string,
     1691      _writer_bits::MapStorageBase<RedNode>* > > RedNodeMaps;
     1692    RedNodeMaps _red_node_maps;
     1693    typedef std::vector<std::pair<std::string,
     1694      _writer_bits::MapStorageBase<BlueNode>* > > BlueNodeMaps;
     1695    BlueNodeMaps _blue_node_maps;
     1696
     1697    typedef std::vector<std::pair<std::string,
     1698      _writer_bits::MapStorageBase<Edge>* > >EdgeMaps;
     1699    EdgeMaps _edge_maps;
     1700
     1701    typedef std::vector<std::pair<std::string,
     1702      _writer_bits::ValueStorageBase*> > Attributes;
     1703    Attributes _attributes;
     1704
     1705    bool _skip_nodes;
     1706    bool _skip_edges;
     1707
     1708  public:
     1709
     1710    /// \brief Constructor
     1711    ///
     1712    /// Construct a bipartite graph writer, which writes to the given
     1713    /// output stream.
     1714    BpGraphWriter(const BGR& graph, std::ostream& os = std::cout)
     1715      : _os(&os), local_os(false), _graph(graph),
     1716        _skip_nodes(false), _skip_edges(false) {}
     1717
     1718    /// \brief Constructor
     1719    ///
     1720    /// Construct a bipartite graph writer, which writes to the given
     1721    /// output file.
     1722    BpGraphWriter(const BGR& graph, const std::string& fn)
     1723      : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph),
     1724        _skip_nodes(false), _skip_edges(false) {
     1725      if (!(*_os)) {
     1726        delete _os;
     1727        throw IoError("Cannot write file", fn);
     1728      }
     1729    }
     1730
     1731    /// \brief Constructor
     1732    ///
     1733    /// Construct a bipartite graph writer, which writes to the given
     1734    /// output file.
     1735    BpGraphWriter(const BGR& graph, const char* fn)
     1736      : _os(new std::ofstream(fn)), local_os(true), _graph(graph),
     1737        _skip_nodes(false), _skip_edges(false) {
     1738      if (!(*_os)) {
     1739        delete _os;
     1740        throw IoError("Cannot write file", fn);
     1741      }
     1742    }
     1743
     1744    /// \brief Destructor
     1745    ~BpGraphWriter() {
     1746      for (typename RedNodeMaps::iterator it = _red_node_maps.begin();
     1747           it != _red_node_maps.end(); ++it) {
     1748        delete it->second;
     1749      }
     1750
     1751      for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin();
     1752           it != _blue_node_maps.end(); ++it) {
     1753        delete it->second;
     1754      }
     1755
     1756      for (typename EdgeMaps::iterator it = _edge_maps.begin();
     1757           it != _edge_maps.end(); ++it) {
     1758        delete it->second;
     1759      }
     1760
     1761      for (typename Attributes::iterator it = _attributes.begin();
     1762           it != _attributes.end(); ++it) {
     1763        delete it->second;
     1764      }
     1765
     1766      if (local_os) {
     1767        delete _os;
     1768      }
     1769    }
     1770
     1771  private:
     1772
     1773    template <typename TBGR>
     1774    friend BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph,
     1775                                             std::ostream& os);
     1776    template <typename TBGR>
     1777    friend BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph,
     1778                                             const std::string& fn);
     1779    template <typename TBGR>
     1780    friend BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, const char *fn);
     1781
     1782    BpGraphWriter(BpGraphWriter& other)
     1783      : _os(other._os), local_os(other.local_os), _graph(other._graph),
     1784        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
     1785
     1786      other._os = 0;
     1787      other.local_os = false;
     1788
     1789      _red_node_index.swap(other._red_node_index);
     1790      _blue_node_index.swap(other._blue_node_index);
     1791      _edge_index.swap(other._edge_index);
     1792
     1793      _red_node_maps.swap(other._red_node_maps);
     1794      _blue_node_maps.swap(other._blue_node_maps);
     1795      _edge_maps.swap(other._edge_maps);
     1796      _attributes.swap(other._attributes);
     1797
     1798      _nodes_caption = other._nodes_caption;
     1799      _edges_caption = other._edges_caption;
     1800      _attributes_caption = other._attributes_caption;
     1801    }
     1802
     1803    BpGraphWriter& operator=(const BpGraphWriter&);
     1804
     1805  public:
     1806
     1807    /// \name Writing Rules
     1808    /// @{
     1809
     1810    /// \brief Node map writing rule
     1811    ///
     1812    /// Add a node map writing rule to the writer.
     1813    template <typename Map>
     1814    BpGraphWriter& nodeMap(const std::string& caption, const Map& map) {
     1815      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
     1816      _writer_bits::MapStorageBase<RedNode>* red_storage =
     1817        new _writer_bits::MapStorage<RedNode, Map>(map);
     1818      _red_node_maps.push_back(std::make_pair(caption, red_storage));
     1819      _writer_bits::MapStorageBase<BlueNode>* blue_storage =
     1820        new _writer_bits::MapStorage<BlueNode, Map>(map);
     1821      _blue_node_maps.push_back(std::make_pair(caption, blue_storage));
     1822      return *this;
     1823    }
     1824
     1825    /// \brief Node map writing rule
     1826    ///
     1827    /// Add a node map writing rule with specialized converter to the
     1828    /// writer.
     1829    template <typename Map, typename Converter>
     1830    BpGraphWriter& nodeMap(const std::string& caption, const Map& map,
     1831                           const Converter& converter = Converter()) {
     1832      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
     1833      _writer_bits::MapStorageBase<RedNode>* red_storage =
     1834        new _writer_bits::MapStorage<RedNode, Map, Converter>(map, converter);
     1835      _red_node_maps.push_back(std::make_pair(caption, red_storage));
     1836      _writer_bits::MapStorageBase<BlueNode>* blue_storage =
     1837        new _writer_bits::MapStorage<BlueNode, Map, Converter>(map, converter);
     1838      _blue_node_maps.push_back(std::make_pair(caption, blue_storage));
     1839      return *this;
     1840    }
     1841
     1842    /// \brief Red node map writing rule
     1843    ///
     1844    /// Add a red node map writing rule to the writer.
     1845    template <typename Map>
     1846    BpGraphWriter& redNodeMap(const std::string& caption, const Map& map) {
     1847      checkConcept<concepts::ReadMap<RedNode, typename Map::Value>, Map>();
     1848      _writer_bits::MapStorageBase<RedNode>* storage =
     1849        new _writer_bits::MapStorage<RedNode, Map>(map);
     1850      _red_node_maps.push_back(std::make_pair(caption, storage));
     1851      return *this;
     1852    }
     1853
     1854    /// \brief Red node map writing rule
     1855    ///
     1856    /// Add a red node map writing rule with specialized converter to the
     1857    /// writer.
     1858    template <typename Map, typename Converter>
     1859    BpGraphWriter& redNodeMap(const std::string& caption, const Map& map,
     1860                              const Converter& converter = Converter()) {
     1861      checkConcept<concepts::ReadMap<RedNode, typename Map::Value>, Map>();
     1862      _writer_bits::MapStorageBase<RedNode>* storage =
     1863        new _writer_bits::MapStorage<RedNode, Map, Converter>(map, converter);
     1864      _red_node_maps.push_back(std::make_pair(caption, storage));
     1865      return *this;
     1866    }
     1867
     1868    /// \brief Blue node map writing rule
     1869    ///
     1870    /// Add a blue node map writing rule to the writer.
     1871    template <typename Map>
     1872    BpGraphWriter& blueNodeMap(const std::string& caption, const Map& map) {
     1873      checkConcept<concepts::ReadMap<BlueNode, typename Map::Value>, Map>();
     1874      _writer_bits::MapStorageBase<BlueNode>* storage =
     1875        new _writer_bits::MapStorage<BlueNode, Map>(map);
     1876      _blue_node_maps.push_back(std::make_pair(caption, storage));
     1877      return *this;
     1878    }
     1879
     1880    /// \brief Blue node map writing rule
     1881    ///
     1882    /// Add a blue node map writing rule with specialized converter to the
     1883    /// writer.
     1884    template <typename Map, typename Converter>
     1885    BpGraphWriter& blueNodeMap(const std::string& caption, const Map& map,
     1886                               const Converter& converter = Converter()) {
     1887      checkConcept<concepts::ReadMap<BlueNode, typename Map::Value>, Map>();
     1888      _writer_bits::MapStorageBase<BlueNode>* storage =
     1889        new _writer_bits::MapStorage<BlueNode, Map, Converter>(map, converter);
     1890      _blue_node_maps.push_back(std::make_pair(caption, storage));
     1891      return *this;
     1892    }
     1893
     1894    /// \brief Edge map writing rule
     1895    ///
     1896    /// Add an edge map writing rule to the writer.
     1897    template <typename Map>
     1898    BpGraphWriter& edgeMap(const std::string& caption, const Map& map) {
     1899      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
     1900      _writer_bits::MapStorageBase<Edge>* storage =
     1901        new _writer_bits::MapStorage<Edge, Map>(map);
     1902      _edge_maps.push_back(std::make_pair(caption, storage));
     1903      return *this;
     1904    }
     1905
     1906    /// \brief Edge map writing rule
     1907    ///
     1908    /// Add an edge map writing rule with specialized converter to the
     1909    /// writer.
     1910    template <typename Map, typename Converter>
     1911    BpGraphWriter& edgeMap(const std::string& caption, const Map& map,
     1912                          const Converter& converter = Converter()) {
     1913      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
     1914      _writer_bits::MapStorageBase<Edge>* storage =
     1915        new _writer_bits::MapStorage<Edge, Map, Converter>(map, converter);
     1916      _edge_maps.push_back(std::make_pair(caption, storage));
     1917      return *this;
     1918    }
     1919
     1920    /// \brief Arc map writing rule
     1921    ///
     1922    /// Add an arc map writing rule to the writer.
     1923    template <typename Map>
     1924    BpGraphWriter& arcMap(const std::string& caption, const Map& map) {
     1925      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
     1926      _writer_bits::MapStorageBase<Edge>* forward_storage =
     1927        new _writer_bits::GraphArcMapStorage<BGR, true, Map>(_graph, map);
     1928      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
     1929      _writer_bits::MapStorageBase<Edge>* backward_storage =
     1930        new _writer_bits::GraphArcMapStorage<BGR, false, Map>(_graph, map);
     1931      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
     1932      return *this;
     1933    }
     1934
     1935    /// \brief Arc map writing rule
     1936    ///
     1937    /// Add an arc map writing rule with specialized converter to the
     1938    /// writer.
     1939    template <typename Map, typename Converter>
     1940    BpGraphWriter& arcMap(const std::string& caption, const Map& map,
     1941                          const Converter& converter = Converter()) {
     1942      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
     1943      _writer_bits::MapStorageBase<Edge>* forward_storage =
     1944        new _writer_bits::GraphArcMapStorage<BGR, true, Map, Converter>
     1945        (_graph, map, converter);
     1946      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
     1947      _writer_bits::MapStorageBase<Edge>* backward_storage =
     1948        new _writer_bits::GraphArcMapStorage<BGR, false, Map, Converter>
     1949        (_graph, map, converter);
     1950      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
     1951      return *this;
     1952    }
     1953
     1954    /// \brief Attribute writing rule
     1955    ///
     1956    /// Add an attribute writing rule to the writer.
     1957    template <typename Value>
     1958    BpGraphWriter& attribute(const std::string& caption, const Value& value) {
     1959      _writer_bits::ValueStorageBase* storage =
     1960        new _writer_bits::ValueStorage<Value>(value);
     1961      _attributes.push_back(std::make_pair(caption, storage));
     1962      return *this;
     1963    }
     1964
     1965    /// \brief Attribute writing rule
     1966    ///
     1967    /// Add an attribute writing rule with specialized converter to the
     1968    /// writer.
     1969    template <typename Value, typename Converter>
     1970    BpGraphWriter& attribute(const std::string& caption, const Value& value,
     1971                             const Converter& converter = Converter()) {
     1972      _writer_bits::ValueStorageBase* storage =
     1973        new _writer_bits::ValueStorage<Value, Converter>(value, converter);
     1974      _attributes.push_back(std::make_pair(caption, storage));
     1975      return *this;
     1976    }
     1977
     1978    /// \brief Node writing rule
     1979    ///
     1980    /// Add a node writing rule to the writer.
     1981    BpGraphWriter& node(const std::string& caption, const Node& node) {
     1982      typedef _writer_bits::DoubleMapLookUpConverter<
     1983        Node, RedNodeIndex, BlueNodeIndex> Converter;
     1984      Converter converter(_red_node_index, _blue_node_index);
     1985      _writer_bits::ValueStorageBase* storage =
     1986        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
     1987      _attributes.push_back(std::make_pair(caption, storage));
     1988      return *this;
     1989    }
     1990
     1991    /// \brief Red node writing rule
     1992    ///
     1993    /// Add a red node writing rule to the writer.
     1994    BpGraphWriter& redNode(const std::string& caption, const RedNode& node) {
     1995      typedef _writer_bits::MapLookUpConverter<Node> Converter;
     1996      Converter converter(_red_node_index);
     1997      _writer_bits::ValueStorageBase* storage =
     1998        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
     1999      _attributes.push_back(std::make_pair(caption, storage));
     2000      return *this;
     2001    }
     2002
     2003    /// \brief Blue node writing rule
     2004    ///
     2005    /// Add a blue node writing rule to the writer.
     2006    BpGraphWriter& blueNode(const std::string& caption, const BlueNode& node) {
     2007      typedef _writer_bits::MapLookUpConverter<Node> Converter;
     2008      Converter converter(_blue_node_index);
     2009      _writer_bits::ValueStorageBase* storage =
     2010        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
     2011      _attributes.push_back(std::make_pair(caption, storage));
     2012      return *this;
     2013    }
     2014
     2015    /// \brief Edge writing rule
     2016    ///
     2017    /// Add an edge writing rule to writer.
     2018    BpGraphWriter& edge(const std::string& caption, const Edge& edge) {
     2019      typedef _writer_bits::MapLookUpConverter<Edge> Converter;
     2020      Converter converter(_edge_index);
     2021      _writer_bits::ValueStorageBase* storage =
     2022        new _writer_bits::ValueStorage<Edge, Converter>(edge, converter);
     2023      _attributes.push_back(std::make_pair(caption, storage));
     2024      return *this;
     2025    }
     2026
     2027    /// \brief Arc writing rule
     2028    ///
     2029    /// Add an arc writing rule to writer.
     2030    BpGraphWriter& arc(const std::string& caption, const Arc& arc) {
     2031      typedef _writer_bits::GraphArcLookUpConverter<BGR> Converter;
     2032      Converter converter(_graph, _edge_index);
     2033      _writer_bits::ValueStorageBase* storage =
     2034        new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
     2035      _attributes.push_back(std::make_pair(caption, storage));
     2036      return *this;
     2037    }
     2038
     2039    /// \name Section Captions
     2040    /// @{
     2041
     2042    /// \brief Add an additional caption to the \c \@red_nodes and
     2043    /// \c \@blue_nodes section
     2044    ///
     2045    /// Add an additional caption to the \c \@red_nodes and \c
     2046    /// \@blue_nodes section.
     2047    BpGraphWriter& nodes(const std::string& caption) {
     2048      _nodes_caption = caption;
     2049      return *this;
     2050    }
     2051
     2052    /// \brief Add an additional caption to the \c \@edges section
     2053    ///
     2054    /// Add an additional caption to the \c \@edges section.
     2055    BpGraphWriter& edges(const std::string& caption) {
     2056      _edges_caption = caption;
     2057      return *this;
     2058    }
     2059
     2060    /// \brief Add an additional caption to the \c \@attributes section
     2061    ///
     2062    /// Add an additional caption to the \c \@attributes section.
     2063    BpGraphWriter& attributes(const std::string& caption) {
     2064      _attributes_caption = caption;
     2065      return *this;
     2066    }
     2067
     2068    /// \name Skipping Section
     2069    /// @{
     2070
     2071    /// \brief Skip writing the node set
     2072    ///
     2073    /// The \c \@red_nodes and \c \@blue_nodes section will not be
     2074    /// written to the stream.
     2075    BpGraphWriter& skipNodes() {
     2076      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
     2077      _skip_nodes = true;
     2078      return *this;
     2079    }
     2080
     2081    /// \brief Skip writing edge set
     2082    ///
     2083    /// The \c \@edges section will not be written to the stream.
     2084    BpGraphWriter& skipEdges() {
     2085      LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member");
     2086      _skip_edges = true;
     2087      return *this;
     2088    }
     2089
     2090    /// @}
     2091
     2092  private:
     2093
     2094    void writeRedNodes() {
     2095      _writer_bits::MapStorageBase<RedNode>* label = 0;
     2096      for (typename RedNodeMaps::iterator it = _red_node_maps.begin();
     2097           it != _red_node_maps.end(); ++it) {
     2098        if (it->first == "label") {
     2099          label = it->second;
     2100          break;
     2101        }
     2102      }
     2103
     2104      *_os << "@red_nodes";
     2105      if (!_nodes_caption.empty()) {
     2106        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
     2107      }
     2108      *_os << std::endl;
     2109
     2110      if (label == 0) {
     2111        *_os << "label" << '\t';
     2112      }
     2113      for (typename RedNodeMaps::iterator it = _red_node_maps.begin();
     2114           it != _red_node_maps.end(); ++it) {
     2115        _writer_bits::writeToken(*_os, it->first) << '\t';
     2116      }
     2117      *_os << std::endl;
     2118
     2119      std::vector<RedNode> nodes;
     2120      for (RedNodeIt n(_graph); n != INVALID; ++n) {
     2121        nodes.push_back(n);
     2122      }
     2123
     2124      if (label == 0) {
     2125        IdMap<BGR, Node> id_map(_graph);
     2126        _writer_bits::MapLess<IdMap<BGR, Node> > id_less(id_map);
     2127        std::sort(nodes.begin(), nodes.end(), id_less);
     2128      } else {
     2129        label->sort(nodes);
     2130      }
     2131
     2132      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
     2133        RedNode n = nodes[i];
     2134        if (label == 0) {
     2135          std::ostringstream os;
     2136          os << _graph.id(static_cast<Node>(n));
     2137          _writer_bits::writeToken(*_os, os.str());
     2138          *_os << '\t';
     2139          _red_node_index.insert(std::make_pair(n, os.str()));
     2140        }
     2141        for (typename RedNodeMaps::iterator it = _red_node_maps.begin();
     2142             it != _red_node_maps.end(); ++it) {
     2143          std::string value = it->second->get(n);
     2144          _writer_bits::writeToken(*_os, value);
     2145          if (it->first == "label") {
     2146            _red_node_index.insert(std::make_pair(n, value));
     2147          }
     2148          *_os << '\t';
     2149        }
     2150        *_os << std::endl;
     2151      }
     2152    }
     2153
     2154    void writeBlueNodes() {
     2155      _writer_bits::MapStorageBase<BlueNode>* label = 0;
     2156      for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin();
     2157           it != _blue_node_maps.end(); ++it) {
     2158        if (it->first == "label") {
     2159          label = it->second;
     2160          break;
     2161        }
     2162      }
     2163
     2164      *_os << "@blue_nodes";
     2165      if (!_nodes_caption.empty()) {
     2166        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
     2167      }
     2168      *_os << std::endl;
     2169
     2170      if (label == 0) {
     2171        *_os << "label" << '\t';
     2172      }
     2173      for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin();
     2174           it != _blue_node_maps.end(); ++it) {
     2175        _writer_bits::writeToken(*_os, it->first) << '\t';
     2176      }
     2177      *_os << std::endl;
     2178
     2179      std::vector<BlueNode> nodes;
     2180      for (BlueNodeIt n(_graph); n != INVALID; ++n) {
     2181        nodes.push_back(n);
     2182      }
     2183
     2184      if (label == 0) {
     2185        IdMap<BGR, Node> id_map(_graph);
     2186        _writer_bits::MapLess<IdMap<BGR, Node> > id_less(id_map);
     2187        std::sort(nodes.begin(), nodes.end(), id_less);
     2188      } else {
     2189        label->sort(nodes);
     2190      }
     2191
     2192      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
     2193        BlueNode n = nodes[i];
     2194        if (label == 0) {
     2195          std::ostringstream os;
     2196          os << _graph.id(static_cast<Node>(n));
     2197          _writer_bits::writeToken(*_os, os.str());
     2198          *_os << '\t';
     2199          _blue_node_index.insert(std::make_pair(n, os.str()));
     2200        }
     2201        for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin();
     2202             it != _blue_node_maps.end(); ++it) {
     2203          std::string value = it->second->get(n);
     2204          _writer_bits::writeToken(*_os, value);
     2205          if (it->first == "label") {
     2206            _blue_node_index.insert(std::make_pair(n, value));
     2207          }
     2208          *_os << '\t';
     2209        }
     2210        *_os << std::endl;
     2211      }
     2212    }
     2213
     2214    void createRedNodeIndex() {
     2215      _writer_bits::MapStorageBase<RedNode>* label = 0;
     2216      for (typename RedNodeMaps::iterator it = _red_node_maps.begin();
     2217           it != _red_node_maps.end(); ++it) {
     2218        if (it->first == "label") {
     2219          label = it->second;
     2220          break;
     2221        }
     2222      }
     2223
     2224      if (label == 0) {
     2225        for (RedNodeIt n(_graph); n != INVALID; ++n) {
     2226          std::ostringstream os;
     2227          os << _graph.id(n);
     2228          _red_node_index.insert(std::make_pair(n, os.str()));
     2229        }
     2230      } else {
     2231        for (RedNodeIt n(_graph); n != INVALID; ++n) {
     2232          std::string value = label->get(n);
     2233          _red_node_index.insert(std::make_pair(n, value));
     2234        }
     2235      }
     2236    }
     2237
     2238    void createBlueNodeIndex() {
     2239      _writer_bits::MapStorageBase<BlueNode>* label = 0;
     2240      for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin();
     2241           it != _blue_node_maps.end(); ++it) {
     2242        if (it->first == "label") {
     2243          label = it->second;
     2244          break;
     2245        }
     2246      }
     2247
     2248      if (label == 0) {
     2249        for (BlueNodeIt n(_graph); n != INVALID; ++n) {
     2250          std::ostringstream os;
     2251          os << _graph.id(n);
     2252          _blue_node_index.insert(std::make_pair(n, os.str()));
     2253        }
     2254      } else {
     2255        for (BlueNodeIt n(_graph); n != INVALID; ++n) {
     2256          std::string value = label->get(n);
     2257          _blue_node_index.insert(std::make_pair(n, value));
     2258        }
     2259      }
     2260    }
     2261
     2262    void writeEdges() {
     2263      _writer_bits::MapStorageBase<Edge>* label = 0;
     2264      for (typename EdgeMaps::iterator it = _edge_maps.begin();
     2265           it != _edge_maps.end(); ++it) {
     2266        if (it->first == "label") {
     2267          label = it->second;
     2268          break;
     2269        }
     2270      }
     2271
     2272      *_os << "@edges";
     2273      if (!_edges_caption.empty()) {
     2274        _writer_bits::writeToken(*_os << ' ', _edges_caption);
     2275      }
     2276      *_os << std::endl;
     2277
     2278      *_os << '\t' << '\t';
     2279      if (label == 0) {
     2280        *_os << "label" << '\t';
     2281      }
     2282      for (typename EdgeMaps::iterator it = _edge_maps.begin();
     2283           it != _edge_maps.end(); ++it) {
     2284        _writer_bits::writeToken(*_os, it->first) << '\t';
     2285      }
     2286      *_os << std::endl;
     2287
     2288      std::vector<Edge> edges;
     2289      for (EdgeIt n(_graph); n != INVALID; ++n) {
     2290        edges.push_back(n);
     2291      }
     2292
     2293      if (label == 0) {
     2294        IdMap<BGR, Edge> id_map(_graph);
     2295        _writer_bits::MapLess<IdMap<BGR, Edge> > id_less(id_map);
     2296        std::sort(edges.begin(), edges.end(), id_less);
     2297      } else {
     2298        label->sort(edges);
     2299      }
     2300
     2301      for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
     2302        Edge e = edges[i];
     2303        _writer_bits::writeToken(*_os, _red_node_index.
     2304                                 find(_graph.redNode(e))->second);
     2305        *_os << '\t';
     2306        _writer_bits::writeToken(*_os, _blue_node_index.
     2307                                 find(_graph.blueNode(e))->second);
     2308        *_os << '\t';
     2309        if (label == 0) {
     2310          std::ostringstream os;
     2311          os << _graph.id(e);
     2312          _writer_bits::writeToken(*_os, os.str());
     2313          *_os << '\t';
     2314          _edge_index.insert(std::make_pair(e, os.str()));
     2315        }
     2316        for (typename EdgeMaps::iterator it = _edge_maps.begin();
     2317             it != _edge_maps.end(); ++it) {
     2318          std::string value = it->second->get(e);
     2319          _writer_bits::writeToken(*_os, value);
     2320          if (it->first == "label") {
     2321            _edge_index.insert(std::make_pair(e, value));
     2322          }
     2323          *_os << '\t';
     2324        }
     2325        *_os << std::endl;
     2326      }
     2327    }
     2328
     2329    void createEdgeIndex() {
     2330      _writer_bits::MapStorageBase<Edge>* label = 0;
     2331      for (typename EdgeMaps::iterator it = _edge_maps.begin();
     2332           it != _edge_maps.end(); ++it) {
     2333        if (it->first == "label") {
     2334          label = it->second;
     2335          break;
     2336        }
     2337      }
     2338
     2339      if (label == 0) {
     2340        for (EdgeIt e(_graph); e != INVALID; ++e) {
     2341          std::ostringstream os;
     2342          os << _graph.id(e);
     2343          _edge_index.insert(std::make_pair(e, os.str()));
     2344        }
     2345      } else {
     2346        for (EdgeIt e(_graph); e != INVALID; ++e) {
     2347          std::string value = label->get(e);
     2348          _edge_index.insert(std::make_pair(e, value));
     2349        }
     2350      }
     2351    }
     2352
     2353    void writeAttributes() {
     2354      if (_attributes.empty()) return;
     2355      *_os << "@attributes";
     2356      if (!_attributes_caption.empty()) {
     2357        _writer_bits::writeToken(*_os << ' ', _attributes_caption);
     2358      }
     2359      *_os << std::endl;
     2360      for (typename Attributes::iterator it = _attributes.begin();
     2361           it != _attributes.end(); ++it) {
     2362        _writer_bits::writeToken(*_os, it->first) << ' ';
     2363        _writer_bits::writeToken(*_os, it->second->get());
     2364        *_os << std::endl;
     2365      }
     2366    }
     2367
     2368  public:
     2369
     2370    /// \name Execution of the Writer
     2371    /// @{
     2372
     2373    /// \brief Start the batch processing
     2374    ///
     2375    /// This funct