File
modules/struct/graph.n
— part of check-in
[2cc341c42f]
at
2002-02-01 22:59:08
on branch trunk
—
log, csv testsuites strengthened to cover all paths in the code.
(user:
andreas_kupries
size: 10431)
0000: 27 5c 22 0a 27 5c 22 20 43 6f 70 79 72 69 67 68 '\".'\" Copyrigh
0010: 74 20 28 63 29 20 31 39 39 38 2d 32 30 30 30 20 t (c) 1998-2000
0020: 62 79 20 41 6a 75 62 61 20 53 6f 6c 75 74 69 6f by Ajuba Solutio
0030: 6e 73 2e 0a 27 5c 22 20 41 6c 6c 20 72 69 67 68 ns..'\" All righ
0040: 74 73 20 72 65 73 65 72 76 65 64 2e 0a 27 5c 22 ts reserved..'\"
0050: 20 0a 27 5c 22 20 52 43 53 3a 20 40 28 23 29 20 .'\" RCS: @(#)
0060: 24 49 64 3a 20 67 72 61 70 68 2e 6e 2c 76 20 31 $Id: graph.n,v 1
0070: 2e 38 20 32 30 30 32 2f 30 32 2f 30 31 20 32 32 .8 2002/02/01 22
0080: 3a 35 39 3a 30 38 20 61 6e 64 72 65 61 73 5f 6b :59:08 andreas_k
0090: 75 70 72 69 65 73 20 45 78 70 20 24 0a 27 5c 22 upries Exp $.'\"
00a0: 20 0a 2e 73 6f 20 6d 61 6e 2e 6d 61 63 72 6f 73 ..so man.macros
00b0: 0a 2e 54 48 20 67 72 61 70 68 20 6e 20 31 2e 32 ..TH graph n 1.2
00c0: 2e 31 20 53 74 72 75 63 74 20 22 54 63 6c 20 44 .1 Struct "Tcl D
00d0: 61 74 61 20 53 74 72 75 63 74 75 72 65 73 22 0a ata Structures".
00e0: 2e 42 53 0a 27 5c 22 20 4e 6f 74 65 3a 20 20 64 .BS.'\" Note: d
00f0: 6f 20 6e 6f 74 20 6d 6f 64 69 66 79 20 74 68 65 o not modify the
0100: 20 2e 53 48 20 4e 41 4d 45 20 6c 69 6e 65 20 69 .SH NAME line i
0110: 6d 6d 65 64 69 61 74 65 6c 79 20 62 65 6c 6f 77 mmediately below
0120: 21 0a 2e 53 48 20 4e 41 4d 45 0a 3a 3a 73 74 72 !..SH NAME.::str
0130: 75 63 74 3a 3a 67 72 61 70 68 20 5c 2d 20 43 72 uct::graph \- Cr
0140: 65 61 74 65 20 61 6e 64 20 6d 61 6e 69 70 75 6c eate and manipul
0150: 61 74 65 20 64 69 72 65 63 74 65 64 20 67 72 61 ate directed gra
0160: 70 68 20 6f 62 6a 65 63 74 73 0a 2e 53 48 20 53 ph objects..SH S
0170: 59 4e 4f 50 53 49 53 0a 5c 66 42 70 61 63 6b 61 YNOPSIS.\fBpacka
0180: 67 65 20 72 65 71 75 69 72 65 20 54 63 6c 20 38 ge require Tcl 8
0190: 2e 32 5c 66 52 0a 2e 73 70 0a 5c 66 42 70 61 63 .2\fR..sp.\fBpac
01a0: 6b 61 67 65 20 72 65 71 75 69 72 65 20 73 74 72 kage require str
01b0: 75 63 74 20 3f 31 2e 32 2e 31 3f 5c 66 52 0a 2e uct ?1.2.1?\fR..
01c0: 73 70 0a 5c 66 42 3a 3a 73 74 72 75 63 74 3a 3a sp.\fB::struct::
01d0: 67 72 61 70 68 5c 66 52 20 5c 66 49 67 72 61 70 graph\fR \fIgrap
01e0: 68 4e 61 6d 65 5c 66 52 0a 2e 73 70 0a 2e 42 45 hName\fR..sp..BE
01f0: 0a 2e 53 48 20 44 45 53 43 52 49 50 54 49 4f 4e ..SH DESCRIPTION
0200: 0a 2e 50 50 0a 54 68 65 20 5c 66 42 3a 3a 73 74 ..PP.The \fB::st
0210: 72 75 63 74 3a 3a 67 72 61 70 68 5c 66 52 20 63 ruct::graph\fR c
0220: 6f 6d 6d 61 6e 64 20 63 72 65 61 74 65 73 20 61 ommand creates a
0230: 20 6e 65 77 20 67 72 61 70 68 20 6f 62 6a 65 63 new graph objec
0240: 74 20 77 69 74 68 20 61 6e 0a 61 73 73 6f 63 69 t with an.associ
0250: 61 74 65 64 20 67 6c 6f 62 61 6c 20 54 63 6c 20 ated global Tcl
0260: 63 6f 6d 6d 61 6e 64 20 77 68 6f 73 65 20 6e 61 command whose na
0270: 6d 65 20 69 73 20 5c 66 49 67 72 61 70 68 4e 61 me is \fIgraphNa
0280: 6d 65 5c 66 52 2e 20 20 54 68 69 73 20 63 6f 6d me\fR. This com
0290: 6d 61 6e 64 0a 6d 61 79 20 62 65 20 75 73 65 64 mand.may be used
02a0: 20 74 6f 20 69 6e 76 6f 6b 65 20 76 61 72 69 6f to invoke vario
02b0: 75 73 20 6f 70 65 72 61 74 69 6f 6e 73 20 6f 6e us operations on
02c0: 20 74 68 65 20 67 72 61 70 68 2e 0a 49 74 20 68 the graph..It h
02d0: 61 73 20 74 68 65 0a 66 6f 6c 6c 6f 77 69 6e 67 as the.following
02e0: 20 67 65 6e 65 72 61 6c 20 66 6f 72 6d 3a 0a 2e general form:..
02f0: 43 53 0a 5c 66 49 67 72 61 70 68 4e 61 6d 65 20 CS.\fIgraphName
0300: 6f 70 74 69 6f 6e 20 5c 66 52 3f 5c 66 49 61 72 option \fR?\fIar
0310: 67 20 61 72 67 20 2e 2e 2e 5c 66 52 3f 0a 2e 43 g arg ...\fR?..C
0320: 45 0a 5c 66 49 4f 70 74 69 6f 6e 5c 66 52 20 61 E.\fIOption\fR a
0330: 6e 64 20 74 68 65 20 5c 66 49 61 72 67 5c 66 52 nd the \fIarg\fR
0340: 73 0a 64 65 74 65 72 6d 69 6e 65 20 74 68 65 20 s.determine the
0350: 65 78 61 63 74 20 62 65 68 61 76 69 6f 72 20 6f exact behavior o
0360: 66 20 74 68 65 20 63 6f 6d 6d 61 6e 64 2e 0a 2e f the command...
0370: 50 50 0a 41 20 64 69 72 65 63 74 65 64 20 67 72 PP.A directed gr
0380: 61 70 68 20 69 73 20 61 20 73 74 72 75 63 74 75 aph is a structu
0390: 72 65 20 63 6f 6e 74 61 69 6e 69 6e 67 20 74 77 re containing tw
03a0: 6f 20 63 6f 6c 6c 65 63 74 69 6f 6e 73 20 6f 66 o collections of
03b0: 0a 65 6c 65 6d 65 6e 74 73 2c 20 63 61 6c 6c 65 .elements, calle
03c0: 64 20 5c 66 49 6e 6f 64 65 73 5c 66 52 20 61 6e d \fInodes\fR an
03d0: 64 20 5c 66 49 61 72 63 73 5c 66 52 20 72 65 73 d \fIarcs\fR res
03e0: 70 2e 2c 20 74 6f 67 65 74 68 65 72 20 77 69 74 p., together wit
03f0: 68 20 61 0a 72 65 6c 61 74 69 6f 6e 20 28 22 63 h a.relation ("c
0400: 6f 6e 6e 65 63 74 69 76 69 74 79 22 29 20 74 68 onnectivity") th
0410: 61 74 20 70 6c 61 63 65 73 20 61 20 67 65 6e 65 at places a gene
0420: 72 61 6c 20 73 74 72 75 63 74 75 72 65 20 75 70 ral structure up
0430: 6f 6e 20 74 68 65 0a 6e 6f 64 65 73 20 61 6e 64 on the.nodes and
0440: 20 61 72 63 73 2e 0a 0a 45 61 63 68 20 61 72 63 arcs...Each arc
0450: 20 69 73 20 63 6f 6e 6e 65 63 74 65 64 20 74 6f is connected to
0460: 20 74 77 6f 20 6e 6f 64 65 73 2c 20 6f 6e 65 20 two nodes, one
0470: 6f 66 20 77 68 69 63 68 20 69 73 20 63 61 6c 6c of which is call
0480: 65 64 20 74 68 65 0a 5c 66 49 73 6f 75 72 63 65 ed the.\fIsource
0490: 5c 66 52 20 61 6e 64 20 74 68 65 20 6f 74 68 65 \fR and the othe
04a0: 72 20 74 68 65 20 5c 66 49 74 61 72 67 65 74 5c r the \fItarget\
04b0: 66 52 2e 20 54 68 69 73 20 69 6d 70 6f 73 65 73 fR. This imposes
04c0: 20 61 20 64 69 72 65 63 74 69 6f 6e 0a 75 70 6f a direction.upo
04d0: 6e 20 74 68 65 20 61 72 63 2c 20 77 68 69 63 68 n the arc, which
04e0: 20 69 73 20 73 61 69 64 20 74 6f 20 67 6f 20 66 is said to go f
04f0: 72 6f 6d 20 74 68 65 20 73 6f 75 72 63 65 20 74 rom the source t
0500: 6f 20 74 68 65 20 74 61 72 67 65 74 2e 20 49 74 o the target. It
0510: 20 69 73 0a 61 6c 6c 6f 77 65 64 20 74 68 61 74 is.allowed that
0520: 20 73 6f 75 72 63 65 20 61 6e 64 20 74 61 72 67 source and targ
0530: 65 74 20 6f 66 20 61 6e 20 61 72 63 20 61 72 65 et of an arc are
0540: 20 74 68 65 20 73 61 6d 65 20 6e 6f 64 65 2e 20 the same node.
0550: 53 75 63 68 20 61 6e 0a 61 72 63 20 69 73 20 63 Such an.arc is c
0560: 61 6c 6c 65 64 20 61 20 5c 66 49 6c 6f 6f 70 5c alled a \fIloop\
0570: 66 52 2e 20 57 68 65 6e 65 76 65 72 20 61 20 6e fR. Whenever a n
0580: 6f 64 65 20 69 73 20 73 6f 75 72 63 65 20 6f 72 ode is source or
0590: 20 74 61 72 67 65 74 20 6f 66 20 61 6e 0a 61 72 target of an.ar
05a0: 63 20 62 6f 74 68 20 61 72 65 20 73 61 69 64 20 c both are said
05b0: 74 6f 20 62 65 20 5c 66 49 61 64 6a 61 63 65 6e to be \fIadjacen
05c0: 74 5c 66 52 2e 20 54 68 69 73 20 65 78 74 65 6e t\fR. This exten
05d0: 64 73 20 69 6e 74 6f 20 61 20 72 65 6c 61 74 69 ds into a relati
05e0: 6f 6e 0a 62 65 74 77 65 65 6e 20 6e 6f 64 65 73 on.between nodes
05f0: 2c 20 69 2e 65 2e 20 69 66 20 74 77 6f 20 6e 6f , i.e. if two no
0600: 64 65 73 20 61 72 65 20 63 6f 6e 6e 65 63 74 65 des are connecte
0610: 64 20 74 68 72 6f 75 67 68 20 61 74 20 6c 65 61 d through at lea
0620: 73 74 20 6f 6e 65 0a 61 72 63 20 74 68 65 79 20 st one.arc they
0630: 61 72 65 20 73 61 69 64 20 74 6f 20 62 65 20 5c are said to be \
0640: 66 49 61 64 6a 61 63 65 6e 74 5c 66 52 20 74 6f fIadjacent\fR to
0650: 6f 2e 0a 0a 45 61 63 68 20 6e 6f 64 65 20 63 61 o...Each node ca
0660: 6e 20 62 65 20 74 68 65 20 73 6f 75 72 63 65 20 n be the source
0670: 61 6e 64 20 74 61 72 67 65 74 20 66 6f 72 20 61 and target for a
0680: 6e 79 20 6e 75 6d 62 65 72 20 6f 66 20 61 72 63 ny number of arc
0690: 73 2e 20 54 68 65 0a 66 6f 72 6d 65 72 20 61 72 s. The.former ar
06a0: 65 20 63 61 6c 6c 65 64 20 74 68 65 20 5c 66 49 e called the \fI
06b0: 6f 75 74 67 6f 69 6e 67 20 61 72 63 73 5c 66 52 outgoing arcs\fR
06c0: 20 6f 66 20 74 68 65 20 6e 6f 64 65 2c 20 74 68 of the node, th
06d0: 65 20 6c 61 74 74 65 72 20 74 68 65 0a 5c 66 49 e latter the.\fI
06e0: 69 6e 63 6f 6d 69 6e 67 20 61 72 63 73 5c 66 52 incoming arcs\fR
06f0: 20 6f 66 20 74 68 65 20 6e 6f 64 65 2e 20 54 68 of the node. Th
0700: 65 20 6e 75 6d 62 65 72 20 6f 66 20 65 64 67 65 e number of edge
0710: 73 20 69 6e 20 65 69 74 68 65 72 20 73 65 74 20 s in either set
0720: 69 73 0a 63 61 6c 6c 65 64 20 74 68 65 20 5c 66 is.called the \f
0730: 49 69 6e 2d 5c 66 52 20 72 65 73 70 2e 20 74 68 Iin-\fR resp. th
0740: 65 20 5c 66 49 6f 75 74 2d 64 65 67 72 65 65 5c e \fIout-degree\
0750: 66 52 20 6f 66 20 74 68 65 20 6e 6f 64 65 2e 0a fR of the node..
0760: 0a 49 6e 20 61 64 64 69 74 69 6f 6e 20 74 6f 20 .In addition to
0770: 6d 61 69 6e 74 61 69 6e 69 6e 67 20 74 68 65 20 maintaining the
0780: 6e 6f 64 65 20 61 6e 64 20 61 72 63 20 72 65 6c node and arc rel
0790: 61 74 69 6f 6e 73 68 69 70 73 2c 20 74 68 69 73 ationships, this
07a0: 20 67 72 61 70 68 0a 69 6d 70 6c 65 6d 65 6e 74 graph.implement
07b0: 61 74 69 6f 6e 20 61 6c 6c 6f 77 73 20 61 6e 79 ation allows any
07c0: 20 6e 75 6d 62 65 72 20 6f 66 20 6b 65 79 65 64 number of keyed
07d0: 20 76 61 6c 75 65 73 20 74 6f 20 62 65 20 61 73 values to be as
07e0: 73 6f 63 69 61 74 65 64 20 77 69 74 68 0a 65 61 sociated with.ea
07f0: 63 68 20 6e 6f 64 65 20 61 6e 64 20 61 72 63 2e ch node and arc.
0800: 0a 2e 50 50 0a 54 68 65 20 66 6f 6c 6c 6f 77 69 ..PP.The followi
0810: 6e 67 20 63 6f 6d 6d 61 6e 64 73 20 61 72 65 20 ng commands are
0820: 70 6f 73 73 69 62 6c 65 20 66 6f 72 20 67 72 61 possible for gra
0830: 70 68 20 6f 62 6a 65 63 74 73 3a 0a 2e 54 50 0a ph objects:..TP.
0840: 5c 66 49 67 72 61 70 68 4e 61 6d 65 20 5c 66 42 \fIgraphName \fB
0850: 64 65 73 74 72 6f 79 5c 66 52 0a 44 65 73 74 72 destroy\fR.Destr
0860: 6f 79 20 74 68 65 20 67 72 61 70 68 2c 20 69 6e oy the graph, in
0870: 63 6c 75 64 69 6e 67 20 69 74 73 20 73 74 6f 72 cluding its stor
0880: 61 67 65 20 73 70 61 63 65 20 61 6e 64 20 61 73 age space and as
0890: 73 6f 63 69 61 74 65 64 20 63 6f 6d 6d 61 6e 64 sociated command
08a0: 2e 0a 2e 54 50 0a 5c 66 49 67 72 61 70 68 4e 61 ...TP.\fIgraphNa
08b0: 6d 65 5c 66 52 20 5c 66 42 61 72 63 20 64 65 6c me\fR \fBarc del
08c0: 65 74 65 5c 66 52 20 5c 66 49 61 72 63 5c 66 52 ete\fR \fIarc\fR
08d0: 20 3f 5c 66 49 61 72 63 5c 66 52 20 2e 2e 2e 3f ?\fIarc\fR ...?
08e0: 0a 52 65 6d 6f 76 65 20 74 68 65 20 73 70 65 63 .Remove the spec
08f0: 69 66 69 65 64 20 61 72 63 73 20 66 72 6f 6d 20 ified arcs from
0900: 74 68 65 20 67 72 61 70 68 2e 0a 2e 54 50 0a 5c the graph...TP.\
0910: 66 49 67 72 61 70 68 4e 61 6d 65 5c 66 52 20 5c fIgraphName\fR \
0920: 66 42 61 72 63 20 65 78 69 73 74 73 5c 66 52 20 fBarc exists\fR
0930: 5c 66 49 61 72 63 5c 66 52 0a 52 65 74 75 72 6e \fIarc\fR.Return
0940: 20 74 72 75 65 20 69 66 20 74 68 65 20 73 70 65 true if the spe
0950: 63 69 66 69 65 64 20 5c 66 49 61 72 63 5c 66 52 cified \fIarc\fR
0960: 20 65 78 69 73 74 73 20 69 6e 20 74 68 65 20 67 exists in the g
0970: 72 61 70 68 2e 0a 2e 54 50 0a 5c 66 49 67 72 61 raph...TP.\fIgra
0980: 70 68 4e 61 6d 65 5c 66 52 20 5c 66 42 61 72 63 phName\fR \fBarc
0990: 20 67 65 74 5c 66 52 20 5c 66 49 61 72 63 5c 66 get\fR \fIarc\f
09a0: 52 20 3f 5c 66 49 2d 6b 65 79 20 6b 65 79 5c 66 R ?\fI-key key\f
09b0: 52 3f 0a 52 65 74 75 72 6e 20 74 68 65 20 76 61 R?.Return the va
09c0: 6c 75 65 20 61 73 73 6f 63 69 61 74 65 64 20 77 lue associated w
09d0: 69 74 68 20 74 68 65 20 6b 65 79 20 5c 66 49 6b ith the key \fIk
09e0: 65 79 5c 66 52 20 66 6f 72 20 74 68 65 0a 5c 66 ey\fR for the.\f
09f0: 49 61 72 63 5c 66 52 2e 20 20 49 66 20 6e 6f 20 Iarc\fR. If no
0a00: 6b 65 79 20 69 73 20 73 70 65 63 69 66 69 65 64 key is specified
0a10: 2c 20 74 68 65 20 6b 65 79 20 5c 66 42 64 61 74 , the key \fBdat
0a20: 61 5c 66 52 20 69 73 20 61 73 73 75 6d 65 64 2e a\fR is assumed.
0a30: 0a 2e 54 50 0a 5c 66 49 67 72 61 70 68 4e 61 6d ..TP.\fIgraphNam
0a40: 65 20 5c 66 42 61 72 63 20 69 6e 73 65 72 74 5c e \fBarc insert\
0a50: 66 52 20 5c 66 49 73 74 61 72 74 5c 66 52 20 5c fR \fIstart\fR \
0a60: 66 49 65 6e 64 5c 66 52 20 3f 5c 66 49 63 68 69 fIend\fR ?\fIchi
0a70: 6c 64 5c 66 52 3f 0a 49 6e 73 65 72 74 20 61 6e ld\fR?.Insert an
0a80: 20 61 72 63 20 6e 61 6d 65 64 20 5c 66 49 63 68 arc named \fIch
0a90: 69 6c 64 5c 66 52 20 69 6e 74 6f 20 74 68 65 20 ild\fR into the
0aa0: 67 72 61 70 68 20 62 65 67 69 6e 6e 69 6e 67 20 graph beginning
0ab0: 61 74 20 74 68 65 20 6e 6f 64 65 0a 5c 66 49 73 at the node.\fIs
0ac0: 74 61 72 74 5c 66 52 20 61 6e 64 20 65 6e 64 69 tart\fR and endi
0ad0: 6e 67 20 61 74 20 74 68 65 20 6e 6f 64 65 20 5c ng at the node \
0ae0: 66 49 65 6e 64 5c 66 52 2e 20 49 66 20 74 68 65 fIend\fR. If the
0af0: 20 6e 61 6d 65 20 6f 66 20 74 68 65 20 6e 65 77 name of the new
0b00: 0a 61 72 63 20 69 73 20 6e 6f 74 20 73 70 65 63 .arc is not spec
0b10: 69 66 69 65 64 20 74 68 65 20 73 79 73 74 65 6d ified the system
0b20: 20 77 69 6c 6c 20 67 65 6e 65 72 61 74 65 20 61 will generate a
0b30: 20 75 6e 69 71 75 65 20 6e 61 6d 65 20 6f 66 20 unique name of
0b40: 74 68 65 0a 66 6f 72 6d 20 5c 66 42 61 72 63 5c the.form \fBarc\
0b50: 66 52 5c 66 49 78 5c 66 52 2e 0a 2e 54 50 0a 5c fR\fIx\fR...TP.\
0b60: 66 49 67 72 61 70 68 4e 61 6d 65 5c 66 52 20 5c fIgraphName\fR \
0b70: 66 42 61 72 63 20 73 65 74 5c 66 52 20 5c 66 49 fBarc set\fR \fI
0b80: 61 72 63 5c 66 52 20 3f 5c 66 49 2d 6b 65 79 20 arc\fR ?\fI-key
0b90: 6b 65 79 5c 66 52 3f 20 3f 5c 66 49 76 61 6c 75 key\fR? ?\fIvalu
0ba0: 65 5c 66 52 3f 0a 53 65 74 20 6f 72 20 67 65 74 e\fR?.Set or get
0bb0: 20 6f 6e 65 20 6f 66 20 74 68 65 20 6b 65 79 65 one of the keye
0bc0: 64 20 76 61 6c 75 65 73 20 61 73 73 6f 63 69 61 d values associa
0bd0: 74 65 64 20 77 69 74 68 20 61 6e 20 61 72 63 2e ted with an arc.
0be0: 20 20 49 66 20 6e 6f 20 6b 65 79 0a 69 73 20 73 If no key.is s
0bf0: 70 65 63 69 66 69 65 64 2c 20 74 68 65 20 6b 65 pecified, the ke
0c00: 79 20 5c 66 42 64 61 74 61 5c 66 52 20 69 73 20 y \fBdata\fR is
0c10: 61 73 73 75 6d 65 64 2e 20 20 45 61 63 68 20 61 assumed. Each a
0c20: 72 63 20 74 68 61 74 20 69 73 20 61 64 64 65 64 rc that is added
0c30: 0a 74 6f 20 61 20 67 72 61 70 68 20 68 61 73 20 .to a graph has
0c40: 74 68 65 20 76 61 6c 75 65 20 22 22 20 61 73 73 the value "" ass
0c50: 69 67 6e 65 64 20 74 6f 20 74 68 65 20 6b 65 79 igned to the key
0c60: 20 5c 66 42 64 61 74 61 5c 66 52 0a 61 75 74 6f \fBdata\fR.auto
0c70: 6d 61 74 69 63 61 6c 6c 79 2e 20 20 41 6e 20 61 matically. An a
0c80: 72 63 20 6d 61 79 20 68 61 76 65 20 61 6e 79 20 rc may have any
0c90: 6e 75 6d 62 65 72 20 6f 66 20 6b 65 79 65 64 20 number of keyed
0ca0: 76 61 6c 75 65 73 20 61 73 73 6f 63 69 61 74 65 values associate
0cb0: 64 0a 77 69 74 68 20 69 74 2e 20 20 49 66 20 5c d.with it. If \
0cc0: 66 49 76 61 6c 75 65 5c 66 52 20 69 73 20 6e 6f fIvalue\fR is no
0cd0: 74 20 73 70 65 63 69 66 69 65 64 2c 20 74 68 69 t specified, thi
0ce0: 73 20 63 6f 6d 6d 61 6e 64 20 72 65 74 75 72 6e s command return
0cf0: 73 20 74 68 65 0a 63 75 72 72 65 6e 74 20 76 61 s the.current va
0d00: 6c 75 65 20 61 73 73 69 67 6e 65 64 20 74 6f 20 lue assigned to
0d10: 74 68 65 20 6b 65 79 3b 20 69 66 20 5c 66 49 76 the key; if \fIv
0d20: 61 6c 75 65 5c 66 52 20 69 73 20 73 70 65 63 69 alue\fR is speci
0d30: 66 69 65 64 2c 20 74 68 69 73 0a 63 6f 6d 6d 61 fied, this.comma
0d40: 6e 64 20 61 73 73 69 67 6e 73 20 74 68 61 74 20 nd assigns that
0d50: 76 61 6c 75 65 20 74 6f 20 74 68 65 20 6b 65 79 value to the key
0d60: 2e 0a 2e 54 50 0a 5c 66 49 67 72 61 70 68 4e 61 ...TP.\fIgraphNa
0d70: 6d 65 5c 66 52 20 5c 66 42 61 72 63 20 73 6f 75 me\fR \fBarc sou
0d80: 72 63 65 5c 66 52 20 5c 66 49 61 72 63 5c 66 52 rce\fR \fIarc\fR
0d90: 0a 52 65 74 75 72 6e 20 74 68 65 20 6e 6f 64 65 .Return the node
0da0: 20 74 68 65 20 67 69 76 65 6e 20 5c 66 49 61 72 the given \fIar
0db0: 63 5c 66 52 20 62 65 67 69 6e 73 20 61 74 2e 0a c\fR begins at..
0dc0: 2e 54 50 0a 5c 66 49 67 72 61 70 68 4e 61 6d 65 .TP.\fIgraphName
0dd0: 5c 66 52 20 5c 66 42 61 72 63 20 74 61 72 67 65 \fR \fBarc targe
0de0: 74 5c 66 52 20 5c 66 49 61 72 63 5c 66 52 0a 52 t\fR \fIarc\fR.R
0df0: 65 74 75 72 6e 20 74 68 65 20 6e 6f 64 65 20 74 eturn the node t
0e00: 68 65 20 67 69 76 65 6e 20 5c 66 49 61 72 63 5c he given \fIarc\
0e10: 66 52 20 65 6e 64 73 20 61 74 2e 0a 2e 54 50 0a fR ends at...TP.
0e20: 5c 66 49 67 72 61 70 68 4e 61 6d 65 5c 66 52 20 \fIgraphName\fR
0e30: 5c 66 42 61 72 63 20 75 6e 73 65 74 5c 66 52 20 \fBarc unset\fR
0e40: 5c 66 49 61 72 63 5c 66 52 20 3f 5c 66 49 2d 6b \fIarc\fR ?\fI-k
0e50: 65 79 20 6b 65 79 5c 66 52 3f 0a 52 65 6d 6f 76 ey key\fR?.Remov
0e60: 65 20 61 20 6b 65 79 65 64 20 76 61 6c 75 65 20 e a keyed value
0e70: 66 72 6f 6d 20 74 68 65 20 61 72 63 20 5c 66 49 from the arc \fI
0e80: 61 72 63 5c 66 52 2e 20 20 49 66 20 6e 6f 20 6b arc\fR. If no k
0e90: 65 79 20 69 73 0a 73 70 65 63 69 66 69 65 64 2c ey is.specified,
0ea0: 20 74 68 65 20 6b 65 79 20 5c 66 42 64 61 74 61 the key \fBdata
0eb0: 5c 66 52 20 69 73 20 61 73 73 75 6d 65 64 2e 0a \fR is assumed..
0ec0: 2e 54 50 0a 5c 66 49 67 72 61 70 68 4e 61 6d 65 .TP.\fIgraphName
0ed0: 5c 66 52 20 5c 66 42 61 72 63 73 5c 66 52 20 3f \fR \fBarcs\fR ?
0ee0: 2d 6b 65 79 20 5c 66 49 6b 65 79 5c 66 52 3f 20 -key \fIkey\fR?
0ef0: 3f 2d 76 61 6c 75 65 20 5c 66 49 76 61 6c 75 65 ?-value \fIvalue
0f00: 5c 66 52 3f 20 3f 2d 69 6e 7c 2d 6f 75 74 7c 2d \fR? ?-in|-out|-
0f10: 61 64 6a 7c 2d 69 6e 6e 65 72 7c 2d 65 6d 62 65 adj|-inner|-embe
0f20: 64 64 69 6e 67 20 5c 66 49 6e 6f 64 65 6c 69 73 dding \fInodelis
0f30: 74 5c 66 52 3f 0a 52 65 74 75 72 6e 20 61 20 6c t\fR?.Return a l
0f40: 69 73 74 20 6f 66 20 61 72 63 73 20 69 6e 20 74 ist of arcs in t
0f50: 68 65 20 67 72 61 70 68 2e 20 49 66 20 6e 6f 20 he graph. If no
0f60: 72 65 73 74 72 69 63 74 69 6f 6e 20 69 73 20 73 restriction is s
0f70: 70 65 63 69 66 69 65 64 20 61 0a 6c 69 73 74 20 pecified a.list
0f80: 63 6f 6e 74 61 69 6e 69 6e 67 20 61 6c 6c 20 61 containing all a
0f90: 72 63 73 20 69 73 20 72 65 74 75 72 6e 65 64 2e rcs is returned.
0fa0: 20 52 65 73 74 72 69 63 74 69 6f 6e 73 20 63 61 Restrictions ca
0fb0: 6e 20 6c 69 6d 69 74 20 74 68 65 20 6c 69 73 74 n limit the list
0fc0: 0a 6f 66 20 72 65 74 75 72 6e 65 64 20 61 72 63 .of returned arc
0fd0: 73 20 62 61 73 65 64 20 6f 6e 20 74 68 65 20 6e s based on the n
0fe0: 6f 64 65 73 20 74 68 61 74 20 61 72 65 20 63 6f odes that are co
0ff0: 6e 6e 65 63 74 65 64 20 62 79 20 74 68 65 20 61 nnected by the a
1000: 72 63 2c 20 6f 6e 0a 74 68 65 20 6b 65 79 65 64 rc, on.the keyed
1010: 20 76 61 6c 75 65 73 20 61 73 73 6f 63 69 61 74 values associat
1020: 65 64 20 77 69 74 68 20 74 68 65 20 61 72 63 2c ed with the arc,
1030: 20 6f 72 20 62 6f 74 68 2e 20 54 68 65 20 72 65 or both. The re
1040: 73 74 72 69 63 74 69 6f 6e 73 0a 74 68 61 74 20 strictions.that
1050: 69 6e 76 6f 6c 76 65 20 63 6f 6e 6e 65 63 74 65 involve connecte
1060: 64 20 6e 6f 64 65 73 20 68 61 76 65 20 61 20 6c d nodes have a l
1070: 69 73 74 20 6f 66 20 6e 6f 64 65 73 20 61 73 20 ist of nodes as
1080: 61 72 67 75 6d 65 6e 74 2c 0a 73 70 65 63 69 66 argument,.specif
1090: 69 65 64 20 61 66 74 65 72 20 74 68 65 20 6e 61 ied after the na
10a0: 6d 65 20 6f 66 20 74 68 65 20 72 65 73 74 72 69 me of the restri
10b0: 63 74 69 6f 6e 20 69 74 73 65 6c 66 2e 0a 2e 52 ction itself...R
10c0: 53 0a 2e 54 50 0a 5c 66 42 2d 69 6e 5c 66 52 0a S..TP.\fB-in\fR.
10d0: 52 65 74 75 72 6e 20 61 20 6c 69 73 74 20 6f 66 Return a list of
10e0: 20 61 6c 6c 20 61 72 63 73 20 77 68 6f 73 65 20 all arcs whose
10f0: 74 61 72 67 65 74 20 69 73 20 6f 6e 65 20 6f 66 target is one of
1100: 20 74 68 65 20 6e 6f 64 65 73 20 69 6e 20 74 68 the nodes in th
1110: 65 0a 5c 66 49 6e 6f 64 65 6c 69 73 74 5c 66 52 e.\fInodelist\fR
1120: 2e 0a 2e 54 50 0a 5c 66 42 2d 6f 75 74 5c 66 52 ...TP.\fB-out\fR
1130: 0a 52 65 74 75 72 6e 20 61 20 6c 69 73 74 20 6f .Return a list o
1140: 66 20 61 6c 6c 20 61 72 63 73 20 77 68 6f 73 65 f all arcs whose
1150: 20 73 6f 75 72 63 65 20 69 73 20 6f 6e 65 20 6f source is one o
1160: 66 20 74 68 65 20 6e 6f 64 65 73 20 69 6e 20 74 f the nodes in t
1170: 68 65 0a 5c 66 49 6e 6f 64 65 6c 69 73 74 5c 66 he.\fInodelist\f
1180: 52 2e 0a 2e 54 50 0a 5c 66 42 2d 61 64 6a 5c 66 R...TP.\fB-adj\f
1190: 52 0a 52 65 74 75 72 6e 20 61 20 6c 69 73 74 20 R.Return a list
11a0: 6f 66 20 61 6c 6c 20 61 72 63 73 20 61 64 6a 61 of all arcs adja
11b0: 63 65 6e 74 20 74 6f 20 61 74 20 6c 65 61 73 74 cent to at least
11c0: 20 6f 6e 65 20 6f 66 20 74 68 65 20 6e 6f 64 65 one of the node
11d0: 73 20 69 6e 0a 74 68 65 20 5c 66 49 6e 6f 64 65 s in.the \fInode
11e0: 6c 69 73 74 5c 66 52 2e 20 54 68 69 73 20 69 73 list\fR. This is
11f0: 20 74 68 65 20 75 6e 69 6f 6e 20 6f 66 20 74 68 the union of th
1200: 65 20 6e 6f 64 65 73 20 72 65 74 75 72 6e 65 64 e nodes returned
1210: 20 62 79 0a 5c 66 42 2d 69 6e 5c 66 52 20 61 6e by.\fB-in\fR an
1220: 64 20 5c 66 42 2d 6f 75 74 5c 66 52 2e 0a 2e 54 d \fB-out\fR...T
1230: 50 0a 5c 66 42 2d 69 6e 6e 65 72 5c 66 52 0a 52 P.\fB-inner\fR.R
1240: 65 74 75 72 6e 20 61 20 6c 69 73 74 20 6f 66 20 eturn a list of
1250: 61 6c 6c 20 61 72 63 73 20 61 64 6a 61 63 65 6e all arcs adjacen
1260: 74 20 74 6f 20 74 77 6f 20 6f 66 20 74 68 65 20 t to two of the
1270: 6e 6f 64 65 73 20 69 6e 20 74 68 65 0a 5c 66 49 nodes in the.\fI
1280: 6e 6f 64 65 6c 69 73 74 5c 66 52 2e 20 54 68 69 nodelist\fR. Thi
1290: 73 20 69 73 20 74 68 65 20 73 65 74 20 6f 66 20 s is the set of
12a0: 61 72 63 73 20 69 6e 20 74 68 65 20 73 75 62 67 arcs in the subg
12b0: 72 61 70 68 20 73 70 61 77 6e 65 64 20 62 79 0a raph spawned by.
12c0: 74 68 65 20 73 70 65 63 69 66 69 65 64 20 6e 6f the specified no
12d0: 64 65 73 2e 0a 2e 54 50 0a 5c 66 42 2d 65 6d 62 des...TP.\fB-emb
12e0: 65 64 64 69 6e 67 5c 66 52 0a 52 65 74 75 72 6e edding\fR.Return
12f0: 20 61 20 6c 69 73 74 20 6f 66 20 61 6c 6c 20 61 a list of all a
1300: 72 63 73 20 61 64 6a 61 63 65 6e 74 20 74 6f 20 rcs adjacent to
1310: 65 78 61 63 74 6c 79 20 6f 6e 65 20 6f 66 20 74 exactly one of t
1320: 68 65 20 6e 6f 64 65 73 20 69 6e 20 74 68 65 0a he nodes in the.
1330: 5c 66 49 6e 6f 64 65 6c 69 73 74 5c 66 52 2e 20 \fInodelist\fR.
1340: 54 68 69 73 20 69 73 20 74 68 65 20 73 65 74 20 This is the set
1350: 6f 66 20 61 72 63 73 20 63 6f 6e 6e 65 63 74 69 of arcs connecti
1360: 6e 67 20 74 68 65 20 73 75 62 67 72 61 70 68 0a ng the subgraph.
1370: 73 70 61 77 6e 65 64 20 62 79 20 74 68 65 20 73 spawned by the s
1380: 70 65 63 69 66 69 65 64 20 6e 6f 64 65 73 20 74 pecified nodes t
1390: 6f 20 74 68 65 20 72 65 73 74 20 6f 66 20 74 68 o the rest of th
13a0: 65 20 67 72 61 70 68 2e 0a 2e 54 50 0a 5c 66 42 e graph...TP.\fB
13b0: 2d 6b 65 79 5c 66 52 20 5c 66 49 6b 65 79 5c 66 -key\fR \fIkey\f
13c0: 52 0a 4c 69 6d 69 74 20 74 68 65 20 6c 69 73 74 R.Limit the list
13d0: 20 6f 66 20 61 72 63 73 20 74 68 61 74 20 61 72 of arcs that ar
13e0: 65 20 72 65 74 75 72 6e 65 64 20 74 6f 20 74 68 e returned to th
13f0: 6f 73 65 20 61 72 63 73 20 74 68 61 74 20 68 61 ose arcs that ha
1400: 76 65 20 61 6e 0a 61 73 73 6f 63 69 61 74 65 64 ve an.associated
1410: 20 6b 65 79 20 5c 66 49 6b 65 79 5c 66 52 2e 0a key \fIkey\fR..
1420: 2e 54 50 0a 5c 66 42 2d 76 61 6c 75 65 5c 66 52 .TP.\fB-value\fR
1430: 20 5c 66 49 76 61 6c 75 65 5c 66 52 0a 54 68 69 \fIvalue\fR.Thi
1440: 73 20 72 65 73 74 72 69 63 74 69 6f 6e 20 63 61 s restriction ca
1450: 6e 20 6f 6e 6c 79 20 62 65 20 75 73 65 64 20 69 n only be used i
1460: 6e 20 63 6f 6d 62 69 6e 61 74 69 6f 6e 20 77 69 n combination wi
1470: 74 68 20 5c 66 42 2d 6b 65 79 5c 66 52 2e 20 49 th \fB-key\fR. I
1480: 74 0a 6c 69 6d 69 74 73 20 74 68 65 20 6c 69 73 t.limits the lis
1490: 74 20 6f 66 20 61 72 63 73 20 74 68 61 74 20 61 t of arcs that a
14a0: 72 65 20 72 65 74 75 72 6e 65 64 20 74 6f 20 74 re returned to t
14b0: 68 6f 73 65 20 61 72 63 73 20 77 68 6f 73 65 0a hose arcs whose.
14c0: 61 73 73 6f 63 69 61 74 65 64 20 6b 65 79 20 5c associated key \
14d0: 66 49 6b 65 79 5c 66 52 20 68 61 73 20 74 68 65 fIkey\fR has the
14e0: 20 76 61 6c 75 65 20 5c 66 49 76 61 6c 75 65 5c value \fIvalue\
14f0: 66 52 2e 0a 2e 52 45 0a 2e 54 50 0a 5c 66 49 67 fR...RE..TP.\fIg
1500: 72 61 70 68 4e 61 6d 65 5c 66 52 20 5c 66 42 6e raphName\fR \fBn
1510: 6f 64 65 20 64 65 67 72 65 65 5c 66 52 20 3f 2d ode degree\fR ?-
1520: 69 6e 7c 2d 6f 75 74 3f 20 5c 66 49 6e 6f 64 65 in|-out? \fInode
1530: 5c 66 52 0a 52 65 74 75 72 6e 20 74 68 65 20 6e \fR.Return the n
1540: 75 6d 62 65 72 20 6f 66 20 61 72 63 73 20 61 64 umber of arcs ad
1550: 6a 61 63 65 6e 74 20 74 6f 20 74 68 65 20 73 70 jacent to the sp
1560: 65 63 69 66 69 65 64 20 5c 66 49 6e 6f 64 65 5c ecified \fInode\
1570: 66 52 2e 20 49 66 0a 6f 6e 65 20 6f 66 20 74 68 fR. If.one of th
1580: 65 20 72 65 73 74 72 69 63 74 69 6f 6e 73 20 5c e restrictions \
1590: 66 42 2d 69 6e 5c 66 52 20 6f 72 20 5c 66 42 2d fB-in\fR or \fB-
15a0: 6f 75 74 5c 66 52 20 69 73 20 67 69 76 65 6e 20 out\fR is given
15b0: 6f 6e 6c 79 20 74 68 65 0a 69 6e 63 6f 6d 69 6e only the.incomin
15c0: 67 20 72 65 73 70 2e 20 6f 75 74 67 6f 69 6e 67 g resp. outgoing
15d0: 20 61 72 63 73 20 61 72 65 20 63 6f 75 6e 74 65 arcs are counte
15e0: 64 2e 0a 2e 54 50 0a 5c 66 49 67 72 61 70 68 4e d...TP.\fIgraphN
15f0: 61 6d 65 5c 66 52 20 5c 66 42 6e 6f 64 65 20 64 ame\fR \fBnode d
1600: 65 6c 65 74 65 5c 66 52 20 5c 66 49 6e 6f 64 65 elete\fR \fInode
1610: 5c 66 52 20 3f 5c 66 49 6e 6f 64 65 5c 66 52 20 \fR ?\fInode\fR
1620: 2e 2e 2e 3f 0a 52 65 6d 6f 76 65 20 74 68 65 20 ...?.Remove the
1630: 73 70 65 63 69 66 69 65 64 20 6e 6f 64 65 73 20 specified nodes
1640: 66 72 6f 6d 20 74 68 65 20 67 72 61 70 68 2e 20 from the graph.
1650: 20 41 6c 6c 20 6f 66 20 74 68 65 20 6e 6f 64 65 All of the node
1660: 73 27 20 61 72 63 73 0a 77 69 6c 6c 20 62 65 20 s' arcs.will be
1670: 72 65 6d 6f 76 65 64 20 61 73 20 77 65 6c 6c 20 removed as well
1680: 74 6f 20 70 72 65 76 65 6e 74 20 75 6e 63 6f 6e to prevent uncon
1690: 6e 65 63 74 65 64 20 61 72 63 73 2e 0a 2e 54 50 nected arcs...TP
16a0: 0a 5c 66 49 67 72 61 70 68 4e 61 6d 65 5c 66 52 .\fIgraphName\fR
16b0: 20 5c 66 42 6e 6f 64 65 20 65 78 69 73 74 73 5c \fBnode exists\
16c0: 66 52 20 5c 66 49 6e 6f 64 65 5c 66 52 0a 52 65 fR \fInode\fR.Re
16d0: 74 75 72 6e 20 74 72 75 65 20 69 66 20 74 68 65 turn true if the
16e0: 20 73 70 65 63 69 66 69 65 64 20 5c 66 49 6e 6f specified \fIno
16f0: 64 65 5c 66 52 20 65 78 69 73 74 73 20 69 6e 20 de\fR exists in
1700: 74 68 65 20 67 72 61 70 68 2e 0a 2e 54 50 0a 5c the graph...TP.\
1710: 66 49 67 72 61 70 68 4e 61 6d 65 5c 66 52 20 5c fIgraphName\fR \
1720: 66 42 6e 6f 64 65 20 67 65 74 5c 66 52 20 5c 66 fBnode get\fR \f
1730: 49 6e 6f 64 65 5c 66 52 20 3f 5c 66 49 2d 6b 65 Inode\fR ?\fI-ke
1740: 79 20 6b 65 79 5c 66 52 3f 0a 52 65 74 75 72 6e y key\fR?.Return
1750: 20 74 68 65 20 76 61 6c 75 65 20 61 73 73 6f 63 the value assoc
1760: 69 61 74 65 64 20 77 69 74 68 20 74 68 65 20 6b iated with the k
1770: 65 79 20 5c 66 49 6b 65 79 5c 66 52 20 66 6f 72 ey \fIkey\fR for
1780: 20 74 68 65 0a 5c 66 49 6e 6f 64 65 5c 66 52 2e the.\fInode\fR.
1790: 20 20 49 66 20 6e 6f 20 6b 65 79 20 69 73 20 73 If no key is s
17a0: 70 65 63 69 66 69 65 64 2c 20 74 68 65 20 6b 65 pecified, the ke
17b0: 79 20 5c 66 42 64 61 74 61 5c 66 52 20 69 73 20 y \fBdata\fR is
17c0: 61 73 73 75 6d 65 64 2e 0a 2e 54 50 0a 5c 66 49 assumed...TP.\fI
17d0: 67 72 61 70 68 4e 61 6d 65 20 5c 66 42 6e 6f 64 graphName \fBnod
17e0: 65 20 69 6e 73 65 72 74 5c 66 52 20 3f 5c 66 49 e insert\fR ?\fI
17f0: 63 68 69 6c 64 5c 66 52 3f 0a 49 6e 73 65 72 74 child\fR?.Insert
1800: 20 61 20 6e 6f 64 65 20 6e 61 6d 65 64 20 5c 66 a node named \f
1810: 49 63 68 69 6c 64 5c 66 52 20 69 6e 74 6f 20 74 Ichild\fR into t
1820: 68 65 20 67 72 61 70 68 2e 20 54 68 65 20 6e 6f he graph. The no
1830: 64 65 73 20 68 61 73 20 6e 6f 20 61 72 63 73 0a des has no arcs.
1840: 63 6f 6e 6e 65 63 74 65 64 20 74 6f 20 69 74 2e connected to it.
1850: 20 49 66 20 74 68 65 20 6e 61 6d 65 20 6f 66 20 If the name of
1860: 74 68 65 20 6e 65 77 20 63 68 69 6c 64 20 69 73 the new child is
1870: 20 6e 6f 74 20 73 70 65 63 69 66 69 65 64 20 74 not specified t
1880: 68 65 0a 73 79 73 74 65 6d 20 77 69 6c 6c 20 67 he.system will g
1890: 65 6e 65 72 61 74 65 20 61 20 75 6e 69 71 75 65 enerate a unique
18a0: 20 6e 61 6d 65 20 6f 66 20 74 68 65 20 66 6f 72 name of the for
18b0: 6d 20 5c 66 42 6e 6f 64 65 5c 66 52 5c 66 49 78 m \fBnode\fR\fIx
18c0: 5c 66 52 2e 0a 2e 54 50 0a 5c 66 49 67 72 61 70 \fR...TP.\fIgrap
18d0: 68 4e 61 6d 65 5c 66 52 20 5c 66 42 6e 6f 64 65 hName\fR \fBnode
18e0: 20 6f 70 70 6f 73 69 74 65 5c 66 52 20 5c 66 49 opposite\fR \fI
18f0: 6e 6f 64 65 5c 66 52 20 5c 66 49 61 72 63 5c 66 node\fR \fIarc\f
1900: 52 0a 52 65 74 75 72 6e 20 74 68 65 20 6e 6f 64 R.Return the nod
1910: 65 20 61 74 20 74 68 65 20 6f 74 68 65 72 20 65 e at the other e
1920: 6e 64 20 6f 66 20 74 68 65 20 73 70 65 63 69 66 nd of the specif
1930: 69 65 64 20 5c 66 49 61 72 63 5c 66 52 2c 20 77 ied \fIarc\fR, w
1940: 68 69 63 68 0a 68 61 73 20 74 6f 20 62 65 20 61 hich.has to be a
1950: 64 6a 61 63 65 6e 74 20 74 6f 20 74 68 65 20 67 djacent to the g
1960: 69 76 65 6e 20 5c 66 49 6e 6f 64 65 5c 66 52 2e iven \fInode\fR.
1970: 0a 2e 54 50 0a 5c 66 49 67 72 61 70 68 4e 61 6d ..TP.\fIgraphNam
1980: 65 5c 66 52 20 5c 66 42 6e 6f 64 65 20 73 65 74 e\fR \fBnode set
1990: 5c 66 52 20 5c 66 49 6e 6f 64 65 5c 66 52 20 3f \fR \fInode\fR ?
19a0: 5c 66 49 2d 6b 65 79 20 6b 65 79 5c 66 52 3f 20 \fI-key key\fR?
19b0: 3f 5c 66 49 76 61 6c 75 65 5c 66 52 3f 0a 53 65 ?\fIvalue\fR?.Se
19c0: 74 20 6f 72 20 67 65 74 20 6f 6e 65 20 6f 66 20 t or get one of
19d0: 74 68 65 20 6b 65 79 65 64 20 76 61 6c 75 65 73 the keyed values
19e0: 20 61 73 73 6f 63 69 61 74 65 64 20 77 69 74 68 associated with
19f0: 20 61 20 6e 6f 64 65 2e 20 20 49 66 20 6e 6f 20 a node. If no
1a00: 6b 65 79 0a 69 73 20 73 70 65 63 69 66 69 65 64 key.is specified
1a10: 2c 20 74 68 65 20 6b 65 79 20 5c 66 42 64 61 74 , the key \fBdat
1a20: 61 5c 66 52 20 69 73 20 61 73 73 75 6d 65 64 2e a\fR is assumed.
1a30: 20 20 45 61 63 68 20 6e 6f 64 65 20 74 68 61 74 Each node that
1a40: 20 69 73 20 61 64 64 65 64 0a 74 6f 20 61 20 67 is added.to a g
1a50: 72 61 70 68 20 68 61 73 20 74 68 65 20 76 61 6c raph has the val
1a60: 75 65 20 22 22 20 61 73 73 69 67 6e 65 64 20 74 ue "" assigned t
1a70: 6f 20 74 68 65 20 6b 65 79 20 5c 66 42 64 61 74 o the key \fBdat
1a80: 61 5c 66 52 0a 61 75 74 6f 6d 61 74 69 63 61 6c a\fR.automatical
1a90: 6c 79 2e 20 20 41 20 6e 6f 64 65 20 6d 61 79 20 ly. A node may
1aa0: 68 61 76 65 20 61 6e 79 20 6e 75 6d 62 65 72 20 have any number
1ab0: 6f 66 20 6b 65 79 65 64 20 76 61 6c 75 65 73 20 of keyed values
1ac0: 61 73 73 6f 63 69 61 74 65 64 0a 77 69 74 68 20 associated.with
1ad0: 69 74 2e 20 20 49 66 20 5c 66 49 76 61 6c 75 65 it. If \fIvalue
1ae0: 5c 66 52 20 69 73 20 6e 6f 74 20 73 70 65 63 69 \fR is not speci
1af0: 66 69 65 64 2c 20 74 68 69 73 20 63 6f 6d 6d 61 fied, this comma
1b00: 6e 64 20 72 65 74 75 72 6e 73 20 74 68 65 0a 63 nd returns the.c
1b10: 75 72 72 65 6e 74 20 76 61 6c 75 65 20 61 73 73 urrent value ass
1b20: 69 67 6e 65 64 20 74 6f 20 74 68 65 20 6b 65 79 igned to the key
1b30: 3b 20 69 66 20 5c 66 49 76 61 6c 75 65 5c 66 52 ; if \fIvalue\fR
1b40: 20 69 73 20 73 70 65 63 69 66 69 65 64 2c 20 74 is specified, t
1b50: 68 69 73 0a 63 6f 6d 6d 61 6e 64 20 61 73 73 69 his.command assi
1b60: 67 6e 73 20 74 68 61 74 20 76 61 6c 75 65 20 74 gns that value t
1b70: 6f 20 74 68 65 20 6b 65 79 2e 0a 2e 54 50 0a 5c o the key...TP.\
1b80: 66 49 67 72 61 70 68 4e 61 6d 65 5c 66 52 20 5c fIgraphName\fR \
1b90: 66 42 6e 6f 64 65 20 75 6e 73 65 74 5c 66 52 20 fBnode unset\fR
1ba0: 5c 66 49 6e 6f 64 65 5c 66 52 20 3f 5c 66 49 2d \fInode\fR ?\fI-
1bb0: 6b 65 79 20 6b 65 79 5c 66 52 3f 0a 52 65 6d 6f key key\fR?.Remo
1bc0: 76 65 20 61 20 6b 65 79 65 64 20 76 61 6c 75 65 ve a keyed value
1bd0: 20 66 72 6f 6d 20 74 68 65 20 6e 6f 64 65 20 5c from the node \
1be0: 66 49 6e 6f 64 65 5c 66 52 2e 20 20 49 66 20 6e fInode\fR. If n
1bf0: 6f 20 6b 65 79 20 69 73 0a 73 70 65 63 69 66 69 o key is.specifi
1c00: 65 64 2c 20 74 68 65 20 6b 65 79 20 5c 66 42 64 ed, the key \fBd
1c10: 61 74 61 5c 66 52 20 69 73 20 61 73 73 75 6d 65 ata\fR is assume
1c20: 64 2e 0a 2e 54 50 0a 5c 66 49 67 72 61 70 68 4e d...TP.\fIgraphN
1c30: 61 6d 65 5c 66 52 20 5c 66 42 6e 6f 64 65 73 5c ame\fR \fBnodes\
1c40: 66 52 20 3f 2d 6b 65 79 20 5c 66 49 6b 65 79 5c fR ?-key \fIkey\
1c50: 66 52 3f 20 3f 2d 76 61 6c 75 65 20 5c 66 49 76 fR? ?-value \fIv
1c60: 61 6c 75 65 5c 66 52 3f 20 3f 2d 69 6e 7c 2d 6f alue\fR? ?-in|-o
1c70: 75 74 7c 2d 61 64 6a 7c 2d 69 6e 6e 65 72 7c 2d ut|-adj|-inner|-
1c80: 65 6d 62 65 64 64 69 6e 67 20 5c 66 49 6e 6f 64 embedding \fInod
1c90: 65 6c 69 73 74 5c 66 52 3f 0a 52 65 74 75 72 6e elist\fR?.Return
1ca0: 20 61 20 6c 69 73 74 20 6f 66 20 6e 6f 64 65 73 a list of nodes
1cb0: 20 69 6e 20 74 68 65 20 67 72 61 70 68 2e 20 52 in the graph. R
1cc0: 65 73 74 72 69 63 74 69 6f 6e 73 20 63 61 6e 20 estrictions can
1cd0: 6c 69 6d 69 74 20 74 68 65 20 6c 69 73 74 0a 6f limit the list.o
1ce0: 66 20 72 65 74 75 72 6e 65 64 20 6e 6f 64 65 73 f returned nodes
1cf0: 20 62 61 73 65 64 20 6f 6e 20 6e 65 69 67 68 62 based on neighb
1d00: 6f 72 69 6e 67 20 6e 6f 64 65 73 2c 20 6f 72 20 oring nodes, or
1d10: 62 61 73 65 64 20 6f 6e 20 74 68 65 20 6b 65 79 based on the key
1d20: 65 64 0a 76 61 6c 75 65 73 20 61 73 73 6f 63 69 ed.values associ
1d30: 61 74 65 64 20 77 69 74 68 20 74 68 65 20 6e 6f ated with the no
1d40: 64 65 2e 20 54 68 65 20 72 65 73 74 72 69 63 74 de. The restrict
1d50: 69 6f 6e 73 20 74 68 61 74 20 69 6e 76 6f 6c 76 ions that involv
1d60: 65 0a 6e 65 69 67 68 62 6f 72 69 6e 67 20 6e 6f e.neighboring no
1d70: 64 65 73 20 68 61 76 65 20 61 20 6c 69 73 74 20 des have a list
1d80: 6f 66 20 6e 6f 64 65 73 20 61 73 20 61 72 67 75 of nodes as argu
1d90: 6d 65 6e 74 2c 20 73 70 65 63 69 66 69 65 64 20 ment, specified
1da0: 61 66 74 65 72 0a 74 68 65 20 6e 61 6d 65 20 6f after.the name o
1db0: 66 20 74 68 65 20 72 65 73 74 72 69 63 74 69 6f f the restrictio
1dc0: 6e 20 69 74 73 65 6c 66 2e 0a 2e 73 70 0a 54 68 n itself...sp.Th
1dd0: 65 20 70 6f 73 73 69 62 6c 65 20 72 65 73 74 72 e possible restr
1de0: 69 63 74 69 6f 6e 73 20 61 72 65 20 74 68 65 20 ictions are the
1df0: 73 61 6d 65 20 61 73 20 66 6f 72 20 6d 65 74 68 same as for meth
1e00: 6f 64 20 5c 66 42 61 72 63 73 5c 66 52 2e 20 54 od \fBarcs\fR. T
1e10: 68 65 0a 73 65 74 20 6f 66 20 6e 6f 64 65 73 20 he.set of nodes
1e20: 74 6f 20 72 65 74 75 72 6e 20 69 73 20 63 6f 6d to return is com
1e30: 70 75 74 65 64 20 61 73 20 74 68 65 20 75 6e 69 puted as the uni
1e40: 6f 6e 20 6f 66 20 61 6c 6c 20 73 6f 75 72 63 65 on of all source
1e50: 20 61 6e 64 0a 74 61 72 67 65 74 20 6e 6f 64 65 and.target node
1e60: 73 20 66 6f 72 20 61 6c 6c 20 74 68 65 20 61 72 s for all the ar
1e70: 63 73 20 73 61 74 69 73 66 79 69 6e 67 20 74 68 cs satisfying th
1e80: 65 20 72 65 73 74 72 69 63 74 69 6f 6e 20 61 73 e restriction as
1e90: 20 64 65 66 69 6e 65 64 0a 66 6f 72 20 5c 66 42 defined.for \fB
1ea0: 61 72 63 73 5c 66 52 2e 0a 2e 54 50 0a 5c 66 49 arcs\fR...TP.\fI
1eb0: 67 72 61 70 68 4e 61 6d 65 5c 66 52 20 5c 66 42 graphName\fR \fB
1ec0: 67 65 74 5c 66 52 20 3f 5c 66 49 2d 6b 65 79 20 get\fR ?\fI-key
1ed0: 6b 65 79 5c 66 52 3f 0a 52 65 74 75 72 6e 20 74 key\fR?.Return t
1ee0: 68 65 20 76 61 6c 75 65 20 61 73 73 6f 63 69 61 he value associa
1ef0: 74 65 64 20 77 69 74 68 20 74 68 65 20 6b 65 79 ted with the key
1f00: 20 5c 66 49 6b 65 79 5c 66 52 20 66 6f 72 20 74 \fIkey\fR for t
1f10: 68 65 20 67 72 61 70 68 2e 20 49 66 0a 6e 6f 20 he graph. If.no
1f20: 6b 65 79 20 69 73 20 73 70 65 63 69 66 69 65 64 key is specified
1f30: 2c 20 74 68 65 20 6b 65 79 20 5c 66 42 64 61 74 , the key \fBdat
1f40: 61 5c 66 52 20 69 73 20 61 73 73 75 6d 65 64 2e a\fR is assumed.
1f50: 0a 2e 54 50 0a 5c 66 49 67 72 61 70 68 4e 61 6d ..TP.\fIgraphNam
1f60: 65 5c 66 52 20 5c 66 42 73 65 74 5c 66 52 20 3f e\fR \fBset\fR ?
1f70: 5c 66 49 2d 6b 65 79 20 6b 65 79 5c 66 52 3f 20 \fI-key key\fR?
1f80: 3f 5c 66 49 76 61 6c 75 65 5c 66 52 3f 0a 53 65 ?\fIvalue\fR?.Se
1f90: 74 20 6f 72 20 67 65 74 20 6f 6e 65 20 6f 66 20 t or get one of
1fa0: 74 68 65 20 6b 65 79 65 64 20 76 61 6c 75 65 73 the keyed values
1fb0: 20 61 73 73 6f 63 69 61 74 65 64 20 77 69 74 68 associated with
1fc0: 20 61 20 67 72 61 70 68 2e 20 49 66 20 6e 6f 20 a graph. If no
1fd0: 6b 65 79 0a 69 73 20 73 70 65 63 69 66 69 65 64 key.is specified
1fe0: 2c 20 74 68 65 20 6b 65 79 20 5c 66 42 64 61 74 , the key \fBdat
1ff0: 61 5c 66 52 20 69 73 20 61 73 73 75 6d 65 64 2e a\fR is assumed.
2000: 20 45 61 63 68 20 67 72 61 70 68 20 68 61 73 20 Each graph has
2010: 74 68 65 20 76 61 6c 75 65 0a 22 22 20 61 73 73 the value."" ass
2020: 69 67 6e 65 64 20 74 6f 20 74 68 65 20 6b 65 79 igned to the key
2030: 20 5c 66 42 64 61 74 61 5c 66 52 20 61 75 74 6f \fBdata\fR auto
2040: 6d 61 74 69 63 61 6c 6c 79 2e 20 41 20 67 72 61 matically. A gra
2050: 70 68 20 6d 61 79 20 68 61 76 65 20 61 6e 79 0a ph may have any.
2060: 6e 75 6d 62 65 72 20 6f 66 20 6b 65 79 65 64 20 number of keyed
2070: 76 61 6c 75 65 73 20 61 73 73 6f 63 69 61 74 65 values associate
2080: 64 20 77 69 74 68 20 69 74 2e 20 49 66 20 5c 66 d with it. If \f
2090: 49 76 61 6c 75 65 5c 66 52 20 69 73 20 6e 6f 74 Ivalue\fR is not
20a0: 0a 73 70 65 63 69 66 69 65 64 2c 20 74 68 69 73 .specified, this
20b0: 20 63 6f 6d 6d 61 6e 64 20 72 65 74 75 72 6e 73 command returns
20c0: 20 74 68 65 20 63 75 72 72 65 6e 74 20 76 61 6c the current val
20d0: 75 65 20 61 73 73 69 67 6e 65 64 20 74 6f 20 74 ue assigned to t
20e0: 68 65 20 6b 65 79 3b 0a 69 66 20 5c 66 49 76 61 he key;.if \fIva
20f0: 6c 75 65 5c 66 52 20 69 73 20 73 70 65 63 69 66 lue\fR is specif
2100: 69 65 64 2c 20 74 68 69 73 20 63 6f 6d 6d 61 6e ied, this comman
2110: 64 20 61 73 73 69 67 6e 73 20 74 68 61 74 20 76 d assigns that v
2120: 61 6c 75 65 20 74 6f 20 74 68 65 0a 6b 65 79 2e alue to the.key.
2130: 0a 2e 54 50 0a 5c 66 49 67 72 61 70 68 4e 61 6d ..TP.\fIgraphNam
2140: 65 5c 66 52 20 5c 66 42 73 77 61 70 5c 66 52 20 e\fR \fBswap\fR
2150: 5c 66 49 6e 6f 64 65 31 5c 66 52 20 5c 66 49 6e \fInode1\fR \fIn
2160: 6f 64 65 32 5c 66 52 0a 53 77 61 70 20 74 68 65 ode2\fR.Swap the
2170: 20 70 6f 73 69 74 69 6f 6e 20 6f 66 20 5c 66 49 position of \fI
2180: 6e 6f 64 65 31 5c 66 52 20 61 6e 64 20 5c 66 49 node1\fR and \fI
2190: 6e 6f 64 65 32 5c 66 52 20 69 6e 20 74 68 65 20 node2\fR in the
21a0: 67 72 61 70 68 2e 0a 2e 54 50 0a 5c 66 49 67 72 graph...TP.\fIgr
21b0: 61 70 68 4e 61 6d 65 5c 66 52 20 5c 66 42 75 6e aphName\fR \fBun
21c0: 73 65 74 5c 66 52 20 3f 5c 66 49 2d 6b 65 79 20 set\fR ?\fI-key
21d0: 6b 65 79 5c 66 52 3f 0a 52 65 6d 6f 76 65 20 61 key\fR?.Remove a
21e0: 20 6b 65 79 65 64 20 76 61 6c 75 65 20 66 72 6f keyed value fro
21f0: 6d 20 74 68 65 20 67 72 61 70 68 2e 20 49 66 20 m the graph. If
2200: 6e 6f 20 6b 65 79 20 69 73 20 73 70 65 63 69 66 no key is specif
2210: 69 65 64 2c 20 74 68 65 20 6b 65 79 0a 5c 66 42 ied, the key.\fB
2220: 64 61 74 61 5c 66 52 20 69 73 20 61 73 73 75 6d data\fR is assum
2230: 65 64 2e 0a 2e 54 50 0a 5c 66 49 67 72 61 70 68 ed...TP.\fIgraph
2240: 4e 61 6d 65 5c 66 52 20 5c 66 42 77 61 6c 6b 5c Name\fR \fBwalk\
2250: 66 52 20 5c 66 49 6e 6f 64 65 5c 66 52 20 3f 5c fR \fInode\fR ?\
2260: 66 49 2d 6f 72 64 65 72 20 6f 72 64 65 72 5c 66 fI-order order\f
2270: 52 3f 20 3f 5c 66 49 2d 74 79 70 65 20 74 79 70 R? ?\fI-type typ
2280: 65 5c 66 52 3f 20 3f 5c 66 49 2d 64 69 72 20 64 e\fR? ?\fI-dir d
2290: 69 72 65 63 74 69 6f 6e 5c 66 52 3f 20 5c 66 49 irection\fR? \fI
22a0: 2d 63 6f 6d 6d 61 6e 64 20 63 6d 64 5c 66 52 0a -command cmd\fR.
22b0: 0a 50 65 72 66 6f 72 6d 20 61 20 62 72 65 61 64 .Perform a bread
22c0: 74 68 2d 66 69 72 73 74 20 6f 72 20 64 65 70 74 th-first or dept
22d0: 68 2d 66 69 72 73 74 20 77 61 6c 6b 20 6f 66 20 h-first walk of
22e0: 74 68 65 20 67 72 61 70 68 20 73 74 61 72 74 69 the graph starti
22f0: 6e 67 20 61 74 0a 74 68 65 20 6e 6f 64 65 20 5c ng at.the node \
2300: 66 49 6e 6f 64 65 5c 66 52 20 67 6f 69 6e 67 20 fInode\fR going
2310: 69 6e 20 65 69 74 68 65 72 20 74 68 65 20 64 69 in either the di
2320: 72 65 63 74 69 6f 6e 20 6f 66 20 6f 75 74 67 6f rection of outgo
2330: 69 6e 67 20 6f 72 0a 6f 70 70 6f 73 69 74 65 20 ing or.opposite
2340: 74 6f 20 74 68 65 20 69 6e 63 6f 6d 69 6e 67 20 to the incoming
2350: 61 72 63 73 2e 0a 0a 54 68 65 20 74 79 70 65 20 arcs...The type
2360: 6f 66 20 77 61 6c 6b 2c 20 62 72 65 61 64 74 68 of walk, breadth
2370: 2d 66 69 72 73 74 20 6f 72 20 64 65 70 74 68 2d -first or depth-
2380: 66 69 72 73 74 2c 20 69 73 20 64 65 74 65 72 6d first, is determ
2390: 69 6e 65 64 20 62 79 20 74 68 65 0a 76 61 6c 75 ined by the.valu
23a0: 65 20 6f 66 20 5c 66 49 74 79 70 65 5c 66 52 3b e of \fItype\fR;
23b0: 20 5c 66 42 62 66 73 5c 66 52 20 69 6e 64 69 63 \fBbfs\fR indic
23c0: 61 74 65 73 20 62 72 65 61 64 74 68 2d 66 69 72 ates breadth-fir
23d0: 73 74 2c 20 5c 66 42 64 66 73 5c 66 52 0a 69 6e st, \fBdfs\fR.in
23e0: 64 69 63 61 74 65 73 20 64 65 70 74 68 2d 66 69 dicates depth-fi
23f0: 72 73 74 2e 20 20 44 65 70 74 68 2d 66 69 72 73 rst. Depth-firs
2400: 74 20 69 73 20 74 68 65 20 64 65 66 61 75 6c 74 t is the default
2410: 2e 0a 0a 54 68 65 20 6f 72 64 65 72 20 6f 66 20 ...The order of
2420: 74 68 65 20 77 61 6c 6b 2c 20 70 72 65 2d 6f 72 the walk, pre-or
2430: 64 65 72 2c 20 70 6f 73 74 2d 6f 72 64 65 72 20 der, post-order
2440: 6f 72 20 62 6f 74 68 2d 6f 72 64 65 72 20 69 73 or both-order is
2450: 0a 64 65 74 65 72 6d 69 6e 65 64 20 62 79 20 74 .determined by t
2460: 68 65 20 76 61 6c 75 65 20 6f 66 20 5c 66 49 6f he value of \fIo
2470: 72 64 65 72 5c 66 52 3b 20 5c 66 42 70 72 65 5c rder\fR; \fBpre\
2480: 66 52 20 69 6e 64 69 63 61 74 65 73 20 70 72 65 fR indicates pre
2490: 2d 6f 72 64 65 72 2c 0a 5c 66 42 70 6f 73 74 5c -order,.\fBpost\
24a0: 66 52 20 69 6e 64 69 63 61 74 65 73 20 70 6f 73 fR indicates pos
24b0: 74 2d 6f 72 64 65 72 2c 20 5c 66 42 62 6f 74 68 t-order, \fBboth
24c0: 5c 66 52 20 69 6e 64 69 63 61 74 65 73 0a 62 6f \fR indicates.bo
24d0: 74 68 2d 6f 72 64 65 72 2e 20 50 72 65 2d 6f 72 th-order. Pre-or
24e0: 64 65 72 20 69 73 20 74 68 65 20 64 65 66 61 75 der is the defau
24f0: 6c 74 2e 20 50 72 65 2d 6f 72 64 65 72 20 77 61 lt. Pre-order wa
2500: 6c 6b 69 6e 67 20 6d 65 61 6e 73 20 74 68 61 74 lking means that
2510: 20 61 0a 6e 6f 64 65 20 69 73 20 76 69 73 69 74 a.node is visit
2520: 65 64 20 62 65 66 6f 72 65 20 61 6e 79 20 6f 66 ed before any of
2530: 20 69 74 73 20 6e 65 69 67 68 62 6f 72 73 20 28 its neighbors (
2540: 61 73 20 64 65 66 69 6e 65 64 20 62 79 20 74 68 as defined by th
2550: 65 0a 5c 66 49 64 69 72 65 63 74 69 6f 6e 5c 66 e.\fIdirection\f
2560: 52 2c 20 73 65 65 20 62 65 6c 6f 77 29 2e 20 50 R, see below). P
2570: 6f 73 74 2d 6f 72 64 65 72 20 77 61 6c 6b 69 6e ost-order walkin
2580: 67 20 6d 65 61 6e 73 20 74 68 61 74 20 61 20 70 g means that a p
2590: 61 72 65 6e 74 20 69 73 0a 76 69 73 69 74 65 64 arent is.visited
25a0: 20 61 66 74 65 72 20 61 6e 79 20 6f 66 20 69 74 after any of it
25b0: 73 20 6e 65 69 67 68 62 6f 72 73 2e 20 42 6f 74 s neighbors. Bot
25c0: 68 2d 6f 72 64 65 72 20 77 61 6c 6b 69 6e 67 20 h-order walking
25d0: 6d 65 61 6e 73 20 74 68 61 74 20 61 0a 6e 6f 64 means that a.nod
25e0: 65 20 69 73 20 76 69 73 69 74 65 64 20 62 65 66 e is visited bef
25f0: 6f 72 65 20 5c 66 42 61 6e 64 5c 66 52 20 61 66 ore \fBand\fR af
2600: 74 65 72 20 61 6e 79 20 6f 66 20 69 74 73 20 6e ter any of its n
2610: 65 69 67 68 62 6f 72 73 2e 20 54 68 65 0a 63 6f eighbors. The.co
2620: 6d 62 69 6e 61 74 69 6f 6e 20 6f 66 20 61 20 62 mbination of a b
2630: 72 65 61 64 2d 66 69 72 73 74 20 77 61 6c 6b 20 read-first walk
2640: 77 69 74 68 20 70 6f 73 74 2d 20 6f 72 20 62 6f with post- or bo
2650: 74 68 2d 6f 72 64 65 72 20 69 73 20 69 6c 6c 65 th-order is ille
2660: 67 61 6c 2e 0a 0a 54 68 65 20 64 69 72 65 63 74 gal...The direct
2670: 69 6f 6e 20 6f 66 20 74 68 65 20 77 61 6c 6b 20 ion of the walk
2680: 69 73 20 64 65 74 65 72 6d 69 6e 65 64 20 62 79 is determined by
2690: 20 74 68 65 20 76 61 6c 75 65 20 6f 66 20 5c 66 the value of \f
26a0: 49 64 69 72 5c 66 52 3b 0a 5c 66 42 62 61 63 6b Idir\fR;.\fBback
26b0: 77 61 72 64 5c 66 52 20 69 6e 64 69 63 61 74 65 ward\fR indicate
26c0: 73 20 74 68 65 20 64 69 72 65 63 74 69 6f 6e 20 s the direction
26d0: 6f 70 70 6f 73 69 74 65 20 74 6f 20 74 68 65 20 opposite to the
26e0: 69 6e 63 6f 6d 69 6e 67 20 61 72 63 73 2c 0a 5c incoming arcs,.\
26f0: 66 42 66 6f 72 77 61 72 64 5c 66 52 20 69 6e 64 fBforward\fR ind
2700: 69 63 61 74 65 73 20 74 68 65 20 64 69 72 65 63 icates the direc
2710: 74 69 6f 6e 20 6f 66 20 74 68 65 20 6f 75 74 67 tion of the outg
2720: 6f 69 6e 67 20 61 72 63 73 2e 0a 0a 41 73 20 74 oing arcs...As t
2730: 68 65 20 77 61 6c 6b 20 70 72 6f 67 72 65 73 73 he walk progress
2740: 65 73 2c 20 74 68 65 20 63 6f 6d 6d 61 6e 64 20 es, the command
2750: 5c 66 49 63 6d 64 5c 66 52 20 77 69 6c 6c 20 62 \fIcmd\fR will b
2760: 65 20 65 76 61 6c 75 61 74 65 64 20 61 74 0a 65 e evaluated at.e
2770: 61 63 68 20 6e 6f 64 65 2c 20 77 69 74 68 20 74 ach node, with t
2780: 68 65 20 6d 6f 64 65 20 6f 66 20 74 68 65 20 63 he mode of the c
2790: 61 6c 6c 20 28 5c 66 42 65 6e 74 65 72 5c 66 52 all (\fBenter\fR
27a0: 20 6f 72 20 5c 66 42 6c 65 61 76 65 5c 66 52 29 or \fBleave\fR)
27b0: 20 61 6e 64 0a 76 61 6c 75 65 73 20 5c 66 49 67 and.values \fIg
27c0: 72 61 70 68 4e 61 6d 65 5c 66 52 20 61 6e 64 20 raphName\fR and
27d0: 74 68 65 20 6e 61 6d 65 20 6f 66 20 74 68 65 20 the name of the
27e0: 63 75 72 72 65 6e 74 20 6e 6f 64 65 20 61 70 70 current node app
27f0: 65 6e 64 65 64 2e 20 46 6f 72 0a 61 20 70 72 65 ended. For.a pre
2800: 2d 6f 72 64 65 72 20 77 61 6c 6b 20 61 6c 6c 20 -order walk all
2810: 6e 6f 64 65 73 20 61 72 65 20 42 65 6e 74 65 72 nodes are Benter
2820: 65 64 2c 20 66 6f 72 20 61 20 70 6f 73 74 2d 6f ed, for a post-o
2830: 72 64 65 72 20 61 6c 6c 20 6e 6f 64 65 73 0a 61 rder all nodes.a
2840: 72 65 20 6c 65 66 74 2e 20 49 6e 20 61 20 62 6f re left. In a bo
2850: 74 68 2d 6f 72 64 65 72 20 77 61 6c 6b 20 74 68 th-order walk th
2860: 65 20 66 69 72 73 74 20 76 69 73 69 74 20 6f 66 e first visit of
2870: 20 61 20 6e 6f 64 65 20 5c 66 42 65 6e 74 65 72 a node \fBenter
2880: 5c 66 52 73 0a 69 74 2c 20 74 68 65 20 73 65 63 \fRs.it, the sec
2890: 6f 6e 64 20 76 69 73 69 74 20 5c 66 42 6c 65 61 ond visit \fBlea
28a0: 76 65 5c 66 52 73 20 69 74 2e 0a 0a 2e 53 48 20 ve\fRs it....SH
28b0: 4b 45 59 57 4f 52 44 53 0a 67 72 61 70 68 0a KEYWORDS.graph.
