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).
     1 %!PS-Adobe-2.0 EPSF-2.0
     2 %%Title: LEMON GraphToEps figure
     3 %%Creator: LEMON GraphToEps function
     4 %%BoundingBox: 0 -199 200 200
     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 100 dup scale
    69 %Edges:
    70 gsave
    71 grestore
    72 %Nodes:
    73 gsave
    74 1 1 1 0.2 1 0.2 nfemale
    75 grestore
    76 grestore
    77 showpage