doc/images/nodeshape_4.eps
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
ladanyi@152
     1
%!PS-Adobe-2.0 EPSF-2.0
ladanyi@152
     2
%%Title: LEMON GraphToEps figure
ladanyi@152
     3
%%Creator: LEMON GraphToEps function
ladanyi@152
     4
%%BoundingBox: 0 -199 200 200
ladanyi@152
     5
%%EndComments
ladanyi@152
     6
/lb { setlinewidth setrgbcolor newpath moveto
ladanyi@152
     7
      4 2 roll 1 index 1 index curveto stroke } bind def
ladanyi@152
     8
/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
ladanyi@152
     9
/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
ladanyi@152
    10
/sq { newpath 2 index 1 index add 2 index 2 index add moveto
ladanyi@152
    11
      2 index 1 index sub 2 index 2 index add lineto
ladanyi@152
    12
      2 index 1 index sub 2 index 2 index sub lineto
ladanyi@152
    13
      2 index 1 index add 2 index 2 index sub lineto
ladanyi@152
    14
      closepath pop pop pop} bind def
ladanyi@152
    15
/di { newpath 2 index 1 index add 2 index moveto
ladanyi@152
    16
      2 index             2 index 2 index add lineto
ladanyi@152
    17
      2 index 1 index sub 2 index             lineto
ladanyi@152
    18
      2 index             2 index 2 index sub lineto
ladanyi@152
    19
      closepath pop pop pop} bind def
ladanyi@152
    20
/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
ladanyi@152
    21
     setrgbcolor 1.1 div c fill
ladanyi@152
    22
   } bind def
ladanyi@152
    23
/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
ladanyi@152
    24
     setrgbcolor 1.1 div sq fill
ladanyi@152
    25
   } bind def
ladanyi@152
    26
/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
ladanyi@152
    27
     setrgbcolor 1.1 div di fill
ladanyi@152
    28
   } bind def
ladanyi@152
    29
/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
ladanyi@152
    30
  newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
ladanyi@152
    31
  lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
ladanyi@152
    32
  5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
ladanyi@152
    33
  5 index 5 index 5 index c fill
ladanyi@152
    34
  setrgbcolor 1.1 div c fill
ladanyi@152
    35
  } bind def
ladanyi@152
    36
/nmale {
ladanyi@152
    37
  0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
ladanyi@152
    38
  newpath 5 index 5 index moveto
ladanyi@152
    39
  5 index 4 index 1 mul 1.5 mul add
ladanyi@152
    40
  5 index 5 index 3 sqrt 1.5 mul mul add
ladanyi@152
    41
  1 index 1 index lineto
ladanyi@152
    42
  1 index 1 index 7 index sub moveto
ladanyi@152
    43
  1 index 1 index lineto
ladanyi@152
    44
  exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
ladanyi@152
    45
  stroke
ladanyi@152
    46
  5 index 5 index 5 index c fill
ladanyi@152
    47
  setrgbcolor 1.1 div c fill
ladanyi@152
    48
  } bind def
ladanyi@152
    49
/arrl 1 def
ladanyi@152
    50
/arrw 0.3 def
ladanyi@152
    51
/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
ladanyi@152
    52
/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
ladanyi@152
    53
       /w exch def /len exch def
ladanyi@152
    54
       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
ladanyi@152
    55
       len w sub arrl sub dx dy lrl
ladanyi@152
    56
       arrw dy dx neg lrl
ladanyi@152
    57
       dx arrl w add mul dy w 2 div arrw add mul sub
ladanyi@152
    58
       dy arrl w add mul dx w 2 div arrw add mul add rlineto
ladanyi@152
    59
       dx arrl w add mul neg dy w 2 div arrw add mul sub
ladanyi@152
    60
       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
ladanyi@152
    61
       arrw dy dx neg lrl
ladanyi@152
    62
       len w sub arrl sub neg dx dy lrl
ladanyi@152
    63
       closepath fill } bind def
ladanyi@152
    64
/cshow { 2 index 2 index moveto dup stringwidth pop
ladanyi@152
    65
         neg 2 div fosi .35 mul neg rmoveto show pop pop} def
ladanyi@152
    66
ladanyi@152
    67
gsave
ladanyi@152
    68
100 dup scale
ladanyi@152
    69
%Edges:
ladanyi@152
    70
gsave
ladanyi@152
    71
grestore
ladanyi@152
    72
%Nodes:
ladanyi@152
    73
gsave
ladanyi@152
    74
1 1 1 0.2 1 0.2 nfemale
ladanyi@152
    75
grestore
ladanyi@152
    76
grestore
ladanyi@152
    77
showpage