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 double 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
            return 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();
        }
    }
}