%%Page: 1 1
1 0 bop 2652 7428 a FH(T)-150 b(ra)-50 b(v)g(ersals)580
b(of)e(Ob)100 b(ject)579 b(Structures:)780 b(Sp)50 b(eci\014cation)579
b(and)g(E\016cien)-50 b(t)19160 10107 y(Implemen)g(tation)31240
9412 y FG(\003)10028 14190 y FF(Karl)435 b(Lieb)36 b(erherr)8311
15894 y FE(lieber@ccs.neu.edu)6316 17599 y FF(College)435
b(of)f(Computer)f(Science)7628 19304 y(Northeastern)g(Univ)-36
b(ersit)g(y)8941 21008 y(Boston,)434 b(MA)867 b(02115)13127
22713 y(USA)30166 14190 y(Boaz)434 b(P)-36 b(att-Shamir)29126
15894 y FE(boaz@eng.tau.ac.il)26472 17599 y FF(Dept.)434
b(of)g(Electrical)g(Engineering)29693 19304 y(T)-108
b(el-Aviv)435 b(Univ)-36 b(ersit)g(y)30979 21008 y(T)-108
b(el-Aviv)435 b(69978)32867 22713 y(ISRAEL)21304 25068
y(Doug)f(Orleans)19390 26773 y FE(dougo@ccs.neu.edu)17053
28478 y FF(College)h(of)f(Computer)f(Science)18365 30182
y(Northeastern)g(Univ)-36 b(ersit)g(y)19678 31887 y(Boston,)434
b(MA)867 b(02115)23864 33592 y(USA)21154 36909 y(Marc)-36
b(h)433 b(7,)h(2004)22765 41412 y FD(Abstract)3091 43793
y FC(Separation)428 b(of)e(concerns)g(and)g(lo)31 b(ose)427
b(coupling)g(of)g(concerns)e(are)h(imp)31 b(ortan)-31
b(t)429 b(issues)c(in)h(soft)-31 b(w)g(are)428 b(engin-)1430
45254 y(nering.)485 b(In)345 b(this)h(pap)31 b(er)345
b(w)-31 b(e)346 b(sho)-31 b(w)346 b(ho)-31 b(w)346 b(to)h(separate)e
(tra)-31 b(v)g(ersal-related)348 b(concerns)d(from)h(other)f(concerns,)
351 b(ho)-31 b(w)1430 46716 y(to)381 b(lo)31 b(osely)381
b(couple)g(tra)-31 b(v)g(ersal-related)382 b(concerns)d(to)i(the)f
(structural)h(concern)e(and)i(ho)-31 b(w)380 b(to)h(e\016cien)-31
b(tly)382 b(imple-)1430 48177 y(men)-31 b(t)330 b(tra)-31
b(v)g(ersal-related)332 b(concerns.)479 b(The)329 b(stress)f(is)h(on)g
(the)h(detailed)h(description)f(of)f(our)g(algorithms)j(and)d(the)1430
49638 y(tra)-31 b(v)g(ersal)371 b(sp)31 b(eci\014cations)370
b(they)g(op)31 b(erate)369 b(on.)3091 51099 y(T)-92 b(ra)-31
b(v)g(ersal)409 b(of)g(ob)61 b(ject)410 b(structures)d(is)h(a)h
(ubiquitous)h(routine)f(in)f(most)i(t)-31 b(yp)31 b(es)408
b(of)h(information)i(pro)31 b(cessing.)1430 52560 y(Ad-ho)g(c)249
b(implemen)-31 b(tations)253 b(of)d(tra)-31 b(v)g(ersals)250
b(lead)f(to)h(scattered)f(and)h(tangled)g(co)31 b(de)249
b(and)g(in)h(this)f(pap)31 b(er)248 b(w)-31 b(e)250 b(presen)-31
b(t)1430 54022 y(a)448 b(new)f(approac)-31 b(h,)469 b(called)448
b FB(tr)-57 b(aversal)467 b(str)-57 b(ate)g(gies,)468
b FC(to)448 b(succinctly)g(mo)31 b(dularize)449 b(tra)-31
b(v)g(ersals.)728 b(In)446 b(our)i(approac)-31 b(h)1430
55483 y(tra)g(v)g(ersals)264 b(are)f(de\014ned)g(using)h(a)f(high-lev)
-31 b(el)266 b(directed)d(graph)h(description,)286 b(whic)-31
b(h)264 b(is)f(compiled)i(in)-31 b(to)265 b(a)e(dynamic)1430
56944 y(road)343 b(map)h(to)f(assist)g(run-time)g(tra)-31
b(v)g(ersals.)485 b(The)343 b(complexit)-31 b(y)345 b(of)e(the)g
(compilation)j(algorithm)g(is)c(p)31 b(olynomial)1430
58405 y(in)283 b(the)f(size)g(of)h(the)f(tra)-31 b(v)g(ersal)283
b(strategy)h(graph)e(and)g(the)h(class)f(graph)g(of)h(the)f(giv)-31
b(en)284 b(application.)466 b(Protot)-31 b(yp)31 b(es)284
b(of)1430 59866 y(the)266 b(system)g(ha)-31 b(v)g(e)267
b(b)31 b(een)265 b(dev)-31 b(elop)31 b(ed)267 b(and)f(are)g(b)31
b(eing)266 b(successfully)g(used)f(to)h(implemen)-31
b(t)268 b(tra)-31 b(v)g(ersals)267 b(for)f(Ja)-31 b(v)-61
b(a)266 b(and)1430 61328 y(Asp)31 b(ectJ)385 b([KHH)8539
60926 y FA(+)9275 61328 y FC(01)q(])h(and)f(for)h(generating)h
(adapters)f(for)f(soft)-31 b(w)g(are)387 b(comp)31 b(onen)-31
b(ts.)543 b(Our)385 b(previous)g(approac)-31 b(h,)1430
62789 y(called)455 b FB(tr)-57 b(aversal)472 b(sp)-57
b(e)g(ci\014c)g(ations)454 b FC([Lie92)r(,)g(PXL95)q(],)475
b(w)-31 b(as)453 b(less)g(general,)475 b(less)452 b(succinct,)475
b(and)453 b(its)h(compilation)1430 64250 y(algorithm)400
b(w)-31 b(as)398 b(of)g(exp)31 b(onen)-31 b(tial)399
b(complexit)-31 b(y)400 b(in)d(some)h(cases.)576 b(In)397
b(an)g(additional)j(result)d(w)-31 b(e)398 b(sho)-31
b(w)398 b(that)g(this)1430 65711 y(bad)337 b(b)31 b(eha)-31
b(vior)337 b(is)g(inheren)-31 b(t)337 b(to)g(the)f(static)i(tra)-31
b(v)g(ersal)338 b(co)31 b(de)336 b(generated)h(b)-31
b(y)337 b(previous)f(implemen)-31 b(tations,)348 b(where)1430
67172 y(tra)-31 b(v)g(ersals)370 b(are)f(carried)g(out)h(b)-31
b(y)370 b(in)-31 b(v)g(oking)372 b(metho)31 b(ds)369
b(without)j(parameters.)p -1600 69827 21440 45 v -237
70544 a Fz(\003)243 70967 y Fy(Researc)-28 b(h)514 b(supp)28
b(orted)514 b(b)-28 b(y)514 b(Defense)i(Adv)-57 b(anced)514
b(Pro)57 b(jects)514 b(Agency)h(\(D)-28 b(ARP)-85 b(A\))513
b(and)h(Rome)h(Lab)28 b(oratory)514 b(under)f(agreemen)-28
b(ts)-1600 72307 y(F30602-96-0239)342 b(and)f(F33615-00-C-1694)h(and)f
(NSF)g(Gran)-28 b(t)341 b(CCR)f(0098643.)p eop
%%Page: 1 2
1 1 bop -1600 2325 a Fx(1)1793 b(In)-50 b(tro)50 b(duction)-1600
5790 y Fw(1.1)1495 b(The)498 b(Idea)h(of)f(Adaptiv)-42
b(e)499 b(T)-125 b(ra)-42 b(v)g(ersals)-1600 8789 y Fv(The)475
b(run-time)h(state)g(of)f(application)g(programs,)493
b(particularly)474 b(of)i(ob)67 b(ject-orien)-34 b(ted)476
b(programs,)493 b(can)475 b(b)34 b(e)475 b(repre-)-1600
10445 y(sen)-34 b(ted)358 b(as)f(a)g(directed)f(graph,)367
b(where)357 b(ob)67 b(jects)357 b(are)g(represen)-34
b(ted)357 b(as)g(no)34 b(des)357 b(and)h(\014eld)f(references)e(are)i
(represen)-34 b(ted)-1600 12101 y(as)421 b(edges.)587
b(T)-101 b(o)421 b(a)f(large)g(exten)-34 b(t,)425 b(program)420
b(execution)g(can)h(b)34 b(e)420 b(view)-34 b(ed)421
b(as)f(tra)-34 b(v)g(ersing)421 b(that)g(graph.)588 b(Examples)421
b(of)-1600 13757 y(tra)-34 b(v)g(ersals)488 b(are)f(that)j(sub-ob)67
b(jects)490 b(with)e(certain)g(prop)34 b(erties)488 b(are)f(sough)-34
b(t;)531 b(or)488 b(it)g(ma)-34 b(y)488 b(b)34 b(e)488
b(desired)g(to)g(compute)-1600 15413 y(a)442 b(function)i(of)e(certain)
g(sub-ob)67 b(jects)444 b(of)f(a)f(giv)-34 b(en)442 b(ob)67
b(ject.)653 b(In)442 b(standard)i(programming)e(tec)-34
b(hniques,)452 b(expressing)-1600 17069 y(tra)-34 b(v)g(ersals)401
b(in)-34 b(v)g(olv)g(es)400 b(a)h(strong)g(commitmen)-34
b(t)402 b(to)e(the)h(whole)g(class)f(structure)i(tra)-34
b(v)g(ersed)400 b(\(since)h(eac)-34 b(h)401 b(hop)g(in)g(the)-1600
18725 y(tra)-34 b(v)g(ersal)483 b(is)g(explicitly)f(co)34
b(ded)484 b(as)f(in)h(\\)p Fu(a:b)p Fv("\),)503 b(ev)-34
b(en)483 b(if)g(the)h(task)g(to)g(b)34 b(e)483 b(p)34
b(erformed)483 b(b)-34 b(y)484 b(the)g(tra)-34 b(v)g(ersal)483
b(dep)34 b(ends)-1600 20381 y(only)404 b(on)g(the)h(start)g(and)g(the)f
(target)h(ob)67 b(jects.)282 22597 y(W)-101 b(e)559 b(call)f(a)h
(concern)g(that)i(deals)e(with)h(tra)-34 b(v)g(ersing)560
b(ob)67 b(jects)560 b(for)f(implemen)-34 b(ting)560 b(some)g(b)34
b(eha)-34 b(vior)559 b(of)g(those)-1600 24253 y(ob)67
b(jects)312 b(a)e(tra)-34 b(v)g(ersal-related)310 b(concern.)507
b(A)311 b(t)-34 b(ypical)310 b(program)h(op)34 b(erating)310
b(on)h(large)f(sets)g(of)h(ob)67 b(jects)312 b(con)-34
b(tains)311 b(man)-34 b(y)-1600 25909 y(tra)g(v)g(ersal-related)340
b(concerns.)517 b(Those)341 b(tra)-34 b(v)g(ersal)340
b(concerns)g(already)g(exist)g(at)g(the)h(design)g(lev)-34
b(el)339 b(and)i(b)34 b(ecome)339 b(more)-1600 27565
y(re\014ned)532 b(as)f(w)-34 b(e)532 b(mo)-34 b(v)g(e)532
b(from)g(the)f(design)h(ob)67 b(ject)533 b(structure)f(to)g(the)f
(implemen)-34 b(tation)533 b(ob)67 b(ject)532 b(structure.)921
b(The)-1600 29221 y(ad-ho)34 b(c)416 b(w)-34 b(a)g(y)417
b(for)f(an)h(exp)34 b(erienced)414 b(programmer)i(to)h(implemen)-34
b(t)416 b(a)g(tra)-34 b(v)g(ersal)416 b(concern)g(is)g(to)g(write)g
(metho)34 b(ds)417 b(for)-1600 30877 y(eac)-34 b(h)443
b(of)f(the)h(classes)f(whose)h(ob)67 b(jects)444 b(are)d(tra)-34
b(v)g(ersed.)654 b(Unfortunately)-101 b(,)453 b(this)443
b(leads)f(to)h(a)f(scattered)h(and)g(tangled)-1600 32533
y(implemen)-34 b(tation)464 b(b)34 b(ecause)462 b(the)i(metho)34
b(ds)463 b(that)h(implemen)-34 b(t)464 b(the)f(concern)f(are)h(spread)g
(across)f(m)-34 b(ultiple)463 b(classes)-1600 34189 y(and)405
b(tangled)g(with)g(metho)34 b(ds)405 b(from)f(other)g(concerns.)282
36405 y(In)394 b(this)g(pap)34 b(er)394 b(w)-34 b(e)394
b(prop)34 b(ose)395 b(a)e(new)i(paradigm,)h(called)d
Ft(tr)-62 b(aversal)422 b(str)-62 b(ate)g(gies)p Fv(,)392
b(or)i Ft(str)-62 b(ate)g(gies)391 b Fv(for)j(short,)i(whic)-34
b(h)-1600 38061 y(helps)485 b(us)g(to)g(not)g(only)f(cleanly)g(mo)34
b(dularize)483 b(tra)-34 b(v)g(ersal-related)484 b(concerns)h(but)g
(also)g(to)f(minimally)g(bind)h(them)-1600 39717 y(to)536
b(the)h(structural)g(concern;)601 b(i.e.,)568 b(strategies)536
b(allo)-34 b(w)536 b(the)h(programmer)e(to)i(sp)34 b(ecify)535
b(tra)-34 b(v)g(ersals)536 b(in)g(a)h(lo)34 b(calized)-1600
41373 y(manner)443 b(with)g(minimal)f(binding)h(to)f(the)h(class)f
(structure.)653 b(Informally)-101 b(,)451 b(the)443 b(idea)f(is)g(to)g
(sp)34 b(ecify)442 b(the)g(high-lev)-34 b(el)-1600 43029
y(top)34 b(ology)327 b(of)h(the)f(tra)-34 b(v)g(ersal,)342
b(in)327 b(whic)-34 b(h)328 b(only)f(the)h(k)-34 b(ey)327
b(\\milestones")g(are)f(explicitly)g(men)-34 b(tioned;)353
b(giv)-34 b(en)327 b(a)h(concrete)-1600 44685 y(class)442
b(structure,)451 b(executable)442 b(tra)-34 b(v)g(ersal)442
b(co)34 b(de)441 b(is)h(compiled,)451 b(with)443 b(all)f(details)g
(\014lled)g(in.)652 b(Since)442 b(the)g(tra)-34 b(v)g(ersal)442
b(is)-1600 46341 y(minimally)462 b(b)34 b(ound)465 b(to)f(the)g(class)e
(structure,)479 b(c)-34 b(hanges)464 b(to)g(the)f(class)g(structure)h
(will)f(often)h(require)e(minimal)h(or)-1600 47997 y(no)405
b(c)-34 b(hanges)404 b(to)h(the)f(tra)-34 b(v)g(ersal)404
b(strategy)-101 b(.)282 50213 y(Strategies)334 b(are)f(a)h(generalized)
f(form)h(of)h Ft(tr)-62 b(aversal)366 b(sp)-62 b(e)g(ci\014c)g(ations)p
Fv(,)345 b(whic)-34 b(h)335 b(w)-34 b(ere)333 b(in)-34
b(tro)34 b(duced)335 b(in)f(a)g(simple)g(form)-1600 51869
y(in)343 b([Lie92)o(])f(and)i(formally)e(treated)h(in)g(a)g(more)f
(general)h(form)g(in)f([PXL95].)518 b(Succinct)343 b(sp)34
b(eci\014cations)343 b(of)g(tra)-34 b(v)g(ersals)-1600
53525 y(are)404 b(an)g(in)-34 b(tegral)404 b(part)h(of)f(Adaptiv)-34
b(e)405 b(Programming)f(\(AP\))h([Lie96)o(].)-1600 57486
y Fw(1.2)1495 b(Example)-1600 60485 y Fv(T)-101 b(o)444
b(giv)-34 b(e)443 b(a)g(more)g(concrete)f(\015a)-34 b(v)g(or)444
b(for)g(the)f(usefulness)i(of)e(strategies,)453 b(let)443
b(us)h(demonstrate)g(with)g(the)g(follo)-34 b(wing)-1600
62141 y(simple)404 b(example.)282 64357 y(Consider)283
b(a)g(program)f(sim)-34 b(ulating)284 b(bus)g(route)e(managemen)-34
b(t.)500 b(F)-101 b(or)282 b(expressing)h(class)f(graphs,)307
b(w)-34 b(e)283 b(use)g(the)g(class)-1600 66013 y(dictionary)510
b(graph)g(graphical)g(represen)-34 b(tation)511 b(from)f(the)g(Demeter)
g(metho)34 b(d)510 b([Lie96)o(].)856 b(Alternativ)-34
b(e)509 b(notations)-1600 67669 y(w)-34 b(ould)360 b(b)34
b(e)358 b(the)g(UML)g(class)g(diagram)h(notation)h([BRJ99)o(])e(or)g
(an)h(XML)f(sc)-34 b(hema)359 b(notation)h([Con].)523
b(F)-101 b(or)358 b(expressing)-1600 69325 y(b)34 b(eha)-34
b(vior,)473 b(w)-34 b(e)460 b(use)g(standard)i(Ja)-34
b(v)-67 b(a)459 b(and)i(the)f(DJ)f(library)g([OL01)o(,)h(LOO01)o(,)f
(Lieb],)473 b(a)459 b(Ja)-34 b(v)-67 b(a)460 b(implemen)-34
b(tation)461 b(of)-1600 70981 y(the)514 b(algorithms)h(in)f(this)g(pap)
34 b(er)514 b(\(see)g(Section)g(7.2.2)g(for)g(more)g(details)g(ab)34
b(out)515 b(DJ)e(and)i(our)f(other)g(soft)-34 b(w)g(are\).)24897
75628 y(1)p eop
%%Page: 2 3
2 2 bop -1600 1107 a
 31733106 15866550 2302361 25062850 38350766 43152834 startTexFig
 -1600 1107 a%%BeginDocument: busstop1.ps
%!PS-Adobe-2.0 EPSF-1.2
%%Creator: idraw
%%DocumentFonts: Helvetica Times-Italic
%%Pages: 1
%%BoundingBox: 35 381 583 656
%%EndComments

%%BeginIdrawPrologue
/arrowhead {
0 begin
transform originalCTM itransform
/taily exch def
/tailx exch def
transform originalCTM itransform
/tipy exch def
/tipx exch def
/dy tipy taily sub def
/dx tipx tailx sub def
/angle dx 0 ne dy 0 ne or { dy dx atan } { 90 } ifelse def
gsave
originalCTM setmatrix
tipx tipy translate
angle rotate
newpath
arrowHeight neg arrowWidth 2 div moveto
0 0 lineto
arrowHeight neg arrowWidth 2 div neg lineto
patternNone not {
originalCTM setmatrix
/padtip arrowHeight 2 exp 0.25 arrowWidth 2 exp mul add sqrt brushWidth mul
arrowWidth div def
/padtail brushWidth 2 div def
tipx tipy translate
angle rotate
padtip 0 translate
arrowHeight padtip add padtail add arrowHeight div dup scale
arrowheadpath
ifill
} if
brushNone not {
originalCTM setmatrix
tipx tipy translate
angle rotate
arrowheadpath
istroke
} if
grestore
end
} dup 0 9 dict put def

/arrowheadpath {
newpath
arrowHeight neg arrowWidth 2 div moveto
0 0 lineto
arrowHeight neg arrowWidth 2 div neg lineto
} def

/leftarrow {
0 begin
y exch get /taily exch def
x exch get /tailx exch def
y exch get /tipy exch def
x exch get /tipx exch def
brushLeftArrow { tipx tipy tailx taily arrowhead } if
end
} dup 0 4 dict put def

/rightarrow {
0 begin
y exch get /tipy exch def
x exch get /tipx exch def
y exch get /taily exch def
x exch get /tailx exch def
brushRightArrow { tipx tipy tailx taily arrowhead } if
end
} dup 0 4 dict put def

%%EndIdrawPrologue

/arrowHeight 8 def
/arrowWidth 4 def

/IdrawDict 52 dict def
IdrawDict begin

/reencodeISO {
dup dup findfont dup length dict begin
{ 1 index /FID ne { def }{ pop pop } ifelse } forall
/Encoding ISOLatin1Encoding def
currentdict end definefont
} def

/ISOLatin1Encoding [
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/space/exclam/quotedbl/numbersign/dollar/percent/ampersand/quoteright
/parenleft/parenright/asterisk/plus/comma/minus/period/slash
/zero/one/two/three/four/five/six/seven/eight/nine/colon/semicolon
/less/equal/greater/question/at/A/B/C/D/E/F/G/H/I/J/K/L/M/N
/O/P/Q/R/S/T/U/V/W/X/Y/Z/bracketleft/backslash/bracketright
/asciicircum/underscore/quoteleft/a/b/c/d/e/f/g/h/i/j/k/l/m
/n/o/p/q/r/s/t/u/v/w/x/y/z/braceleft/bar/braceright/asciitilde
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/dotlessi/grave/acute/circumflex/tilde/macron/breve
/dotaccent/dieresis/.notdef/ring/cedilla/.notdef/hungarumlaut
/ogonek/caron/space/exclamdown/cent/sterling/currency/yen/brokenbar
/section/dieresis/copyright/ordfeminine/guillemotleft/logicalnot
/hyphen/registered/macron/degree/plusminus/twosuperior/threesuperior
/acute/mu/paragraph/periodcentered/cedilla/onesuperior/ordmasculine
/guillemotright/onequarter/onehalf/threequarters/questiondown
/Agrave/Aacute/Acircumflex/Atilde/Adieresis/Aring/AE/Ccedilla
/Egrave/Eacute/Ecircumflex/Edieresis/Igrave/Iacute/Icircumflex
/Idieresis/Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis
/multiply/Oslash/Ugrave/Uacute/Ucircumflex/Udieresis/Yacute
/Thorn/germandbls/agrave/aacute/acircumflex/atilde/adieresis
/aring/ae/ccedilla/egrave/eacute/ecircumflex/edieresis/igrave
/iacute/icircumflex/idieresis/eth/ntilde/ograve/oacute/ocircumflex
/otilde/odieresis/divide/oslash/ugrave/uacute/ucircumflex/udieresis
/yacute/thorn/ydieresis
] def
/Helvetica reencodeISO def
/Times-Italic reencodeISO def

/none null def
/numGraphicParameters 17 def
/stringLimit 65535 def

/Begin {
save
numGraphicParameters dict begin
} def

/End {
end
restore
} def

/SetB {
dup type /nulltype eq {
pop
false /brushRightArrow idef
false /brushLeftArrow idef
true /brushNone idef
} {
/brushDashOffset idef
/brushDashArray idef
0 ne /brushRightArrow idef
0 ne /brushLeftArrow idef
/brushWidth idef
false /brushNone idef
} ifelse
} def

/SetCFg {
/fgblue idef
/fggreen idef
/fgred idef
} def

/SetCBg {
/bgblue idef
/bggreen idef
/bgred idef
} def

/SetF {
/printSize idef
/printFont idef
} def

/SetP {
dup type /nulltype eq {
pop true /patternNone idef
} {
dup -1 eq {
/patternGrayLevel idef
/patternString idef
} {
/patternGrayLevel idef
} ifelse
false /patternNone idef
} ifelse
} def

/BSpl {
0 begin
storexyn
newpath
n 1 gt {
0 0 0 0 0 0 1 1 true subspline
n 2 gt {
0 0 0 0 1 1 2 2 false subspline
1 1 n 3 sub {
/i exch def
i 1 sub dup i dup i 1 add dup i 2 add dup false subspline
} for
n 3 sub dup n 2 sub dup n 1 sub dup 2 copy false subspline
} if
n 2 sub dup n 1 sub dup 2 copy 2 copy false subspline
patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if
brushNone not { istroke } if
0 0 1 1 leftarrow
n 2 sub dup n 1 sub dup rightarrow
} if
end
} dup 0 4 dict put def

/Circ {
newpath
0 360 arc
closepath
patternNone not { ifill } if
brushNone not { istroke } if
} def

/CBSpl {
0 begin
dup 2 gt {
storexyn
newpath
n 1 sub dup 0 0 1 1 2 2 true subspline
1 1 n 3 sub {
/i exch def
i 1 sub dup i dup i 1 add dup i 2 add dup false subspline
} for
n 3 sub dup n 2 sub dup n 1 sub dup 0 0 false subspline
n 2 sub dup n 1 sub dup 0 0 1 1 false subspline
patternNone not { ifill } if
brushNone not { istroke } if
} {
Poly
} ifelse
end
} dup 0 4 dict put def

/Elli {
0 begin
newpath
4 2 roll
translate
scale
0 0 1 0 360 arc
closepath
patternNone not { ifill } if
brushNone not { istroke } if
end
} dup 0 1 dict put def

/Line {
0 begin
2 storexyn
newpath
x 0 get y 0 get moveto
x 1 get y 1 get lineto
brushNone not { istroke } if
0 0 1 1 leftarrow
0 0 1 1 rightarrow
end
} dup 0 4 dict put def

/MLine {
0 begin
storexyn
newpath
n 1 gt {
x 0 get y 0 get moveto
1 1 n 1 sub {
/i exch def
x i get y i get lineto
} for
patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if
brushNone not { istroke } if
0 0 1 1 leftarrow
n 2 sub dup n 1 sub dup rightarrow
} if
end
} dup 0 4 dict put def

/Poly {
3 1 roll
newpath
moveto
-1 add
{ lineto } repeat
closepath
patternNone not { ifill } if
brushNone not { istroke } if
} def

/Rect {
0 begin
/t exch def
/r exch def
/b exch def
/l exch def
newpath
l b moveto
l t lineto
r t lineto
r b lineto
closepath
patternNone not { ifill } if
brushNone not { istroke } if
end
} dup 0 4 dict put def

/Text {
ishow
} def

/idef {
dup where { pop pop pop } { exch def } ifelse
} def

/ifill {
0 begin
gsave
patternGrayLevel -1 ne {
fgred bgred fgred sub patternGrayLevel mul add
fggreen bggreen fggreen sub patternGrayLevel mul add
fgblue bgblue fgblue sub patternGrayLevel mul add setrgbcolor
eofill
} {
eoclip
originalCTM setmatrix
pathbbox /t exch def /r exch def /b exch def /l exch def
/w r l sub ceiling cvi def
/h t b sub ceiling cvi def
/imageByteWidth w 8 div ceiling cvi def
/imageHeight h def
bgred bggreen bgblue setrgbcolor
eofill
fgred fggreen fgblue setrgbcolor
w 0 gt h 0 gt and {
l w add b translate w neg h scale
w h true [w 0 0 h neg 0 h] { patternproc } imagemask
} if
} ifelse
grestore
end
} dup 0 8 dict put def

/istroke {
gsave
brushDashOffset -1 eq {
[] 0 setdash
1 setgray
} {
brushDashArray brushDashOffset setdash
fgred fggreen fgblue setrgbcolor
} ifelse
brushWidth setlinewidth
originalCTM setmatrix
stroke
grestore
} def

/ishow {
0 begin
gsave
fgred fggreen fgblue setrgbcolor
/fontDict printFont printSize scalefont dup setfont def
/descender fontDict begin 0 [FontBBox] 1 get FontMatrix end
transform exch pop def
/vertoffset 1 printSize sub descender sub def {
0 vertoffset moveto show
/vertoffset vertoffset printSize sub def
} forall
grestore
end
} dup 0 3 dict put def
/patternproc {
0 begin
/patternByteLength patternString length def
/patternHeight patternByteLength 8 mul sqrt cvi def
/patternWidth patternHeight def
/patternByteWidth patternWidth 8 idiv def
/imageByteMaxLength imageByteWidth imageHeight mul
stringLimit patternByteWidth sub min def
/imageMaxHeight imageByteMaxLength imageByteWidth idiv patternHeight idiv
patternHeight mul patternHeight max def
/imageHeight imageHeight imageMaxHeight sub store
/imageString imageByteWidth imageMaxHeight mul patternByteWidth add string def
0 1 imageMaxHeight 1 sub {
/y exch def
/patternRow y patternByteWidth mul patternByteLength mod def
/patternRowString patternString patternRow patternByteWidth getinterval def
/imageRow y imageByteWidth mul def
0 patternByteWidth imageByteWidth 1 sub {
/x exch def
imageString imageRow x add patternRowString putinterval
} for
} for
imageString
end
} dup 0 12 dict put def

/min {
dup 3 2 roll dup 4 3 roll lt { exch } if pop
} def

/max {
dup 3 2 roll dup 4 3 roll gt { exch } if pop
} def

/midpoint {
0 begin
/y1 exch def
/x1 exch def
/y0 exch def
/x0 exch def
x0 x1 add 2 div
y0 y1 add 2 div
end
} dup 0 4 dict put def

/thirdpoint {
0 begin
/y1 exch def
/x1 exch def
/y0 exch def
/x0 exch def
x0 2 mul x1 add 3 div
y0 2 mul y1 add 3 div
end
} dup 0 4 dict put def

/subspline {
0 begin
/movetoNeeded exch def
y exch get /y3 exch def
x exch get /x3 exch def
y exch get /y2 exch def
x exch get /x2 exch def
y exch get /y1 exch def
x exch get /x1 exch def
y exch get /y0 exch def
x exch get /x0 exch def
x1 y1 x2 y2 thirdpoint
/p1y exch def
/p1x exch def
x2 y2 x1 y1 thirdpoint
/p2y exch def
/p2x exch def
x1 y1 x0 y0 thirdpoint
p1x p1y midpoint
/p0y exch def
/p0x exch def
x2 y2 x3 y3 thirdpoint
p2x p2y midpoint
/p3y exch def
/p3x exch def
movetoNeeded { p0x p0y moveto } if
p1x p1y p2x p2y p3x p3y curveto
end
} dup 0 17 dict put def

/storexyn {
/n exch def
/y n array def
/x n array def
n 1 sub -1 0 {
/i exch def
y i 3 2 roll put
x i 3 2 roll put
} for
} def

/SSten {
fgred fggreen fgblue setrgbcolor
dup true exch 1 0 0 -1 0 6 -1 roll matrix astore
} def

/FSten {
dup 3 -1 roll dup 4 1 roll exch
newpath
0 0 moveto
dup 0 exch lineto
exch dup 3 1 roll exch lineto
0 lineto
closepath
bgred bggreen bgblue setrgbcolor
eofill
SSten
} def

/Rast {
exch dup 3 1 roll 1 0 0 -1 0 6 -1 roll matrix astore
} def

%%EndProlog

%I Idraw 12 Grid 8 8 

%%Page: 1 1

Begin
%I b u
%I cfg u
%I cbg u
%I f u
%I p u
%I t
[ 0.796717 0 0 0.796717 0 0 ] concat
/originalCTM matrix currentmatrix def

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0.75 SetP
%I t
[ 1 -0 -0 1 -173 121 ] concat
%I 4
653 576
789 576
787 596
653 596
4 Poly
End

Begin %I Rect
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0.75 SetP
%I t
[ 0.5 0 0 0.5 276.5 337.5 ] concat
%I
457 289 553 329 Rect
End

Begin %I Rect
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0.75 SetP
%I t
[ 0.5 0 0 0.5 171.5 360.5 ] concat
%I
601 337 849 377 Rect
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 476 544 ] concat
%I
[
(NonEmptyPersonList)
] Text
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0.75 SetP
%I t
[ 0.5 0 0 0.5 183.5 260.5 ] concat
%I 6
617 705
729 705
761 673
729 641
617 641
585 673
6 Poly
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 492 600 ] concat
%I
[
(PersonList)
] Text
End

Begin %I Rect
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0.75 SetP
%I t
[ 0.5 0 0 0.5 195.5 400.5 ] concat
%I
601 497 713 537 Rect
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0.75 SetP
%I t
[ 0.5 0 0 0.5 187.5 428.5 ] concat
%I 6
617 705
729 705
761 673
729 641
617 641
585 673
6 Poly
End

Begin %I Rect
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0.75 SetP
%I t
[ 0.5 0 0 0.5 195.5 472.5 ] concat
%I
297 657 425 697 Rect
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 348 816 ] concat
%I
[
(BusRoute)
] Text
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 545 464 ] concat
%I 4
102 610
94 602
102 594
110 602
4 Poly
End

Begin %I Pict
%I b u
%I cfg u
%I cbg u
%I f u
%I p u
%I t
[ 1 0 0 1 -132 -107 ] concat

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 184 851 ] concat
%I
[
(EmptyBusList)
] Text
End

Begin %I Rect
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 143.5 571.5 ] concat
%I
73 529 241 569 Rect
End

End %I eop

Begin %I Pict
%I b u
%I cfg u
%I cbg u
%I f u
%I p u
%I t
[ 1 0 0 1 -140 -131 ] concat

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 296 835 ] concat
%I
[
(NonEmptyBusList)
] Text
End

Begin %I Rect
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 143.5 571.5 ] concat
%I
297 497 513 537 Rect
End

End %I eop

Begin %I Pict
%I b u
%I cfg u
%I cbg u
%I f u
%I p u
%I t
[ 1 0 0 1 -108 -131 ] concat

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 296 795 ] concat
%I
[
(Bus)
] Text
End

Begin %I Rect
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 143.5 571.5 ] concat
%I
297 417 361 457 Rect
End

End %I eop

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 500 664 ] concat
%I
[
(BusStop)
] Text
End

Begin %I Pict
%I b u
%I cfg u
%I cbg u
%I f u
%I p u
%I t
[ 1 0 0 1 44 -195 ] concat

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 576 779 ] concat
%I
[
(EmptyPersonList)
] Text
End

Begin %I Rect
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 143.5 571.5 ] concat
%I
857 385 1057 425 Rect
End

End %I eop

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 509 497 ] concat
%I
[
(Person)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 492 768 ] concat
%I
[
(BusStopList)
] Text
End

Begin %I Pict
%I b u
%I cfg u
%I cbg u
%I f u
%I p u
%I t
[ 1 0 0 1 -116 -115 ] concat

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 296 879 ] concat
%I
[
(BusList)
] Text
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 -16.5 539.5 ] concat
%I 6
617 705
729 705
761 673
729 641
617 641
585 673
6 Poly
End

End %I eop

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 -0 -0 1 -128.5 226.5 ] concat
%I
538 574 626 555 Line
%I 1
End

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 -0 -0 1 -128.5 226.5 ] concat
%I
473 575 361 551 Line
%I 1
End

Begin %I Line
%I b 65535
3 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 -0 -0 1 -128.5 226.5 ] concat
%I
654 522 654 492 Line
%I 1
End

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 -0 -0 1 -128.5 226.5 ] concat
%I
656 471 656 444 Line
%I 1
End

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 -0 -0 1 -128.5 226.5 ] concat
%I
334 462 334 444 Line
%I 1
End

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 -0 -0 1 -128.5 226.5 ] concat
%I
657 422 657 389 Line
%I 1
End

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 -0 -0 1 -128.5 226.5 ] concat
%I
660 302 660 277 Line
%I 1
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 486 434 ] concat
%I 4
102 610
94 602
102 594
110 602
4 Poly
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 164 429 ] concat
%I 4
102 610
94 602
102 594
110 602
4 Poly
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 94 464 ] concat
%I 4
102 610
94 602
102 594
110 602
4 Poly
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 490 268 ] concat
%I 4
102 610
94 602
102 594
110 602
4 Poly
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 539 301 ] concat
%I 4
102 610
94 602
102 594
110 602
4 Poly
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 269 811 ] concat
%I
[
(buses)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 445 811 ] concat
%I
[
(busStops)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 221 683 ] concat
%I
[
(first)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 541 691 ] concat
%I
[
(first)
] Text
End

Begin %I BSpl
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 -0 -0 1 -128.5 226.5 ] concat
%I 6
609 470
596 464
577 478
572 510
576 534
608 539
6 BSpl
%I 1
End

Begin %I BSpl
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 -0 -0 1 -128.5 226.5 ] concat
%I 6
602 303
590 293
566 297
566 332
565 365
605 372
6 BSpl
%I 1
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 541 527 ] concat
%I
[
(first)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 269 683 ] concat
%I
[
(rest)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 453 691 ] concat
%I
[
(rest)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 405 539 ] concat
%I
[
(rest)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 534 636 ] concat
%I
[
(waiting)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 484 712 ] concat
%I
[
(NonEmptyBusStopList)
] Text
End

Begin %I BSpl
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 116 341 ] concat
%I 7
275 696
283 675
325 691
361 777
343 833
313 849
267 841
7 BSpl
%I 2
End

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 116 341 ] concat
%I
200 616 753 545 Line
%I 2
End

Begin %I Line
%I b 65535
3 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 27 581 ] concat
%I
266 359 221 339 Line
%I 2
End

Begin %I Line
%I b 65535
3 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 27 581 ] concat
%I
355 327 355 263 Line
%I 2
End

Begin %I Line
%I b 65535
3 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 161 581 ] concat
%I
814 367 898 338 Line
%I 2
End

Begin %I Line
%I b 65535
3 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 161 478 ] concat
%I
739 205 739 151 Line
%I 2
End

Begin %I Line
%I b 65535
3 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 161 478 ] concat
%I
807 238 904 222 Line
%I 2
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 253 635 ] concat
%I
[
(passengers)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 620 744 ] concat
%I
[
(EmptyBusStopList)
] Text
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.599539 -0 -0 0.599539 25.1806 591.145 ] concat
%I 4
979 230
1174 230
1174 263
979 263
4 Poly
End

End %I eop

showpage

%%Trailer

end

%%EndDocument

 endTexFig
 -1600 30670 a Fv(Figure)494 b(1:)718 b Ft(Bus)515 b(simulation)f
(class)h(gr)-62 b(aph.)803 b(Squar)-62 b(es)515 b(and)h(hexagons)e
(denote)h(classes)e(\(c)-62 b(oncr)g(ete)514 b(and)i(abstr)-62
b(act,)-1600 32326 y(r)g(esp)g(e)g(ctively\),)406 b(r)-62
b(e)g(gular)403 b(arr)-62 b(ows)404 b(denote)f(\014eld)h(r)-62
b(efer)g(enc)g(e)403 b(and)h(ar)-62 b(e)404 b(lab)-62
b(ele)g(d)402 b(by)i(the)g(\014eld)g(name,)410 b(and)404
b(he)-62 b(avy)403 b(arr)-62 b(ows)-1600 33982 y(\(lab)g(ele)g(d)431
b(with)i Fs(\005)p Ft(\))g(denote)f(the)g(sub)-62 b(class)431
b(r)-62 b(elation)432 b(\(for)h(the)f(shading,)g(se)-62
b(e)432 b(text\).)-1600 37560 y Fv(Consider)420 b(the)g(class)e(graph)i
(depicted)g(in)f(Figure)g(1,)k(whic)-34 b(h)420 b(de\014nes)g(a)g(data)
g(structure)f(describing)h(a)f(bus)h(route.)-1600 39216
y(A)335 b(bus)h(route)f(ob)67 b(ject)336 b(consists)g(of)f(t)-34
b(w)g(o)337 b(lists:)504 b(a)335 b(list)g(of)g(bus)h(ob)67
b(jects,)350 b(eac)-34 b(h)335 b(con)-34 b(taining)336
b(a)f(list)g(of)h(passengers;)358 b(and)336 b(a)-1600
40872 y(list)323 b(of)g(bus)h(stop)f(ob)67 b(jects,)340
b(eac)-34 b(h)323 b(con)-34 b(taining)324 b(a)f(list)f(of)i(p)34
b(eople)322 b(w)-34 b(aiting.)512 b(Supp)34 b(ose)324
b(that)g(as)f(a)g(part)g(of)h(a)e(sim)-34 b(ulation,)-1600
42528 y(w)g(e)401 b(w)-34 b(ould)402 b(lik)-34 b(e)400
b(to)h(determine)g(the)g(set)g(of)g(p)34 b(erson)401
b(ob)67 b(jects)402 b(corresp)34 b(onding)401 b(to)g(p)34
b(eople)400 b(w)-34 b(aiting)402 b(at)f(an)-34 b(y)401
b(bus)h(stop)-1600 44184 y(on)483 b(a)g(giv)-34 b(en)483
b(bus)g(route.)775 b(The)483 b(group)g(of)h(collab)34
b(orating)482 b(classes)g(whic)-34 b(h)484 b(is)e(needed)h(for)g(this)h
(task)f(is)f(shaded)i(in)-1600 45840 y(Figure)352 b(1.)521
b(T)-101 b(o)352 b(carry)f(out)h(the)h(sim)-34 b(ulation,)363
b(an)352 b(ob)67 b(ject-orien)-34 b(ted)353 b(program)f(w)-34
b(ould)353 b(con)-34 b(tain)353 b(a)f(metho)34 b(d)353
b(for)f(eac)-34 b(h)352 b(of)-1600 47496 y(these)k(shaded)i(classes.)
522 b(These)356 b(metho)34 b(ds)357 b(that)g(are)f(scattered)g(across)g
(sev)-34 b(eral)356 b(classes)f(w)-34 b(ould)358 b(tra)-34
b(v)g(erse)356 b(bus)h(route)-1600 49153 y(ob)67 b(jects.)523
b(Ho)-34 b(w)g(ev)g(er,)366 b(using)356 b(the)g(tec)-34
b(hnique)356 b(of)g(strategies,)365 b(one)356 b(can)g(solv)-34
b(e)355 b(the)h(problem)g(in)g(a)g(m)-34 b(uc)g(h)356
b(more)g(elegan)-34 b(t)-1600 50809 y(w)g(a)g(y)-101
b(,)581 b(b)-34 b(y)545 b(mo)34 b(dularizing)545 b(the)h(co)34
b(de)544 b(and)i(k)-34 b(eeping)545 b(it)h(in)f(one)g(place,)580
b(rather)545 b(than)h(scattered)f(through)i(sev)-34 b(eral)-1600
52465 y(classes)466 b(and)i(tangled)f(with)g(other)g(metho)34
b(ds.)727 b(W)-101 b(e)466 b(de\014ne)h(a)g(strategy)g(graph)g(with)g
(no)34 b(des)467 b Fr(BusRoute)p Fv(,)482 b Fr(BusStop)-1600
54121 y Fv(and)h Fr(P)-34 b(erson)484 b Fv(that)g(are)e(connected)h(b)
-34 b(y)483 b(an)g(edge)f(from)h Fr(BusRoute)f Fv(to)i
Fr(BusStop)f Fv(and)g(an)g(edge)g(from)g Fr(BusStop)g
Fv(to)-1600 55777 y Fr(P)-34 b(erson)p Fv(.)539 b(In)404
b(our)g(textual)h(syn)-34 b(tax,)404 b(the)h(strategy)f(can)g(b)34
b(e)404 b(expressed)g(as:)1430 58794 y Fq(from)638 b(BusRoute)h(via)f
(BusStop)h(to)e(Person)282 62371 y Fv(The)330 b(b)34
b(ene\014t)331 b(of)f(strategies)g(is)f(apparen)-34 b(t)332
b(when)e(considering)g(the)g(follo)-34 b(wing)331 b(scenario:)501
b(Supp)34 b(ose)331 b(that)g(the)f(bus)-1600 64027 y(route)362
b(class)f(has)h(b)34 b(een)361 b(mo)34 b(di\014ed)362
b(so)f(that)i(the)f(bus)g(stops)g(are)f(group)34 b(ed)362
b(b)-34 b(y)362 b(villages.)523 b(The)362 b(revised)e(class)h(graph)h
(is)-1600 65683 y(depicted)432 b(in)f(Figure)h(2.)620
b(T)-101 b(o)432 b(implemen)-34 b(t)432 b(the)g(same)f(requiremen)-34
b(t)431 b(of)h(\014nding)h(all)d(p)34 b(eople)431 b(w)-34
b(aiting)433 b(for)e(a)h(bus,)439 b(an)-1600 67339 y(ob)67
b(ject-orien)-34 b(ted)371 b(program)f(m)-34 b(ust)371
b(no)-34 b(w)371 b(con)-34 b(tain)371 b(one)f(metho)34
b(d)371 b(for)f(eac)-34 b(h)370 b(of)g(the)g(classes)f(shaded)i(in)f
(Figure)g(2,)376 b(and)-1600 68995 y(th)-34 b(us)475
b(the)f(previous)g(ob)67 b(ject-orien)-34 b(ted)475 b(implemen)-34
b(tation)475 b(b)34 b(ecomes)473 b(in)-34 b(v)-67 b(alid.)747
b(The)474 b(tra)-34 b(v)g(ersal)474 b(strategy)-101 b(,)491
b(ho)-34 b(w)g(ev)g(er,)-1600 70651 y(is)510 b(up-to-date)i(and)g(do)34
b(es)510 b(not)h(require)e(an)-34 b(y)511 b(rewriting.)857
b(In)511 b(fairness,)537 b(the)510 b(revision)g(to)h(the)g(class)f
(graph)h(m)-34 b(ust)-1600 72307 y(preserv)g(e)347 b(the)h(class)g
(names)g(referred)e(to)j(in)e(the)i(tra)-34 b(v)g(ersal)347
b(strategy)h(and)h(the)f(meaning)g(of)g(the)g(tra)-34
b(v)g(ersal)348 b(strategy)24897 75628 y(2)p eop
%%Page: 3 4
3 3 bop -1600 1107 a
 31733106 15549219 1710325 24997068 38350766 43087052 startTexFig
 -1600 1107 a%%BeginDocument: busstop2.ps
%!PS-Adobe-2.0 EPSF-1.2
%%Creator: idraw
%%DocumentFonts: Helvetica Times-Italic
%%Pages: 1
%%BoundingBox: 26 380 583 655
%%EndComments

%%BeginIdrawPrologue
/arrowhead {
0 begin
transform originalCTM itransform
/taily exch def
/tailx exch def
transform originalCTM itransform
/tipy exch def
/tipx exch def
/dy tipy taily sub def
/dx tipx tailx sub def
/angle dx 0 ne dy 0 ne or { dy dx atan } { 90 } ifelse def
gsave
originalCTM setmatrix
tipx tipy translate
angle rotate
newpath
arrowHeight neg arrowWidth 2 div moveto
0 0 lineto
arrowHeight neg arrowWidth 2 div neg lineto
patternNone not {
originalCTM setmatrix
/padtip arrowHeight 2 exp 0.25 arrowWidth 2 exp mul add sqrt brushWidth mul
arrowWidth div def
/padtail brushWidth 2 div def
tipx tipy translate
angle rotate
padtip 0 translate
arrowHeight padtip add padtail add arrowHeight div dup scale
arrowheadpath
ifill
} if
brushNone not {
originalCTM setmatrix
tipx tipy translate
angle rotate
arrowheadpath
istroke
} if
grestore
end
} dup 0 9 dict put def

/arrowheadpath {
newpath
arrowHeight neg arrowWidth 2 div moveto
0 0 lineto
arrowHeight neg arrowWidth 2 div neg lineto
} def

/leftarrow {
0 begin
y exch get /taily exch def
x exch get /tailx exch def
y exch get /tipy exch def
x exch get /tipx exch def
brushLeftArrow { tipx tipy tailx taily arrowhead } if
end
} dup 0 4 dict put def

/rightarrow {
0 begin
y exch get /tipy exch def
x exch get /tipx exch def
y exch get /taily exch def
x exch get /tailx exch def
brushRightArrow { tipx tipy tailx taily arrowhead } if
end
} dup 0 4 dict put def

%%EndIdrawPrologue

/arrowHeight 8 def
/arrowWidth 4 def

/IdrawDict 52 dict def
IdrawDict begin

/reencodeISO {
dup dup findfont dup length dict begin
{ 1 index /FID ne { def }{ pop pop } ifelse } forall
/Encoding ISOLatin1Encoding def
currentdict end definefont
} def

/ISOLatin1Encoding [
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/space/exclam/quotedbl/numbersign/dollar/percent/ampersand/quoteright
/parenleft/parenright/asterisk/plus/comma/minus/period/slash
/zero/one/two/three/four/five/six/seven/eight/nine/colon/semicolon
/less/equal/greater/question/at/A/B/C/D/E/F/G/H/I/J/K/L/M/N
/O/P/Q/R/S/T/U/V/W/X/Y/Z/bracketleft/backslash/bracketright
/asciicircum/underscore/quoteleft/a/b/c/d/e/f/g/h/i/j/k/l/m
/n/o/p/q/r/s/t/u/v/w/x/y/z/braceleft/bar/braceright/asciitilde
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/dotlessi/grave/acute/circumflex/tilde/macron/breve
/dotaccent/dieresis/.notdef/ring/cedilla/.notdef/hungarumlaut
/ogonek/caron/space/exclamdown/cent/sterling/currency/yen/brokenbar
/section/dieresis/copyright/ordfeminine/guillemotleft/logicalnot
/hyphen/registered/macron/degree/plusminus/twosuperior/threesuperior
/acute/mu/paragraph/periodcentered/cedilla/onesuperior/ordmasculine
/guillemotright/onequarter/onehalf/threequarters/questiondown
/Agrave/Aacute/Acircumflex/Atilde/Adieresis/Aring/AE/Ccedilla
/Egrave/Eacute/Ecircumflex/Edieresis/Igrave/Iacute/Icircumflex
/Idieresis/Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis
/multiply/Oslash/Ugrave/Uacute/Ucircumflex/Udieresis/Yacute
/Thorn/germandbls/agrave/aacute/acircumflex/atilde/adieresis
/aring/ae/ccedilla/egrave/eacute/ecircumflex/edieresis/igrave
/iacute/icircumflex/idieresis/eth/ntilde/ograve/oacute/ocircumflex
/otilde/odieresis/divide/oslash/ugrave/uacute/ucircumflex/udieresis
/yacute/thorn/ydieresis
] def
/Helvetica reencodeISO def
/Times-Italic reencodeISO def

/none null def
/numGraphicParameters 17 def
/stringLimit 65535 def

/Begin {
save
numGraphicParameters dict begin
} def

/End {
end
restore
} def

/SetB {
dup type /nulltype eq {
pop
false /brushRightArrow idef
false /brushLeftArrow idef
true /brushNone idef
} {
/brushDashOffset idef
/brushDashArray idef
0 ne /brushRightArrow idef
0 ne /brushLeftArrow idef
/brushWidth idef
false /brushNone idef
} ifelse
} def

/SetCFg {
/fgblue idef
/fggreen idef
/fgred idef
} def

/SetCBg {
/bgblue idef
/bggreen idef
/bgred idef
} def

/SetF {
/printSize idef
/printFont idef
} def

/SetP {
dup type /nulltype eq {
pop true /patternNone idef
} {
dup -1 eq {
/patternGrayLevel idef
/patternString idef
} {
/patternGrayLevel idef
} ifelse
false /patternNone idef
} ifelse
} def

/BSpl {
0 begin
storexyn
newpath
n 1 gt {
0 0 0 0 0 0 1 1 true subspline
n 2 gt {
0 0 0 0 1 1 2 2 false subspline
1 1 n 3 sub {
/i exch def
i 1 sub dup i dup i 1 add dup i 2 add dup false subspline
} for
n 3 sub dup n 2 sub dup n 1 sub dup 2 copy false subspline
} if
n 2 sub dup n 1 sub dup 2 copy 2 copy false subspline
patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if
brushNone not { istroke } if
0 0 1 1 leftarrow
n 2 sub dup n 1 sub dup rightarrow
} if
end
} dup 0 4 dict put def

/Circ {
newpath
0 360 arc
closepath
patternNone not { ifill } if
brushNone not { istroke } if
} def

/CBSpl {
0 begin
dup 2 gt {
storexyn
newpath
n 1 sub dup 0 0 1 1 2 2 true subspline
1 1 n 3 sub {
/i exch def
i 1 sub dup i dup i 1 add dup i 2 add dup false subspline
} for
n 3 sub dup n 2 sub dup n 1 sub dup 0 0 false subspline
n 2 sub dup n 1 sub dup 0 0 1 1 false subspline
patternNone not { ifill } if
brushNone not { istroke } if
} {
Poly
} ifelse
end
} dup 0 4 dict put def

/Elli {
0 begin
newpath
4 2 roll
translate
scale
0 0 1 0 360 arc
closepath
patternNone not { ifill } if
brushNone not { istroke } if
end
} dup 0 1 dict put def

/Line {
0 begin
2 storexyn
newpath
x 0 get y 0 get moveto
x 1 get y 1 get lineto
brushNone not { istroke } if
0 0 1 1 leftarrow
0 0 1 1 rightarrow
end
} dup 0 4 dict put def

/MLine {
0 begin
storexyn
newpath
n 1 gt {
x 0 get y 0 get moveto
1 1 n 1 sub {
/i exch def
x i get y i get lineto
} for
patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if
brushNone not { istroke } if
0 0 1 1 leftarrow
n 2 sub dup n 1 sub dup rightarrow
} if
end
} dup 0 4 dict put def

/Poly {
3 1 roll
newpath
moveto
-1 add
{ lineto } repeat
closepath
patternNone not { ifill } if
brushNone not { istroke } if
} def

/Rect {
0 begin
/t exch def
/r exch def
/b exch def
/l exch def
newpath
l b moveto
l t lineto
r t lineto
r b lineto
closepath
patternNone not { ifill } if
brushNone not { istroke } if
end
} dup 0 4 dict put def

/Text {
ishow
} def

/idef {
dup where { pop pop pop } { exch def } ifelse
} def

/ifill {
0 begin
gsave
patternGrayLevel -1 ne {
fgred bgred fgred sub patternGrayLevel mul add
fggreen bggreen fggreen sub patternGrayLevel mul add
fgblue bgblue fgblue sub patternGrayLevel mul add setrgbcolor
eofill
} {
eoclip
originalCTM setmatrix
pathbbox /t exch def /r exch def /b exch def /l exch def
/w r l sub ceiling cvi def
/h t b sub ceiling cvi def
/imageByteWidth w 8 div ceiling cvi def
/imageHeight h def
bgred bggreen bgblue setrgbcolor
eofill
fgred fggreen fgblue setrgbcolor
w 0 gt h 0 gt and {
l w add b translate w neg h scale
w h true [w 0 0 h neg 0 h] { patternproc } imagemask
} if
} ifelse
grestore
end
} dup 0 8 dict put def

/istroke {
gsave
brushDashOffset -1 eq {
[] 0 setdash
1 setgray
} {
brushDashArray brushDashOffset setdash
fgred fggreen fgblue setrgbcolor
} ifelse
brushWidth setlinewidth
originalCTM setmatrix
stroke
grestore
} def

/ishow {
0 begin
gsave
fgred fggreen fgblue setrgbcolor
/fontDict printFont printSize scalefont dup setfont def
/descender fontDict begin 0 [FontBBox] 1 get FontMatrix end
transform exch pop def
/vertoffset 1 printSize sub descender sub def {
0 vertoffset moveto show
/vertoffset vertoffset printSize sub def
} forall
grestore
end
} dup 0 3 dict put def
/patternproc {
0 begin
/patternByteLength patternString length def
/patternHeight patternByteLength 8 mul sqrt cvi def
/patternWidth patternHeight def
/patternByteWidth patternWidth 8 idiv def
/imageByteMaxLength imageByteWidth imageHeight mul
stringLimit patternByteWidth sub min def
/imageMaxHeight imageByteMaxLength imageByteWidth idiv patternHeight idiv
patternHeight mul patternHeight max def
/imageHeight imageHeight imageMaxHeight sub store
/imageString imageByteWidth imageMaxHeight mul patternByteWidth add string def
0 1 imageMaxHeight 1 sub {
/y exch def
/patternRow y patternByteWidth mul patternByteLength mod def
/patternRowString patternString patternRow patternByteWidth getinterval def
/imageRow y imageByteWidth mul def
0 patternByteWidth imageByteWidth 1 sub {
/x exch def
imageString imageRow x add patternRowString putinterval
} for
} for
imageString
end
} dup 0 12 dict put def

/min {
dup 3 2 roll dup 4 3 roll lt { exch } if pop
} def

/max {
dup 3 2 roll dup 4 3 roll gt { exch } if pop
} def

/midpoint {
0 begin
/y1 exch def
/x1 exch def
/y0 exch def
/x0 exch def
x0 x1 add 2 div
y0 y1 add 2 div
end
} dup 0 4 dict put def

/thirdpoint {
0 begin
/y1 exch def
/x1 exch def
/y0 exch def
/x0 exch def
x0 2 mul x1 add 3 div
y0 2 mul y1 add 3 div
end
} dup 0 4 dict put def

/subspline {
0 begin
/movetoNeeded exch def
y exch get /y3 exch def
x exch get /x3 exch def
y exch get /y2 exch def
x exch get /x2 exch def
y exch get /y1 exch def
x exch get /x1 exch def
y exch get /y0 exch def
x exch get /x0 exch def
x1 y1 x2 y2 thirdpoint
/p1y exch def
/p1x exch def
x2 y2 x1 y1 thirdpoint
/p2y exch def
/p2x exch def
x1 y1 x0 y0 thirdpoint
p1x p1y midpoint
/p0y exch def
/p0x exch def
x2 y2 x3 y3 thirdpoint
p2x p2y midpoint
/p3y exch def
/p3x exch def
movetoNeeded { p0x p0y moveto } if
p1x p1y p2x p2y p3x p3y curveto
end
} dup 0 17 dict put def

/storexyn {
/n exch def
/y n array def
/x n array def
n 1 sub -1 0 {
/i exch def
y i 3 2 roll put
x i 3 2 roll put
} for
} def

/SSten {
fgred fggreen fgblue setrgbcolor
dup true exch 1 0 0 -1 0 6 -1 roll matrix astore
} def

/FSten {
dup 3 -1 roll dup 4 1 roll exch
newpath
0 0 moveto
dup 0 exch lineto
exch dup 3 1 roll exch lineto
0 lineto
closepath
bgred bggreen bgblue setrgbcolor
eofill
SSten
} def

/Rast {
exch dup 3 1 roll 1 0 0 -1 0 6 -1 roll matrix astore
} def

%%EndProlog

%I Idraw 12 Grid 8 8 

%%Page: 1 1

Begin
%I b u
%I cfg u
%I cbg u
%I f u
%I p u
%I t
[ 0.796717 0 0 0.796717 0 0 ] concat
/originalCTM matrix currentmatrix def

Begin %I BSpl
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 21 498.5 ] concat
%I 8
716 396
709 377
606 365
476 429
469 456
470 504
574 577
687 564
8 BSpl
%I 2
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0.75 SetP
%I t
[ 0.5 -0 -0 0.5 222 498.5 ] concat
%I 4
622 395
888 396
888 435
622 435
4 Poly
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 21 498.5 ] concat
%I 4
484 450
686 450
686 490
484 490
4 Poly
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0.75 SetP
%I t
[ 0.5 -0 -0 0.5 21 498.5 ] concat
%I 4
657 396
911 396
911 436
657 436
4 Poly
End

Begin %I BSpl
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 -0 -0 1 -131.5 225.5 ] concat
%I 8
291 422
288 407
304 387
375 379
469 382
580 382
626 411
631 389
8 BSpl
%I 1
End

Begin %I Rect
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0.75 SetP
%I t
[ 0.5 0 0 0.5 273.5 336.5 ] concat
%I
457 289 553 329 Rect
End

Begin %I Rect
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0.75 SetP
%I t
[ 0.5 0 0 0.5 168.5 359.5 ] concat
%I
601 337 849 377 Rect
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 473 543 ] concat
%I
[
(NonEmptyPersonList)
] Text
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0.75 SetP
%I t
[ 0.5 0 0 0.5 180.5 259.5 ] concat
%I 6
617 705
729 705
761 673
729 641
617 641
585 673
6 Poly
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 489 599 ] concat
%I
[
(PersonList)
] Text
End

Begin %I Rect
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0.75 SetP
%I t
[ 0.5 0 0 0.5 192.5 471.5 ] concat
%I
297 657 425 697 Rect
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 345 815 ] concat
%I
[
(BusRoute)
] Text
End

Begin %I Pict
%I b u
%I cfg u
%I cbg u
%I f u
%I p u
%I t
[ 1 0 0 1 41 -196 ] concat

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 576 779 ] concat
%I
[
(EmptyPersonList)
] Text
End

Begin %I Rect
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 143.5 571.5 ] concat
%I
857 385 1057 425 Rect
End

End %I eop

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 506 496 ] concat
%I
[
(Person)
] Text
End

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 -0 -0 1 -131.5 225.5 ] concat
%I
660 302 660 277 Line
%I 1
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 487.5 267.5 ] concat
%I 4
102 610
94 602
102 594
110 602
4 Poly
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 536 300 ] concat
%I 4
102 610
94 602
102 594
110 602
4 Poly
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 266 810 ] concat
%I
[
(buses)
] Text
End

Begin %I BSpl
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 -0 -0 1 -131.5 225.5 ] concat
%I 6
602 303
590 293
566 297
566 332
565 365
605 372
6 BSpl
%I 1
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 538 526 ] concat
%I
[
(first)
] Text
End

Begin %I Rect
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0.75 SetP
%I t
[ 0.5 0 0 0.5 248.5 399.5 ] concat
%I
601 497 713 537 Rect
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0.75 SetP
%I t
[ 0.5 0 0 0.5 240.5 427.5 ] concat
%I 6
617 705
729 705
761 673
729 641
617 641
585 673
6 Poly
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 586 458 ] concat
%I 4
102 610
94 602
102 594
110 602
4 Poly
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 553 663 ] concat
%I
[
(BusStop)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 545 767 ] concat
%I
[
(BusStopList)
] Text
End

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 -0 -0 1 -75.5 225.5 ] concat
%I
656 471 656 444 Line
%I 1
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 539 433 ] concat
%I 4
102 610
94 602
102 594
110 602
4 Poly
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 594 690 ] concat
%I
[
(first)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 509.5 686.5 ] concat
%I
[
(rest)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 402 538 ] concat
%I
[
(rest)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 547 634 ] concat
%I
[
(waiting)
] Text
End

Begin %I Pict
%I b u
%I cfg u
%I cbg u
%I f u
%I p u
%I t
[ 1 0 0 1 -144 -119 ] concat

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 184 851 ] concat
%I
[
(EmptyBusList)
] Text
End

Begin %I Rect
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 143.5 571.5 ] concat
%I
73 529 241 569 Rect
End

End %I eop

Begin %I Pict
%I b u
%I cfg u
%I cbg u
%I f u
%I p u
%I t
[ 1 0 0 1 -183 -132 ] concat

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 296 835 ] concat
%I
[
(NonEmptyBusList)
] Text
End

Begin %I Rect
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 143.5 571.5 ] concat
%I
297 497 513 537 Rect
End

End %I eop

Begin %I Pict
%I b u
%I cfg u
%I cbg u
%I f u
%I p u
%I t
[ 1 0 0 1 -151 -132 ] concat

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 296 795 ] concat
%I
[
(Bus)
] Text
End

Begin %I Rect
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 143.5 571.5 ] concat
%I
297 417 361 457 Rect
End

End %I eop

Begin %I Pict
%I b u
%I cfg u
%I cbg u
%I f u
%I p u
%I t
[ 1 0 0 1 -159 -116 ] concat

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 296 879 ] concat
%I
[
(BusList)
] Text
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 -0 -0 0.5 -16.5 539.5 ] concat
%I 6
617 705
729 705
761 673
729 641
617 641
585 673
6 Poly
End

End %I eop

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 0 0 1 -171.5 225.5 ] concat
%I
334 462 334 444 Line
%I 1
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 0 0 0.5 121 428 ] concat
%I 4
102 610
94 602
102 594
110 602
4 Poly
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 0 0 0.5 45 457 ] concat
%I 4
102 610
94 602
102 594
110 602
4 Poly
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 178 682 ] concat
%I
[
(first)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 221 679 ] concat
%I
[
(rest)
] Text
End

Begin %I Rect
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0.75 SetP
%I t
[ 0.5 0 0 0.5 64.5 399.5 ] concat
%I
601 497 713 537 Rect
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0.75 SetP
%I t
[ 0.5 0 0 0.5 56.5 427.5 ] concat
%I 6
617 705
729 705
761 673
729 641
617 641
585 673
6 Poly
End

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 0 0 1 -259.5 225.5 ] concat
%I
656 471 656 444 Line
%I 1
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 0 0 0.5 355 433 ] concat
%I 4
102 610
94 602
102 594
110 602
4 Poly
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 410 690 ] concat
%I
[
(first)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 302 683.5 ] concat
%I
[
(rest)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 362 768 ] concat
%I
[
(VillageList)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 354 712 ] concat
%I
[
(NonEmptyVillageList)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 370 664 ] concat
%I
[
(Village)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 399 798 ] concat
%I
[
(villages)
] Text
End

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 -0 -0 1 -131.5 225.5 ] concat
%I
473 575 321 551 Line
%I 1
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 410 645 ] concat
%I
[
(busStops)
] Text
End

Begin %I BSpl
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 -0 -0 1 -131.5 225.5 ] concat
%I 5
716 422
715 413
664 414
664 410
664 389
5 BSpl
%I 1
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 537 711 ] concat
%I
[
(NonEmptyBusStopList)
] Text
End

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 88 498.5 ] concat
%I
597 604 597 568 Line
%I 2
End

Begin %I BSpl
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 88 498.5 ] concat
%I 7
243 379
253 358
295 374
331 460
313 516
283 532
237 524
7 BSpl
%I 2
End

Begin %I Line
%I b 65535
3 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 222 498.5 ] concat
%I
798 530 825 498 Line
%I 2
End

Begin %I Line
%I b 65535
3 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 222 498.5 ] concat
%I
713 498 713 441 Line
%I 2
End

Begin %I Line
%I b 65535
3 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 21 498.5 ] concat
%I
281 491 281 428 Line
%I 2
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 267.5 739 ] concat
%I
[
(EmptyVillageList)
] Text
End

Begin %I BSpl
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 222 498.5 ] concat
%I 6
656 395
651 354
559 410
549 474
557 522
621 532
6 BSpl
%I 2
End

Begin %I BSpl
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 -0 -0 1 -46 292 ] concat
%I 8
439 356
443 337
471 334
522 340
537 377
533 504
589 520
596 490
8 BSpl
%I 1
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.5 0 0 0.5 285 463 ] concat
%I 4
102 610
94 602
102 594
110 602
4 Poly
End

Begin %I Line
%I b 65535
3 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 29 477.5 ] concat
%I
176 565 118 526 Line
%I 2
End

Begin %I Line
%I b 65535
3 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 29 477.5 ] concat
%I
731 540 731 492 Line
%I 2
End

Begin %I Line
%I b 65535
3 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 29 477.5 ] concat
%I
640 572 619 542 Line
%I 2
End

Begin %I Line
%I b 65535
3 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 29 477.5 ] concat
%I
997 204 997 151 Line
%I 2
End

Begin %I Line
%I b 65535
3 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 0.5 -0 -0 0.5 230 477.5 ] concat
%I
662 236 754 221 Line
%I 2
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-times-medium-i-normal-*-14-*-*-*-*-*-*-*
Times-Italic 14 SetF
%I t
[ 1 0 0 1 209 624 ] concat
%I
[
(passengers)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-*
Helvetica 12 SetF
%I t
[ 1 0 0 1 620 744 ] concat
%I
[
(EmptyBusStopList)
] Text
End

Begin %I Poly
%I b 65535
1 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
none SetP %I p n
%I t
[ 0.599539 -0 -0 0.599539 25.1806 591.145 ] concat
%I 4
979 230
1174 230
1174 263
979 263
4 Poly
End

End %I eop

showpage

%%Trailer

end

%%EndDocument

 endTexFig
 13222 30134 a Fv(Figure)404 b(2:)539 b Ft(Evolve)-62
b(d)431 b(bus)i(simulation)e(class)h(gr)-62 b(aph.)-1600
33801 y Fv(m)-34 b(ust)408 b(b)34 b(e)407 b(correct)f(for)i(the)f(new)h
(class)f(graph.)548 b(When)407 b(a)g(class)g(graph)h(is)f(c)-34
b(hanged,)409 b(it)e(is)g(imp)34 b(ortan)-34 b(t)408
b(to)f(c)-34 b(hec)g(k)407 b(the)-1600 35457 y(correctness)469
b(of)h(all)f(tra)-34 b(v)g(ersal)469 b(strategies)g(that)i(dep)34
b(end)470 b(on)g(that)h(class)e(graph.)735 b(Sometimes)470
b(it)g(is)f(necessary)g(to)-1600 37113 y(re\014ne)402
b(the)h(strategies)f(to)g(mak)-34 b(e)402 b(them)g(correct)g(in)g(the)g
(new)h(class)e(graph,)i(but)g(this)g(is)f(easier)f(than)i(up)34
b(dating)404 b(all)-1600 38769 y(tra)-34 b(v)g(ersal)404
b(metho)34 b(ds)405 b(man)-34 b(ually)404 b([Lie96)o(].)282
40985 y(The)339 b(actual)g(w)-34 b(ork)339 b(on)g(the)h(ob)67
b(jects)339 b(is)g(done)g(b)-34 b(y)340 b(metho)34 b(ds)339
b(on)g(a)g Ft(visitor)467 b Fv(ob)67 b(ject:)507 b(these)339
b(are)f(metho)34 b(ds)340 b(that)g(can)-1600 42641 y(b)34
b(e)354 b(asso)34 b(ciated)354 b(with)h(classes)f(or)g(edges)g(in)g
(the)h(class)f(graph,)364 b(sp)34 b(ecifying)354 b(what)i(to)e(do)h
(when)g(the)g(tra)-34 b(v)g(ersal)354 b(arriv)-34 b(es)-1600
44297 y(at)370 b(an)g(ob)67 b(ject)371 b(of)f(a)g(particular)f(t)-34
b(yp)34 b(e)370 b(or)g(dereferences)e(a)i(particular)g(\014eld.)527
b(Visitor)369 b(ob)67 b(jects)371 b(are)e(named)i(after)e(the)-1600
45953 y(Visitor)452 b(design)h(pattern)g([GHJV95])f(but)i(are)e(m)-34
b(uc)g(h)453 b(simpler)f(than)i(visitor)d(ob)67 b(jects)454
b(describ)34 b(ed)452 b(b)-34 b(y)452 b(the)h(Visitor)-1600
47609 y(design)476 b(pattern,)495 b(since)476 b(none)g(of)g(the)h
(sca\013olding)f(is)g(needed|b)-34 b(y)477 b(sca\013olding)f(w)-34
b(e)476 b(mean)g(writing)h(an)f(abstract)-1600 49265
y(visitor)404 b(class)f(that)j(duplicates)e(m)-34 b(uc)g(h)405
b(information)h(from)e(the)g(class)g(graph.)282 51482
y(Strategies)493 b(e\013ectiv)-34 b(ely)491 b(\014lter)i(out)h(the)f
(noise)g(in)f(the)i(class)e(graph)i(whic)-34 b(h)493
b(is)g(irrelev)-67 b(an)-34 b(t)492 b(to)h(the)g(implemen-)-1600
53138 y(tation)447 b(of)g(the)f(curren)-34 b(t)447 b(task.)664
b(F)-101 b(or)446 b(the)h(class)f(graph)g(in)g(Figure)g(2,)457
b(the)446 b(ab)34 b(o)-34 b(v)g(e)446 b(strategy)-101
b(,)457 b(whic)-34 b(h)447 b(men)-34 b(tions)447 b(only)-1600
54794 y(three)556 b(classes,)594 b(replaces)555 b(metho)34
b(ds)558 b(for)e(ten)h(classes:)842 b Fr(BusRoute,)594
b(VillageList,)e(NonEmpt)-34 b(yVillageList,)591 b(Village,)-1600
56450 y(BusStopList,)403 b(NonEmpt)-34 b(yBusStopList,)402
b(BusStop,)j(P)-34 b(ersonList,)402 b(NonEmpt)-34 b(yP)g(ersonList,)403
b(P)-34 b(erson)p Fv(.)282 58666 y(T)-101 b(o)396 b(sho)-34
b(w)397 b(ho)-34 b(w)397 b(to)f(program)f(with)i(strategies,)g(w)-34
b(e)396 b(complete)f(the)h(Ja)-34 b(v)-67 b(a)396 b(program)f(\(using)i
(the)f(DJ)g(library\))f(of)-1600 60322 y(\014nding)405
b(all)f(p)34 b(eople)404 b(w)-34 b(aiting)405 b(at)f(an)-34
b(y)405 b(bus)g(stop)g(on)f(a)g(particular)g(bus)h(route:)1430
63534 y Fq(//)637 b(in)g(class)i(BusRoute:)1430 65190
y(static)g(ClassGraph)h(cg)d(=)g(new)g(ClassGraph\(\);)1430
66846 y(static)i(Strategy)g(waiting)g(=)e(new)g(Strategy\("from)k
(BusRoute)f(via)d(BusStop)i(to)e(Person"\);)1430 68502
y(void)h(printWaitingPersons\(\))644 b({)2703 70158 y
(cg.traverse\(this,)e(waiting,)e(new)d(PrintVisitor\(\)\);)1430
71814 y(})24897 75628 y Fv(3)p eop
%%Page: 4 5
4 4 bop -1600 2325 a Fv(The)411 b(program)g(ab)34 b(o)-34
b(v)g(e)410 b(de\014nes)i(a)e(metho)34 b(d)411 b(called)f
Fr(p)-34 b(rintW)g(aitingP)g(ersons)411 b Fv(for)g(the)g(class)f
Fr(BusRoute)p Fv(.)557 b(This)411 b(metho)34 b(d)-1600
3981 y(will)471 b(execute)g(the)h(tra)-34 b(v)g(ersal)471
b(sp)34 b(eci\014ed)472 b(b)-34 b(y)472 b(the)g(strategy)g(and)g(prin)
-34 b(t)472 b(the)g(ob)67 b(ject)473 b(of)f(class)f Fr(BusRoute)g
Fv(using)h(the)-1600 5637 y(visitor)374 b(class)h Fr(PrintVisito)-34
b(r)p Fv(.)528 b(Note)375 b(that)h(the)f(de\014nition)h(of)g
Fr(p)-34 b(rintW)g(aitingP)g(ersons)375 b Fv(w)-34 b(orks)375
b(without)i(an)-34 b(y)375 b(c)-34 b(hange)376 b(for)-1600
7293 y(b)34 b(oth)405 b(class)f(graphs,)g(whic)-34 b(h)405
b(is)f(the)h(reason)f(for)g(calling)f(it)i(an)f Ft(adaptive)430
b(metho)-62 b(d)403 b Fv([LOO01)n(].)282 9509 y(Notice)316
b(that)i(the)f(adaptiv)-34 b(e)317 b(metho)34 b(d)318
b(is)e(expressed)g(in)h(plain)g(Ja)-34 b(v)-67 b(a)316
b(using)h(the)g(DJ)g(library)e(of)i(whic)-34 b(h)318
b(w)-34 b(e)317 b(use)f(the)-1600 11165 y(classes)377
b Fr(ClassGraph)h Fv(and)h Fr(Visito)-34 b(r)p Fv(,)381
b(the)d(sup)34 b(erclass)377 b(of)h(all)f(visitor)g(classes)g(\(suc)-34
b(h)379 b(as)e Fr(PrintVisito)-34 b(r)p Fv(\).)529 b(A)378
b Fr(ClassGraph)p Fv(-)-1600 12821 y(ob)67 b(ject)454
b(is)e(a)h(graph)h(whose)f(no)34 b(des)453 b(are)g(classes)f(and)i
(whose)f(edges)g(are)f Ft(is-a)544 b Fv(and)454 b Ft(has-a)544
b Fv(relationships)453 b(b)34 b(et)-34 b(w)g(een)-1600
14477 y(classes.)679 b(Class)451 b Fr(ClassGraph)h Fv(pro)-34
b(vides)452 b(metho)34 b(ds)452 b(to)f(create)f(and)i(main)-34
b(tain)452 b(a)g(class)e(graph.)680 b(The)452 b(simplest)f(w)-34
b(a)g(y)-1600 16133 y(to)532 b(create)f(a)h Fr(ClassGraph)p
Fv(-ob)67 b(ject)534 b(is)e(to)g(call)f(the)h(constructor)h
Fr(ClassGraph\(\))g Fv(without)h(argumen)-34 b(ts)533
b(whic)-34 b(h)532 b(will)-1600 17789 y(create)462 b(the)i(class)f
(graph)g(using)h(Ja)-34 b(v)-67 b(a)463 b(re\015ection)g(b)-34
b(y)463 b(taking)g(all)g(classes)f(in)h(the)h(default)g(pac)-34
b(k)-67 b(age.)715 b(A)463 b(tra)-34 b(v)g(ersal)-1600
19445 y(strategy)427 b(ma)-34 b(y)426 b(b)34 b(e)426
b(applied)h(to)g(b)34 b(oth)427 b(a)f Fr(ClassGraph)p
Fv(-ob)67 b(ject)428 b(and)g(a)e(Ja)-34 b(v)-67 b(a)426
b(ob)67 b(ject.)606 b(F)-101 b(rom)427 b(the)f(p)34 b(oin)-34
b(t)428 b(of)e(view)g(of)h(a)-1600 21101 y Fr(ClassGraph)p
Fv(-ob)67 b(ject,)367 b(a)355 b(tra)-34 b(v)g(ersal)356
b(strategy)f(is)h(a)f(subgraph)i(of)f(the)g(transitiv)-34
b(e)356 b(closure)e(of)i(the)g Fr(ClassGraph)p Fv(-ob)67
b(ject.)-1600 22757 y(When)418 b(it)g(is)f(applied)h(to)g(a)g(class)g
(graph)g(it)g(selects)f(a)h(subset)g(of)g(the)h(paths)g(in)e(the)i
(class)e(graph.)580 b(If)418 b(applied)g(to)g(a)-1600
24413 y(Ja)-34 b(v)-67 b(a)404 b(ob)67 b(ject,)405 b(a)f(tra)-34
b(v)g(ersal)404 b(strategy)g(de\014nes)h(a)f(subgraph)h(of)g(the)f(ob)
67 b(ject)405 b(graph)g(represen)-34 b(ting)405 b(the)f(Ja)-34
b(v)-67 b(a)404 b(ob)67 b(ject.)282 26629 y(In)463 b(this)g(implemen)
-34 b(tation)464 b(of)f(adaptiv)-34 b(e)464 b(programming)f(with)h(DJ)e
(the)i(class)e(graph)i(and)f(the)h(tra)-34 b(v)g(ersals)462
b(are)-1600 28285 y(computed)566 b(dynamically)-101 b(.)1020
b(In)564 b(other)h(implemen)-34 b(tations)566 b(of)f(adaptiv)-34
b(e)566 b(programming)f(\(see)g(Section)g(7.2\),)604
b(the)-1600 29941 y(tra)-34 b(v)g(ersals)404 b(are)g(computed)h
(statically)-101 b(.)282 32157 y(T)g(o)431 b(sho)-34
b(w)433 b(the)e(details)g(of)h(visitors,)437 b(w)-34
b(e)431 b(write)g(a)g(Ja)-34 b(v)-67 b(a)431 b(metho)34
b(d)432 b(that)g(coun)-34 b(ts)433 b(\(instead)f(of)f(prin)-34
b(ts\))433 b(all)d(p)34 b(eople)-1600 33813 y(w)-34 b(aiting)405
b(at)f(an)-34 b(y)405 b(bus)f(stop)h(on)f(a)g(particular)g(bus)h
(route.)539 b(Because)403 b(the)h(tra)-34 b(v)g(ersals)404
b(for)g Fr(p)-34 b(rintW)g(aitingP)g(ersons)404 b Fv(and)-1600
35469 y Fr(countW)-34 b(aitingP)g(ersons)335 b Fv(are)g(iden)-34
b(tical,)349 b(w)-34 b(e)336 b(reuse)f(the)h(same)f Fr(w)-34
b(aiting)336 b Fv(tra)-34 b(v)g(ersal)335 b(strategy)-101
b(.)516 b(W)-101 b(e)335 b(also)g(reuse)g(the)h(class)-1600
37125 y(graph)405 b Fr(cg)p Fv(:)2703 40338 y Fq(//)637
b(in)g(class)h(BusRoute:)2703 41994 y(int)f(countWaitingPersons\(\))644
b({)3976 43650 y(Integer)639 b(result)f(=)f(\(Integer\))i
(cg.traverse\(this,)k(waiting,)c(new)e(CountVisitor\(\)\);)3976
45306 y(return)h(result.intValue\(\);)2703 46962 y(})1430
50274 y(class)g(CountVisitor)j(extends)e(Visitor)g({)2703
51930 y(int)e(c;)2703 53586 y(public)i(void)e(start\(\))i({)e(c)g(=)f
(0;)h(})2703 55242 y(public)i(void)e(before\(Person)k(p\))c({)g(c++;)h
(})2703 56898 y(public)h(Object)f(getReturnValue\(\))k({)637
b(return)h(new)g(Integer\(c\);)i(})1430 58554 y(})-1600
61766 y Fv(Class)450 b Fr(Visito)-34 b(r)449 b Fv(has)h(a)g(simple)g
(in)-34 b(terface:)630 b(with)451 b(the)f Fr(sta)-34
b(rt)450 b Fv(metho)34 b(d)450 b(w)-34 b(e)451 b(sa)-34
b(y)450 b(what)h(needs)f(to)g(b)34 b(e)450 b(done)g(b)34
b(efore)449 b(the)-1600 63422 y(tra)-34 b(v)g(ersal)509
b(starts.)854 b(With)509 b(the)h Fr(getReturnV)-34 b(alue)509
b Fv(metho)34 b(d)509 b(w)-34 b(e)510 b(express)e(what)j(needs)e(to)g
(b)34 b(e)509 b(returned)h(when)f(the)-1600 65078 y(tra)-34
b(v)g(ersal)349 b(completes.)520 b(With)350 b(a)f Fr(b)34
b(efo)-34 b(re)350 b Fv(metho)34 b(d)350 b(w)-34 b(e)349
b(express)g(what)i(needs)e(to)h(b)34 b(e)349 b(done)h(b)34
b(efore)349 b(w)-34 b(e)349 b(visit)g(an)h(ob)67 b(ject)-1600
66734 y(of)376 b(a)g(sp)34 b(eci\014c)375 b(class,)380
b(sp)34 b(eci\014ed)376 b(b)-34 b(y)376 b(the)g(metho)34
b(d's)376 b(argumen)-34 b(t)377 b(t)-34 b(yp)34 b(e.)529
b(There)376 b(are)f(also)h Fr(after)g Fv(and)g Fr(a)-34
b(round)377 b Fv(metho)34 b(ds;)-1600 68390 y(the)415
b(complete)f(API)f(is)h(do)34 b(cumen)-34 b(ted)416 b(in)e([Lieb)o(].)
568 b(The)415 b Fr(b)34 b(efo)-34 b(re)p Fv(,)416 b Fr(after)p
Fv(,)h(and)e Fr(a)-34 b(round)416 b Fv(metho)34 b(ds)415
b(that)g(are)f(de\014ned)h(in)-1600 70046 y(a)404 b(visitor)g(class)f
(are)h(in)-34 b(v)g(ok)g(ed)405 b(using)f(the)h(Ja)-34
b(v)-67 b(a)404 b(Re\015ection)g(API.)24897 75628 y(4)p
eop
%%Page: 5 6
5 5 bop -1600 2325 a Fw(1.3)1495 b(New)499 b(Con)-42
b(tributions)-1600 5324 y Fv(The)485 b(con)-34 b(tributions)486
b(of)e(this)h(pap)34 b(er)484 b(are)g(three-fold:)699
b(an)485 b(extension)f(to)h(the)g(tra)-34 b(v)g(ersal)484
b(sp)34 b(eci\014cation)484 b(language,)-1600 6980 y(a)474
b(p)34 b(olynomial-time)473 b(compilation)h(algorithm)g(for)g(the)g
(extended)h(language)f(that)h(is)e(simpler)h(than)h(our)f(earlier)-1600
8636 y(algorithm,)342 b(and)329 b(a)e(lo)-34 b(w)g(er)327
b(b)34 b(ound)329 b(result)e(whic)-34 b(h)328 b(explains)f(the)h
(shortcomings)g(of)f(the)h(previous)f(algorithms.)513
b(More)-1600 10292 y(sp)34 b(eci\014cally)-101 b(,)390
b(w)-34 b(e)390 b(allo)-34 b(w)389 b(the)h(underlying)f(sp)34
b(eci\014cation)389 b(of)g(a)g(tra)-34 b(v)g(ersal)389
b(to)h(ha)-34 b(v)g(e)389 b(an)-34 b(y)390 b(top)34 b(ology)-101
b(,)392 b(generalizing)387 b(the)-1600 11948 y(series-parallel)371
b(and)j(tree)e(top)34 b(ologies)372 b(considered)h(previously)-101
b(,)378 b(and)c(w)-34 b(e)373 b(allo)-34 b(w)373 b(the)g(use)g(of)g(a)g
(name)g(map)g(b)34 b(et)-34 b(w)g(een)-1600 13604 y(no)34
b(des)500 b(in)f(the)h(strategy)g(graph)g(and)g(those)g(in)g(the)g
(class)f(graph.)825 b(This)500 b(name)g(map)g(supp)34
b(orts)500 b(the)g(option)h(for)-1600 15260 y(di\013eren)-34
b(t)474 b(no)34 b(des)475 b(in)f(the)g(strategy)g(graph)h(to)f(b)34
b(e)474 b(mapp)34 b(ed)475 b(to)f(the)h(same)f(no)34
b(de)474 b(in)g(the)g(class)g(graph.)749 b(Section)474
b(9)-1600 16916 y(pro)-34 b(vides)404 b(a)g(more)g(detailed)g
(comparison)h(of)f(tra)-34 b(v)g(ersal)404 b(strategies)g(and)h(tra)-34
b(v)g(ersal)404 b(sp)34 b(eci\014cations.)282 19132 y(The)411
b(generalization)f(of)h(our)f(previous)g(algorithm)h(to)g(a)f(larger)g
(class)g(of)h(graphs)g(w)-34 b(as)411 b(not)h(our)e(primary)g(goal)
-1600 20788 y(for)419 b(coming)g(up)h(with)g(a)e(b)34
b(etter)419 b(algorithm.)584 b(It)419 b(happ)34 b(ened)420
b(as)f(a)g(side-e\013ect:)567 b(as)419 b(w)-34 b(e)420
b(made)f(the)g(algorithm)g(more)-1600 22444 y(e\016cien)-34
b(t)453 b(and)h(usable)g(for)f(a)g(larger)f(class)h(of)h
(series-parallel)d(graph/class)j(graph)g(com)-34 b(binations,)466
b(the)454 b(resulting)-1600 24100 y(algorithm)404 b(also)g(naturally)g
(w)-34 b(ork)g(ed)405 b(for)f(an)-34 b(y)405 b(kind)f(of)h(graph.)282
26316 y(Our)466 b(new)h(p)34 b(olynomial-time)466 b(algorithm)h(presen)
-34 b(ted)467 b(in)f(Section)h(5)g(has)g(the)g(b)34 b(ene\014cial)465
b(prop)34 b(ert)-34 b(y)467 b(that)h(it)e(is)-1600 27972
y(simpler)446 b(and)h(easier)e(to)i(understand.)666 b(Our)446
b(earlier)f(algorithm)h(required)g(an)g(unin)-34 b(tuitiv)g(e)448
b(c)-34 b(hec)g(k)446 b(for)h(the)f(short-)-1600 29628
y(cut)503 b(and)h(zig-zag)e(conditions.)836 b(Those)504
b(t)-34 b(w)g(o)504 b(conditions)g(had)f(to)h(b)34 b(e)502
b(c)-34 b(hec)g(k)g(ed)504 b(to)f(mak)-34 b(e)503 b(sure)g(that)h(the)f
(tra)-34 b(v)g(er-)-1600 31284 y(sal)470 b(is)g(correct.)735
b(The)471 b(short-cut)g(and)g(zig-zag)e(conditions)i(also)f(prohibited)
h(man)-34 b(y)470 b(series-parallel)f(graph/class)-1600
32940 y(graph)539 b(com)-34 b(binations.)943 b(W)-101
b(e)538 b(notice)g(that)i(this)e(pap)34 b(er)539 b(is)f(related)g(to)h
(t)-34 b(w)g(o)540 b(applications)f(of)f(P)-34 b(oly)g(a's)539
b(in)-34 b(v)g(en)g(tors)-1600 34596 y(parado)g(x[P)g(ol49)q(]:)-118
37808 y(1.)605 b(Although)396 b(w)-34 b(e)395 b(solv)-34
b(e)395 b(a)f(more)g(general)g(algorithmic)h(problem)f(at)h(the)g
(programming)g(to)34 b(ol)395 b(lev)-34 b(el,)395 b(the)g(algo-)1430
39464 y(rithm)405 b(b)34 b(ecomes)403 b(simpler.)-118
42117 y(2.)605 b(The)377 b(algorithm)g(supp)34 b(orts)377
b(b)34 b(etter)377 b(adaptiv)-34 b(e)377 b(programming)g(whic)-34
b(h)377 b(is)f(ab)34 b(out)377 b(solving)f(problems)h(for)f(more)1430
43773 y(general)599 b(data)h(structures)f(than)h(the)g(one)f
(originally)f(giv)-34 b(en,)647 b(leading)599 b(to)h(simpler)e
(programs)h(\([Lie96],)1430 45429 y(Section)405 b(4.1.1\).)282
48641 y(The)539 b(compilation)f(algorithm)h(generates)f(co)34
b(de)538 b(whose)h(running)g(time)f(ma)-34 b(y)539 b(b)34
b(e)538 b(sligh)-34 b(tly)538 b(w)-34 b(orse)539 b(than)h(the)-1600
50297 y(running)424 b(time)f(of)g(the)g(co)34 b(de)422
b(generated)h(b)-34 b(y)423 b(previous)g(compilation)g(algorithms)g
(\(when)h(they)f(apply\),)428 b(since)422 b(the)-1600
51953 y(previous)457 b(algorithm)f(generated)h(tra)-34
b(v)g(ersal)457 b(metho)34 b(ds)457 b(whic)-34 b(h)458
b(did)f(not)g(pass)h(argumen)-34 b(ts)458 b(at)f(all.)695
b(Ho)-34 b(w)g(ev)g(er,)470 b(this)-1600 53609 y(minor)344
b(p)34 b(enalt)-34 b(y)343 b(in)h(running)h(time)e(is)g(una)-34
b(v)g(oidable)345 b(if)e(w)-34 b(e)344 b(w)-34 b(an)g(t)346
b(the)e(size)f(of)g(the)h(tra)-34 b(v)g(ersal)344 b(co)34
b(de)343 b(to)h(b)34 b(e)343 b(reasonably)-1600 55265
y(b)34 b(ounded:)535 b(w)-34 b(e)395 b(pro)-34 b(v)g(e)395
b(in)f(Section)h(6)f(that)i(if)e(no)h(argumen)-34 b(ts)396
b(are)e(passed)h(b)-34 b(y)395 b(the)g(tra)-34 b(v)g(ersal)394
b(metho)34 b(ds,)397 b(then)e(there)-1600 56921 y(are)298
b(cases)g(where)h(the)g(n)-34 b(um)g(b)34 b(er)299 b(of)g(distinct)h
(tra)-34 b(v)g(ersal)298 b(metho)34 b(ds)300 b(m)-34
b(ust)299 b(b)34 b(e)299 b(exp)34 b(onen)-34 b(tial)298
b(in)h(the)g(size)f(of)h(the)g(strategy)-1600 58577 y(sp)34
b(eci\014cation.)-1600 62538 y Fw(1.4)1495 b(Algorithm)500
b(Ov)-42 b(erview)-1600 65537 y Fv(F)-101 b(or)422 b(those)g(readers)f
(who)h(don't)h(need)e(to)h(understand)i(all)d(the)h(details)f(b)34
b(ehind)423 b(the)f(algorithms)f(w)-34 b(e)422 b(giv)-34
b(e)422 b(a)f(brief)-1600 67193 y(o)-34 b(v)g(erview.)905
b(Giv)-34 b(en)526 b(a)h(strategy)f Fu(S)597 b Fv(and)527
b(a)f(class)g(graph)h Fu(G)p Fv(,)557 b(w)-34 b(e)527
b(need)f(to)h(pro)-34 b(vide)526 b(an)h(algorithm)g(that)g(decides)
-1600 68849 y(whic)-34 b(h)437 b(ob)67 b(jects)436 b(to)h(visit)e(from)
h(a)f(no)34 b(de)436 b Fu(o)g Fv(in)f(an)h(ob)67 b(ject)437
b(graph,)444 b(i.e.,)e(w)-34 b(e)436 b(need)g(to)g(compute)h
Ft(\014rst)114 b Fv(\()p Ft(o)77 b Fv(\),)444 b(the)436
b(set)g(of)-1600 70505 y(edges)451 b(that)i(w)-34 b(e)452
b(need)f(to)h(tra)-34 b(v)g(erse)451 b(from)h(no)34 b(de)451
b Fu(o)p Fv(.)680 b(The)452 b(function)h Ft(\014rst)115
b Fv(\()p Ft(o)77 b Fv(\))451 b(is)g(computed)i(based)f(on)f(answ)-34
b(ers)453 b(to)-1600 72161 y(reac)-34 b(habilit)g(y)431
b(questions)g(in)g(the)g(class)g(graph;)444 b(it)431
b(con)-34 b(tains)432 b(all)e(edges)h(that)h Ft(c)-62
b(ould)428 b Fv(lead)j(\(according)g(to)g(the)g(rules)24897
75628 y(5)p eop
%%Page: 6 7
6 6 bop -1600 2325 a Fv(of)502 b(the)g(class)f(graph\))h(to)g(target)g
(ob)67 b(jects.)831 b(The)502 b Ft(\\c)-62 b(ould")499
b Fv(represen)-34 b(ts)502 b(our)f(lac)-34 b(k)501 b(of)h(kno)-34
b(wledge)502 b(ab)34 b(out)502 b(the)g(rest)-1600 4130
y(of)451 b(the)g(ob)67 b(ject)452 b(graph)f([L)-135 b(W01].)678
b(More)450 b(precisely)-101 b(,)461 b Ft(\014rst)115
b Fv(\()p Ft(o)77 b Fv(\))450 b(con)-34 b(tains)452 b(all)e(edges)h
Fu(o)37941 3464 y Fp(l)37481 4130 y Fs(!)414 b Fu(o)39695
3690 y Fo(0)40456 4130 y Fv(suc)-34 b(h)452 b(that)g(there)e(exists)
-1600 5786 y(an)413 b(ob)67 b(ject)413 b(graph)g(ro)34
b(oted)413 b(at)f Fu(o)13110 5346 y Fo(0)13833 5786 y
Fv(that)h(con)-34 b(tains)414 b(a)e(target)h(ob)67 b(ject)413
b(and)h(that)f(satis\014es)g(a)g(\014xed)f(set)h(of)g(constrain)-34
b(ts)-1600 7442 y(\(expressed)404 b(b)-34 b(y)405 b Fu(S)474
b Fv(and)405 b Fu(G)p Fv(\).)282 9658 y(Our)493 b(goal)f(is)h(to)g(mak)
-34 b(e)493 b(the)g(tra)-34 b(v)g(ersal)493 b(e\016cien)-34
b(t;)537 b(therefore)492 b(w)-34 b(e)494 b(don't)f(w)-34
b(an)g(t)495 b(to)e(lo)34 b(ok)492 b(ahead)i(in)f(the)g(ob)67
b(ject)-1600 11314 y(graph)437 b(to)f(decide)g(whether)h(going)f
(through)h(an)g(edge)f(in)g Ft(\014rst)115 b Fv(\()p
Ft(o)77 b Fv(\))435 b(will)h(ev)-34 b(en)g(tually)436
b(lead)g(us)g(to)h(a)f(target)g(ob)67 b(ject.)-1600 12970
y(W)-101 b(e)327 b(only)g(lo)34 b(ok)327 b(ahead)h(in)g(the)f(class)h
(graph)g(b)34 b(ecause)327 b(it)g(giv)-34 b(es)328 b(us)f
(meta-information)i(ab)34 b(out)329 b(the)f(shap)34 b(e)327
b(of)h(ob)67 b(jects.)-1600 14626 y(So)417 b Ft(\014rst)115
b Fv(\()p Ft(o)77 b Fv(\))417 b(will)f(con)-34 b(tain)418
b(all)e(those)h(edges)g(after)g(whic)-34 b(h,)421 b(according)416
b(to)i(the)f(class)f(graph)i(information,)i(there)d(is)-1600
16282 y(still)355 b(a)h(p)34 b(ossibilit)-34 b(y)355
b(of)h(reac)-34 b(hing)356 b(a)f(target)h(ob)67 b(ject.)523
b(T)-101 b(o)356 b(quic)-34 b(kly)355 b(answ)-34 b(er)356
b(the)g(reac)-34 b(habilit)g(y)355 b(questions)h(w)-34
b(e)356 b(compute)-1600 17938 y(a)387 b(new)h(graph,)j(called)c(a)g
(tra)-34 b(v)g(ersal)387 b(graph,)k(whic)-34 b(h)388
b(is)g(basically)e(the)i(pro)34 b(duct)388 b(of)f(the)h(t)-34
b(w)g(o)389 b(graphs)f Fu(S)457 b Fv(and)389 b Fu(G)p
Fv(.)532 b(The)-1600 19594 y(tra)-34 b(v)g(ersal)518
b(graph)g(stores)g(the)g(answ)-34 b(ers)518 b(to)h(the)f(reac)-34
b(habilit)g(y)517 b(questions)i(that)g(w)-34 b(e)518
b(will)f(ask)g(during)i(the)f(ob)67 b(ject)-1600 21250
y(tra)-34 b(v)g(ersal.)282 23466 y(The)352 b(T)-101 b(ra)-34
b(v)g(ersal)352 b(Graph)g(Algorithm)g(\(TGA\))h(is)e(based)i(on)f(the)g
(follo)-34 b(wing)352 b(idea)g(of)g(a)g(reduction:)512
b(F)-101 b(or)352 b(tra)-34 b(v)g(ersal)-1600 25122 y(strategies)495
b(of)g(the)h(form)f(\\)p Fr(from)h(A)f(to)g(B)p Fv(",)f(the)i(paths)g
(de\014ned)g(in)f(the)h(class)e(graph)i(can)f(b)34 b(e)495
b(represen)-34 b(ted)495 b(b)-34 b(y)496 b(a)-1600 26778
y(subgraph)507 b(of)f(the)g(class)f(graph:)742 b(Compute)507
b(all)e(edges)h(reac)-34 b(hable)505 b(from)h Fr(A)g
Fv(\(called)f(forw)-34 b(ard)506 b(edges\))g(and)h(from)-1600
28435 y(whic)-34 b(h)505 b Fr(B)g Fv(can)g(b)34 b(e)504
b(reac)-34 b(hed)504 b(\(called)h(bac)-34 b(kw)g(ard)505
b(edges\).)840 b(This)505 b(computation)i(is)d(called)g
Ft(fr)-62 b(om-to)524 b(c)-62 b(omputation)p Fv(.)-1600
30091 y(Edges)529 b(in)g(the)g(in)-34 b(tersection)530
b(of)f(the)g(forw)-34 b(ard)530 b(and)g(bac)-34 b(kw)g(ard)530
b(edges)f(form)g(the)h(graph)f(whic)-34 b(h)530 b(represen)-34
b(ts)529 b(the)-1600 31747 y(tra)-34 b(v)g(ersal.)928
b(An)-34 b(y)535 b(strategy)f(can)h(b)34 b(e)534 b(reduced)g(to)g(a)g
(from-to)h(computation)h(on)f(a)f(graph)g(that)i(is)e(m)-34
b(uc)g(h)535 b(larger)-1600 33403 y(than)540 b(the)g(original)e(class)h
(graph.)944 b(This)539 b(larger)f(graph,)573 b(called)538
b(the)i(tra)-34 b(v)g(ersal)539 b(graph,)573 b(will)538
b(con)-34 b(tain)540 b(as)f(man)-34 b(y)-1600 35059 y(copies)482
b(of)h(the)f(class)g(graph)h(as)g(the)f(tra)-34 b(v)g(ersal)482
b(strategy)h(graph)g(has)g(edges.)773 b(The)482 b(size)g(of)g(the)h
(tra)-34 b(v)g(ersal)482 b(graph)-1600 36715 y(will)470
b(b)34 b(e)471 b(reduced)g(b)-34 b(y)471 b(a)g(from-to)h(computation.)
740 b(In)471 b(other)g(w)-34 b(ords,)489 b(the)471 b(from-to)h
(computation)g(\(whic)-34 b(h)472 b(can)f(b)34 b(e)-1600
38371 y(implemen)-34 b(ted,)510 b(e.g.,)e(with)490 b(a)e(forw)-34
b(ard)489 b(and)h(a)e(bac)-34 b(kw)g(ard)490 b(depth-\014rst)g(searc)
-34 b(h\))489 b(is)f(fundamen)-34 b(tal)491 b(to)e(computing)-1600
40027 y(the)360 b(tra)-34 b(v)g(ersal)359 b(graph.)524
b(The)360 b(size)e(of)i(the)g(tra)-34 b(v)g(ersal)359
b(graph)h(is)f(a)g(small)g(p)34 b(olynomial)359 b(in)h(the)f(size)g(of)
h(the)f(class)g(graph)-1600 41683 y(and)405 b(the)f(strategy)h(graph.)
282 43899 y(The)343 b(tra)-34 b(v)g(ersal)342 b(graph)i(is)e
(non-deterministic)h(in)g(nature:)508 b(from)343 b(a)g(no)34
b(de)343 b(there)f(migh)-34 b(t)344 b(b)34 b(e)342 b(t)-34
b(w)g(o)344 b(outgoing)g(edges)-1600 45555 y(with)451
b(the)f(same)g(lab)34 b(el)449 b(\(leading)h(to)h(di\013eren)-34
b(t)450 b(no)34 b(des|there)450 b(are)g(no)g(parallel)f(edges\).)676
b(This)451 b(non-determinism)-1600 47211 y(needs)346
b(to)g(b)34 b(e)345 b(handled)i(carefully)e(in)h(order)f(to)h(a)-34
b(v)g(oid)346 b(an)g(exp)34 b(onen)-34 b(tial)346 b(blo)-34
b(w-up)347 b(in)f(algorithm)g(p)34 b(erformance.)518
b(The)-1600 48867 y(T)-101 b(ra)-34 b(v)g(ersal)381 b(Metho)34
b(ds)382 b(Algorithm)f(\(TMA\))i(tra)-34 b(v)g(erses)381
b(an)g(ob)67 b(ject)382 b(graph,)k(guided)c(b)-34 b(y)381
b(a)g(tra)-34 b(v)g(ersal)381 b(graph.)532 b(T)-101 b(o)381
b(deal)-1600 50523 y(with)327 b(the)f(non-determinism,)342
b(w)-34 b(e)326 b(allo)-34 b(w)326 b(m)-34 b(ultiple)326
b(tok)-34 b(ens)326 b(sim)-34 b(ultaneously)326 b(to)g(b)34
b(e)326 b(put)h(on)f(the)g(tra)-34 b(v)g(ersal)325 b(graph)i(to)-1600
52179 y(k)-34 b(eep)395 b(trac)-34 b(k)396 b(of)g(the)g(legal)f(tra)-34
b(v)g(ersal)395 b(p)34 b(ossibilities.)535 b(As)396 b(the)g(tra)-34
b(v)g(ersal)395 b(progresses)h(the)g(n)-34 b(um)g(b)34
b(er)396 b(of)g(tok)-34 b(ens)397 b(on)e(the)-1600 53835
y(tra)-34 b(v)g(ersal)364 b(graph)h(\015uctuates.)527
b(F)-101 b(ortunately)g(,)372 b(the)365 b(n)-34 b(um)g(b)34
b(er)365 b(of)g(sim)-34 b(ultaneous)365 b(tok)-34 b(ens)365
b(is)f(b)34 b(ounded)366 b(b)-34 b(y)364 b(the)h(n)-34
b(um)g(b)34 b(er)-1600 55491 y(of)404 b(edges)h(in)f(the)g(strategy)g
(graph.)282 57707 y(As)517 b(suggested)h(b)-34 b(y)517
b([PPL97,)f(Sma)q(],)544 b(these)518 b(t)-34 b(w)g(o)518
b(algorithms)f(are)g(ab)34 b(out)518 b(computing)g(in)-34
b(tersections)517 b(of)h(sets)-1600 59363 y(of)449 b(paths.)673
b(TGA)450 b(is)e(a)h(v)-67 b(ariation)448 b(on)h(an)g(algorithm)g(to)g
(compute)g(the)g(cross)g(pro)34 b(duct)449 b(of)g(t)-34
b(w)g(o)450 b(automata,)461 b(while)-1600 61019 y(TMA)487
b(is)f(inspired)h(b)-34 b(y)487 b(the)f(NF)-135 b(A)487
b(sim)-34 b(ulation)488 b(tec)-34 b(hnique)487 b(describ)34
b(ed)486 b(in)g([ASU86].)786 b(The)487 b(complications)f(are)g(in)-1600
62675 y(the)364 b(constrain)-34 b(t)365 b(maps,)373 b(the)364
b(name)g(maps)h(and)f(the)h(more)e(complex)g(structure)i(of)f(the)g
(graphs:)519 b(class)364 b(graphs)g(ha)-34 b(v)g(e)-1600
64331 y(t)g(w)g(o)406 b(kinds)e(of)g(no)34 b(des)405
b(and)g(t)-34 b(w)g(o)405 b(kinds)g(of)f(edges.)24897
75628 y(6)p eop
%%Page: 7 8
7 7 bop -1600 2325 a Fw(1.5)1495 b(P)-42 b(ap)42 b(er)499
b(Organization)-1600 5324 y Fv(The)g(remainder)e(of)i(this)f(pap)34
b(er)498 b(is)g(organized)g(as)g(follo)-34 b(ws.)821
b(In)498 b(Section)g(2)g(w)-34 b(e)499 b(in)-34 b(tro)34
b(duce)498 b(the)h(basic)f(concepts,)-1600 6980 y(terminology)545
b(and)g(notation)i(w)-34 b(e)545 b(use)g(throughout)j(the)d(pap)34
b(er.)961 b(In)545 b(Section)g(3)g(w)-34 b(e)546 b(giv)-34
b(e)544 b(a)h(de\014nition)h(for)g(the)-1600 8636 y(concept)519
b(of)h(tra)-34 b(v)g(ersals,)547 b(based)520 b(on)f([PPL97].)882
b(In)520 b(Section)f(4)g(w)-34 b(e)519 b(de\014ne)h(the)f(new)h
(concept)f(of)h(strategies.)883 b(In)-1600 10292 y(Section)531
b(5)g(w)-34 b(e)531 b(sp)34 b(ecify)530 b(and)i(analyze)e(the)h
(algorithm)g(whic)-34 b(h)532 b(translates)g(strategies)e(in)-34
b(to)532 b(tra)-34 b(v)g(ersal)531 b(co)34 b(de.)918
b(In)-1600 11948 y(Section)407 b(6)f(w)-34 b(e)407 b(pro)-34
b(v)g(e)406 b(a)h(lo)-34 b(w)g(er)406 b(b)34 b(ound)408
b(for)e(tra)-34 b(v)g(ersal)406 b(metho)34 b(ds)408 b(that)f(do)g(not)g
(pass)g(argumen)-34 b(ts.)546 b(In)407 b(Section)f(7)h(w)-34
b(e)-1600 13604 y(commen)g(t)447 b(ab)34 b(out)446 b(some)g(practical)g
(asp)34 b(ects)446 b(of)g(the)g(implemen)-34 b(tation)447
b(of)g(the)f(strategies)g(approac)-34 b(h.)665 b(In)446
b(Section)-1600 15260 y(8)459 b(w)-34 b(e)459 b(surv)-34
b(ey)458 b(related)g(w)-34 b(ork.)702 b(In)459 b(Section)g(9)f(w)-34
b(e)459 b(compare)g(strategies)f(with)i(the)f(earlier)d(approac)-34
b(h)460 b(of)f(tra)-34 b(v)g(ersal)-1600 16916 y(sp)34
b(eci\014cations.)520 b(In)350 b(Section)g(10)g(w)-34
b(e)350 b(describ)34 b(e)349 b(some)h(applications)g(of)g(strategies.)
520 b(In)350 b(Section)g(11)g(w)-34 b(e)350 b(describ)34
b(e)349 b(our)-1600 18572 y(exp)34 b(eriences)376 b(using)j(strategies)
e(and)i(presen)-34 b(t)378 b(some)g(empirical)f(evidence)g(of)h(ho)-34
b(w)379 b(they)f(are)f(used.)530 b(W)-101 b(e)377 b(giv)-34
b(e)378 b(a)f(few)-1600 20228 y(concluding)405 b(though)-34
b(ts)406 b(in)e(Section)h(12.)-1600 24806 y Fx(2)1793
b(Preliminaries)-1600 28223 y Fv(In)346 b(this)g(section)g(w)-34
b(e)347 b(formally)e(de\014ne)h(the)h(basic)f(concepts,)357
b(terminology)346 b(and)h(notation)g(w)-34 b(e)346 b(use)g(throughout)i
(this)-1600 29879 y(pap)34 b(er.)538 b(All)404 b(notions)h(in)f(this)h
(section)f(are)g(standard,)h(with)g(the)f(exception)g(of)h(Subsection)g
(2.3.)-1600 33839 y Fw(2.1)1495 b(Graphs)499 b(and)g(paths)-1600
36838 y Fv(A)512 b(directed)g(graph)h(is)g(a)f(pair)g(\()p
Fu(V)67 b(;)202 b(E)70 b Fv(\))513 b(where)f Fu(V)782
b Fv(is)512 b(a)h(set)f(of)h Ft(no)-62 b(des)p Fv(,)538
b(and)513 b Fu(E)587 b Fs(\022)517 b Fu(V)611 b Fs(\002)341
b Fu(V)782 b Fv(is)512 b(a)g(set)h(of)g Ft(e)-62 b(dges)p
Fv(.)861 b(A)-1600 38494 y(directed)492 b(lab)34 b(eled)491
b(graph)i(is)f(a)g(triple)g Fu(G)483 b Fv(=)g(\()p Fu(V)67
b(;)202 b(E)70 b(;)202 b(L)p Fv(\))492 b(where)g Fu(V)762
b Fv(is)492 b(a)g(set)g(of)g Ft(no)-62 b(des)p Fv(,)513
b Fu(L)492 b Fv(is)g(a)g(set)g(of)h Ft(lab)-62 b(els)p
Fv(,)511 b(and)-1600 40150 y Fu(E)406 b Fs(\022)337 b
Fu(V)502 b Fs(\002)232 b Fu(L)h Fs(\002)f Fu(V)655 b
Fv(is)386 b(a)g(set)g(of)g Ft(e)-62 b(dges)p Fv(.)530
b(If)386 b Fu(e)337 b Fv(=)f(\()p Fu(u;)202 b(l)24 b(;)202
b(v)43 b Fv(\))336 b Fs(2)h Fu(E)70 b Fv(,)389 b(then)e
Fu(u)e Fv(is)h(the)g Ft(sour)-62 b(c)g(e)383 b Fv(of)k
Fu(e)p Fv(,)i Fu(l)409 b Fv(is)386 b(the)g Ft(lab)-62
b(el)384 b Fv(of)i Fu(e)p Fv(,)j(and)e Fu(v)-1600 41956
y Fv(is)404 b(the)g Ft(tar)-62 b(get)403 b Fv(of)h Fu(e)p
Fv(.)539 b(W)-101 b(e)403 b(denote)i(an)g(edge)f(\()p
Fu(u;)202 b(l)24 b(;)202 b(v)43 b Fv(\))403 b(b)-34 b(y)405
b Fu(u)25667 41290 y Fp(l)25206 41956 y Fs(!)337 b Fu(v)43
b Fv(.)282 44172 y(Giv)-34 b(en)461 b(a)g(directed)f(lab)34
b(eled)461 b(graph)g Fu(G)432 b Fv(=)f(\()p Fu(V)67 b(;)202
b(E)70 b(;)202 b(L)p Fv(\),)475 b(a)461 b Ft(no)-62 b(de-p)g(ath)458
b Fv(is)j(a)g(sequence)f Fu(p)431 b Fv(=)h Fs(h)p Fu(v)42945
44354 y Fn(0)43470 44172 y Fu(v)44058 44354 y Fn(1)44786
44172 y Fu(:)202 b(:)g(:)f(v)46990 44354 y Fp(n)47616
44172 y Fs(i)p Fv(,)475 b(where)-1600 46014 y Fu(v)-1012
46196 y Fp(i)-133 46014 y Fs(2)504 b Fu(V)773 b Fv(for)505
b(0)e Fs(\024)h Fu(i)f Fs(\024)h Fu(n)p Fv(,)528 b(and)505
b Fu(v)14177 46196 y Fp(i)p Fo(\000)p Fn(1)16548 45311
y Fp(l)16829 45446 y Fm(i)16258 46014 y Fs(!)f Fu(v)18562
46196 y Fp(i)19441 46014 y Fs(2)g Fu(E)574 b Fv(for)504
b(some)g Fu(l)27676 46196 y Fp(i)28555 46014 y Fs(2)g
Fu(L)g Fv(for)h(all)e(0)h Fu(<)f(i)h Fs(\024)f Fu(n)p
Fv(.)839 b(Similarly)-101 b(,)527 b(a)505 b Ft(p)-62
b(ath)595 b Fv(is)-1600 47827 y(a)474 b(sequence)g Fs(h)q
Fu(v)5634 48009 y Fn(0)6159 47827 y Fu(l)6521 48009 y
Fn(1)7046 47827 y Fu(v)7634 48009 y Fn(1)8160 47827 y
Fu(l)8522 48009 y Fn(2)9249 47827 y Fu(:)202 b(:)g(:)f(l)11227
48009 y Fp(n)11853 47827 y Fu(v)12441 48009 y Fp(n)13067
47827 y Fs(i)475 b Fv(where)f Fs(h)q Fu(v)18648 48009
y Fn(0)19375 47827 y Fu(:)202 b(:)g(:)f(v)21579 48009
y Fp(n)22205 47827 y Fs(i)475 b Fv(is)f(a)g(no)34 b(de-path,)493
b(and)475 b Fu(v)34717 48009 y Fp(i)p Fo(\000)p Fn(1)37039
47125 y Fp(l)37320 47260 y Fm(i)36749 47827 y Fs(!)453
b Fu(v)39002 48009 y Fp(i)39831 47827 y Fs(2)h Fu(E)544
b Fv(for)475 b(all)e(0)454 b Fu(<)g(i)f Fs(\024)h Fu(n)p
Fv(.)-1600 49483 y(Unlab)34 b(eled)462 b(graphs)i(ha)-34
b(v)g(e)463 b(only)f(no)34 b(de-paths.)716 b(P)-34 b(aths)463
b(of)g(the)g(form)g Fs(h)q Fu(v)31662 49665 y Fn(0)32187
49483 y Fs(i)g Fv(are)f(called)g Ft(trivial.)712 b Fv(The)463
b(\014rst)g(no)34 b(de)463 b(of)-1600 51139 y(a)484 b(path)h(\(or)e(a)h
(no)34 b(de-path\))485 b Fu(p)f Fv(is)f(called)g(the)h
Ft(sour)-62 b(c)g(e)482 b Fv(of)i Fu(p)p Fv(,)503 b(and)484
b(the)g(last)g(no)34 b(de)484 b(in)g Fu(p)f Fv(is)h(called)f(the)h
Ft(tar)-62 b(get)481 b Fv(of)j Fu(p)p Fv(,)-1600 52795
y(denoted)438 b Fr(Source)p Fv(\()p Fu(p)p Fv(\))f(and)h
Fr(T)-101 b(a)-34 b(rget)p Fv(\()p Fu(p)p Fv(\),)445
b(resp)34 b(ectiv)-34 b(ely)-101 b(.)634 b(The)437 b(elemen)-34
b(ts)437 b(other)g(than)h(the)f(source)f(and)i(the)f(target)g(of)-1600
54451 y(a)414 b(path)i(\(no)34 b(des)415 b(for)f(a)g(no)34
b(de-path,)418 b(no)34 b(des)415 b(and)g(edges)f(for)h(a)f(path\))i
(are)d(the)i Ft(interior)e Fv(of)i(the)g(path.)570 b(F)-101
b(or)414 b(a)g(graph)-1600 56107 y Fu(G)p Fv(,)397 b(no)34
b(des)396 b Fu(u;)202 b(v)43 b Fv(,)396 b(and)g(sets)g(of)g(no)34
b(des)395 b Fu(U)m(;)202 b(V)269 b Fv(,)397 b(w)-34 b(e)396
b(de\014ne)g Fu(P)24684 56295 y Fp(G)25473 56107 y Fv(\()p
Fu(u;)202 b(v)43 b Fv(\))395 b(to)h(b)34 b(e)395 b(the)h(set)g(of)g
(all)e(paths)j(in)e Fu(G)h Fv(with)g(source)f Fu(u)-1600
57763 y Fv(and)405 b(target)f Fu(v)447 b Fv(and)405 b
Fu(P)8499 57951 y Fp(G)9288 57763 y Fv(\()p Fu(U)m(;)202
b(V)270 b Fv(\))404 b(to)h(b)34 b(e)403 b(the)i(set)f(of)h(all)e(paths)
j(in)e Fu(G)g Fv(with)h(source)f(in)g Fu(U)535 b Fv(and)405
b(with)g(target)g(in)f Fu(V)269 b Fv(.)282 59979 y(If)450
b Fu(p)2150 60161 y Fn(1)3089 59979 y Fv(=)414 b Fs(h)p
Fu(v)5505 60161 y Fn(0)6232 59979 y Fu(:)202 b(:)g(:)f(l)8210
60161 y Fp(i)8586 59979 y Fu(v)9174 60161 y Fp(i)9549
59979 y Fs(i)451 b Fv(and)g Fu(p)13484 60161 y Fn(2)14423
59979 y Fv(=)413 b Fs(h)q Fu(v)16839 60161 y Fp(i)17214
59979 y Fu(l)17576 60161 y Fp(i)p Fn(+1)19355 59979 y
Fu(:)202 b(:)g(:)g(v)21560 60161 y Fp(n)22185 59979 y
Fs(i)451 b Fv(are)f(paths)h(with)g(the)g(target)f(of)h
Fu(p)39125 60161 y Fn(1)40101 59979 y Fv(iden)-34 b(tical)450
b(to)h(the)f(source)-1600 61635 y(of)425 b Fu(p)411 61817
y Fn(2)937 61635 y Fv(,)k(w)-34 b(e)426 b(de\014ne)f(the)g
(concatenation)h Fu(p)17514 61817 y Fn(1)18323 61635
y Fs(\001)283 b Fu(p)19553 61817 y Fn(2)20449 61635 y
Fv(=)371 b Fs(h)q Fu(v)22823 61817 y Fn(0)23550 61635
y Fu(:)202 b(:)g(:)f(v)25754 61817 y Fp(i)p Fo(\000)p
Fn(1)27332 61635 y Fu(l)27694 61817 y Fp(i)28069 61635
y Fu(v)28657 61817 y Fp(i)29032 61635 y Fu(l)29394 61817
y Fp(i)p Fn(+1)30972 61635 y Fu(v)31560 61817 y Fp(i)p
Fn(+1)33340 61635 y Fu(:)h(:)g(:)f(v)35544 61817 y Fp(n)36170
61635 y Fs(i)p Fv(.)600 b(Notice)425 b(that)h Fu(p)44661
61817 y Fn(1)45470 61635 y Fs(\001)282 b Fu(p)46699 61817
y Fn(2)47650 61635 y Fv(con)-34 b(tains)-1600 63291 y(only)432
b(one)g(cop)-34 b(y)432 b(of)g(the)h(meeting)f(p)34 b(oin)-34
b(t)433 b Fu(v)18106 63473 y Fp(i)18481 63291 y Fv(.)622
b(Concatenation)434 b(of)e(no)34 b(de)432 b(paths)h(is)f(de\014ned)h
(similarly)-101 b(.)621 b(Let)431 b Fu(P)49089 63473
y Fn(1)50047 63291 y Fv(and)-1600 64948 y Fu(P)-822 65130
y Fn(2)126 64948 y Fv(b)34 b(e)422 b(sets)g(of)h(paths)g(suc)-34
b(h)424 b(that)f(for)f(some)g(no)34 b(de)423 b Fu(v)43
b Fv(,)426 b Fr(T)-101 b(a)-34 b(rget)p Fv(\()p Fu(p)27922
65130 y Fn(1)28448 64948 y Fv(\))367 b(=)g Fu(v)465 b
Fv(for)422 b(all)g Fu(p)35834 65130 y Fn(1)36726 64948
y Fs(2)367 b Fu(P)38679 65130 y Fn(1)39205 64948 y Fv(,)427
b(and)c Fr(Source)p Fv(\()p Fu(p)46822 65130 y Fn(2)47348
64948 y Fv(\))367 b(=)g Fu(v)465 b Fv(for)-1600 66604
y(all)404 b Fu(p)694 66786 y Fn(2)1556 66604 y Fs(2)337
b Fu(P)3479 66786 y Fn(2)4005 66604 y Fv(.)538 b(Then)405
b(w)-34 b(e)405 b(de\014ne)14193 69477 y Fu(P)14971 69659
y Fn(1)15766 69477 y Fs(\001)269 b Fu(P)17150 69659 y
Fn(2)18013 69477 y Fv(=)336 b Fs(f)p Fu(p)20508 69659
y Fn(1)21303 69477 y Fs(\001)269 b Fu(p)22519 69659 y
Fn(2)23382 69477 y Fs(j)336 b Fu(p)24665 69659 y Fn(1)25528
69477 y Fs(2)g Fu(P)27450 69659 y Fn(1)28380 69477 y
Fv(and)405 b Fu(p)31347 69659 y Fn(2)32210 69477 y Fs(2)336
b Fu(P)34132 69659 y Fn(2)34658 69477 y Fs(g)607 b Fu(:)24897
75628 y Fv(7)p eop
%%Page: 8 9
8 8 bop -1600 2325 a Fw(2.2)1495 b(Class)500 b(graphs)g(and)f(ob)83
b(ject)498 b(graphs)-1600 5324 y Fv(In)448 b(this)h(pap)34
b(er)448 b(w)-34 b(e)449 b(will)f(b)34 b(e)448 b(in)-34
b(terested)448 b(in)h(sp)34 b(ecial)447 b(kinds)i(of)f(graphs,)460
b(called)447 b(class)h(graphs)h(and)g(ob)67 b(ject)450
b(graphs,)-1600 6980 y(de\014ned)405 b(as)f(follo)-34
b(ws.)282 9196 y(Fix)402 b(a)h(\014nite)h(set)f Fs(C)474
b Fv(of)403 b Ft(class)431 b(names)p Fv(.)537 b(Eac)-34
b(h)404 b(class)e(name)h(is)g(either)g Ft(abstr)-62 b(act)400
b Fv(or)j Ft(c)-62 b(oncr)g(ete)p Fv(.)536 b(Fix)402
b(a)h(\014nite)h(set)f Fs(L)-1600 10852 y Fv(of)461 b
Ft(\014eld)485 b(names)p Fv(.)708 b(W)-101 b(e)461 b(sometimes)g(call)f
(\014eld)h(names)g Ft(lab)-62 b(els)p Fv(.)706 b(W)-101
b(e)460 b(assume)i(the)f(existence)f(of)h(t)-34 b(w)g(o)463
b(distinguished)-1600 12508 y(sym)-34 b(b)34 b(ols:)654
b Fq(this)435 b Fs(2)e(L)462 b Fv(and)h Fs(\005)568 b
Fu(=)-741 b Fs(2)434 b(L)p Fv(.)712 b(Class)462 b(graphs)h(mo)34
b(del)462 b(the)g(class)g(structure)g(of)h(ob)67 b(ject-orien)-34
b(ted)463 b(programs.)-1600 14164 y(F)-101 b(ormally)g(,)403
b Ft(class)432 b(gr)-62 b(aphs)402 b Fv(are)h(graphs)i
Fu(G)337 b Fv(=)f(\()p Fu(V)67 b(;)202 b(E)70 b(;)202
b(L)p Fv(\))405 b(suc)-34 b(h)405 b(that)218 17376 y
Fs(\017)606 b Fu(V)g Fs(\022)337 b(C)71 b Fv(,)404 b(i.e.,)e(the)j(no)
34 b(des)404 b(are)g(class)f(names.)218 20028 y Fs(\017)606
b Fu(L)456 b Fs(\022)g(L)317 b([)g(f\005g)p Fv(,)493
b(i.e.,)f(edges)476 b(are)f(lab)34 b(eled)475 b(b)-34
b(y)476 b(\014eld)f(names)h(or)g(\\)p Fs(\005)p Fv(".)753
b(Edges)475 b(lab)34 b(eled)475 b(b)-34 b(y)476 b(a)g(\014eld)g(name)f
(are)1430 21684 y(called)404 b Ft(r)-62 b(efer)g(enc)g(e)402
b Fv(edges,)i(and)h(edges)f(lab)34 b(eled)403 b(b)-34
b(y)405 b Fs(\005)f Fv(are)f(called)h Ft(sub)-62 b(class)401
b Fv(edges.)218 24337 y Fs(\017)606 b Fv(F)-101 b(or)485
b(eac)-34 b(h)486 b Fu(v)514 b Fs(2)472 b Fu(V)270 b
Fv(,)505 b(the)485 b(\014eld)h(names)f(of)h(all)e(edges)h(going)g(out)h
(from)g Fu(v)528 b Fv(are)484 b(distinct)i(\(but)h(there)e(ma)-34
b(y)485 b(b)34 b(e)1430 25993 y(man)-34 b(y)405 b(edges)f(lab)34
b(eled)403 b(b)-34 b(y)405 b Fs(\005)f Fv(going)g(out)h(from)g
Fu(v)43 b Fv(\).)218 28645 y Fs(\017)606 b Fv(F)-101
b(or)404 b(eac)-34 b(h)405 b Fu(v)379 b Fs(2)337 b Fu(V)674
b Fv(suc)-34 b(h)405 b(that)g Fu(v)447 b Fv(is)404 b(concrete,)f
Fu(v)23529 27979 y Fl(this)23864 28645 y Fs(!)671 b Fu(v)380
b Fs(2)337 b Fu(E)70 b Fv(.)218 31297 y Fs(\017)606 b
Fv(The)405 b(set)f(of)h(sub)34 b(class)404 b(edges)g(is)g(acyclic.)
-1600 34510 y(W)-101 b(e)502 b(shall)h(use)f(the)h(\(re\015exiv)-34
b(e\))502 b(notion)i(of)f(a)g Ft(sup)-62 b(er)g(class)99
b Fv(:)732 b(giv)-34 b(en)502 b(a)h(class)f(graph)h Fu(G)e
Fv(=)g(\()p Fu(V)67 b(;)202 b(E)70 b(;)202 b(L)p Fv(\),)527
b(w)-34 b(e)503 b(sa)-34 b(y)503 b(that)-1600 36166 y
Fu(v)397 b Fs(2)354 b Fu(V)683 b Fv(is)414 b(a)h(sup)34
b(erclass)414 b(of)h Fu(u)353 b Fs(2)h Fu(V)684 b Fv(if)414
b(there)g(is)g(a)h(\(p)34 b(ossibly)414 b(empt)-34 b(y\))416
b(path)f(of)g(sub)34 b(class)415 b(edges)f(from)g Fu(v)458
b Fv(to)414 b Fu(u)p Fv(.)569 b(The)-1600 37822 y(collection)396
b(of)g(all)g(sup)34 b(er-classes)396 b(of)h(a)f(class)g
Fu(v)440 b Fv(is)396 b(called)g(the)h Ft(anc)-62 b(estry)394
b Fv(of)j Fu(v)43 b Fv(.)536 b(Multiple)396 b(inheritance)h
(con\015icts)f(are)-1600 39478 y(disallo)-34 b(w)g(ed:)539
b(w)-34 b(e)405 b(require)e(that)i(the)g(follo)-34 b(wing)404
b(condition)h(holds)g(true.)1430 42690 y Fk(Single)464
b(Inheritance)e(Condition:)540 b Fv(F)-101 b(or)402 b(all)g(no)34
b(des)402 b Fu(v)43 b Fv(,)402 b(if)h Fu(v)445 b Fv(has)403
b(t)-34 b(w)g(o)403 b(sup)34 b(erclasses)402 b Fu(u)g
Fv(and)h Fu(w)435 b Fv(with)1430 44346 y(outgoing)f(edges)f(lab)34
b(eled)433 b(b)-34 b(y)433 b(the)h(same)f(lab)34 b(el,)439
b(then)433 b(either)g Fu(u)g Fv(is)g(in)g(the)g(ancestry)g(of)g
Fu(w)466 b Fv(or)432 b Fu(w)466 b Fv(is)433 b(in)1430
46002 y(the)405 b(ancestry)f(of)g Fu(u)p Fv(.)-1600 49214
y(The)521 b(set)h(of)f Ft(induc)-62 b(e)g(d)539 b(r)-62
b(efer)g(enc)g(es)519 b Fv(of)i(a)g(giv)-34 b(en)521
b(class)f Fu(v)564 b Fv(is)521 b(the)g(set)h(of)f(all)f(reference)g
(edges)h(going)g(out)h(from)f(its)-1600 50870 y(ancestry)-101
b(,)408 b(with)g(the)f(usual)h(o)-34 b(v)g(erriding)407
b(rule:)544 b(for)408 b(eac)-34 b(h)407 b(lab)34 b(el)406
b Fu(l)431 b Fv(used)408 b(in)f(edges)g(going)h(out)g(from)f(the)h
(ancestry)f(of)-1600 52526 y Fu(v)43 b Fv(,)394 b(only)e(the)g(edge)f
(lab)34 b(eled)392 b Fu(l)415 b Fv(closest)391 b(to)i
Fu(v)434 b Fv(is)392 b(in)g(the)g(induced)g(references)f(of)h
Fu(v)43 b Fv(.)535 b(The)392 b(notion)h(of)f(\\closest")g(is)f(w)-34
b(ell)-1600 54182 y(de\014ned)374 b(b)-34 b(y)373 b(the)h(Single)f
(Inheritance)g(Condition)h(ab)34 b(o)-34 b(v)g(e.)529
b(Note)373 b(that)h(since)f(a)g(class)g(is)f(a)h(sup)34
b(erclass)373 b(of)h(itself,)k(the)-1600 55838 y(induced)405
b(edges)f(include)g(b)34 b(oth)405 b(the)f(direct)g(references)f(and)i
(the)g(inherited)f(references.)282 58055 y(Next,)367
b(w)-34 b(e)358 b(de\014ne)h Ft(obje)-62 b(ct)389 b(gr)-62
b(aphs)p Fv(,)365 b(whic)-34 b(h)359 b(mo)34 b(del)357
b(the)i(instan)-34 b(tiations)360 b(of)e(class)g(graphs.)524
b(An)358 b(ob)67 b(ject)359 b(graph)g(is)f(a)-1600 59711
y(lab)34 b(eled)417 b(directed)g(graph)h(\012)360 b(=)f(\()p
Fu(V)14654 59271 y Fo(0)14964 59711 y Fu(;)202 b(E)16468
59271 y Fo(0)16778 59711 y Fu(;)g(L)18142 59271 y Fo(0)18453
59711 y Fv(\),)421 b(where)c(no)34 b(des)418 b(are)f(called)g
Ft(obje)-62 b(cts)p Fv(,)418 b(and)g Fu(L)39559 59271
y Fo(0)40229 59711 y Fs(\022)359 b(L)p Fv(.)579 b(An)418
b(ob)67 b(ject)418 b(graph)-1600 61367 y(\012)436 b(=)g(\()p
Fu(V)2537 60927 y Fo(0)2848 61367 y Fu(;)202 b(E)4352
60927 y Fo(0)4662 61367 y Fu(;)g(L)6026 60927 y Fo(0)6336
61367 y Fv(\))464 b(is)f(an)h Ft(instanc)-62 b(e)462
b Fv(of)i(a)g(class)f(graph)h Fu(G)436 b Fv(=)f(\()p
Fu(V)67 b(;)202 b(E)70 b(;)202 b(L)p Fv(\))464 b(under)g(a)f(giv)-34
b(en)464 b(function)h Fr(Class)e Fv(mapping)-1600 63023
y(ob)67 b(jects)405 b(to)g(classes,)e(if)h(the)h(follo)-34
b(wing)404 b(conditions)h(are)f(satis\014ed.)218 66235
y Fs(\017)606 b Fv(F)-101 b(or)404 b(all)g(ob)67 b(jects)405
b Fu(o)336 b Fs(2)h Fu(V)12483 65795 y Fo(0)12793 66235
y Fv(,)404 b Fr(Class)p Fv(\()p Fu(o)p Fv(\))g(is)g(concrete.)218
68887 y Fs(\017)606 b Fv(F)-101 b(or)463 b(eac)-34 b(h)462
b(ob)67 b(ject)464 b Fu(o)433 b Fs(2)h Fu(V)13417 68447
y Fo(0)13728 68887 y Fv(,)476 b(the)463 b(lab)34 b(els)462
b(of)h(edges)f(going)h(out)g(from)g Fu(o)e Fv(is)i(exactly)e(the)i(set)
f(of)h(lab)34 b(els)462 b(of)g(the)1430 70543 y(induced)437
b(references)d(of)j Fr(Class)o Fv(\()p Fu(o)p Fv(\).)634
b(\(In)436 b(particular,)443 b(this)437 b(means)f(that)h(the)f(edges)g
(going)g(out)g(from)g Fu(o)f Fv(ha)-34 b(v)g(e)1430 72199
y(distinct)405 b(lab)34 b(els.\))24897 75628 y(8)p eop
%%Page: 9 10
9 9 bop 218 2499 a Fs(\017)606 b Fv(F)-101 b(or)542 b(eac)-34
b(h)543 b(edge)f Fu(o)11122 1833 y Fp(l)10662 2499 y
Fs(!)567 b Fu(o)13029 2059 y Fo(0)13905 2499 y Fs(2)g
Fu(E)16245 2059 y Fo(0)16555 2499 y Fv(,)577 b Fr(Class)o
Fv(\()p Fu(o)p Fv(\))543 b(has)f(an)h(induced)g(reference)d(edge)i
Fu(v)40673 1833 y Fp(l)40213 2499 y Fs(!)567 b Fu(u)542
b Fv(suc)-34 b(h)543 b(that)g Fu(v)585 b Fv(is)542 b(a)1430
4155 y(sup)34 b(erclass)404 b(of)h Fr(Class)o Fv(\()p
Fu(o)p Fv(\))g(and)g Fu(u)f Fv(is)f(a)i(sup)34 b(erclass)403
b(of)i Fr(Class)p Fv(\()p Fu(o)29448 3715 y Fo(0)29758
4155 y Fv(\).)-1600 7367 y(F)-101 b(or)520 b(the)g(greater)f(part)h(of)
g(this)h(pap)34 b(er,)548 b(w)-34 b(e)520 b(shall)g(assume)g(that)h(ob)
67 b(ject)521 b(graphs)f(are)f(acyclic.)884 b(W)-101
b(e)519 b(discuss)i(an)-1600 9023 y(extension)404 b(to)h(cyclic)d(ob)67
b(ject)405 b(graphs)g(in)f(Section)h(5.4.)-1600 12984
y Fw(2.3)1495 b(Non-standard)502 b(notions)-1600 15983
y Fv(In)404 b(this)h(pap)34 b(er,)404 b(w)-34 b(e)404
b(assume)h(that)g(class)f(graphs)g(are)g Ft(simple)p
Fv(,)e(formally)i(de\014ned)h(as)f(follo)-34 b(ws.)-1600
18531 y Fk(De\014nition)466 b(2.1)606 b Ft(A)434 b(class)e(gr)-62
b(aph)432 b Fu(G)337 b Fv(=)f(\()p Fu(V)67 b(;)202 b(E)70
b(;)202 b(L)p Fv(\))434 b Ft(is)f Fr(simple)f Ft(if)-167
21893 y(1.)605 b(for)433 b(al)62 b(l)433 b(e)-62 b(dges)432
b Fu(u)9752 21227 y Fp(l)9291 21893 y Fs(!)337 b Fu(v)380
b Fs(2)336 b Fu(E)70 b Ft(,)434 b(we)f(have)f(that)g
Fu(l)360 b Fv(=)337 b Fs(\005)433 b Ft(if)h(and)f(only)g(if)g
Fu(u)g Ft(is)g(abstr)-62 b(act,)431 b(and)-167 24545
y(2.)605 b(for)433 b(al)62 b(l)433 b(e)-62 b(dges)432
b Fu(u)9662 23879 y Fo(\005)9291 24545 y Fs(!)337 b Fu(v)380
b Fs(2)336 b Fu(E)70 b Ft(,)434 b(we)f(have)f(that)g
Fu(v)477 b Ft(is)433 b(c)-62 b(oncr)g(ete.)-1600 27758
y Fv(The)487 b(\014rst)f(requiremen)-34 b(t)486 b(sa)-34
b(ys)486 b(that)h(all)f(edges)g(going)g(out)h(from)f(abstract)h
(classes)e(are)h(sub)34 b(class)486 b(edges)g(and)h(all)-1600
29414 y(edges)462 b(going)h(out)g(from)g(concrete)f(classes)f(are)h
(reference)f(edges.)714 b(This)463 b(prop)34 b(ert)-34
b(y)462 b(is)g(called)g Ft(\015atness)p Fv(.)712 b(Flatness)-1600
31070 y(helps)470 b(us)f(map)h(paths)h(in)e(a)g(class)g(graph)h
Fu(G)f Fv(to)h(paths)g(in)g(an)f(ob)67 b(ject)471 b(graph)e(whic)-34
b(h)471 b(is)e(an)g(instance)h(of)g Fu(G)p Fv(.)733 b(The)-1600
32726 y(second)389 b(requiremen)-34 b(t)389 b(sa)-34
b(ys)389 b(that)h(all)e(sub)34 b(class)389 b(edges)g(are)g(coming)f(in)
-34 b(to)390 b(concrete)e(classes;)394 b(this)389 b(helps)g(us)h
(\014nd)g(all)-1600 34382 y(sub)34 b(classes)369 b(of)h(a)f(giv)-34
b(en)370 b(class)f(quic)-34 b(kly)-101 b(.)525 b(Note)370
b(that)g(no)g(generalit)-34 b(y)369 b(is)g(lost)g(b)-34
b(y)370 b(the)g(assumption)h(that)f(class)f(graphs)-1600
36038 y(are)404 b(simple,)f(as)h(the)h(follo)-34 b(wing)405
b(prop)34 b(osition)404 b(asserts.)-1600 38254 y Fk(Prop)39
b(osition)465 b(2.1)607 b Ft(L)-62 b(et)557 b Fu(G)563
b Fv(=)f(\()p Fu(V)67 b(;)202 b(E)70 b(;)202 b(L)p Fv(\))558
b Ft(b)-62 b(e)558 b(an)g(arbitr)-62 b(ary)556 b(class)g(gr)-62
b(aph.)930 b(Then)558 b(ther)-62 b(e)557 b(exists)f(a)i(simple)f(class)
-1600 39910 y(gr)-62 b(aph)433 b Fr(Simplify)p Fv(\()p
Fu(G)p Fv(\))340 b(=)f(\()p Fu(V)10726 39470 y Fo(0)11037
39910 y Fu(;)202 b(E)12541 39470 y Fo(0)12850 39910 y
Fu(;)g(L)p Fv(\))436 b Ft(such)d(that)g(an)j(obje)-62
b(ct)432 b(gr)-62 b(aph)434 b Fv(\012)h Ft(is)g(an)g(instanc)-62
b(e)434 b(of)g Fu(G)h Ft(if)f(and)h(only)g(if)f Fv(\012)i
Ft(is)e(an)-1600 41566 y(instanc)-62 b(e)432 b(of)h Fr(Simplify)p
Fv(\()p Fu(G)p Fv(\))p Ft(.)558 b(Mor)-62 b(e)g(over,)431
b Fs(j)p Fu(V)18465 41126 y Fo(0)18776 41566 y Fs(j)336
b Fv(=)h Fu(O)34 b Fv(\()p Fs(j)p Fu(V)269 b Fs(j)p Fv(\))433
b Ft(and)h Fs(j)p Fu(E)28370 41126 y Fo(0)28679 41566
y Fs(j)337 b Fv(=)f Fu(O)34 b Fv(\()p Fs(j)p Fu(E)70
b Fs(j)33701 41126 y Fn(2)34226 41566 y Fv(\))p Ft(.)-1600
43782 y Fv(The)551 b Fr(Simplify)f Fv(transformation)i(is)f(outlined)g
(in)g(App)34 b(endix)551 b(A.)978 b(Note)551 b(that)g(the)g(output)i
(of)e(our)g(compilation)-1600 45438 y(algorithm)381 b(is)g(a)g(set)h
(of)f(metho)34 b(ds)382 b(on)f(an)h(arbitrary)f(class)f(graph,)386
b(i.e.)380 b(it)h(need)h(not)g(b)34 b(e)380 b(simple.)531
b(An)381 b(existing)g(class)-1600 47094 y(structure)279
b(do)34 b(es)279 b(not)g(need)g(to)g(b)34 b(e)279 b(mo)34
b(di\014ed)279 b(to)g(b)34 b(e)279 b(used)g(with)h(our)e(algorithm;)321
b(it)279 b(is)f(only)h(the)g(graph)g(represen)-34 b(tation)-1600
48750 y(of)404 b(the)h(class)f(structure)g(that)i(ma)-34
b(y)404 b(need)g(to)h(b)34 b(e)404 b(pre-pro)34 b(cessed)403
b(b)-34 b(y)405 b(the)f Fr(Simplify)g Fv(transformation.)282
50966 y(De\014ne)377 b(a)f Ft(c)-62 b(oncr)g(ete)407
b(p)-62 b(ath)374 b Fv(to)j(b)34 b(e)377 b(an)f(alternating)i(sequence)
e(of)h(concrete)e(class)i(names)g(and)g(lab)34 b(els)376
b(\(excluding)-1600 52622 y Fs(\005)p Fv(\).)730 b(W)-101
b(e)467 b(shall)h(map)g(paths)h(in)f(class)f(graphs)i(to)f(concrete)f
(paths)i(b)-34 b(y)468 b(omitting)g(abstract)h(classes)e(and)i(sub)34
b(class)-1600 54278 y(edges.)670 b(W)-101 b(e)447 b(refer)h(to)g(this)h
(mapping)g(as)f(the)g Ft(natur)-62 b(al)473 b(c)-62 b(orr)g(esp)g
(ondenc)g(e)p Fv(,)455 b(and)449 b(denote)g(it)f(b)-34
b(y)448 b Fu(X)95 b Fv(\()p Fu(p)p Fv(\),)460 b(where)447
b Fu(p)h Fv(is)g(a)-1600 55934 y(path)317 b(in)e(a)g(class)g(graph)h
Fu(G)f Fv(and)h Fu(X)95 b Fv(\()p Fu(p)p Fv(\))317 b(is)e(the)g
(corresp)34 b(onding)316 b(concrete)f(path.)510 b(Similarly)-101
b(,)331 b(w)-34 b(e)316 b(denote)g(the)g(concrete)-1600
57590 y(path)404 b(resulting)e(from)h(taking)f(the)h(sequence)f(of)h
(class)f(names)h(and)g(edge)f(lab)34 b(els)402 b(in)g(an)h(ob)67
b(ject)403 b(graph)g(path)h Fu(p)50008 57150 y Fo(0)50721
57590 y Fv(b)-34 b(y)-1600 59246 y Fu(Y)269 b Fv(\()p
Fu(p)454 58806 y Fo(0)765 59246 y Fv(\),)366 b(and)358
b(\(o)-34 b(v)g(erloading)358 b(the)f(term\))h(w)-34
b(e)357 b(call)f(this)i(mapping)g(also)f(a)g Ft(natur)-62
b(al)389 b(c)-62 b(orr)g(esp)g(ondenc)g(e)p Fv(.)519
b(The)358 b(motiv)-67 b(ation)-1600 60902 y(for)394 b(these)h
(de\014nitions)g(is)f(that)h(if)f Fu(p)g Fv(is)g(a)g(path)h(in)f(a)g
(class)g(graph)g Fu(G)p Fv(,)i(then)f(there)f(is)g(some)g(ob)67
b(ject)395 b(graph)g(\012)f(whic)-34 b(h)-1600 62558
y(is)404 b(an)g(instance)h(of)f Fu(G)p Fv(,)g(and)h(a)f(path)h
Fu(p)15902 62118 y Fo(0)16617 62558 y Fv(in)f(\012,)g(suc)-34
b(h)405 b(that)g Fu(X)95 b Fv(\()p Fu(p)p Fv(\))338 b(=)f
Fu(Y)269 b Fv(\()p Fu(p)31330 62118 y Fo(0)31640 62558
y Fv(\).)282 64924 y(F)-101 b(or)404 b(a)g(class)g(graph)h(path)g(set)f
Fu(P)168 b Fv(,)404 b(de\014ne)h Fu(X)95 b Fv(\()p Fu(P)168
b Fv(\))22981 64258 y Fn(def)23159 64924 y Fv(=)514 b
Fs(f)q Fu(X)95 b Fv(\()p Fu(p)p Fv(\))337 b Fs(j)g Fu(p)f
Fs(2)h Fu(P)168 b Fs(g)p Fv(.)24897 75628 y(9)p eop
%%Page: 10 11
10 10 bop -1600 2325 a Fx(3)1793 b(De\014nition)599 b(of)f(tra)-50
b(v)g(ersals)-1600 5741 y Fv(W)-101 b(e)373 b(no)-34
b(w)374 b(arriv)-34 b(e)373 b(at)g(the)h(cen)-34 b(tral)373
b(topic)h(of)g(this)g(pap)34 b(er:)523 b(tra)-34 b(v)g(ersals)373
b(of)h(ob)67 b(ject)374 b(graphs.)529 b(Informally)-101
b(,)379 b(a)373 b(tra)-34 b(v)g(ersal)373 b(is)-1600
7397 y(a)447 b(\(p)34 b(ossibly)447 b(in\014nite\))h(set)e(of)i
(concrete)e(paths;)469 b(when)447 b(used)h(in)f(conjunction)h(with)f
(an)h(ob)67 b(ject)447 b(graph,)458 b(it)447 b(results)-1600
9053 y(in)383 b(a)g(sequence)f(of)i(ob)67 b(jects,)388
b(called)382 b(the)h Ft(tr)-62 b(aversal)412 b(history)p
Fv(.)529 b(The)383 b(tra)-34 b(v)g(ersal)383 b(history)g(is)g(a)g
(depth-\014rst)i(tra)-34 b(v)g(ersal)383 b(of)-1600 10709
y(the)393 b(ob)67 b(ject)394 b(graph)f(along)g(ob)67
b(ject)394 b(paths)g(agreeing)e(with)i(the)f(giv)-34
b(en)392 b(concrete)g(path)i(set.)535 b(T)-101 b(o)393
b(mak)-34 b(e)393 b(the)g(tra)-34 b(v)g(ersal)-1600 12365
y(useful,)397 b(eac)-34 b(h)396 b(ob)67 b(ject)396 b(has)g(a)f(sp)34
b(ecial)394 b Ft(visit)g Fv(metho)34 b(d)396 b(attac)-34
b(hed)396 b(to)g(it;)i(when)e(an)f(ob)67 b(ject)397 b(is)e(added)h(to)f
(the)h(tra)-34 b(v)g(ersal)-1600 14021 y(history)-101
b(,)431 b(this)c(metho)34 b(d)427 b(is)f(in)-34 b(v)g(ok)g(ed.)605
b(\(A)426 b(more)g(comprehensiv)-34 b(e)426 b(discussion)h(of)f(the)h
(Visitor)f(design)g(pattern)h(and)-1600 15677 y(visitor)404
b(metho)34 b(ds)404 b(can)h(b)34 b(e)403 b(found)j(in)e([GHJV95,)g
(SPL96,)g(SPL98].\))282 17893 y(But)365 b(\014rst,)373
b(w)-34 b(e)366 b(de\014ne)f(tra)-34 b(v)g(ersals)365
b(formally)-101 b(.)525 b(The)365 b(de\014nition)h(here)f(is)f(adapted)
j(from)e(the)g(\\simpli\014ed)h(seman-)-1600 19549 y(tics")372
b(from)g([PPL97].)527 b(W)-101 b(e)372 b(use)g(a)g(few)h(tec)-34
b(hnical)372 b(notions.)529 b(F)-101 b(or)372 b(a)g(set)h(of)f
(sequences)g Fu(R)346 b Fs(\022)337 b Fv(\006)41430 19109
y Fo(\003)42328 19549 y Fv(for)372 b(an)h(alphab)34 b(et)373
b(\006,)-1600 21205 y(de\014ne)13741 24073 y Fr(head)q
Fv(\()p Fu(R)9 b Fv(\))1108 b(=)f Fs(f)p Fu(x)336 b Fs(2)h
Fv(\006)g Fs(j)f(9)p Fu(\013)t(:)p Fv(\()p Fu(x\013)343
b Fs(2)337 b Fu(R)9 b Fv(\))p Fs(g)13284 26061 y Fr(tail)o
Fv(\()p Fu(R)g(;)202 b(x)p Fv(\))1108 b(=)f Fs(f)p Fu(\013)341
b Fs(j)c Fu(x\013)k Fs(2)c Fu(R)414 b Fv(for)404 b(some)g
Fu(x)336 b Fs(2)h Fv(\006)p Fs(g)405 b Fu(:)-1600 28928
y Fv(In)-34 b(tuitiv)g(ely)-101 b(,)322 b Fr(head)q Fv(\()p
Fu(R)9 b Fv(\))304 b(is)d(the)i(set)f(of)h(all)e(\014rst)i(elemen)-34
b(ts)302 b(of)g Fu(R)9 b Fv(,)323 b(and)303 b Fr(tail)o
Fv(\()p Fu(R)9 b(;)202 b(x)p Fv(\))303 b(is)f(the)h(set)f(of)g(all)g
(\\tails")g(of)g(sequences)-1600 30584 y(of)404 b Fu(R)414
b Fv(that)406 b(start)e(with)h Fu(x)f Fv(\(where)g(a)h(tail)e(of)i(a)f
(sequence)g(is)f(the)i(whole)f(sequence)g(except)g(its)g(\014rst)h
(elemen)-34 b(t\).)282 32800 y(In)470 b(the)g(de\014nition)i(b)34
b(elo)-34 b(w,)486 b(w)-34 b(e)470 b(assume)h(that)g(there)f(exists)g
(a)g(total)g(order)g Fs(\036)g Fv(on)g(the)h(set)f(of)g(\014eld)h
(names)f Fs(L)-1600 34456 y Fv(\(this)414 b(assumption)h(ma)-34
b(y)414 b(b)34 b(e)413 b(w)-34 b(eak)g(ened)414 b(somewhat\).)568
b(W)-101 b(e)412 b(\014rst)i(giv)-34 b(e)413 b(the)h(formal)f
(de\014nition,)j(then)f(explain)e(it)g(in)-1600 36112
y(w)-34 b(ords.)-1600 38660 y Fk(De\014nition)466 b(3.1)f(\(from)f
([PPL97)q(]\))606 b Ft(Fix)512 b(a)g(class)e(gr)-62 b(aph)510
b Fu(G)p Ft(.)793 b(If)512 b Fv(\012)g Ft(is)f(an)i(acyclic)c(obje)-62
b(ct)510 b(gr)-62 b(aph)510 b(which)h(is)g(an)-1600 40316
y(instanc)-62 b(e)560 b(of)g Fu(G)p Ft(,)592 b Fu(o)561
b Ft(an)g(obje)-62 b(ct)558 b(in)k Fv(\012)p Ft(,)593
b Fu(R)570 b Ft(a)561 b(set)f(of)g(c)-62 b(oncr)g(ete)559
b(p)-62 b(aths)559 b(c)-62 b(orr)g(esp)g(onding)558 b(to)i(p)-62
b(aths)559 b(of)h Fu(G)p Ft(,)593 b(and)560 b Fu(H)659
b Ft(a)-1600 41972 y(se)-62 b(quenc)g(e)431 b(of)i(obje)-62
b(cts,)431 b(then)i(the)f(judgment)21253 43628 y Fv(\012)337
b Fs(`)23206 43810 y Fp(s)24033 43628 y Fu(o)f Fv(:)g
Fu(R)279 b Fj(\003)269 b Fu(H)-1600 46000 y Ft(me)-62
b(ans)424 b(that)f(when)h(tr)-62 b(aversing)422 b(the)h(obje)-62
b(ct)422 b(gr)-62 b(aph)423 b Fv(\012)h Ft(starting)f(with)h
Fu(o)p Ft(,)h(and)f(guide)-62 b(d)422 b(by)h(the)g(c)-62
b(oncr)g(ete)423 b(p)-62 b(ath)422 b(set)i Fu(R)9 b Ft(,)-1600
47656 y(then)433 b Fu(H)532 b Ft(is)433 b(the)f Fr(traversal)404
b(histo)-34 b(ry)p Ft(.)14372 47216 y Fn(1)15455 47656
y Ft(This)433 b(judgment)f(holds)f(when)j(it)f(is)g(derivable)d(using)j
(the)f(fol)62 b(lowing)433 b(rules:)p 8259 50243 7281
45 v 8259 51355 a Fv(\012)337 b Fs(`)10212 51537 y Fp(s)11039
51355 y Fu(o)f Fv(:)g Fu(R)279 b Fj(\003)269 b Fu(\017)18140
50523 y Ft(if)433 b Fr(tail)o Fv(\()p Fu(R)9 b(;)202
b Fr(Class)q Fv(\()p Fu(o)p Fv(\)\))337 b(=)f Fs(;)p
Ft(,)20424 b Fv(\(1\))-1600 53754 y Ft(wher)-62 b(e)433
b Fu(\017)h Ft(denotes)d(the)i(empty)f(history,)f(and)-1427
57176 y Fv(\012)337 b Fs(`)526 57358 y Fp(s)1353 57176
y Fu(o)1941 57358 y Fp(i)2653 57176 y Fv(:)f Fr(tail)p
Fv(\()p Fr(tail)o Fv(\()p Fu(R)9 b(;)202 b Fr(Class)q
Fv(\()p Fu(o)p Fv(\)\))p Fu(;)g(l)14414 57358 y Fp(i)14790
57176 y Fv(\))269 b Fj(\003)h Fu(H)17751 57358 y Fp(i)20646
57176 y Fs(8)p Fu(i)336 b Fs(2)h Fv(1)p Fu(::n)p -1427
57715 26653 45 v 4809 58827 a Fv(\012)g Fs(`)6762 59009
y Fp(s)7589 58827 y Fu(o)f Fv(:)h Fu(R)279 b Fj(\003)269
b Fu(o)g Fs(\001)g Fu(H)14069 59009 y Fn(1)14864 58827
y Fs(\001)g Fu(:::)f Fs(\001)h Fu(H)18363 59009 y Fp(n)27825
56221 y Ft(if)433 b Fr(head)q Fv(\()p Fr(tail)p Fv(\()p
Fu(R)9 b(;)202 b Fr(Class)p Fv(\()p Fu(o)p Fv(\)\)\))338
b(=)f Fs(f)p Fu(l)43020 56403 y Fp(i)43732 56221 y Fs(j)f
Fu(i)g Fs(2)h Fv(1)p Fu(::n)p Fs(g)p Ft(,)27825 58063
y Fu(o)29039 57361 y Fp(l)29320 57496 y Fm(i)28749 58063
y Fs(!)g Fu(o)30886 58245 y Fp(i)31695 58063 y Ft(is)433
b(in)h Fv(\012)p Fu(;)202 b(i)336 b Fs(2)h Fv(1)p Fu(::n)p
Ft(,)433 b(and)27825 59719 y Fu(l)28187 59901 y Fp(j)29010
59719 y Fs(\036)337 b Fu(l)30652 59916 y Fp(k)31654 59719
y Ft(for)433 b Fv(1)337 b Fs(\024)f Fu(j)407 b(<)336
b(k)375 b Fs(\024)336 b Fu(n)p Ft(.)50451 61093 y Fv(\(2\))-1600
63640 y(In)416 b(other)f(w)-34 b(ords,)419 b(a)d(tra)-34
b(v)g(ersal)415 b(of)h(an)g(ob)67 b(ject)416 b(graph)g(\012)g(starting)
g(with)h(an)e(ob)67 b(ject)417 b Fu(o)e Fv(guided)h(b)-34
b(y)416 b(a)f(path)i(set)f Fu(R)9 b Fv(,)418 b(is)-1600
65296 y(done)464 b(as)f(follo)-34 b(ws.)715 b(First,)478
b(the)463 b(\014rst)h(elemen)-34 b(ts)463 b(of)g(the)h(sequences)e(of)i
Fu(R)472 b Fv(are)463 b(compared)g(to)g Fr(Class)p Fv(\()p
Fu(o)p Fv(\):)656 b(sequences)-1600 66952 y(b)34 b(eginning)437
b(with)f(another)h(elemen)-34 b(t)436 b(are)g(immediately)f(thro)-34
b(wn)438 b(out)e(of)h(consideration.)634 b(If)436 b(the)h(remaining)f
(path)-1600 68608 y(set)328 b(is)g(not)h(empt)-34 b(y)-101
b(,)343 b(then)329 b Fu(o)f Fv(b)34 b(ecomes)327 b(the)i(\014rst)f
(elemen)-34 b(t)328 b(of)h(the)f(history;)353 b(it)328
b(is)g(follo)-34 b(w)g(ed)329 b(b)-34 b(y)328 b(the)h(histories)f
(resulting)-1600 70264 y(from)504 b(starting)g(a)f(tra)-34
b(v)g(ersal)503 b(from)h(eac)-34 b(h)504 b(descenden)-34
b(t)504 b(of)g Fu(o)p Fv(,)527 b(guided)504 b(b)-34 b(y)504
b(the)g(remainder)f(of)h(the)g(path)g(set)g(after)p -1600
71081 21440 45 v -218 71884 a Fi(1)243 72307 y Fy(The)341
b(lab)28 b(el)343 b Fh(s)e Fy(of)h(the)f(turnstile)h(indicates)h
(\\seman)-28 b(tics.")24594 75628 y Fv(10)p eop
%%Page: 11 12
11 11 bop -1600 2325 a Fv(\\p)34 b(eeling)474 b(o\013)94
b(")475 b(the)g(\014rst)h(t)-34 b(w)g(o)476 b(elemen)-34
b(ts)475 b(\(corresp)34 b(onding)475 b(to)g Fu(o)f Fv(and)i(the)f(edge)
g(going)g(out)g(to)g(the)h(descenden)-34 b(t\).)-1600
3981 y(In)g(tuitiv)g(ely)-101 b(,)334 b(this)317 b(pro)34
b(cedure)317 b(is)f(depth-\014rst)j(searc)-34 b(h)317
b(on)g(\012)g(with)g Fu(R)327 b Fv(used)317 b(to)g(determine)g(ho)-34
b(w)318 b(to)f(prune)g(the)g(searc)-34 b(h.)-1600 5637
y(Please)356 b(note)i(that)h(concatenation)f(of)f(tra)-34
b(v)g(ersal)358 b(histories)f(do)34 b(es)357 b(not)h(use)f(the)h(same)f
(de\014nition)i(as)e(concatenation)-1600 7293 y(of)404
b(paths;)i(it)e(is)g(the)g(usual)h(concatenation)g(of)f(sequences.)
-1600 11205 y Fk(Remarks.)1211 b Fv(Note)409 b(that)g(the)f(guaran)-34
b(tee)409 b(made)f(b)-34 b(y)408 b(a)g(tra)-34 b(v)g(ersal)408
b(guided)g(b)-34 b(y)409 b(a)e(path)j(set)e Fu(R)417
b Fv(is)408 b(the)g(follo)-34 b(wing:)547 b(A)-1600 12861
y(path)409 b Fu(p)f Fv(in)g(the)h(ob)67 b(ject)409 b(graph)f(is)g
(follo)-34 b(w)g(ed)409 b(so)f(long)h(as)f(there)g(is)f(a)i(path)g
Fu(q)387 b Fs(2)343 b Fu(R)418 b Fv(suc)-34 b(h)409 b(that)g
Fu(q)451 b Fv(has)409 b(a)f(pre\014x)g(whic)-34 b(h)-1600
14517 y(is)408 b(equal)h(to)g(the)g(curren)-34 b(t)409
b(pre\014x)f(of)h Fu(p)g Fv(\(taking)g(the)g Fr(Class)p
Fv(\()p Fu(o)p Fv(\))g(instead)g(of)g Fu(o)f Fv(in)h
Fu(p)p Fv(\).)552 b(In)409 b(other)g(w)-34 b(ords,)410
b(the)f(decision)-1600 16173 y(whether)444 b(the)f(tra)-34
b(v)g(ersal)443 b(tak)-34 b(es)443 b(a)g(certain)g(branc)-34
b(h)444 b(in)f(the)g(ob)67 b(ject)444 b(graph)g(dep)34
b(ends)443 b(only)g(on)g(the)h(p)34 b(ortion)443 b(of)g(the)-1600
17829 y(graph)g(visited)e(so)i(far)f(and)h(on)f(the)h(curren)-34
b(t)442 b(branc)-34 b(h,)452 b(and)443 b(not)g(on)g(the)f(links)g
(further)h(ahead.)653 b(This)442 b(means,)452 b(for)-1600
19485 y(example,)423 b(that)e(ev)-34 b(en)420 b(if)g(all)g(paths)h(in)f
Fu(R)430 b Fv(end)420 b(with)h(the)g(same)f(class)f Fu(A)p
Fv(,)424 b(some)c(of)h(the)f(tra)-34 b(v)g(ersal)420
b(paths)h(ma)-34 b(y)420 b(end)-1600 21141 y(with)391
b(a)f(no)34 b(de)390 b Fu(o)f Fv(with)i Fr(Class)p Fv(\()p
Fu(o)p Fv(\))337 b Fs(6)p Fv(=)f Fu(A)390 b Fv(just)i(b)34
b(ecause)389 b(the)i(path)g(to)f Fu(o)g Fv(is)f(a)h(pre\014x)g(of)g(a)g
(path)h(in)f Fu(R)9 b Fv(.)535 b(This)390 b(relaxation)-1600
22797 y(is)427 b(necessary)f(to)h(enable)g(e\016cien)-34
b(t)426 b(implemen)-34 b(tation)428 b(of)g(tra)-34 b(v)g(ersals)426
b(b)-34 b(y)428 b(lo)34 b(oking)426 b(only)g(ahead)i(in)f(the)g(class)f
(graph)-1600 24453 y(and)405 b(not)g(in)f(the)h(ob)67
b(ject)405 b(graph)f(as)g(discussed)h(earlier.)-1600
29031 y Fx(4)1793 b(Strategies:)799 b(Sp)50 b(eci\014cation)599
b(of)e(tra)-50 b(v)g(ersals)-1600 32448 y Fv(In)500 b(this)h(section)f
(w)-34 b(e)501 b(de\014ne)g(strategies,)524 b(whic)-34
b(h)501 b(are)f(a)g(graph-based)i(language)f(for)f(expressing)g(tra)-34
b(v)g(ersals.)827 b(In)-1600 34104 y(Section)347 b(4.1)g(w)-34
b(e)347 b(giv)-34 b(e)346 b(a)h(basic)g(de\014nition)h(of)f(strategies)
g(and)g(explain)g(ho)-34 b(w)348 b(strategies)f(express)f(tra)-34
b(v)g(ersals.)519 b(Then,)-1600 35760 y(in)336 b(Section)g(4.2,)349
b(w)-34 b(e)336 b(giv)-34 b(e)335 b(the)i(full)f(de\014nition)g(of)h
(strategies)e(using)i(the)f(additional)h(concept)f(of)g(a)g(constrain)
-34 b(t)337 b(map.)-1600 37416 y(This)449 b(extended)f(notion)i(is)d
(the)i(one)f(w)-34 b(e)449 b(shall)f(b)34 b(e)448 b(using)h(in)f(the)h
(remainder)e(of)i(the)f(pap)34 b(er.)671 b(In)448 b(Section)h(4.3,)459
b(w)-34 b(e)-1600 39072 y(discuss)405 b(a)f(few)g(p)34
b(ossible)404 b(additional)h(re\014nemen)-34 b(ts)405
b(of)g(the)f(concept)h(of)f(strategies.)-1600 43033 y
Fw(4.1)1495 b(Strategies)-1600 46032 y Fv(T)-101 b(ra)-34
b(v)g(ersals)402 b(are)f(de\014ned)i(in)f(terms)g(of)h(sets)f(of)g
(concrete)f(paths.)540 b(Strategies)402 b(select)f(class)h(graph)g
(paths)h(and)g(then)-1600 47688 y(deriv)-34 b(e)543 b(concrete)f(paths)
j(b)-34 b(y)544 b(applying)f(the)h(natural)g(corresp)34
b(ondence.)956 b(In)-34 b(tuitiv)g(ely)-101 b(,)578 b(a)543
b(strategy)h(selects)e(class)-1600 49344 y(graph)464
b(paths)g(b)-34 b(y)464 b(sp)34 b(ecifying)463 b(a)g(high-lev)-34
b(el)462 b(top)34 b(ology)464 b(whic)-34 b(h)464 b(spans)g(all)e(paths)
j(in)e(the)h(selected)e(set.)716 b(F)-101 b(ormally)g(,)-1600
51000 y(strategies)404 b(are)g(de\014ned)h(as)f(follo)-34
b(ws.)-1600 53548 y Fk(De\014nition)466 b(4.1)606 b Ft(A)460
b Fr(strategy)f Fs(S)550 b Ft(is)459 b(a)g(triple)f Fs(S)475
b Fv(=)383 b(\()p Fu(S)s(;)202 b(s;)g(t)p Fv(\))p Ft(,)465
b(wher)-62 b(e)459 b Fu(S)454 b Fv(=)383 b(\()p Fu(C)19
b(;)202 b(D)34 b Fv(\))460 b Ft(is)f(a)g(dir)-62 b(e)g(cte)g(d)457
b(unlab)-62 b(ele)g(d)457 b(gr)-62 b(aph)-1600 55204
y(c)g(al)62 b(le)-62 b(d)427 b(the)h Fr(strategy)399
b(graph)p Ft(,)431 b(wher)-62 b(e)428 b Fu(C)516 b Ft(is)429
b(the)f(set)g(of)h Fr(strategy)398 b(graph)j(no)34 b(des)429
b Ft(and)f Fu(D)463 b Ft(is)428 b(the)h(set)f(of)g Fr(strategy)399
b(graph)-1600 56860 y(edges)p Ft(,)433 b(and)g Fu(s;)202
b(t)336 b Fs(2)h Fu(C)521 b Ft(ar)-62 b(e)433 b(the)f
Fr(source)h Ft(and)h Fr(ta)-34 b(rget)433 b Ft(of)g Fs(S)91
b Ft(,)434 b(r)-62 b(esp)g(e)g(ctively.)-1600 59408 y
Fv(The)405 b(connection)f(b)34 b(et)-34 b(w)g(een)405
b(strategies)f(and)h(class)f(graphs)h(is)f(done)g(b)-34
b(y)405 b(a)f(name)g(map,)h(de\014ned)g(as)f(follo)-34
b(ws.)-1600 61956 y Fk(De\014nition)466 b(4.2)606 b Ft(L)-62
b(et)482 b Fu(S)494 b Fv(=)424 b(\()p Fu(C)19 b(;)202
b(D)34 b Fv(\))483 b Ft(b)-62 b(e)481 b(a)g(str)-62 b(ate)g(gy)480
b(gr)-62 b(aph)480 b(and)i(let)f Fu(G)424 b Fv(=)g(\()p
Fu(V)67 b(;)202 b(E)70 b(;)202 b(L)p Fv(\))482 b Ft(b)-62
b(e)481 b(a)h(class)e(gr)-62 b(aph.)701 b(A)482 b Fr(name)-1600
63612 y(map)462 b Ft(for)f Fu(S)531 b Ft(and)461 b Fu(G)g
Ft(is)g(a)g(function)f Fs(N)565 b Fv(:)386 b Fu(C)474
b Fs(!)387 b Fu(V)269 b Ft(.)641 b(If)461 b Fu(p)g Ft(is)g(a)g(se)-62
b(quenc)g(e)458 b(of)j(str)-62 b(ate)g(gy)459 b(gr)-62
b(aph)459 b(no)-62 b(des,)467 b(then)461 b Fs(N)179 b
Fv(\()p Fu(p)p Fv(\))461 b Ft(is)-1600 65268 y(the)432
b(se)-62 b(quenc)g(e)432 b(of)h(class)e(no)-62 b(des)433
b(obtaine)-62 b(d)431 b(by)i(applying)e Fs(N)612 b Ft(to)433
b(e)-62 b(ach)432 b(element)g(of)h Fu(p)p Ft(.)282 67817
y Fv(The)297 b(basic)g(idea)g(of)g(strategies)g(is)f(that)i(under)g(a)f
(name)g(map,)318 b(a)297 b(path)h(in)f(the)h(strategy)f(graph)g(is)g
(an)g(abstraction)-1600 69473 y(of)538 b(a)g(set)g(of)g(paths)h(in)e
(the)h(class)g(graph.)940 b(This)538 b(is)f(done)i(b)-34
b(y)538 b(viewing)f(eac)-34 b(h)538 b(strategy)g(graph)g(edge)g
Fu(a)559 b Fs(!)g Fu(b)538 b Fv(as)-1600 71129 y(represen)-34
b(ting)480 b(the)g(set)g(of)g(paths)h(in)f(the)g(class)f(graph)h
(starting)h(with)f(no)34 b(de)480 b Fs(N)179 b Fv(\()p
Fu(a)p Fv(\))480 b(and)g(ending)g(at)g(no)34 b(de)480
b Fs(N)179 b Fv(\()p Fu(b)p Fv(\).)24594 75628 y(11)p
eop
%%Page: 12 13
12 12 bop -1600 2325 a Fv(This)468 b(represen)-34 b(tation)468
b(naturally)f(extends)h(to)g(paths)g(in)g(the)f(strategy)h(graph:)665
b(A)467 b(path)i(in)e(the)h(strategy)f(graph)-1600 3981
y(represen)-34 b(ts)468 b(a)h(set)f(of)g(paths)i(in)e(the)g(class)g
(graph)h(obtained)g(b)-34 b(y)469 b(concatenating)g(the)f(sets)h(of)f
(class)g(graph)h(paths)-1600 5637 y(obtained)405 b(from)g(eac)-34
b(h)404 b(strategy)g(graph)h(edge.)282 7853 y(W)-101
b(e)403 b(no)-34 b(w)406 b(mak)-34 b(e)404 b(this)g(in)-34
b(tuition)406 b(formal)e(using)h(the)f(concept)h(of)f(path)h
(expansion,)g(de\014ned)g(as)f(follo)-34 b(ws.)-1600
10401 y Fk(De\014nition)466 b(4.3)606 b Ft(Given)578
b(a)h(nontrivial)e(se)-62 b(quenc)g(e)577 b Fu(p)p Ft(,)615
b(a)578 b(se)-62 b(quenc)g(e)577 b(is)h(c)-62 b(al)62
b(le)-62 b(d)577 b(an)h Fr(expansion)i Ft(of)e Fu(p)h
Ft(if)f(it)g(c)-62 b(an)579 b(b)-62 b(e)-1600 12057 y(obtaine)g(d)404
b(by)h(inserting)g(one)h(or)g(mor)-62 b(e)406 b(elements)e(b)-62
b(etwe)g(en)405 b(the)g(elements)g(of)h Fu(p)p Ft(.)548
b(The)405 b(only)h(exp)-62 b(ansion)405 b(of)g(a)h(trivial)-1600
13713 y(se)-62 b(quenc)g(e)431 b(is)i(itself.)-1600 16261
y Fv(Note)471 b(that)h(if)f Fu(p)5877 15821 y Fo(0)6658
16261 y Fv(is)g(a)g(path)h(whic)-34 b(h)471 b(is)g(an)g(expansion)h(of)
f(another)h(path)g Fu(p)e Fv(\(p)34 b(ossibly)471 b(in)g(another)h
(graph\),)488 b(then)-1600 17917 y Fr(Source)p Fv(\()p
Fu(p)p Fv(\))338 b(=)e Fr(Source)p Fv(\()p Fu(p)9444
17477 y Fo(0)9755 17917 y Fv(\))405 b(and)g Fr(T)-101
b(a)-34 b(rget)p Fv(\()p Fu(p)p Fv(\))337 b(=)g Fr(T)-101
b(a)-34 b(rget)p Fv(\()p Fu(p)23776 17477 y Fo(0)24087
17917 y Fv(\).)282 20133 y(W)-101 b(e)298 b(no)-34 b(w)301
b(formally)d(de\014ne)i(the)g(basic)f(w)-34 b(a)g(y)300
b(strategies)f(express)f(paths)j(in)e(ob)67 b(ject)300
b(graphs.)504 b(Recall)299 b(that)h Fu(P)48724 20321
y Fp(G)49513 20133 y Fv(\()p Fu(s;)202 b(t)p Fv(\))-1600
21789 y(denotes)431 b(that)g(set)g(of)f(all)g(paths)h(in)f
Fu(G)h Fv(starting)g(at)f Fu(s)g Fv(and)h(ending)g(at)g
Fu(t)f Fv(and)h Fu(X)525 b Fv(is)430 b(the)h(natural)f(corresp)34
b(ondence)-1600 23445 y(mapping)405 b(class)f(graph)h(paths)g(to)g
(concrete)e(paths.)-1600 25993 y Fk(De\014nition)466
b(4.4)606 b Ft(L)-62 b(et)379 b Fs(S)427 b Fv(=)337 b(\()p
Fu(S)s(;)202 b(s;)g(t)p Fv(\))378 b Ft(b)-62 b(e)378
b(a)g(str)-62 b(ate)g(gy,)387 b(let)377 b Fu(G)337 b
Fv(=)f(\()p Fu(V)67 b(;)202 b(E)70 b(;)202 b(L)p Fv(\))379
b Ft(b)-62 b(e)378 b(a)g(class)e(gr)-62 b(aph,)388 b(and)378
b(let)g Fs(N)556 b Ft(b)-62 b(e)378 b(a)g(name)-1600
27649 y(map)433 b(for)g Fs(S)525 b Ft(and)433 b Fu(G)p
Ft(.)557 b(Then)-785 30523 y Fs(S)91 b Fv([)p Fu(G;)202
b Fs(N)179 b Fv(])335 b(=)4994 29268 y Fg(n)5732 30523
y Fu(X)95 b Fv(\()p Fu(p)7912 30023 y Fo(0)8223 30523
y Fv(\))337 b Fs(j)g Fu(p)10315 30023 y Fo(0)10962 30523
y Fs(2)f Fu(P)12884 30711 y Fp(G)13673 30523 y Fv(\()p
Fs(N)179 b Fv(\()p Fu(s)p Fv(\))p Fu(;)202 b Fs(N)179
b Fv(\()p Fu(t)p Fv(\)\))434 b Ft(and)f Fs(9)p Fu(p)337
b Fs(2)g Fu(P)26723 30711 y Fp(S)27400 30523 y Fv(\()p
Fu(s;)202 b(t)p Fv(\))434 b Ft(such)e(that)g Fu(p)36166
30023 y Fo(0)36910 30523 y Ft(is)h(an)h(exp)-62 b(ansion)432
b(of)h Fs(N)179 b Fv(\()p Fu(p)p Fv(\))49677 29268 y
Fg(o)50849 30523 y Fu(:)-1600 33957 y Fv(Note)474 b(that)h
Fs(S)91 b Fv([)p Fu(G;)202 b Fs(N)179 b Fv(])473 b(is)g(a)h(set)h(of)f
(concrete)f(paths:)680 b(in)-34 b(tuitiv)g(ely)-101 b(,)491
b(\014rst)475 b(a)f(set)g(of)g(class)g(graph)h(paths)g(is)f(selected,)
-1600 35613 y(and)467 b(then)g(the)f(natural)h(corresp)34
b(ondence)465 b(is)h(applied)h(to)f(obtain)h(concrete)e(paths.)726
b(These)466 b(concrete)g(paths)h(can)-1600 37269 y(b)34
b(e)404 b(used)h(\(pla)-34 b(ying)404 b(the)h(role)e(of)i(\\)p
Fu(R)9 b Fv("\))405 b(in)f(De\014nition)h(3.1.)-1600
41230 y Fw(4.2)1495 b(Using)500 b(a)e(constrain)-42 b(t)501
b(map)-1600 44229 y Fv(Strategies)458 b(imp)34 b(ose)458
b(p)34 b(ositiv)-34 b(e)458 b(constrain)-34 b(ts)460
b(on)f(paths,)472 b(in)459 b(the)f(sense)h(that)g(they)f(sp)34
b(ecify)458 b(whic)-34 b(h)459 b(no)34 b(des)459 b(m)-34
b(ust)459 b(b)34 b(e)-1600 45885 y(tra)-34 b(v)g(ersed)446
b(in)g(whic)-34 b(h)447 b(order.)664 b(It)446 b(turns)h(out)g(that)g
(it)g(is)e(quite)h(useful)h(to)f(also)g(ha)-34 b(v)g(e)447
b(negativ)-34 b(e)446 b(constrain)-34 b(ts:)624 b(what)-1600
47541 y(no)34 b(des)494 b(and)h(edges)f(cannot)h(b)34
b(e)494 b(used)h(b)34 b(et)-34 b(w)g(een)495 b(the)f(sp)34
b(eci\014ed)494 b(milestones.)808 b(W)-101 b(e)494 b(formalize)f(this)i
(idea)f(with)g(the)-1600 49197 y(concepts)405 b(of)f(elemen)-34
b(t)404 b(predicates)g(and)h(constrain)-34 b(t)405 b(maps.)-1600
51745 y Fk(De\014nition)466 b(4.5)606 b Ft(Given)400
b(a)h(class)e(gr)-62 b(aph)399 b Fu(G)337 b Fv(=)f(\()p
Fu(V)67 b(;)202 b(E)70 b(;)202 b(L)p Fv(\))p Ft(,)408
b(an)400 b Fr(element)368 b(p)-34 b(redicate)400 b Fu(E)70
b(P)570 b Ft(for)400 b Fu(G)h Ft(is)f(a)g(pr)-62 b(e)g(dic)g(ate)398
b(over)-1600 53401 y Fu(V)514 b Fs([)245 b Fu(E)70 b
Ft(.)553 b(Given)422 b(a)f(str)-62 b(ate)g(gy)420 b(gr)-62
b(aph)421 b Fu(S)70 b Ft(,)424 b(a)e(function)f Fs(B)460
b Ft(mapping)421 b(e)-62 b(ach)420 b(e)-62 b(dge)421
b(of)g Fu(S)493 b Ft(to)421 b(an)i(element)e(pr)-62 b(e)g(dic)g(ate)419
b(for)j Fu(G)-1600 55057 y Ft(is)433 b(c)-62 b(al)62
b(le)-62 b(d)431 b(a)j Fr(constraint)403 b(map)435 b
Ft(for)e Fu(S)503 b Ft(and)434 b Fu(G)p Ft(.)-1600 57605
y Fv(\(Of)418 b(course,)i(some)e(predicate)f(sp)34 b(eci\014cation)418
b(languages)g(ma)-34 b(y)418 b(b)34 b(e)417 b(v)-34 b(ery)417
b(hard)h(to)g(compute.)580 b(F)-101 b(or)418 b(computational)-1600
59261 y(complexit)-34 b(y)376 b(purp)34 b(oses,)383 b(w)-34
b(e)377 b(assume)g(that)h(there)f(exists)f(a)h(parameter,)382
b(denoted)c Fu(\034)137 b Fv(,)382 b(suc)-34 b(h)377
b(that)h(giv)-34 b(en)377 b(an)g(elemen)-34 b(t)-1600
60917 y(of)416 b Fu(G)p Fv(,)i(determining)d(whether)i(it)e
(satis\014es)h(an)g(elemen)-34 b(t)415 b(predicate)h(can)f(b)34
b(e)415 b(computed)i(in)e(no)h(more)f(than)i Fu(\034)552
b Fv(time)-1600 62573 y(units.\))282 64789 y(The)423
b(constrain)-34 b(t)423 b(map)g(is)f(used)h(to)f(sp)34
b(ecify)-101 b(,)426 b(for)c(eac)-34 b(h)423 b(edge)f(in)g(the)h
(strategy)f(graph,)427 b(whic)-34 b(h)424 b(elemen)-34
b(ts)422 b(of)h(the)-1600 66445 y(class)401 b(graph)h(ma)-34
b(y)402 b(b)34 b(e)401 b(used)h(in)g(the)g(tra)-34 b(v)g(ersal)401
b(corresp)34 b(onding)402 b(to)f(that)i(edge.)537 b(F)-101
b(ormally)g(,)401 b(w)-34 b(e)402 b(ha)-34 b(v)g(e)402
b(the)g(follo)-34 b(wing)-1600 68101 y(de\014nition.)-1600
70650 y Fk(De\014nition)466 b(4.6)606 b Ft(L)-62 b(et)426
b Fu(S)496 b Ft(b)-62 b(e)424 b(a)i(str)-62 b(ate)g(gy)423
b(gr)-62 b(aph,)425 b(let)g Fu(G)h Ft(b)-62 b(e)425 b(a)g(class)f(gr)
-62 b(aph,)425 b(let)g Fs(N)603 b Ft(b)-62 b(e)425 b(a)h(name)f(map)g
(for)g Fu(S)496 b Ft(and)425 b Fu(G)p Ft(,)-1600 72306
y(and)493 b(let)f Fs(B)531 b Ft(b)-62 b(e)492 b(a)h(c)-62
b(onstr)g(aint)492 b(map)g(for)h Fu(S)563 b Ft(and)493
b Fu(G)p Ft(.)736 b(Given)493 b(a)g(str)-62 b(ate)g(gy)490
b(gr)-62 b(aph)492 b(no)-62 b(de)492 b(p)-62 b(ath)492
b Fu(p)445 b Fv(=)f Fs(h)q Fu(a)44509 72488 y Fn(0)45034
72306 y Fu(a)45675 72488 y Fn(1)46403 72306 y Fu(:)202
b(:)g(:)f(a)48660 72488 y Fp(n)49286 72306 y Fs(i)p F