1 algorithms
1.1 floyd-warshall algorithm
1.2 thorup s algorithm
1.3 kameda s algorithm
algorithms
algorithms determining reachability fall 2 classes: require preprocessing , not.
if have 1 (or few) queries make, may more efficient forgo use of more complex data structures , compute reachability of desired pair directly. can accomplished in linear time using algorithms such breadth first search or iterative deepening depth-first search.
if making many queries, more sophisticated method may used; exact choice of method depends on nature of graph being analysed. in exchange preprocessing time , storage space, can create data structure can answer reachability queries on pair of vertices in low
o
(
1
)
{\displaystyle o(1)}
time. 3 different algorithms , data structures 3 different, increasingly specialized situations outlined below.
floyd-warshall algorithm
the floyd–warshall algorithm can used compute transitive closure of directed graph, gives rise reachability relation in definition, above.
the algorithm requires
o
(
|
v
|
3
)
{\displaystyle o(|v|^{3})}
time ,
o
(
|
v
|
2
)
{\displaystyle o(|v|^{2})}
space in worst case. algorithm not solely interested in reachability computes shortest path distance between pairs of vertices. graphs containing negative cycles, shortest paths may undefined, reachability between pairs can still noted.
thorup s algorithm
for planar digraphs, faster method available, described mikkel thorup in 2004. method can answer reachability queries on planar graph in
o
(
1
)
{\displaystyle o(1)}
time after spending
o
(
n
log
n
)
{\displaystyle o(n\log {n})}
preprocessing time create data structure of
o
(
n
log
n
)
{\displaystyle o(n\log {n})}
size. algorithm can supply approximate shortest path distances, route information.
the overall approach associate each vertex relatively small set of so-called separator paths such path vertex
v
{\displaystyle v}
other vertex
w
{\displaystyle w}
must go through @ least 1 of separators associated
v
{\displaystyle v}
or
w
{\displaystyle w}
. outline of reachability related sections follows.
given graph
g
{\displaystyle g}
, algorithm begins organizing vertices layers starting arbitrary vertex
v
0
{\displaystyle v_{0}}
. layers built in alternating steps first considering vertices reachable previous step (starting
v
0
{\displaystyle v_{0}}
) , vertices reach previous step until vertices have been assigned layer. construction of layers, every vertex appears @ 2 layers, , every directed path, or dipath, in
g
{\displaystyle g}
contained within 2 adjacent layers
l
i
{\displaystyle l_{i}}
,
l
i
+
1
{\displaystyle l_{i+1}}
. let
k
{\displaystyle k}
last layer created, is, lowest value
k
{\displaystyle k}
such
⋃
i
=
0
k
=
v
{\displaystyle \bigcup _{i=0}^{k}=v}
.
the graph re-expressed series of digraphs
g
0
,
g
1
,
…
,
g
k
−
1
{\displaystyle g_{0},g_{1},\ldots ,g_{k-1}}
each
g
i
=
r
i
∪
l
i
∪
l
i
+
1
{\displaystyle g_{i}=r_{i}\cup l_{i}\cup l_{i+1}}
,
r
i
{\displaystyle r_{i}}
contraction of previous levels
l
0
…
l
i
−
1
{\displaystyle l_{0}\ldots l_{i-1}}
single vertex. because every dipath appears in @ 2 consecutive layers, , because each
g
i
{\displaystyle g_{i}}
formed 2 consecutive layers, every dipath in
g
{\displaystyle g}
appears in entirety in @ least 1
g
i
{\displaystyle g_{i}}
(and no more 2 consecutive such graphs)
for each
g
i
{\displaystyle g_{i}}
, 3 separators identified which, when removed, break graph 3 components each contain @
1
/
2
{\displaystyle 1/2}
vertices of original.
g
i
{\displaystyle g_{i}}
built 2 layers of opposed dipaths, each separator may consist of 2 dipaths, total of 6 dipaths on of separators. let
s
{\displaystyle s}
set of dipaths. proof such separators can found related planar separator theorem of lipton , tarjan, , these separators can located in linear time.
for each
q
∈
s
{\displaystyle q\in s}
, directed nature of
q
{\displaystyle q}
provides natural indexing of vertices start end of path. each vertex
v
{\displaystyle v}
in
g
i
{\displaystyle g_{i}}
, locate first vertex in
q
{\displaystyle q}
reachable
v
{\displaystyle v}
, , last vertex in
q
{\displaystyle q}
reaches
v
{\displaystyle v}
. is, looking @ how
q
{\displaystyle q}
can
v
{\displaystyle v}
, , how far can stay in
q
{\displaystyle q}
, still
v
{\displaystyle v}
. information stored each
v
{\displaystyle v}
. pair of vertices
u
{\displaystyle u}
,
w
{\displaystyle w}
,
u
{\displaystyle u}
can reach
w
{\displaystyle w}
via
q
{\displaystyle q}
if
u
{\displaystyle u}
connects
q
{\displaystyle q}
earlier
w
{\displaystyle w}
connects
q
{\displaystyle q}
.
every vertex labelled above each step of recursion builds
g
0
…
,
g
k
{\displaystyle g_{0}\ldots ,g_{k}}
. recursion has logarithmic depth, total of
o
(
log
n
)
{\displaystyle o(\log {n})}
information stored per vertex. point, logarithmic time query reachability simple looking on each pair of labels common, suitable
q
{\displaystyle q}
. original paper works tune query time down
o
(
1
)
{\displaystyle o(1)}
.
in summarizing analysis of method, first consider layering approach partitions vertices each vertex considered
o
(
1
)
{\displaystyle o(1)}
times. separator phase of algorithm breaks graph components @
1
/
2
{\displaystyle 1/2}
size of original graph, resulting in logarithmic recursion depth. @ each level of recursion, linear work needed identify separators connections possible between vertices. overall result
o
(
n
log
n
)
{\displaystyle o(n\log n)}
preprocessing time
o
(
log
n
)
{\displaystyle o(\log {n})}
additional information stored each vertex.
kameda s algorithm
a suitable digraph kameda s method
s
{\displaystyle s}
,
t
{\displaystyle t}
added.
the same graph above after kameda s algorithm has run, showing dfs labels each vertex
an faster method pre-processing, due t. kameda in 1975, can used if graph planar, acyclic, , exhibits following additional properties: 0-indegree , 0-outdegree vertices appear on same face (often assumed outer face), , possible partition boundary of face 2 parts such 0-indegree vertices appear on 1 part, , 0-outdegree vertices appear on other (i.e. 2 types of vertices not alternate).
if
g
{\displaystyle g}
exhibits these properties, can preprocess graph in
o
(
n
)
{\displaystyle o(n)}
time, , store
o
(
log
n
)
{\displaystyle o(\log {n})}
bits per vertex, answering reachability queries pair of vertices in
o
(
1
)
{\displaystyle o(1)}
time simple comparison.
preprocessing performs following steps. add new vertex
s
{\displaystyle s}
has edge each 0-indegree vertex, , new vertex
t
{\displaystyle t}
edges each 0-outdegree vertex. note properties of
g
{\displaystyle g}
allow while maintaining planarity, is, there still no edge crossings after these additions. each vertex store list of adjacencies (out-edges) in order of planarity of graph (for example, clockwise respect graph s embedding). initialize counter
i
=
n
+
1
{\displaystyle i=n+1}
, begin depth-first traversal
s
{\displaystyle s}
. during traversal, adjacency list of each vertex visited left-to-right needed. vertices popped traversal s stack, labelled value
i
{\displaystyle i}
, ,
i
{\displaystyle i}
decremented. note
t
{\displaystyle t}
labelled value
n
+
1
{\displaystyle n+1}
,
s
{\displaystyle s}
labelled
0
{\displaystyle 0}
. depth-first traversal repeated, time adjacency list of each vertex visited right-to-left.
when completed,
s
{\displaystyle s}
,
t
{\displaystyle t}
, , incident edges, removed. each remaining vertex stores 2-dimensional label values
1
{\displaystyle 1}
n
{\displaystyle n}
. given 2 vertices
u
{\displaystyle u}
,
v
{\displaystyle v}
, , labels
l
(
u
)
=
(
a
1
,
a
2
)
{\displaystyle l(u)=(a_{1},a_{2})}
,
l
(
v
)
=
(
b
1
,
b
2
)
{\displaystyle l(v)=(b_{1},b_{2})}
,
l
(
u
)
<
l
(
v
)
{\displaystyle l(u)<l(v)}
if , if
a
1
≤
b
1
{\displaystyle a_{1}\leq b_{1}}
,
a
2
≤
b
2
{\displaystyle a_{2}\leq b_{2}}
, , there exists @ least 1 component
a
1
{\displaystyle a_{1}}
or
a
2
{\displaystyle a_{2}}
strictly less
b
1
{\displaystyle b_{1}}
or
b
2
{\displaystyle b_{2}}
, respectively.
the main result of method states
v
{\displaystyle v}
reachable
u
{\displaystyle u}
if and
only if
l
(
u
)
<
l
(
v
)
{\displaystyle l(u)<l(v)}
, calculated in
o
(
1
)
{\displaystyle o(1)}
time.
Comments
Post a Comment