DotNet Reference

DotNet Reference

SimpleMaxFlowProgram.cs
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 // [START program]
15 using System;
16 using Google.OrTools.Graph;
17 
19 {
20  static void Main()
21  {
22  // [START data]
23  // Define three parallel arrays: start_nodes, end_nodes, and the capacities
24  // between each pair. For instance, the arc from node 0 to node 1 has a
25  // capacity of 20.
26  // From Taha's 'Introduction to Operations Research',
27  // example 6.4-2.
28  int[] startNodes = {0, 0, 0, 1, 1, 2, 2, 3, 3};
29  int[] endNodes = {1, 2, 3, 2, 4, 3, 4, 2, 4};
30  int[] capacities = {20, 30, 10, 40, 30, 10, 20, 5, 20};
31  // [END data]
32 
33  // [START constraints]
34  // Instantiate a SimpleMaxFlow solver.
35  MaxFlow maxFlow = new MaxFlow();
36 
37  // Add each arc.
38  for (int i = 0; i < startNodes.Length; ++i)
39  {
40  int arc = maxFlow.AddArcWithCapacity(startNodes[i], endNodes[i],
41  capacities[i]);
42  if (arc != i) throw new Exception("Internal error");
43  }
44  // [END constraints]
45 
46  // [START solve]
47  // Find the maximum flow between node 0 and node 4.
48  MaxFlow.Status solveStatus = maxFlow.Solve(0, 4);
49  // [END solve]
50 
51  // [START print_solution]
52  if (solveStatus == MaxFlow.Status.OPTIMAL)
53  {
54  Console.WriteLine("Max. flow: " + maxFlow.OptimalFlow());
55  Console.WriteLine("");
56  Console.WriteLine(" Arc Flow / Capacity");
57  for (int i = 0; i < maxFlow.NumArcs(); ++i)
58  {
59  Console.WriteLine(maxFlow.Tail(i) + " -> " +
60  maxFlow.Head(i) + " " +
61  string.Format("{0,3}", maxFlow.Flow(i)) + " / " +
62  string.Format("{0,3}", maxFlow.Capacity(i)));
63  }
64  }
65  else
66  {
67  Console.WriteLine("Solving the max flow problem failed. Solver status: " +
68  solveStatus);
69  }
70  // [END print_solution]
71  }
72 }
73 // [END program]
MaxFlow.Status Solve(int source, int sink)
Definition: MaxFlow.cs:80
int AddArcWithCapacity(int tail, int head, long capacity)
Definition: MaxFlow.cs:50
long Flow(int arc)
Definition: MaxFlow.cs:90
Definition: MaxFlow.cs:13
int NumArcs()
Definition: MaxFlow.cs:60
Status
Definition: MaxFlow.cs:95
int Head(int arc)
Definition: MaxFlow.cs:70
long OptimalFlow()
Definition: MaxFlow.cs:85
long Capacity(int arc)
Definition: MaxFlow.cs:75
int Tail(int arc)
Definition: MaxFlow.cs:65