Changeset - r865:d48d79b11f5b
« 864:d3ea19
866:2d9c65 »
gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Replace figure at matching doc #348 The original bibartite_matching.eps is kept for future use.
0 3 1
default
4 files changed with 134 insertions and 2 deletions:
doc/images/matching.eps
130
doc/CMakeLists.txt
1
doc/Makefile.am
1
doc/groups.dox
2
2
↑ Collapse diff ↑
doc/images/matching.eps
Ignore white space 24 line context
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


			




        

    

    

    

        

            

                

                    doc/CMakeLists.txt
                

                

                  
                  
                  
                  Ignore white space
                  6 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -11,24 +11,25 @@


			




	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}

			




        

    

    

    

        

            

                

                    doc/Makefile.am
                

                

                  
                  
                  
                  Ignore white space
                  6 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -18,24 +18,25 @@


			




	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/%)

			




        

    

    

    

        

            

                

                    doc/groups.dox
                

                

                  
                  
                  
                  Ignore white space
                  6 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -514,26 +514,26 @@


			




	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

			




        

    






    
    



    


    

     
    
0 comments (0 inline)