completed project

21 files changed, 261 insertions, 10 deletions

diff --git a/src/NetworkFlow/Graph.cs b/src/NetworkFlow/Graph.cs
new file mode 100644
index 0000000..d98539a
--- /dev/null
+++ b/src/NetworkFlow/Graph.cs
@@ -0,0 +1,146 @@
+using System.Collections.Generic;
+using System.Collections;
+using System;
+
+namespace NetworkFlow
+{
+    using Path = List<int>;
+    using Nodes = Dictionary<int, Node>;
+    public class Graph
+    {
+
+        Dictionary<int, Node> _nodes;
+
+        public Nodes Nodes { get => _nodes; set => _nodes = value; }
+
+        public Graph()
+        {
+            Nodes = new Nodes();
+        }
+
+        /// <summary>
+        /// Indexer; Retrieves the node with node.Id of <c>id</c> 
+        /// </summary>
+        public Node this[int id]
+        {
+            get { return _nodes[id]; }
+            set { _nodes[id] = value; }
+        }
+
+        /// <summary>
+        /// Adds a node with an id of <c>id</c> 
+        /// </summary>
+        public void AddNode(int id)
+        {
+            if (!this.Nodes.ContainsKey(id))
+                this.Nodes.Add(id, new(id));
+        }
+
+        /// <summary>
+        /// Adds an edge to node <c>u</c> pointing to <c>v</c> with a <c>capacity</c> 
+        /// </summary>
+        public void AddEdge(int u, int v, double capacity)
+        {
+            AddNode(u);
+            this[u].Edges.Add(v, capacity);
+        }
+
+        /// <summary>
+        /// Decrements the edge between nodes <c>u</c>  and <c>v</c> by <c>capacity</c> 
+        /// </summary>
+        public void ChangeEdge(int u, int v, double capacity)
+            => this[u].Edges[v] -= capacity;
+
+        /// <summary>
+        /// Finds the maximum flow possible from the <c>source</c> 
+        /// node to the <c>terminal</c> node.
+        /// </summary>
+        public void MaxFlow(int source, int terminal)
+        {
+            double maxFlow = 0;
+            Path path = null;
+            // run bfs on graph (returns a path)
+            // until there are no paths remaining to the termination node
+            while (true)
+            {
+                double capacity = int.MaxValue;
+                path = BFS(source, terminal);
+
+                // get the min edge weight (capacity) on that path
+                for (int i = 0; i < path.Count - 1; i++)
+                    capacity = Math.Min(capacity, this[path[i]].Edges[path[i + 1]]);
+
+                // run changeEdge on each edge in the path, subtracting the capacity
+                for (int i = 0; i < path.Count - 1; i++)
+                    this.ChangeEdge(path[i], path[i + 1], capacity);
+
+                // exit early
+                if (path.Count == 0)
+                    break;
+
+                // update maxFlow with capacity
+                maxFlow += capacity;
+
+                // output the current progress
+                Console.WriteLine($"The augmenting path is {String.Join(",", path)} capacity = {capacity}");
+            }
+
+            // output when completed
+            Console.WriteLine($"The max flow is {maxFlow}");
+        }
+
+
+        /// <summary>
+        /// Searches the graph for a path from the <c>source</c> node to the 
+        /// <c>terminal</c> node while respecting edges that have 0 capacity. 
+        /// </summary>
+        public Path BFS(int source, int terminal)
+        {
+            Queue<Path> queue = new();
+            HashSet<int> visited = new();
+
+            // enqueue the source node a path of 1 node
+            queue.Enqueue(new Path { source });
+            while (queue.Count > 0)
+            {
+                var path = queue.Dequeue();
+
+                // get the last node in the path
+                var node = path[path.Count - 1];
+                visited.Add(node);
+
+                // loop through that nodes edges
+                foreach ((int nextNode, double capacity) in this[node].Edges)
+                {
+                    // ignore the edge if the capacity is 0
+                    if (capacity <= 0 || visited.Contains(nextNode))
+                        continue;
+
+                    // enqueue (a copy of) the current path with the child node appended
+                    var nextPath = new Path(path);
+                    nextPath.Add(nextNode);
+                    queue.Enqueue(nextPath);
+
+                    // if we found the terminal node, return its path 
+                    if (nextNode == terminal)
+                        return nextPath;
+                }
+            }
+
+            // return an empty path if a path to terminal node was not found
+            return new();
+        }
+    }
+
+    public struct Node
+    {
+        public int Id { get; set; }
+        public Dictionary<int, double> Edges { get; set; }
+
+        public Node(int id)
+        {
+            Id = id;
+            Edges = new();
+        }
+    }
+}
\ No newline at end of file
diff --git a/src/NetworkFlow/NetworkFlow.cs b/src/NetworkFlow/NetworkFlow.cs
deleted file mode 100644
index df6c513..0000000
--- a/src/NetworkFlow/NetworkFlow.cs
+++ /dev/null
@@ -1,8 +0,0 @@
-using System;
-
-namespace NetworkFlow
-{
-    public class NetworkFlow
-    {
-    }
-}
diff --git a/src/NetworkFlow/bin/Debug/net5.0/NetworkFlow.dll b/src/NetworkFlow/bin/Debug/net5.0/NetworkFlow.dll
index 32dbc27..70f418f 100644
--- a/src/NetworkFlow/bin/Debug/net5.0/NetworkFlow.dll
+++ b/src/NetworkFlow/bin/Debug/net5.0/NetworkFlow.dll
diff --git a/src/NetworkFlow/bin/Debug/net5.0/NetworkFlow.pdb b/src/NetworkFlow/bin/Debug/net5.0/NetworkFlow.pdb
index af52e51..cab380a 100644
--- a/src/NetworkFlow/bin/Debug/net5.0/NetworkFlow.pdb
+++ b/src/NetworkFlow/bin/Debug/net5.0/NetworkFlow.pdb
diff --git a/src/NetworkFlow/bin/Debug/net5.0/ref/NetworkFlow.dll b/src/NetworkFlow/bin/Debug/net5.0/ref/NetworkFlow.dll
index fc632b4..8dc1269 100644
--- a/src/NetworkFlow/bin/Debug/net5.0/ref/NetworkFlow.dll
+++ b/src/NetworkFlow/bin/Debug/net5.0/ref/NetworkFlow.dll
diff --git a/src/NetworkFlow/obj/Debug/net5.0/NetworkFlow.csproj.AssemblyReference.cache b/src/NetworkFlow/obj/Debug/net5.0/NetworkFlow.csproj.AssemblyReference.cache
index ea4ccf7..f5e894a 100644
--- a/src/NetworkFlow/obj/Debug/net5.0/NetworkFlow.csproj.AssemblyReference.cache
+++ b/src/NetworkFlow/obj/Debug/net5.0/NetworkFlow.csproj.AssemblyReference.cache
diff --git a/src/NetworkFlow/obj/Debug/net5.0/NetworkFlow.csproj.CoreCompileInputs.cache b/src/NetworkFlow/obj/Debug/net5.0/NetworkFlow.csproj.CoreCompileInputs.cache
index 5f1250d..1877c1c 100644
--- a/src/NetworkFlow/obj/Debug/net5.0/NetworkFlow.csproj.CoreCompileInputs.cache
+++ b/src/NetworkFlow/obj/Debug/net5.0/NetworkFlow.csproj.CoreCompileInputs.cache
@@ -1 +1 @@
-8db3d10a3258119a31fd03929778a726cec4943e
+9bf59d87b5f792cedb1dddda78b2fc4dd3b00336
diff --git a/src/NetworkFlow/obj/Debug/net5.0/NetworkFlow.dll b/src/NetworkFlow/obj/Debug/net5.0/NetworkFlow.dll
index 32dbc27..70f418f 100644
--- a/src/NetworkFlow/obj/Debug/net5.0/NetworkFlow.dll
+++ b/src/NetworkFlow/obj/Debug/net5.0/NetworkFlow.dll
diff --git a/src/NetworkFlow/obj/Debug/net5.0/NetworkFlow.pdb b/src/NetworkFlow/obj/Debug/net5.0/NetworkFlow.pdb
index af52e51..cab380a 100644
--- a/src/NetworkFlow/obj/Debug/net5.0/NetworkFlow.pdb
+++ b/src/NetworkFlow/obj/Debug/net5.0/NetworkFlow.pdb
diff --git a/src/NetworkFlow/obj/Debug/net5.0/ref/NetworkFlow.dll b/src/NetworkFlow/obj/Debug/net5.0/ref/NetworkFlow.dll
index fc632b4..8dc1269 100644
--- a/src/NetworkFlow/obj/Debug/net5.0/ref/NetworkFlow.dll
+++ b/src/NetworkFlow/obj/Debug/net5.0/ref/NetworkFlow.dll
diff --git a/src/Program/Program.cs b/src/Program/Program.cs
index 426284a..d6d3379 100644
--- a/src/Program/Program.cs
+++ b/src/Program/Program.cs
@@ -1,4 +1,8 @@
 using System;
+using System.Collections.Generic;
+using System.IO;
+using System.Linq;
+using Graph = NetworkFlow.Graph;
 
 namespace Program
 {
@@ -6,7 +10,116 @@ namespace Program
     {
         static void Main(string[] args)
         {
-            Console.WriteLine("Hello World!");
+            // 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
+            graph.MaxFlow(s, t);
+        }
+
+        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;
         }
     }
 }
diff --git a/src/Program/bin/Debug/net5.0/NetworkFlow.dll b/src/Program/bin/Debug/net5.0/NetworkFlow.dll
index 32dbc27..70f418f 100644
--- a/src/Program/bin/Debug/net5.0/NetworkFlow.dll
+++ b/src/Program/bin/Debug/net5.0/NetworkFlow.dll
diff --git a/src/Program/bin/Debug/net5.0/NetworkFlow.pdb b/src/Program/bin/Debug/net5.0/NetworkFlow.pdb
index af52e51..cab380a 100644
--- a/src/Program/bin/Debug/net5.0/NetworkFlow.pdb
+++ b/src/Program/bin/Debug/net5.0/NetworkFlow.pdb
diff --git a/src/Program/bin/Debug/net5.0/Program.dll b/src/Program/bin/Debug/net5.0/Program.dll
index e966d61..f89cebf 100644
--- a/src/Program/bin/Debug/net5.0/Program.dll
+++ b/src/Program/bin/Debug/net5.0/Program.dll
diff --git a/src/Program/bin/Debug/net5.0/Program.pdb b/src/Program/bin/Debug/net5.0/Program.pdb
index 43d2591..149705e 100644
--- a/src/Program/bin/Debug/net5.0/Program.pdb
+++ b/src/Program/bin/Debug/net5.0/Program.pdb
diff --git a/src/Program/bin/Debug/net5.0/ref/Program.dll b/src/Program/bin/Debug/net5.0/ref/Program.dll
index 5ddfe14..0c17e27 100644
--- a/src/Program/bin/Debug/net5.0/ref/Program.dll
+++ b/src/Program/bin/Debug/net5.0/ref/Program.dll
diff --git a/src/Program/obj/Debug/net5.0/Program.assets.cache b/src/Program/obj/Debug/net5.0/Program.assets.cache
index d8aa262..6591bc4 100644
--- a/src/Program/obj/Debug/net5.0/Program.assets.cache
+++ b/src/Program/obj/Debug/net5.0/Program.assets.cache
diff --git a/src/Program/obj/Debug/net5.0/Program.csproj.AssemblyReference.cache b/src/Program/obj/Debug/net5.0/Program.csproj.AssemblyReference.cache
index 460fb12..0a85c42 100644
--- a/src/Program/obj/Debug/net5.0/Program.csproj.AssemblyReference.cache
+++ b/src/Program/obj/Debug/net5.0/Program.csproj.AssemblyReference.cache
diff --git a/src/Program/obj/Debug/net5.0/Program.dll b/src/Program/obj/Debug/net5.0/Program.dll
index e966d61..f89cebf 100644
--- a/src/Program/obj/Debug/net5.0/Program.dll
+++ b/src/Program/obj/Debug/net5.0/Program.dll
diff --git a/src/Program/obj/Debug/net5.0/Program.pdb b/src/Program/obj/Debug/net5.0/Program.pdb
index 43d2591..149705e 100644
--- a/src/Program/obj/Debug/net5.0/Program.pdb
+++ b/src/Program/obj/Debug/net5.0/Program.pdb
diff --git a/src/Program/obj/Debug/net5.0/ref/Program.dll b/src/Program/obj/Debug/net5.0/ref/Program.dll
index 5ddfe14..0c17e27 100644
--- a/src/Program/obj/Debug/net5.0/ref/Program.dll
+++ b/src/Program/obj/Debug/net5.0/ref/Program.dll