// GraphTea Project: http://github.com/graphtheorysoftware/GraphTea
// Copyright (C) 2012 Graph Theory Software Foundation: http://GraphTheorySoftware.com
// Copyright (C) 2008 Mathematical Science Department of Sharif University of Technology
// Distributed under the terms of the GNU Lesser General Public License (LGPL): http://www.gnu.org/licenses/

package graphtea.extensions.algorithms.vertexcover;

import graphtea.graph.graph.Edge;
import graphtea.graph.graph.GraphModel;
import graphtea.graph.graph.Vertex;
import graphtea.library.exceptions.InvalidGraphException;
import graphtea.library.exceptions.InvalidVertexException;
import graphtea.platform.core.BlackBoard;
import graphtea.plugins.algorithmanimator.core.GraphAlgorithm;
import graphtea.plugins.algorithmanimator.extension.AlgorithmExtension;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * @author Soroush Sabet
 */
public class AppVertexCover extends GraphAlgorithm implements AlgorithmExtension {
    public AppVertexCover(BlackBoard blackBoard) {
        super(blackBoard);
    }
    /**
     * @throws InvalidGraphException The graph is invalid
     * @throws InvalidVertexException The vertex is invalid
     */
    @Override
    public void doAlgorithm() {
        step("Start of the algorithm.") ;
        GraphModel graph = graphData.getGraph();
        GraphModel gCopy = graph.getCopy();
        List<Vertex> C = new ArrayList<>();
        List<Vertex> D = new ArrayList<>();
        List<Vertex> marked = new ArrayList<>();
        //cleat marks
        for (Edge edge : graph.getEdges())
            edge.setMark(false);
        Edge e;

        Iterator<Edge> iet = graph.edgeIterator();
        while (iet.hasNext()) {
            e = iet.next();
            if (!(C.contains(e.source) || C.contains(e.target))) {
                e.setMark(true);
                step("");
                C.add(e.source);
                C.add(e.target);
                            for (Edge edge : graph.edges(e.source)) {
                                gCopy.removeEdge(edge);
                            }

                            for (Edge edge : gCopy.edges(e.target)) {
                                gCopy.removeEdge(edge);
                            }
                            iet = gCopy.edgeIterator();
            }
        }

        for (Vertex v : C) {
//            int j = v.getId();
//            for (Vertex u : graph){
//                if (u.getId() == j){
//                    dispatchEvent(new VertexEvent(graph, v, VertexEvent.EventType.MARK));
            v.setMark(true);
            step("");
            D.add(v);
//                }
//            }
        }
    }

    @Override
    public String getName() {
        return "Vertex Cover";
    }

    @Override
    public String getDescription() {
        return "Vertex Cover";
    }
}