doc/images/edge_disjoint.eps
author deba
Tue, 17 Oct 2006 10:50:57 +0000
changeset 2247 269a0dcee70b
permissions -rw-r--r--
Update the Path concept
Concept check for paths

DirPath renamed to Path
The interface updated to the new lemon interface
Make difference between the empty path and the path from one node
Builder interface have not been changed
// I wanted but there was not accordance about it

UPath is removed
It was a buggy implementation, it could not iterate on the
nodes in the right order
Right way to use undirected paths => path of edges in undirected graphs

The tests have been modified to the current implementation
deba@2079
     1
%!PS-Adobe-2.0 EPSF-2.0
deba@2079
     2
%%Title: edge disjoint path
deba@2079
     3
%%Copyright: (C) 2006 LEMON Project
deba@2079
     4
%%Creator: LEMON, graphToEps()
deba@2079
     5
%%CreationDate: Fri May 12 01:53:21 2006
deba@2079
     6
%%BoundingBox: -290 -170 470 230
deba@2079
     7
%%EndComments
deba@2079
     8
/lb { setlinewidth setrgbcolor newpath moveto
deba@2079
     9
      4 2 roll 1 index 1 index curveto stroke } bind def
deba@2079
    10
/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
deba@2079
    11
/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
deba@2079
    12
/sq { newpath 2 index 1 index add 2 index 2 index add moveto
deba@2079
    13
      2 index 1 index sub 2 index 2 index add lineto
deba@2079
    14
      2 index 1 index sub 2 index 2 index sub lineto
deba@2079
    15
      2 index 1 index add 2 index 2 index sub lineto
deba@2079
    16
      closepath pop pop pop} bind def
deba@2079
    17
/di { newpath 2 index 1 index add 2 index moveto
deba@2079
    18
      2 index             2 index 2 index add lineto
deba@2079
    19
      2 index 1 index sub 2 index             lineto
deba@2079
    20
      2 index             2 index 2 index sub lineto
deba@2079
    21
      closepath pop pop pop} bind def
deba@2079
    22
/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
deba@2079
    23
     setrgbcolor 1.1 div c fill
deba@2079
    24
   } bind def
deba@2079
    25
/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
deba@2079
    26
     setrgbcolor 1.1 div sq fill
deba@2079
    27
   } bind def
deba@2079
    28
/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
deba@2079
    29
     setrgbcolor 1.1 div di fill
deba@2079
    30
   } bind def
deba@2079
    31
/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
deba@2079
    32
  newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
deba@2079
    33
  lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
deba@2079
    34
  5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
deba@2079
    35
  5 index 5 index 5 index c fill
deba@2079
    36
  setrgbcolor 1.1 div c fill
deba@2079
    37
  } bind def
deba@2079
    38
/nmale {
deba@2079
    39
  0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
deba@2079
    40
  newpath 5 index 5 index moveto
deba@2079
    41
  5 index 4 index 1 mul 1.5 mul add
deba@2079
    42
  5 index 5 index 3 sqrt 1.5 mul mul add
deba@2079
    43
  1 index 1 index lineto
deba@2079
    44
  1 index 1 index 7 index sub moveto
deba@2079
    45
  1 index 1 index lineto
deba@2079
    46
  exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
deba@2079
    47
  stroke
deba@2079
    48
  5 index 5 index 5 index c fill
deba@2079
    49
  setrgbcolor 1.1 div c fill
deba@2079
    50
  } bind def
deba@2079
    51
/arrl 1 def
deba@2079
    52
/arrw 0.3 def
deba@2079
    53
/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
deba@2079
    54
/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
deba@2079
    55
       /w exch def /len exch def
deba@2079
    56
       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
deba@2079
    57
       len w sub arrl sub dx dy lrl
deba@2079
    58
       arrw dy dx neg lrl
deba@2079
    59
       dx arrl w add mul dy w 2 div arrw add mul sub
deba@2079
    60
       dy arrl w add mul dx w 2 div arrw add mul add rlineto
deba@2079
    61
       dx arrl w add mul neg dy w 2 div arrw add mul sub
deba@2079
    62
       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
deba@2079
    63
       arrw dy dx neg lrl
deba@2079
    64
       len w sub arrl sub neg dx dy lrl
deba@2079
    65
       closepath fill } bind def
deba@2079
    66
/cshow { 2 index 2 index moveto dup stringwidth pop
deba@2079
    67
         neg 2 div fosi .35 mul neg rmoveto show pop pop} def
deba@2079
    68
deba@2079
    69
gsave
deba@2079
    70
10 dup scale
deba@2079
    71
%Edges:
deba@2079
    72
gsave
deba@2079
    73
15.6433 0.3 0.841178 -0.540758 -27 5 1 0 0 arr
deba@2079
    74
19.5913 0.3 0.874157 0.485643 -27 5 1 0 0 arr
deba@2079
    75
10.1803 0.3 0.98387 -0.178885 -20 17 1 0 0 arr
deba@2079
    76
20.587 0.3 0.972806 0.231621 -18 -14 1 0 0 arr
deba@2079
    77
15.7631 0.3 0.95448 -0.298275 -13 -4 0 0 0 arr
deba@2079
    78
15.9706 0.3 0.707107 -0.707107 -9 15 1 0 0 arr
deba@2079
    79
16.4642 0.3 0.916157 0.400819 -13 -4 1 0 0 arr
deba@2079
    80
14.5242 0.3 0.966235 -0.257663 -12 7 0 0 0 arr
deba@2079
    81
10.6619 0.3 0.857493 0.514496 -9 15 1 0 0 arr
deba@2079
    82
22.4094 0.3 0.939793 -0.341743 3 3 1 0 0 arr
deba@2079
    83
27.1602 0.3 0.958798 -0.284088 1 21 1 0 0 arr
deba@2079
    84
25.9258 0.3 0.928477 0.371391 3 3 1 0 0 arr
deba@2079
    85
25.9072 0.3 0.743294 0.668965 25 -15 1 0 0 arr
deba@2079
    86
20.5407 0.3 0.928477 0.371391 25 -5 1 0 0 arr
deba@2079
    87
18.7231 0.3 0.861934 -0.50702 28 13 1 0 0 arr
deba@2079
    88
14.2315 0.3 0.393919 0.919145 39 -11 0 0 0 arr
deba@2079
    89
10.6619 0.3 0.514496 -0.857493 39 13 1 0 0 arr
deba@2079
    90
20.0238 0.3 0.428086 -0.903738 -27 5 1 0 0 arr
deba@2079
    91
21.8035 0.3 0.964764 -0.263117 3 -9 1 0 0 arr
deba@2079
    92
14.1328 0.3 0.991228 0.132164 -27 5 0 0 0 arr
deba@2079
    93
13.5602 0.3 0.961524 0.274721 25 -15 0 0 0 arr
deba@2079
    94
10 0.3 1 0 28 13 1 0 0 arr
deba@2079
    95
12.8924 0.3 0.503871 0.863779 -27 5 1 0 0 arr
deba@2079
    96
grestore
deba@2079
    97
%Nodes:
deba@2079
    98
gsave
deba@2079
    99
-27 5 1 1 1 1 nc
deba@2079
   100
-13 -4 1 1 1 1 nc
deba@2079
   101
-9 15 1 1 1 1 nc
deba@2079
   102
3 -9 1 1 1 1 nc
deba@2079
   103
3 3 1 1 1 1 nc
deba@2079
   104
1 21 1 1 1 1 nc
deba@2079
   105
25 -5 1 1 1 1 nc
deba@2079
   106
28 13 1 1 1 1 nc
deba@2079
   107
45 3 1 1 1 1 nc
deba@2079
   108
-18 -14 1 1 1 1 nc
deba@2079
   109
25 -15 1 1 1 1 nc
deba@2079
   110
-12 7 1 1 1 1 nc
deba@2079
   111
39 -11 1 1 1 1 nc
deba@2079
   112
39 13 1 1 1 1 nc
deba@2079
   113
-20 17 1 1 1 1 nc
deba@2079
   114
grestore
deba@2079
   115
grestore
deba@2079
   116
showpage