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.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * A solver for a Maximum Matching problem, essentially runs a Cap1EdmondsKarpMaxFlowSolver
 * then removes any edges involving the source and sink from the given solution.
 */
public class MaxMatchingSolver {
    public static List<Edge> Solve(MaxFlowGraph fullGraph){
        List<Edge> initialResult = Cap1EdmondsKarpMaxFlowSolver.Solve(fullGraph);
        List<Edge> finalResult = new ArrayList<>();
        List<GraphNode> allNodes = new LinkedList<GraphNode>(fullGraph.fullGraph); // new copy since we'll edit it

        for (Edge edge : initialResult){
            if (!edge.child.isSink() && !edge.parent.isSource())
                finalResult.add(edge);
            allNodes.remove(edge.child);
            allNodes.remove(edge.parent);
        }

        if (!allNodes.isEmpty())
            return null; // problem cannot be solved, a node doesnt have a connection

        return finalResult;
    }
}