package uk.ac.aber.cs31920.assignment.implementation.solvers;

import uk.ac.aber.cs31920.assignment.implementation.datastructures.Edge;
import uk.ac.aber.cs31920.assignment.implementation.datastructures.GraphNode;
import uk.ac.aber.cs31920.assignment.implementation.datastructures.MaxFlowGraph;

import java.util.*;

/**
 * A solver for Max Flow using Edmonds-Karp algorithm but that only solves problems where
 * all edges have a capacity of 1.
 */
public class Cap1EdmondsKarpMaxFlowSolver {
    public static List<Edge> Solve(MaxFlowGraph fullGraph){
        List<Edge> flow = new LinkedList<>();
        while (true){
            ResidualCalculator.calculateResidualNetwork(fullGraph.source, flow, fullGraph);
            List<GraphNode> residualPath = BreadthFirstSearchRunner.run(fullGraph.source, fullGraph.sink, GraphNode::getResidualNetworkChildren);
            if (residualPath == null)
                return flow;

            for (int i = 0; i < residualPath.size()-1; i++) {
                Edge currentEdge = new Edge(residualPath.get(i), residualPath.get(i+1));
                if (isBackwardsEdge(currentEdge))
                    flow.remove(currentEdge);
                else
                    flow.add(currentEdge);
            }
        }

    }

    private static boolean isBackwardsEdge(Edge edge){
        return edge.child.getNetworkChildren().contains(edge.parent);
    }
}