# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1268554384 -3600
# Node ID d48d79b11f5b9254ff3d516a587286dc0560609b
# Parent d3ea191c341258fddc1366953daefc8b1903073c
Replace figure at matching doc #348
The original bibartite_matching.eps is kept for future use.
diff -r d3ea191c3412 -r d48d79b11f5b doc/CMakeLists.txt
--- a/doc/CMakeLists.txt Sat Mar 13 22:01:38 2010 +0100
+++ b/doc/CMakeLists.txt Sun Mar 14 09:13:04 2010 +0100
@@ -20,6 +20,7 @@
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
diff -r d3ea191c3412 -r d48d79b11f5b doc/Makefile.am
--- a/doc/Makefile.am Sat Mar 13 22:01:38 2010 +0100
+++ b/doc/Makefile.am Sun Mar 14 09:13:04 2010 +0100
@@ -27,6 +27,7 @@
bipartite_partitions.eps \
connected_components.eps \
edge_biconnected_components.eps \
+ matching.eps \
node_biconnected_components.eps \
planar.eps \
strongly_connected_components.eps
diff -r d3ea191c3412 -r d48d79b11f5b doc/groups.dox
--- a/doc/groups.dox Sat Mar 13 22:01:38 2010 +0100
+++ b/doc/groups.dox Sun Mar 14 09:13:04 2010 +0100
@@ -523,8 +523,8 @@
Edmond's blossom shrinking algorithm for calculating maximum weighted
perfect matching in general graphs.
-\image html bipartite_matching.png
-\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
+\image html matching.png
+\image latex matching.eps "Bipartite Matching" width=\textwidth
*/
/**
diff -r d3ea191c3412 -r d48d79b11f5b doc/images/matching.eps
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/images/matching.eps Sun Mar 14 09:13:04 2010 +0100
@@ -0,0 +1,130 @@
+%!PS-Adobe-2.0 EPSF-2.0
+%%Creator: LEMON, graphToEps()
+%%CreationDate: Sun Mar 14 09:08:34 2010
+%%BoundingBox: -353 -264 559 292
+%%EndComments
+/lb { setlinewidth setrgbcolor newpath moveto
+ 4 2 roll 1 index 1 index curveto stroke } bind def
+/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
+/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
+/sq { newpath 2 index 1 index add 2 index 2 index add moveto
+ 2 index 1 index sub 2 index 2 index add lineto
+ 2 index 1 index sub 2 index 2 index sub lineto
+ 2 index 1 index add 2 index 2 index sub lineto
+ closepath pop pop pop} bind def
+/di { newpath 2 index 1 index add 2 index moveto
+ 2 index 2 index 2 index add lineto
+ 2 index 1 index sub 2 index lineto
+ 2 index 2 index 2 index sub lineto
+ closepath pop pop pop} bind def
+/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
+ setrgbcolor 1.1 div c fill
+ } bind def
+/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
+ setrgbcolor 1.1 div sq fill
+ } bind def
+/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
+ setrgbcolor 1.1 div di fill
+ } bind def
+/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
+ newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
+ lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
+ 5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
+ 5 index 5 index 5 index c fill
+ setrgbcolor 1.1 div c fill
+ } bind def
+/nmale {
+ 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
+ newpath 5 index 5 index moveto
+ 5 index 4 index 1 mul 1.5 mul add
+ 5 index 5 index 3 sqrt 1.5 mul mul add
+ 1 index 1 index lineto
+ 1 index 1 index 7 index sub moveto
+ 1 index 1 index lineto
+ exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
+ stroke
+ 5 index 5 index 5 index c fill
+ setrgbcolor 1.1 div c fill
+ } bind def
+/arrl 1 def
+/arrw 0.3 def
+/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
+/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
+ /w exch def /len exch def
+ newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
+ len w sub arrl sub dx dy lrl
+ arrw dy dx neg lrl
+ dx arrl w add mul dy w 2 div arrw add mul sub
+ dy arrl w add mul dx w 2 div arrw add mul add rlineto
+ dx arrl w add mul neg dy w 2 div arrw add mul sub
+ dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
+ arrw dy dx neg lrl
+ len w sub arrl sub neg dx dy lrl
+ closepath fill } bind def
+/cshow { 2 index 2 index moveto dup stringwidth pop
+ neg 2 div fosi .35 mul neg rmoveto show pop pop} def
+
+gsave
+%Arcs:
+gsave
+140.321 266.249 -327.729 150.06 0 0 0 4.99223 l
+82.1207 -238.726 -245.288 -110.743 0 0 0 4.99223 l
+336.635 -229.036 533.603 13.109 0 0 0 4.99223 l
+53.8598 -45.8071 -245.288 -110.743 0 0 0 4.99223 l
+-75.5617 118.579 -327.729 150.06 0 0 0 4.99223 l
+-327.729 150.06 -245.288 -110.743 1 0 0 11.9813 l
+533.603 13.109 218.184 -84.2955 0 0 0 4.99223 l
+39.87 175.035 141.163 67.2575 0 0 0 4.99223 l
+53.8598 -45.8071 -75.5617 118.579 0 0 0 4.99223 l
+-102.406 -141.267 82.1207 -238.726 0 0 0 4.99223 l
+399.144 166.894 533.603 13.109 1 0 0 11.9813 l
+39.87 175.035 140.321 266.249 1 0 0 11.9813 l
+399.144 166.894 140.321 266.249 0 0 0 4.99223 l
+399.144 166.894 141.163 67.2575 0 0 0 4.99223 l
+53.8598 -45.8071 204.765 -173.77 0 0 0 4.99223 l
+82.1207 -238.726 204.765 -173.77 0 0 0 4.99223 l
+258.227 61.658 399.144 166.894 0 0 0 4.99223 l
+53.8598 -45.8071 -102.406 -141.267 1 0 0 11.9813 l
+175.073 -37.4477 141.163 67.2575 0 0 0 4.99223 l
+258.227 61.658 380 0 0 0 0 4.99223 l
+34.6739 40.8267 -75.5617 118.579 1 0 0 11.9813 l
+380 0 533.603 13.109 0 0 0 4.99223 l
+175.073 -37.4477 380 0 0 0 0 4.99223 l
+218.184 -84.2955 204.765 -173.77 0 0 0 4.99223 l
+53.8598 -45.8071 34.6739 40.8267 0 0 0 4.99223 l
+167.905 -213.988 82.1207 -238.726 1 0 0 11.9813 l
+336.635 -229.036 204.765 -173.77 1 0 0 11.9813 l
+336.635 -229.036 167.905 -213.988 0 0 0 4.99223 l
+329.08 -26.3098 218.184 -84.2955 0 0 0 4.99223 l
+39.87 175.035 -75.5617 118.579 0 0 0 4.99223 l
+53.8598 -45.8071 175.073 -37.4477 0 0 0 4.99223 l
+34.6739 40.8267 141.163 67.2575 0 0 0 4.99223 l
+258.227 61.658 141.163 67.2575 1 0 0 11.9813 l
+175.073 -37.4477 218.184 -84.2955 1 0 0 11.9813 l
+380 0 329.08 -26.3098 1 0 0 11.9813 l
+grestore
+%Nodes:
+gsave
+-245.288 -110.743 14.9767 1 1 1 nc
+204.765 -173.77 14.9767 1 1 1 nc
+-327.729 150.06 14.9767 1 1 1 nc
+-75.5617 118.579 14.9767 1 1 1 nc
+218.184 -84.2955 14.9767 1 1 1 nc
+140.321 266.249 14.9767 1 1 1 nc
+141.163 67.2575 14.9767 1 1 1 nc
+82.1207 -238.726 14.9767 1 1 1 nc
+329.08 -26.3098 14.9767 1 1 1 nc
+-102.406 -141.267 14.9767 1 1 1 nc
+533.603 13.109 14.9767 1 1 1 nc
+167.905 -213.988 14.9767 1 1 1 nc
+336.635 -229.036 14.9767 1 1 1 nc
+380 0 14.9767 1 1 1 nc
+399.144 166.894 14.9767 1 1 1 nc
+34.6739 40.8267 14.9767 1 1 1 nc
+39.87 175.035 14.9767 1 1 1 nc
+175.073 -37.4477 14.9767 1 1 1 nc
+53.8598 -45.8071 14.9767 1 1 1 nc
+258.227 61.658 14.9767 1 1 1 nc
+grestore
+grestore
+showpage