Last updated August 6, 1996.Brian Grant (grant@cs.washington.edu)
These are graphs I made up to test my various block-reorder algorithms.
Simple case #1:
|
D
/ \
S C
/ \ |
A B |
\ / |
M |
\ /
Z
|
Edge ME with last edge:
|
D
/ \
A S
| / \
| B C
\ | /
\ \ /
\|/
Z
|
Several constant disjunctive merges:
ENTRY
|
1
|
S1
/ \
2 3
| |
S2 S3
/ \ / \
4 5 6 7
\ \ / /
\ 8 /
\ / /
9 /
\ /
10
|
EXIT
Some nonconstant disjunctive merges:
ENTRY
|
1
|
D1
/ \
2 3
| |
S2 S3
/ \ / \
4 5 6 7
\ \ / /
\ 8 /
\ / /
9 /
\ /
10
|
EXIT
A graph with edges that cut across both left and right:
|
D1
/ \
S1 D2
/ \ /|\
A | S3 E H
| |/ \| |
| B F |
| | | |
| S2 / |
\ /\___ |
C / \ /
\ / I
G /
\ /
M
|
Lotsa disjunctive merges:
|
D1
/ \
/ \
D2 S1
/ \ / \
S2 A D3 B
/||\ | /\ /
/ || | _/ \ /
D4 / | | / I
/\/ | |/ | |
C E F G | |
\ | / / | |
\ || / | /
\||/ / /
J / /
\ / /
\ / /
K /
\ /
Z
|
The following loop is an example of one with multiple entries:
|
S __
/|\ / |
A | H |
| \| |
| Q |
\ / |
D |
/ \ |
B T |
| |__|
Ensure loop is stitched iff it needs to be:
|
S1
/ \
/ S2 __
. / \ / \
. | H |
. | | |
| S3 |
| / \ |
| A B |
| \ / |
| M1 |
\ | |
\ / |
\/ |
X1 |
/ \ |
/ S4 |
/ / \ |
. . T |
. . |__|
. .
Simple, straight-line, overlapping loops:
| / \
H1 _|__
| / | |
H2 | |
| | |
T1 | |
/|\__| |
/ T2 |
/ /|_____|
. .
. .
. .
Loops can be much more convoluted, with multiple entries, multiple
tails, and overlapping loops with heads and tails on different paths:
|
_ S1 _
/ \ / \ / \
| H1 H2 |
| | | |
| \ / |
| M |
| | |
| S2 |
| / \ |
| T1 T2 |
\_/| |\_/
| |
\ /
Z
|
Another one:
____ |
/ \|
| H1 ______
| | / \
| H2 |
| | |
| S1 |
| / \ |
| D1 S2 |
|_/ \ / \ |
D2 D3 |
/ \ / \_|
| \/
| M1
\ /
\ /
M2
|
Last updated August 6, 1996.