(47steps total)
PrintForm
Definitions
Lemmas
graph
1
3
Sections
Graphs
Doc
At:
topsortl-properties
1
2
1
2
1
3
1.
the_graph:
Graph
2.
the_obj:
GraphObject(the_graph)
3.
L:
Vertices(the_graph) List
4.
i:Vertices(the_graph). (i
L)
5.
paren(Vertices(the_graph);dfsl(the_obj;L))
6.
no_repeats(Vertices(the_graph)+Vertices(the_graph);dfsl(the_obj;L))
7.
dfsl-traversal(the_graph;L;dfsl(the_obj;L))
8.
i:Vertices(the_graph). (i
L)
(inr(i)
dfsl(the_obj;L)) & (inl(i)
dfsl(the_obj;L))
9.
non-trivial-loop-free(the_graph)
10.
L1,L2:Vertices(the_graph) List. L = (L1 @ L2)
(
s1,s2:Vertices(the_graph) List. topsortl(the_obj;L) = (s2 @ s1) & (
j:Vertices(the_graph). ((j
s1)
L1-the_graph- > *j) & ((j
s2)
L2-the_graph- > *j &
L1-the_graph- > *j)))
11.
i:Vertices(the_graph), s1,s2:traversal(the_graph). (
j:Vertices(the_graph). i-the_graph- > *j
non-trivial-loop(the_graph;j))
dfsl(the_obj;L) = (s1 @ [inl(i)] @ s2)
(
j:Vertices(the_graph).
j = i
i-the_graph- > *j
(inl(j)
s2))
12.
i:
Vertices(the_graph)
13.
s1:
Vertices(the_graph) List
14.
s2:
Vertices(the_graph) List
15.
L1:
(Vertices(the_graph)+Vertices(the_graph)) List
16.
L2:
(Vertices(the_graph)+Vertices(the_graph)) List
17.
dfsl(the_obj;L) = (L1 @ L2)
(Vertices(the_graph)+Vertices(the_graph)) List
18.
mapoutl(L1) = s1
19.
L3:
(Vertices(the_graph)+Vertices(the_graph)) List
20.
L3@0:
(Vertices(the_graph)+Vertices(the_graph)) List
21.
L2 = (L3 @ L3@0)
22.
L4:
(Vertices(the_graph)+Vertices(the_graph)) List
23.
L5:
(Vertices(the_graph)+Vertices(the_graph)) List
24.
L3 = (L4 @ [inl(i)] @ L5)
25.
mapoutl(L4) = nil
26.
mapoutl(L5) = nil
27.
mapoutl(L3@0) = s2
28.
j:
Vertices(the_graph)
29.
j = i
30.
i-the_graph- > *j
31.
(inl(j)
L5 @ L3@0)
(j
s2)
By:
RWO "mapoutl_member < " -1
THEN
RWO
Thm*
L1,L2:(A+B) List. mapoutl(L1 @ L2) ~ (mapoutl(L1) @ mapoutl(L2)) -1
THEN
RWO
Thm*
x:T, l1,l2:T List. (x
l1 @ l2)
(x
l1)
(x
l2) -1
THEN
Analyze -1
Generated subgoals:
1
31.
(j
mapoutl(L5))
(j
s2)
1
step
 
2
31.
(j
mapoutl(L3@0))
(j
s2)
1
step
About:
(47steps total)
PrintForm
Definitions
Lemmas
graph
1
3
Sections
Graphs
Doc