FordFulkersonAlgorithm.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace FlowForge;

public class FordFulkersonAlgorithm
{
    public enum SearchStrategy
    {
        BreadthFirstSearch,
        DepthFirstSearch
    }
    
    private readonly FlowGraph _flowGraph;

    public FordFulkersonAlgorithm(FlowGraph flowGraph)
    {
        _flowGraph = flowGraph;
    }

    public double Run(string sourceId, string targetId, SearchStrategy strategy=SearchStrategy.BreadthFirstSearch)
    {
        // get source and target nodes
        FlowNode? source = _flowGraph.GetVertexById(sourceId);
        FlowNode? target = _flowGraph.GetVertexById(targetId);

        if (source == null || target == null)
            throw new ArgumentException("Invalid source or target node!");

        double maxFlow = 0.0;
        var pathFlow = new Dictionary<FlowEdge, double>();


        var allEdges = _flowGraph.GetEdges();
        foreach (var edge in allEdges)
        {
            edge.Residual = edge.MaxFlow;
        }
        
        Console.WriteLine("Start of Ford-Fulkerson Algorithm...");

        // execute as long as there is an augmenting path
        while (FindAugmentingPath(source, target, pathFlow, strategy))
        {
            PrintOrderedPath(pathFlow);
            
            // calculate bottleneck in augmenting path
            double pathMinFlow = double.MaxValue;
            foreach (var edge in pathFlow.Keys)
            {
                pathMinFlow = Math.Min(pathMinFlow, pathFlow[edge]);
            }
            Console.WriteLine($"Bottleneck (minimum flow in path): {pathMinFlow}");

            // add flow along the augmenting path
            foreach (var edge in pathFlow.Keys)
            {
                edge.Residual -= pathMinFlow;
                Console.WriteLine($"Updating forward edge {edge.Source.Id} -> {edge.Target.Id}, New Residual: {edge.Residual}");


                // check if backwards edge exists
                FlowEdge? reverseEdge;
                if (!_flowGraph.Graph.TryGetEdge(edge.Target, edge.Source, out reverseEdge))
                {
                    // create a backwards edge if it doesn't exist
                    reverseEdge = new FlowEdge(edge.Target, edge.Source, edge.MaxFlow);

                    reverseEdge.Residual = 0;
                    reverseEdge.IsBackwards = true;
                    
                    _flowGraph.Graph.AddEdge(reverseEdge);
                    
                    Console.WriteLine($"Creating reverse edge {reverseEdge.Source.Id} -> {reverseEdge.Target.Id}");
                }

                if (reverseEdge != null)
                {
                    reverseEdge.Residual += pathMinFlow;
                    
                    Console.WriteLine($"Updating reverse edge {reverseEdge.Source.Id} -> {reverseEdge.Target.Id}, New Residual: {reverseEdge.Residual}");
                }
            }

            // add to total flow
            maxFlow += pathMinFlow;
            Console.WriteLine($"Current max flow: {maxFlow}\n");
        }

        Console.WriteLine("No Augmenting Path found anymore!\n");

        Console.WriteLine($"Max flow found: {maxFlow}\n");
        // return maximum flow after no augmenting paths were found anymore
        return maxFlow;
    }
    
    private bool FindAugmentingPath(FlowNode source, FlowNode target, Dictionary<FlowEdge, double> pathFlow, SearchStrategy strategy)
    {
        // parent map to walk back path
        var parentMap = new Dictionary<FlowNode, FlowEdge>();
        
        // Choose the appropriate data structure based on the strategy
        IEnumerable<FlowNode> nodesToVisit;
        if (strategy == SearchStrategy.BreadthFirstSearch)
        {
            var queue = new Queue<FlowNode>();
            queue.Enqueue(source);
            nodesToVisit = queue;
        }
        else
        {
            var stack = new Stack<FlowNode>();
            stack.Push(source);
            nodesToVisit = stack;
        }
        
        // map to store visited nodes
        var visited = new HashSet<FlowNode> {source};

        while (nodesToVisit.Any())
        {
            var current = strategy == SearchStrategy.BreadthFirstSearch ? ((Queue<FlowNode>)nodesToVisit).Dequeue() : ((Stack<FlowNode>)nodesToVisit).Pop();

            Console.WriteLine("Current: " + current);
            var outEdges = _flowGraph.Graph.OutEdges(current).ToList();
            
            List<FlowEdge> sortedOutEdges;
            if (strategy == SearchStrategy.BreadthFirstSearch)
            {
                sortedOutEdges = outEdges.OrderBy(edge => int.Parse(edge.Target.Id)).ToList();
            }
            else
            {
                sortedOutEdges = outEdges.OrderByDescending(edge => int.Parse(edge.Target.Id)).ToList();
            }
            
            // go through all outgoing edges
            foreach (FlowEdge currentEdge in sortedOutEdges)
            {
                if (currentEdge.Residual <= 0 || visited.Contains(currentEdge.Target)) continue;
                
                visited.Add(currentEdge.Target);
                parentMap.Add(currentEdge.Target, currentEdge);
                
                // if we reached the target node
                if (currentEdge.Target.Equals(target))
                {
                    BuildAugmentingPath(source, target, parentMap, pathFlow);
                    return true;
                }
                
                // search further
                if (strategy == SearchStrategy.BreadthFirstSearch)
                {
                    ((Queue<FlowNode>)nodesToVisit).Enqueue(currentEdge.Target);
                }
                else
                {
                    ((Stack<FlowNode>)nodesToVisit).Push(currentEdge.Target);
                }
            }
        }
        
        return false;
    }
    
    private static void BuildAugmentingPath(FlowNode source, FlowNode target, Dictionary<FlowNode, FlowEdge> parentMap, Dictionary<FlowEdge, double> pathFlow)
    {
        FlowNode currentNode = target;
        pathFlow.Clear();

        while (currentNode != source)
        {
            FlowEdge pathEdge = parentMap[currentNode];
            pathFlow[pathEdge] = pathEdge.Residual;
            currentNode = pathEdge.Source;
        }
    }
    
    public static void PrintOrderedPath(Dictionary<FlowEdge, double> pathFlow)
    {
        Console.WriteLine("Augmenting Path found:");
        
        // Step 1: Find the starting edge
        FlowEdge startEdge = pathFlow.Keys
            .First(edge => !pathFlow.Keys.Any(e => e.Target.Id == edge.Source.Id));

        // Step 2: Follow the path from start to end
        List<FlowEdge> orderedPath = new List<FlowEdge> { startEdge };
        while (true)
        {
            var currentEdge = orderedPath.Last();
            var nextEdge = pathFlow.Keys.FirstOrDefault(edge => edge.Source.Id == currentEdge.Target.Id);
            
            if (nextEdge == null) break; // End of path reached
            orderedPath.Add(nextEdge);
        }

        // Step 3: Output the ordered path
        foreach (var edge in orderedPath)
        {
            Console.WriteLine($"{edge.Source.Id} -> {edge.Target.Id}, Residual Capacity: {pathFlow[edge]}");
        }
    }
}