Hopcroft-Tarjan: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(18 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[Category:Graph Algorithms]]
== Abstract view ==
== Abstract view ==


Line 10: Line 11:


'''Abstract view:'''
'''Abstract view:'''
A variation of [[Depth-first search|DFS]], where for each node <math>v\in v</math> two additional nonnegative integral numbers are computed:
# A start node <math>s</math> and an edge <math>\{s,v\}</math> to an arbitrarily chosen node <math>v\in V</math> are added to <math>G</math>.
# The '''depth''' of <math>v</math> in the arborescence created by the DFS procedure.
# The core algorithm is a variation of [[Depth-first search|DFS]], where for each node <math>v\in V</math> two additional nonnegative integral numbers are computed:
# The '''lowpoint''', that is, the minimal depth of any node <math>w/in V</math> such that <math>(u,w)\in A</math> for some immediate or non-immediate successor of <math>v</math> in the DFS tree.
## The '''depth''' of <math>v</math> in the [[Basic graph definitions#Forests, trees, branchings, arborescences|arborescence]] created by the DFS procedure.
## The '''lowpoint''', that is the minimal depth of any node <math>w\in V</math> such that <math>\{u,w\}\in E</math>, where <math>u</math> is <math>v</math> or an immediate or non-immediate successor of <math>v</math> in the DFS tree.
# The start node <math>s</math> and the edge <math>\{s,v\}</math> are removed from <math>G</math> and from the DFS arborescence (which is rooted at <matH>v</math> afterwards).


'''Implementation:'''
'''Implementation of step 1:'''
# ''Depth'': The DFS maintains a global integral number, the '''current depth'''. Whenever a node is seen for the first time, its depth attribute is set identical to the current depth. In each forward step, the current depth is ''in''creased by one, in each backward step, it is ''de''creased by one.
# ''Depth'': The DFS maintains a global integral number, the '''current depth'''. Whenever a node is seen for the first time, its depth attribute is set identical to the current depth. In each forward step, the current depth is ''in''creased by one, in each backward step, it is ''de''creased by one.
# ''Lowpoint'':
# ''Lowpoint'':
## Whenever a node <math>v\in V</math> is seen for the first time, its lowpoint is set identical to its depth.
## Whenever a node <math>v\in V</math> is seen for the first time, its lowpoint is set to its depth.
## Whenever an arc <math>(v,w)</math> is examined such that <math>w</math> has already been seen and the depth of <math>w</math> is smaller than the lowpoint of <math>v</math>, the lowpoint of <math>w</math> is set identical to the depth of <math>w</math>.
## Whenever an arc <math>(v,w)</math> is examined such that <math>w</math> has already been seen and the depth of <math>w</math> is smaller than the lowpoint of <math>v</math>, the lowpoint of <math>v</math> is set identical to the depth of <math>w</math>.
## In each backward step of DFS from a node <math>w</math> back to its immediate predecessor <math>v</math>: If the lowpoint valueof <math>w</math> is smaller than the lowpoint value of <math>v</math>, the set the latter value identical to the former value.
## In each backward step of DFS from a node <math>w</math> back to its immediate predecessor <math>v</math>: If the lowpoint value of <math>w</math> is smaller than the lowpoint value of <math>v</math>, the lowpoint value of <math>v</math> is set identical to the lowpoint value of <math>w</math>.


'''Remark:'''
'''Remarks:'''
This is another example where it makes perfect sense to implement graph traversal algorithms as iterators. In fact, then the operations on the depth and lowpoint attributes can be inserted in the DFS loop in an easy, obvious way (cf. [[Graph traversal#Remarks|here]]).
# We do not choose a start node from the given nodes but insert a new start node to avoid a special treatment of the start node.
# This is another example where it makes perfect sense to implement graph traversal algorithms as iterators (cf. [[Graph traversal#Remarks|here]]). In fact, then the operations on the depth and lowpoint attributes can be inserted in the DFS loop in an easy, obvious way.


== Step 2 ==
== Step 2 ==


'''Definition:'''
'''Definition:'''
A node <math>v\in V</math> is '''essential''' if, for each arc <math>(v,w)</math> in the arborescence from step 1, the lowpoint value of <math>w</math> is equal to or larger than the depth of <math>w</math>.
A node <math>v\in V</math> is '''essential''' if, for at least one arc <math>(v,w)</math> in the arborescence from step 1, the lowpoint value of <math>w</math> is equal to or larger than the depth of <math>v</math>.


'''Abstract view:'''
'''Abstract view:'''
A repeated application of [[Depth-first search|DFS]], where the start nodes of the individual DFS runs are the essential node. In that, the essential nodes are considered in ascending order of their finishing times as computed in step 1. The nodes hit in one DFS run are removed from <math>G</math> before the next DFS run commences. The node sets visited in the individual DFS runs are returned as the biconnected components.
A repeated application of a modified [[Depth-first search|DFS]] (going only along that outgoing arc of the start node, that leads to the first seen successor, then as usual) in the [[Depth-first search|DFS]] [[Basic graph definitions#Forests, trees, branchings, arborescences|arborescence]] of step 1, where the start nodes of the individual DFS runs are the essential nodes. In that, the essential nodes are considered in ascending order of their finishing times as computed in step 1. The nodes hit in one DFS run (except for the essential start node if it has further outgoing arcs in the initial [[Depth-first search|DFS]] [[Basic graph definitions#Forests, trees, branchings, arborescences|arborescence]] of step 1) and all of their [[Basic graph definitions#Adjacency, incidence, and degree|incident]] edges are removed from <math>G</math> before the next DFS run commences. The node sets visited in the individual DFS runs are returned as the biconnected components.
 
'''Remark:'''
We do not remove the essential start node after a [[Depth-first search|DFS]] run if it has further outgoing arcs in the initial [[Depth-first search|DFS]] [[Basic graph definitions#Forests, trees, branchings, arborescences|arborescence]] of step 1, because these nodes belong to another [[Basic graph definitions#Connectedness|biconnected component]] as well (not only to the [[Basic graph definitions#Connectedness|biconnected component]] which was traversed by the latest [[Depth-first search|DFS]] run), which means they are always [[Basic graph definitions#Connectedness|articulation nodes]] (but not the other way around).


== Correctness ==
== Correctness ==
Line 36: Line 43:
Obviously, the depth and the lowpoint are set correctly according to their intended semantics.
Obviously, the depth and the lowpoint are set correctly according to their intended semantics.


For a biconnected component <math>C</math>, let <math>(v,w)</math> denote the first arc in the [[Basic graph definitions#Subgraphs|subgraph induced]] by <math>C</math> that is considered by the DFS in step 1.
First consider an essential node <math>v\in V</math>. Let <math>(v,w)</math> be an arc in the arborescence such that the lowpoint value of <math>w</math> is equal to or larger than the depth of <math>v</math>. We have to show that the subarborescence rooted at <math>(v,w)</math> is connected to the rest of the graph via <math>v</math> only. So suppose for a contradiction that there is an edge <math>\{x,y\}</math> such that <math>x</math> belongs to that subarborescence and <math>y</math> does not. Then <math>y</math> must have been seen before <math>x</math>, because otherwise, <math>y</math> would be in the subarborescence rooted at <math>x</math>. Since the lowpoint of <math>x</math> is equal to or larger than the depth of <math>v</math>, <math>y</math> cannot be a predecessor of <math>v</math> in the arborescence. Hence, <math>y</math> was even finished before <math>v</math> was seen. In particular, <math>y</math> was finished before <math>x</math> was seen, which is impossible.
 
In the following, the '''root''' of a biconnected component <math>C</math> is the first node of <math>C</math> seen in the DFS in step 1. We say that the root <math>v_1</math> of some biconnected component <math>C_1</math> '''follows''' the root <math>v_2</math> of some biconnected component <math>C_2</math> if <math>v_1\neq v_2</math> and both nodes were on the DFS path in step 1 at some stage such that <math>v_2</math> preceded <math>v_1</math> on this path. The subarborecence
 
Obviously, the biconnected component <math>C</math> is exactly the following node set: all nodes in the subarborescence rooted at the root <math>v</math> of a biconnected component minus all nodes in all subarborescences whose roots
 
We have to show that the nodes whose lowpoints are not smaller than their depths are exactly the roots of biconnected components in the arborescence created in step 1.


First consider a node <math>v\in V</math> whose lowpoint is smaller than its depth. Then <math>v</math> cannot be
Now consider a node <math>v\in V</math> that is ''not'' essential. Opposite to the first case, we have to show that the subarborescence rooted at an arc <math>(v,w)</math> is not only connected to the rest of the graph via <math>v</math>. However, this follows immediately from the definition of the lowpoint value: There is some <math>x\in V</math> in the subarborescence rooted at <math>(v,w)</math> connected to some node <math>y</math> that cannot be in the subarborescence due to its smaller depth.


== Complexity ==
== Complexity ==

Latest revision as of 13:31, 3 November 2015

Abstract view

Algorithmic problem: Biconnected components

Type of algorithm: two steps.

Step 1

Abstract view:

  1. A start node [math]\displaystyle{ s }[/math] and an edge [math]\displaystyle{ \{s,v\} }[/math] to an arbitrarily chosen node [math]\displaystyle{ v\in V }[/math] are added to [math]\displaystyle{ G }[/math].
  2. The core algorithm is a variation of DFS, where for each node [math]\displaystyle{ v\in V }[/math] two additional nonnegative integral numbers are computed:
    1. The depth of [math]\displaystyle{ v }[/math] in the arborescence created by the DFS procedure.
    2. The lowpoint, that is the minimal depth of any node [math]\displaystyle{ w\in V }[/math] such that [math]\displaystyle{ \{u,w\}\in E }[/math], where [math]\displaystyle{ u }[/math] is [math]\displaystyle{ v }[/math] or an immediate or non-immediate successor of [math]\displaystyle{ v }[/math] in the DFS tree.
  3. The start node [math]\displaystyle{ s }[/math] and the edge [math]\displaystyle{ \{s,v\} }[/math] are removed from [math]\displaystyle{ G }[/math] and from the DFS arborescence (which is rooted at [math]\displaystyle{ v }[/math] afterwards).

Implementation of step 1:

  1. Depth: The DFS maintains a global integral number, the current depth. Whenever a node is seen for the first time, its depth attribute is set identical to the current depth. In each forward step, the current depth is increased by one, in each backward step, it is decreased by one.
  2. Lowpoint:
    1. Whenever a node [math]\displaystyle{ v\in V }[/math] is seen for the first time, its lowpoint is set to its depth.
    2. Whenever an arc [math]\displaystyle{ (v,w) }[/math] is examined such that [math]\displaystyle{ w }[/math] has already been seen and the depth of [math]\displaystyle{ w }[/math] is smaller than the lowpoint of [math]\displaystyle{ v }[/math], the lowpoint of [math]\displaystyle{ v }[/math] is set identical to the depth of [math]\displaystyle{ w }[/math].
    3. In each backward step of DFS from a node [math]\displaystyle{ w }[/math] back to its immediate predecessor [math]\displaystyle{ v }[/math]: If the lowpoint value of [math]\displaystyle{ w }[/math] is smaller than the lowpoint value of [math]\displaystyle{ v }[/math], the lowpoint value of [math]\displaystyle{ v }[/math] is set identical to the lowpoint value of [math]\displaystyle{ w }[/math].

Remarks:

  1. We do not choose a start node from the given nodes but insert a new start node to avoid a special treatment of the start node.
  2. This is another example where it makes perfect sense to implement graph traversal algorithms as iterators (cf. here). In fact, then the operations on the depth and lowpoint attributes can be inserted in the DFS loop in an easy, obvious way.

Step 2

Definition: A node [math]\displaystyle{ v\in V }[/math] is essential if, for at least one arc [math]\displaystyle{ (v,w) }[/math] in the arborescence from step 1, the lowpoint value of [math]\displaystyle{ w }[/math] is equal to or larger than the depth of [math]\displaystyle{ v }[/math].

Abstract view: A repeated application of a modified DFS (going only along that outgoing arc of the start node, that leads to the first seen successor, then as usual) in the DFS arborescence of step 1, where the start nodes of the individual DFS runs are the essential nodes. In that, the essential nodes are considered in ascending order of their finishing times as computed in step 1. The nodes hit in one DFS run (except for the essential start node if it has further outgoing arcs in the initial DFS arborescence of step 1) and all of their incident edges are removed from [math]\displaystyle{ G }[/math] before the next DFS run commences. The node sets visited in the individual DFS runs are returned as the biconnected components.

Remark: We do not remove the essential start node after a DFS run if it has further outgoing arcs in the initial DFS arborescence of step 1, because these nodes belong to another biconnected component as well (not only to the biconnected component which was traversed by the latest DFS run), which means they are always articulation nodes (but not the other way around).

Correctness

Obviously, the depth and the lowpoint are set correctly according to their intended semantics.

First consider an essential node [math]\displaystyle{ v\in V }[/math]. Let [math]\displaystyle{ (v,w) }[/math] be an arc in the arborescence such that the lowpoint value of [math]\displaystyle{ w }[/math] is equal to or larger than the depth of [math]\displaystyle{ v }[/math]. We have to show that the subarborescence rooted at [math]\displaystyle{ (v,w) }[/math] is connected to the rest of the graph via [math]\displaystyle{ v }[/math] only. So suppose for a contradiction that there is an edge [math]\displaystyle{ \{x,y\} }[/math] such that [math]\displaystyle{ x }[/math] belongs to that subarborescence and [math]\displaystyle{ y }[/math] does not. Then [math]\displaystyle{ y }[/math] must have been seen before [math]\displaystyle{ x }[/math], because otherwise, [math]\displaystyle{ y }[/math] would be in the subarborescence rooted at [math]\displaystyle{ x }[/math]. Since the lowpoint of [math]\displaystyle{ x }[/math] is equal to or larger than the depth of [math]\displaystyle{ v }[/math], [math]\displaystyle{ y }[/math] cannot be a predecessor of [math]\displaystyle{ v }[/math] in the arborescence. Hence, [math]\displaystyle{ y }[/math] was even finished before [math]\displaystyle{ v }[/math] was seen. In particular, [math]\displaystyle{ y }[/math] was finished before [math]\displaystyle{ x }[/math] was seen, which is impossible.

Now consider a node [math]\displaystyle{ v\in V }[/math] that is not essential. Opposite to the first case, we have to show that the subarborescence rooted at an arc [math]\displaystyle{ (v,w) }[/math] is not only connected to the rest of the graph via [math]\displaystyle{ v }[/math]. However, this follows immediately from the definition of the lowpoint value: There is some [math]\displaystyle{ x\in V }[/math] in the subarborescence rooted at [math]\displaystyle{ (v,w) }[/math] connected to some node [math]\displaystyle{ y }[/math] that cannot be in the subarborescence due to its smaller depth.

Complexity

Statement: The asymptotic complexity is linear.

Proof: Follows immediately from the linear asymptotic complexity of DFS.

Retrieved from "https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Hopcroft-Tarjan&oldid=3605"