Network flow problem - Revision history

Wc593 at 11:33, 21 December 2020

2020-12-21T11:33:32Z

← Older revision		Revision as of 07:33, 21 December 2020
Line 1:		Line 1:
	Author: Aaron Wheeler, Chang Wei, Cagla Deniz Bahadir, Ruobing Shui, Ziqiu Zhang (~~CHEME~~ 6800 Fall 2020)		Author: Aaron Wheeler, Chang Wei, Cagla Deniz Bahadir, Ruobing Shui, Ziqiu Zhang (ChemE 6800 Fall 2020)

	== Introduction ==		== Introduction ==

Wc593 at 10:18, 21 December 2020

2020-12-21T10:18:41Z

← Older revision		Revision as of 06:18, 21 December 2020
Line 1:		Line 1:
	Author: Aaron Wheeler, Chang Wei, Cagla Deniz Bahadir, Ruobing Shui, Ziqiu Zhang (CHEME 6800 Fall 2020)		Author: Aaron Wheeler, Chang Wei, Cagla Deniz Bahadir, Ruobing Shui, Ziqiu Zhang (CHEME 6800 Fall 2020)

	~~Steward: Fengqi You, Allen Yang~~

	== Introduction ==		== Introduction ==
Line 453:		Line 451:
	There are several special cases of network problems, such as the shortest path problem, minimum cost flow problem, assignment problem and transportation problem.<sup>[6]</sup> Three application cases will be introduced here.		There are several special cases of network problems, such as the shortest path problem, minimum cost flow problem, assignment problem and transportation problem.<sup>[6]</sup> Three application cases will be introduced here.

	=== The ~~minimum cost flow problem~~ ===		=== The Minimum Cost Flow Problem ===
	[[File:Pic8.jpg\|thumb\|Figure. 12. Illustration of the ship subnetwork.<sub>[14]</sub>]]		[[File:Pic8.jpg\|thumb\|Figure. 12. Illustration of the ship subnetwork.<sub>[14]</sub>]]
	[[File:Pic9.jpg\|thumb\|Figure. 13. Illustration of cargo subnetwork.<sub>[14]</sub>]]		[[File:Pic9.jpg\|thumb\|Figure. 13. Illustration of cargo subnetwork.<sub>[14]</sub>]]
Line 460:		Line 458:
	R. Dewil and his group use MCNFP to assist traffic enforcement.<sup>[13]</sup> Police patrol “hot spots”, which are areas where crashes occur frequently on highways. R. Dewil studies a method intended to estimate the optimal route of hot spots. He describes the time it takes to move the detector to a certain position as the cost, and the number of patrol cars from one node to next as the flow, in order to minimize the total cost.<sup>[13]</sup>		R. Dewil and his group use MCNFP to assist traffic enforcement.<sup>[13]</sup> Police patrol “hot spots”, which are areas where crashes occur frequently on highways. R. Dewil studies a method intended to estimate the optimal route of hot spots. He describes the time it takes to move the detector to a certain position as the cost, and the number of patrol cars from one node to next as the flow, in order to minimize the total cost.<sup>[13]</sup>

	=== The ~~assignment problem~~ ===		=== The Assignment Problem ===
	Dung-Ying Lin studies an assignment problem in which he aims to assign freights to ships and arrange transportation paths along the Northern Sea Route in a manner which yields maximum profit.<sup>[14]</sup> Within this network composed of a ship subnetwork and a cargo subnetwork( shown as Figure 12 and Figure 13), each node corresponds to a port at a specific time and each arc represents the movement of a ship or a cargo. Other types of assignment problems are faculty scheduling, freight assignment, and so on.		Dung-Ying Lin studies an assignment problem in which he aims to assign freights to ships and arrange transportation paths along the Northern Sea Route in a manner which yields maximum profit.<sup>[14]</sup> Within this network composed of a ship subnetwork and a cargo subnetwork( shown as Figure 12 and Figure 13), each node corresponds to a port at a specific time and each arc represents the movement of a ship or a cargo. Other types of assignment problems are faculty scheduling, freight assignment, and so on.

	=== The ~~shortest path problem~~ ===		=== The Shortest Path Problem ===
	Shortest path problems are also present in many fields, such as transportation, 5G wireless communication, and implantation of the global dynamic routing scheme.<sup>[15][16][17]</sup>		Shortest path problems are also present in many fields, such as transportation, 5G wireless communication, and implantation of the global dynamic routing scheme.<sup>[15][16][17]</sup>

Zz at 03:57, 13 December 2020

2020-12-13T03:57:46Z

← Older revision		Revision as of 23:57, 12 December 2020
Line 359:		Line 359:
	bii. <math>c(e)= c(e) - c_{f}(p),c(e')= c(e') + c_{f}(p)</math> in <math> G_{f}</math>		bii. <math>c(e)= c(e) - c_{f}(p),c(e')= c(e') + c_{f}(p)</math> in <math> G_{f}</math>

			[[File:Phase 1.png\|thumb\|Figure 8: Flow graph and residue graph at the first phase]]
	An example of running the FFA is as below.		An example of running the FFA is as below.
	The flow graph <math>G</math> and residue graph<math>G_{f}</math> at the initial phase is depicted in Figure 8, where the number of each edge in the flow graph is the flow units on the edge, whereas it is the updated edge capacity in the residue graph.		The flow graph <math>G</math> and residue graph<math>G_{f}</math> at the initial phase is depicted in Figure 8, where the number of each edge in the flow graph is the flow units on the edge, whereas it is the updated edge capacity in the residue graph.

	~~[[File:Phase 1.png\|thumb\|Figure 8: Flow graph and residue graph at the first phase]]~~

	In the residue graph, an <math>s-t</math> path can be found in the residue graph tracing the edge <math>s\rightarrow A\rightarrow B\rightarrow t</math> with the flow of two units. After augmenting the path on both graphs, the flow graph and the residue graph look like the Figure 9.		In the residue graph, an <math>s-t</math> path can be found in the residue graph tracing the edge <math>s\rightarrow A\rightarrow B\rightarrow t</math> with the flow of two units. After augmenting the path on both graphs, the flow graph and the residue graph look like the Figure 9.

Zz: /* Ford–Fulkerson Algorithm */

2020-12-13T03:54:26Z

Ford–Fulkerson Algorithm

← Older revision		Revision as of 23:54, 12 December 2020
Line 362:		Line 362:
	The flow graph <math>G</math> and residue graph<math>G_{f}</math> at the initial phase is depicted in Figure 8, where the number of each edge in the flow graph is the flow units on the edge, whereas it is the updated edge capacity in the residue graph.		The flow graph <math>G</math> and residue graph<math>G_{f}</math> at the initial phase is depicted in Figure 8, where the number of each edge in the flow graph is the flow units on the edge, whereas it is the updated edge capacity in the residue graph.

	[~~pic8~~]		[[File:Phase 1.png\|thumb\|Figure 8: Flow graph and residue graph at the first phase]]

	In the residue graph, an <math>s-t</math> path can be found in the residue graph tracing the edge <math>s\rightarrow A\rightarrow B\rightarrow t</math> with the flow of two units. After augmenting the path on both graphs, the flow graph and the residue graph look like the Figure 9.		In the residue graph, an <math>s-t</math> path can be found in the residue graph tracing the edge <math>s\rightarrow A\rightarrow B\rightarrow t</math> with the flow of two units. After augmenting the path on both graphs, the flow graph and the residue graph look like the Figure 9.

	[~~pic9~~]		[[File:Phase 2.png\|thumb\|Figure 9: Flow graph and residue graph after updating with the first s,t-path]]

	At this stage, there is still <math>s,t</math>-path in the residue graph <math>s\rightarrow B\rightarrow A\rightarrow t</math> with a flow of one unit. After augmenting the path on both graphs, the flow graph and the residue graph look like the Figure 10.		At this stage, there is still <math>s,t</math>-path in the residue graph <math>s\rightarrow B\rightarrow A\rightarrow t</math> with a flow of one unit. After augmenting the path on both graphs, the flow graph and the residue graph look like the Figure 10.

	[~~pic10~~]		[[File:Phase 3.png\|thumb\|Figure 10: Flow graph and residue graph after augmenting with the second s,t-path]]

	At this stage, there is no more <math>s,t</math>-path in the residue graph, so FFA terminates and the maximum flow can be read from the flow graph as 3 units.		At this stage, there is no more <math>s,t</math>-path in the residue graph, so FFA terminates and the maximum flow can be read from the flow graph as 3 units.

Wei45039: /* Ford–Fulkerson Algorithm */

2020-12-13T03:47:55Z

Ford–Fulkerson Algorithm

← Older revision		Revision as of 23:47, 12 December 2020
Line 347:		Line 347:
	The steps of FFA are as below. <sup>[10]</sup> Essentially, the method repeatedly finds a path with positive flow in the residue graph, and updates the flow graph and residue graph until <math>s</math> and <math>t</math> become disjoint in the residue graph.		The steps of FFA are as below. <sup>[10]</sup> Essentially, the method repeatedly finds a path with positive flow in the residue graph, and updates the flow graph and residue graph until <math>s</math> and <math>t</math> become disjoint in the residue graph.

	1.Set <math>f(e) = 0, \forall e\in E</math>in <math>G</math>, and create a copy as <math>G_{f}</math>.		1. Set <math>f(e) = 0, \forall e\in E</math>in <math>G</math>, and create a copy as <math>G_{f}</math>.

	2.While there is still a <math>s, t</math> path <math>p</math> in <math>G_{f}</math>:		2. While there is still a <math>s, t</math> path <math>p</math> in <math>G_{f}</math>:

	a.Find <math>c_{f}(p) = min(c_{f}(e):e\in p)</math>		a. Find <math>c_{f}(p) = min(c_{f}(e):e\in p)</math>

	b.For each edge <math>e\in p</math>:		b. For each edge <math>e\in p</math>:

	bi.<math>f(e) = f(e) + c_{f}(p)</math> if <math>e\in E</math> in <math>G</math>, <math>f(e) = f(e) - c_{f}(p)</math> if <math>e'\in E</math> in <math>G</math>		bi. <math>f(e) = f(e) + c_{f}(p)</math> if <math>e\in E</math> in <math>G</math>, <math>f(e) = f(e) - c_{f}(p)</math> if <math>e'\in E</math> in <math>G</math>

	bii.<math>c(e)= c(e) - c_{f}(p),c(e')= c(e') + c_{f}(p)</math> in <math> G_{f}</math>		bii. <math>c(e)= c(e) - c_{f}(p),c(e')= c(e') + c_{f}(p)</math> in <math> G_{f}</math>

	An example of running the FFA is as below.		An example of running the FFA is as below.

Wei45039: /* Ford–Fulkerson Algorithm */

2020-12-13T03:47:18Z

Ford–Fulkerson Algorithm

← Older revision		Revision as of 23:47, 12 December 2020
Line 351:		Line 351:
	2.While there is still a <math>s, t</math> path <math>p</math> in <math>G_{f}</math>:		2.While there is still a <math>s, t</math> path <math>p</math> in <math>G_{f}</math>:

	~~&nbsp~~ a.Find <math>c_{f}(p) = min(c_{f}(e):e\in p)</math>		a.Find <math>c_{f}(p) = min(c_{f}(e):e\in p)</math>

	~~&nbsp~~ b.For each edge <math>e\in p</math>:		b.For each edge <math>e\in p</math>:

	~~&nbsp &nbsp i~~.<math>f(e) = f(e) + c_{f}(p)</math> if <math>e\in E</math> in <math>G</math>, <math>f(e) = f(e) - c_{f}(p)</math> if <math>e'\in E</math> in <math>G</math>		bi.<math>f(e) = f(e) + c_{f}(p)</math> if <math>e\in E</math> in <math>G</math>, <math>f(e) = f(e) - c_{f}(p)</math> if <math>e'\in E</math> in <math>G</math>

	~~&nbsp &nbsp ii~~.<math>c(e)= c(e) - c_{f}(p),c(e')= c(e') + c_{f}(p)</math> in <math> G_{f}</math>		bii.<math>c(e)= c(e) - c_{f}(p),c(e')= c(e') + c_{f}(p)</math> in <math> G_{f}</math>

	An example of running the FFA is as below.		An example of running the FFA is as below.

Wei45039: /* Ford–Fulkerson Algorithm */

2020-12-13T03:46:25Z

Ford–Fulkerson Algorithm

← Older revision		Revision as of 23:46, 12 December 2020
Line 351:		Line 351:
	2.While there is still a <math>s, t</math> path <math>p</math> in <math>G_{f}</math>:		2.While there is still a <math>s, t</math> path <math>p</math> in <math>G_{f}</math>:

	a.Find <math>c_{f}(p) = min(c_{f}(e):e\in p)</math>		&nbsp a.Find <math>c_{f}(p) = min(c_{f}(e):e\in p)</math>

	b.For each edge <math>e\in p</math>:		&nbsp b.For each edge <math>e\in p</math>:

	i.<math>f(e) = f(e) + c_{f}(p)</math> if <math>e\in E</math> in <math>G</math>, <math>f(e) = f(e) - c_{f}(p)</math> if <math>e'\in E</math> in <math>G</math>		&nbsp &nbsp i.<math>f(e) = f(e) + c_{f}(p)</math> if <math>e\in E</math> in <math>G</math>, <math>f(e) = f(e) - c_{f}(p)</math> if <math>e'\in E</math> in <math>G</math>

	ii.<math>c(e)= c(e) - c_{f}(p),c(e')= c(e') + c_{f}(p)</math> in <math> G_{f}</math>		&nbsp &nbsp ii.<math>c(e)= c(e) - c_{f}(p),c(e')= c(e') + c_{f}(p)</math> in <math> G_{f}</math>

	An example of running the FFA is as below.		An example of running the FFA is as below.
Line 364:		Line 364:
	[pic8]		[pic8]

	In the residue graph, an <math>s-t</math> path can be found in the residue graph tracing the edge <math>s->A->B->t</math> with the flow of two units. After augmenting the path on both graphs, the flow graph and the residue graph look like the Figure 9.		In the residue graph, an <math>s-t</math> path can be found in the residue graph tracing the edge <math>s\rightarrow A\rightarrow B\rightarrow t</math> with the flow of two units. After augmenting the path on both graphs, the flow graph and the residue graph look like the Figure 9.

	[pic9]		[pic9]

	At this stage, there is still <math>s,t</math>-path in the residue graph <math>s->B->A->t</math> with a flow of one unit. After augmenting the path on both graphs, the flow graph and the residue graph look like the Figure 10.		At this stage, there is still <math>s,t</math>-path in the residue graph <math>s\rightarrow B\rightarrow A\rightarrow t</math> with a flow of one unit. After augmenting the path on both graphs, the flow graph and the residue graph look like the Figure 10.

	[pic10]		[pic10]

Wei45039: /* Ford–Fulkerson Algorithm */

2020-12-13T03:44:12Z

Ford–Fulkerson Algorithm

← Older revision		Revision as of 23:44, 12 December 2020
Line 338:		Line 338:

	FFA introduces the concept of residue graph based on the original graph <math>G</math> to allow backtracking, or pushing backward on edges that are already carrying flow.<sup>[9]</sup> The residue graph <math>G_{f} </math>is defined as the following:		FFA introduces the concept of residue graph based on the original graph <math>G</math> to allow backtracking, or pushing backward on edges that are already carrying flow.<sup>[9]</sup> The residue graph <math>G_{f} </math>is defined as the following:

	1. <math>G_{f}</math>has exactly the same node set as <math>G</math>.		1. <math>G_{f}</math>has exactly the same node set as <math>G</math>.

	2. For each edge <math>e = (u,v)</math>with a nonnegative flow <math> f( e)</math> in <math>G</math>, <math>G_{f}</math>has the edge e with the capacity <math>c(e)_{f} = c_{e} - f(e)</math>, and also <math>G_f</math> has the edge <math>e' = (v,u)</math> with the capacity <math>c(e')_{f} = f(e)</math>.		2. For each edge <math>e = (u,v)</math>with a nonnegative flow <math> f( e)</math> in <math>G</math>, <math>G_{f}</math>has the edge e with the capacity <math>c(e)_{f} = c_{e} - f(e)</math>, and also <math>G_f</math> has the edge <math>e' = (v,u)</math> with the capacity <math>c(e')_{f} = f(e)</math>.

	Note that initially, the <math>G_{f} </math> is identical to <math>G</math> since there is no flow present in <math>G</math>.		Note that initially, the <math>G_{f} </math> is identical to <math>G</math> since there is no flow present in <math>G</math>.

	The steps of FFA are as below. <sup>[10]</sup> Essentially, the method repeatedly finds a path with positive flow in the residue graph, and updates the flow graph and residue graph until <math>s</math> and <math>t</math> become disjoint in the residue graph.		The steps of FFA are as below. <sup>[10]</sup> Essentially, the method repeatedly finds a path with positive flow in the residue graph, and updates the flow graph and residue graph until <math>s</math> and <math>t</math> become disjoint in the residue graph.

	1.Set <math>f(e) = 0, \forall e\in E</math>in <math>G</math>, and create a copy as <math>G_{f}</math>.		1.Set <math>f(e) = 0, \forall e\in E</math>in <math>G</math>, and create a copy as <math>G_{f}</math>.

	2.While there is still a <math>s, t</math> path <math>p</math> in <math>G_{f}</math>:		2.While there is still a <math>s, t</math> path <math>p</math> in <math>G_{f}</math>:
	a.Find <math>c_{f}(p) = min(c_{f}(e):e\in p)</math>
	b.For each edge <math>e\in p</math>:		a.Find <math>c_{f}(p) = min(c_{f}(e):e\in p)</math>
	i.<math>f(e) = f(e) + c_{f}(p)</math> if <math>e\in E</math> in <math>G</math>, <math>f(e) = f(e) - c_{f}(p)</math> if <math>e'\in E</math> in <math>G</math>
	ii.<math>c(e)= c(e) - c_{f}(p),c(e')= c(e') + c_{f}(p)</math> in <math> G_{f}</math>		b.For each edge <math>e\in p</math>:

			i.<math>f(e) = f(e) + c_{f}(p)</math> if <math>e\in E</math> in <math>G</math>, <math>f(e) = f(e) - c_{f}(p)</math> if <math>e'\in E</math> in <math>G</math>

			ii.<math>c(e)= c(e) - c_{f}(p),c(e')= c(e') + c_{f}(p)</math> in <math> G_{f}</math>

	An example of running the FFA is as below.		An example of running the FFA is as below.
Line 355:		Line 364:
	[pic8]		[pic8]

	In the residue graph, an s-t path can be found in the residue graph tracing the edge s->A->B->t with the flow of two units. After augmenting the path on both graphs, the flow graph and the residue graph look like the Figure 9.		In the residue graph, an <math>s-t</math> path can be found in the residue graph tracing the edge <math>s->A->B->t</math> with the flow of two units. After augmenting the path on both graphs, the flow graph and the residue graph look like the Figure 9.

	[pic9]		[pic9]

	At this stage, there is still s,t-path in the residue graph s->B->A->t with a flow of one unit. After augmenting the path on both graphs, the flow graph and the residue graph look like the Figure 10.		At this stage, there is still <math>s,t</math>-path in the residue graph <math>s->B->A->t</math> with a flow of one unit. After augmenting the path on both graphs, the flow graph and the residue graph look like the Figure 10.

	[pic10]		[pic10]

	At this stage, there is no more s,t-path in the residue graph, so FFA terminates and the maximum flow can be read from the flow graph as 3 units.		At this stage, there is no more <math>s,t</math>-path in the residue graph, so FFA terminates and the maximum flow can be read from the flow graph as 3 units.

	== Numerical Example and Solution ==		== Numerical Example and Solution ==

Wei45039: /* Ford–Fulkerson Algorithm */

2020-12-13T03:41:21Z

Ford–Fulkerson Algorithm

← Older revision		Revision as of 23:41, 12 December 2020
Line 340:		Line 340:
	1. <math>G_{f}</math>has exactly the same node set as <math>G</math>.		1. <math>G_{f}</math>has exactly the same node set as <math>G</math>.
	2. For each edge <math>e = (u,v)</math>with a nonnegative flow <math> f( e)</math> in <math>G</math>, <math>G_{f}</math>has the edge e with the capacity <math>c(e)_{f} = c_{e} - f(e)</math>, and also <math>G_f</math> has the edge <math>e' = (v,u)</math> with the capacity <math>c(e')_{f} = f(e)</math>.		2. For each edge <math>e = (u,v)</math>with a nonnegative flow <math> f( e)</math> in <math>G</math>, <math>G_{f}</math>has the edge e with the capacity <math>c(e)_{f} = c_{e} - f(e)</math>, and also <math>G_f</math> has the edge <math>e' = (v,u)</math> with the capacity <math>c(e')_{f} = f(e)</math>.
	Note that initially, the <math>G_{f} </math> is identical to G since there is no flow present in <math>G</math>.		Note that initially, the <math>G_{f} </math> is identical to <math>G</math> since there is no flow present in <math>G</math>.

	The steps of FFA are as below. <sup>[10]</sup> Essentially, the method repeatedly finds a path with positive flow in the residue graph, and updates the flow graph and residue graph until s and t become disjoint in the residue graph.		The steps of FFA are as below. <sup>[10]</sup> Essentially, the method repeatedly finds a path with positive flow in the residue graph, and updates the flow graph and residue graph until <math>s</math> and <math>t</math> become disjoint in the residue graph.
	1.Set <math>f~~\left~~ ( e ~~\right~~ ) = 0, \forall e\in E\: in\: G</math> , and create a copy as <math>G_{f}</math>.		1.Set <math>f(e) = 0, \forall e\in E</math>in <math>G</math>, and create a copy as <math>G_{f}</math>.
	2.While there is still a s, t path p in <math>G_{f}</math>:		2.While there is still a <math>s, t</math> path <math>p</math> in <math>G_{f}</math>:
	a.Find <math>c_{f}~~\left~~ ( p ~~\right~~ ) = min~~\left~~ ( c_{f}~~\left~~ ( e ~~\right~~ )\, :\, e\in p ~~\right~~ )</math>		a.Find <math>c_{f}(p) = min(c_{f}(e):e\in p)</math>
	b.For each edge <math>e\in p</math>:		b.For each edge <math>e\in p</math>:
	i.<math>f~~\left~~ ( e ~~\right~~ ) = f~~\left~~ ( e ~~\right~~ ) + c_{f}~~\left~~ ( p ~~\right~~ )\: if\: e\in E in G, f~~\left~~ ( e ~~\right~~ ) = f~~\left~~ ( e ~~\right~~ ) - c_{f}~~\left~~ ( p ~~\right~~ )\: if\: e'\in E\: in\: G</math>		i.<math>f(e) = f(e) + c_{f}(p)</math> if <math>e\in E</math> in <math>G</math>, <math>f(e) = f(e) - c_{f}(p)</math> if <math>e'\in E</math> in <math>G</math>
	ii.<math>c~~\left~~ ( e ~~\right~~ )= c~~\left~~ ( e ~~\right~~ ) - c_{f}~~\left~~ ( p ~~\right~~ ),\:c~~\left~~ ( e' ~~\right~~ )= c~~\left~~ ( e' ~~\right~~ ) + c_{f}~~\left~~ ( p ~~\right~~ )\: in\: G_{f}</math>		ii.<math>c(e)= c(e) - c_{f}(p),c(e')= c(e') + c_{f}(p)</math> in <math> G_{f}</math>

	An example of running the FFA is as below.		An example of running the FFA is as below.

Wei45039: /* Ford–Fulkerson Algorithm */

2020-12-13T03:36:09Z

Ford–Fulkerson Algorithm

← Older revision		Revision as of 23:36, 12 December 2020
Line 337:		Line 337:
	Typically, FFA is applied to flow networks with only one source node s and one sink node t. In addition, the capacity conditions and the conservation conditions, which are two properties defining the flow, must be satisfied.<sup>[9]</sup> The capacity conditions require that each edge carry a flow that is no more than its capacity, or <math>0\leq f(e)\leq c_{e},\forall e\in E</math>, where function f returns the flow on a certain edge. The conservation conditions require all nodes except the source and the sink to have a net flow of 0, or ,<math>\sum_{e~into~v}f(v)= \sum_{e~out~of~v}f(v),\forall v\in V-{s,t} </math>.		Typically, FFA is applied to flow networks with only one source node s and one sink node t. In addition, the capacity conditions and the conservation conditions, which are two properties defining the flow, must be satisfied.<sup>[9]</sup> The capacity conditions require that each edge carry a flow that is no more than its capacity, or <math>0\leq f(e)\leq c_{e},\forall e\in E</math>, where function f returns the flow on a certain edge. The conservation conditions require all nodes except the source and the sink to have a net flow of 0, or ,<math>\sum_{e~into~v}f(v)= \sum_{e~out~of~v}f(v),\forall v\in V-{s,t} </math>.

	FFA introduces the concept of residue graph based on the original graph G to allow backtracking, or pushing backward on edges that are already carrying flow.<sup>[9]</sup> The residue graph <math>G_{f} </math>is defined as the following:		FFA introduces the concept of residue graph based on the original graph <math>G</math> to allow backtracking, or pushing backward on edges that are already carrying flow.<sup>[9]</sup> The residue graph <math>G_{f} </math>is defined as the following:
	1. <math>G_{f}</math>has exactly the same node set as G.		1. <math>G_{f}</math>has exactly the same node set as <math>G</math>.
	2. For each edge <math>e = ~~\left~~ ( v~~,u \right~~ )</math>with a nonnegative flow <math> f~~\left~~ ( e ~~\right~~ )</math> in G, <math>G_{f}</math>has the edge e with the capacity <math>c~~\left~~ ( e ~~\right~~ )_{f} = c_{e} - f~~\left~~ ( e ~~\right~~ )</math>, and also Gf has the edge <math>e' = ~~\left~~ ( v,u ~~\right~~ )</math> with the capacity <math>c~~\left~~ ( e' ~~\right~~ )_{f} = f~~\left~~ ( e ~~\right~~ )</math>.		2. For each edge <math>e = (u,v)</math>with a nonnegative flow <math> f( e)</math> in <math>G</math>, <math>G_{f}</math>has the edge e with the capacity <math>c(e)_{f} = c_{e} - f(e)</math>, and also <math>G_f</math> has the edge <math>e' = (v,u)</math> with the capacity <math>c(e')_{f} = f(e)</math>.
	Note that initially, the <math>G_{f} </math> is identical to G since there is no flow present in <math>G</math>.		Note that initially, the <math>G_{f} </math> is identical to G since there is no flow present in <math>G</math>.