Skip to content
Snippets Groups Projects
Select Git revision
  • ce1229757b71c72e29f9d2ec8a36465cf8c71014
  • master default protected
2 results

WorstCaseSearch.cs

Blame
  • WorstCaseSearch.cs 4.76 KiB
    using System;
    using System.Collections.Generic;
    using System.Linq;
    
    namespace FlowForge;
    
    public class WorstCaseSearch
    {
        public bool FindAugmentingPathWithEdge(FlowGraph flowGraph, FlowNode source, FlowNode target, FlowEdge requiredEdge, Dictionary<FlowEdge, double> pathFlow)
        {
            Console.WriteLine($"Searching for augmenting path that includes edge {requiredEdge.Source.Id} -> {requiredEdge.Target.Id}");
    
            // Determine if the required edge is valid in either direction
            FlowEdge? validEdge = null;
            bool isReversed = false;
    
            if (requiredEdge.Residual > 0)
            {
                validEdge = requiredEdge;
            }
            else if (flowGraph.Graph.TryGetEdge(requiredEdge.Target, requiredEdge.Source, out validEdge))
            {
                if (validEdge.Residual > 0)
                {
                    isReversed = true;
                }
                else
                {
                    validEdge = null;
                }
            }
            else
            {
                validEdge = null;
            }
    
            if (validEdge == null)
            {
                Console.WriteLine("No valid residual capacity on the required edge in either direction.");
                return FindAugmentingPath(flowGraph, source, target, pathFlow);
            }
    
            // Phase 1: Find a path from source to the starting node of the valid edge
            var phase1Path = new Dictionary<FlowEdge, double>();
            var phase1Success = FindAugmentingPath(flowGraph, source, isReversed ? validEdge.Target : validEdge.Source, phase1Path);
    
            if (!phase1Success)
            {
                Console.WriteLine("No path found from source to the required edge.");
                return FindAugmentingPath(flowGraph, source, target, pathFlow);
            }
    
            // Phase 2: Find a path from the ending node of the valid edge to the target
            var phase2Path = new Dictionary<FlowEdge, double>();
            var phase2Success = FindAugmentingPath(flowGraph, isReversed ? validEdge.Source : validEdge.Target, target, phase2Path);
    
            if (!phase2Success)
            {
                Console.WriteLine("No path found from the required edge to the target.");
                return FindAugmentingPath(flowGraph, source, target, pathFlow);
            }
    
            // Combine the results
            pathFlow.Clear();
            foreach (var kvp in phase1Path)
            {
                pathFlow[kvp.Key] = kvp.Value;
            }
            pathFlow[validEdge] = validEdge.Residual; // Include the required edge
            foreach (var kvp in phase2Path)