(Solved): MAXIMUM FLOW PROBLEM NODE LABELING ALGORITHM c# or python code? book isbn 0131889230 exampl ...

MAXIMUM FLOW PROBLEM – NODE LABELING ALGORITHM c# or python code?
book isbn 0131889230 example 6.4.2 page 266

???????

???????

Determine the maximal flow in the network of Example 6.4-1 (Figure 6.29). Figure \( 6.31 \) provides a graphical summary of the iterations of the algorithm. You will find it helpful to compare the description of the iterations with the graphical summary. Iteration 1. Set the initial residuals \( \left(c_{i j}, c_{j i}\right) \) equal to the initial capacities \( \left(\bar{C}_{i j}, \bar{C}_{j i}\right) \). Step 1. Set \( a_{1}=\infty \) and label node 1 with \( [\infty,-] \). Set \( i=1 \). Step 2. \( S_{1}=\{2,3,4\}(\neq \varnothing) \). Step 3. \( k=3 \), because \( c_{13}=\max \left\{c_{12}, c_{13}, c_{14}\right\}=\max \{20,30,10\}=30 \). Set \( a_{3}=c_{13}=30 \), and label node 3 with \( [30,1] \). Set \( i=3 \), and repeat step 2 . Step 2. \( S_{3}=(4,5) \). Step 3. \( k=5 \) and \( a_{5}=c_{35}=\max \{10,20\}=20 \). Label node 5 with \( [20,3] \). Breakthrough is achieved. Go to step 5 . Step 5. The breakthrough path is determined from the labels starting at node 5 and moving backward to node 1-that is, \( (5) \rightarrow[20,3] \rightarrow(3) \rightarrow[30,1] \rightarrow(\mathbf{1}) \). Thus, \( N_{1}=\{1,3,5\} \) and \( f_{1}=\min \left\{a_{1}, a_{3}, a_{5}\right\}=\{\infty, 30,20\}=20 \). The residual capacities along path \( N_{1} \) are \[ \begin{array}{l} \left(c_{13}, c_{31}\right)=(30-20,0+20)=(10,20) \\ \left(c_{35}, c_{53}\right)=(20-20,0+20)=(0,20) \end{array} \] Iteration 2 Step 1. Set \( a_{1}=\infty \), and label node 1 with \( [\infty,-] \). Set \( i=1 \). Step 2. \( S_{1}=\{2,3,4\} \). Step 3. \( k=2 \) and \( a_{2}=c_{12}=\max \{20,10,10\}=20 \). Set \( i=2 \), and repeat step 2 . Iterations of the maximum flow algorithm of Example 6.4-2 Step 2. \( S_{2}=\{3,5\} \). Step 3. \( k=3 \) and \( a_{3}=c_{23}=40 \). Label node 3 with \( [40,2] \). Set \( i=3 \), and repeat step 2 . Step 2. \( S_{3}=\{4\} \) (note that \( c_{35}=0 \)-hence, node 5 cannot be included in \( S_{3} \) ). Step 3. \( k=4 \) and \( a_{4}=c_{34}=10 \). Label node 4 with \( [10,3] \). Set \( i=4 \), and repeat step 2 . Step 2. \( S_{4}=\{5\} \) (note that nodes 1 and 3 are already labeled-hence, they cannot be included in \( S_{4} \) ). hapter 6 Network Models Step 3. \( k=5 \) and \( a_{5}=c_{45}=20 \). Label node 5 with \( [20,4] \). Breakthrough has been achieved. Go to step 5. Step 5. \( N_{2}=\{1,2,3,4,5\} \) and \( f_{2}=\min \{\infty, 20,40,10,20\}=10 \). The residuals along the path of \( N_{2} \) are \[ \begin{array}{l} \left(c_{12}, c_{21}\right)=(20-10,0+10)=(10,10) \\ \left(c_{23}, c_{32}\right)=(40-10,0+10)=(30,10) \\ \left(c_{34}, c_{43}\right)=(10-10,5+10)=(0,15) \\ \left(c_{45}, c_{54}\right)=(20-10,0+10)=(10,10) \end{array} \] Step 1. Set \( a_{1}=\infty \) and label node 1 with \( [\infty,-] \). Set \( i=1 \). Step 2. \( S_{1}=\{2,3,4\} \). Step 3. \( k=2 \) and \( a_{2}=c_{12}=\max \{10,10,10\}=10 \). (Though ties are broken arbitrarily, TORA always selects the tied node with the smallest index. We will use this convention throughout the example.) Label node 2 with \( [10,1] \). Set \( i=2 \), and repeat step 2 . Step 2. \( S_{2}=\{3,5\} \). Step 3. \( k=3 \) and \( a_{3}=c_{23}=30 \). Label node 3 with \( [30,2] \). Set \( i=3 \), and repeat step 2 . Step 2. \( S_{3}=\emptyset \) (because \( c_{34}=c_{35}=0 \) ). Go to step 4 to backtrack. Step 3. Backtracking. The label \( [30,2] \) at node 3 gives the immediately preceding node \( r=2 \). Remove node 3 from further consideration in this iteration by crossing it out. Set \( i=r=2 \), and repeat step 2 . Step 2. \( S_{2}=\{5\} \) (note that node 3 has been removed in the backtracking step). Step 3. \( k=5 \) and \( a_{5}=c_{25}=30 \). Label node 5 with \( [30,2] \). Breakthrough has been achieved; go to step 5 . Step 5. \( N_{3}=\{1,2,5\} \) and \( c_{5}=\min \{\infty, 10,30\}=10 \). The residuals along the path of \( N_{3} \) are \[ \begin{array}{l} \left(c_{12}, c_{21}\right)=(10-10,10+10)=(0,20) \\ \left(c_{25}, c_{52}\right)=(30-10,0+10)=(20,10) \end{array} \] Iteration 4. This iteration yields \( N_{4}=\{1,3,2,5\} \) with \( f_{4}=10 \) (verify!). Iteration 5. This iteration yields \( N_{5}=\{1,4,5\} \) with \( f_{5}=10 \) (verify!). Iteration 6. All the arcs out of node 1 have zero residuals. Hence, no further breakthroughs are possible. We turn to step 6 to determine the solution. Step 6. Maximal flow in the network is \( F=f_{1}+f_{2}+\cdots+f_{5}=20+10+10+ \) \( 10+10=60 \) units. The flow in the different arcs is computed by subtracting the last residuals \( \left(c_{i j}, c_{j i}\right) \) in iterations 6 from the initial capacities \( \left(\bar{C}_{i j}\right. \), \( \left.\bar{C}_{j i}\right) \), as the following table shows. \begin{tabular}{cccc} \hline Are & \( \left(\bar{C}_{i j}, \bar{C}_{i j}\right)-\left(c_{i j}, c_{j i}\right)_{6} \) & Flow amount & Direction \\ \hline\( (1,2) \) & \( (20,0)-(0,20)=(20,-20) \) & 20 & \( 1 \rightarrow 2 \) \\ \( (1,3) \) & \( (30,0)-(0,30)=(30,-30) \) & 30 & \( 1 \rightarrow 3 \) \\ \( (1,4) \) & \( (10,0)-(0,10)=(10,-10) \) & 10 & \( 1 \rightarrow 4 \) \\ \( (2,3) \) & \( (40,0)-(40,0)=(0,0) \) & 0 & \( - \) \\ \( (2,5) \) & \( (30,0)-(10,20)=(20,-20) \) & 20 & \( 2 \rightarrow 5 \) \\ \( (3,4) \) & \( (10,5)-(0,15)=(10,-10) \) & 10 & \( 3 \rightarrow 4 \) \\ \( (3,5) \) & \( (20,0)-(0,20)=(20,-20) \) & 20 & \( 3 \rightarrow 5 \) \\ \( (4,5) \) & \( (20,0)-(0,20)=(20,-20) \) & 20 & \( 4 \rightarrow 5 \) \\ \hline \end{tabular}