Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download

📚 The CoCalc Library - books, templates and other resources

132930 views
License: OTHER
Tweet
Share
Share
1
\documentclass{article}

2
\usepackage[pdftex,active,tightpage]{preview}

3
\setlength\PreviewBorder{2mm}

4


5
\usepackage{amssymb,amsmath,amsfonts} % nice math rendering

6
\usepackage{braket} % needed for \Set

7
\usepackage{algorithm,algpseudocode}

8


9
\begin{document}

10
\begin{preview}

11
    \begin{itemize}

12
        \item $c:E \rightarrow \mathbb{R}_0^+$: capacity of an edge

13
        \item $e: V \rightarrow \mathbb{R}_0^+$: excess (too much flow in one node)

14
        \item $r_f: V \times V \rightarrow \mathbb{R}, \; r_f(u,v) := c(u,v) - f(u,v) $: remaining capacity

15
        \item $dist: V \rightarrow \mathbb{N}$: the label (imagine this as height)

16
    \end{itemize}

17


18
    \begin{algorithm}[H]

19
        \begin{algorithmic}

20
             \Function{PushRelabel}{Network $N(D, s, t, c)$}

21
                \ForAll{$(v,w) \in (V \times V \setminus E)$} \Comment{If an edge is not in $D=(V,E)$,}

22
                    \State $c(v,w) \gets 0$ \Comment{then its capacity is 0}

23
                \EndFor

24
                \\

25
                \ForAll{$(v,w) \in V \times V$} \Comment{At the beginning, every edge}

26
                    \State $f(v,w) \gets 0$ \Comment{has flow=0}

27
                    \State $r_f(v,w) \gets c(v,w)$  \Comment{flow=max in the residualgraph}

28
                \EndFor

29
                \\

30
                \State $dist(s) \gets |V|$

31


32
                \ForAll{$v \in V \setminus \Set{s}$}

33
                    \State $f(s,v) \gets c(s,v)$    \Comment{Push maximum flow out at the beginning}

34
                    \State $r(v,s) \gets c(v,s) - f(v,s)$

35
                    \State $dist(v) \gets 0$

36
                    \State $e(v) \gets c(s,v)$ \Comment{$v$ has too much flow}

37
                \EndFor

38
                \\

39
                \While{$\exists v \in V:$ \Call{isActive}{$v$}}

40
                    \If{\Call{isPushOk}{$v$}}

41
                        \State \Call{Push}{$v$}

42
                    \EndIf

43
                    \If{\Call{isRelabelOk}{$v$}}

44
                        \State \Call{Relabel}{$v$}

45
                    \EndIf

46
                \EndWhile

47
                \\

48
                \State \Return $f$ \Comment{Maximaler Fluss}

49
             \EndFunction

50
            \\

51
            \Function{Push}{Node $v$, Node $w$}

52
                \State $\Delta \gets \min\Set{e(v), r_f(v,w)}$

53
                \State $f(v,w) \gets f(v,w) + \Delta$

54
                \State $f(w,v) \gets f(w,v) - \Delta$

55
                \State $r_f(v,w) \gets r_f(v,w) - \Delta$

56
                \State $r_f(w,v) \gets r_f(w,v) + \Delta$

57
                \State $e(v) \gets e(v) - \Delta$

58
                \State $e(w) \gets e(w) + \Delta$

59
            \EndFunction

60
            \\

61
            \Function{Relabel}{Node $v$}

62
                \If{$\Set{w \in V |r_f(v,w) > 0} == \emptyset$}

63
                    \State $dist(v) \gets \infty$

64
                \Else

65
                    \State $dist(v) \gets \min\Set{dist(w)+1|w \in V: r_f(v,w) > 0}$

66
                \EndIf

67
            \EndFunction

68
            \\

69
            \Function{isActive}{Node $v$}

70
                \State\Return $(e(v) > 0) \land (dist(v) < \infty)$

71
            \EndFunction

72
            \\

73
            \Function{isRelabelOk}{Node $v$}

74
                \State\Return \Call{isActive}{$v$} $\displaystyle \bigwedge_{w \in \Set{w \in V | r_f(v,w) >0}}(dist(v) \leq dist(w))$

75
            \EndFunction

76
            \\

77
            \Function{isPushOk}{Node $v$}

78
                \State\Return \Call{isActive}{$v$} $\land (e(v) > 0) \land (dist(v) == dist(w)+1)$

79
            \EndFunction

80
        \end{algorithmic}

81
    \caption{Algorithm of Goldberg and Tarjan}

82
    \label{alg:seq1}

83
    \end{algorithm}

84
\end{preview}

85
\end{document}

86


87