1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using Graph = NetworkFlow.Graph;
namespace Program
{
class Program
{
static void Main(string[] args)
{
// attempt to read file from command line args, otherwise asks for a file
FileInfo inputFile = (args.Length > 0) ? new FileInfo(args[0]) : ReadFileName();
// attempt to get source and terminal nodes from command line args
string source = (args.Length >= 2) ? args[1] : default(string);
string terminal = (args.Length >= 3) ? args[2] : default(string);
if (!inputFile.Exists)
{
Console.WriteLine($"Failed to open {inputFile}: File does not exist.");
return;
}
// read file into graph
Graph graph = ReadFile(inputFile.FullName);
// verify command line source and terminal values or gets new values from the user
(int s, int t) = ReadSourceAndTerminal(graph, source, terminal);
// call maxFlow
double maxFlow = graph.MaxFlow(s, t);
Console.WriteLine($"The max flow is {maxFlow}");
}
public static (int s, int t) ReadSourceAndTerminal(Graph graph, string source, string terminal)
{
int s, t;
// retries until it succeeds
while (true)
{
// try to parse supplied values
bool isSetSource = int.TryParse(source, out s);
bool isSetTerminal = int.TryParse(terminal, out t);
// validates the values are ints and the graph contains the corresponding node
if (!(isSetSource && graph.Nodes.ContainsKey(s)))
{
if (source != default(string))
Console.WriteLine($"Invalid Source Node: {source}");
Console.Write($"Enter the Source Node: ");
// asks for a new value
source = Console.ReadLine();
}
// validates the values are ints and the graph contains the corresponding node
if (!(isSetTerminal && graph.Nodes.ContainsKey(t)))
{
if (terminal != default(string))
Console.WriteLine($"Invalid Terminal Node: {terminal}");
Console.Write($"Enter the Terminal Node: ");
// asks for a new value
terminal = Console.ReadLine();
}
// if everything is correct then we can return
if (isSetSource && isSetTerminal && graph.Nodes.ContainsKey(s) && graph.Nodes.ContainsKey(t))
break;
}
return (s, t);
}
public static FileInfo ReadFileName()
{
string filePath;
// continues to ask for a valid filepath until obtained
while (true)
{
Console.Write("Enter a path to a points file: ");
filePath = Console.ReadLine();
if (String.IsNullOrEmpty(filePath))
Console.WriteLine("File path cannot be empty!");
else if (!System.IO.File.Exists(filePath))
Console.WriteLine($"{filePath} does not exist.");
else
break;
}
FileInfo file = new FileInfo(filePath);
return file;
}
public static Graph ReadFile(string file)
{
// create default Graph object
Graph graph = new Graph();
// Read in graph file
foreach (string line in File.ReadLines(file))
{
// each file line is a Node with optional edges
// line format:
// vertex:int optional[ connected-vertex:int edge-weight:double optional[..] ]
List<string> vals = line.Split(' ').ToList();
int u, v;
double weight;
int.TryParse(vals[0], out u);
graph.AddNode(u);
for (int i = 1; i < vals.Count - 1; i += 2)
{
// AddEdge(int u, int v, double weight)
int.TryParse(vals[i], out v);
double.TryParse(vals[i + 1], out weight);
graph.AddEdge(u, v, weight);
}
}
// return object when done
return graph;
}
}
}
|