package A08_GraphZusammenhängend;

import basisAlgorithmen.Graph;
import basisAlgorithmen.WeightedEdge;

import java.util.LinkedHashSet;
import java.util.Set;
import java.util.Stack;

public class ConnectedComponents {

    /**
     * Retourniert die Anzahl der zusammenhängenden Komponenten eines Graphen
     *
     * @param g zu prüfender Graph
     * @return Anzahl der Komponenten
     */
    public int getNumberOfComponents(Graph g) {

        Stack<WeightedEdge> edges = new Stack<WeightedEdge>();
        Set<Integer> visited = new LinkedHashSet<Integer>();
        int counter = 0;
        int startVertex = 0;

        while (visited.size() <= g.numVertices()) {
            while (visited.contains(startVertex)) {
                startVertex++;
            }
            if (startVertex >= g.numVertices())
                break;
                visited.add(startVertex);
            for (WeightedEdge edge : g.getEdges(startVertex)) {
                edges.push(edge);
            }
            while (edges.size() != 0) {
                WeightedEdge currentEdge;

                    currentEdge = edges.pop();


                for (WeightedEdge edge : g.getEdges(currentEdge.to_vertex)) {
                    if (!visited.contains(edge.to_vertex))
                        edges.push(edge);
                }

                visited.add(currentEdge.from_vertex);
                visited.add(currentEdge.to_vertex);
            }
            counter++;
        }
        return counter;
    }

}