Enumerating All Spanning Trees of a Directed Graph
An Algorithm for enumerating All
Spanning Trees of a Directed Graph
- S. Kapoor and H. Ramesh
S
p
e
a
k
e
r
s
:
李
孟
韓
1
,
林
蔚
茵
2
,
莊
秋
芸
3
,
黃
稚
穎
4
Reference
•
H. N. Gabow and E. W. Myers: Finding all spanning trees of directed and
undirected graphs,
SIAM J
.
Comput
., Vol. 7, No. 3, 1978.
•
S. Kapoor, V. Kumar, and H. Ramesh: An algorithm for generating all
spanning trees of directed graphs, Proceedings of the Workshop on
Algorithms and Data Structures, LNCS, Vol. 955, Springer-Verlag, Berlin, pp.
428–439, 1995.
•
S
.
K
a
p
o
o
r
a
n
d
H
.
R
a
m
e
s
h
:
A
l
g
o
r
i
t
h
m
s
f
o
r
g
e
n
e
r
a
t
i
n
g
a
l
l
s
p
a
n
n
i
n
g
t
r
e
e
s
o
f
u
n
d
i
r
e
c
t
e
d
a
n
d
w
e
i
g
h
t
e
d
g
r
a
p
h
s
,
S
I
A
M
J
.
C
o
m
p
u
t
.
,
V
o
l
.
2
4
,
N
o
.
2
,
1
9
9
5
.
•
W. Mayeda: Graph Theory, Wiley, New York, 1972.
•
S. Shinoda: Finding all possible directed trees of a directed graph, Electron
Comm. Japan, Vol. 51-A, pp. 45–47, 1968.
Outline
•
Introduction and Algorithm outline
–
李孟韓
•
Main Algorithm
–
林蔚茵
•
Correctness
–
莊秋芸
•
Time analysis and conclusion
–
黃稚穎
Definition
•
A
n
e
x
c
h
a
n
g
e
f
o
r
a
s
p
a
n
n
i
n
g
t
r
e
e
T
o
f
G
r
o
o
t
e
d
a
t
v
i
s
a
p
a
i
r
o
f
e
d
g
e
s
(
e
,
f
)
,
w
h
e
r
e
e
∈
T
,
f
∈
E
–
T
,
a
n
d
T
–
{e
}
∪
{f
}
i
s
a
s
p
a
n
n
i
n
g
t
r
e
e
r
o
o
t
e
d
a
t
v
.
•
A
e
d
g
e
p
∈
E
-
T
i
s
b
a
c
k
e
d
g
e
i
f
i
t
s
t
a
i
l
i
s
a
n
a
n
c
e
s
t
o
r
o
f
i
t
s
h
e
a
d
i
n
T
.
•
A
e
d
g
e
p
’
∈
E
-
T
i
s
f
o
r
w
a
r
d
e
d
g
e
i
f
i
t
s
t
a
i
l
i
s
a
d
e
s
c
e
n
d
a
n
t
o
f
i
t
s
h
e
a
d
i
n
T
.
v
u
T
v
u
z
x
G
back edge
forward edge
f
x
=
T
a
i
l
(
f
)
V
=
h
e
a
d
(
f
)
cross edge
Property 1
•
Every nonback nontree edge
,
f
,
relative to a spanning tree T
,
may
replace exactly one tree edge
,
e
,
in the spanning tree
,
namely
,
the
edge having the same tail
,
to result in a new spanning tree rooted at
the same vertex as T
.
x
f
e
v
u
z
Property 2
•
A back edge cannot be exchanged for any edge in the spanning tree
to get a new spanning tree
.
x
e
v
u
z
g
Computation Tree
•
let
CD(G,v)
be the computation tree which generates all spanning
trees of the directed graph G with root v.
a
b
1
b
2
C
D
(
G
,
v
)
S
D
a
x
f
e
v
u
z
g
Computation Tree
•
SD
b
1
is obtained from
SD
a
by exchanging
f
with
e
, where
f
is a
nontree nonback edge and
e
is the unique tree edge with the same
tail as
f
.
a
b
1
b
2
C
D
(
G
,
v
)
S
D
b
1
p
i
c
k
f
x
f
e
v
u
z
g
Computation Tree
•
SD
b
2
is the same as
SD
a
. The significance of
b
2
is that the subtree
rooted at
b
2
will not include
f
in any spanning tree.
a
b
1
b
2
C
D
(
G
,
v
)
S
D
b
2
d
e
l
e
t
e
f
x
e
v
u
z
g
Computation Tree
a
b
1
b
2
C
D
(
G
,
v
)
S
D
b
1
p
i
c
k
f
x
f
e
v
u
z
Computation Tree
a
b
1
b
2
C
D
(
G
,
v
)
S
D
b
2
d
e
l
e
t
e
f
x
e
v
u
z
g
Lemma
•
CD(G,v) has at its nodes all directed spanning
trees of G rooted at vertex v.
An Algorithm for enumerating All
Spanning Trees of a Directed Graph
--- S. Kapoor and H. Ramesh
S
p
e
a
k
e
r
:
林
蔚
茵
2
Algorithm Description
•
DFS tree of
G
(rooted at
r
)
–
The root of the computation tree
CD(G,r)
•
For each node a of the computation tree
–
NB
: a set of those nontree edges which are nonback
w.r.t. the directed spanning tree and which are
not included in
•
Maintained as a list of nonempty lists
–
Each nonempty list containg edges incident upon a particular
vertex
–
Arranged in postorder number
–
B: a set of those back edges w.r.t. which are not
included in
Property 3
•
Let spanning tree
T’
be
obtained from spanning tree
T
by applying the exchange
(e,f).
If
x
is a nontree edge
which is back w.r.t.
T
and
nonback w.r.t.
T’
, then
head(x)
lies in the subtree of
T
rooted at
tail(f)
, and
tail(x)
is a vertex which is a proper
ancestor of
tail(f)
and a
proper descendant of
lca(head(f), tail(f))
in
T
v
f
e
a
u
x
head(x)
tail(x)
tail(f)
lca(head(f),tail(f))
ALGO Main(
G
,
r
)
•
The first edge in the first list of NB is the one having tail node with
the least postorder number.
•
CHANGES
is used to store the differences from the last spanning
tree generated
ALGO Gen(T)
b
1
b
2
ALGO Compute-back-to-nonback(f,T)
•
The sets
NB
and
B
are updated at every
exchange
–
transferring edges from
B
to
NB
–
Removal of edges from
B
and
NB
•
Data structure for
B
–
For each node
v
of
G
•
B[v]:
a list of nontree back edges in
B
having head vertex
v
•
A[v][p]
: each element points to the first edge in its list which is
incident upon a proper ancestor of node p
•
BASE[v]
: initialized to be
v
ALGO Compute-back-to-nonback(f,T)
(cont’d)
An Algorithm for enumerating All
Spanning Trees of a Directed Graph
--- S. Kapoor and H. Ramesh
S
p
e
a
k
e
r
:
莊
秋
芸
3
PROPERTY 4
u
v
f
b
lca(u,v)
If f =(u, v) is an edge in
NB and b=lca (u,v) in
SD
a
,
then no edge in NB has
its head in the subtree
of SD
a
rooted at v and
its tail on the path from
b to u
(b excluded).
•
DFS
•
The order of the selection
of the exchange edge from
NB
.
•
All “exchangeable edges”
must connect a vertex with
higher postorder number to
a vertex with lower
postorder number.
PROPERTY 4 (some
observations)
u
v
f
b
lca(u,v)
•
By induction on the level of
x
,
where
x
is a node on the
computation tree.
1.
Base case: root node.
2.
Induction hypothesis: assume
this is true for any node
x
of the
computation tree.
3.
Consider the left and right sons
b
1
,
b
2
of
x
.
1) It’s trivially true for the right
son
b
2
.
PROPERTY 4 (proof)
5
3
4
1
2
A DFS tree with postorder
number on each node.
4
2
3
2) For the left son
b
1.
PROPERTY 4 (proof)
9
5
8
1
4
f
e
7
6
2
3
9
5
8
1
f
7
6
Exchange
e
and
f
5.1
5.2
5.3
PROPERTY 4 (conclusion)
u
v
f
b
lca(u,v)
Since no such edges
exist, there’s no
nonback edges will
become back edges.
LEMMA 4.1
•
During the construction of the computation
tree the following changes to NB and B
suffice after an exchange at a node a in
the computation tree:
a)
changes from B to NB by Property 3.
b)
deletions from NB according to IN and OUT
definitions.
c)
removal of RB
a
from B.
PROPERTY 5
•
If an exchange (e, f), f=(u,v) is made at a
node x of the computation tree, then the
subtree of SD
x
rooted at v is preserved as
such in each of the trees generated at
descendant nodes of x in the computation tree.
So at node x, any edge in B incident upon a
vertex in that subtree, is redundant for future
computations at descendant nodes of x and
may be removed from B.
PROPERTY 5
v
f
e
u
computation tree
x
All have the same
subtree rooted at
v
SD
x
An Algorithm for enumerating All
Spanning Trees of a Directed Graph
--- S. Kapoor and H. Ramesh
S
p
e
a
k
e
r
:
黃
稚
穎
4
LEMMA 4.4
•
ALGO Main outputs the changes corresponding
to the compressed computation tree CD'(G,r) in
O(N(r)V+V
2
) operations.
The time for manipulating the
data structures
NB, B, and
STACK is O(V*(NBC
x
+1))
The total time required by
ALGO
Gen minus the output operations
equals O(
Σ
(V*NBC
x
))
At any node
x in the compressed
computation tree,
the above
summation gives an
O(N(r)V)
time bound.
Total output operations are
O(N(r)).
Computing
B and NB initially
require O(V
2
) time.
DFS requires
O(V+E)time
.
Total requires O(N(r)V+V
2
+V+E+N(r))
= O(N(r)V+V
2
) time
.
LEMMA 4.5
•
ALGO Main requires O(V
2
) space.
–
Follows from the size of the data structures
involved.
B requires O(V
2
)-space.
NB requires O(V+E)-space.
Changes stored on
STACK is O(V+NBC
x
)-space.
The total stack space required is
O(V
2
+
Σ
NBC
x
)
= O(V
2
)
Complexity
•
From
LEMMA 4.4
and
LEMMA 4.5
the following result
follows if the above procedure is repeated with each
vertex in turn as root.
THEOREM 4.6. All rooted directed spanning trees can
be output in
O(NV+V
3
)
operations and
O(V
2
)
space.
This research paper discusses an algorithm for enumerating all spanning trees of a directed graph, providing insights into the computation process and properties of the spanning trees. The algorithm outlined by Kapoor and Ramesh, along with references to related work, forms the basis of the discussion on tree exchanges, properties, and computation trees.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
An Algorithm for enumerating All Spanning Trees of a Directed Graph - S. Kapoor and H. Ramesh Speakers: 1, 2, 3, 4
Reference H. N. Gabow and E. W. Myers: Finding all spanning trees of directed and undirected graphs, SIAM J. Comput., Vol. 7, No. 3, 1978. S. Kapoor, V. Kumar, and H. Ramesh: An algorithm for generating all spanning trees of directed graphs, Proceedings of the Workshop on Algorithms and Data Structures, LNCS, Vol. 955, Springer-Verlag, Berlin, pp. 428 439, 1995. S. Kapoor and H. Ramesh: Algorithms for generating all spanning trees of undirected and weighted graphs, SIAM J. Comput., Vol. 24, No. 2, 1995. W. Mayeda: Graph Theory, Wiley, New York, 1972. S. Shinoda: Finding all possible directed trees of a directed graph, Electron Comm. Japan, Vol. 51-A, pp. 45 47, 1968.
Outline Introduction and Algorithm outline Main Algorithm Correctness Time analysis and conclusion
Definition An exchange for a spanning tree T of G rooted at v is a pair of edges (e, f) , where e T , f E T , and T {e} {f} is a spanning tree rooted at v. A edge p E - T is back edge if its tail is an ancestor of its head in T. A edge p E - T is forward edge if its tail is a descendant of its head in T. T G x = Tail(f) v v V = head(f) forward edge f back edge u u cross edge z x
Property 1 Every nonback nontree edge, f , relative to a spanning tree T , may replace exactly one tree edge, e, in the spanning tree, namely, the edge having the same tail, to result in a new spanning tree rooted at the same vertex as T. v f u e x z
Property 2 A back edge cannot be exchanged for any edge in the spanning tree to get a new spanning tree. v u e x g z
Computation Tree let CD(G,v) be the computation tree which generates all spanning trees of the directed graph G with root v. SDa CD(G,v) v u a f g b b x 1 2 e z
Computation Tree SDb1is obtained from SDaby exchanging f with e, where f is a nontree nonback edge and e is the unique tree edge with the same tail as f . CD(G,v) SDb1 v u a pick f f g b b x 1 2 e z
Computation Tree SDb2is the same as SDa. The significance of b2is that the subtree rooted at b2will not include f in any spanning tree. SDb2 CD(G,v) v u a delete f g b b x 1 2 e z
Computation Tree SDb1 CD(G,v) v u a pick f f b b x 1 2 e z
Computation Tree SDb2 CD(G,v) v u a delete f g b b x 1 2 e z
Lemma CD(G,v) has at its nodes all directed spanning trees of G rooted at vertex v.
An Algorithm for enumerating All Spanning Trees of a Directed Graph --- S. Kapoor and H. Ramesh Speaker: 2
Algorithm Description DFS tree of G (rooted at r) The root of the computation tree CD(G,r) For each node a of the computation tree NB: a set of those nontree edges which are nonback w.r.t. the directed spanning tree and which are not included in Maintained as a list of nonempty lists Each nonempty list containg edges incident upon a particular vertex Arranged in postorder number B: a set of those back edges w.r.t. which are not included in a OUT SD a OUT a SD a
Property 3 Let spanning tree T be obtained from spanning tree T by applying the exchange (e,f). If x is a nontree edge which is back w.r.t. T and nonback w.r.t. T , then head(x) lies in the subtree of T rooted at tail(f), and tail(x) is a vertex which is a proper ancestor of tail(f) and a proper descendant of lca(head(f), tail(f)) in T lca(head(f),tail(f)) a tail(x) u e f tail(f) v x head(x)
ALGO Main(G,r) The first edge in the first list of NB is the one having tail node with the least postorder number. CHANGES is used to store the differences from the last spanning tree generated
ALGO Gen(T) b1 b2
ALGO Compute-back-to-nonback(f,T) The sets NB and B are updated at every exchange transferring edges from B to NB Removal of edges from B and NB Data structure for B For each node v of G B[v]: a list of nontree back edges in B having head vertex v A[v][p]: each element points to the first edge in its list which is incident upon a proper ancestor of node p BASE[v]: initialized to be v
ALGO Compute-back-to-nonback(f,T) (cont d)
An Algorithm for enumerating All Spanning Trees of a Directed Graph --- S. Kapoor and H. Ramesh Speaker: 3
PROPERTY 4 If f =(u, v) is an edge in NB and b=lca (u,v) in SDa, then no edge in NB has its head in the subtree of SDarooted at v and its tail on the path from b to u (b excluded). lca(u,v) b u f v
PROPERTY 4 (some observations) DFS The order of the selection of the exchange edge from NB. All exchangeable edges must connect a vertex with higher postorder number to a vertex with lower postorder number. lca(u,v) b u f v
PROPERTY 4 (proof) By induction on the level of x, where x is a node on the computation tree. 1. Base case: root node. 2. Induction hypothesis: assume this is true for any node x of the computation tree. 3. Consider the left and right sons b1, b2 of x. 1) It s trivially true for the right son b2. 5 3 4 1 2 A DFS tree with postorder number on each node.
PROPERTY 4 (proof) 2) For the left son b1. 9 9 7 8 7 8 Exchange e and f 5 5 e f f 5.3 1 4 6 1 4 6 5.1 5.2 2 3 2 3
PROPERTY 4 (conclusion) lca(u,v) b Since no such edges exist, there s no nonback edges will become back edges. u f v
LEMMA 4.1 During the construction of the computation tree the following changes to NB and B suffice after an exchange at a node a in the computation tree: a) changes from B to NB by Property 3. b) deletions from NB according to IN and OUT definitions. c) removal of RBafrom B.
PROPERTY 5 If an exchange (e, f), f=(u,v) is made at a node x of the computation tree, then the subtree of SDxrooted at v is preserved as such in each of the trees generated at descendant nodes of x in the computation tree. So at node x, any edge in B incident upon a vertex in that subtree, is redundant for future computations at descendant nodes of x and may be removed from B.
PROPERTY 5 SDx computation tree e f v u x A redundant back edge All have the same subtree rooted at v
An Algorithm for enumerating All Spanning Trees of a Directed Graph --- S. Kapoor and H. Ramesh Speaker: 4
LEMMA 4.4 ALGO Main outputs the changes corresponding to the compressed computation tree CD'(G,r) in O(N(r)V+V2) operations. The time for manipulating the data structures NB, B, and STACK is O(V*(NBCx+1)) The total time required by ALGO Gen minus the output operations equals O( (V*NBCx)) At any node x in the compressed computation tree, the above summation gives an O(N(r)V) time bound. Computing B and NB initially require O(V2) time. Total requires O(N(r)V+V2+V+E+N(r)) = O(N(r)V+V2) time. DFS requires O(V+E)time. Total output operations are O(N(r)).
LEMMA 4.5 ALGO Main requires O(V2) space. Follows from the size of the data structures involved. B requires O(V2)-space. NB requires O(V+E)-space. Changes stored on STACK is O(V+NBCx)-space. The total stack space required is O(V2+ NBCx) = O(V2)
Complexity From LEMMA 4.4 and LEMMA 4.5 the following result follows if the above procedure is repeated with each vertex in turn as root. THEOREM 4.6. All rooted directed spanning trees can be output in O(NV+V3) operations and O(V2) space.
