package de.develman.mmi.algorithm;

import de.develman.mmi.model.Edge;
import de.develman.mmi.model.Graph;
import de.develman.mmi.model.Vertex;
import javax.inject.Inject;

/**
 * Die Klasse Matching implementiert den Matching Algorithmus zur Berechnung Anzahl an "gematchten" Kanten in einem
 * gerichteten bipartiten Graphen
 *
 * @author Georg Henkel <georg@develman.de>
 */
public class Matching
{
    @Inject
    EdmondsKarp edmondsKarp;

    /**
     * Berechnung der Anzahl an Matchings
     *
     * @param graph Graph
     * @return Liefert die Anzahl der "gematchten" Kanten
     */
    public int countMatching(Graph graph)
    {
        Graph residualGraph = graph.copy();
        Vertex superSource = addSuperSource(residualGraph);
        Vertex superSink = addSuperSink(residualGraph);

        edmondsKarp.calculateMaxFlowGraph(residualGraph, superSource, superSink);
        return extractEdgesWithFlow(graph, residualGraph);
    }

    private int extractEdgesWithFlow(Graph graph, Graph residualGraph)
    {
        int countEdgesWithFlow = 0;
        for (Edge edge : graph.getEdges())
        {
            Vertex source = residualGraph.getVertex(edge.getSource().getKey());
            Vertex sink = residualGraph.getVertex(edge.getSink().getKey());

            Edge residualEdge = residualGraph.getEdge(sink, source);
            if (residualEdge != null)
            {
                countEdgesWithFlow++;
            }
        }

        return countEdgesWithFlow;
    }

    private Vertex addSuperSource(Graph graph)
    {
        Vertex superSource = new Vertex(-1);
        graph.addVertex(superSource);

        graph.getVertices().stream().filter(v -> v.getKey() < graph.getGroupedVerticeCount()).forEach(v ->
        {
            Edge edge = new Edge(superSource, v, 1.0, 0.0);
            graph.addEdge(edge, 0);
        });

        return superSource;
    }

    private Vertex addSuperSink(Graph graph)
    {
        Vertex superSink = new Vertex(-2);
        graph.addVertex(superSink);

        graph.getVertices().stream().filter(v -> v.getKey() >= graph.getGroupedVerticeCount()).forEach(v ->
        {
            Edge edge = new Edge(v, superSink, 1.0, 0.0);
            graph.addEdge(edge, 0);
        });

        return superSink;
    }
}

@@ -802,16 +802,29 @@
 %0A       
+ return (int)
  edmonds
@@ -894,616 +894,8 @@
 k);%0A
-        return extractEdgesWithFlow(graph, residualGraph);%0A    %7D%0A%0A    private int extractEdgesWithFlow(Graph graph, Graph residualGraph)%0A    %7B%0A        int countEdgesWithFlow = 0;%0A        for (Edge edge : graph.getEdges())%0A        %7B%0A            Vertex source = residualGraph.getVertex(edge.getSource().getKey());%0A            Vertex sink = residualGraph.getVertex(edge.getSink().getKey());%0A%0A            Edge residualEdge = residualGraph.getEdge(sink, source);%0A            if (residualEdge != null)%0A            %7B%0A                countEdgesWithFlow++;%0A            %7D%0A        %7D%0A%0A        return countEdgesWithFlow;%0A
     

optimize matching algorithm