doc/images/nodeshape_2.eps
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 651 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 0 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
/arrl 1 def
ladanyi@152
    30
/arrw 0.3 def
ladanyi@152
    31
/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
ladanyi@152
    32
/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
ladanyi@152
    33
       /w exch def /len exch def
ladanyi@152
    34
       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
ladanyi@152
    35
       len w sub arrl sub dx dy lrl
ladanyi@152
    36
       arrw dy dx neg lrl
ladanyi@152
    37
       dx arrl w add mul dy w 2 div arrw add mul sub
ladanyi@152
    38
       dy arrl w add mul dx w 2 div arrw add mul add rlineto
ladanyi@152
    39
       dx arrl w add mul neg dy w 2 div arrw add mul sub
ladanyi@152
    40
       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
ladanyi@152
    41
       arrw dy dx neg lrl
ladanyi@152
    42
       len w sub arrl sub neg dx dy lrl
ladanyi@152
    43
       closepath fill } bind def
ladanyi@152
    44
/cshow { 2 index 2 index moveto dup stringwidth pop
ladanyi@152
    45
         neg 2 div fosi .35 mul neg rmoveto show pop pop} def
ladanyi@152
    46
ladanyi@152
    47
gsave
ladanyi@152
    48
100 dup scale
ladanyi@152
    49
%Edges:
ladanyi@152
    50
gsave
ladanyi@152
    51
grestore
ladanyi@152
    52
%Nodes:
ladanyi@152
    53
gsave
ladanyi@152
    54
1 1 1 0.2 1 0.2 ndi
ladanyi@152
    55
grestore
ladanyi@152
    56
grestore
ladanyi@152
    57
showpage