1.1 --- a/Makefile.in Sun Feb 21 15:07:59 2010 +0100
1.2 +++ b/Makefile.in Sun Feb 21 18:34:28 2010 +0100
1.3 @@ -2,8 +2,13 @@
1.4
1.5 EPS_IMAGES18 =
1.6
1.7 +EPS_IMAGES27 = \
1.8 + splitnodes1.eps \
1.9 + splitnodes2.eps
1.10 +
1.11 EPS_IMAGES = \
1.12 - $(EPS_IMAGES18)
1.13 + $(EPS_IMAGES18) \
1.14 + $(EPS_IMAGES27)
1.15
1.16 PNG_IMAGES = \
1.17 $(EPS_IMAGES:%.eps=gen-images/%.png)
1.18 @@ -18,6 +23,10 @@
1.19 -mkdir -p gen-images
1.20 $(GS_COMMAND) -sDEVICE=pngalpha -r18 -sOutputFile=$@ $<
1.21
1.22 +$(EPS_IMAGES27:%.eps=gen-images/%.png): gen-images/%.png: images/%.eps
1.23 + -mkdir -p gen-images
1.24 + $(GS_COMMAND) -sDEVICE=pngalpha -r27 -sOutputFile=$@ $<
1.25 +
1.26 html: Doxyfile-gen $(PNG_IMAGES)
1.27 -mkdir -p gen-dox
1.28 ./scripts/titlegen.py
2.1 --- a/adaptors.dox Sun Feb 21 15:07:59 2010 +0100
2.2 +++ b/adaptors.dox Sun Feb 21 18:34:28 2010 +0100
2.3 @@ -359,6 +359,12 @@
2.4 The maximum number of \e edge \e disjoint paths from a source node to
2.5 a sink node in a digraph can be easily computed using a maximum flow
2.6 algorithm with all arc capacities set to 1.
2.7 +For example, in the following digraph, four arc disjoint paths can be found
2.8 +from the node on the left to the node on the right.
2.9 +
2.10 +\image html splitnodes1.png
2.11 +\image latex splitnodes1.eps "Arc disjoint paths" width=\textwidth
2.12 +
2.13 On the other hand, \e node \e disjoint paths cannot be found directly
2.14 using a standard algorithm.
2.15 However, \ref SplitNodes adaptor makes it really simple.
2.16 @@ -366,6 +372,10 @@
2.17 bottleneck of the flow (i.e. the minimum cut) will be formed by bind arcs,
2.18 thus the found flow will correspond to the union of some node disjoint
2.19 paths in terms of the original digraph.
2.20 +For example, in the above digraph, there are only three node disjoint paths.
2.21 +
2.22 +\image html splitnodes2.png
2.23 +\image latex splitnodes2.eps "Node disjoint paths" width=\textwidth
2.24
2.25 In flow, circulation and matching problems, the residual network is of
2.26 particular importance, which is implemented in \ref ResidualDigraph.
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/images/splitnodes1.eps Sun Feb 21 18:34:28 2010 +0100
3.3 @@ -0,0 +1,116 @@
3.4 +%!PS-Adobe-2.0 EPSF-2.0
3.5 +%%Title: edge disjoint path
3.6 +%%Copyright: (C) 2006 LEMON Project
3.7 +%%Creator: LEMON, graphToEps()
3.8 +%%CreationDate: Fri May 12 01:53:21 2006
3.9 +%%BoundingBox: -290 -170 470 230
3.10 +%%EndComments
3.11 +/lb { setlinewidth setrgbcolor newpath moveto
3.12 + 4 2 roll 1 index 1 index curveto stroke } bind def
3.13 +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
3.14 +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
3.15 +/sq { newpath 2 index 1 index add 2 index 2 index add moveto
3.16 + 2 index 1 index sub 2 index 2 index add lineto
3.17 + 2 index 1 index sub 2 index 2 index sub lineto
3.18 + 2 index 1 index add 2 index 2 index sub lineto
3.19 + closepath pop pop pop} bind def
3.20 +/di { newpath 2 index 1 index add 2 index moveto
3.21 + 2 index 2 index 2 index add lineto
3.22 + 2 index 1 index sub 2 index lineto
3.23 + 2 index 2 index 2 index sub lineto
3.24 + closepath pop pop pop} bind def
3.25 +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
3.26 + setrgbcolor 1.1 div c fill
3.27 + } bind def
3.28 +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
3.29 + setrgbcolor 1.1 div sq fill
3.30 + } bind def
3.31 +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
3.32 + setrgbcolor 1.1 div di fill
3.33 + } bind def
3.34 +/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
3.35 + newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
3.36 + lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
3.37 + 5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
3.38 + 5 index 5 index 5 index c fill
3.39 + setrgbcolor 1.1 div c fill
3.40 + } bind def
3.41 +/nmale {
3.42 + 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
3.43 + newpath 5 index 5 index moveto
3.44 + 5 index 4 index 1 mul 1.5 mul add
3.45 + 5 index 5 index 3 sqrt 1.5 mul mul add
3.46 + 1 index 1 index lineto
3.47 + 1 index 1 index 7 index sub moveto
3.48 + 1 index 1 index lineto
3.49 + exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
3.50 + stroke
3.51 + 5 index 5 index 5 index c fill
3.52 + setrgbcolor 1.1 div c fill
3.53 + } bind def
3.54 +/arrl 1 def
3.55 +/arrw 0.3 def
3.56 +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
3.57 +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
3.58 + /w exch def /len exch def
3.59 + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
3.60 + len w sub arrl sub dx dy lrl
3.61 + arrw dy dx neg lrl
3.62 + dx arrl w add mul dy w 2 div arrw add mul sub
3.63 + dy arrl w add mul dx w 2 div arrw add mul add rlineto
3.64 + dx arrl w add mul neg dy w 2 div arrw add mul sub
3.65 + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
3.66 + arrw dy dx neg lrl
3.67 + len w sub arrl sub neg dx dy lrl
3.68 + closepath fill } bind def
3.69 +/cshow { 2 index 2 index moveto dup stringwidth pop
3.70 + neg 2 div fosi .35 mul neg rmoveto show pop pop} def
3.71 +
3.72 +gsave
3.73 +10 dup scale
3.74 +%Edges:
3.75 +gsave
3.76 +15.6433 0.3 0.841178 -0.540758 -27 5 1 0 0 arr
3.77 +19.5913 0.3 0.874157 0.485643 -27 5 1 0 0 arr
3.78 +10.1803 0.3 0.98387 -0.178885 -20 17 1 0 0 arr
3.79 +20.587 0.3 0.972806 0.231621 -18 -14 1 0 0 arr
3.80 +15.7631 0.3 0.95448 -0.298275 -13 -4 0 0 0 arr
3.81 +15.9706 0.3 0.707107 -0.707107 -9 15 1 0 0 arr
3.82 +16.4642 0.3 0.916157 0.400819 -13 -4 1 0 0 arr
3.83 +14.5242 0.3 0.966235 -0.257663 -12 7 0 0 0 arr
3.84 +10.6619 0.3 0.857493 0.514496 -9 15 1 0 0 arr
3.85 +22.4094 0.3 0.939793 -0.341743 3 3 1 0 0 arr
3.86 +27.1602 0.3 0.958798 -0.284088 1 21 1 0 0 arr
3.87 +25.9258 0.3 0.928477 0.371391 3 3 1 0 0 arr
3.88 +25.9072 0.3 0.743294 0.668965 25 -15 1 0 0 arr
3.89 +20.5407 0.3 0.928477 0.371391 25 -5 1 0 0 arr
3.90 +18.7231 0.3 0.861934 -0.50702 28 13 1 0 0 arr
3.91 +14.2315 0.3 0.393919 0.919145 39 -11 0 0 0 arr
3.92 +10.6619 0.3 0.514496 -0.857493 39 13 1 0 0 arr
3.93 +20.0238 0.3 0.428086 -0.903738 -27 5 1 0 0 arr
3.94 +21.8035 0.3 0.964764 -0.263117 3 -9 1 0 0 arr
3.95 +14.1328 0.3 0.991228 0.132164 -27 5 0 0 0 arr
3.96 +13.5602 0.3 0.961524 0.274721 25 -15 0 0 0 arr
3.97 +10 0.3 1 0 28 13 1 0 0 arr
3.98 +12.8924 0.3 0.503871 0.863779 -27 5 1 0 0 arr
3.99 +grestore
3.100 +%Nodes:
3.101 +gsave
3.102 +-27 5 1 1 1 1 nc
3.103 +-13 -4 1 1 1 1 nc
3.104 +-9 15 1 1 1 1 nc
3.105 +3 -9 1 1 1 1 nc
3.106 +3 3 1 1 1 1 nc
3.107 +1 21 1 1 1 1 nc
3.108 +25 -5 1 1 1 1 nc
3.109 +28 13 1 1 1 1 nc
3.110 +45 3 1 1 1 1 nc
3.111 +-18 -14 1 1 1 1 nc
3.112 +25 -15 1 1 1 1 nc
3.113 +-12 7 1 1 1 1 nc
3.114 +39 -11 1 1 1 1 nc
3.115 +39 13 1 1 1 1 nc
3.116 +-20 17 1 1 1 1 nc
3.117 +grestore
3.118 +grestore
3.119 +showpage
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/images/splitnodes2.eps Sun Feb 21 18:34:28 2010 +0100
4.3 @@ -0,0 +1,146 @@
4.4 +%!PS-Adobe-2.0 EPSF-2.0
4.5 +%%Title: node disjoint path
4.6 +%%Copyright: (C) 2006 LEMON Project
4.7 +%%Creator: LEMON, graphToEps()
4.8 +%%CreationDate: Fri May 12 01:53:21 2006
4.9 +%%BoundingBox: -290 -170 520 230
4.10 +%%EndComments
4.11 +/lb { setlinewidth setrgbcolor newpath moveto
4.12 + 4 2 roll 1 index 1 index curveto stroke } bind def
4.13 +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
4.14 +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
4.15 +/sq { newpath 2 index 1 index add 2 index 2 index add moveto
4.16 + 2 index 1 index sub 2 index 2 index add lineto
4.17 + 2 index 1 index sub 2 index 2 index sub lineto
4.18 + 2 index 1 index add 2 index 2 index sub lineto
4.19 + closepath pop pop pop} bind def
4.20 +/di { newpath 2 index 1 index add 2 index moveto
4.21 + 2 index 2 index 2 index add lineto
4.22 + 2 index 1 index sub 2 index lineto
4.23 + 2 index 2 index 2 index sub lineto
4.24 + closepath pop pop pop} bind def
4.25 +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
4.26 + setrgbcolor 1.1 div c fill
4.27 + } bind def
4.28 +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
4.29 + setrgbcolor 1.1 div sq fill
4.30 + } bind def
4.31 +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
4.32 + setrgbcolor 1.1 div di fill
4.33 + } bind def
4.34 +/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
4.35 + newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
4.36 + lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
4.37 + 5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
4.38 + 5 index 5 index 5 index c fill
4.39 + setrgbcolor 1.1 div c fill
4.40 + } bind def
4.41 +/nmale {
4.42 + 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
4.43 + newpath 5 index 5 index moveto
4.44 + 5 index 4 index 1 mul 1.5 mul add
4.45 + 5 index 5 index 3 sqrt 1.5 mul mul add
4.46 + 1 index 1 index lineto
4.47 + 1 index 1 index 7 index sub moveto
4.48 + 1 index 1 index lineto
4.49 + exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
4.50 + stroke
4.51 + 5 index 5 index 5 index c fill
4.52 + setrgbcolor 1.1 div c fill
4.53 + } bind def
4.54 +/arrl 1 def
4.55 +/arrw 0.3 def
4.56 +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
4.57 +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
4.58 + /w exch def /len exch def
4.59 + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
4.60 + len w sub arrl sub dx dy lrl
4.61 + arrw dy dx neg lrl
4.62 + dx arrl w add mul dy w 2 div arrw add mul sub
4.63 + dy arrl w add mul dx w 2 div arrw add mul add rlineto
4.64 + dx arrl w add mul neg dy w 2 div arrw add mul sub
4.65 + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
4.66 + arrw dy dx neg lrl
4.67 + len w sub arrl sub neg dx dy lrl
4.68 + closepath fill } bind def
4.69 +/cshow { 2 index 2 index moveto dup stringwidth pop
4.70 + neg 2 div fosi .35 mul neg rmoveto show pop pop} def
4.71 +
4.72 +gsave
4.73 +10 dup scale
4.74 +%Edges:
4.75 +gsave
4.76 +4 0.3 1 0 -27 5 0 0 0 arr
4.77 +4 0.3 1 0 -13 -4 1 0 0 arr
4.78 +4 0.3 1 0 -9 15 1 0 0 arr
4.79 +4 0.3 1 0 3 -9 1 0 0 arr
4.80 +4 0.3 1 0 3 3 1 0 0 arr
4.81 +4 0.3 1 0 1 21 1 0 0 arr
4.82 +4 0.3 1 0 25 -5 1 0 0 arr
4.83 +4 0.3 1 0 28 13 1 0 0 arr
4.84 +4 0.3 1 0 45 3 0 0 0 arr
4.85 +4 0.3 1 0 -18 -14 1 0 0 arr
4.86 +4 0.3 1 0 25 -15 1 0 0 arr
4.87 +4 0.3 1 0 -12 7 0 0 0 arr
4.88 +4 0.3 1 0 39 -11 0 0 0 arr
4.89 +4 0.3 1 0 39 13 0 0 0 arr
4.90 +4 0.3 1 0 -20 17 1 0 0 arr
4.91 +11.7279 0.3 0.707107 -0.707107 -22 5 1 0 0 arr
4.92 +15.4012 0.3 0.792624 0.609711 -22 5 0 0 0 arr
4.93 +5.32455 0.3 0.948683 -0.316228 -15 17 1 0 0 arr
4.94 +15.7631 0.3 0.95448 0.298275 -13 -14 1 0 0 arr
4.95 +11.083 0.3 0.910366 -0.413803 -8 -4 0 0 0 arr
4.96 +12.8924 0.3 0.503871 -0.863779 -4 15 0 0 0 arr
4.97 +12.0384 0.3 0.843661 0.536875 -8 -4 1 0 0 arr
4.98 +9.77033 0.3 0.928477 -0.371391 -7 7 0 0 0 arr
4.99 +6.81025 0.3 0.640184 0.768221 -4 15 1 0 0 arr
4.100 +17.7883 0.3 0.904819 -0.425797 8 3 1 0 0 arr
4.101 +22.4094 0.3 0.939793 -0.341743 6 21 1 0 0 arr
4.102 +21.3607 0.3 0.894427 0.447214 8 3 0 0 0 arr
4.103 +22.4307 0.3 0.640184 0.768221 30 -15 1 0 0 arr
4.104 +16 0.3 0.882353 0.470588 30 -5 1 0 0 arr
4.105 +14.6205 0.3 0.768221 -0.640184 33 13 1 0 0 arr
4.106 +13.0357 0.3 0.071247 0.997459 44 -11 0 0 0 arr
4.107 +9.04987 0.3 0.0995037 -0.995037 44 13 0 0 0 arr
4.108 +18.4165 0.3 0.20601 -0.97855 -22 5 1 0 0 arr
4.109 +17.0278 0.3 0.94299 -0.33282 8 -9 1 0 0 arr
4.110 +9.19804 0.3 0.980581 0.196116 -22 5 0 0 0 arr
4.111 +8.84886 0.3 0.913812 0.406138 30 -15 0 0 0 arr
4.112 +5 0.3 1 0 33 13 0 0 0 arr
4.113 +11.1655 0.3 0.164399 0.986394 -22 5 1 0 0 arr
4.114 +grestore
4.115 +%Nodes:
4.116 +gsave
4.117 +-27 5 1 1 1 1 nc
4.118 +-22 5 1 1 1 1 nc
4.119 +-13 -4 1 1 1 1 nc
4.120 +-8 -4 1 1 1 1 nc
4.121 +-9 15 1 1 1 1 nc
4.122 +-4 15 1 1 1 1 nc
4.123 +3 -9 1 1 1 1 nc
4.124 +8 -9 1 1 1 1 nc
4.125 +3 3 1 1 1 1 nc
4.126 +8 3 1 1 1 1 nc
4.127 +1 21 1 1 1 1 nc
4.128 +6 21 1 1 1 1 nc
4.129 +25 -5 1 1 1 1 nc
4.130 +30 -5 1 1 1 1 nc
4.131 +28 13 1 1 1 1 nc
4.132 +33 13 1 1 1 1 nc
4.133 +45 3 1 1 1 1 nc
4.134 +50 3 1 1 1 1 nc
4.135 +-18 -14 1 1 1 1 nc
4.136 +-13 -14 1 1 1 1 nc
4.137 +25 -15 1 1 1 1 nc
4.138 +30 -15 1 1 1 1 nc
4.139 +-12 7 1 1 1 1 nc
4.140 +-7 7 1 1 1 1 nc
4.141 +39 -11 1 1 1 1 nc
4.142 +44 -11 1 1 1 1 nc
4.143 +39 13 1 1 1 1 nc
4.144 +44 13 1 1 1 1 nc
4.145 +-20 17 1 1 1 1 nc
4.146 +-15 17 1 1 1 1 nc
4.147 +grestore
4.148 +grestore
4.149 +showpage