Algowiki - User contributions [en]

Dial implementation

2015-02-26T09:57:47Z

BB91: /* Methods */

[[Category:Checkup]]
[[Category:Data Structures]]
==General information==
'''Abstract data structure:''' [[Bounded monotonous priority queue]].

'''Implementation invariant:'''
An object of "Dial implementation" comprises:
# A specific '''maximum span of keys''' <math>S\in\mathbb{N}</math>.
# An array <math>A</math> with index set <math>\{0,\ldots,S-1\}</math> and [[Sets and sequences|sets]] of keys as components,
# A '''current position of the minimum''' <math>P</math>, which is dynamically changing.
# An [[Index handler|index handler]], whose value type is a pointer to an element in a [[Sets and sequences|set]] of keys.

All keys at an index of <math>A</math> are equal. For <math>i\in\{0,\ldots,S-1\}</math>, the value of the keys at position <math>i</math> is larger than the value of the keys at index <math>P</math> by exactly <math>(S+i-P)\bmod S</math>.

For each key currently stored in <math>A</math>, the index handler contains a pointer to the corresponding set element.

== Methods ==

# '''Extract minimum:''' The minimum keys are found at position <math>P</math>. If the set at position <math>P</math> is empty after extracting one minimum element, the current position <math>P</math> is increased by 1 modulo <math>S</math>,
# '''Insert:''' A key <math>K</math> is inserted at index <math>(K-A[P]+P)\bmod S</math>.
# '''Decrease key:''' Decreasing a key value <math>K</math> to value <math>K'</math> amounts to removing the key from the set at index <math>(K-A[P]+P)\bmod S</math> and re-insert it at index <math>(K'-A[P]+P)\bmod S</math>. The set element is retrieved from the index handler.

==Remark==
The implementations of the methods [[Bounded priority queue|Bounded priority queue: number]] and [[Bounded priority queue|Bounded priority queue: find minimum]] are trivial and, hence, left out here.

==References==

Matchings in graphs

2015-02-22T09:53:25Z

BB91: /* Blossoms */ insgesamt häufiger u_B verwendet, daher nun in diese Richtung abgeändert

== Matchings ==

# Let <math>G=(V,E)</math> be an [[Basic graph definitions|undirected graph]]. Without loss of generality, <math>G</math> is [[Basic graph definitions#Connectedness|connected]]. A '''matching''' in <math>G</math> is a set <math>M\subseteq E</math> of edges such that no two edges in <math>M</math> are [[Basic graph definitions#Adjacency, incidence, and degree|incident]].
# An edge in <math>M</math> is called '''matched''', an edge in <math>E\setminus M</math> is '''unmatched'''.
# A node <math>v\in V</math> is '''matched''' with respect to a matching <math>M</math> if it is incident to a matched edge; otherwise, <math>v</math> is called '''free''' or '''exposed'''.
# A matching is called '''perfect''' if there is no exposed node.

'''Remark:'''
A perfect matching <math>M</math> is only possible if <math>|V|</math> is even. Then <math>M</math> is perfect if, and only if, <math>|M|=|V|/2</math>.

== Alternating and augmenting paths ==

# A path <math>p</math> in an undirected graph <math>G=(V,E)</math> is called '''alternating''' with respect to some matching <math>M</math> if, for any two successive edges on <math>p</math>, exactly one of them belongs to <math>M</math>. In other words, the edges in <math>M</math> and the edges not in <math>M</math> appear strictly alternatingly on <math>p</math>.
# An alternating path <math>p</math> in an undirected graph <math>G=(V,E)</math> is called '''augmenting''' with respect to some matching <math>M</math> if both of its end nodes are exposed.
# '''Augmenting''' a matching <math>M</math> '''along an augmenting path''' <math>p</math> means increasing the size of <math>M</math> by one as follows:
## Each edge of <math>p</math> that was in <math>M</math> immediately before this augmentation step, is removed from <math>M</math>.
## Each edge of <math>p</math> that was ''not'' in <math>M</math> immediately before this augmentation step, is inserted in <math>M</math>.

== Finding augmenting paths ==

To find alternating paths in a matching <math>M</math>, a [[Graph traversal|graph traversal strategy]] is chosen and modified as follows:
# Whenever the current node <math>v</math> has been reached via an edge in <math>M</math>, only incident edges in <math>E\setminus M</math> are considered for seeing new nodes.
# Mirror-symmetrically, whenever the current node <math>v</math> has been reached via an edge in <math>E\setminus M</math>, only the (unique) incident edge in <math>M</math>, if existing, is considered for seeing a new node.
To find augmenting paths, the start node must be an exposed node.

'''Remark on the implementation:'''
This modified graph traversal in an undirected graph could be implemented as an ordinary graph traversal in a directed graph:
# Duplicate each matched node <math>v</math> giving <math>v_1</math> and <math>v_2</math>.
# Replace each edge <math>\{v,w\}</math> by two arcs, <math>(v,w)</math> and <math>(w,v)</math>.
# For each matched node <math>v</math>:
## Let all incoming arcs of <math>v</math> in <math>M</math> point to <math>v_1</math> and all outgoing arcs in <math>E\setminus M</math> leave <math>v_1</math>.
## Mirror-symmetrically, let all incoming arcs of <math>v</math> in <math>E\setminus M</math> point to <math>v_2</math> and all outgoing arcs of <math>v</math> in <math>M</math> leave <math>v_2</math>.

'''Caveat:'''
If the graph is not [[Basic graph definitions#Bipartite and k-partite graphs|bipartite]], no [[Graph traversal|graph traversal strategies]], modified as described above, guarantees to find an augmenting path if there is one; [[#Blossoms|blossom handling]] is necessary in addition.

== Blossoms ==

'''Definitions:'''
# For a matching <math>M</math> in <math>G</math>, a '''blossom''' is a cycle <math>B</math> of odd length in <math>G</math> such that <math>\lfloor|B|/2\rfloor</math> edges on <math>B</math> are matched and the remaining node on <math>B</math> is matched as well (by an edge not on <math>B</math>, in fact).
# The unique matched edge with exactly one incident node on <math>B</math> is called the '''stem''' of the blossom.
# '''Shrinking''' a blossom <math>B</math> means:
## Insert a new node <math>u_B</math> in <math>V</math>.
## For each edge <math>\{v,w\}</math> such that <math>v</math> is on <math>B</math> and <math>w</math> is not: Replace <math>\{v,w\}</math> by a new edge <math>\{u_B,w\}</math>.
## Remove all nodes and edges on <math>B</math>.
# An augmenting path <math>p</math> '''conforms''' to <math>B</math> if <math>p</math> contains the stem.

'''Statement:'''
Let <math>G=(V,E)</math> be an undirected graph, <math>M</math> a matching in <math>G</math>, and <math>B</math> a blossom. Further, let <math>G'=(V',E')</math> be the undirected graph resulting from shrinking <math>B</math>, and let <math>M'</math> be the restriction of <math>M</math> to <math>G'</math>. There is an augmenting path conforming to <math>B</math> in <math>G</math> with respect to <math>M</math> if, and only if, there is an augmenting path in <math>G'</math> with respect to <math>M'</math> that contains <math>u_B</math>.

'''Proof:'''
First suppose there is a conforming augmenting path <math>p</math> in <math>G</math> with respect to <math>M</math>. According to either possible orientation of <math>p</math>, let <math>s</math> and <math>t</math> denote the first and the last node of <math>p</math>. Moreover, let <math>v</math> and <math>w</math> denote the first and the last node of <math>p</math> that also belongs to <math>B</math> (possibly <math>v=w</math>). The concatenation of the subpaths of <math>p</math> from <math>s</math> to <math>v</math> and from <math>w</math> to <math>t</math> is an augmenting path in <math>G'</math>, and this path contains <math>u_B</math>.

So, consider the case that there is an augmenting path <math>p</math> in <math>G'</math> with respect to <math>M'</math>, and that <math>p</math> contains <math>u_B</math>. Since <math>u_B</math> is matched, <math>u_B</math> is not an end node of <math>p</math>, so <math>p</math> contains the stem of <math>B</math> because this is the only matched edge incident to <math>u_B</math>. Let <math>v</math> be the node of <math>B</math> incident to the stem and let <math>w</math> be the node on <math>p</math> that is farthest away from <math>v</math> on <math>p</math> among all nodes of <math>p</math> that also belong to <math>B</math>. Exactly one of the two subpaths of <math>B</math> from <math>v</math> to <math>w</math> yields a conforming augmenting path by concatenation with the two subpaths of <math>p</math> from the end nodes of <math>p</math> up to <math>v</math> and <math>w</math>, respectively.

Maximum matching by Edmonds

2015-02-22T09:25:36Z

BB91: /* Recursive step */ Bezeichnung und Link

== Abstract view ==

'''Algorithmic problem:'''
[[Cardinality-maximal matching]]

'''Type of algorithm:''' recursion.

'''Invariant:'''
Each recursive step returns a cardinality-maximal matching of its input graph.

'''Variant:'''
The number of nodes decreases.

== Recursion anchor ==

The graph search does not find an augmenting path, nor does it run into a [[Matchings in graphs#Blossoms|blossom]].

== Recursive step ==

'''Abstract view:'''
Apply the [[Classical bipartite cardinality matching#Induction step|modified repeated graph search]] from the [[Classical bipartite cardinality matching|classical algorithm]] for the restriction to [[Basic graph definitions#Bipartite and k-partite graphs|bipartite graphs]]. More specifically, choose a [[Breadth-first search|BFS]] or another graph traversal strategy that will never return to the start node (this requirement excludes [[Depth-first search|DFS]]).

The search maintains a boolean flag even/odd, which indicates the parity of the distance of the current node from the start node of the current search. Also, each node has a boolean label even/odd. When this node is seen for the first time, its label is set according to the flag. If a labeled node is seen again, but with another distance parity than before:
# The repeated graph search is terminated.
# A blossom <math>B</math> is identified.
# <math>B</math> is [[Matchings in graphs#Blossoms|shrunken]], giving <math>G'=(V',E')</math> and the restriction <math>M'</math> of <math>M</math> to <math>G'</math>.
# The procedure is called recursively with <math>G'</math> and <math>M'</math>.
# Exactly one node of <math>B</math> is matched by <math>M'</math>, so extend <math>M'</math> in the obvious, unique way by <math>\lfloor|B|/2\rfloor</math> edges of <math>B</math>.
# This extension of <math>M'</math> is returned.

'''Remark:'''
In typical formulations of this algorithm, the graph search is not left open but the search strategy applied in [[Hopcroft-Karp]] is hard-coded.

'''Implementation of step 2:'''
Let <math>w</math> be the node on which the two different parities occur, and let <math>v</math> be the node from which <math>w</math> is seen at that moment. In the arborescence constructed so far, let <math>u</math> denote the node such that the paths from the start node to <math>v</math> and <math>w</math> coincide up to <math>u</math> and part at <math>u</math>. Note that the incoming edge of <math>u</math> in the arborescence is matched because, otherwise, the arborescence could not branch at <math>u</math>. Therefore, the concatenation of the branch from <math>u</math> to <math>v</math>, the branch from <math>u</math> to <math>w</math>, and <math>\{v,w\}</math> is a blossom, and the search entered this blossom via its stem.

'''Proof:'''
First we show: If <math>M</math> is not maximum, the graph search will either find an augmenting path or run into a blossom via its stem. Suppose the search does not find an augmenting path. Due to the proof in the [[Classical bipartite cardinality matching#Induction step|induction step]] of the [[Classical bipartite cardinality matching|classical bipartite cardinality matching algorithm]], the graph search runs into an odd cycle. Since we chose a graph search strategy that never returns to the start node, the remark on that proof implies that this odd cycle is a blossom, and that the search entered this blossom via its stem.

It remains to show that the returned extension of <math>M'</math> is cardinality-maximal for <math>G</math> provided <math>M'</math> is cardinality-maximal fpr <math>G'</math>. However, this follows immediately from the fundamental [[Matchings in graphs#Blossoms|statement about blossoms]].

== Correctness ==

Follows immediately from the invariant.

== Complexity ==

'''Statement:'''
The asymptotic worst-case complexity is in <math>\mathcal{O}(n\!\cdot\!m)</math>, where <math>n=|V|</math> and <math>m=|E|</math>.

'''Proof:'''
Due to the variant, the recursion depth is in <math>\mathcal{O}(n)</math>. Each recursive step is dominated by the graph traversal. The [[Basic graph definitions#Adjacency, incidence, and degree|statement and remark on isolated nodes]] apply.

Classical bipartite cardinality matching

2015-02-22T08:49:07Z

BB91: /* Induction step */ Korrektur Bezeichnung p''

== Abstract view ==

'''Algorithmic problem:'''
[[Cardinality-maximal matching|Cardinality-maximal matching]] in [[Basic graph definitions#Bipartite and k-partite graphs|bipartite graphs]].

'''Type of algorithm:''' loop.

'''Invariant:'''
<math>M</math> is a matching in <math>G</math>.

'''Variant:'''
<math>|M|</math> is increased by one.

'''Break condition:'''
There is no more [[Matchings in graphs#Alternating and augmenting paths|augmenting path]].

== Induction basis ==

'''Abstract view:'''
Initialize <math>M</math> to be a feasible matching, for example, the empty matching.

== Induction step ==

'''Abstract view:'''
# Search for an [[Matchings in graphs#Alternating and augmenting paths|augmenting path]].
# If there is none, the loop terminates.
# Let <math>p</math> denote the augmenting path found in step 1.
# [[Matchings in graphs#Alternating and augmenting paths|Augment]] <math>M</math> along <math>p</math>.

'''Implementation of step 1:'''
A [[Graph traversal|graph traversal strategy]] is to be chosen that generates an [[Basic graph definitions#Forests, trees, branchings, arborescences|arborescence]] rooted at the start node, for example, a [[Depth-first search|DFS]] or a [[Breadth-first search|BFS]]. The [[Matchings in graphs#Finding augmenting paths|modification to find augmenting paths]] must be applied.
In a loop over all exposed nodes, a graph search is started at each of them. This loop may terminate early, namely when the first augmenting path is found.

'''Proof:'''
Basically, we have to show that there is no more augmenting path if this repeated graph search does not find one. So suppose for a contradiction that a search from an exposed node <math>u</math> fails although there is an augmenting path <math>p</math> from <math>u</math> to some other exposed node <math>v</math>. Then <math>v</math> is not seen by this graph search. Let <math>x</math> be the last node on <math>p</math> seen by this graph search, let <math>e</math> denote the edge over which <math>x</math> was seen, and let <math>e'</math> be the next edge on <math>p</math> (as seen in the direction from <math>u</math> to <math>v</math>). Since <math>e</math> was considered by the graph search and <math>e'</math> was not, we may conclude <math>e,e'\not\in M</math>. Let <math>p'</math> be the subpath of <math>p</math> from <math>u</math> to <math>x</math> and <math>p''</math> the path from <math>u</math> to <math>x</math> in the arborescence. As <math>e'\not\in M</math>, the last edge of <math>p'</math> is in <math>M</math>, so <math>p'</math> has even length. Since <math>e\not\in M</math>, <math>p''</math> has odd length. In summary, the concatenation <math>p'+p''</math> is a (usually non-simple) cycle of odd length. In particular, <math>G</math> is not bipartite.

'''Remark on the proof:'''
Go from <math>x</math> backwards along <math>p''</math> until the first node <math>y</math>, say, is seen that also belongs to <math>p</math>. In case <math>y\neq u</math>, the subpaths of <math>p'</math> and <math>p''</math> from <math>x</math> to <math>y</math> form a [[Matchings in graphs#Blossoms|blossom]], and the graph search entered this blossom via its [[Matchings in graphs#Blossoms|stem]].

== Correctness ==

[[Cardinality-maximal matching#Berge's theorem|Berge's theorem]] immediately implies that the resulting matching is [[Sets and sequences#Maximal and minimal sets|cardinality-maximal]].

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}(n\!\cdot\!m)</math>, where <math>n=|V|</math> and <math>m=|E|</math>.

'''Proof:'''
Since a matching cannot have more than <math>|V|/2</math> edges, the number of iterations is linear in the number of nodes. The complexity of an iteration is dominated by the graph search. The [[Basic graph definitions#Adjacency, incidence, and degree|statement and remark on isolated nodes]] apply.

== Connection to max-flow ==

This algorithm may be interpreted as an application of [[Ford-Fulkerson]]:
# Let <math>\{V_1,V_2\}</math> denote a [[Sets and sequences#Partitions|bipartition]] of <math>V</math> such that each edge is incident to one node of <math>V_1</math> and one node of <math>V_2</math>.
# Replace each undirected edge <math>\{v,w\}</math> by the directed arc <math>(v,w)</math> with infinite capacity, where <math>v\in V_1</math> and <math>w\in V_2</math> (so, all arcs go from <math>V_1</math> to <math>V_2</math>).
# Insert a new super-source <math>s</math> and a new super-target <math>t</math> in <math>V</math>.
# For each node <math>v\in V_1</math>, insert an arc <math>(s,v)</math> with capacity one.
# Mirror-symmetrically, for each node <math>w\in V_2</math>, insert an arc <math>(w,t)</math> with capacity one.
There is an obvious one-to-one correspondence between integral flows in that network and matchings in the original graph: An edge belongs to the matching if, and only if, the corresponding arc has positive flow value. The maximum flows correspond to the cardinality-maximal matchings. There is also a one-to-one correspondence between [[Matchings in graphs#Alternating and augmenting paths|augmenting paths]] in the original graph and [[Basic flow definitions#Flow-augmenting paths and saturated arcs|flow-augmenting paths]] in the induced flow network. [[Matchings in graphs#Alternating and augmenting paths|Augmenting]] the matching along an augmenting path is tantamount to [[Basic flow definitions#Augmenting along a path|augmenting]] the flow along the corresponding flow-augmenting path. Finally, the [[Max-flow min-cut|max-flow min-cut theorem]] reduces to the famous min-max theorem for bipartite matchings:

'''Definition:'''
# A '''node cover''' in an undirected graph is a set of nodes such that each edge is incident to at least one node in this set.
# A node in a node cover is said to '''cover''' the edges incident to this node.

'''Min-max theorem:'''
In a bipartite graph, the maximum cardinality of a matching equals the minimum cardinality of a node cover.

'''Reduction to the max-flow min-cut theorem:'''
Let <math>M</math> be a cardinality-maximal matching. No node can cover more than one edge of <math>M</math>. Therefore, no node set of less than <math>|M|</math> nodes can be a node cover. Thus, it suffices to construct a node cover of cardinality <math>|M|</math>.

The [[Max-flow min-cut|max-flow min-cut theorem]] implies that the minimum <math>(s,t)</math>-cut <math>(S,T)</math> has capacity <math>|M|</math>. In particular, <math>(S,T)</math> has finite capacity, so it is only crossed by arcs from <math>s</math> to <math>T</math> and by arcs from <math>S</math> to <math>t</math>. Now, let <math>S':=S\cap V_2</math> and <math>T':=T\cap V_1</math>. By construction, the node sets <math>S'</math> and <math>T'</math> are disjoint. The nodes in <math>S'</math> are in one-to-one correspondence to the arcs from <math>s</math> to <math>T</math>, and the nodes in <math>T'</math> are in one-to-one correspondence to the arcs from <math>S</math> into <math>t</math>. In summary, <math>|S'\cup T'|</math> is the capacity of <math>(S,T)</math>. Hence, it suffices to show that <math>S'\cup T'</math> is a node cover for the original graph.

For a contradiction suppose some edge <math>\{v,w\}</math> is not covered, where <math>v\in V_1</math> and <math>w\in V_2</math>, say. So, it is <math>v\in S</math> and <math>w\in T</math>, However, then <math>(v,w)</math> would go from <math>S</math> to <math>T</math>, which contradicts the fact that the capacity of <math>(S,T)</math> is finite.

'''Comment:'''
'''Tutte's theorem''' extends the min-max theorem to non-bipartite graphs.

Matchings in graphs

2015-02-22T08:06:32Z

BB91: /* Blossoms */ einheitliche Bezeichnung des Parameters im Text

== Matchings ==

# Let <math>G=(V,E)</math> be an [[Basic graph definitions|undirected graph]]. Without loss of generality, <math>G</math> is [[Basic graph definitions#Connectedness|connected]]. A '''matching''' in <math>G</math> is a set <math>M\subseteq E</math> of edges such that no two edges in <math>M</math> are [[Basic graph definitions#Adjacency, incidence, and degree|incident]].
# An edge in <math>M</math> is called '''matched''', an edge in <math>E\setminus M</math> is '''unmatched'''.
# A node <math>v\in V</math> is '''matched''' with respect to a matching <math>M</math> if it is incident to a matched edge; otherwise, <math>v</math> is called '''free''' or '''exposed'''.
# A matching is called '''perfect''' if there is no exposed node.

'''Remark:'''
A perfect matching <math>M</math> is only possible if <math>|V|</math> is even. Then <math>M</math> is perfect if, and only if, <math>|M|=|V|/2</math>.

== Alternating and augmenting paths ==

# A path <math>p</math> in an undirected graph <math>G=(V,E)</math> is called '''alternating''' with respect to some matching <math>M</math> if, for any two successive edges on <math>p</math>, exactly one of them belongs to <math>M</math>. In other words, the edges in <math>M</math> and the edges not in <math>M</math> appear strictly alternatingly on <math>p</math>.
# An alternating path <math>p</math> in an undirected graph <math>G=(V,E)</math> is called '''augmenting''' with respect to some matching <math>M</math> if both of its end nodes are exposed.
# '''Augmenting''' a matching <math>M</math> '''along an augmenting path''' <math>p</math> means increasing the size of <math>M</math> by one as follows:
## Each edge of <math>p</math> that was in <math>M</math> immediately before this augmentation step, is removed from <math>M</math>.
## Each edge of <math>p</math> that was ''not'' in <math>M</math> immediately before this augmentation step, is inserted in <math>M</math>.

== Finding augmenting paths ==

To find alternating paths in a matching <math>M</math>, a [[Graph traversal|graph traversal strategy]] is chosen and modified as follows:
# Whenever the current node <math>v</math> has been reached via an edge in <math>M</math>, only incident edges in <math>E\setminus M</math> are considered for seeing new nodes.
# Mirror-symmetrically, whenever the current node <math>v</math> has been reached via an edge in <math>E\setminus M</math>, only the (unique) incident edge in <math>M</math>, if existing, is considered for seeing a new node.
To find augmenting paths, the start node must be an exposed node.

'''Remark on the implementation:'''
This modified graph traversal in an undirected graph could be implemented as an ordinary graph traversal in a directed graph:
# Duplicate each matched node <math>v</math> giving <math>v_1</math> and <math>v_2</math>.
# Replace each edge <math>\{v,w\}</math> by two arcs, <math>(v,w)</math> and <math>(w,v)</math>.
# For each matched node <math>v</math>:
## Let all incoming arcs of <math>v</math> in <math>M</math> point to <math>v_1</math> and all outgoing arcs in <math>E\setminus M</math> leave <math>v_1</math>.
## Mirror-symmetrically, let all incoming arcs of <math>v</math> in <math>E\setminus M</math> point to <math>v_2</math> and all outgoing arcs of <math>v</math> in <math>M</math> leave <math>v_2</math>.

'''Caveat:'''
If the graph is not [[Basic graph definitions#Bipartite and k-partite graphs|bipartite]], no [[Graph traversal|graph traversal strategies]], modified as described above, guarantees to find an augmenting path if there is one; [[#Blossoms|blossom handling]] is necessary in addition.

== Blossoms ==

'''Definitions:'''
# For a matching <math>M</math> in <math>G</math>, a '''blossom''' is a cycle <math>B</math> of odd length in <math>G</math> such that <math>\lfloor|B|/2\rfloor</math> edges on <math>B</math> are matched and the remaining node on <math>B</math> is matched as well (by an edge not on <math>B</math>, in fact).
# The unique matched edge with exactly one incident node on <math>B</math> is called the '''stem''' of the blossom.
# '''Shrinking''' a blossom <math>B</math> means:
## Insert a new node <math>v_B</math> in <math>V</math>.
## For each edge <math>\{v,w\}</math> such that <math>v</math> is on <math>B</math> and <math>w</math> is not: Replace <math>\{v,w\}</math> by a new edge <math>\{v_B,w\}</math>.
## Remove all nodes and edges on <math>B</math>.
# An augmenting path <math>p</math> '''conforms''' to <math>B</math> if <math>p</math> contains the stem.

'''Statement:'''
Let <math>G=(V,E)</math> be an undirected graph, <math>M</math> a matching in <math>G</math>, and <math>B</math> a blossom. Further, let <math>G'=(V',E')</math> be the undirected graph resulting from shrinking <math>B</math>, and let <math>M'</math> be the restriction of <math>M</math> to <math>G'</math>. There is an augmenting path conforming to <math>B</math> in <math>G</math> with respect to <math>M</math> if, and only if, there is an augmenting path in <math>G'</math> with respect to <math>M'</math> that contains <math>u_B</math>.

'''Proof:'''
First suppose there is a conforming augmenting path <math>p</math> in <math>G</math> with respect to <math>M</math>. According to either possible orientation of <math>p</math>, let <math>s</math> and <math>t</math> denote the first and the last node of <math>p</math>. Moreover, let <math>v</math> and <math>w</math> denote the first and the last node of <math>p</math> that also belongs to <math>B</math> (possibly <math>v=w</math>). The concatenation of the subpaths of <math>p</math> from <math>s</math> to <math>v</math> and from <math>w</math> to <math>t</math> is an augmenting path in <math>G'</math>, and this path contains <math>u_B</math>.

So, consider the case that there is an augmenting path <math>p</math> in <math>G'</math> with respect to <math>M'</math>, and that <math>p</math> contains <math>u_B</math>. Since <math>u_B</math> is matched, <math>u_B</math> is not an end node of <math>p</math>, so <math>p</math> contains the stem of <math>B</math> because this is the only matched edge incident to <math>u_B</math>. Let <math>v</math> be the node of <math>B</math> incident to the stem and let <math>w</math> be the node on <math>p</math> that is farthest away from <math>v</math> on <math>p</math> among all nodes of <math>p</math> that also belong to <math>B</math>. Exactly one of the two subpaths of <math>B</math> from <math>v</math> to <math>w</math> yields a conforming augmenting path by concatenation with the two subpaths of <math>p</math> from the end nodes of <math>p</math> up to <math>v</math> and <math>w</math>, respectively.

Successive shortest paths with reduced costs

2015-02-20T14:39:39Z

BB91: /* Abstract view */ Vereinheitlichung Seitenaufbau

== Abstract view ==

'''Algorithmic problem:''' [[Min-cost flow problem]]

'''Type of algorithm:''' loop

'''Auxiliary data:'''
For each node <math>v\in V</math>, there is a real number <math>\pi(v)</math>.

'''Invariant:'''
# All points of the invariant of the [[Successive shortest paths|successive shortest paths]] algorithm.
# For each arc <math>a=(v,w)\in A_f</math>, the '''reduced cost''' <math>c^\pi(a):=c(a)-\pi(v)+\pi(w)</math> is nonnegative.

'''Variant:''' The total imbalance strictly decreases.

'''Definition:'''
Such a node labeling <math>\pi</math> is called '''consistent''' with <math>f</math>.

== Induction basis ==

'''Abstract view:'''
Start with the zero flow <math>f</math> and with the zero node labeling <math>\pi</math>.

'''Proof:'''
The assumption that all cost values are nonnegative implies that <math>\pi\equiv 0</math> is consistent with <math>f\equiv 0</math>.

== Induction step ==

'''Abstract view:'''
The induction step is a variation and extension of the [[Successive shortest paths#Induction step|induction step]] of the [[Successive shortest paths|successive shortest paths algorithm]]. The essential modification is that <math>c</math> is replaced by <math>c^\pi</math>. Due to point 2 of the invariant, it is always <math>c^\pi\geq 0</math>. Therefore, an efficient algorithm such as [[Dijkstra|Dijkstra's]] may be applied. The extension is that, after each augmentation of the flow, the reduced cost values must be updated to maintain consistency.

'''Implementation''' of the update of the reduced cost values:
For all nodes <math>v\in V</math>, set <math>\pi(v):=\pi(v)-\delta(v)</math>, where <math>\delta(v)</math> is the distance of <math>v</math> from <math>s</math> as computed in the [[Successive shortest paths#Induction step|induction step]] of the [[Successive shortest paths|successive shortest paths algorithm]].

'''Proof:'''
The variant and points 1 and 3 of the invariant of the [[Successive shortest paths|successive shortest paths algorithm]] are obviously maintained. For point 2 of that invariant, it suffices to show that the shortest paths with respect to the arc lengths <math>c^\pi</math> are also shortest paths with respect to the arc lengths <math>c</math>; however, that results immediately from [[Basics of shortest paths#(Admissible) node potentials|this statement]].

It remains to show that the updated node potentials are consistent with the augmented flow. Let <math>\pi_\mathrm{before}</math> and <math>\pi_\mathrm{after}</math> denote the values of <math>\pi</math> immediately before and after the current iteration, respectively. Let <math>(v,w)</math> be an arc in the [[Basic flow definitions#Residual network|residual network]] of the augmented flow, that is, the flow immediately after the current iteration. We make a case distinction:
# If <math>(v,w)</math> was also in the residual network immediately before the current iteration, the new reduced cost of <math>(v,w)</math> is <math>c^{\pi_\mathrm{after}}(v,w)</math> <math> =c(v,w)-\pi_\mathrm{after}(v)+\pi_\mathrm{after}(w)</math> <math>=c(v,w)-\left[\pi_\mathrm{before}(v)-\delta(v)\right]+\left[\pi_\mathrm{before}(w)-\delta(w)\right]</math> <matH>=c^{\pi_\mathrm{before}}(v,w)-\delta(w)+\delta(v)</math>. As the <math>\delta</math>-values are shortest-path distances with respect to arc lengths <math>c^{\pi_\mathrm{before}}</math>, the [[basics of shortest paths#Valid distance property|valid distance property]] yields <math>\delta(w)\leq\delta(v)+c^{\pi_\mathrm{before}}(v,w)</math>, which proves the claim.
# Otherwise, <math>(w,v)</math> is on the shortest path computed in the current iteration. Recall <math>c(v,w)=-c(w,v)</math>, so we obtain <math>c^{\pi_\mathrm{after}}(v,w)</math> <math>=c(v,w)-\pi_\mathrm{after}(v)+\pi_\mathrm{after}(w)</math> <math>=-\left[c(w,v)-\pi_\mathrm{after}(w)+\pi_\mathrm{after}(v)\right]</math> <math>=-\left[c(w,v)-(\pi_\mathrm{before}(w)-\delta(w))+(\pi_\mathrm{before}(v)-\delta(v))\right]</math> <math>=-\left[c^{\pi_\mathrm{before}}(w,v)-\delta(v)+\delta(w)\right]</math>. [[Basics of shortest paths#Distances along shortest paths|This statement]] proves that the last expression is zero.

== Correctness ==

Cf. [[Successive shortest paths#Correctness|here]].

== Complexity ==

The asymptotic complexity and its proof are identical to the [[Successive shortest paths#Complexity|complexity considerations]] of the [[Successive shortest paths|successive shortest paths algorithm]]. Note that <math>T</math> may now be the asymptotic complexity of an algorithm that cannot handle negative arc weights.

Successive shortest paths

2015-02-20T14:37:39Z

BB91: /* Abstract view */ Vereinheitlichung Seitenaufbau

== Abstract view ==

'''Algorithmic problem:''' [[Min-cost flow problem]]

'''Type of algorithm:''' loop

'''Definition:'''
# For a node <math>v\in V</math>, let <math>\delta f(v):=\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)</math>.
# The '''imbalance''' of a node <math>v\in V</math> is defined as <math>I_f(v):=\delta f(v)-b(v)</math>.
# The imbalance of a node <math>v\in V</math> is '''underestimating''' if <math>0\leq\delta f(v)\leq b(v)</math> or <math>0\geq\delta f(v)\geq b(v)</math>.
# The '''total imbalance''' of <math>f</math> is defined as <math>\sum_{v\in V}|I_f(v)|</math>.

'''Invariant:'''
# The capacity constraints are fulfilled, that is, <math>0\leq f(a)\leq u(a)</math> for all <math>a\in A</math>.
# There is no negative cycle in the [[Basic flow definitions#Residual network|residual network]] of <math>f</math>.
# The imbalance of every node is underestimating.

'''Variant:'''
The total imbalance strictly decreases.

'''Break condition:'''
The imbalances of all nodes are zero or there is no augmenting path from some node <math>v\in V</math> with <math>I_f(v)<0</math> to any node <math>w</math> with <math>I_f(w)>0</math>.

== Induction basis ==

'''Abstract view:'''
Start with the zero flow.

'''Proof:'''
Obvious.

== Induction step ==

# Choose some node <math>s</math> with <math>I_f(s)<0</math>.
# Find a shortest <math>(s,t)</math>-path <math>p</math> to some node <math>t</math> with <math>I_f(t)>0</math>.
# If there is none, terminate the algorithm.
# Increase the flow on all arcs of <math>p</math> by the minimum of the following three values: <math>|I_f(s)|</math>, <math>I_f(t)>0</math>, and the minimal [[Basic flow definitions#Residual network|residual capacity]] taken over all arcs on <math>p</math>.

'''Remark:'''
Since cost values may be negative in the [[Basic flow definitions#Residual network|residual network]], step 2 requires an algorithm that copes with negative arc lengths. In particular, efficient algorithms such as [[Dijkstra|Dijkstra's]] are not an option. However, a [[Successive shortest paths with reduced costs|variant]] of the algorithm works on a nonnegative variation of the cost values, which allows efficient algorithms.

'''Proof:'''
The variant follows from the fact that the amount by which the flow is increased in step 3 is strictly positive. The first and third points of the invariant result from the choice of this amount as the minimum of the imbalances of the end nodes and all residual capacities. Thus, it remains to show point 2 of the invariant.

By induction hypothesis, there were no negative cycles immediately before the iteration. So, any negative cycle <math>C</math> must have been created by the flow augmentation along <math>p</math>. Let <math>p_1,\ldots,p_k</math> denote the [[Sets and sequences#Maximal and minimal sets|inclusion-maximal]] subpaths of <math>C</math> whose [[Basic graph definitions#Paths|internal nodes]] do not belong to <math>p</math>. In other words, each <math>p_i</math> starts and ends on <math>p</math> but does not share any further node with <math>p</math>. Now, for <math>i\in\{1,\ldots,k\}</math>, let <math>p'_i</math> denote
# the subpath of <math>p</math> from the start node of <math>p_i</math> to the end node of <math>p_i</math>, if the start node of <math>p_i</math> appears on <math>p</math> before its end node;
# the subpath of the [[Basic graph definitions#Transpose|transpose]] of <math>p</math> from the start node of <math>p_i</math> to the end node of <math>p_i</math>, if the end node of <math>p_i</math> appears on <math>p</math> before the start node of <math>p_i</math>.

Further, let <math>C'</math> be the cycle that results from <math>C</math> when each subpath <math>p_i</math> is replaced by the corresponding subpath <math>p'_i</math> of <math>p</math> (in the first case) or of the [[Basic graph definitions#Transpose|transpose]] of <math>p</math> (in the second case). In general, this cycle is extremely non-simple. It contains each arc of <math>p</math> as often as its opposite arc. Therefore, the total cost of <math>C'</math> ist zero. Now it suffices to show that the total cost of <math>C</math> is not smaller than the total cost of <math>C'</math>. More specifically, for each <math>i\in\{1,\ldots,k\}</math>, we will show that the cost of <math>p_i</math> is not smaller than the cost of <math>p'_i</math>. Note that all arcs on all subpaths <math>p_i</math> are in the residual network immediately before and immediately after the current iteration (with positive residual capacity, by definition). We apply the case distinction in the definition of <math>p'_i</math> above.
# For a path <math>p_i</math> of the first type, the fact that <math>p</math> is a shortest path implies that <math>p_i</math> is a shortest path from its start node to its end node in the residual network immediately before the current iteration. Therefore, <math>p'_i</math> is not shorter than <math>p_i</math>.
# For a path <math>p_i</math> of the second type, let <math>p''</math> denote the transpose of <math>p'_i</math>. In particular, <math>p''_i</math> is a subpath of <math>p</math>. Note that <math>p_i</math> and <math>p''_i</math> form a cycle, and that this cycle was augmenting immediately before the current iteration. By induction hypothesis, this cycle is not negative, <math>c(p_i)+c(p''_i)\geq 0</math>. The claim now follows from <math>c(p'_i)=-c(p''_i)</math>.

== Correctness ==

The proof of the induction step shows that the invariant is fulfilled on termination. If no path is found, the instance is obviously infeasible. On the other hand, if all imbalances are removed, the resulting flow is feasible. Due to the second point of the invariant, it is also minimum (cf. [[Negative cycle-canceling#Correctness|here]]).

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}(B\cdot T)</math>, where <math>B=\sum_{v\in V}|b(v)|</math>, and <math>T</math> is the asymptotic complexity of the shortest-path algorithm.

'''Proof:'''
Obviously, the number of iterations is in <math>\mathcal{O}(B)</math>. The complexity of an iteration is dominated by the shortest-path computation.

Successive shortest paths

2015-02-20T14:06:39Z

BB91: /* Induction step */ Hier muss Zykel C gemeint sein, damit Beweis Sinn ergibt

== Abstract view ==

'''Definition:'''
# For a node <math>v\in V</math>, let <math>\delta f(v):=\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)</math>.
# The '''imbalance''' of a node <math>v\in V</math> is defined as <math>I_f(v):=\delta f(v)-b(v)</math>.
# The imbalance of a node <math>v\in V</math> is '''underestimating''' if <math>0\leq\delta f(v)\leq b(v)</math> or <math>0\geq\delta f(v)\geq b(v)</math>.
# The '''total imbalance''' of <math>f</math> is defined as <math>\sum_{v\in V}|I_f(v)|</math>.

'''Invariant:'''
# The capacity constraints are fulfilled, that is, <math>0\leq f(a)\leq u(a)</math> for all <math>a\in A</math>.
# There is no negative cycle in the [[Basic flow definitions#Residual network|residual network]] of <math>f</math>.
# The imbalance of every node is underestimating.

'''Variant:'''
The total imbalance strictly decreases.

'''Break condition:'''
The imbalances of all nodes are zero or there is no augmenting path from some node <math>v\in V</math> with <math>I_f(v)<0</math> to any node <math>w</math> with <math>I_f(w)>0</math>.

== Induction basis ==

'''Abstract view:'''
Start with the zero flow.

'''Proof:'''
Obvious.

== Induction step ==

# Choose some node <math>s</math> with <math>I_f(s)<0</math>.
# Find a shortest <math>(s,t)</math>-path <math>p</math> to some node <math>t</math> with <math>I_f(t)>0</math>.
# If there is none, terminate the algorithm.
# Increase the flow on all arcs of <math>p</math> by the minimum of the following three values: <math>|I_f(s)|</math>, <math>I_f(t)>0</math>, and the minimal [[Basic flow definitions#Residual network|residual capacity]] taken over all arcs on <math>p</math>.

'''Remark:'''
Since cost values may be negative in the [[Basic flow definitions#Residual network|residual network]], step 2 requires an algorithm that copes with negative arc lengths. In particular, efficient algorithms such as [[Dijkstra|Dijkstra's]] are not an option. However, a [[Successive shortest paths with reduced costs|variant]] of the algorithm works on a nonnegative variation of the cost values, which allows efficient algorithms.

'''Proof:'''
The variant follows from the fact that the amount by which the flow is increased in step 3 is strictly positive. The first and third points of the invariant result from the choice of this amount as the minimum of the imbalances of the end nodes and all residual capacities. Thus, it remains to show point 2 of the invariant.

By induction hypothesis, there were no negative cycles immediately before the iteration. So, any negative cycle <math>C</math> must have been created by the flow augmentation along <math>p</math>. Let <math>p_1,\ldots,p_k</math> denote the [[Sets and sequences#Maximal and minimal sets|inclusion-maximal]] subpaths of <math>C</math> whose [[Basic graph definitions#Paths|internal nodes]] do not belong to <math>p</math>. In other words, each <math>p_i</math> starts and ends on <math>p</math> but does not share any further node with <math>p</math>. Now, for <math>i\in\{1,\ldots,k\}</math>, let <math>p'_i</math> denote
# the subpath of <math>p</math> from the start node of <math>p_i</math> to the end node of <math>p_i</math>, if the start node of <math>p_i</math> appears on <math>p</math> before its end node;
# the subpath of the [[Basic graph definitions#Transpose|transpose]] of <math>p</math> from the start node of <math>p_i</math> to the end node of <math>p_i</math>, if the end node of <math>p_i</math> appears on <math>p</math> before the start node of <math>p_i</math>.

Further, let <math>C'</math> be the cycle that results from <math>C</math> when each subpath <math>p_i</math> is replaced by the corresponding subpath <math>p'_i</math> of <math>p</math> (in the first case) or of the [[Basic graph definitions#Transpose|transpose]] of <math>p</math> (in the second case). In general, this cycle is extremely non-simple. It contains each arc of <math>p</math> as often as its opposite arc. Therefore, the total cost of <math>C'</math> ist zero. Now it suffices to show that the total cost of <math>C</math> is not smaller than the total cost of <math>C'</math>. More specifically, for each <math>i\in\{1,\ldots,k\}</math>, we will show that the cost of <math>p_i</math> is not smaller than the cost of <math>p'_i</math>. Note that all arcs on all subpaths <math>p_i</math> are in the residual network immediately before and immediately after the current iteration (with positive residual capacity, by definition). We apply the case distinction in the definition of <math>p'_i</math> above.
# For a path <math>p_i</math> of the first type, the fact that <math>p</math> is a shortest path implies that <math>p_i</math> is a shortest path from its start node to its end node in the residual network immediately before the current iteration. Therefore, <math>p'_i</math> is not shorter than <math>p_i</math>.
# For a path <math>p_i</math> of the second type, let <math>p''</math> denote the transpose of <math>p'_i</math>. In particular, <math>p''_i</math> is a subpath of <math>p</math>. Note that <math>p_i</math> and <math>p''_i</math> form a cycle, and that this cycle was augmenting immediately before the current iteration. By induction hypothesis, this cycle is not negative, <math>c(p_i)+c(p''_i)\geq 0</math>. The claim now follows from <math>c(p'_i)=-c(p''_i)</math>.

== Correctness ==

The proof of the induction step shows that the invariant is fulfilled on termination. If no path is found, the instance is obviously infeasible. On the other hand, if all imbalances are removed, the resulting flow is feasible. Due to the second point of the invariant, it is also minimum (cf. [[Negative cycle-canceling#Correctness|here]]).

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}(B\cdot T)</math>, where <math>B=\sum_{v\in V}|b(v)|</math>, and <math>T</math> is the asymptotic complexity of the shortest-path algorithm.

'''Proof:'''
Obviously, the number of iterations is in <math>\mathcal{O}(B)</math>. The complexity of an iteration is dominated by the shortest-path computation.

Preflow-push

2015-02-17T13:12:23Z

BB91: /* Induction step */ intuitivere Benennung

== Abstract view ==

'''Algorithmic problem:'''
[[Max-Flow Problems#Standard version|max-flow problem (standard version)]]

'''Type of algorithm:'''
loop.

'''Auxiliary data:'''
# A nonnegative integral value <math>d(v)</math> for each node <math>v\in V</math>.
# Each node <math>v\in V\setminus\{t\}</math> has a '''current arc''', which may be implemented as an iterator on the list of outgoing residual arcs of <math>v</math>.
# The [[Basic flow definitions#Preflow|excess]] <math>e_f(v)</math> of a node <math>v\in V\setminus\{s,t\}</math> with respect to the current [[Basic flow definitions#Preflow|preflow]].
# A (dynamically changing) [[Sets and sequences|set]] <math>S</math> of nodes.

'''Invariant:'''
Before and after each iteration:
# For each arc <math>a\in A</math>, it is <math>0\leq f(a)\leq u(a)</math> . If all upper bounds are integral, all <math>f</math>-values are integral, too.
# For each node <math>v\in V\setminus\{s,t\} </math>, it is <math>e_f(v)\geq 0</math>. In other words, <math>f</math> is a [[Basic flow definitions#Preflow|preflow]].
# The node labels <math>d</math> form a [[Basic flow definitions#Valid distance labeling|valid distance labeling]], and it is <math>d(s)=|V|</math>.
# The currently [[Basic flow definitions#Preflow|active nodes]] are stored in <math>S</math>.

'''Variant:'''
In each iteration, one of the following three actions will take place:
# The label <math>d(v)</math> of at least one node <math>v\in V\setminus\{s,t\}</math> is increased.
# A saturating push is performed.
# The value of <math>D:=\sum_{v\in V\setminus\{s,t\}\atop e_f(v)>0}d(v)</math> decreases.
No label <math>d(\cdot)</math> is ever decreased.

'''Break condition:'''
<math>S=\emptyset</math>.

== Induction basis ==

'''Abstract view:'''
# For all arcs <math>a\in A</math>, set <math>f(a):=0</math>.
# For each arc <math>(s,v)\in A</math>, overwrite this value by <math>f(a):=u(a)</math> and put <math>v</math> into <math>S</math>.
# Compute a [[Basic flow definitions#Valid distance labeling|valid distance labeling]] <math>d</math> for <math>V\setminus\{s\}</math> with respect to <math>f</math>, for example, the true distances from all nodes to <math>t</math> in the residual network of <math>f</math>.
# Set <math>d(s):=n</math>.
# For all <math>v\in V\setminus\{s,t\}</math>, reset the current arc of <math>v</math> so as to point to the first arc in the list of outgoing arcs of <math>v</math>.

'''Proof:'''
For the [[Basic graph definitions#Subgraphs|subgraph induced]] by <math>V\setminus\{s\}</math>, the arguments in the [[Ahuja-Orlin#Correctness|correctness proof]] for the [[Ahuja-Orlin]] algorithm prove that the <math>d</math>-labels form a valid distance labeling here as well. For <math>s</math>, nothing is to show because all outgoing arcs are saturated.

== Induction step ==

'''Abstract view:'''
# Choose an [[Basic flow definitions#Preflow|active node]] <math>v</math> from <math>S</math>.
# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling|admissible]] either, move the current arc one step forward.
# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:
## If <math>w\neq s</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.
## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.
## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.
## If <math>e_f(v)=0</math> now, extract <math>v</math> from <math>S</math>.
# Otherwise:
## Let <math>d_\min</math> denote the minimal label <math>d(w)</math> of any arc <math>(v,w)</math> in the residual network.
## Set <math>d(v):=d_\min+1</math>.
## Reset the current arc of <math>v</math> so as to point to the beginning of the list of outgoing arcs of <math>v</math>.

'''Remark:'''
The preflow-push algorithm is also known as the '''push-relabel''' algorithm. The ''push'' operation is step 3; the ''relabel'' operation is step 4.

'''Proof:'''
Points 1, 2, and 4 of the invariant and <math>d(s)=n</math> are obviously fulfilled. The rest of point 3 of the invariant is affected by step 4 only, and the outgoing arcs of <math>v</math> are the only arcs where the distance labeling may become invalid. However, the extremely conservative increase of <math>d(v)</math> ensures point 3 of the invariant.

To prove the variant, consider a step in which neither any <math>d</math>-value is increased nor a saturating push is performed. This means step 3.2 is applied, but the arc <math>(v,w)</math> is not saturated by that. Potentially, <math>w</math> becomes active. However, <math>v</math> definitely becomes inactive since the push step is non-saturating. Now the variant follows from the fact that <math>d(w)=d(v)-1</math> for an admissible arc <math>(v,w)</math>.

It remains to show termination; this is proved by the following complexity considerations.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}(n^2m)</math>, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
First we show that the total number of relabel operations (step 4 of the main loop) is in <math>\mathcal{O}(n^2)</math>. To see that, let <math>v\in V\setminus\{s,t\}</math> be an active node between two iterations of the main loop. A straightforward induction over the number of push operations shows that there is at least one simple <math>(s,v)</math>-path <math>p</math> with positive flow on all arcs. The [[Basic graph definitions#Transpose of a graph|transpose]] of <math>p</math> is [[Basic flow definitions#Flow-augmenting paths and saturated arcs|augmenting]]. Due to the validity of <math>d</math> (induction hypothesis), <math>d(v)-d(s)=d(v)-n</math> cannot be larger than the number of arcs on <math>p</math>, which is not larger than <math>n-1</math>. Therefore, no node label can be larger than <math>2n-1</math>. Since node labels are nonnegative and increase at least by one in each relabel operation, the claimed upper bound on the relabel operations follows.

From this bound, we may immediately conclude that the current arc of a node is reset <math>\mathcal{O}(n)</math> times, so the total number of forward steps of the current arcs of all nodes is in <math>\mathcal{O}(n^2)</math>.

The argument in the [[Ahuja-Orlin#Complexity|complexity analysis]] of the [[Ahuja-Orlin]] algorithm to prove that the total number of ''saturating'' push operations is in <math>\mathcal{O}(nm)</math>, applies here as well.

Finally, we consider the ''non-saturating'' push operations. First note that <math>D\geq 0</math> before and after each iteration. The value of <math>D</math> is increased in each relabel operation exactly by the amount by which the label of the current node is increased. Since node labels are never decreased and bounded from above by <math>2n-1</math>, <math>D</math> increases by less than <math>2n^2</math> in total over all relabel operations. On the other hand, a saturating push operation may increase <math>D</math> by at most <math>2n-1</math> (namely, in the case that <math>w</math> was not active immediately before the push). In summary, the total sum of all values by which <math>D</math> is increased throughout the algorithm is in <math>\mathcal{O}(n^2m)</math>. Due to the variant, the value of <math>D</math> is decreased by at least one in each non-saturating push operation. This proves the claim.

== Heuristic speedup techniques ==

# After <math>\Omega(n)</math> iterations of the main loop, the <math>d</math>-values are recomputed analogously to the induction basis: as the current distance of each node to <math>t</math> in the residual network. This modification is seldom enough, so the asymptotic complexity is not increased. In practice, this technique may save many unnecessary relabel steps.
# The main loop may be decomposed into two phases: First, as much flow as possible is sent into <math>t</math>; second, all surplus flow that cannot reach <math>t</math> is sent back to <math>s</math>. The first phase may be finished once there is no more path in the residual network from any active node to <math>t</math>. A sufficient and easy-to-check condition for that is <math>d(v)\geq n</math> for all active nodes <math>v</math>. All nodes from which <math>t</math> is reachable may be safely disregarded in the second phase. For any other node, to save unnecessary relabel operations, the distance label may be safely increased to the minimum number of arcs in the residual network from this node back to <math>s</math>.

Three indians' algorithm

2015-02-16T13:30:38Z

BB91: /* Induction step */

== General information ==

'''Algorithmic problem:''' [[Blocking flow]].

'''Type of algorithm:''' loop.

== Abstract view ==

'''Invariant:'''
The current flow is feasible.

'''Variant:'''
The number of nodes strictly decreases.

'''Break condition:'''
There is no more [[Basic graph definitions#Paths|ordinary <math>(s,t)</math>-path]] in <math>G</math>.

== Induction basis ==

'''Abstract view:'''
The flow is initialized to be feasible, for example, the zero flow.

'''Proof:'''
Obvious.

== Induction step ==

'''Abstract view:'''
Choose the node <math>v_0</math> through which the minimum amount of flow may go, and propagate this amount from <math>v_0</math> forward to <math>t</math> and backward to <math>s</math>.

'''Implementation:'''
# For each node <math>v\in V\setminus\{s,t\}</math>, let <math>T(v)</math> denote the '''throughput''' of <math>v</math>, which is defined by <math>T(v):=\min\left\{\sum_{w:(v,w)\in A}u(v,w),\sum_{w:(w,v)\in A}u(w,v)\right\}</math>.
# Remove all nodes with zero throughput and all arcs incident to at least one of these nodes.
# Let <math>v_0\in V\setminus\{s,t\}</math> be a node with minimum throughput <math>T(v_0)</math>.
# Set <math>F(v_0):=T(v_0)</math> and <math>F(v):=0</math> for all nodes <math>v\in V\setminus\{s,t,v_0\}</math>.
# Run a modified [[Breadth-first search|BFS]] from <math>v_0</math>, where for every processed arc <math>(v,w)\in A</math>:
## Let <math>\Delta:=\min\{u(v,w),F(v)\}</math>.
## Set the flow over <math>(v,w)</math> to <math>\Delta</math>.
## Increase <math>F(w)</math> by <math>\Delta</math>.
## Decrease <math>F(v)</math>, <math>T(v)</math>, and <math>u(v,w)</math> by <math>\Delta</math>.
## If <math>u(v,w)=0</math>, remove <math>(v,w)</math> from <math>G</math>.
## If <math>F(v)=0</math>, finish this iteration.
# Run the same modified [[Breadth-first search|BFS]] from <math>v_0</math> on the [[Basic graph definitions#Transpose of a graph|transpose]] of <math>G</math> (all removals apply to <math>G</math>).

'''Proof:'''
Consider step 5 (step 6 is analogous). The specific choice of <matH>v_0</math> ensures <math>F(v)\leq T(v_0)\leq T(v)</math> for each node <math>v\in V</math> at any time. Therefore, all flow arrived at <math>v</math> can be moved forward along the arcs leaving <math>v</math>. In other words, when <math>v</math> is finished, it is <math>F(v)=0</math>. Since <math>G</math> is an [[Basic graph definitions#Cycles|<math>(s,t)</math>-graph]], the result is a feasible <math>(s,t)</math>-flow, and the flow value has increased by the initial value of <math>T(v_0)</math>. In particular, it is <math>T(v_0)=0</math> at the end, so at least <math>v_0</math> will be removed in this iteration.

== Correctness ==

When a node is removed, either all of its outgoing arcs or all of its ingoing arcs are saturated. Therefore, an arc is only removed if this arc itself or all immediate predecessors or all immediate successors are saturated. In particular, an arc is only removed if it is not on any flow-augmenting path anymore. Therefore, when the break condition is fulfilled, the flow is blocking. Termination follows from the following complexity considerations.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}(n^2)</math>, where <math>n=|V|</math>.

'''Proof:'''
Due to the variant, the number of iterations is linear in <math>n</math>. When an arc is saturated, it is removed in step 5.5 (resp., 6.5), so the total number of saturating increases of flow values of arcs over all iterations of the main loop is linear in the number of arcs, which is in <math>\mathcal{O}(n^2)</math>. In each execution of step 5 (resp., step 6), the flow on at most one outgoing (resp., incoming) arc of each node is increased without saturation, so the number of ''non''-saturating flow value settings is linear in the number of nodes in each iteration.

== Remarks ==

# The algorithm is named after three indian researchers, V. M. Malhotra, M. Pramodh Kumar, and S. N. Mahashwari.
# Of course, the nodes and arcs need not really be removed from the graph. However, "removed" nodes and arcs must be hidden from the algorithm to ensure the asymptotic complexity; a Boolean label "is removed" does not suffice for that.
# This application of [[Breadth-first search|BFS]] is an example for one of the remarks on [[Graph traversal#Remarks|graph traversal]]: It is reasonable to implement graph-traversal algorithms as iterators. In fact, then the modification may be simply added to the loop that runs the iterator.

Negative cycle-canceling

2015-02-05T15:18:29Z

BB91: /* Induction step */

== Abstract view ==

'''Algorithmic problem:''' [[Min-cost flow problem]]

'''Type of algorithm:''' loop

'''Invariant:'''
# The flow is [[Basic flow definitions#Feasible flow|feasible]].
# If all upper bounds are integral, the flow is integral as well.

'''Variant:''' The cost of the flow decreases.

'''Break condition:''' There is no more [[Basics of shortest paths#Path lengths and distances|negative cycle]] in the residual network.

== Induction basis ==

'''Abstract view:''' Start with an arbitrary feasible flow.

'''Implementation:'''
The problem to find a feasible flow is reduced to a [[Max-Flow Problems|max-flow problem]] as follows:
# Insert new vertices, <math>s</math> and <math>t</math>.
# For each original node <math>v\in V</math> such that <math>b[v]>0</math>: Insert an arc <math>(s,v)</math> with capacity <math>b[v]</math>.
# For each original node <math>v\in V</math> such that <math>b[v]<0</math>: Insert an arc <math>(v,t)</math> with capacity <math>-b[v]</math>.
# Determine a [[Max-Flow Problems|maximum flow]] from <math>s</math> to <math>t</math> in the extended graph (cost factors and balance values are disregarded).
# If all arcs <math>(s,v)</math> are [[Basic flow definitions#Flow-augmenting paths and saturated arcs|saturated]], return the restriction of this flow to the original arcs.
# Otherwise, the original [[Min-cost flow problem|min-cost flow]] instance is infeasible.

'''Proof:'''
If the arcs leaving <math>s</math> (or, equivalently, the arcs entering <math>t</math>) are saturated, the flow balances at all original nodes are obviously fulfilled in the original [[Min-cost flow problem|min-cost flow]] instance. On the other hand, if a feasible flow exists at all in the original [[Min-cost flow problem|min-cost flow]] instance, its extension to the inserted arcs yields a flow that saturates all arcs leaving <math>s</math>. Therefore, if the ''maximum'' flow in the extended flow network does not saturate all of these arcs, the original instance is infeasible.

== Induction step ==

'''Abstract view:'''
# Find a [[Basics of shortest paths#Path lengths and distances|cycle of negative cost]] in the [[Basic flow definitions#Residual network|residual network]].
# [[Basic flow definitions#Augmenting along a path|Augment]] the flow along this cycle up to saturation.

'''Implementation of step 1:'''
# Run an [[All pairs shortest paths|all-pairs shortest-paths]] algorithm on the [[Basic flow definitions#Residual network|residual network]] <math>(G_f,u_f)</math>, where for each arc <math>(v,w)\in A</math>, the length of <math>(v,w)</math> is <math>c(v,w)</math> in case <math>(v,w)\in A_f</math>, and the length of <math>(w,v)</math> is <math>-c(v,w)</math> in case <math>(w,v)\in A_f</math>. Let the algorithm [[Basics of shortest paths#Constructing a shortest-paths arborescence or a negative cycle|construct an arborescence or a negative cycle]].
# If the distance <math>v\rightarrow v</math> is 0 for all <math>v\in V</math>, the break condition applies.
# Otherwise (that is, the distances <math>v\rightarrow v</math> of some nodes <math>v\in V</math> are negative): Reconstruct one negative cycle <math>C</math>.

'''Proof:'''
The invariant and the variant are obviously fulfilled.

== Correctness ==

In the following, arithmetic operations and comparisons of flows are arc-wise. For a [[Basic graph definitions#Cycles|generalized cycle]] <math>C</math> and <math>\varepsilon>0</math>, adding <math>\varepsilon\cdot C</math> to a flow <math>f</math> means that <math>f</math> is [[Basic flow definitions#Augmenting along a path|augmented]] along <math>C</math> by <math>\varepsilon</math>.

First we will show a general fact: For two feasible flows, <math>f_1</math> and <math>f_2</math>, there are [[basic graph definitions#Cycles|generalized cycles]] <math>C_1,\ldots,C_k</math> in <math>G</math> and <math>\varepsilon_1,\ldots,\varepsilon_k>0</math> such that:
# '''Decomposition''' of <math>f_2-f_1</math>: It is <math>f_2=f_1+\varepsilon_1\cdot C_1+\cdots+\varepsilon_k\cdot C_k</math>.
# '''Consistency:''' For each arc <math>a\in A</math> and <math>i,j\in\{1,\ldots,k\}</math>: If <math>a</math> belongs to <math>C_i</math> and <math>C_j</math>, then <math>a</math> is a forward arc on both cycles, or <math>a</math> is a backward arc in both cycles.

To prove this general fact, we apply an induction on the number <math>d</math> of arcs on which <math>f_1</math> and <math>f_2</math> differ. For <math>d=0</math>, it is <math>f_1=f_2</math>, so the empty set of cycles (<math>k=0</math>) describes the difference between <math>f_1</math> and <math>f_2</math>.

So suppose <math>d>0</math>. Let <math>(v_1,v_2)</math> be an arc on which <math>f_1</math> and <math>f_2</math> differ, say <math>f_1(v_1,v_2)<f_2(v_1,v_2)</math>. Then there is either an arc <math>(v_2,v_3)</math> with <math>f_1(v_2,v_3)<f_2(v_2,v_3)</math> or an arc <math>(v_3,v_2)</math> with <math>f_1(v_3,v_2)>f_2(v_3,v_2)</math>. This argument may be continued, so we obtain a sequence <math>v_1,v_2,v_3,v_4,\ldots</math> such that for all <math>i=1,2,3,\ldots</math>, there is <math>(v_i,v_{i+1})</math> with <math>f_1(v_i,v_{i+1})<f_2(v_i,v_{i+1})</math> or <math>(v_{i+1},v_i)</math> with <math>f_1(v_{i+1},v_i)<f_2(v_{i+1},v_i)</math>. Since the number of nodes is finite, there must be <math>i</math> and <math>j</math> such that <math>v_i=v_j</math>. Therefore, a generalized cycle <math>C_1</math> is closed such that <math>f_1(a)<f_2(a)\leq u(a)</math> on each forward arc and <math>f_1(a)>f_2(a)\geq 0</math> on each backward arc. In particular, there is <math>\varepsilon_1>0</math> such that <math>f_1+\varepsilon_1\cdot C_1</math> is feasible. If <math>\varepsilon_1</math> is chosen maximal, <math>f_1+\varepsilon_1\cdot C_1</math> agrees one at least one more arc with <math>f_2</math> than <math>f_1</math>. Now the induction hypothesis proves the general fact.

Finally, we are in a position to prove correctness of the algorithm. For that, we have to show that a feasible flow is minimum if it admits no negative cycle. So assume a feasible flow <math>f</math> is ''not'' minimum. Then there is a feasible flow <math>\tilde{f}</math> such that <math>c(\tilde{f})<c(f)</math>. There are <math>C_1,\ldots,C_k</math> and <math>\varepsilon_1,\ldots,\varepsilon_k</math> as described above. Since <math>c(\tilde{f})<c(f)</math>, at least one of the cycles must be a negative one,say <math>C_i</math>. Since the cycles are consistent, they may be permuted in the decomposition, so <math>f+\varepsilon_i\cdot C_i</math> is feasible.

== Complexity ==

'''Statement:'''
If all upper bounds are integral, the asymptotic complexity is in <math>\mathcal{O}(T\cdot C\cdot U)</math>, where <math>T</math> is the asymptotic complexity of the [[All pairs shortest paths|all-pairs shortest-paths problem]], <math>C=\sum_{a\in A}|c(a)|</math>, and <math>U=\max\{u(a)|a\in A\}</math>.

'''Proof:'''
The initial flow has a total cost of at most <math>C\cdot U</math>, and the min-cost flow has a total cost of at least <math>-C\cdot U</math>. Therefore, the number of iterations is in <math>\mathcal{O}(C\cdot U)</math>. The complexity of an iteration is dominated by the all-pairs shortest-paths algorithm.

Preflow-push

2015-02-04T18:03:44Z

BB91: Undo revision 2789 by BB91 (talk) wird in vielen anderen Artikeln als O(n^2) benötigt

== Abstract view ==

'''Algorithmic problem:'''
[[Max-Flow Problems#Standard version|max-flow problem (standard version)]]

'''Type of algorithm:'''
loop.

'''Auxiliary data:'''
# A nonnegative integral value <math>d(v)</math> for each node <math>v\in V</math>.
# Each node <math>v\in V\setminus\{t\}</math> has a '''current arc''', which may be implemented as an iterator on the list of outgoing residual arcs of <math>v</math>.
# The [[Basic flow definitions#Preflow|excess]] <math>e_f(v)</math> of a node <math>v\in V\setminus\{s,t\}</math> with respect to the current [[Basic flow definitions#Preflow|preflow]].
# A (dynamically changing) [[Sets and sequences|set]] <math>S</math> of nodes.

'''Invariant:'''
Before and after each iteration:
# For each arc <math>a\in A</math>, it is <math>0\leq f(a)\leq u(a)</math> . If all upper bounds are integral, all <math>f</math>-values are integral, too.
# For each node <math>v\in V\setminus\{s,t\} </math>, it is <math>e_f(v)\geq 0</math>. In other words, <math>f</math> is a [[Basic flow definitions#Preflow|preflow]].
# The node labels <math>d</math> form a [[Basic flow definitions#Valid distance labeling|valid distance labeling]], and it is <math>d(s)=|V|</math>.
# The currently [[Basic flow definitions#Preflow|active nodes]] are stored in <math>S</math>.

'''Variant:'''
In each iteration, one of the following three actions will take place:
# The label <math>d(v)</math> of at least one node <math>v\in V\setminus\{s,t\}</math> is increased.
# A saturating push is performed.
# The value of <math>D:=\sum_{v\in V\setminus\{s,t\}\atop e_f(v)>0}d(v)</math> decreases.
No label <math>d(\cdot)</math> is ever decreased.

'''Break condition:'''
<math>S=\emptyset</math>.

== Induction basis ==

'''Abstract view:'''
# For all arcs <math>a\in A</math>, set <math>f(a):=0</math>.
# For each arc <math>(s,v)\in A</math>, overwrite this value by <math>f(a):=u(a)</math> and put <math>v</math> into <math>S</math>.
# Compute a [[Basic flow definitions#Valid distance labeling|valid distance labeling]] <math>d</math> for <math>V\setminus\{s\}</math> with respect to <math>f</math>, for example, the true distances from all nodes to <math>t</math> in the residual network of <math>f</math>.
# Set <math>d(s):=n</math>.
# For all <math>v\in V\setminus\{s,t\}</math>, reset the current arc of <math>v</math> so as to point to the first arc in the list of outgoing arcs of <math>v</math>.

'''Proof:'''
For the [[Basic graph definitions#Subgraphs|subgraph induced]] by <math>V\setminus\{s\}</math>, the arguments in the [[Ahuja-Orlin#Correctness|correctness proof]] for the [[Ahuja-Orlin]] algorithm prove that the <math>d</math>-labels form a valid distance labeling here as well. For <math>s</math>, nothing is to show because all outgoing arcs are saturated.

== Induction step ==

'''Abstract view:'''
# Choose an [[Basic flow definitions#Preflow|active node]] <math>v</math> from <math>S</math>.
# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling|admissible]] either, move the current arc one step forward.
# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:
## If <math>w\neq s</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.
## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.
## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.
## If <math>e_f(v)=0</math> now, extract <math>v</math> from <math>S</math>.
# Otherwise:
## Let <math>d_\max</math> denote the minimal label <math>d(w)</math> of any arc <math>(v,w)</math> in the residual network.
## Set <math>d(v):=d_\max+1</math>.
## Reset the current arc of <math>v</math> so as to point to the beginning of the list of outgoing arcs of <math>v</math>.

'''Remark:'''
The preflow-push algorithm is also known as the '''push-relabel''' algorithm. The ''push'' operation is step 3; the ''relabel'' operation is step 4.

'''Proof:'''
Points 1, 2, and 4 of the invariant and <math>d(s)=n</math> are obviously fulfilled. The rest of point 3 of the invariant is affected by step 4 only, and the outgoing arcs of <math>v</math> are the only arcs where the distance labeling may become invalid. However, the extremely conservative increase of <math>d(v)</math> ensures point 3 of the invariant.

To prove the variant, consider a step in which neither any <math>d</math>-value is increased nor a saturating push is performed. This means step 3.2 is applied, but the arc <math>(v,w)</math> is not saturated by that. Potentially, <math>w</math> becomes active. However, <math>v</math> definitely becomes inactive since the push step is non-saturating. Now the variant follows from the fact that <math>d(w)=d(v)-1</math> for an admissible arc <math>(v,w)</math>.

It remains to show termination; this is proved by the following complexity considerations.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}(n^2m)</math>, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
First we show that the total number of relabel operations (step 4 of the main loop) is in <math>\mathcal{O}(n^2)</math>. To see that, let <math>v\in V\setminus\{s,t\}</math> be an active node between two iterations of the main loop. A straightforward induction over the number of push operations shows that there is at least one simple <math>(s,v)</math>-path <math>p</math> with positive flow on all arcs. The [[Basic graph definitions#Transpose of a graph|transpose]] of <math>p</math> is [[Basic flow definitions#Flow-augmenting paths and saturated arcs|augmenting]]. Due to the validity of <math>d</math> (induction hypothesis), <math>d(v)-d(s)=d(v)-n</math> cannot be larger than the number of arcs on <math>p</math>, which is not larger than <math>n-1</math>. Therefore, no node label can be larger than <math>2n-1</math>. Since node labels are nonnegative and increase at least by one in each relabel operation, the claimed upper bound on the relabel operations follows.

From this bound, we may immediately conclude that the current arc of a node is reset <math>\mathcal{O}(n)</math> times, so the total number of forward steps of the current arcs of all nodes is in <math>\mathcal{O}(n^2)</math>.

The argument in the [[Ahuja-Orlin#Complexity|complexity analysis]] of the [[Ahuja-Orlin]] algorithm to prove that the total number of ''saturating'' push operations is in <math>\mathcal{O}(nm)</math>, applies here as well.

Finally, we consider the ''non-saturating'' push operations. First note that <math>D\geq 0</math> before and after each iteration. The value of <math>D</math> is increased in each relabel operation exactly by the amount by which the label of the current node is increased. Since node labels are never decreased and bounded from above by <math>2n-1</math>, <math>D</math> increases by less than <math>2n^2</math> in total over all relabel operations. On the other hand, a saturating push operation may increase <math>D</math> by at most <math>2n-1</math> (namely, in the case that <math>w</math> was not active immediately before the push). In summary, the total sum of all values by which <math>D</math> is increased throughout the algorithm is in <math>\mathcal{O}(n^2m)</math>. Due to the variant, the value of <math>D</math> is decreased by at least one in each non-saturating push operation. This proves the claim.

== Heuristic speedup techniques ==

# After <math>\Omega(n)</math> iterations of the main loop, the <math>d</math>-values are recomputed analogously to the induction basis: as the current distance of each node to <math>t</math> in the residual network. This modification is seldom enough, so the asymptotic complexity is not increased. In practice, this technique may save many unnecessary relabel steps.
# The main loop may be decomposed into two phases: First, as much flow as possible is sent into <math>t</math>; second, all surplus flow that cannot reach <math>t</math> is sent back to <math>s</math>. The first phase may be finished once there is no more path in the residual network from any active node to <math>t</math>. A sufficient and easy-to-check condition for that is <math>d(v)\geq n</math> for all active nodes <math>v</math>. All nodes from which <math>t</math> is reachable may be safely disregarded in the second phase. For any other node, to save unnecessary relabel operations, the distance label may be safely increased to the minimum number of arcs in the residual network from this node back to <math>s</math>.

FIFO preflow-push

2015-02-04T17:56:25Z

BB91: /* Complexity */

== Abstract view ==

This is a specialization of the [[Preflow-push|generic preflow-push algorithm]]:
# The set of all [[Basic flow definitions#Preflow|active nodes]] is stored in a [[Sets and sequences#Stacks and queues|FIFO queue]] <math>Q</math>.
# Always choose the first node in <math>Q</math> (recall from the generic preflow-push that this node is not extracted from <math>Q</math> as long as it is active).

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}(n^3)</math>, where <math>n=|V|</math>.

'''Proof:'''
The [[Preflow-push#Complexity|complexity considerations]] for the [[Preflow-push|generic preflow-push algorithm]] yield <math>\mathcal{O}(n^2)</math> relabel operations and forward steps of current arcs, and <math>\mathcal{O}(n\!\cdot\!m)\subseteq\mathcal{O}(n^3)</math> saturating push operations, where <math>m=|A|</math>. There it was also shown that the total number of changes of outgoing arcs is in <math>\mathcal{O}(n^3)</math>. Hence, it remains to show that the total number of non-saturating push operations is in <math>\mathcal{O}(n^3)</math> as well.

Conceptually, we may partition the iterations of the main loop into ''phases''. The first phase commences with the very first iteration. A new phase commences as soon as all nodes that were in <math>Q</math> at the beginning of the last phase, have been extracted once from <matH>Q</math>. Before and after each iteration, let <math>D</math> denote the maximum label <math>d(v)</math> of any active node <math>v\in V\setminus\{s,t\}</math>. In particular, it is always <math>0\leq D<2n</math>. Clearly, only relabel operations can increase <math>D</math>, and the sum of all increases of <math>D</math>, taken over all relabel operations, cannot increase <math>D</math> by more than <math>2n^2</math> in total.

This observation immediately implies that the number of phases in which at least one relabeling operation takes place, is in <math>\mathcal{O}(n^2)</math>. On the other hand, <math>D</math> is decreased in every phase without relabel operation, because in this case, all excess is pushed from each active node to a node with smaller <math>d</math>-label. Due to the bound <math>\mathcal{O}(n^2)</math> on all increases of <math>D</math>, the number of ''de''creases of <math>D</math> and, hence, the number of phases without relabel operations is in <math>\mathcal{O}(n^2)</math> as well. The claim now follows from the observation that, in each phase, at most one non-saturating push is performed with each node because a non-saturating push makes a node inactive.

Preflow-push

2015-02-04T17:34:04Z

BB91: /* Abstract view */ current arc muss im Residualgraph sein

== Abstract view ==

'''Algorithmic problem:'''
[[Max-Flow Problems#Standard version|max-flow problem (standard version)]]

'''Type of algorithm:'''
loop.

'''Auxiliary data:'''
# A nonnegative integral value <math>d(v)</math> for each node <math>v\in V</math>.
# Each node <math>v\in V\setminus\{t\}</math> has a '''current arc''', which may be implemented as an iterator on the list of outgoing residual arcs of <math>v</math>.
# The [[Basic flow definitions#Preflow|excess]] <math>e_f(v)</math> of a node <math>v\in V\setminus\{s,t\}</math> with respect to the current [[Basic flow definitions#Preflow|preflow]].
# A (dynamically changing) [[Sets and sequences|set]] <math>S</math> of nodes.

'''Invariant:'''
Before and after each iteration:
# For each arc <math>a\in A</math>, it is <math>0\leq f(a)\leq u(a)</math> . If all upper bounds are integral, all <math>f</math>-values are integral, too.
# For each node <math>v\in V\setminus\{s,t\} </math>, it is <math>e_f(v)\geq 0</math>. In other words, <math>f</math> is a [[Basic flow definitions#Preflow|preflow]].
# The node labels <math>d</math> form a [[Basic flow definitions#Valid distance labeling|valid distance labeling]], and it is <math>d(s)=|V|</math>.
# The currently [[Basic flow definitions#Preflow|active nodes]] are stored in <math>S</math>.

'''Variant:'''
In each iteration, one of the following three actions will take place:
# The label <math>d(v)</math> of at least one node <math>v\in V\setminus\{s,t\}</math> is increased.
# A saturating push is performed.
# The value of <math>D:=\sum_{v\in V\setminus\{s,t\}\atop e_f(v)>0}d(v)</math> decreases.
No label <math>d(\cdot)</math> is ever decreased.

'''Break condition:'''
<math>S=\emptyset</math>.

== Induction basis ==

'''Abstract view:'''
# For all arcs <math>a\in A</math>, set <math>f(a):=0</math>.
# For each arc <math>(s,v)\in A</math>, overwrite this value by <math>f(a):=u(a)</math> and put <math>v</math> into <math>S</math>.
# Compute a [[Basic flow definitions#Valid distance labeling|valid distance labeling]] <math>d</math> for <math>V\setminus\{s\}</math> with respect to <math>f</math>, for example, the true distances from all nodes to <math>t</math> in the residual network of <math>f</math>.
# Set <math>d(s):=n</math>.
# For all <math>v\in V\setminus\{s,t\}</math>, reset the current arc of <math>v</math> so as to point to the first arc in the list of outgoing arcs of <math>v</math>.

'''Proof:'''
For the [[Basic graph definitions#Subgraphs|subgraph induced]] by <math>V\setminus\{s\}</math>, the arguments in the [[Ahuja-Orlin#Correctness|correctness proof]] for the [[Ahuja-Orlin]] algorithm prove that the <math>d</math>-labels form a valid distance labeling here as well. For <math>s</math>, nothing is to show because all outgoing arcs are saturated.

== Induction step ==

'''Abstract view:'''
# Choose an [[Basic flow definitions#Preflow|active node]] <math>v</math> from <math>S</math>.
# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling|admissible]] either, move the current arc one step forward.
# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:
## If <math>w\neq s</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.
## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.
## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.
## If <math>e_f(v)=0</math> now, extract <math>v</math> from <math>S</math>.
# Otherwise:
## Let <math>d_\max</math> denote the minimal label <math>d(w)</math> of any arc <math>(v,w)</math> in the residual network.
## Set <math>d(v):=d_\max+1</math>.
## Reset the current arc of <math>v</math> so as to point to the beginning of the list of outgoing arcs of <math>v</math>.

'''Remark:'''
The preflow-push algorithm is also known as the '''push-relabel''' algorithm. The ''push'' operation is step 3; the ''relabel'' operation is step 4.

'''Proof:'''
Points 1, 2, and 4 of the invariant and <math>d(s)=n</math> are obviously fulfilled. The rest of point 3 of the invariant is affected by step 4 only, and the outgoing arcs of <math>v</math> are the only arcs where the distance labeling may become invalid. However, the extremely conservative increase of <math>d(v)</math> ensures point 3 of the invariant.

To prove the variant, consider a step in which neither any <math>d</math>-value is increased nor a saturating push is performed. This means step 3.2 is applied, but the arc <math>(v,w)</math> is not saturated by that. Potentially, <math>w</math> becomes active. However, <math>v</math> definitely becomes inactive since the push step is non-saturating. Now the variant follows from the fact that <math>d(w)=d(v)-1</math> for an admissible arc <math>(v,w)</math>.

It remains to show termination; this is proved by the following complexity considerations.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}(n^2m)</math>, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
First we show that the total number of relabel operations (step 4 of the main loop) is in <math>\mathcal{O}(n^2)</math>. To see that, let <math>v\in V\setminus\{s,t\}</math> be an active node between two iterations of the main loop. A straightforward induction over the number of push operations shows that there is at least one simple <math>(s,v)</math>-path <math>p</math> with positive flow on all arcs. The [[Basic graph definitions#Transpose of a graph|transpose]] of <math>p</math> is [[Basic flow definitions#Flow-augmenting paths and saturated arcs|augmenting]]. Due to the validity of <math>d</math> (induction hypothesis), <math>d(v)-d(s)=d(v)-n</math> cannot be larger than the number of arcs on <math>p</math>, which is not larger than <math>n-1</math>. Therefore, no node label can be larger than <math>2n-1</math>. Since node labels are nonnegative and increase at least by one in each relabel operation, the claimed upper bound on the relabel operations follows.

From this bound, we may immediately conclude that the current arc of a node is reset <math>\mathcal{O}(n)</math> times, so the total number of forward steps of the current arcs of all nodes is in <math>\mathcal{O}(n^3)</math> (<math>n</math> nodes and at most <math>n-1</math> outgoing residual arcs per node).

The argument in the [[Ahuja-Orlin#Complexity|complexity analysis]] of the [[Ahuja-Orlin]] algorithm to prove that the total number of ''saturating'' push operations is in <math>\mathcal{O}(nm)</math>, applies here as well.

Finally, we consider the ''non-saturating'' push operations. First note that <math>D\geq 0</math> before and after each iteration. The value of <math>D</math> is increased in each relabel operation exactly by the amount by which the label of the current node is increased. Since node labels are never decreased and bounded from above by <math>2n-1</math>, <math>D</math> increases by less than <math>2n^2</math> in total over all relabel operations. On the other hand, a saturating push operation may increase <math>D</math> by at most <math>2n-1</math> (namely, in the case that <math>w</math> was not active immediately before the push). In summary, the total sum of all values by which <math>D</math> is increased throughout the algorithm is in <math>\mathcal{O}(n^2m)</math>. Due to the variant, the value of <math>D</math> is decreased by at least one in each non-saturating push operation. This proves the claim.

== Heuristic speedup techniques ==

# After <math>\Omega(n)</math> iterations of the main loop, the <math>d</math>-values are recomputed analogously to the induction basis: as the current distance of each node to <math>t</math> in the residual network. This modification is seldom enough, so the asymptotic complexity is not increased. In practice, this technique may save many unnecessary relabel steps.
# The main loop may be decomposed into two phases: First, as much flow as possible is sent into <math>t</math>; second, all surplus flow that cannot reach <math>t</math> is sent back to <math>s</math>. The first phase may be finished once there is no more path in the residual network from any active node to <math>t</math>. A sufficient and easy-to-check condition for that is <math>d(v)\geq n</math> for all active nodes <math>v</math>. All nodes from which <math>t</math> is reachable may be safely disregarded in the second phase. For any other node, to save unnecessary relabel operations, the distance label may be safely increased to the minimum number of arcs in the residual network from this node back to <math>s</math>.

Preflow-push

2015-02-04T17:31:30Z

BB91: /* Complexity */ Korrektur der Anzahl an Vorwärtsschritten der current arc

== Abstract view ==

'''Algorithmic problem:'''
[[Max-Flow Problems#Standard version|max-flow problem (standard version)]]

'''Type of algorithm:'''
loop.

'''Auxiliary data:'''
# A nonnegative integral value <math>d(v)</math> for each node <math>v\in V</math>.
# Each node <math>v\in V\setminus\{t\}</math> has a '''current arc''', which may be implemented as an iterator on the list of outgoing arcs of <math>v</math>.
# The [[Basic flow definitions#Preflow|excess]] <math>e_f(v)</math> of a node <math>v\in V\setminus\{s,t\}</math> with respect to the current [[Basic flow definitions#Preflow|preflow]].
# A (dynamically changing) [[Sets and sequences|set]] <math>S</math> of nodes.

'''Invariant:'''
Before and after each iteration:
# For each arc <math>a\in A</math>, it is <math>0\leq f(a)\leq u(a)</math> . If all upper bounds are integral, all <math>f</math>-values are integral, too.
# For each node <math>v\in V\setminus\{s,t\} </math>, it is <math>e_f(v)\geq 0</math>. In other words, <math>f</math> is a [[Basic flow definitions#Preflow|preflow]].
# The node labels <math>d</math> form a [[Basic flow definitions#Valid distance labeling|valid distance labeling]], and it is <math>d(s)=|V|</math>.
# The currently [[Basic flow definitions#Preflow|active nodes]] are stored in <math>S</math>.

'''Variant:'''
In each iteration, one of the following three actions will take place:
# The label <math>d(v)</math> of at least one node <math>v\in V\setminus\{s,t\}</math> is increased.
# A saturating push is performed.
# The value of <math>D:=\sum_{v\in V\setminus\{s,t\}\atop e_f(v)>0}d(v)</math> decreases.
No label <math>d(\cdot)</math> is ever decreased.

'''Break condition:'''
<math>S=\emptyset</math>.

== Induction basis ==

'''Abstract view:'''
# For all arcs <math>a\in A</math>, set <math>f(a):=0</math>.
# For each arc <math>(s,v)\in A</math>, overwrite this value by <math>f(a):=u(a)</math> and put <math>v</math> into <math>S</math>.
# Compute a [[Basic flow definitions#Valid distance labeling|valid distance labeling]] <math>d</math> for <math>V\setminus\{s\}</math> with respect to <math>f</math>, for example, the true distances from all nodes to <math>t</math> in the residual network of <math>f</math>.
# Set <math>d(s):=n</math>.
# For all <math>v\in V\setminus\{s,t\}</math>, reset the current arc of <math>v</math> so as to point to the first arc in the list of outgoing arcs of <math>v</math>.

'''Proof:'''
For the [[Basic graph definitions#Subgraphs|subgraph induced]] by <math>V\setminus\{s\}</math>, the arguments in the [[Ahuja-Orlin#Correctness|correctness proof]] for the [[Ahuja-Orlin]] algorithm prove that the <math>d</math>-labels form a valid distance labeling here as well. For <math>s</math>, nothing is to show because all outgoing arcs are saturated.

== Induction step ==

'''Abstract view:'''
# Choose an [[Basic flow definitions#Preflow|active node]] <math>v</math> from <math>S</math>.
# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling|admissible]] either, move the current arc one step forward.
# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:
## If <math>w\neq s</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.
## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.
## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.
## If <math>e_f(v)=0</math> now, extract <math>v</math> from <math>S</math>.
# Otherwise:
## Let <math>d_\max</math> denote the minimal label <math>d(w)</math> of any arc <math>(v,w)</math> in the residual network.
## Set <math>d(v):=d_\max+1</math>.
## Reset the current arc of <math>v</math> so as to point to the beginning of the list of outgoing arcs of <math>v</math>.

'''Remark:'''
The preflow-push algorithm is also known as the '''push-relabel''' algorithm. The ''push'' operation is step 3; the ''relabel'' operation is step 4.

'''Proof:'''
Points 1, 2, and 4 of the invariant and <math>d(s)=n</math> are obviously fulfilled. The rest of point 3 of the invariant is affected by step 4 only, and the outgoing arcs of <math>v</math> are the only arcs where the distance labeling may become invalid. However, the extremely conservative increase of <math>d(v)</math> ensures point 3 of the invariant.

To prove the variant, consider a step in which neither any <math>d</math>-value is increased nor a saturating push is performed. This means step 3.2 is applied, but the arc <math>(v,w)</math> is not saturated by that. Potentially, <math>w</math> becomes active. However, <math>v</math> definitely becomes inactive since the push step is non-saturating. Now the variant follows from the fact that <math>d(w)=d(v)-1</math> for an admissible arc <math>(v,w)</math>.

It remains to show termination; this is proved by the following complexity considerations.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}(n^2m)</math>, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
First we show that the total number of relabel operations (step 4 of the main loop) is in <math>\mathcal{O}(n^2)</math>. To see that, let <math>v\in V\setminus\{s,t\}</math> be an active node between two iterations of the main loop. A straightforward induction over the number of push operations shows that there is at least one simple <math>(s,v)</math>-path <math>p</math> with positive flow on all arcs. The [[Basic graph definitions#Transpose of a graph|transpose]] of <math>p</math> is [[Basic flow definitions#Flow-augmenting paths and saturated arcs|augmenting]]. Due to the validity of <math>d</math> (induction hypothesis), <math>d(v)-d(s)=d(v)-n</math> cannot be larger than the number of arcs on <math>p</math>, which is not larger than <math>n-1</math>. Therefore, no node label can be larger than <math>2n-1</math>. Since node labels are nonnegative and increase at least by one in each relabel operation, the claimed upper bound on the relabel operations follows.

From this bound, we may immediately conclude that the current arc of a node is reset <math>\mathcal{O}(n)</math> times, so the total number of forward steps of the current arcs of all nodes is in <math>\mathcal{O}(n^3)</math> (<math>n</math> nodes and at most <math>n-1</math> outgoing residual arcs per node).

The argument in the [[Ahuja-Orlin#Complexity|complexity analysis]] of the [[Ahuja-Orlin]] algorithm to prove that the total number of ''saturating'' push operations is in <math>\mathcal{O}(nm)</math>, applies here as well.

Finally, we consider the ''non-saturating'' push operations. First note that <math>D\geq 0</math> before and after each iteration. The value of <math>D</math> is increased in each relabel operation exactly by the amount by which the label of the current node is increased. Since node labels are never decreased and bounded from above by <math>2n-1</math>, <math>D</math> increases by less than <math>2n^2</math> in total over all relabel operations. On the other hand, a saturating push operation may increase <math>D</math> by at most <math>2n-1</math> (namely, in the case that <math>w</math> was not active immediately before the push). In summary, the total sum of all values by which <math>D</math> is increased throughout the algorithm is in <math>\mathcal{O}(n^2m)</math>. Due to the variant, the value of <math>D</math> is decreased by at least one in each non-saturating push operation. This proves the claim.

== Heuristic speedup techniques ==

# After <math>\Omega(n)</math> iterations of the main loop, the <math>d</math>-values are recomputed analogously to the induction basis: as the current distance of each node to <math>t</math> in the residual network. This modification is seldom enough, so the asymptotic complexity is not increased. In practice, this technique may save many unnecessary relabel steps.
# The main loop may be decomposed into two phases: First, as much flow as possible is sent into <math>t</math>; second, all surplus flow that cannot reach <math>t</math> is sent back to <math>s</math>. The first phase may be finished once there is no more path in the residual network from any active node to <math>t</math>. A sufficient and easy-to-check condition for that is <math>d(v)\geq n</math> for all active nodes <math>v</math>. All nodes from which <math>t</math> is reachable may be safely disregarded in the second phase. For any other node, to save unnecessary relabel operations, the distance label may be safely increased to the minimum number of arcs in the residual network from this node back to <math>s</math>.

Preflow-push

2015-02-03T19:32:11Z

BB91: /* Induction step */

== Abstract view ==

'''Algorithmic problem:'''
[[Max-Flow Problems#Standard version|max-flow problem (standard version)]]

'''Type of algorithm:'''
loop.

'''Auxiliary data:'''
# A nonnegative integral value <math>d(v)</math> for each node <math>v\in V</math>.
# Each node <math>v\in V\setminus\{t\}</math> has a '''current arc''', which may be implemented as an iterator on the list of outgoing arcs of <math>v</math>.
# The [[Basic flow definitions#Preflow|excess]] <math>e_f(v)</math> of a node <math>v\in V\setminus\{s,t\}</math> with respect to the current [[Basic flow definitions#Preflow|preflow]].
# A (dynamically changing) [[Sets and sequences|set]] <math>S</math> of nodes.

'''Invariant:'''
Before and after each iteration:
# For each arc <math>a\in A</math>, it is <math>0\leq f(a)\leq u(a)</math> . If all upper bounds are integral, all <math>f</math>-values are integral, too.
# For each node <math>v\in V\setminus\{s,t\} </math>, it is <math>e_f(v)\geq 0</math>. In other words, <math>f</math> is a [[Basic flow definitions#Preflow|preflow]].
# The node labels <math>d</math> form a [[Basic flow definitions#Valid distance labeling|valid distance labeling]], and it is <math>d(s)=|V|</math>.
# The currently [[Basic flow definitions#Preflow|active nodes]] are stored in <math>S</math>.

'''Variant:'''
In each iteration, one of the following three actions will take place:
# The label <math>d(v)</math> of at least one node <math>v\in V\setminus\{s,t\}</math> is increased.
# A saturating push is performed.
# The value of <math>D:=\sum_{v\in V\setminus\{s,t\}\atop e_f(v)>0}d(v)</math> decreases.
No label <math>d(\cdot)</math> is ever decreased.

'''Break condition:'''
<math>S=\emptyset</math>.

== Induction basis ==

'''Abstract view:'''
# For all arcs <math>a\in A</math>, set <math>f(a):=0</math>.
# For each arc <math>(s,v)\in A</math>, overwrite this value by <math>f(a):=u(a)</math> and put <math>v</math> into <math>S</math>.
# Compute a [[Basic flow definitions#Valid distance labeling|valid distance labeling]] <math>d</math> for <math>V\setminus\{s\}</math> with respect to <math>f</math>, for example, the true distances from all nodes to <math>t</math> in the residual network of <math>f</math>.
# Set <math>d(s):=n</math>.
# For all <math>v\in V\setminus\{s,t\}</math>, reset the current arc of <math>v</math> so as to point to the first arc in the list of outgoing arcs of <math>v</math>.

'''Proof:'''
For the [[Basic graph definitions#Subgraphs|subgraph induced]] by <math>V\setminus\{s\}</math>, the arguments in the [[Ahuja-Orlin#Correctness|correctness proof]] for the [[Ahuja-Orlin]] algorithm prove that the <math>d</math>-labels form a valid distance labeling here as well. For <math>s</math>, nothing is to show because all outgoing arcs are saturated.

== Induction step ==

'''Abstract view:'''
# Choose an [[Basic flow definitions#Preflow|active node]] <math>v</math> from <math>S</math>.
# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling|admissible]] either, move the current arc one step forward.
# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:
## If <math>w\neq s</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.
## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.
## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.
## If <math>e_f(v)=0</math> now, extract <math>v</math> from <math>S</math>.
# Otherwise:
## Let <math>d_\max</math> denote the minimal label <math>d(w)</math> of any arc <math>(v,w)</math> in the residual network.
## Set <math>d(v):=d_\max+1</math>.
## Reset the current arc of <math>v</math> so as to point to the beginning of the list of outgoing arcs of <math>v</math>.

'''Remark:'''
The preflow-push algorithm is also known as the '''push-relabel''' algorithm. The ''push'' operation is step 3; the ''relabel'' operation is step 4.

'''Proof:'''
Points 1, 2, and 4 of the invariant and <math>d(s)=n</math> are obviously fulfilled. The rest of point 3 of the invariant is affected by step 4 only, and the outgoing arcs of <math>v</math> are the only arcs where the distance labeling may become invalid. However, the extremely conservative increase of <math>d(v)</math> ensures point 3 of the invariant.

To prove the variant, consider a step in which neither any <math>d</math>-value is increased nor a saturating push is performed. This means step 3.2 is applied, but the arc <math>(v,w)</math> is not saturated by that. Potentially, <math>w</math> becomes active. However, <math>v</math> definitely becomes inactive since the push step is non-saturating. Now the variant follows from the fact that <math>d(w)=d(v)-1</math> for an admissible arc <math>(v,w)</math>.

It remains to show termination; this is proved by the following complexity considerations.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}(n^2m)</math>, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
First we show that the total number of relabel operations (step 4 of the main loop) is in <math>\mathcal{O}(n^2)</math>. To see that, let <math>v\in V\setminus\{s,t\}</math> be an active node between two iterations of the main loop. A straightforward induction over the number of push operations shows that there is at least one simple <math>(s,v)</math>-path <math>p</math> with positive flow on all arcs. The [[Basic graph definitions#Transpose of a graph|transpose]] of <math>p</math> is [[Basic flow definitions#Flow-augmenting paths and saturated arcs|augmenting]]. Due to the validity of <math>d</math> (induction hypothesis), <math>d(v)-d(s)=d(v)-n</math> cannot be larger than the number of arcs on <math>p</math>, which is not larger than <math>n-1</math>. Therefore, no node label can be larger than <math>2n-1</math>. Since node labels are nonnegative and increase at least by one in each relabel operation, the claimed upper bound on the relabel operations follows.

From this bound, we may immediately conclude that the current arc of a node is reset <math>\mathcal{O}(n)</math> times, so the total number of forward steps of the current arcs of all nodes is in <math>\mathcal{O}(n^2)</math>.

The argument in the [[Ahuja-Orlin#Complexity|complexity analysis]] of the [[Ahuja-Orlin]] algorithm to prove that the total number of ''saturating'' push operations is in <math>\mathcal{O}(nm)</math>, applies here as well.

Finally, we consider the ''non-saturating'' push operations. First note that <math>D\geq 0</math> before and after each iteration. The value of <math>D</math> is increased in each relabel operation exactly by the amount by which the label of the current node is increased. Since node labels are never decreased and bounded from above by <math>2n-1</math>, <math>D</math> increases by less than <math>2n^2</math> in total over all relabel operations. On the other hand, a saturating push operation may increase <math>D</math> by at most <math>2n-1</math> (namely, in the case that <math>w</math> was not active immediately before the push). In summary, the total sum of all values by which <math>D</math> is increased throughout the algorithm is in <math>\mathcal{O}(n^2m)</math>. Due to the variant, the value of <math>D</math> is decreased by at least one in each non-saturating push operation. This proves the claim.

== Heuristic speedup techniques ==

# After <math>\Omega(n)</math> iterations of the main loop, the <math>d</math>-values are recomputed analogously to the induction basis: as the current distance of each node to <math>t</math> in the residual network. This modification is seldom enough, so the asymptotic complexity is not increased. In practice, this technique may save many unnecessary relabel steps.
# The main loop may be decomposed into two phases: First, as much flow as possible is sent into <math>t</math>; second, all surplus flow that cannot reach <math>t</math> is sent back to <math>s</math>. The first phase may be finished once there is no more path in the residual network from any active node to <math>t</math>. A sufficient and easy-to-check condition for that is <math>d(v)\geq n</math> for all active nodes <math>v</math>. All nodes from which <math>t</math> is reachable may be safely disregarded in the second phase. For any other node, to save unnecessary relabel operations, the distance label may be safely increased to the minimum number of arcs in the residual network from this node back to <math>s</math>.

Dinic

2015-01-08T10:43:29Z

BB91: /* Induction step */ auch V wird i.A. reduziert

== General Information ==

'''Algorithmic problem:''' [[Max-Flow Problems#Standard version|Max-flow problem (standard version)]]

'''Type of algorithm :''' loop.

== Abstract View ==

'''Invariant:'''
After <math>i \ge 0</math> iterations:
#The flow <math>f</math> is feasible.
# If all upper bounds are integral, the <math>f</math>-values are integral as well.

'''Variant:'''
The smallest number of arcs on a flow-augmenting <math>(s,t)</math>-path strictly increases.

'''Break condition:''' There is no flow-augmenting <math>(s,t)</math>-path anymore.

== Induction basis ==

'''Abstract view:'''
Initialize <math>f</math> as an arbitrary feasible flow, for example, the zero flow.

'''Proof:'''
Nothing to show.

== Induction step ==

'''Abstract view:'''
# Construct the [[Basic graph definitions#Cycles|acyclic]] [[Basic graph definitions#Subgraphs|subgraph]] <math>G'=(V',A')</math> of the residual network that contains an arc if, and only if, the arc is on at least one <math>(s,t)</math>-path with smallest number of arcs (and contains all nodes incident to these arcs).
# Use one of the algorithms for the [[Blocking flow|blocking flow]] problem to construct a blocking flow <math>f'</math> in <math>G'</math> with respect to the residual capacities for <math>f</math>.
# Add <math>f'</math> to <math>f</math>.

'''Proof:''' Obvious.

== Correctness ==

Feasibility of <math>f</math> follows immediately from the invariant. If the algorithm terminates, the break condition immediately proves maximality along with the [[Max-flow min-cut|max-flow min-cut theorem]]. Termination follows immediately from the following complexity considerations.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}(n\cdot T(n,m))</math>, where <math>n=|V|</math>, <math>m=|A|</math>, and <math>T(n,m)</math> is the asymptotic complexity of the blocking-flow algorithm.

'''Proof:'''
Evidenty, the smallest number of arcs on a flow-augmenting <math>(s,t)</math>-path cannot exceed <math>n-1</math>. Therefore, the variant implies that the algorithm terminates after <math>n-1</math> iterations. The complexity of a single iteration is dominated by the computation of a blocking flow.

Max-flow min-cut

2015-01-03T09:29:23Z

BB91: /* Proof */

== Max-flow min-cut theorem ==

Let <math>G=(V,A)</math>, <math>s,t\in V</math>, and for <math>a\in A</math> let <math>u(a)</math> and <math>f(a)</math> be real values such that <math>0\leq f(a)\leq u(a)</math> and <math>f</math> is a [[Basic flow definitions#Feasible flow|feasible <math>(s,t)</math>-flow]]. Then the following three statements are equivalent:
# The [[Basic flow definitions#Flow value|flow value]] of <math>f</math> is maximum among all [[Basic flow definitions#Feasible flow|feasible <math>(s,t)</math>-flows]].
# There is a [[Basic flow definitions#Cuts and saturated cuts|saturated cut]].
# There is no [[Basic flow definitions#Flow-augmenting paths and saturated arcs|flow-augmenting path]] from <math>s</math> to <math>t</math>.

== Proof ==

First suppose there is no [[Basic flow definitions#Flow-augmenting paths and saturated arcs|flow-augmenting path]] from <math>s</math> to <math>t</math>. Let <math>S</math> denote the set of all nodes reachable from <math>s</math> via flow-augmenting paths, and let <math>T:=V\setminus S</math>. Then we have <math>s\in S</math> and <math>t\in T</math>. Obviously, <math>(S,T)</math> is [[Basic flow definitions#Cuts and saturated cuts|saturated]].

Next suppose there is a [[Basic flow definitions#Cuts and saturated cuts|saturated]] cut. No flow <math>f'</math> can carry more units of flow value from <math>s</math> to <math>t</math> than the capacity of any [[Basic flow definitions#Cuts and saturated cuts|<math>(s,t)</math>-cut]] allows. Consequently, <math>f</math> is maximum.

Finally suppose <math>f</math> is maximum. Clearly, then a [[Basic flow definitions#Flow-augmenting paths and saturated arcs|flow-augmenting path]] from <math>s</math> to <math>t</math> cannot exist.

Max-flow min-cut

2015-01-03T09:27:12Z

BB91: /* Proof */ Konkretisierung der Formulierung + Links eingefügt

Max-flow min-cut

2015-01-03T09:19:21Z

BB91:

== Max-flow min-cut theorem ==

Let <math>G=(V,A)</math>, <math>s,t\in V</math>, and for <math>a\in A</math> let <math>u(a)</math> and <math>f(a)</math> be real values such that <math>0\leq f(a)\leq u(a)</math> and <math>f</math> is a [[Basic flow definitions#Feasible flow|feasible <math>(s,t)</math>-flow]]. Then the following three statements are equivalent:
# The [[Basic flow definitions#Flow value|flow value]] of <math>f</math> is maximum among all [[Basic flow definitions#Feasible flow|feasible <math>(s,t)</math>-flows]].
# There is a [[Basic flow definitions#Cuts and saturated cuts|saturated cut]].
# There is no [[Basic flow definitions#Flow-augmenting paths and saturated arcs|flow-augmenting path]] from <math>s</math> to <math>t</math>.

== Proof ==

First suppose there is no flow-augmenting path from <math>s</math> to <math>t</math>. Let <math>S</math> denote the set of all nodes reachable from <math>s</math> via flow-augmenting paths, and let <math>T:=V\setminus S</math>. Then we have <math>s\in S</math> and <math>t\in T</math>. Obviously, <math>(S,T)</math> is saturated.

Next suppose there is a saturated cut. No flow <math>f'</math> can carry more units of flow value from <math>S</math> to <math>T</math> than the capacity of any cut allows. Consequently, <math>f</math> is maximum.

Finally suppose <math>f</math> is maximum. Clearly, then a flow-augmenting path cannot exist.

Max-Flow Problems

2015-01-02T16:18:18Z

BB91: Undo revision 2722 by BB91 (talk) Irrtum

== Basic definitions ==

# [[Basic graph definitions]]
# [[Basic flow definitions]]

== Standard version ==

'''Input:'''
# A directed graph <math>G=(V,A)</math>.
# A '''source node''' <math>s\in V</math> and a '''target (a.k.a. sink) node''' <math>t\in V</math>.
# A nonnegative '''upper bound (a.k.a. capacity)''' <math>u(a)</math> for each arc <math>a\in A</math>.

'''Output:'''
A [[Basic flow definitions#Feasible flow|feasible <math>(s,t)</math>-flow]] that has maximum [[Basic flow definitions#Flow value|flow value]] among all feasible <math>(s,t)</math>-flows.

== Known algorithms ==

# [[Ford-Fulkerson]]
# [[Edmonds-Karp]]
# [[Ahuja-Orlin]]
# [[Dinic]]
# [[Preflow-push]]
# [[FIFO preflow-push]]
# [[Preflow-push with excess scaling]]

== Generalizations ==

# For each arc <math>a\in A</math>, there is a '''lower bound''' <math>\ell(a)</math>, and <math>f(a)\geq\ell(a)</math> is additionally required. The lower bounds need not be nonnegative, so the flow values need not be nonnegative, either. This version is often called '''maximum flow with edge demands'''. It may be reduced to solving two instances of the standard version as follows:
## First, we construct a new graph <math>G'=(V',A')</math> as follows: We add a super-source <math>s'</math> and a super-target <math>t'</math> to <math>V</math>. Next, for every node <math>v\in V</math>, we add an arc <math>(s',v)</math> and an arc <math>(v,t')</math> to <math>A</math>. Finally we add an arc <math>(t,s)</math> to <math>A</math>, if not in <math>A</math> yet.
## For all arcs <math>a\in A</math>, we set <math>\ell'(a):=0</math>. For each node <math>v\in V</math>, we set
##:<math>u'(s',v):=\sum_{(w,v)\in A}\ell(w,v)</math> and <math>u'(v,t'):=\sum_{(v,w)\in A} \ell(v,w)</math>.
##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.
## It is easy to see that there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math> if, and only if, all arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are saturated. This the case if, and only if, the maximum flow <math>f'</math> in <math>G</math> from <math>s'</math> to <math>t'</math> with respect to <math>\ell'</math> and <math>u'</math> yields a flow of value <math>\sum_{a\in A}\ell(a)</math>.
## More specifically, for <math>(v,w)\in A</math>, we set <math>f(v,w):=f'(v,w)+\ell(v,w)</math>.[[File:Maxflowmultiplesource.png|350px|thumb|right|Max-Flow Problem with several sources and targets]]
# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").
# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow an the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).
# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.

Max-Flow Problems

2015-01-02T16:05:28Z

BB91: /* Generalizations */ Hilfskapazitäten

== Basic definitions ==

# [[Basic graph definitions]]
# [[Basic flow definitions]]

== Standard version ==

'''Input:'''
# A directed graph <math>G=(V,A)</math>.
# A '''source node''' <math>s\in V</math> and a '''target (a.k.a. sink) node''' <math>t\in V</math>.
# A nonnegative '''upper bound (a.k.a. capacity)''' <math>u(a)</math> for each arc <math>a\in A</math>.

'''Output:'''
A [[Basic flow definitions#Feasible flow|feasible <math>(s,t)</math>-flow]] that has maximum [[Basic flow definitions#Flow value|flow value]] among all feasible <math>(s,t)</math>-flows.

== Known algorithms ==

# [[Ford-Fulkerson]]
# [[Edmonds-Karp]]
# [[Ahuja-Orlin]]
# [[Dinic]]
# [[Preflow-push]]
# [[FIFO preflow-push]]
# [[Preflow-push with excess scaling]]

== Generalizations ==

# For each arc <math>a\in A</math>, there is a '''lower bound''' <math>\ell(a)</math>, and <math>f(a)\geq\ell(a)</math> is additionally required. The lower bounds need not be nonnegative, so the flow values need not be nonnegative, either. This version is often called '''maximum flow with edge demands'''. It may be reduced to solving two instances of the standard version as follows:
## First, we construct a new graph <math>G'=(V',A')</math> as follows: We add a super-source <math>s'</math> and a super-target <math>t'</math> to <math>V</math>. Next, for every node <math>v\in V</math>, we add an arc <math>(s',v)</math> and an arc <math>(v,t')</math> to <math>A</math>. Finally we add an arc <math>(t,s)</math> to <math>A</math>, if not in <math>A</math> yet.
## For all arcs <math>a\in A</math>, we set <math>\ell'(a):=0</math>. For each node <math>v\in V</math>, we set
##:<math>u'(s',v):=\sum_{(v,w)\in A} \ell(v,w)</math> and <math>u'(v,t'):=\sum_{(w,v)\in A}\ell(w,v)</math>.
##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.
## It is easy to see that there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math> if, and only if, all arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are saturated. This the case if, and only if, the maximum flow <math>f'</math> in <math>G</math> from <math>s'</math> to <math>t'</math> with respect to <math>\ell'</math> and <math>u'</math> yields a flow of value <math>\sum_{a\in A}\ell(a)</math>.
## More specifically, for <math>(v,w)\in A</math>, we set <math>f(v,w):=f'(v,w)+\ell(v,w)</math>.[[File:Maxflowmultiplesource.png|350px|thumb|right|Max-Flow Problem with several sources and targets]]
# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").
# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow an the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).
# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.

Branching by Edmonds

2015-01-02T11:19:38Z

BB91: /* Recursive step */

== Abstract view ==

'''Algorithmic problem:''' [[Maximum branching]]

'''Definition:'''
# An arc <math>(v,w)\in A</math> is '''critical''' for <math>w\in V</math> if its weight is not smaller than the weight of any other incoming arc of <math>w</math>.
# A '''critical subgraph''' <math>G'=(V,A')</math> of <math>G</math> contains exactly one incoming arc <math>(v,w)\in A</math> for each node <math>w\in V</math> of positive indegree, where <math>(v,w)</math> is critical.

'''Type of algorithm:''' recursion

'''Invariant:''' The output of a recursive call is a maximum branching of the weighted graph that was the input for this recursive call.

== Recursion anchor ==

'''Abstract view:''' Terminate if <math>G'</math> is cycle-free.

'''Proof:'''
If <math>G'</math> is cycle-free, it is a branching. Consider some other branching <math>B</math>. We have to show that <math>B</math> does not have more total weight than <math>G'</math>.

By definition, a critical graph contains one incoming arc for each node that does have incoming arcs. Therefore, for each arc <math>a</math> of <math>B</math>, there is an arc <math>a'</math> in <math>G'</math> pointing to the same node. Due to the choice of arcs for <math>G'</math>, it is <math>w(a)\leq w(a')</math>.

== Recursive step ==
[[File:Edmonds max branching ani 10000.gif|thumb|350px|''animated gif:'' Branching by Edmonds]]
'''Abstract view:'''
# Compute a critical subgraph <math>G'=(V,A')</math> for the input graph <math>G</math>.
# Identify some cycle <math>C</math> in <math>G'</math>.
# Let <math>W</math> denote the minimum weight of all arcs on <math>C</math>.
# For every arc <math>(v,w)\in A</math> pointing from some node <math>v</math> outside <math>C</math> to some node <math>w</math> on <math>C</math>:
##Decrease the weight of <math>(v,w)</math> by <math>w(v',w)-W\geq 0</math>, where <math>(v',w)</math> is the incoming arc of <math>w</math> on <math>C</math>.
## If the new weight of <math>(v,w)</math> is not positive, remove <math>(v,w)</math> from <math>G</math>.
# Shrink <math>C</math> into one new super-node, where every arc pointing to (resp., from) some node on <math>C</math> now points to (from) that super-node.
# Call the algorithm recursively for the modified weighted graph after shrinking, giving branching <math>B</math>.
# Unshrink the graph.
# Add all arcs of <math>C</math> to <math>B</math> giving <math>B'</math>.
# If <math>B'</math> contains an arc <math>(v,w)</math> such that <math>v</math> is outside <math>C</math> and <math>w</math> is on <math>C</math>: remove the incoming arc of <math>w</math> on <math>C</math> from <math>B</math>; otherwise, remove one arc with weight <math>W</math> on <math>C</math>. Let <math>B''</math> be the result in both cases.
# Return <math>B''</math>.

'''Proof:'''
Obviously, <math>B''</math> is a branching, so we have to prove that it has maximum weight among all branchings in <math>G</math>. Let <math>B_{\mathrm{opt}}</math> be a maximum branching in <math>G</math> such that, among all maximum branchings in <math>G</math>, <math>B_{\mathrm{opt}}</math> shares as many arcs as possible with <math>B''</math>.

Let <math>C'</math> be a cycle of <math>G'</math> (the case <math>C'=C</math> not excluded). First we show that <math>B_{\mathrm{opt}}</math> contains all arcs of <math>C'</math> except one. So, suppose for a contradiction that <math>B_{\mathrm{opt}}</math> does not contain some of the arcs of <math>C'</math>, say, <math>(v_1,w_1),\ldots,(v_k,w_k)</math> with <math>k>1</math>.

Replacing the incoming arc of any <math>w_i</math> by <math>(v_i,w_i)</math> in <math>B_{\mathrm{opt}}</math> and doing nothing else, would not decrease the total weight. Since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>, such a replacement cannot result in a branching anymore. Since the indegrees do not change by that replacement, this means that adding <math>(v_i,w_i)</math> to <math>B_{\mathrm{opt}}</math> would close a cycle. In other words, there is a path <math>p_i</math> in <math>B_{\mathrm{opt}}</math> from <math>w_i</math> to <math>v_i</math>. Each path <math>p_i</math> must enter <math>C'</math> at one of the nodes <math>w_j</math> (actually at the nearest <math>w_j</math> looking backwards from <math>v_i</math> on <math>C'</math>) because, otherwise, the node where <math>p_i</math> enters <math>C'</math> had two incoming arcs in <math>B_{\mathrm{opt}}</math>: the incoming arc on <math>C'</math> and the arc over which <math>p_i</math> enters <math>C'</math>. However, this would imply that there is a cycle in the union of all paths <math>p_i</math>. This union is a subset of <math>B_{\mathrm{opt}}</math>, which yields the desired contradiction.

Now we know that <math>B_{\mathrm{opt}}</math> contains all arcs except one on all cycles of <math>G'</math>. Note that, for any node not on a cycle, the incoming branching arc may be freely chosen (except for arcs which would close a cycle) without any effect on the rest. So, since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>,<math>B_{\mathrm{opt}}</math> and <math>B''</math> agree on all of these choices. Further note that all cycles of <math>G'</math> are node-disjoint. In summary, we may compare <math>B_{\mathrm{opt}}</math> and <math>B''</math> on each cycle of <math>G'</math> separately.

For <math>C</math>, complete agreement between <math>B_{\mathrm{opt}}</math> and <math>B''</math> follows from the observation that the choice of incoming arcs for all nodes on <math>C</math> is optimal in <math>B''</math> due to the specific modification of the arc weights. And for all other cycles of <math>G'</math>, complete agreement follows from the induction hypothesis. In both cases, we again used the specific choice of <math>B_{\mathrm{opt}}</math> to be as close to <math>B''</math> as possible.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}((n+m)\cdot n)</math> in the worst case, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
Using [[Depth-first search|DFS]] for cycle detection, each recursive step requires <math>\mathcal{O}(n+m)</math>. In each shrink operation, the number of nodes decreases, so the recursion depth is <math>\mathcal{O}(n)</math>.

'''Remark:'''
More sophisticated implementations of this algorithm yield better asymptotic complexities.

== Remarks ==

# The unshrink operation requires that the shrink operation performs some bookkeeping: For the super-node, a cyclically ordered sequence of all nodes and arcs on <math>C</math> (or an equivalent bulk of information) must be attached to a super-node.
# Several cycles may be discovered simultaneously by one run of [[Depth-first search|DFS]]. Note that all cycles in a critical graph are node-disjoint, because no node has more than one incoming arc. Therefore, several cycles may be handled in the same recursive call, without any interference.

Branching by Edmonds

2015-01-02T11:09:30Z

BB91: /* Recursive step */ Tipp zur Veranschaulichung

== Abstract view ==

'''Algorithmic problem:''' [[Maximum branching]]

'''Definition:'''
# An arc <math>(v,w)\in A</math> is '''critical''' for <math>w\in V</math> if its weight is not smaller than the weight of any other incoming arc of <math>w</math>.
# A '''critical subgraph''' <math>G'=(V,A')</math> of <math>G</math> contains exactly one incoming arc <math>(v,w)\in A</math> for each node <math>w\in V</math> of positive indegree, where <math>(v,w)</math> is critical.

'''Type of algorithm:''' recursion

'''Invariant:''' The output of a recursive call is a maximum branching of the weighted graph that was the input for this recursive call.

== Recursion anchor ==

'''Abstract view:''' Terminate if <math>G'</math> is cycle-free.

'''Proof:'''
If <math>G'</math> is cycle-free, it is a branching. Consider some other branching <math>B</math>. We have to show that <math>B</math> does not have more total weight than <math>G'</math>.

By definition, a critical graph contains one incoming arc for each node that does have incoming arcs. Therefore, for each arc <math>a</math> of <math>B</math>, there is an arc <math>a'</math> in <math>G'</math> pointing to the same node. Due to the choice of arcs for <math>G'</math>, it is <math>w(a)\leq w(a')</math>.

== Recursive step ==
[[File:Edmonds max branching ani 10000.gif|thumb|350px|''animated gif:'' Branching by Edmonds]]
'''Abstract view:'''
# Compute a critical subgraph <math>G'=(V,A')</math> for the input graph <math>G</math>.
# Identify some cycle <math>C</math> in <math>G'</math>.
# Let <math>W</math> denote the minimum weight of all arcs on <math>C</math>.
# For every arc <math>(v,w)\in A</math> pointing from some node <math>v</math> outside <math>C</math> to some node <math>w</math> on <math>C</math>:
##Decrease the weight of <math>(v,w)</math> by <math>w(v',w)-W\geq 0</math>, where <math>(v',w)</math> is the incoming arc of <math>w</math> on <math>C</math>.
## If the new weight of <math>(v,w)</math> is not positive, remove <math>(v,w)</math> from <math>G</math>.
# Shrink <math>C</math> into one new super-node, where every arc pointing to (resp., from) some node on <math>C</math> now points to (from) that super-node.
# Call the algorithm recursively for the modified weighted graph after shrinking, giving branching <math>B</math>.
# Unshrink the graph.
# Add all arcs of <math>C</math> to <math>B</math> giving <math>B'</math>.
# If <math>B'</math> contains an arc <math>(v,w)</math> such that <math>v</math> is outside <math>C</math> and <math>w</math> is on <math>C</math>: remove the incoming arc of <math>w</math> on <math>C</math> from <math>B</math>; otherwise, remove one arc with weight <math>W</math> on <math>C</math>. Let <math>B''</math> be the result in both cases.
# Return <math>B''</math>.

'''Proof:'''
Obviously, <math>B''</math> is a branching, so we have to prove that it has maximum weight among all branchings in <math>G</math>. Let <math>B_{\mathrm{opt}}</math> be a maximum branching in <math>G</math> such that, among all maximum branchings in <math>G</math>, <math>B_{\mathrm{opt}}</math> shares as many arcs as possible with <math>B''</math>.

Let <math>C'</math> be a cycle of <math>G'</math> (the case <math>C'=C</math> not excluded). First we show that <math>B_{\mathrm{opt}}</math> contains all arcs of <math>C'</math> except one. So, suppose for a contradiction that <math>B_{\mathrm{opt}}</math> does not contain some of the arcs of <math>C'</math>, say, <math>(v_1,w_1),\ldots,(v_k,w_k)</math> with <math>k>1</math>.

Replacing the incoming arc of any <math>w_i</math> by <math>(v_i,w_i)</math> in <math>B_{\mathrm{opt}}</math> and doing nothing else, would not decrease the total weight. Since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>, such a replacement cannot result in a branching anymore. Since the indegrees do not change by that replacement, this means that adding <math>(v_i,w_i)</math> to <math>B_{\mathrm{opt}}</math> would close a cycle. In other words, there is a path <math>p_i</math> in <math>B_{\mathrm{opt}}</math> from <math>w_i</math> to <math>v_i</math>. Each path <math>p_i</math> must enter <math>C'</math> at one of the nodes <math>w_j</math> (actually at the nearest <math>w_j</math> looking backwards from <math>v_i</math> on <math>C'</math>) because, otherwise, the node where <math>p_i</math> enters <math>C'</math> had two incoming arcs in <math>B_{\mathrm{opt}}</math>: the incoming arc on <math>C'</math> and the arc over which <math>p_i</math> enters <math>C'</math>. However, this would imply that there is a cycle in the union of all paths <math>p_i</math>. This union is a subset of <math>B_{\mathrm{opt}}</math>, which yields the desired contradiction.

Now we know that <math>B_{\mathrm{opt}}</math> contains all arcs except one on all cycles of <math>G'</math>. Note that, for any node not on a cycle, the incoming branching arc may be freely chosen without any effect on the rest. So, since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>,<math>B_{\mathrm{opt}}</math> and <math>B''</math> agree on all of these choices. Further note that all cycles of <math>G'</math> are node-disjoint. In summary, we may compare <math>B_{\mathrm{opt}}</math> and <math>B''</math> on each cycle of <math>G'</math> separately.

For <math>C</math>, complete agreement between <math>B_{\mathrm{opt}}</math> and <math>B''</math> follows from the observation that the choice of incoming arcs for all nodes on <math>C</math> is optimal in <math>B''</math> due to the specific modification of the arc weights. And for all other cycles of <math>G'</math>, complete agreement follows from the induction hypothesis. In both cases, we again used the specific choice of <math>B_{\mathrm{opt}}</math> to be as close to <math>B''</math> as possible.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}((n+m)\cdot n)</math> in the worst case, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
Using [[Depth-first search|DFS]] for cycle detection, each recursive step requires <math>\mathcal{O}(n+m)</math>. In each shrink operation, the number of nodes decreases, so the recursion depth is <math>\mathcal{O}(n)</math>.

'''Remark:'''
More sophisticated implementations of this algorithm yield better asymptotic complexities.

== Remarks ==

# The unshrink operation requires that the shrink operation performs some bookkeeping: For the super-node, a cyclically ordered sequence of all nodes and arcs on <math>C</math> (or an equivalent bulk of information) must be attached to a super-node.
# Several cycles may be discovered simultaneously by one run of [[Depth-first search|DFS]]. Note that all cycles in a critical graph are node-disjoint, because no node has more than one incoming arc. Therefore, several cycles may be handled in the same recursive call, without any interference.

Branching by Edmonds

2015-01-02T11:01:57Z

BB91: /* Recursive step */ bereits in Vereinigung der p_i liegt der Zykel

== Abstract view ==

'''Algorithmic problem:''' [[Maximum branching]]

'''Definition:'''
# An arc <math>(v,w)\in A</math> is '''critical''' for <math>w\in V</math> if its weight is not smaller than the weight of any other incoming arc of <math>w</math>.
# A '''critical subgraph''' <math>G'=(V,A')</math> of <math>G</math> contains exactly one incoming arc <math>(v,w)\in A</math> for each node <math>w\in V</math> of positive indegree, where <math>(v,w)</math> is critical.

'''Type of algorithm:''' recursion

'''Invariant:''' The output of a recursive call is a maximum branching of the weighted graph that was the input for this recursive call.

== Recursion anchor ==

'''Abstract view:''' Terminate if <math>G'</math> is cycle-free.

'''Proof:'''
If <math>G'</math> is cycle-free, it is a branching. Consider some other branching <math>B</math>. We have to show that <math>B</math> does not have more total weight than <math>G'</math>.

By definition, a critical graph contains one incoming arc for each node that does have incoming arcs. Therefore, for each arc <math>a</math> of <math>B</math>, there is an arc <math>a'</math> in <math>G'</math> pointing to the same node. Due to the choice of arcs for <math>G'</math>, it is <math>w(a)\leq w(a')</math>.

== Recursive step ==
[[File:Edmonds max branching ani 10000.gif|thumb|350px|''animated gif:'' Branching by Edmonds]]
'''Abstract view:'''
# Compute a critical subgraph <math>G'=(V,A')</math> for the input graph <math>G</math>.
# Identify some cycle <math>C</math> in <math>G'</math>.
# Let <math>W</math> denote the minimum weight of all arcs on <math>C</math>.
# For every arc <math>(v,w)\in A</math> pointing from some node <math>v</math> outside <math>C</math> to some node <math>w</math> on <math>C</math>:
##Decrease the weight of <math>(v,w)</math> by <math>w(v',w)-W\geq 0</math>, where <math>(v',w)</math> is the incoming arc of <math>w</math> on <math>C</math>.
## If the new weight of <math>(v,w)</math> is not positive, remove <math>(v,w)</math> from <math>G</math>.
# Shrink <math>C</math> into one new super-node, where every arc pointing to (resp., from) some node on <math>C</math> now points to (from) that super-node.
# Call the algorithm recursively for the modified weighted graph after shrinking, giving branching <math>B</math>.
# Unshrink the graph.
# Add all arcs of <math>C</math> to <math>B</math> giving <math>B'</math>.
# If <math>B'</math> contains an arc <math>(v,w)</math> such that <math>v</math> is outside <math>C</math> and <math>w</math> is on <math>C</math>: remove the incoming arc of <math>w</math> on <math>C</math> from <math>B</math>; otherwise, remove one arc with weight <math>W</math> on <math>C</math>. Let <math>B''</math> be the result in both cases.
# Return <math>B''</math>.

'''Proof:'''
Obviously, <math>B''</math> is a branching, so we have to prove that it has maximum weight among all branchings in <math>G</math>. Let <math>B_{\mathrm{opt}}</math> be a maximum branching in <math>G</math> such that, among all maximum branchings in <math>G</math>, <math>B_{\mathrm{opt}}</math> shares as many arcs as possible with <math>B''</math>.

Let <math>C'</math> be a cycle of <math>G'</math> (the case <math>C'=C</math> not excluded). First we show that <math>B_{\mathrm{opt}}</math> contains all arcs of <math>C'</math> except one. So, suppose for a contradiction that <math>B_{\mathrm{opt}}</math> does not contain some of the arcs of <math>C'</math>, say, <math>(v_1,w_1),\ldots,(v_k,w_k)</math> with <math>k>1</math>.

Replacing the incoming arc of any <math>w_i</math> by <math>(v_i,w_i)</math> in <math>B_{\mathrm{opt}}</math> and doing nothing else, would not decrease the total weight. Since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>, such a replacement cannot result in a branching anymore. Since the indegrees do not change by that replacement, this means that adding <math>(v_i,w_i)</math> to <math>B_{\mathrm{opt}}</math> would close a cycle. In other words, there is a path <math>p_i</math> in <math>B_{\mathrm{opt}}</math> from <math>w_i</math> to <math>v_i</math>. Each path <math>p_i</math> must enter <math>C'</math> at one of the nodes <math>w_j</math> because, otherwise, the node where <math>p_i</math> enters <math>C'</math> had two incoming arcs in <math>B_{\mathrm{opt}}</math>: the incoming arc on <math>C'</math> and the arc over which <math>p_i</math> enters <math>C'</math>. However, this would imply that there is a cycle in the union of all paths <math>p_i</math>. This union is a subset of <math>B_{\mathrm{opt}}</math>, which yields the desired contradiction.

Now we know that <math>B_{\mathrm{opt}}</math> contains all arcs except one on all cycles of <math>G'</math>. Note that, for any node not on a cycle, the incoming branching arc may be freely chosen without any effect on the rest. So, since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>,<math>B_{\mathrm{opt}}</math> and <math>B''</math> agree on all of these choices. Further note that all cycles of <math>G'</math> are node-disjoint. In summary, we may compare <math>B_{\mathrm{opt}}</math> and <math>B''</math> on each cycle of <math>G'</math> separately.

For <math>C</math>, complete agreement between <math>B_{\mathrm{opt}}</math> and <math>B''</math> follows from the observation that the choice of incoming arcs for all nodes on <math>C</math> is optimal in <math>B''</math> due to the specific modification of the arc weights. And for all other cycles of <math>G'</math>, complete agreement follows from the induction hypothesis. In both cases, we again used the specific choice of <math>B_{\mathrm{opt}}</math> to be as close to <math>B''</math> as possible.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}((n+m)\cdot n)</math> in the worst case, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
Using [[Depth-first search|DFS]] for cycle detection, each recursive step requires <math>\mathcal{O}(n+m)</math>. In each shrink operation, the number of nodes decreases, so the recursion depth is <math>\mathcal{O}(n)</math>.

'''Remark:'''
More sophisticated implementations of this algorithm yield better asymptotic complexities.

== Remarks ==

# The unshrink operation requires that the shrink operation performs some bookkeeping: For the super-node, a cyclically ordered sequence of all nodes and arcs on <math>C</math> (or an equivalent bulk of information) must be attached to a super-node.
# Several cycles may be discovered simultaneously by one run of [[Depth-first search|DFS]]. Note that all cycles in a critical graph are node-disjoint, because no node has more than one incoming arc. Therefore, several cycles may be handled in the same recursive call, without any interference.

Branching by Edmonds

2015-01-02T10:44:28Z

BB91: /* Recursive step */

== Abstract view ==

'''Algorithmic problem:''' [[Maximum branching]]

'''Definition:'''
# An arc <math>(v,w)\in A</math> is '''critical''' for <math>w\in V</math> if its weight is not smaller than the weight of any other incoming arc of <math>w</math>.
# A '''critical subgraph''' <math>G'=(V,A')</math> of <math>G</math> contains exactly one incoming arc <math>(v,w)\in A</math> for each node <math>w\in V</math> of positive indegree, where <math>(v,w)</math> is critical.

'''Type of algorithm:''' recursion

'''Invariant:''' The output of a recursive call is a maximum branching of the weighted graph that was the input for this recursive call.

== Recursion anchor ==

'''Abstract view:''' Terminate if <math>G'</math> is cycle-free.

'''Proof:'''
If <math>G'</math> is cycle-free, it is a branching. Consider some other branching <math>B</math>. We have to show that <math>B</math> does not have more total weight than <math>G'</math>.

By definition, a critical graph contains one incoming arc for each node that does have incoming arcs. Therefore, for each arc <math>a</math> of <math>B</math>, there is an arc <math>a'</math> in <math>G'</math> pointing to the same node. Due to the choice of arcs for <math>G'</math>, it is <math>w(a)\leq w(a')</math>.

== Recursive step ==
[[File:Edmonds max branching ani 10000.gif|thumb|350px|''animated gif:'' Branching by Edmonds]]
'''Abstract view:'''
# Compute a critical subgraph <math>G'=(V,A')</math> for the input graph <math>G</math>.
# Identify some cycle <math>C</math> in <math>G'</math>.
# Let <math>W</math> denote the minimum weight of all arcs on <math>C</math>.
# For every arc <math>(v,w)\in A</math> pointing from some node <math>v</math> outside <math>C</math> to some node <math>w</math> on <math>C</math>:
##Decrease the weight of <math>(v,w)</math> by <math>w(v',w)-W\geq 0</math>, where <math>(v',w)</math> is the incoming arc of <math>w</math> on <math>C</math>.
## If the new weight of <math>(v,w)</math> is not positive, remove <math>(v,w)</math> from <math>G</math>.
# Shrink <math>C</math> into one new super-node, where every arc pointing to (resp., from) some node on <math>C</math> now points to (from) that super-node.
# Call the algorithm recursively for the modified weighted graph after shrinking, giving branching <math>B</math>.
# Unshrink the graph.
# Add all arcs of <math>C</math> to <math>B</math> giving <math>B'</math>.
# If <math>B'</math> contains an arc <math>(v,w)</math> such that <math>v</math> is outside <math>C</math> and <math>w</math> is on <math>C</math>: remove the incoming arc of <math>w</math> on <math>C</math> from <math>B</math>; otherwise, remove one arc with weight <math>W</math> on <math>C</math>. Let <math>B''</math> be the result in both cases.
# Return <math>B''</math>.

'''Proof:'''
Obviously, <math>B''</math> is a branching, so we have to prove that it has maximum weight among all branchings in <math>G</math>. Let <math>B_{\mathrm{opt}}</math> be a maximum branching in <math>G</math> such that, among all maximum branchings in <math>G</math>, <math>B_{\mathrm{opt}}</math> shares as many arcs as possible with <math>B''</math>.

Let <math>C'</math> be a cycle of <math>G'</math> (the case <math>C'=C</math> not excluded). First we show that <math>B_{\mathrm{opt}}</math> contains all arcs of <math>C'</math> except one. So, suppose for a contradiction that <math>B_{\mathrm{opt}}</math> does not contain some of the arcs of <math>C'</math>, say, <math>(v_1,w_1),\ldots,(v_k,w_k)</math> with <math>k>1</math>.

Replacing the incoming arc of any <math>w_i</math> by <math>(v_i,w_i)</math> in <math>B_{\mathrm{opt}}</math> and doing nothing else, would not decrease the total weight. Since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>, such a replacement cannot result in a branching anymore. Since the indegrees do not change by that replacement, this means that adding <math>(v_i,w_i)</math> to <math>B_{\mathrm{opt}}</math> would close a cycle. In other words, there is a path <math>p_i</math> in <math>B_{\mathrm{opt}}</math> from <math>w_i</math> to <math>v_i</math>. Each path <math>p_i</math> must enter <math>C'</math> at one of the nodes <math>w_j</math> because, otherwise, the node where <math>p_i</math> enters <math>C'</math> had two incoming arcs in <math>B_{\mathrm{opt}}</math>: the incoming arc on <math>C'</math> and the arc over which <math>p_i</math> enters <math>C'</math>. However, this would imply that there is a cycle in the union of all paths <math>p_i</math> plus all arcs of <math>C'</math> '''not''' in <math>\{(v_1,w_1),\ldots,(v_k,w_k)\}</math>. This union is a subset of <math>B_{\mathrm{opt}}</math>, which yields the desired contradiction.

Now we know that <math>B_{\mathrm{opt}}</math> contains all arcs except one on all cycles of <math>G'</math>. Note that, for any node not on a cycle, the incoming branching arc may be freely chosen without any effect on the rest. So, since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>,<math>B_{\mathrm{opt}}</math> and <math>B''</math> agree on all of these choices. Further note that all cycles of <math>G'</math> are node-disjoint. In summary, we may compare <math>B_{\mathrm{opt}}</math> and <math>B''</math> on each cycle of <math>G'</math> separately.

For <math>C</math>, complete agreement between <math>B_{\mathrm{opt}}</math> and <math>B''</math> follows from the observation that the choice of incoming arcs for all nodes on <math>C</math> is optimal in <math>B''</math> due to the specific modification of the arc weights. And for all other cycles of <math>G'</math>, complete agreement follows from the induction hypothesis. In both cases, we again used the specific choice of <math>B_{\mathrm{opt}}</math> to be as close to <math>B''</math> as possible.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}((n+m)\cdot n)</math> in the worst case, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
Using [[Depth-first search|DFS]] for cycle detection, each recursive step requires <math>\mathcal{O}(n+m)</math>. In each shrink operation, the number of nodes decreases, so the recursion depth is <math>\mathcal{O}(n)</math>.

'''Remark:'''
More sophisticated implementations of this algorithm yield better asymptotic complexities.

== Remarks ==

# The unshrink operation requires that the shrink operation performs some bookkeeping: For the super-node, a cyclically ordered sequence of all nodes and arcs on <math>C</math> (or an equivalent bulk of information) must be attached to a super-node.
# Several cycles may be discovered simultaneously by one run of [[Depth-first search|DFS]]. Note that all cycles in a critical graph are node-disjoint, because no node has more than one incoming arc. Therefore, several cycles may be handled in the same recursive call, without any interference.

Branching by Edmonds

2015-01-02T10:41:49Z

BB91: /* Recursive step */

== Abstract view ==

'''Algorithmic problem:''' [[Maximum branching]]

'''Definition:'''
# An arc <math>(v,w)\in A</math> is '''critical''' for <math>w\in V</math> if its weight is not smaller than the weight of any other incoming arc of <math>w</math>.
# A '''critical subgraph''' <math>G'=(V,A')</math> of <math>G</math> contains exactly one incoming arc <math>(v,w)\in A</math> for each node <math>w\in V</math> of positive indegree, where <math>(v,w)</math> is critical.

'''Type of algorithm:''' recursion

'''Invariant:''' The output of a recursive call is a maximum branching of the weighted graph that was the input for this recursive call.

== Recursion anchor ==

'''Abstract view:''' Terminate if <math>G'</math> is cycle-free.

'''Proof:'''
If <math>G'</math> is cycle-free, it is a branching. Consider some other branching <math>B</math>. We have to show that <math>B</math> does not have more total weight than <math>G'</math>.

By definition, a critical graph contains one incoming arc for each node that does have incoming arcs. Therefore, for each arc <math>a</math> of <math>B</math>, there is an arc <math>a'</math> in <math>G'</math> pointing to the same node. Due to the choice of arcs for <math>G'</math>, it is <math>w(a)\leq w(a')</math>.

== Recursive step ==
[[File:Edmonds max branching ani 10000.gif|thumb|350px|''animated gif:'' Branching by Edmonds]]
'''Abstract view:'''
# Compute a critical subgraph <math>G'=(V,A')</math> for the input graph <math>G</math>.
# Identify some cycle <math>C</math> in <math>G'</math>.
# Let <math>W</math> denote the minimum weight of all arcs on <math>C</math>.
# For every arc <math>(v,w)\in A</math> pointing from some node <math>v</math> outside <math>C</math> to some node <math>w</math> on <math>C</math>:
##Decrease the weight of <math>(v,w)</math> by <math>w(v',w)-W\geq 0</math>, where <math>(v',w)</math> is the incoming arc of <math>w</math> on <math>C</math>.
## If the new weight of <math>(v,w)</math> is not positive, remove <math>(v,w)</math> from <math>G</math>.
# Shrink <math>C</math> into one new super-node, where every arc pointing to (resp., from) some node on <math>C</math> now points to (from) that super-node.
# Call the algorithm recursively for the modified weighted graph after shrinking, giving branching <math>B</math>.
# Unshrink the graph.
# Add all arcs of <math>C</math> to <math>B</math> giving <math>B'</math>.
# If <math>B'</math> contains an arc <math>(v,w)</math> such that <math>v</math> is outside <math>C</math> and <math>w</math> is on <math>C</math>: remove the incoming arc of <math>w</math> on <math>C</math> from <math>B</math>; otherwise, remove one arc with weight <math>W</math> on <math>C</math>. Let <math>B''</math> be the result in both cases.
# Return <math>B''</math>.

'''Proof:'''
Obviously, <math>B''</math> is a branching, so we have to prove that it has maximum weight among all branchings in <math>G</math>. Let <math>B_{\mathrm{opt}}</math> be a maximum branching in <math>G</math> such that, among all maximum branchings in <math>G</math>, <math>B_{\mathrm{opt}}</math> shares as many arcs as possible with <math>B''</math>.

Let <math>C'</math> be a cycle of <math>G'</math> (the case <math>C'=C</math> not excluded). First we show that <math>B_{\mathrm{opt}}</math> contains all arcs of <math>C'</math> except one. So, suppose for a contradiction that <math>B_{\mathrm{opt}}</math> does not contain some of the arcs of <math>C'</math>, say, <math>(v_1,w_1),\ldots,(v_k,w_k)</math> with <math>k>1</math>.

Replacing the incoming arc of any <math>w_i</math> by <math>(v_i,w_i)</math> in <math>B_{\mathrm{opt}}</math> and doing nothing else, would not decrease the total weight. Since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>, such a replacement cannot result in a branching anymore. Since the indegrees do not change by that replacement, this means that adding <math>(v_i,w_i)</math> to <math>B_{\mathrm{opt}}</math> would close a cycle. In other words, there is a path <math>p_i</math> in <math>B_{\mathrm{opt}}</math> from <math>w_i</math> to <math>v_i</math>. Each path <math>p_i</math> must enter <math>C'</math> at one of the nodes <math>w_j</math> because, otherwise, the node where <math>p_i</math> enters <math>C'</math> had two incoming arcs in <math>B_{\mathrm{opt}}</math>: the incoming arc on <math>C'</math> and the arc over which <math>p_i</math> enters <math>C'</math>. However, this would imply that there is a cycle in the union of all paths <math>p_i</math> plus all arcs of <math>C'</math> '''not''' in <math>\{(v_1,w_1),\ldots,(v_k,w_k)\}</math>. This union is a subset of <math>B_{\mathrm{opt}}</math>, which yields the desired contradiction.

Now we know that <math>B_{\mathrm{opt}}</math> contains all arcs except one on all cycles of <math>G'</math>. Note that, for any node not on a cycle, the incoming branching arc may be freely chosen without any effect on the rest. So, since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>,<math>B_{\mathrm{opt}}</math> and <math>B''</math> agree on all of these choices. Further note that all cycles of <math>G'</math> are node-disjoint. In summary, we may compare <math>B_{\mathrm{opt}}</math> and <math>B'</math> on each cycle of <math>G'</math> separately.

For <math>C</math>, complete agreement between <math>B_{\mathrm{opt}}</math> and <math>B''</math> follows from the observation that the choice of incoming arcs for all nodes on <math>C</math> is optimal in <math>B''</math> due to the specific modification of the arc weights. And for all other cycles of <math>G'</math>, complete agreement follows from the induction hypothesis. In both cases, we again used the specific choice of <math>B_{\mathrm{opt}}</math> to be as close to <math>B''</math> as possible.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}((n+m)\cdot n)</math> in the worst case, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
Using [[Depth-first search|DFS]] for cycle detection, each recursive step requires <math>\mathcal{O}(n+m)</math>. In each shrink operation, the number of nodes decreases, so the recursion depth is <math>\mathcal{O}(n)</math>.

'''Remark:'''
More sophisticated implementations of this algorithm yield better asymptotic complexities.

== Remarks ==

# The unshrink operation requires that the shrink operation performs some bookkeeping: For the super-node, a cyclically ordered sequence of all nodes and arcs on <math>C</math> (or an equivalent bulk of information) must be attached to a super-node.
# Several cycles may be discovered simultaneously by one run of [[Depth-first search|DFS]]. Note that all cycles in a critical graph are node-disjoint, because no node has more than one incoming arc. Therefore, several cycles may be handled in the same recursive call, without any interference.

Branching by Edmonds

2015-01-02T10:21:00Z

BB91: /* Recursive step */

== Abstract view ==

'''Algorithmic problem:''' [[Maximum branching]]

'''Definition:'''
# An arc <math>(v,w)\in A</math> is '''critical''' for <math>w\in V</math> if its weight is not smaller than the weight of any other incoming arc of <math>w</math>.
# A '''critical subgraph''' <math>G'=(V,A')</math> of <math>G</math> contains exactly one incoming arc <math>(v,w)\in A</math> for each node <math>w\in V</math> of positive indegree, where <math>(v,w)</math> is critical.

'''Type of algorithm:''' recursion

'''Invariant:''' The output of a recursive call is a maximum branching of the weighted graph that was the input for this recursive call.

== Recursion anchor ==

'''Abstract view:''' Terminate if <math>G'</math> is cycle-free.

'''Proof:'''
If <math>G'</math> is cycle-free, it is a branching. Consider some other branching <math>B</math>. We have to show that <math>B</math> does not have more total weight than <math>G'</math>.

By definition, a critical graph contains one incoming arc for each node that does have incoming arcs. Therefore, for each arc <math>a</math> of <math>B</math>, there is an arc <math>a'</math> in <math>G'</math> pointing to the same node. Due to the choice of arcs for <math>G'</math>, it is <math>w(a)\leq w(a')</math>.

== Recursive step ==
[[File:Edmonds max branching ani 10000.gif|thumb|350px|''animated gif:'' Branching by Edmonds]]
'''Abstract view:'''
# Compute a critical subgraph <math>G'=(V,A')</math> for the input graph <math>G</math>.
# Identify some cycle <math>C</math> in <math>G'</math>.
# Let <math>W</math> denote the minimum weight of all arcs on <math>C</math>.
# For every arc <math>(v,w)\in A</math> pointing from some node <math>v</math> outside <math>C</math> to some node <math>w</math> on <math>C</math>:
##Decrease the weight of <math>(v,w)</math> by <math>w(v',w)-W\geq 0</math>, where <math>(v',w)</math> is the incoming arc of <math>w</math> on <math>C</math>.
## If the new weight of <math>(v,w)</math> is not positive, remove <math>(v,w)</math> from <math>G</math>.
# Shrink <math>C</math> into one new super-node, where every arc pointing to (resp., from) some node on <math>C</math> now points to (from) that super-node.
# Call the algorithm recursively for the modified weighted graph after shrinking, giving branching <math>B</math>.
# Unshrink the graph.
# Add all arcs of <math>C</math> to <math>B</math> giving <math>B'</math>.
# If <math>B'</math> contains an arc <math>(v,w)</math> such that <math>v</math> is outside <math>C</math> and <math>w</math> is on <math>C</math>: remove the incoming arc of <math>w</math> on <math>C</math> from <math>B</math>; otherwise, remove one arc with weight <math>W</math> on <math>C</math>. Let <math>B''</math> be the result in both cases.
# Return <math>B''</math>.

'''Proof:'''
Obviously, <math>B''</math> is a branching, so we have to prove that it has maximum weight among all branchings in <math>G</math>. Let <math>B_{\mathrm{opt}}</math> be a maximum branching in <math>G</math> such that, among all maximum branchings in <math>G</math>, <math>B_{\mathrm{opt}}</math> shares as many arcs as possible with <math>B''</math>.

Let <math>C'</math> be a cycle of <math>G'</math> (the case <math>C'=C</math> not excluded). First we show that <math>B_{\mathrm{opt}}</math> contains all arcs of <math>C'</math> except one. So, suppose for a contradiction that <math>B_{\mathrm{opt}}</math> does not contain some of the arcs of <math>C'</math>, say, <math>(v_1,w_1),\ldots,(v_k,w_k)</math> with <math>k>1</math>.

Replacing the incoming arc of any <math>w_i</math> by <math>(v_i,w_i)</math> in <math>B_{\mathrm{opt}}</math> and doing nothing else, would not decrease the total weight. Since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>, such a replacement cannot result in a branching anymore. Since the indegrees do not change by that replacement, this means that adding <math>(v_i,w_i)</math> to <math>B_{\mathrm{opt}}</math> would close a cycle. In other words, there is a path <math>p_i</math> in <math>B_{\mathrm{opt}}</math> from <math>w_i</math> to <math>v_i</math>. Each path <math>p_i</math> must enter <math>C'</math> at one of the nodes <math>w_j</math> because, otherwise, the node where <math>p_i</math> enters <math>C'</math> had two incoming arcs in <math>B_{\mathrm{opt}}</math>: the incoming arc on <math>C'</math> and the arc over which <math>p_i</math> enters <math>C'</math>. However, this would imply that there is a cycle in the union of all paths <math>p_i</math> plus all arcs of <math>C''</math> '''not''' in <math>\{(v_1,w_1),\ldots,(v_k,w_k)\}</math>. This union is a subset of <math>B_{\mathrm{opt}}</math>, which yields the desired contradiction.

Now we know that <math>B_{\mathrm{opt}}</math> contains all arcs except one on all cycles of <math>G'</math>. Note that, for any node not on a cycle, the incoming branching arc may be freely chosen without any effect on the rest. So, since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>,<math>B_{\mathrm{opt}}</math> and <math>B''</math> agree on all of these choices. Further note that all cycles of <math>G'</math> are node-disjoint. In summary, we may compare <math>B_{\mathrm{opt}}</math> and <math>B'</math> on each cycle of <math>G'</math> separately.

For <math>C</math>, complete agreement between <math>B_{\mathrm{opt}}</math> and <math>B''</math> follows from the observation that the choice of incoming arcs for all nodes on <math>C</math> is optimal in <math>B''</math> due to the specific modification of the arc weights. And for all other cycles of <math>G'</math>, complete agreement follows from the induction hypothesis. In both cases, we again used the specific choice of <math>B_{\mathrm{opt}}</math> to be as close to <math>B''</math> as possible.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}((n+m)\cdot n)</math> in the worst case, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
Using [[Depth-first search|DFS]] for cycle detection, each recursive step requires <math>\mathcal{O}(n+m)</math>. In each shrink operation, the number of nodes decreases, so the recursion depth is <math>\mathcal{O}(n)</math>.

'''Remark:'''
More sophisticated implementations of this algorithm yield better asymptotic complexities.

== Remarks ==

# The unshrink operation requires that the shrink operation performs some bookkeeping: For the super-node, a cyclically ordered sequence of all nodes and arcs on <math>C</math> (or an equivalent bulk of information) must be attached to a super-node.
# Several cycles may be discovered simultaneously by one run of [[Depth-first search|DFS]]. Note that all cycles in a critical graph are node-disjoint, because no node has more than one incoming arc. Therefore, several cycles may be handled in the same recursive call, without any interference.

Branching by Edmonds

2015-01-02T10:12:23Z

BB91: /* Recursive step */ B -> B'

== Abstract view ==

'''Algorithmic problem:''' [[Maximum branching]]

'''Definition:'''
# An arc <math>(v,w)\in A</math> is '''critical''' for <math>w\in V</math> if its weight is not smaller than the weight of any other incoming arc of <math>w</math>.
# A '''critical subgraph''' <math>G'=(V,A')</math> of <math>G</math> contains exactly one incoming arc <math>(v,w)\in A</math> for each node <math>w\in V</math> of positive indegree, where <math>(v,w)</math> is critical.

'''Type of algorithm:''' recursion

'''Invariant:''' The output of a recursive call is a maximum branching of the weighted graph that was the input for this recursive call.

== Recursion anchor ==

'''Abstract view:''' Terminate if <math>G'</math> is cycle-free.

'''Proof:'''
If <math>G'</math> is cycle-free, it is a branching. Consider some other branching <math>B</math>. We have to show that <math>B</math> does not have more total weight than <math>G'</math>.

By definition, a critical graph contains one incoming arc for each node that does have incoming arcs. Therefore, for each arc <math>a</math> of <math>B</math>, there is an arc <math>a'</math> in <math>G'</math> pointing to the same node. Due to the choice of arcs for <math>G'</math>, it is <math>w(a)\leq w(a')</math>.

== Recursive step ==
[[File:Edmonds max branching ani 10000.gif|thumb|350px|''animated gif:'' Branching by Edmonds]]
'''Abstract view:'''
# Compute a critical subgraph <math>G'=(V,A')</math> for the input graph <math>G</math>.
# Identify some cycle <math>C</math> in <math>G'</math>.
# Let <math>W</math> denote the minimum weight of all arcs on <math>C</math>.
# For every arc <math>(v,w)\in A</math> pointing from some node <math>v</math> outside <math>C</math> to some node <math>w</math> on <math>C</math>:
##Decrease the weight of <math>(v,w)</math> by <math>w(v',w)-W\geq 0</math>, where <math>(v',w)</math> is the incoming arc of <math>w</math> on <math>C</math>.
## If the new weight of <math>(v,w)</math> is not positive, remove <math>(v,w)</math> from <math>G</math>.
# Shrink <math>C</math> into one new super-node, where every arc pointing to (resp., from) some node on <math>C</math> now points to (from) that super-node.
# Call the algorithm recursively for the modified weighted graph after shrinking, giving branching <math>B</math>.
# Unshrink the graph.
# Add all arcs of <math>C</math> to <math>B</math> giving <math>B'</math>.
# If <math>B'</math> contains an arc <math>(v,w)</math> such that <math>v</math> is outside <math>C</math> and <math>w</math> is on <math>C</math>: remove the incoming arc of <math>w</math> on <math>C</math> from <math>B</math>; otherwise, remove one arc with weight <math>W</math> on <math>C</math>. Let <math>B''</math> be the result in both cases.
# Return <math>B''</math>.

'''Proof:'''
Obviously, <math>B''</math> is a branching, so we have to prove that it has maximum weight among all branchings in <math>G</math>. Let <math>B_{\mathrm{opt}}</math> be a maximum branching in <math>G</math> such that, among all maximum branchings in <math>G</math>, <math>B_{\mathrm{opt}}</math> shares as many arcs as possible with <math>B''</math>.

Let <math>C'</math> be a cycle of <math>G'</math> (the case <math>C'=C</math> not excluded). First we show that <math>B_{\mathrm{opt}}</math> contains all arcs of <math>C'</math> except one. So, suppose for a contradiction that <math>B_{\mathrm{opt}}</math> does not contain some of the arcs of <math>C'</math>, say, <math>(v_1,w_1),\ldots,(v_k,w_k)</math> with <math>k>1</math>.

Replacing the incoming arc of any <math>w_i</math> by <math>(v_i,w_i)</math> in <math>B_{\mathrm{opt}}</math> and doing nothing else, would not decrease the total weight. Since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>, such a replacement cannot result in a branching anymore. Since the indegrees do not change by that replacement, this means that adding <math>(v_i,w_i)</math> to <math>B_{\mathrm{opt}}</math> would close a cycle. In other words, there is a path <math>p_i</math> in <math>B_{\mathrm{opt}}</math> from <math>w_i</math> to <math>v_i</math>. Each path <math>p_i</math> must enter <math>C</math> at one of the nodes <math>w_j</math> because, otherwise, the node where <math>p_i</math> enters <math>C'</math> had two incoming arcs in <math>B_{\mathrm{opt}}</math>: the incoming arc on <math>C'</math> and the arc over which <math>p_i</math> enters <math>C'</math>. However, this would imply that there is a cycle in the union of all paths <math>p_i</math> plus all arcs of <math>C''</math> '''not''' in <math>\{(v_1,w_1),\ldots,(v_k,w_k)\}</math>. This union is a subset of <math>B_{\mathrm{opt}}</math>, which yields the desired contradiction.

Now we know that <math>B_{\mathrm{opt}}</math> contains all arcs except one on all cycles of <math>G'</math>. Note that, for any node not on a cycle, the incoming branching arc may be freely chosen without any effect on the rest. So, since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>,<math>B_{\mathrm{opt}}</math> and <math>B''</math> agree on all of these choices. Further note that all cycles of <math>G'</math> are node-disjoint. In summary, we may compare <math>B_{\mathrm{opt}}</math> and <math>B'</math> on each cycle of <math>G'</math> separately.

For <math>C</math>, complete agreement between <math>B_{\mathrm{opt}}</math> and <math>B''</math> follows from the observation that the choice of incoming arcs for all nodes on <math>C</math> is optimal in <math>B''</math> due to the specific modification of the arc weights. And for all other cycles of <math>G'</math>, complete agreement follows from the induction hypothesis. In both cases, we again used the specific choice of <math>B_{\mathrm{opt}}</math> to be as close to <math>B''</math> as possible.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}((n+m)\cdot n)</math> in the worst case, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
Using [[Depth-first search|DFS]] for cycle detection, each recursive step requires <math>\mathcal{O}(n+m)</math>. In each shrink operation, the number of nodes decreases, so the recursion depth is <math>\mathcal{O}(n)</math>.

'''Remark:'''
More sophisticated implementations of this algorithm yield better asymptotic complexities.

== Remarks ==

# The unshrink operation requires that the shrink operation performs some bookkeeping: For the super-node, a cyclically ordered sequence of all nodes and arcs on <math>C</math> (or an equivalent bulk of information) must be attached to a super-node.
# Several cycles may be discovered simultaneously by one run of [[Depth-first search|DFS]]. Note that all cycles in a critical graph are node-disjoint, because no node has more than one incoming arc. Therefore, several cycles may be handled in the same recursive call, without any interference.

Classical eulerian cycle algorithm

2015-01-02T08:10:10Z

BB91: /* Correctness */ kleine Einfügung zum Verständnis; Korrektur tail -> beginning node im Beweis

[[File:Nikolaus.png|400px|thumb|right|Another may well know example with 44 solutions]]

== General information ==

'''Algorithmic problem:''' [[Eulerian cycle]]

''' Type of algorithm:''' recursion with an arbitrarily chosen start node <math>s\in V</math> as an additional input. Before the proper recursive procedure is invoked, the output sequence <math>S</math> is initialized so as to contain the start node <math>s</math> and nothing else.

== Recursion anchor ==

No edges/arcs leave the start node <math>s</math> of that recursive call.

== Recursive step ==

For notational convenience, both undirected edges and directed arcs are denoted by parentheses in the following (in the direction in which they are looked at).

# Let <math>p</math> be a (dynamically growing) path, represented in <math>p</math> as an alternating sequence of nodes and edges/arcs.
# Initialize <math>p</math> so as to contain <math>s</math> and nothing else.
# Set <math>x:=s</math>.
# While there are edges/arcs leaving <math>x</math>:
## Choose one such arc <math>(x,y)</math>.
## Remove <math>(x,y)</math> from the graph.
## Append <math>(x,y)</math> and then <math>y</math> to <math>p</math>.
## Set <math>x:=y</math>.
# If <math>x\neq s</math>, terminate the algorithm with the statement that no eulerian cycle exists.
# Otherwise: For each node <math>v</math> on <math>p</math> that still has leaving edges/arcs,:
## Call the procedure recursively with <math>v</math> as the start node, giving path <math>p'</math>.
## Replace <math>v</math> in <math>p</math> by <math>p'</math>.

== Correctness ==

Since each edge/arc is removed immediately when it is processed, no edge/arc occurs twice in the output. Obviously, steps 4.3 and 6.2 ensure that the order in which the nodes and edges/arcs occur in the output yields a correct path. Obviously, whenever step 4 is finished, it is <math>x=s</math> and the remaining graph is eulerian, if the original graph was eulerian. Consequently, the statement that no eulerian cycle exists is only delivered if the graph is indeed non-eulerian. Moreover, the graph handed over to a recursive call is Eulerian, if the original graph was Eulerian.

Suppose for a contradiction that some edge/arc <math>e/a</math> is '''not''' in the output. Since the graph is (strongly) connected, there is a path <math>q</math> from the start node of the algorithm to the beginning node of <math>a</math> (an arbitrary endnode of <math>e</math> in the undirected case). Let <math>v</math> be the last node on <math>q</math> processed by any recursive call. Then the subsequent edge/arc on <math>q</math> has not been processed, which contradicts the procedure.

== Complexity ==

'''Statement:'''
Both for directed and undirected graphs, the asymtptotic complexity is linear in the number of edges/ars.

'''Proof:'''
We assume that all data structures are implemented in the obvious appropriate way. First note that steps 1, 2, 3, and 5 take constant time each. So the total complexity of these steps is linear in the number of recursive calls, which is linear in the number of edges/arcs in turn. The total number of iterations of steps 4 and 6, respectively, taken over all recursive calls, is linear in the number of edges/arcs as well.

'''Remarks:'''
# Since the graph is (strongly) connected, the number of nodes is asymptotically dominated by the number of edges/arcs and, therefore, irrelevant here.
# Of course, the edges/arcs need not be removed permanently. However, when an edge/arc is processed, it must be hidden from the algorithm up to its termination to achieve the linear bound on the complexity. A boolean edge/arc label to indicate whether this edge/arc has already been processed, does not suffice.

== Example ==
<gallery>
File:Eulerpath_1.png|Step 1
File:Eulerpath_2.png|Step 2
File:Eulerpath_3.png|Step 3
File:Eulerpath_4.png|Step 4
File:Eulerpath_5.png|Step 5
File:Eulerpath_6.png|Step 6
File:Eulerpath_7.png|Step 7
File:Eulerpath_8.png|Step 8
File:Eulerpath_9.png|Step 9
File:Eulerpath_10.png|Step 10
File:Eulerpath_11.png|Final Step
</gallery>

Hopcroft-Tarjan

2015-01-01T17:43:47Z

BB91: /* Step 2 */ Behandlung von besonderen Artikulationsknoten

[[Category:Graph Algorithms]]
== Abstract view ==

'''Algorithmic problem:'''
[[Biconnected components]]

'''Type of algorithm:'''
two steps.

== Step 1 ==

'''Abstract view:'''
# 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 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 '''depth''' of <math>v</math> in the 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 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.
# ''Lowpoint'':
## Whenever a node <math>v\in V</math> is seen for the first time, its lowpoint is set identical 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>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 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>.

'''Remarks:'''
# 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 ==

'''Definition:'''
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:'''
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 ==

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

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.

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 ==

'''Statement:'''
The asymptotic complexity is linear.

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

Hopcroft-Tarjan

2015-01-01T17:31:41Z

BB91: /* Step 2 */ Behandlung von besonderen Artikulationsknoten

[[Category:Graph Algorithms]]
== Abstract view ==

'''Algorithmic problem:'''
[[Biconnected components]]

'''Type of algorithm:'''
two steps.

== Step 1 ==

'''Abstract view:'''
# 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 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 '''depth''' of <math>v</math> in the 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 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.
# ''Lowpoint'':
## Whenever a node <math>v\in V</math> is seen for the first time, its lowpoint is set identical 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>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 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>.

'''Remarks:'''
# 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 ==

'''Definition:'''
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:'''
A repeated application of [[Depth-first search|DFS]], 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 ==

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

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.

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 ==

'''Statement:'''
The asymptotic complexity is linear.

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

Hopcroft-Tarjan

2015-01-01T16:36:25Z

BB91: /* Step 1 */ Berichtigung der Definition von "lowpoint"

[[Category:Graph Algorithms]]
== Abstract view ==

'''Algorithmic problem:'''
[[Biconnected components]]

'''Type of algorithm:'''
two steps.

== Step 1 ==

'''Abstract view:'''
# 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 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 '''depth''' of <math>v</math> in the 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 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.
# ''Lowpoint'':
## Whenever a node <math>v\in V</math> is seen for the first time, its lowpoint is set identical 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>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 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>.

'''Remarks:'''
# 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 ==

'''Definition:'''
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:'''
A repeated application of [[Depth-first search|DFS]], 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 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.

== Correctness ==

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

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.

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 ==

'''Statement:'''
The asymptotic complexity is linear.

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

Kosaraju

2014-12-30T14:40:34Z

BB91: /* Correctness */

[[Category:Graph Algorithms]]

== General information ==

'''Algorithmic problem:''' [[Strongly connected components]]

'''Type of algorithm:''' loop

== Abstract View ==

# Apply a [[repeated depth-first search]] to <math>G</math>, the output order is parenthetical.
# Invert the output order of the nodes.
# Let <math>G^t=(V,A^t)</math> be the [[Basic graph definitions#Transpose of a graph|transpose]] of <math>G=(V,A)</math>.
# Apply a [[repeated depth-first search]] to <math>G^t</math> with a modification: The order in which the nodes are considered as potential start nodes is the inverted parenthetical order from step 2.
# The node sets from the individual applications of [[Depth-first search|DFS]] inside step 4 are exactly the SCC of <math>G</math>.

== Correctness ==

First note that the transposition of all arcs does not change the SCC of a graph, so step 4 indeed processes the SCC of <math>G</math>.
[[File:CondensedGraphKosaraju.jpg|200px|thumb|right|Construction of the condensed graph (example)]]
Consider the condensed graph <math>G'</math> whose nodes are these SCC, and there is an arc from an SCC <math>C_i</math> to an SCC <math>C_j</math> in <math>G'</math> if, and only if, there is at least one arc in <math>G</math> from some node in <math>C_i</math> to some node in <math>C_j</math>. This condensed graph is acyclic because all nodes in all SCC on a cycle would be mutually reachable from each other in <math>G</math> and their union would consequently form a single larger SCC contradicting the construction of the condensed graph.

In step 1, each [[Depth-first search|DFS]] run either meets ''all'' nodes of an SCC of <math>G</math> or ''none'' of the nodes of this SCC. More specifically, all nodes in the same SCC as the start node and in all SCC reachable from that SCC, except for the SCC processed in previous [[Depth-first search|DFS]] runs.

Due to the parenthetical order of the [[Depth-first search|DFS]], if an SCC <math>C_i</math> is reachable from an SCC <math>C_j</math> in <math>G</math>, then there is at least one node of <math>C_j</math> which appears after all nodes of <math>C_i</math> in the output sequence of step 1 (because it is finished in [[Depth-first search|DFS]] after the nodes of <math>C_i</math>). Equivalently, there is at least one node of <math>C_j</math> which appears before all nodes of <math>C_i</math> in the reverse order of step 2 on which step 4 is based.

Let <math>C_i</math> and <math>C_j (i \neq j)</math> be two SCC of <math>G</math>. Since each SCC is processed exhaustively or not at all in a [[Depth-first search|DFS]] run, it suffices to show that <math>C_i</math> and <math>C_j</math> are not processed within the same run of step 4. Suppose for a contradiction that <math>C_i</math> and <math>C_j</math> are processed in the same [[Depth-first search|DFS]] run in step 4 (not necessarily in the same run in step 1). Let <math>C_k</math> be the SCC which the start node of that run in step 4 belongs to (possibly <math>k=i</math> or <math>k=j</math>). Without loss of generality, suppose <math>k\neq i</math>. Then <math>C_i</math> is reachable from <math>C_k</math> in <math>G^t</math>; in other words, <math>C_k</math> is reachable from <math>C_i</math> in <math>G</math>. However, then at least one node of <math>C_i</math> had had a higher finishing time in step 1 than the nodes of <math>C_k</math>, so it had been chosen as a start node in step 4 before any node of <math>C_k</math> and the whole SCC <math>C_i</math> had been seen in the [[Depth-first search|DFS]] run from this node which contradicts the assumption that it is seen in a [[Depth-first search|DFS]] run from a node of <math>C_k</math>.

== Complexity ==

'''Statement:''' The asymptotic complexity is in <math>\Theta(|V|+|A|)</math>.

'''Proof:''' Follows immediately from the linear asymptotic complexity of [[Repeated depth-first search|repeated DFS]].

== Pseudocode ==

<code>
STRONGLY-CONNECTED-COMPONENTS(''D'')
1 call '''DFS'''(''D'') to compute finishing times ''f''[v] for each vertex ''v'' ∈ ''V''
2 compute ''D''''T'' (w.r.t. step 3)
3 call '''DFS'''(''D''''T''), but in the main loop of '''DFS''', consider the vertices in order of decreasing ''f''[v] as computed in step 1
4 output the vertices of each tree in the '''DFS''' forest of step 3 as a separate strongly connected component
</code>

Kosaraju

2014-12-30T14:19:59Z

BB91: /* Correctness */

[[Category:Graph Algorithms]]

== General information ==

'''Algorithmic problem:''' [[Strongly connected components]]

'''Type of algorithm:''' loop

== Abstract View ==

# Apply a [[repeated depth-first search]] to <math>G</math>, the output order is parenthetical.
# Invert the output order of the nodes.
# Let <math>G^t=(V,A^t)</math> be the [[Basic graph definitions#Transpose of a graph|transpose]] of <math>G=(V,A)</math>.
# Apply a [[repeated depth-first search]] to <math>G^t</math> with a modification: The order in which the nodes are considered as potential start nodes is the inverted parenthetical order from step 2.
# The node sets from the individual applications of [[Depth-first search|DFS]] inside step 4 are exactly the SCC of <math>G</math>.

== Correctness ==

First note that the transposition of all arcs does not change the SCC of a graph, so step 4 indeed processes the SCC of <math>G</math>.
[[File:CondensedGraphKosaraju.jpg|200px|thumb|right|Construction of the condensed graph (example)]]
Consider the condensed graph <math>G'</math> whose nodes are these SCC, and there is an arc from an SCC <math>C_i</math> to an SCC <math>C_j</math> in <math>G'</math> if, and only if, there is at least one arc in <math>G</math> from some node in <math>C_i</math> to some node in <math>C_j</math>. This condensed graph is acyclic because all nodes in all SCC on a cycle would be mutually reachable from each other in <math>G</math> and their union would consequently form a single larger SCC contradicting the construction of the condensed graph.

In step 1, each [[Depth-first search|DFS]] run either meets ''all'' nodes of an SCC of <math>G</math> or ''none'' of the nodes of this SCC. More specifically, all nodes in the same SCC as the start node and in all SCC reachable from that SCC, except for the SCC processed in previous [[Depth-first search|DFS]] runs.

Due to the parenthetical order of the [[Depth-first search|DFS]], if an SCC <math>C_i</math> is reachable from an SCC <math>C_j</math> in <math>G</math>, then there is at least one node of <math>C_j</math> which appears after all nodes of <math>C_i</math> in the output sequence of step 1 (because it is finished in [[Depth-first search|DFS]] after the nodes of <math>C_i</math>). Equivalently, there is at least one node of <math>C_j</math> which appears before all nodes of <math>C_i</math> in the reverse order of step 2 on which step 4 is based.

Let <math>C_i</math> and <math>C_j</math> be two SCC of <math>G</math>. Since each SCC is processed exhaustively or not at all in a [[Depth-first search|DFS]] run, it suffices to show that <math>C_i</math> and <math>C_j</math> are not processed within the same run of step 4. Suppose for a contradiction that <math>C_i</math> and <math>C_j</math> are processed in the same [[Depth-first search|DFS]] run in step 4 (not necessarily in the same run in step 1). Let <math>C_k</math> be the SCC to which the start node of that run belongs (possibly <math>k=i</math> or <math>k=j</math>). Without loss of generality, suppose <math>k\neq i</math>. Then <math>C_i</math> is reachable from <math>C_k</math> in <math>G'</math>; in other words, <math>C_k</math> is reachable from <math>C_i</math> in <math>G</math>. However, then the nodes of <math>C_i</math> have higher finishing times than the nodes of <math>C_k</math>, so some node of <math>C_i</math> had been chosen as a start node before any node of <math>C_k</math>.

== Complexity ==

'''Statement:''' The asymptotic complexity is in <math>\Theta(|V|+|A|)</math>.

'''Proof:''' Follows immediately from the linear asymptotic complexity of [[Repeated depth-first search|repeated DFS]].

== Pseudocode ==

<code>
STRONGLY-CONNECTED-COMPONENTS(''D'')
1 call '''DFS'''(''D'') to compute finishing times ''f''[v] for each vertex ''v'' ∈ ''V''
2 compute ''D''''T'' (w.r.t. step 3)
3 call '''DFS'''(''D''''T''), but in the main loop of '''DFS''', consider the vertices in order of decreasing ''f''[v] as computed in step 1
4 output the vertices of each tree in the '''DFS''' forest of step 3 as a separate strongly connected component
</code>

Kosaraju

2014-12-30T14:17:55Z

BB91: /* Correctness */

[[Category:Graph Algorithms]]

== General information ==

'''Algorithmic problem:''' [[Strongly connected components]]

'''Type of algorithm:''' loop

== Abstract View ==

# Apply a [[repeated depth-first search]] to <math>G</math>, the output order is parenthetical.
# Invert the output order of the nodes.
# Let <math>G^t=(V,A^t)</math> be the [[Basic graph definitions#Transpose of a graph|transpose]] of <math>G=(V,A)</math>.
# Apply a [[repeated depth-first search]] to <math>G^t</math> with a modification: The order in which the nodes are considered as potential start nodes is the inverted parenthetical order from step 2.
# The node sets from the individual applications of [[Depth-first search|DFS]] inside step 4 are exactly the SCC of <math>G</math>.

== Correctness ==

First note that the transposition of all arcs does not change the SCC of a graph, so step 4 indeed processes the SCC of <math>G</math>.
[[File:CondensedGraphKosaraju.jpg|200px|thumb|right|Construction of the condensed graph (example)]]
Consider the condensed graph <math>G'</math> whose nodes are these SCC, and there is an arc from an SCC <math>C_i</math> to an SCC <math>C_j</math> in <math>G'</math> if, and only if, there is at least one arc in <math>G</math> from some node in <math>C_i</math> to some node in <math>C_j</math>. This condensed graph is acyclic because all nodes in all SCC on a cycle would be mutually reachable from each other in <math>G</math> and their union would consequently form a single larger SCC contradicting the construction of the condensed graph.

In step 1, each [[Depth-first search|DFS]] run either meets ''all'' nodes of an SCC of <math>G</math> or ''none'' of the nodes of this SCC. More specifically, all nodes in the same SCC as the start node and in all SCC reachable from that SCC, except for the SCC processed in previous [[Depth-first search|DFS]] runs.

Due to the parenthetical order of the [[Depth-first search|DFS]], if an SCC <math>C_i</math> is reachable from an SCC <math>C_j</math> in <math>G</math>, then there is at least one node of <math>C_j</math> which appears after all nodes of <math>C_i</math> in the output sequence of step 1. Equivalently, there is at least one node of <math>C_j</math> which appears before all nodes of <math>C_i</math> in the reverse order of step 2 on which step 4 is based.

Let <math>C_i</math> and <math>C_j</math> be two SCC of <math>G</math>. Since each SCC is processed exhaustively or not at all in a [[Depth-first search|DFS]] run, it suffices to show that <math>C_i</math> and <math>C_j</math> are not processed within the same run of step 4. Suppose for a contradiction that <math>C_i</math> and <math>C_j</math> are processed in the same [[Depth-first search|DFS]] run in step 4 (not necessarily in the same run in step 1). Let <math>C_k</math> be the SCC to which the start node of that run belongs (possibly <math>k=i</math> or <math>k=j</math>). Without loss of generality, suppose <math>k\neq i</math>. Then <math>C_i</math> is reachable from <math>C_k</math> in <math>G'</math>; in other words, <math>C_k</math> is reachable from <math>C_i</math> in <math>G</math>. However, then the nodes of <math>C_i</math> have higher finishing times than the nodes of <math>C_k</math>, so some node of <math>C_i</math> had been chosen as a start node before any node of <math>C_k</math>.

== Complexity ==

'''Statement:''' The asymptotic complexity is in <math>\Theta(|V|+|A|)</math>.

'''Proof:''' Follows immediately from the linear asymptotic complexity of [[Repeated depth-first search|repeated DFS]].

== Pseudocode ==

<code>
STRONGLY-CONNECTED-COMPONENTS(''D'')
1 call '''DFS'''(''D'') to compute finishing times ''f''[v] for each vertex ''v'' ∈ ''V''
2 compute ''D''''T'' (w.r.t. step 3)
3 call '''DFS'''(''D''''T''), but in the main loop of '''DFS''', consider the vertices in order of decreasing ''f''[v] as computed in step 1
4 output the vertices of each tree in the '''DFS''' forest of step 3 as a separate strongly connected component
</code>

Depth-first search

2014-12-30T09:55:17Z

BB91: /* Abstract view */

[[Category:Algorithms]]
[[Category:Search Algorithms]]
[[Category:Tree Algorithms]]
[[Category:Graph Traversal]]

== General information ==

'''Algorithmic problem:''' [[Graph traversal]]

'''Type of algorithm:''' loop

== Definitions ==
# For each node, an arbitrary but fixed ordering of the outgoing arcs is assumed. An arc <math>(v,w)</math> preceding an arc <math>(v,w')</math> in this ordering is called '''lexicographically smaller''' than <math>(v,w)</math>.
# Let <math>p</math> and <math>p'</math> be two paths that start from the same node <math>v\in V</math>, but may or may not have the same end node. Let <math>w</math> be the last common node such that the subpaths of <math>p</math> and <math>p'</math> from <math>v</math> up to <math>w</math> are identical (possibly <math>v=w</math>). If the next arc of <math>p</math> from <math>w</math> onwards is lexicographically smaller than the next arc of <math>p'</math> from <math>w</math> onwards, <math>p</math> is said to be '''lexicograpically smaller''' than <math>p'</math>. Note that the lexicographically ''smallest'' path from <math>v\in V</math> to <math>w\in V</math> is well defined and unique.
# With respect to a starting node <math>s\in V</math>, a node <math>v\in V</math> is '''lexicographically smaller''' than <math>w\in V</math> if the lexicographically smallest path from <math>s</math> to <math>v</math> is lexicographically smaller than the lexicographically smallest path from <math>s</math> to <math>w</math>.
# In all of the above cases, the reverse relation is called '''lexicographically larger'''.
# A node <math>v\in V</math> is '''lexicographically smaller''' (resp., '''lexicograpically larger''') than a path <math>p</math> if <math>v</math> does not belong to <math>p</math> and the lexicographically smallest path from the start node of <math>p</math> to <math>v</math> is lexicographically smaller (resp., larger) than <math>p</math>. (Note the asymmetry: In both cases, the lexicographically ''smallest'' path to <math>v</math> is used.)
# In all cases, we also say '''precedes''' and '''succeeds''', respectively, instead of "is lexicograpically smaller/larger".

== Abstract view ==

'''Additional output:'''
# Each node has two Boolean labels with semantics, "is seen" and "is finished".
# An [[Basic graph definitions#Forests, trees, branchings, arborescences|arborescence]] <math>A=(V',A')</math> rooted at <math>s</math> such that <math>V'\subseteq V</math> is the set of all nodes reachable from <math>s</math> (including <math>s</math>). For each node <math>v\in V'</math>, the path from <math>s</math> to <math>v</math> in <math>A</math> is the lexicographically smallest <math>(s,v)</math>-path in <math>G</math>.

'''Specific characteristic:'''
The nodes may be returned either in lexicographic order or (alternatively or simultaneously) in '''parenthetical order''', that is:
Let <math>v,w\in V</math> such that <math>v</math> is seen before <math>w</math>. If there is a path from <math>v</math> to <math>w</math>, <math>w</math> is finished prior to <math>v</math>.

'''Remark:'''
''Parenthetical'' refers to the following intuition: Whenever a node is seen, open a parenthesis, and close it once the node is finished. The result is a correct parenthetial expression: Two parentheses are either disjoint, or one is nested in the other one.

'''Auxiliary data:'''
# A [[Sets and sequences#Stacks and queues|stack]] <math>S</math> whose elements are nodes in <math>V</math>.
# Each node has a '''current arc''' <math>a_v\in V</math>, which is either void or an outgoing arc <math>a_v=(v,w)</math> of <math>v</math>. (May be viewed as an iterator over the list of all outgoing arcs.)

'''Invariant:'''
Before and after each iteration:
# <math>S</math> forms a path <math>p</math> from the start node <math>s</math> to some other node, that is, the order of the nodes on <math>p</math> is the order in which they appear in <math>S</math> (start node <math>s</math> at the bottom of <math>S</math>).
# For each node not yet seen, the current arc is the first arc (or void if the node has no outgoing arcs).
# For each node <math>v</math> on <math>p</math>:
## If there are arcs <math>(v,w)\in A</math> such that <math>w</math> is not yet seen, the current arc equals or precedes the first such arc.
## The subpath of <math>p</math> from the start node <math>s</math> to <math>v</math> is the lexicographically first <math>(s,v)</math>-path.
# The nodes on <math>p</math> are seen but not finished. Let <math>p+a</math> denote the concatenation of <math>p</math> with the current arc <math>a</math> of the last node of <math>p</math>. The nodes that are lexicographically smaller than <math>p+a</math> are seen and finished, and the nodes that lexicographically succeed <math>p+a</math> are neither seen nor finished. (Note that nothing is said about the head of <math>a</math>).

'''Variant:''' Either one node is finished or the current arc of one node is moved forward.

'''Break condition:''' <math>S=\emptyset</math>.

== Induction basis ==

'''Abstract view:''' No node is finished. The start node <math>s</math> is seen, no other node is seen. The start node is the only element of <math>S</math>. The current arc of each node is its first outgoing arc. If the nodes are to be returned in lexicographic order, the start node <math></math> is, initially, the only member of the output sequence; otherwise, the initial output sequence is empty. Arborescence <math>A</math> is initialized so as to contain <math>s</math> and nothing else.

'''Implementation:''' Obvious.

'''Proof:''' Obvious.

== Induction step ==

'''Abstract view:'''
# Let <math>v</math> be the last node of <math>p</math> (=the top element of <math>S</math>).
# While the current arc of <math>v</math> is not void and while the head of the current arc is labeled as seen: Move the current arc one step forward.
# If the current arc of <math>v</math> is not void, say, <math>a_v=(v,w)</math>:
## Insert <math>w</math> and <math>(v,w)</math> in <math>A</math>.
## Push <math>w</math> on <math>S</math>.
## Label <math>w</math> as seen.
## If the output order is the lexicographical one: Append <math>w</math> to the output sequence.
# Otherwise:
## Remove <math>v</math> from <math>S</math>
## Label <math>v</math> as finished.
## If the output order is the parenthetical one: Put <math>v</math> in the output sequence.

'''Implementation:''' Obvious.

'''Proof:'''
The loop ''variant'' is obviously fulfilled.

The first point of the ''invariant'' is obviously fulfilled, too. The second point follows from the fact that the current arc of a node is initialized to be the node's very first outgoing arc and only changed after the node is labeled as ''seen''. Point 3.1 follows from the fact that, in step 2, the current arc never skips an arc that points to an unseen node.

For point 3.2, let <math>p'</math> be the lexicographically smallest <math>(s,v)</math>-path. Moreover, let <math>w\neq v</math> be the last node on <math>p</math> and <math>p'</math> such that both paths are identical from <math>s</math> to <math>w</math> (possibly, <math>w=s</math>). Further, let <math>u</math> and <math>u'</math> be the immediate successors of <math>w</math> on <math>p</math> and <math>p'</math>, respectively. Then <math>u'</math> has been seen before <math>u</math> because <math>(w,u)</math> is the arc over which <math>u</math> was seen for the first time, and <math>(w,u')</math> precedes <math>(w,u)</math>. Note that <math>v</math> has not been seen earlier than <math>u</math> (in fact, later than <math>u</math>, unless <math>v=u</math>). In summary, <math>u'</math> has been seen before <math>v</math>. Since there is a path from <math>u'</math> to <math>v</math>, the correctness proof [[#Correctness|below]] will prove that <math>v</math> was finished before <math>u'</math>. This contradicts the induction hypothesis (point 4 of the invariant).

When a node is pushed on <math>S</math>, it is neither seen nor finished immediately before that iteration and then labeled as seen in that iteration. The node is finished when it leaves <math>S</math>. Both facts together give the first sentence of point 4. The other statements of point 4 follow from the observation that the concatenation of <math>p</math> with the current arc of the endnode of <math>p</math> increases lexicographically in each iteration.

== Correctness ==

It is easy to see that each operation of the algorithm is well defined. Due to the variant, the loop terminates after a finite number of steps. Immediately before the last iteration, <math>p</math> consists of the start node <math>s</math> only, and the current arc of <math>s</math> is void. Therefore, ''all'' nodes reachable from <math>s</math> except for <math>s</math> itself are lexicographically smaller than <math>p</math> at that moment. Due to point 4 of the invariant, all of these nodes are finished. In the last iteration, <math>s</math> is finished as well.

So, it remains to show that the specific characteristic is fulfilled in both cases.
Due to point 3.2 of the invariant, a node is seen for the first time via its lexicographically smallest path from <math>s</math>. Since the current path increases lexicographically in each iteration, the nodes are labeled as seen in lexicographic order. In summary, the lexicographical order is correct.

So consider the second, the parenthetical case.
Let <math>v</math> be seen before <math>w</math> and assume there is a path from <math>v</math> to <math>w</math>. We have to show that <math>w</math> is finished prior to <math>v</math>. Let <math>p'</math> denote the lexicographically smallest <math>(v,w)</math>-path. There is a stage in which this path is a subpath of the current path <math>p</math>. Clearly, <math>v</math> cannot be removed from <math>S</math> before <math>w</math>. This proves the claim.

== Complexity ==

'''Statement:''' The asymptotic complexity is in <math>\Theta(|V|+|A|)</math> in the worst case.

'''Proof:'''
For every node reachable from <math>s</math> (including <math>s</math>), the algorithm processes each of its outgoing arcs exactly once. And from each of these nodes, the algorithm goes backwards exactly once. Obviously, each of these steps requires a constant number of operations.

== Remark ==

Alternatively, DFS could be implemented as a recursive procedure. However, this excludes the option to implement DFS as an iterator, which means to turn the loop inside-out (cf. remarks on [[Graph traversal|graph traversal]]).

== Pseudocode recursive implementation ==

==== DFS(''G'') ====
:'''for''' each vertex ''u'' ∈ ''V'' [''G'']
::'''do''' color[''u''] ← WHITE
::: ''π''[''u''] ← NIL
:''time'' ← 0
:: '''do if''' ''color''[''u''] == WHITE
::: '''then''' DFS-VISiT(''u'')

====DFS-VISIT(''u'')====
: ''color''[''u''] ← GRAY
: ''time'' ← ''time'' + 1
: ''d''[''u''] ← ''time''
: '''for''' each ''v'' ∈ ''Adj''[''u'']
:: '''do if''' ''color''[''v''] = WHITE
::: ''' then ''' π [''v''] ← ''u''
:::: DFS-VISIT(''v'')
:''color''[''u''] ← BLACK
:''f''[''u''] ← ''time'' ← ''time'' + 1

== Pseudocode stack implementation ==

====DFS(''s'')====
: ''S = new Stack()''
: ''s.IsSeen = true''
: ''S.push(s)''
: '''while''' ''S'' ≠ ∅
:: ''n'' = ''S.peek()''
:: ''a'' = ''(v, w)'' = ''n.nextArc()''
:: '''if''' ''a'' == ''null''
::: ''n.IsFinised'' = ''true''
::: ''S.pop()''
:: '''else if''' ''w.IsSeen'' == ''false''
::: ''w.IsSeen'' = ''true''
::: ''S.push(w)''

Bounded priority queue

2014-12-28T14:17:35Z

BB91:

__NOTOC__
[[Category:Checkup]]
[[Category:Abstract Data Structure]]
[[Category:Sequence]]

== General information ==
'''Representation invariant:'''
# This abstract data structure is [[Genericity|generic]] and parameterized by a fixed '''key type''' <math>\mathcal{K}</math> and a fixed [[comparison]] <math>c</math> defined on <math>\mathcal{K}</math>.
# An object with key type <math>\mathcal{K}</math> represents a finite, dynamically changing [[multiset]], of elements of type <math>\mathcal{K}</math> (the multiset may be empty).
# An object has two additional attributes, which are natural numbers:
## Attribute <math>n</math> stores the current number of elements (in particular, <math>n</math> is dynamically changing).
## Attribute <math>N_\text{max}\in\mathrm{N}</math> is the maximum number of elements that can be stored in the queue (<math>N_\text{max}</math> is constant throughout the object's life time).
# Therefore, at any moment, it is <math>n\le N_\text{max}</math>.
'''Constructor:''' Gets a [[comparison]] <math>c</math> and a natural number <math>N_\text{max}</math>, and initializes the queue so as to be empty with a maximum capacity of <math>N_\text{max}</math> items.

== Method ==
'''Name:''' insert

'''Input:''' A key <math>K</math> of type <math>\mathcal{K}</math>

'''Output:''' A unique ID (natural number), which is permanently associated with the inserted key, until the key is extracted from the queue.

'''Precondition:''' It is <math>n<N_\text{max}</math>.

'''Postcondition:''' The input key <math>K</math> is inserted into the queue (a.k.a. ''enqueued'').

== Method ==
'''Name:''' extract minimum

'''Input:''' -

'''Output:''' Returns the minimum key <math>K</math> that is currently stored in the queue.

'''Precondition:''' It is <math>n>0</math>.

'''Postcondition:''' For the minimum key currently stored in the queue, one occurrence is removed (a.k.a. ''dequeued'').

== Method ==
'''Name:''' find minimum

'''Input:''' -

'''Output:''' Returns the minimum key <math>K</math> currently stored in the queue.

'''Precondition:''' It is <math>n>0</math>.

'''Postcondition:''' -

== Method ==
'''Name:''' decrease key

'''Input:''' A natural number <math>ID</math> and a key <math>K</math> of type <math>\mathcal{K}</math>.

'''Output:''' -

'''Precondition:'''
# The input is the ID of some queue element (returned on insertion).
# The value of <math>K</math> is not larger according to <math>c</math> than the current value of the key to which ID refers.

'''Postcondition:''' The key to which ID refers is now <math>K</math> (the old value of that key is lost).

== Method ==
'''Name:''' number

'''Input:''' -

'''Output:''' The value of attribute <math>n</math>, that is, the number of keys currently stored in the queue.

'''Precondition:''' -

'''Postcondition:''' -

== Known implementations ==
[[Heap as array]]

== Remark ==
Usually in applications, the key is actually a pair comprising the key proper and an associated piece of information. In ghis case, the [[Comparison|comparison]] would extract the key proper from each pair and compare the keys proper only.

== Reference ==

Bounded priority queue

2014-12-28T14:08:52Z

BB91:

__NOTOC__
[[Category:Checkup]]
[[Category:Abstract Data Structure]]
[[Category:Sequence]]

== General information ==
'''Representation invariant:'''
# This abstract data structure is [[Genericity|generic]] and parameterized by a fixed '''key type''' <math>\mathcal{K}</math> and a fixed [[comparison]] <math>c</math> defined on <math>\mathcal{K}</math>.
# An object with key type <math>\mathcal{K}</math> represents a finite, dynamically changing [[multiset]], of elements of type <math>\mathcal{K}</math> (the multiset may be empty).
# An object has two additional attributes, which are natural numbers:
## Attribute <math>n</math> stores the current number of elements (in particular, <math>n</math> is dynamically changing).
## Attribute <math>N_\text{max}\in\mathrm{N}</math> is the maximum number of elements that can be stored in the queue (<math>N_\text{max}</math> is constant throughout the object's life time).
# Therefore, at any moment, it is <math>n\le N_\text{max}</math>.
'''Constructor:''' Gets a [[comparison]] <math>c</math> and a natural number <math>N_\text{max}</math>, and initializes the queue so as to be empty with a maximum capacity of <math>N_\text{max}</math> items.

== Method ==
'''Name:''' insert

'''Input:''' A key <math>K</math> of type <math>\mathcal{K}</math>

'''Output:''' A unique ID (natural number), which is permanently associated with the inserted key, until the key is extracted from the queue.

'''Precondition:''' It is <math>n<N_\text{max}</math>.

'''Postcondition:''' The input key <math>K</math> is inserted into the queue (a.k.a. ''enqueued'').

== Method ==
'''Name:''' extract minimum

'''Input:''' -

'''Output:''' Returns the minimum key <math>K</math> that is currently stored in the queue.

'''Precondition:''' It is <math>n>0</math>.

'''Postcondition:''' For the minimum key currently stored in the queue, one occurrence is removed (a.k.a. ''dequeued'').

== Method ==
'''Name:''' find minimum

'''Input:''' -

'''Output:''' Returns the minimum key <math>K</math> currently stored in the queue.

'''Precondition:''' It is <math>n>0</math>.

'''Postcondition:''' -

== Method ==
'''Name:''' decrease key

'''Input:''' A natural number <math>ID</math> and a real number <math>x</math>.

'''Output:''' -

'''Precondition:'''
# The input is the ID of some queue element (returned on insertion).
# The value of <math>x</math> is not larger than the current value of the key to which ID refers.

'''Postcondition:''' The key to which ID refers is now <math>x</math> (the old value of that key is lost).

== Method ==
'''Name:''' number

'''Input:''' -

'''Output:''' The value of attribute <math>n</math>, that is, the number of keys currently stored in the queue.

'''Precondition:''' -

'''Postcondition:''' -

== Known implementations ==
[[Heap as array]]

== Remark ==
Usually in applications, the key is actually a pair comprising the key proper and an associated piece of information. In ghis case, the [[Comparison|comparison]] would extract the key proper from each pair and compare the keys proper only.

== Reference ==

Preflow-push

2014-12-23T14:20:09Z

BB91: /* Induction basis */

== Abstract view ==

'''Algorithmic problem:'''
[[Max-Flow Problems#Standard version|max-flow problem (standard version)]]

'''Type of algorithm:'''
loop.

'''Auxiliary data:'''
# A nonnegative integral value <math>d(v)</math> for each node <math>v\in V</math>.
# Each node <math>v\in V\setminus\{t\}</math> has a '''current arc''', which may be implemented as an iterator on the list of outgoing arcs of <math>v</math>.
# The [[Basic flow definitions#Preflow|excess]] <math>e_f(v)</math> of a node <math>v\in V\setminus\{s,t\}</math> with respect to the current [[Basic flow definitions#Preflow|preflow]].
# A (dynamically changing) [[Sets and sequences|set]] <math>S</math> of nodes.

'''Invariant:'''
Before and after each iteration:
# For each arc <math>a\in A</math>, it is <math>0\leq f(a)\leq u(a)</math> . If all upper bounds are integral, all <math>f</math>-values are integral, too.
# For each node <math>v\in V\setminus\{s,t\} </math>, it is <math>e_f(v)\geq 0</math>. In other words, <math>f</math> is a [[Basic flow definitions#Preflow|preflow]].
# The node labels <math>d</math> form a [[Basic flow definitions#Valid distance labeling|valid distance labeling]], and it is <math>d(s)=|V|</math>.
# The currently [[Basic flow definitions#Preflow|active nodes]] are stored in <math>S</math>.

'''Variant:'''
In each iteration, one of the following three actions will take place:
# The label <math>d(v)</math> of at least one node <math>v\in V\setminus\{s,t\}</math> is increased.
# A saturating push is performed.
# The value of <math>D:=\sum_{v\in V\setminus\{s,t\}\atop e_f(v)>0}d(v)</math> decreases.
No label <math>d(\cdot)</math> is ever decreased.

'''Break condition:'''
<math>S=\emptyset</math>.

== Induction basis ==

'''Abstract view:'''
# For all arcs <math>a\in A</math>, set <math>f(a):=0</math>.
# For each arc <math>(s,v)\in A</math>, overwrite this value by <math>f(a):=u(a)</math> and put <math>v</math> into <math>S</math>.
# Compute a [[Basic flow definitions#Valid distance labeling|valid distance labeling]] <math>d</math> for <math>V\setminus\{s\}</math> with respect to <math>f</math>, for example, the true distances from all nodes to <math>t</math> in the residual network of <math>f</math>.
# Set <math>d(s):=n</math>.
# For all <math>v\in V\setminus\{s,t\}</math>, reset the current arc of <math>v</math> so as to point to the first arc in the list of outgoing arcs of <math>v</math>.

'''Proof:'''
For the [[Basic graph definitions#Subgraphs|subgraph induced]] by <math>V\setminus\{s\}</math>, the arguments in the [[Ahuja-Orlin#Correctness|correctness proof]] for the [[Ahuja-Orlin]] algorithm prove that the <math>d</math>-labels form a valid distance labeling here as well. For <math>s</math>, nothing is to show because all outgoing arcs are saturated.

== Induction step ==

'''Abstract view:'''
# Choose an [[Basic flow definitions#Preflow|active node]] <math>v</math> from <math>S</math>.
# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling|admissible]] either, move the current arc one step forward.
# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:
## If <math>w\neq s</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.
## Increase the flow over <math>f</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.
## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.
## If <math>e_f(v)=0</math> now, extract <math>v</math> from <math>S</math>.
# Otherwise:
## Let <math>d_\max</math> denote the minimal label <math>d(w)</math> of any arc <math>(v,w)</math> in the residual network.
## Set <math>d(v):=d_\max+1</math>.
## Reset the current arc of <math>v</math> so as to point to the beginning of the list of outgoing arcs of <math>v</math>.

'''Remark:'''
The preflow-push algorithm is also known as the '''push-relabel''' algorithm. The ''push'' operation is step 3; the ''relabel'' operation is step 4.

'''Proof:'''
Points 1, 2, and 4 of the invariant and <math>d(s)=n</math> are obviously fulfilled. The rest of point 3 of the invariant is affected by step 4 only, and the outgoing arcs of <math>v</math> are the only arcs where the distance labeling may become invalid. However, the extremely conservative increase of <math>d(v)</math> ensures point 3 of the invariant.

To prove the variant, consider a step in which neither any <math>d</math>-value is increased nor a saturating push is performed. This means step 3.2 is applied, but the arc <math>(v,w)</math> is not saturated by that. Potentially, <math>w</math> becomes active. However, <math>v</math> definitely becomes inactive since the push step is non-saturating. Now the variant follows from the fact that <math>d(w)=d(v)-1</math> for an admissible arc <math>(v,w)</math>.

It remains to show termination; this is proved by the following complexity considerations.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}(n^2m)</math>, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
First we show that the total number of relabel operations (step 4 of the main loop) is in <math>\mathcal{O}(n^2)</math>. To see that, let <math>v\in V\setminus\{s,t\}</math> be an active node between two iterations of the main loop. A straightforward induction over the number of push operations shows that there is at least one simple <math>(s,v)</math>-path <math>p</math> with positive flow on all arcs. The [[Basic graph definitions#Transpose of a graph|transpose]] of <math>p</math> is [[Basic flow definitions#Flow-augmenting paths and saturated arcs|augmenting]]. Due to the validity of <math>d</math> (induction hypothesis), <math>d(v)-d(s)=d(v)-n</math> cannot be larger than the number of arcs on <math>p</math>, which is not larger than <math>n-1</math>. Therefore, no node label can be larger than <math>2n-1</math>. Since node labels are nonnegative and increase at least by one in each relabel operation, the claimed upper bound on the relabel operations follows.

From this bound, we may immediately conclude that the current arc of a node is reset <math>\mathcal{O}(n)</math> times, so the total number of forward steps of the current arcs of all nodes is in <math>\mathcal{O}(n^2)</math>.

The argument in the [[Ahuja-Orlin#Complexity|complexity analysis]] of the [[Ahuja-Orlin]] algorithm to prove that the total number of ''saturating'' push operations is in <math>\mathcal{O}(nm)</math>, applies here as well.

Finally, we consider the ''non-saturating'' push operations. First note that <math>D\geq 0</math> before and after each iteration. The value of <math>D</math> is increased in each relabel operation exactly by the amount by which the label of the current node is increased. Since node labels are never decreased and bounded from above by <math>2n-1</math>, <math>D</math> increases by less than <math>2n^2</math> in total over all relabel operations. On the other hand, a saturating push operation may increase <math>D</math> by at most <math>2n-1</math> (namely, in the case that <math>w</math> was not active immediately before the push). In summary, the total sum of all values by which <math>D</math> is increased throughout the algorithm is in <math>\mathcal{O}(n^2m)</math>. Due to the variant, the value of <math>D</math> is decreased by at least one in each non-saturating push operation. This proves the claim.

== Heuristic speedup techniques ==

# After <math>\Omega(n)</math> iterations of the main loop, the <math>d</math>-values are recomputed analogously to the induction basis: as the current distance of each node to <math>t</math> in the residual network. This modification is seldom enough, so the asymptotic complexity is not increased. In practice, this technique may save many unnecessary relabel steps.
# The main loop may be decomposed into two phases: First, as much flow as possible is sent into <math>t</math>; second, all surplus flow that cannot reach <math>t</math> is sent back to <math>s</math>. The first phase may be finished once there is no more path in the residual network from any active node to <math>t</math>. A sufficient and easy-to-check condition for that is <math>d(v)\geq n</math> for all active nodes <math>v</math>. All nodes from which <math>t</math> is reachable may be safely disregarded in the second phase. For any other node, to save unnecessary relabel operations, the distance label may be safely increased to the minimum number of arcs in the residual network from this node back to <math>s</math>.

Preflow-push

2014-12-20T10:36:34Z

BB91: /* Induction basis */

== Abstract view ==

'''Algorithmic problem:'''
[[Max-Flow Problems#Standard version|max-flow problem (standard version)]]

'''Type of algorithm:'''
loop.

'''Auxiliary data:'''
# A nonnegative integral value <math>d(v)</math> for each node <math>v\in V</math>.
# Each node <math>v\in V\setminus\{t\}</math> has a '''current arc''', which may be implemented as an iterator on the list of outgoing arcs of <math>v</math>.
# The [[Basic flow definitions#Preflow|excess]] <math>e_f(v)</math> of a node <math>v\in V\setminus\{s,t\}</math> with respect to the current [[Basic flow definitions#Preflow|preflow]].
# A (dynamically changing) [[Sets and sequences|set]] <math>S</math> of nodes.

'''Invariant:'''
Before and after each iteration:
# For each arc <math>a\in A</math>, it is <math>0\leq f(a)\leq u(a)</math> . If all upper bounds are integral, all <math>f</math>-values are integral, too.
# For each node <math>v\in V\setminus\{s,t\} </math>, it is <math>e_f(v)\geq 0</math>. In other words, <math>f</math> is a [[Basic flow definitions#Preflow|preflow]].
# The node labels <math>d</math> form a [[Basic flow definitions#Valid distance labeling|valid distance labeling]], and it is <math>d(s)=|V|</math>.
# The currently [[Basic flow definitions#Preflow|active nodes]] are stored in <math>S</math>.

'''Variant:'''
In each iteration, one of the following three actions will take place:
# The label <math>d(v)</math> of at least one node <math>v\in V\setminus\{s,t\}</math> is increased.
# A saturating push is performed.
# The value of <math>D:=\sum_{v\in V\setminus\{s,t\}\atop e_f(v)>0}d(v)</math> decreases.
No label <math>d(\cdot)</math> is ever decreased.

'''Break condition:'''
<math>S=\emptyset</math>.

== Induction basis ==

'''Abstract view:'''
# For all arcs <math>a\in A</math>, set <math>f(a):=0</math>.
# For each arc <math>(s,v)\in A</math>, overwrite this value by <math>f(a):=u(a)</math> and put <math>v</math> into <math>S</math>.
# Compute a valid distance labeling <math>d</math> for <math>V\setminus\{s\}</math> with respect to <math>f</math>, for example, the true distances from all nodes to <math>t</math> in the residual network of <math>f</math>.
# Set <math>d(s):=n</math>.
# For all <math>v\in V\setminus\{s,t\}</math>, reset the current arc of <math>v</math> so as to point to the first arc in the list of outgoing arcs of <math>v</math>.

'''Proof:'''
For the [[Basic graph definitions#Subgraphs|subgraph induced]] by <math>V\setminus\{s\}</math>, the arguments in the [[Ahuja-Orlin#Correctness|correctness proof]] for the [[Ahuja-Orlin]] algorithm prove that the <math>d</math>-labels form a valid distance labeling here as well. For <math>s</math>, nothing is to show because all outgoing arcs are saturated.

== Induction step ==

'''Abstract view:'''
# Choose an [[Basic flow definitions#Preflow|active node]] <math>v</math> from <math>S</math>.
# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling|admissible]] either, move the current arc one step forward.
# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:
## If <math>w\neq s</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.
## Increase the flow over <math>f</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.
## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.
## If <math>e_f(v)=0</math> now, extract <math>v</math> from <math>S</math>.
# Otherwise:
## Let <math>d_\max</math> denote the minimal label <math>d(w)</math> of any arc <math>(v,w)</math> in the residual network.
## Set <math>d(v):=d_\max+1</math>.
## Reset the current arc of <math>v</math> so as to point to the beginning of the list of outgoing arcs of <math>v</math>.

'''Remark:'''
The preflow-push algorithm is also known as the '''push-relabel''' algorithm. The ''push'' operation is step 3; the ''relabel'' operation is step 4.

'''Proof:'''
Points 1, 2, and 4 of the invariant and <math>d(s)=n</math> are obviously fulfilled. The rest of point 3 of the invariant is affected by step 4 only, and the outgoing arcs of <math>v</math> are the only arcs where the distance labeling may become invalid. However, the extremely conservative increase of <math>d(v)</math> ensures point 3 of the invariant.

To prove the variant, consider a step in which neither any <math>d</math>-value is increased nor a saturating push is performed. This means step 3.2 is applied, but the arc <math>(v,w)</math> is not saturated by that. Potentially, <math>w</math> becomes active. However, <math>v</math> definitely becomes inactive since the push step is non-saturating. Now the variant follows from the fact that <math>d(w)=d(v)-1</math> for an admissible arc <math>(v,w)</math>.

It remains to show termination; this is proved by the following complexity considerations.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}(n^2m)</math>, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
First we show that the total number of relabel operations (step 4 of the main loop) is in <math>\mathcal{O}(n^2)</math>. To see that, let <math>v\in V\setminus\{s,t\}</math> be an active node between two iterations of the main loop. A straightforward induction over the number of push operations shows that there is at least one simple <math>(s,v)</math>-path <math>p</math> with positive flow on all arcs. The [[Basic graph definitions#Transpose of a graph|transpose]] of <math>p</math> is [[Basic flow definitions#Flow-augmenting paths and saturated arcs|augmenting]]. Due to the validity of <math>d</math> (induction hypothesis), <math>d(v)-d(s)=d(v)-n</math> cannot be larger than the number of arcs on <math>p</math>, which is not larger than <math>n-1</math>. Therefore, no node label can be larger than <math>2n-1</math>. Since node labels are nonnegative and increase at least by one in each relabel operation, the claimed upper bound on the relabel operations follows.

From this bound, we may immediately conclude that the current arc of a node is reset <math>\mathcal{O}(n)</math> times, so the total number of forward steps of the current arcs of all nodes is in <math>\mathcal{O}(n^2)</math>.

The argument in the [[Ahuja-Orlin#Complexity|complexity analysis]] of the [[Ahuja-Orlin]] algorithm to prove that the total number of ''saturating'' push operations is in <math>\mathcal{O}(nm)</math>, applies here as well.

Finally, we consider the ''non-saturating'' push operations. First note that <math>D\geq 0</math> before and after each iteration. The value of <math>D</math> is increased in each relabel operation exactly by the amount by which the label of the current node is increased. Since node labels are never decreased and bounded from above by <math>2n-1</math>, <math>D</math> increases by less than <math>2n^2</math> in total over all relabel operations. On the other hand, a saturating push operation may increase <math>D</math> by at most <math>2n-1</math> (namely, in the case that <math>w</math> was not active immediately before the push). In summary, the total sum of all values by which <math>D</math> is increased throughout the algorithm is in <math>\mathcal{O}(n^2m)</math>. Due to the variant, the value of <math>D</math> is decreased by at least one in each non-saturating push operation. This proves the claim.

== Heuristic speedup techniques ==

# After <math>\Omega(n)</math> iterations of the main loop, the <math>d</math>-values are recomputed analogously to the induction basis: as the current distance of each node to <math>t</math> in the residual network. This modification is seldom enough, so the asymptotic complexity is not increased. In practice, this technique may save many unnecessary relabel steps.
# The main loop may be decomposed into two phases: First, as much flow as possible is sent into <math>t</math>; second, all surplus flow that cannot reach <math>t</math> is sent back to <math>s</math>. The first phase may be finished once there is no more path in the residual network from any active node to <math>t</math>. A sufficient and easy-to-check condition for that is <math>d(v)\geq n</math> for all active nodes <math>v</math>. All nodes from which <math>t</math> is reachable may be safely disregarded in the second phase. For any other node, to save unnecessary relabel operations, the distance label may be safely increased to the minimum number of arcs in the residual network from this node back to <math>s</math>.

Basic flow definitions

2014-12-20T10:32:22Z

BB91: /* Preflow */

== Basic definitions ==

# [[Basic graph definitions]]

== Basic setting ==
On this page and all dependent pages, <math>G=(V,A)</math> is an [[Basic graph definitions#Directed and undirected graphs|anti-symmetric, simple directed graph]], unless stated otherwise.
# For <math>a\in A</math>, there is a nonnegative '''upper bound''' <math>u(a)</math>.
# In some flow problems, there is a '''lower bound''' <math>\ell(a)</math> as well, which need not be nonnegative.
# In some flow problems, each node <math>v\in V</math> has a '''required balance''' (or '''balance''' for short) <math>b(v)</math>. We also speak of the '''node balance'''.
# In some flow problems, there is a real-valued (not necessarily nonnegative) '''cost factor''' <math>c(a)</math>.
Other node and arc attributes may occur in specific flow problems. Unless stated otherwise, there are no node or arc attributes except for the upper bounds on arcs.

'''Neutral values of attributes:'''
When a node or arc is added to a graph, it is sometimes appropriate to set its attributes to neutral values. The neutral values for upper and lower bounds are <math>+\infty</math> and <math>-\infty</math>, respectively. For cost factors and node balances, the neutral value is zero.

'''Remark:'''
Simplicity and anti-symmetry do not reduce generality in the context of flow problems:
# If there are two arcs <math>a_1</math> and <math>a_2</math>, say, from <math>v</math> to <math>w</math>, add a new node <math>u</math> to <math>V</math>, replace <math>a_1</math> by new arcs <math>(v,u)</math> and <math>(u,w)</math>, transfer the attribute values of <math>a_1</math> to <math>(v,u)</math> and set all attributes of <math>u</math> and of <math>(u,w)</math> to their neutral values.
# If there is a loop <math>(v,v)</math>, add a new node <math>w</math> to <math>V</math>, replace <math>(v,v)</math> by <math>(v,w)</math> and <math>(w,v)</math>, and set the attribute values analogously to the case of parallel arcs.
# If <math>(v,w),(w,v)\in A</math> add a new node <math>u</math> to <math>V</math>, replace <math>(v,w)</math> by new arcs <math>(v,u)</math> and <math>(u,w)</math>, and set the attribute values analogously to the case of parallel arcs.

'''Integrality assumption:'''
All numerical node and arc attributes are integral.

In the context of flow problems, this assumption does not reduce generality, either: Choosing a sufficiently small <math>\delta>0</math> and replacing each attribute value by the nearest integral multiple of <math>\delta</math> has a negligible impact on the output.

== Feasible flow ==

'''Capacity constraints:'''
Let <math>f</math> be an arc weighting, that is, a value <math>f(a)</math> is given for each arc <math>a\in A</math>.
# We say that <math>f</math> fulfills the '''capacity constraints''' if <math>0\leq f(a)\leq u(a)</math> for all <math>a\in A</math>.
# If lower bounds <math>\ell</math> are given, the condition <math>f(a)\geq 0</math> is to be replaced by <math>f(a)\geq\ell(a)</math>. In particular, <math>f(a)</math> may be negative if <math>\ell(a)</math> is so.

'''Flow conservation condition:'''
Let <math>W\subseteq V</math>.
# An arc weighting fulfills the flow conservation condition with respect to <math>W</math> if for all nodes <math>v\in V</math>: <math>\sum_{w\in V\atop(v,w)\in A}f(v,w)-\sum_{w\in V\atop(w,v)\in A}f(w,v)=0</math>.
# If there are balance values <math>b(v)</math> for all nodes <math>v\in V\setminus W</math>, the right-hand side of this condition is not zero but <math>b(v)</math>.

A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.

== Preflow ==

# Preflows generalize feasible flows as follows: Instead of an equation, the following inequality is to be fulfilled for each <math>v\in V\setminus W</math>: <math>\sum_{w:(w,v)\in A}f(w,v)-\sum_{w:(v,w)\in A}f(v,w)\geq 0</math> (resp., <math>\geq b(v)</math>, if node balances are given).
# The '''excess''' of <math>v\in V\setminus W</math> is the value of the left-hand side of that inequality. A node is '''active''' if its excess is strictly positive.

== Flow value ==

Let <math>S,T\in V</math> such that <math>S\cap T=\emptyset</math>, and let <math>f</math> be a flow with respect to <math>S\cup T</math>. The '''flow value''' <math>v(f)</math> of <math>f</math> is defined by
:<math>v(f):=\sum_{s\in S,v\in V\setminus S\atop(s,v)\in A}f(s,v)-\sum_{s\in S,v\in V\setminus S\atop(v,s)\in A}f(v,s)</math>.

'''Remark:'''
A straightforward induction on <math>k\geq|S|</math> shows that for all partitions <math>(V_S,V_T)</math> of <math>V</math> with <math>|V_S|=k</math>, it is
:<math>v(f)=\sum_{v\in V_S,w\in V_T\atop(v,w)\in A}f(v,w)-\sum_{v\in V_S,w\in V_T\atop(w,v)\in A}f(w,v)</math>.
In particular, mirror-symmetrically to the definition of <math>v(f)</math>, it is
:<math>v(f)=\sum_{v\in V\setminus T,t\in T\atop(v,t)\in A}f(v,t)-\sum_{v\in V\setminus T,t\in T\atop(t,v)\in A}f(t,v)</math>.

== Residual network ==

The '''residual network''' <math>(G_f,u_f)</math> of <math>(G,u)</math> with respect to an arc weighting <math>f</math> is defined as follows: It is <math>G_f=(V,A_f)</math>, and for each arc <math>(v,w)\in A</math>, we have:
# <math>(v,w)\in A_f</math> with <math>u_f(v,w)=u(v,w)-f(v,w)</math> if <math>u(v,w)-f(v,w)>0</math>.
# <math>(w,v)\in A_f</math> with <math>u_f(w,v)=f(v,w)</math> if <math>f(v,w)>0</math>.
The value <math>u_f(a)</math> of an arc <math>a\in A_f</math>is called the '''residual capacity''' of <math>a\in A</math> with respect to <math>f</math>.

'''Remark:'''
Changes of <math>f</math> in <math>G</math> and changes of <math>u_f</math> in <math>G_f</math> are equivalent in an obvious way. Since <math>G</math> is anti-symmetric, this equivalence is one-to-one. So, the view on <math>G</math> and <math>f</math> is exchangeable with the view on <math>G_f</math> and <math>u_f</math>. We will adopt both views simultaneously in the presentation and discussion of the individual algorithms. An implementation of an algorithm may be based on <math>(G,f)</math> or on <math>(G_f,u_f)</math> or even on both representations simultaneously.

== Flow-augmenting paths and saturated arcs ==

A '''flow-augmenting path''' (or '''augmenting path''' for short) from some node <math>s\in V</math> to some node <math>t\in V</math> is an [[Basic graph definitions#Paths|ordinary path]] in the residual network <math>G_f</math>. Equivalently, a flow-augmenting path is a [[Basic graph definitions#Paths|generalized path]] in <math>G</math> such that:
# <math>f(a)<u(a)</math> if <math>a\in A</math> is a forward arc;
# <math>f(a)>0</math> if <math>a\in A</math> is a backward arc.
An arc <math>a\in A</math> is '''saturated'''
# in forward direction if <math>f(a)=u(a)</math>.
# in backward direction if <math>f(a)=0</math>.
We say that an arc of a path is '''saturated''' if it is saturated in the direction of this path. Clearly, a path is augmenting if, and only if, it contains no saturated arc in its direction.

== Augmenting along a path ==

Let <math>p</math> denote some flow-augmenting path in <math>G</math>, and let <math>\varepsilon>0</math> such that
# <math>f(a)+\varepsilon\leq u(a)</math> if <math>a\in A</math> is a forward arc;
# <math>f(a)-\varepsilon\geq 0</math> if <math>a\in A</math> is a backward arc.
In the residual network <math>(G_f,u_f)</math>, '''augmenting''' <math>f</math> by <math>\varepsilon</math> along the [[Basic graph definitions#Paths|ordinary path]] induced by <math>p</math> means reducing all residual capacities by <math>\varepsilon</math>. Equivalently, for each arc <math>a \in A</math> on <math>p</math> in <math>G</math>, this means:
# Increase the flow value by <math>\varepsilon</math> if <math>a</math> is a forward arc on <math>p</math>.
# Decrease the flow value by <math>\varepsilon</math> if <math>a</math> is a backward arc on <math>p</math>.
Obviously, the capacity constraints are preserved. The flow conservation conditions are preserved at every [[Basic graph definitions#Paths|internal node]] of <math>p</math>. To see that, let <math>v</math> be such an internal node, and let <math>u</math> and <math>w</math> denote the immediate predecessor and successor of <math>v</math> on <math>p</math>, respectively. Basically, there are four cases:
*Either <math>(u,v)</math> is on <math>p</math> as a forward arc or <math>(v,u)</math> is on <math>p</math> as a backward arc.
*Either <math>(v,w)</math> is on <math>p</math> as a forward arc or <math>(w,v)</math> is on <math>p</math> as a backward arc.
It is easy to check preservation of the flow conservation conditions at <math>v</math> for each of these four cases.

'''Augmenting up to saturation:'''
Again, let <math>p</math> denote some flow-augmenting path.
# Let <math>\varepsilon_1>0</math> denote the minimum of the values <math>u(a)-f(a)</math> on all forward arcs of <math>p</math>.
# Let <math>\varepsilon_2>0</math> denote the minimum of the values <math>f(a)</math> on all backward arcs of <math>p</math>.
# Let <math>\varepsilon</math> denote the minimum of <math>\varepsilon</math> and <math>\varepsilon_2</math>.
Augmenting the flow <math>f</math> along <math>p</math> by <math>\varepsilon</math> yields at least one saturated arc.

== Cuts and saturated cuts ==

# Let <math>G=(V,A)</math> be a directed graph and <math>s,t\in V</math>. An <math>(s,t)</math>-'''cut''' (or '''cut''' for short) is a bipartition <math>(S,T)</math> of <math>V</math> such that <math>s\in S</math> and <math>t\in T</math>.
# For <math>a\in A</math>, let <math>u(a)</math> and <math>f(a)</math> be real values such that <math>0\leq f(a)\leq u(a)</math> (<math>f</math> need not be a flow here). A cut <math>(S,T)</math> is '''saturated''' if:
## <math>f(v,w)=u(v,w)</math> for every arc <math>(v,w)\in A</math> such that <math>v\in S</math> and <math>w\in T</math>.
## <math>f(v,w)=0</math> for every arc <math>(v,w)\in A</math> such that <math>v\in T</math> and <math>w\in S</math>.

== Valid distance labeling ==

'''Definition:'''
# Let <math>G=(V,A)</math> be a directed graph, and for each arc <math>a\in A</math> let <math>u(a)</math> and <math>f(a)</math> be defined such that <math>0\leq f(a)\leq u(a)</math>. An assignment of a value <math>d(v)</math> to each node <math>v\in V</math> is a '''valid distance labeling''' if the following two conditions ar fulfilled:
## It is <math>d(t)=0</math>.
## For each arc <math>(v,w)\in A</math> in the residual network, it is <math>d(v)\leq d(w)+1</math>.
# If even <math>d(v)=d(w)+1</math>, <math>(v,w)</math> is called an '''admissible arc'''.

Hopcroft-Tarjan

2014-11-27T16:24:01Z

BB91: /* Step 1 */

[[Category:Graph Algorithms]]
== Abstract view ==

'''Algorithmic problem:'''
[[Biconnected components]]

'''Type of algorithm:'''
two steps.

== Step 1 ==

'''Abstract view:'''
# 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 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 '''depth''' of <math>v</math> in the 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 A</math> for some immediate or non-immediate successor <math>u</math> 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 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.
# ''Lowpoint'':
## Whenever a node <math>v\in V</math> is seen for the first time, its lowpoint is set identical 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>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 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>.

'''Remarks:'''
# 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 ==

'''Definition:'''
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:'''
A repeated application of [[Depth-first search|DFS]], 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 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.

== Correctness ==

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

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.

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 ==

'''Statement:'''
The asymptotic complexity is linear.

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

Main Page

2014-11-18T11:28:08Z

BB91: /* Flow Algorithms */

== News ==
* The http://wiki.algo.informatik.tu-darmstadt.de domain will forward to this page from 13th October.
* The old wiki will be reachable at http://huffmann.algo.informatik.tu-darmstadt.de/wiki/
* <math>LaTeX</math> [http://www.mediawiki.org/wiki/Manual:Math available now!]
* ToDo List added
* Every content has to be in English!
* [http://www.mediawiki.org/wiki/Extension:SyntaxHighlight_GeSHi Syntaxhighlight]

== Rules ==
* Add finalized reconstructions of the old Wiki to Category:Checkup.
* Don't any non-Weihe content until the reconstructions isn't finished.
* Keep your active reconstructing Pages in "Division of labor" section up to date!

'''Look here for short/uncomplete Pages''' [[Special:ShortPages]]

== Page Status ==
Final: [[:Category:Checkup]]

== To Do ==
=== Notations ===
* [[Big O notation]]
* [[L' Hospital]]
* [[Master theorem]]

=== Problems ===
* [[Matchings in graphs#Cardinality-maximal matching|Maximum matching problem]]
* [[Max-Flow Problems]]
* [[Min-Cost Flow Problems]]
* [[Shortest Paths Problems]]
** [[All pairs shortest paths]]
*** [[Floyd-Warshall]]
*** [[Bellman-Ford]] (DONE)
*** [[Shortest paths by repeated squaring]] (variant of Bellman-Ford)
** [[Single source shortest paths]]
*** [[Dijkstra]]
** [[Single source single target shortest paths]]
*** [[A*]]
* [[Maximum spanning forest]]
* [[Problems on Sequences]]
** [[Basic Problems on Sequences]]
*** [[Find an element in a sequence]] (DONE)
*** [[Insert an element in a sequence]] (Empty in old wiki?!)
*** [[Median]] (DONE)
*** [[Merging two sorted sequences]] (DONE)
** [[Pattern Matching]]
*** [[One-dimensional string matching]] (DONE)
*** [[String matching]] (DONE)
** [[Sorting]]
*** [[Sorting based on pairwise comparison]] (DONE)
*** [[Sorting Sequences of Strings]] (DONE)

=== Coding Basics ===
* [[Inheritance]]
* [[Generics]]
* [[Collections]]
** [[Iterator]]
** [[Comparator]]

=== String Matching Algorithms ===
* [[Simple string matching algorithm]] (DONE)
* [[String matching based on finite automaton]] (DONE)

=== Sorting Algorithms ===
* [[Bubble]]
* [[Insertion sort]]
* [[Quicksort]]
* [[Bubblesort]]
* [[Mergesort]]
* [[Bucketsort]]
* [[Selection sort]]
* [[Bogosort]]

=== Search Algorithms ===
* [[Binary search]]

=== Auxillary Algorithms ===
* [[Pivot partitioning by scanning]]

=== Manipulation ===
* [[Array list: find]]
* [[Array list: find at position]]
* [[Array list: insert at head]]
* [[Array list: insert at position]]
* [[Array list: number]]
* [[Array list: remove]]
* [[Doubly-linked list: insert at position]]
* [[Doubly-linked list: insert at tail]]
* [[Doubly-linked list: remove]]
* [[Find element in sequence iteratively]]
* [[Find element in sequence recursively]]
* [[Hashtable: find]]
* [[Hashtable: insert]]

=== Tree Algorithms ===
* [[Depth-first search]]
* [[Breadth-first search]]
* [[B-tree: find]]
* [[B-tree: minimum]]
* [[B-tree: maximum]]
* [[B-tree: insert]]
* [[B-tree: insert and rearrange]]
* [[B-tree: merge two siblings]]
* [[B-tree: remove]]
* [[B-tree: shift key to sibling]]
* [[B-tree: rotate]]
* [[B-tree: merge]]
* [[B-tree: split]]
* [[Binary search tree: find]]
* [[Binary search tree: minimum]]
* [[Binary search tree: maximum]]
* [[Binary search tree: insert]]
* [[Binary search tree: remove]]
* [[Binary search tree: remove node]]
* [[Binary search tree: traverse]]

=== Graph Theory ===
* [[Directed graph]]
* [[Bipartite graph|Bipartite graph]] (DONE)
* [[k-partite graph]]
* [[Negative paths]]

=== Graph Algorithms ===
* [[Dijkstra]]
* [[Kruskal]]
* [[Prim]]
* [[Bellman-Ford]] (DONE)
* [[Floyd-Warshall]]
* [[Union Find]]
* [[A*]]
* [[Alternating paths algorithm]]
* [[Johnson]]
* [[Union-find with disjoint trees: find]]
* [[Union-find with lists: unite]]
* [[Max-flow min-cut]]

=== Flow Algorithms ===
* [[Ford-Fulkerson]]
* [[Edmonds-Karp]]

=== Abstract Data Structures ===
*[[Network Structures]]
**[[Graph]]
**[[Tree]]
*[[Sequence]]
**[[Sorted sequence]]
**[[Bounded priority queue]]
**[[Linear sequence]]
**[[Priority queue]]
**[[Sorted sequence]]
=== Implementations of Abstract Data Structures ===
* [[Linked list]]
* [[Array list]]
* [[Binary search tree]]
* [[Doubly-linked list]]
* [[Heap as array]] (DONE (Heap as Array))
* [[Hashtable]]
* [[Multi-way search tree]]
* [[Red-black tree]]
* [[B-tree]]

=== ??? ===
* [[Min-Max Heaps]]
* [[First In - First Out]]
* [[First In - Last Out]]
* [[Directed Tree]]
* [[Decision Tree]]

=== Other ===
* [[Model computer]]

=== Other Algorithms (LOCKED) ===
* [[B*]]
* [[Cyclic redundancy check]]
* [[Euclid]]
* [[Gauss]]
* [[Discrete fourier transform]]
* [[Fast fourier transform]]
* [[Bresenham]]
* [[Round robin]]
* [[Seperate and conquer]]
* [[Message-Digest algorithm]]
* [[Secure hash algorithm]]
* [[Sequent calculus]]
* [[Resolution calculus]]
* [[Cocke-Younger-Kasami algorithm]]
* [[Distance vector routing]]
* [[Link state routing]]
* [[Z Buffer algorithm]]
* [[Marching squares]]
* [[Marching cubes]]
* [[Bottom-Up heapsort]]
* [[Radixsort]]
* [[Median cut]]
* [[Pancake sorting]]
* [[Karnaugh-Veitch diagramm]]
* [[Delanuay triangulation]]
* [[Backtracking]]
* [[Alpha–beta pruning]]
* [[Beam search]]
* [[Best-first search]]
* [[Bidirectional search]]
* [[Borůvka's algorithm]]
* [[Branch and bound]]
* [[D*]]
* [[Depth-limited search]]
* [[Edmonds' algorithm]]
* [[Fringe search]]
* [[Hill climbing]]
* [[IDA*]]
* [[Iterative deepening depth-first search]]
* [[Jump point search]]
* [[Lexicographic breadth-first search]]
* [[SMA*]]
* [[Uniform-cost search]]

=== Other Data Structures (LOCKED) ===
* [[Adelson-Velskii and Landis' tree]]
* [[Patricia-Trie]]
* [[Suffix Tree]]
* [[Huffmann Tree]]
* [[Binary Expression Tree]]
* [[Hash Set]]
* [[Incidence Matrix]]
* [[Voronoi Diagramm]]
* [[Quad Tree]]
* [[Oct Tree]]
* [[kd Tree]]
* [[Binary space partitioning]]

Main Page

2014-11-18T11:24:45Z

BB91: /* To Do */

== News ==
* The http://wiki.algo.informatik.tu-darmstadt.de domain will forward to this page from 13th October.
* The old wiki will be reachable at http://huffmann.algo.informatik.tu-darmstadt.de/wiki/
* <math>LaTeX</math> [http://www.mediawiki.org/wiki/Manual:Math available now!]
* ToDo List added
* Every content has to be in English!
* [http://www.mediawiki.org/wiki/Extension:SyntaxHighlight_GeSHi Syntaxhighlight]

== Rules ==
* Add finalized reconstructions of the old Wiki to Category:Checkup.
* Don't any non-Weihe content until the reconstructions isn't finished.
* Keep your active reconstructing Pages in "Division of labor" section up to date!

'''Look here for short/uncomplete Pages''' [[Special:ShortPages]]

== Page Status ==
Final: [[:Category:Checkup]]

== To Do ==
=== Notations ===
* [[Big O notation]]
* [[L' Hospital]]
* [[Master theorem]]

=== Problems ===
* [[Matchings in graphs#Cardinality-maximal matching|Maximum matching problem]]
* [[Max-Flow Problems]]
* [[Min-Cost Flow Problems]]
* [[Shortest Paths Problems]]
** [[All pairs shortest paths]]
*** [[Floyd-Warshall]]
*** [[Bellman-Ford]] (DONE)
*** [[Shortest paths by repeated squaring]] (variant of Bellman-Ford)
** [[Single source shortest paths]]
*** [[Dijkstra]]
** [[Single source single target shortest paths]]
*** [[A*]]
* [[Maximum spanning forest]]
* [[Problems on Sequences]]
** [[Basic Problems on Sequences]]
*** [[Find an element in a sequence]] (DONE)
*** [[Insert an element in a sequence]] (Empty in old wiki?!)
*** [[Median]] (DONE)
*** [[Merging two sorted sequences]] (DONE)
** [[Pattern Matching]]
*** [[One-dimensional string matching]] (DONE)
*** [[String matching]] (DONE)
** [[Sorting]]
*** [[Sorting based on pairwise comparison]] (DONE)
*** [[Sorting Sequences of Strings]] (DONE)

=== Coding Basics ===
* [[Inheritance]]
* [[Generics]]
* [[Collections]]
** [[Iterator]]
** [[Comparator]]

=== String Matching Algorithms ===
* [[Simple string matching algorithm]] (DONE)
* [[String matching based on finite automaton]] (DONE)

=== Sorting Algorithms ===
* [[Bubble]]
* [[Insertion sort]]
* [[Quicksort]]
* [[Bubblesort]]
* [[Mergesort]]
* [[Bucketsort]]
* [[Selection sort]]
* [[Bogosort]]

=== Search Algorithms ===
* [[Binary search]]

=== Auxillary Algorithms ===
* [[Pivot partitioning by scanning]]

=== Manipulation ===
* [[Array list: find]]
* [[Array list: find at position]]
* [[Array list: insert at head]]
* [[Array list: insert at position]]
* [[Array list: number]]
* [[Array list: remove]]
* [[Doubly-linked list: insert at position]]
* [[Doubly-linked list: insert at tail]]
* [[Doubly-linked list: remove]]
* [[Find element in sequence iteratively]]
* [[Find element in sequence recursively]]
* [[Hashtable: find]]
* [[Hashtable: insert]]

=== Tree Algorithms ===
* [[Depth-first search]]
* [[Breadth-first search]]
* [[B-tree: find]]
* [[B-tree: minimum]]
* [[B-tree: maximum]]
* [[B-tree: insert]]
* [[B-tree: insert and rearrange]]
* [[B-tree: merge two siblings]]
* [[B-tree: remove]]
* [[B-tree: shift key to sibling]]
* [[B-tree: rotate]]
* [[B-tree: merge]]
* [[B-tree: split]]
* [[Binary search tree: find]]
* [[Binary search tree: minimum]]
* [[Binary search tree: maximum]]
* [[Binary search tree: insert]]
* [[Binary search tree: remove]]
* [[Binary search tree: remove node]]
* [[Binary search tree: traverse]]

=== Graph Theory ===
* [[Directed graph]]
* [[Bipartite graph|Bipartite graph]] (DONE)
* [[k-partite graph]]
* [[Negative paths]]

=== Graph Algorithms ===
* [[Dijkstra]]
* [[Kruskal]]
* [[Prim]]
* [[Bellman-Ford]] (DONE)
* [[Floyd-Warshall]]
* [[Union Find]]
* [[A*]]
* [[Alternating paths algorithm]]
* [[Johnson]]
* [[Union-find with disjoint trees: find]]
* [[Union-find with lists: unite]]
* [[Max-flow min-cut]]

=== Flow Algorithms ===
* [[Ford-Fulkerson]]
=== Abstract Data Structures ===
*[[Network Structures]]
**[[Graph]]
**[[Tree]]
*[[Sequence]]
**[[Sorted sequence]]
**[[Bounded priority queue]]
**[[Linear sequence]]
**[[Priority queue]]
**[[Sorted sequence]]
=== Implementations of Abstract Data Structures ===
* [[Linked list]]
* [[Array list]]
* [[Binary search tree]]
* [[Doubly-linked list]]
* [[Heap as array]] (DONE (Heap as Array))
* [[Hashtable]]
* [[Multi-way search tree]]
* [[Red-black tree]]
* [[B-tree]]

=== ??? ===
* [[Min-Max Heaps]]
* [[First In - First Out]]
* [[First In - Last Out]]
* [[Directed Tree]]
* [[Decision Tree]]

=== Other ===
* [[Model computer]]

=== Other Algorithms (LOCKED) ===
* [[B*]]
* [[Cyclic redundancy check]]
* [[Euclid]]
* [[Gauss]]
* [[Discrete fourier transform]]
* [[Fast fourier transform]]
* [[Bresenham]]
* [[Round robin]]
* [[Seperate and conquer]]
* [[Message-Digest algorithm]]
* [[Secure hash algorithm]]
* [[Sequent calculus]]
* [[Resolution calculus]]
* [[Cocke-Younger-Kasami algorithm]]
* [[Distance vector routing]]
* [[Link state routing]]
* [[Z Buffer algorithm]]
* [[Marching squares]]
* [[Marching cubes]]
* [[Bottom-Up heapsort]]
* [[Radixsort]]
* [[Median cut]]
* [[Pancake sorting]]
* [[Karnaugh-Veitch diagramm]]
* [[Delanuay triangulation]]
* [[Backtracking]]
* [[Alpha–beta pruning]]
* [[Beam search]]
* [[Best-first search]]
* [[Bidirectional search]]
* [[Borůvka's algorithm]]
* [[Branch and bound]]
* [[D*]]
* [[Depth-limited search]]
* [[Edmonds' algorithm]]
* [[Fringe search]]
* [[Hill climbing]]
* [[IDA*]]
* [[Iterative deepening depth-first search]]
* [[Jump point search]]
* [[Lexicographic breadth-first search]]
* [[SMA*]]
* [[Uniform-cost search]]

=== Other Data Structures (LOCKED) ===
* [[Adelson-Velskii and Landis' tree]]
* [[Patricia-Trie]]
* [[Suffix Tree]]
* [[Huffmann Tree]]
* [[Binary Expression Tree]]
* [[Hash Set]]
* [[Incidence Matrix]]
* [[Voronoi Diagramm]]
* [[Quad Tree]]
* [[Oct Tree]]
* [[kd Tree]]
* [[Binary space partitioning]]

Directed graph

2014-11-17T20:12:48Z

BB91: /* Definition */

==Definition==
A directed graph is a graph, where every edge has a direction. More precisely, a directed graph is a pair <math>G=(V,A)</math>, where <math>V</math> represents a set of nodes and <math>A</math> a set of arcs. Arcs are ordered pairs of nodes in contrast to unordered pairs of nodes (called edges) in an undirected graph. An arc <math>a = (v, w)</math> is considered to be directed '''from''' <math>v</math> '''to''' <math>w</math>.

K-partite graph

2014-11-17T19:53:33Z

BB91: Created page with "==Definition== An undirected graph <math>G=(V,E)</math> is called '''k-partite''', if there is a partition of <math>V</math>, hereinafter referred to as <math>V=\dot\cup_{i=1..."

==Definition==

An undirected graph <math>G=(V,E)</math> is called '''k-partite''', if there is a partition of <math>V</math>, hereinafter referred to as <math>V=\dot\cup_{i=1}^k V_{i}</math>, such that there is no edge between two nodes that belong to the same partition component <math>V_{i}</math>. In other words, the following implication must hold:
:<math>\forall i\in \{1,\ldots,k\}: v \in V_i \wedge w \in V_i \rightarrow \{v,w\} \not\in E</math>.

==Remark==

For <math>k=2</math>, <math>G</math> is called [[bipartite graph]].

Basic flow definitions

2014-11-16T11:56:12Z

BB91: /* Residual network */

== Basic definitions ==

# [[Basic graph definitions]]

== Basic setting ==
On this page and all dependent pages, <math>G=(V,A)</math> is an [[Basic graph definitions#Directed and undirected graphs|anti-symmetric, simple directed graph]], unless stated otherwise.
# For <math>a\in A</math>, there is a nonnegative '''upper bound''' <math>u(a)</math>.
# In some flow problems, there is a '''lower bound''' <math>\ell(a)</math> as well, which need not be nonnegative.
# In some flow problems, each node <math>v\in V</math> has a '''required balance''' (or '''balance''' for short) <math>b(v)</math>. We also speak of the '''node balance'''.
# In some flow problems, there is a real-valued (not necessarily nonnegative) '''cost factor''' <math>c(a)</math>.
Other node and arc attributes may occur in specific flow problems. Unless stated otherwise, there are no node or arc attributes except for the upper bounds on arcs.

'''Neutral values of attributes:'''
When a node or arc is added to a graph, it is sometimes appropriate to set its attributes to neutral values. The neutral values for upper and lower bounds are <math>+\infty</math> and <math>-\infty</math>, respectively. For cost factors and node balances, the neutral value is zero.

'''Remark:'''
Simplicity and anti-symmetry do not reduce generality in the context of flow problems:
# If there are two arcs <math>a_1</math> and <math>a_2</math>, say, from <math>v</math> to <math>w</math>, add a new node <math>u</math> to <math>V</math>, replace <math>a_1</math> by new arcs <math>(v,u)</math> and <math>(u,w)</math>, transfer the attribute values of <math>a_1</math> to <math>(v,u)</math> and set all attributes of <math>u</math> and of <math>(u,w)</math> to their neutral values.
# If there is a loop <math>(v,v)</math>, add a new node <math>w</math> to <math>V</math>, replace <math>(v,v)</math> by <math>(v,w)</math> and <math>(w,v)</math>, and set the attribute values analogously to the case of parallel arcs.
# If <math>(v,w),(w,v)\in A</math> add a new node <math>u</math> to <math>V</math>, replace <math>(v,w)</math> by new arcs <math>(v,u)</math> and <math>(u,w)</math>, and set the attribute values analogously to the case of parallel arcs.

'''Integrality assumption:'''
All numerical node and arc attributes are integral.

In the context of flow problems, this assumption does not reduce generality, either: Choosing a sufficiently small <math>\delta>0</math> and replacing each attribute value by the nearest integral multiple of <math>\delta</math> has a negligible impact on the output.

== Feasible flow ==

'''Capacity constraints:'''
Let <math>f</math> be an arc weighting, that is, a value <math>f(a)</math> is given for each arc <math>a\in A</math>.
# We say that <math>f</math> fulfills the '''capacity constraints''' if <math>0\leq f(a)\leq u(a)</math> for all <math>a\in A</math>.
# If lower bounds <math>\ell</math> are given, the condition <math>f(a)\geq 0</math> is to be replaced by <math>f(a)\geq\ell(a)</math>. In particular, <math>f(a)</math> may be negative if <math>\ell(a)</math> is so.

'''Flow conservation condition:'''
Let <math>W\subseteq V</math>.
# An arc weighting fulfills the flow conservation condition with respect to <math>W</math> if for all nodes <math>v\in V</math>: <math>\sum_{w\in V\atop(v,w)\in A}f(v,w)-\sum_{w\in V\atop(w,v)\in A}f(w,v)=0</math>.
# If there are balance values <math>b(v)</math> for all nodes <math>v\in V\setminus W</math>, the right-hand side of this condition is not zero but <math>b(v)</math>.

A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.

== Preflow ==

# Preflows generalize feasible flows as follows: Instead of an equation, the following inequality is to be fulfilled for each <math>v\in V\setminus W</math>: <math>\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)\geq 0</math> (resp., <math>\geq b(v)</math>, if node balances are given).
# The '''excess''' of <math>v\in V\setminus W</math> is the value of the left-hand side of that inequality. A node is '''active''' if its excess is strictly positive.

== Flow value ==

Let <math>S,T\in V</math> such that <math>S\cap T=\emptyset</math>, and let <math>f</math> be a flow with respect to <math>S\cup T</math>. The '''flow value''' <math>v(f)</math> of <math>f</math> is defined by
:<math>v(f):=\sum_{s\in S,v\in V\setminus S\atop(s,v)\in A}f(s,v)-\sum_{s\in S,v\in V\setminus S\atop(v,s)\in A}f(v,s)</math>.

'''Remark:'''
A straightforward induction on <math>k\geq|S|</math> shows that for all partitions <math>(V_S,V_T)</math> of <math>V</math> with <math>|V_S|=k</math>, it is
:<math>v(f)=\sum_{v\in V_S,w\in V_T\atop(v,w)\in A}f(v,w)-\sum_{v\in V_S,w\in V_T\atop(w,v)\in A}f(w,v)</math>.
In particular, mirror-symmetrically to the definition of <math>v(f)</math>, it is
:<math>v(f)=\sum_{v\in V\setminus T,t\in T\atop(v,t)\in A}f(v,t)-\sum_{v\in V\setminus T,t\in T\atop(t,v)\in A}f(t,v)</math>.

== Residual network ==

The '''residual network''' <math>(G_f,u_f)</math> of <math>(G,u)</math> with respect to an arc weighting <math>f</math> is defined as follows: It is <math>G_f=(V,A_f)</math>, and for each arc <math>(v,w)\in A</math>, we have:
# <math>(v,w)\in A_f</math> with <math>u_f(v,w)=u(v,w)-f(v,w)</math> if <math>u(v,w)-f(v,w)>0</math>.
# <math>(w,v)\in A_f</math> with <math>u_f(w,v)=f(v,w)</math> if <math>f(v,w)>0</math>.
The value <math>u_f(a)</math> of an arc <math>a\in A_f</math>is called the '''residual capacity''' of <math>a\in A</math> with respect to <math>f</math>.

'''Remark:'''
Changes of <math>f</math> in <math>G</math> and changes of <math>u_f</math> in <math>G_f</math> are equivalent in an obvious way. Since <math>G</math> is anti-symmetric, this equivalence is one-to-one. So, the view on <math>G</math> and <math>f</math> is exchangeable with the view on <math>G_f</math> and <math>u_f</math>. We will adopt both views simultaneously in the presentation and discussion of the individual algorithms. An implementation of an algorithm may be based on <math>(G,f)</math> or on <math>(G_f,u_f)</math> or even on both representations simultaneously.

== Flow-augmenting paths and saturated arcs ==

A '''flow-augmenting path''' (or '''augmenting path''' for short) from some node <math>s\in V</math> to some node <math>t\in V</math> is an [[Basic graph definitions#Paths|ordinary path]] in the residual network <math>G_f</math>. Equivalently, a flow-augmenting path is a [[Basic graph definitions#Paths|generalized path]] in <math>G</math> such that:
# <math>f(a)<u(a)</math> if <math>a\in A</math> is a forward arc;
# <math>f(a)>0</math> if <math>a\in A</math> is a backward arc.
An arc <math>a\in A</math> is '''saturated'''
# in forward direction if <math>f(a)=u(a)</math>.
# in backward direction if <math>f(a)=0</math>.
We say that an arc of a path is '''saturated''' if it is saturated in the direction of this path. Clearly, a path is augmenting if, and only if, it contains no saturated arc in its direction.

== Augmenting along a path ==

Let <math>p</math> denote some flow-augmenting path in <math>G</math>, and let <math>\varepsilon>0</math> such that
# <math>f(a)+\varepsilon\leq u(a)</math> if <math>a\in A</math> is a forward arc;
# <math>f(a)-\varepsilon\geq 0</math> if <math>a\in A</math> is a backward arc.
In the residual network <math>(G_f,u_f)</math>, '''augmenting''' <math>f</math> by <math>\varepsilon</math> along the [[Basic graph definitions#Paths|ordinary path]] induced by <math>p</math> means reducing all residual capacities by <math>\varepsilon</math>. Equivalently, for each arc <math>a \in A</math> on <math>p</math> in <math>G</math>, this means:
# Increase the flow value by <math>\varepsilon</math> if <math>a</math> is a forward arc on <math>p</math>.
# Decrease the flow value by <math>\varepsilon</math> if <math>a</math> is a backward arc on <math>p</math>.
Obviously, the capacity constraints are preserved. The flow conservation conditions are preserved at every [[Basic graph definitions#Paths|internal node]] of <math>p</math>. To see that, let <math>v</math> be such an internal node, and let <math>u</math> and <math>w</math> denote the immediate predecessor and successor of <math>v</math> on <math>p</math>, respectively. Basically, there are four cases:
*Either <math>(u,v)</math> is on <math>p</math> as a forward arc or <math>(v,u)</math> is on <math>p</math> as a backward arc.
*Either <math>(v,w)</math> is on <math>p</math> as a forward arc or <math>(w,v)</math> is on <math>p</math> as a backward arc.
It is easy to check preservation of the flow conservation conditions at <math>v</math> for each of these four cases.

'''Augmenting up to saturation:'''
Again, let <math>p</math> denote some flow-augmenting path.
# Let <math>\varepsilon_1>0</math> denote the minimum of the values <math>c(a)-f(a)</math> on all forward arcs of <math>p</math>.
# Let <math>\varepsilon_2>0</math> denote the minimum of the values <math>f(a)</math> on all backward arcs of <math>p</math>.
# Let <math>\varepsilon</math> denote the minimum of <math>\varepsilon</math> and <math>\varepsilon_2</math>.
Augmenting the flow <math>f</math> along <math>p</math> by <math>\varepsilon</math> yields at least one saturated arc.

== Cuts and saturated cuts ==

# Let <math>G=(V,A)</math> be a directed graph and <math>s,t\in V</math>. An <math>(s,t)</math>-'''cut''' (or '''cut''' for short) is a bipartition <math>(S,T)</math> of <math>V</math> such that <math>s\in S</math> and <math>t\in T</math>.
# For <math>a\in A</math>, let <math>u(a)</math> and <math>f(a)</math> be real values such that <math>0\leq f(a)\leq u(a)</math> (<math>f</math> need not be a flow here). A cut <math>(S,T)</math> is '''saturated''' if:
## <math>f(v,w)=u(v,w)</math> for every arc <math>(v,w)\in A</math> such that <math>v\in S</math> and <math>w\in T</math>.
## <math>f(v,w)=0</math> for every arc <math>(v,w)\in A</math> such that <math>v\in T</math> and <math>w\in S</math>.

== Valid distance labeling ==

'''Definition:'''
# Let <math>G=(V,A)</math> be a directed graph, and for each arc <math>a\in A</math> let <math>u(a)</math> and <math>f(a)</math> be defined such that <math>0\leq f(a)\leq u(a)</math>. An assignment of a value <math>d(v)</math> to each node <math>v\in V</math> is a '''valid distance labeling''' if the following two conditions ar fulfilled:
## It is <math>d(t)=0</math>.
## For each arc <math>(v,w)\in A</math> in the residual network, it is <math>d(v)\leq d(w)+1</math>.
# If even <math>d(v)=d(w)+1</math>, <math>(v,w)</math> is called an '''admissible arc'''.

Kosaraju

2014-11-09T14:59:10Z

BB91: /* Correctness */

== General information ==

'''Algorithmic problem:''' [[Strongly connected components]]

'''Type of algorithm:''' loop

== Abstract View ==

# Apply a [[repeated depth-first search]] to <math>G</math>, the output order is parenthetical.
# Invert the output order of the nodes.
# Let <math>G^t=(V,A^t)</math> be the [[Basic graph definitions#Transpose of a graph|transpose]] of <math>G=(V,A)</math>.
# Apply a [[repeated depth-first search]] to <math>G^t</math> with a modification: The order in which the nodes are considered as potential start nodes is the inverted parenthetical order from step 2.
# The node sets from the individual applications of [[Depth-first search|DFS]] inside step 4 are exactly the SCC of <math>G</math>.

== Correctness ==

First note that the transposition of all arcs does not change the SCC of a graph, so step 4 indeed processes the SCC of <math>G</math>.
[[File:CondensedGraphKosaraju.jpg|200px|thumb|right|Construction of the condensed graph (example)]]
Consider the condensed graph <math>G'</math> whose nodes are these SCC, and there is an arc from an SCC <math>C_i</math> to an SCC <math>C_j</math> in <math>G'</math> if, and only if, there is at least one arc in <math>G</math> from some node in <math>C_i</math> to some node in <math>C_j</math>. This condensed graph is acyclic because all nodes in all SCC on a cycle would be mutually reachable from each other in <math>G</math> and their union would consequently form a single larger SCC contradicting the construction of the condensed graph.

In step 1, each [[Depth-first search|DFS]] run either meets ''all'' nodes of an SCC of <math>G</math> or ''none'' of the nodes of this SCC. More specifically, all nodes in the same SCC as the start node and in all SCC reachable from that SCC, except for the SCC processed in previous [[Depth-first search|DFS]] runs.

It is easy to see that all nodes of an SCC are finished consecutively (because of the parenthetical order); that is, all nodes of an SCC form a connected subsequence in the output sequence of step 1. In particular, it does not matter in step 4 which node of an SCC is chosen as a start node for a [[Depth-first search|DFS]] run. If an SCC <math>C_i</math> is reachable from an SCC <math>C_j</math> in <math>G</math>, then the nodes of <math>C_i</math> appear before the nodes of <math>C_j</math> in parenthetical order. Equivalently, the nodes of <math>C_i</math> appear ''after'' the nodes of <math>C_j</math> in the reverse order on which step 4 is based.

Let <math>C_i</math> and <math>C_j</math> be two SCC of <math>G</math>. Since each SCC is processed exhaustively or not at all in a [[Depth-first search|DFS]] run, it suffices to show that <math>C_i</math> and <math>C_j</math> are not processed within the same run of step 4. Suppose for a contradiction that <math>C_i</math> and <math>C_j</math> are processed in the same [[Depth-first search|DFS]] run in step 4 (not necessarily in the same run in step 1). Let <math>C_k</math> be the SCC to which the start node of that run belongs (possibly <math>k=i</math> or <math>k=j</math>). Without loss of generality, suppose <math>k\neq i</math>. Then <math>C_i</math> is reachable from <math>C_k</math> in <math>G'</math>; in other words, <math>C_k</math> is reachable from <math>C_i</math> in <math>G</math>. However, then the nodes of <math>C_i</math> have higher finishing times than the nodes of <math>C_k</math>, so some node of <math>C_i</math> had been chosen as a start node before any node of <math>C_k</math>.

== Complexity ==

'''Statement:''' The asymptotic complexity is in <math>\Theta(|V|+|A|)</math>.

'''Proof:''' Follows immediately from the linear asymptotic complexity of [[Repeated depth-first search|repeated DFS]].

== Pseudocode ==

<code>
STRONGLY-CONNECTED-COMPONENTS(''D'')
1 call '''DFS'''(''D'') to compute finishing times ''f''[v] for each vertex ''v'' ∈ ''V''
2 compute ''D''''T'' (w.r.t. step 3)
3 call '''DFS'''(''D''''T''), but in the main loop of '''DFS''', consider the vertices in order of decreasing ''f''[v] as computed in step 1
4 output the vertices of each tree in the '''DFS''' forest of step 3 as a separate strongly connected component
</code>

File:CondensedGraphKosaraju.jpg

2014-11-09T14:52:30Z

BB91: