r865:d48d79b11f5b
Sun, 14 Mar 2010 09:13:04
[Not Reviewed]
0 comments (0 inline)
0
3
1
| 1 |
%!PS-Adobe-2.0 EPSF-2.0 |
|
| 2 |
%%Creator: LEMON, graphToEps() |
|
| 3 |
%%CreationDate: Sun Mar 14 09:08:34 2010 |
|
| 4 |
%%BoundingBox: -353 -264 559 292 |
|
| 5 |
%%EndComments |
|
| 6 |
/lb { setlinewidth setrgbcolor newpath moveto
|
|
| 7 |
4 2 roll 1 index 1 index curveto stroke } bind def |
|
| 8 |
/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
|
|
| 9 |
/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
|
|
| 10 |
/sq { newpath 2 index 1 index add 2 index 2 index add moveto
|
|
| 11 |
2 index 1 index sub 2 index 2 index add lineto |
|
| 12 |
2 index 1 index sub 2 index 2 index sub lineto |
|
| 13 |
2 index 1 index add 2 index 2 index sub lineto |
|
| 14 |
closepath pop pop pop} bind def |
|
| 15 |
/di { newpath 2 index 1 index add 2 index moveto
|
|
| 16 |
2 index 2 index 2 index add lineto |
|
| 17 |
2 index 1 index sub 2 index lineto |
|
| 18 |
2 index 2 index 2 index sub lineto |
|
| 19 |
closepath pop pop pop} bind def |
|
| 20 |
/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
|
|
| 21 |
setrgbcolor 1.1 div c fill |
|
| 22 |
} bind def |
|
| 23 |
/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
|
|
| 24 |
setrgbcolor 1.1 div sq fill |
|
| 25 |
} bind def |
|
| 26 |
/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
|
|
| 27 |
setrgbcolor 1.1 div di fill |
|
| 28 |
} bind def |
|
| 29 |
/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
|
|
| 30 |
newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub |
|
| 31 |
lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto |
|
| 32 |
5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke |
|
| 33 |
5 index 5 index 5 index c fill |
|
| 34 |
setrgbcolor 1.1 div c fill |
|
| 35 |
} bind def |
|
| 36 |
/nmale {
|
|
| 37 |
0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth |
|
| 38 |
newpath 5 index 5 index moveto |
|
| 39 |
5 index 4 index 1 mul 1.5 mul add |
|
| 40 |
5 index 5 index 3 sqrt 1.5 mul mul add |
|
| 41 |
1 index 1 index lineto |
|
| 42 |
1 index 1 index 7 index sub moveto |
|
| 43 |
1 index 1 index lineto |
|
| 44 |
exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto |
|
| 45 |
stroke |
|
| 46 |
5 index 5 index 5 index c fill |
|
| 47 |
setrgbcolor 1.1 div c fill |
|
| 48 |
} bind def |
|
| 49 |
/arrl 1 def |
|
| 50 |
/arrw 0.3 def |
|
| 51 |
/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
|
|
| 52 |
/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
|
|
| 53 |
/w exch def /len exch def |
|
| 54 |
newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto |
|
| 55 |
len w sub arrl sub dx dy lrl |
|
| 56 |
arrw dy dx neg lrl |
|
| 57 |
dx arrl w add mul dy w 2 div arrw add mul sub |
|
| 58 |
dy arrl w add mul dx w 2 div arrw add mul add rlineto |
|
| 59 |
dx arrl w add mul neg dy w 2 div arrw add mul sub |
|
| 60 |
dy arrl w add mul neg dx w 2 div arrw add mul add rlineto |
|
| 61 |
arrw dy dx neg lrl |
|
| 62 |
len w sub arrl sub neg dx dy lrl |
|
| 63 |
closepath fill } bind def |
|
| 64 |
/cshow { 2 index 2 index moveto dup stringwidth pop
|
|
| 65 |
neg 2 div fosi .35 mul neg rmoveto show pop pop} def |
|
| 66 |
|
|
| 67 |
gsave |
|
| 68 |
%Arcs: |
|
| 69 |
gsave |
|
| 70 |
140.321 266.249 -327.729 150.06 0 0 0 4.99223 l |
|
| 71 |
82.1207 -238.726 -245.288 -110.743 0 0 0 4.99223 l |
|
| 72 |
336.635 -229.036 533.603 13.109 0 0 0 4.99223 l |
|
| 73 |
53.8598 -45.8071 -245.288 -110.743 0 0 0 4.99223 l |
|
| 74 |
-75.5617 118.579 -327.729 150.06 0 0 0 4.99223 l |
|
| 75 |
-327.729 150.06 -245.288 -110.743 1 0 0 11.9813 l |
|
| 76 |
533.603 13.109 218.184 -84.2955 0 0 0 4.99223 l |
|
| 77 |
39.87 175.035 141.163 67.2575 0 0 0 4.99223 l |
|
| 78 |
53.8598 -45.8071 -75.5617 118.579 0 0 0 4.99223 l |
|
| 79 |
-102.406 -141.267 82.1207 -238.726 0 0 0 4.99223 l |
|
| 80 |
399.144 166.894 533.603 13.109 1 0 0 11.9813 l |
|
| 81 |
39.87 175.035 140.321 266.249 1 0 0 11.9813 l |
|
| 82 |
399.144 166.894 140.321 266.249 0 0 0 4.99223 l |
|
| 83 |
399.144 166.894 141.163 67.2575 0 0 0 4.99223 l |
|
| 84 |
53.8598 -45.8071 204.765 -173.77 0 0 0 4.99223 l |
|
| 85 |
82.1207 -238.726 204.765 -173.77 0 0 0 4.99223 l |
|
| 86 |
258.227 61.658 399.144 166.894 0 0 0 4.99223 l |
|
| 87 |
53.8598 -45.8071 -102.406 -141.267 1 0 0 11.9813 l |
|
| 88 |
175.073 -37.4477 141.163 67.2575 0 0 0 4.99223 l |
|
| 89 |
258.227 61.658 380 0 0 0 0 4.99223 l |
|
| 90 |
34.6739 40.8267 -75.5617 118.579 1 0 0 11.9813 l |
|
| 91 |
380 0 533.603 13.109 0 0 0 4.99223 l |
|
| 92 |
175.073 -37.4477 380 0 0 0 0 4.99223 l |
|
| 93 |
218.184 -84.2955 204.765 -173.77 0 0 0 4.99223 l |
|
| 94 |
53.8598 -45.8071 34.6739 40.8267 0 0 0 4.99223 l |
|
| 95 |
167.905 -213.988 82.1207 -238.726 1 0 0 11.9813 l |
|
| 96 |
336.635 -229.036 204.765 -173.77 1 0 0 11.9813 l |
|
| 97 |
336.635 -229.036 167.905 -213.988 0 0 0 4.99223 l |
|
| 98 |
329.08 -26.3098 218.184 -84.2955 0 0 0 4.99223 l |
|
| 99 |
39.87 175.035 -75.5617 118.579 0 0 0 4.99223 l |
|
| 100 |
53.8598 -45.8071 175.073 -37.4477 0 0 0 4.99223 l |
|
| 101 |
34.6739 40.8267 141.163 67.2575 0 0 0 4.99223 l |
|
| 102 |
258.227 61.658 141.163 67.2575 1 0 0 11.9813 l |
|
| 103 |
175.073 -37.4477 218.184 -84.2955 1 0 0 11.9813 l |
|
| 104 |
380 0 329.08 -26.3098 1 0 0 11.9813 l |
|
| 105 |
grestore |
|
| 106 |
%Nodes: |
|
| 107 |
gsave |
|
| 108 |
-245.288 -110.743 14.9767 1 1 1 nc |
|
| 109 |
204.765 -173.77 14.9767 1 1 1 nc |
|
| 110 |
-327.729 150.06 14.9767 1 1 1 nc |
|
| 111 |
-75.5617 118.579 14.9767 1 1 1 nc |
|
| 112 |
218.184 -84.2955 14.9767 1 1 1 nc |
|
| 113 |
140.321 266.249 14.9767 1 1 1 nc |
|
| 114 |
141.163 67.2575 14.9767 1 1 1 nc |
|
| 115 |
82.1207 -238.726 14.9767 1 1 1 nc |
|
| 116 |
329.08 -26.3098 14.9767 1 1 1 nc |
|
| 117 |
-102.406 -141.267 14.9767 1 1 1 nc |
|
| 118 |
533.603 13.109 14.9767 1 1 1 nc |
|
| 119 |
167.905 -213.988 14.9767 1 1 1 nc |
|
| 120 |
336.635 -229.036 14.9767 1 1 1 nc |
|
| 121 |
380 0 14.9767 1 1 1 nc |
|
| 122 |
399.144 166.894 14.9767 1 1 1 nc |
|
| 123 |
34.6739 40.8267 14.9767 1 1 1 nc |
|
| 124 |
39.87 175.035 14.9767 1 1 1 nc |
|
| 125 |
175.073 -37.4477 14.9767 1 1 1 nc |
|
| 126 |
53.8598 -45.8071 14.9767 1 1 1 nc |
|
| 127 |
258.227 61.658 14.9767 1 1 1 nc |
|
| 128 |
grestore |
|
| 129 |
grestore |
|
| 130 |
showpage |
| 1 | 1 |
SET(PACKAGE_NAME ${PROJECT_NAME})
|
| 2 | 2 |
SET(PACKAGE_VERSION ${PROJECT_VERSION})
|
| 3 | 3 |
SET(abs_top_srcdir ${PROJECT_SOURCE_DIR})
|
| 4 | 4 |
SET(abs_top_builddir ${PROJECT_BINARY_DIR})
|
| 5 | 5 |
|
| 6 | 6 |
CONFIGURE_FILE( |
| 7 | 7 |
${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
|
| 8 | 8 |
${PROJECT_BINARY_DIR}/doc/Doxyfile
|
| 9 | 9 |
@ONLY |
| 10 | 10 |
) |
| 11 | 11 |
|
| 12 | 12 |
IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE) |
| 13 | 13 |
FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
|
| 14 | 14 |
SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha) |
| 15 | 15 |
ADD_CUSTOM_TARGET(html |
| 16 | 16 |
COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images
|
| 17 | 17 |
COMMAND ${CMAKE_COMMAND} -E make_directory gen-images
|
| 18 | 18 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
|
| 19 | 19 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
|
| 20 | 20 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
|
| 21 | 21 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
|
| 22 | 22 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
|
| 23 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
|
|
| 23 | 24 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
|
| 24 | 25 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
|
| 25 | 26 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
|
| 26 | 27 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
|
| 27 | 28 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
|
| 28 | 29 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
|
| 29 | 30 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
|
| 30 | 31 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
|
| 31 | 32 |
COMMAND ${CMAKE_COMMAND} -E remove_directory html
|
| 32 | 33 |
COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
|
| 33 | 34 |
COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
|
| 34 | 35 |
WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
|
| 35 | 36 |
) |
| 36 | 37 |
|
| 37 | 38 |
SET_TARGET_PROPERTIES(html PROPERTIES PROJECT_LABEL BUILD_DOC) |
| 38 | 39 |
|
| 39 | 40 |
IF(UNIX) |
| 40 | 41 |
INSTALL( |
| 41 | 42 |
DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
|
| 42 | 43 |
DESTINATION share/doc/lemon/html |
| 43 | 44 |
COMPONENT html_documentation |
| 44 | 45 |
) |
| 45 | 46 |
ELSEIF(WIN32) |
| 46 | 47 |
INSTALL( |
| ... | ... |
@@ -6,48 +6,49 @@ |
| 6 | 6 |
doc/groups.dox \ |
| 7 | 7 |
doc/lgf.dox \ |
| 8 | 8 |
doc/license.dox \ |
| 9 | 9 |
doc/mainpage.dox \ |
| 10 | 10 |
doc/migration.dox \ |
| 11 | 11 |
doc/min_cost_flow.dox \ |
| 12 | 12 |
doc/named-param.dox \ |
| 13 | 13 |
doc/namespaces.dox \ |
| 14 | 14 |
doc/html \ |
| 15 | 15 |
doc/CMakeLists.txt |
| 16 | 16 |
|
| 17 | 17 |
DOC_EPS_IMAGES18 = \ |
| 18 | 18 |
grid_graph.eps \ |
| 19 | 19 |
nodeshape_0.eps \ |
| 20 | 20 |
nodeshape_1.eps \ |
| 21 | 21 |
nodeshape_2.eps \ |
| 22 | 22 |
nodeshape_3.eps \ |
| 23 | 23 |
nodeshape_4.eps |
| 24 | 24 |
|
| 25 | 25 |
DOC_EPS_IMAGES27 = \ |
| 26 | 26 |
bipartite_matching.eps \ |
| 27 | 27 |
bipartite_partitions.eps \ |
| 28 | 28 |
connected_components.eps \ |
| 29 | 29 |
edge_biconnected_components.eps \ |
| 30 |
matching.eps \ |
|
| 30 | 31 |
node_biconnected_components.eps \ |
| 31 | 32 |
planar.eps \ |
| 32 | 33 |
strongly_connected_components.eps |
| 33 | 34 |
|
| 34 | 35 |
DOC_EPS_IMAGES = \ |
| 35 | 36 |
$(DOC_EPS_IMAGES18) \ |
| 36 | 37 |
$(DOC_EPS_IMAGES27) |
| 37 | 38 |
|
| 38 | 39 |
DOC_PNG_IMAGES = \ |
| 39 | 40 |
$(DOC_EPS_IMAGES:%.eps=doc/gen-images/%.png) |
| 40 | 41 |
|
| 41 | 42 |
EXTRA_DIST += $(DOC_EPS_IMAGES:%=doc/images/%) |
| 42 | 43 |
|
| 43 | 44 |
doc/html: |
| 44 | 45 |
$(MAKE) $(AM_MAKEFLAGS) html |
| 45 | 46 |
|
| 46 | 47 |
GS_COMMAND=gs -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 |
| 47 | 48 |
|
| 48 | 49 |
$(DOC_EPS_IMAGES18:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps |
| 49 | 50 |
-mkdir doc/gen-images |
| 50 | 51 |
if test ${gs_found} = yes; then \
|
| 51 | 52 |
$(GS_COMMAND) -sDEVICE=pngalpha -r18 -sOutputFile=$@ $<; \ |
| 52 | 53 |
else \ |
| 53 | 54 |
echo; \ |
| ... | ... |
@@ -502,50 +502,50 @@ |
| 502 | 502 |
easier than in general graphs. The goal of the matching optimization |
| 503 | 503 |
can be finding maximum cardinality, maximum weight or minimum cost |
| 504 | 504 |
matching. The search can be constrained to find perfect or |
| 505 | 505 |
maximum cardinality matching. |
| 506 | 506 |
|
| 507 | 507 |
The matching algorithms implemented in LEMON: |
| 508 | 508 |
- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm |
| 509 | 509 |
for calculating maximum cardinality matching in bipartite graphs. |
| 510 | 510 |
- \ref PrBipartiteMatching Push-relabel algorithm |
| 511 | 511 |
for calculating maximum cardinality matching in bipartite graphs. |
| 512 | 512 |
- \ref MaxWeightedBipartiteMatching |
| 513 | 513 |
Successive shortest path algorithm for calculating maximum weighted |
| 514 | 514 |
matching and maximum weighted bipartite matching in bipartite graphs. |
| 515 | 515 |
- \ref MinCostMaxBipartiteMatching |
| 516 | 516 |
Successive shortest path algorithm for calculating minimum cost maximum |
| 517 | 517 |
matching in bipartite graphs. |
| 518 | 518 |
- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating |
| 519 | 519 |
maximum cardinality matching in general graphs. |
| 520 | 520 |
- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating |
| 521 | 521 |
maximum weighted matching in general graphs. |
| 522 | 522 |
- \ref MaxWeightedPerfectMatching |
| 523 | 523 |
Edmond's blossom shrinking algorithm for calculating maximum weighted |
| 524 | 524 |
perfect matching in general graphs. |
| 525 | 525 |
|
| 526 |
\image html bipartite_matching.png |
|
| 527 |
\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth |
|
| 526 |
\image html matching.png |
|
| 527 |
\image latex matching.eps "Bipartite Matching" width=\textwidth |
|
| 528 | 528 |
*/ |
| 529 | 529 |
|
| 530 | 530 |
/** |
| 531 | 531 |
@defgroup graph_properties Connectivity and Other Graph Properties |
| 532 | 532 |
@ingroup algs |
| 533 | 533 |
\brief Algorithms for discovering the graph properties |
| 534 | 534 |
|
| 535 | 535 |
This group contains the algorithms for discovering the graph properties |
| 536 | 536 |
like connectivity, bipartiteness, euler property, simplicity etc. |
| 537 | 537 |
|
| 538 | 538 |
\image html connected_components.png |
| 539 | 539 |
\image latex connected_components.eps "Connected components" width=\textwidth |
| 540 | 540 |
*/ |
| 541 | 541 |
|
| 542 | 542 |
/** |
| 543 | 543 |
@defgroup planar Planarity Embedding and Drawing |
| 544 | 544 |
@ingroup algs |
| 545 | 545 |
\brief Algorithms for planarity checking, embedding and drawing |
| 546 | 546 |
|
| 547 | 547 |
This group contains the algorithms for planarity checking, |
| 548 | 548 |
embedding and drawing. |
| 549 | 549 |
|
| 550 | 550 |
\image html planar.png |
| 551 | 551 |
\image latex planar.eps "Plane graph" width=\textwidth |
0 comments (0 inline)