package org.omnetpp.common.util;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

/**
 * Graph related utilities.
 *
 * @author tomi
 */
public class GraphUtils {

    public interface GraphModel<N> {
        List<N> getAllNodes();
        List<N> getNextNodes(N node);
    }

    public static <N> Collection<Set<N>> getStronglyConnectedComponents(GraphModel<N> graph) {
        TarjanSCCFinder<N> finder = new TarjanSCCFinder<N>(graph);
        return finder.computeSCCs();
    }

    public static <N> Collection<Set<N>> getCycles(GraphModel<N> graph) {
        List<Set<N>> cycles = new ArrayList<Set<N>>();
        for (Set<N> component : getStronglyConnectedComponents(graph)) {
            if (component.size() > 1)
                cycles.add(component);
            else {
                N node = component.iterator().next();
                boolean circular = graph.getNextNodes(node).contains(node);
                if (circular)
                    cycles.add(component);
            }
        }

        return cycles;
    }

    // see "http://en.wikipedia.org/wiki/Tarjan%E2%80%99s_strongly_connected_components_algorithm"
    static class TarjanSCCFinder<N> {

        class Wrapper<Node> {
            Node node;
            int index;
            int lowlink;
            public Wrapper(Node node) {
                this.node = node;
                index = UNDEFINED;
                lowlink = UNDEFINED;
            }
        }

        private static final int UNDEFINED = -1;

        GraphModel<N> graph;
        int index;
        Stack<Wrapper<N>> S = new Stack<Wrapper<N>>();
        Map<N, Wrapper<N>> nodes = new HashMap<N,Wrapper<N>>();
        List<Set<N>> result = new ArrayList<Set<N>>();

        public TarjanSCCFinder(GraphModel<N> graph) {
            this.graph = graph;
        }

        public List<Set<N>> computeSCCs() {
            result.clear();
            nodes.clear();
            for (N node : graph.getAllNodes())
                nodes.put(node, new Wrapper<N>(node));

            index = 0;
            S.clear();
            for (Wrapper<N> v : nodes.values()) {
                if (v.index == UNDEFINED)
                    tarjan(v);
            }

            return result;
        }

        private List<Wrapper<N>> getNextNodes(Wrapper<N> node) {
            List<Wrapper<N>> result = new ArrayList<Wrapper<N>>();
            for (N node1 : graph.getNextNodes(node.node))
                result.add(nodes.get(node1));
            return result;
        }

        private void tarjan(Wrapper<N> v) {
            v.index = index;
            v.lowlink = index;
            index++;
            S.push(v);

            for (Wrapper<N> v1 : getNextNodes(v)) {
                if (v1.index == UNDEFINED) {
                    tarjan(v1);
                    v.lowlink = Math.min(v.lowlink, v1.lowlink);
                }
                else if (S.contains(v1)) {
                    v.lowlink = Math.min(v.lowlink, v1.index);
                }
            }

            if (v.lowlink == v.index) {
                Wrapper<N> v1;
                Set<N> scc = new HashSet<N>();
                do {
                    v1 = S.pop();
                    scc.add(v1.node);
                } while (!v1.equals(v));
                result.add(scc);
            }
        }
    }
}
