class SimpleCycleBasis {

    public List equivalenceClasses() {
        int[] weight = weightVector();

        SimpleCycle[] cyclesArray = cycles.toArray(new SimpleCycle[cycles.size()]);
        Arrays.sort(cyclesArray, new Comparator<SimpleCycle>() {

            @Override
            public int compare(SimpleCycle o1, SimpleCycle o2) {
                if (o1.weight() > o2.weight()) return +1;
                if (o1.weight() < o2.weight()) return -1;
                return 0;
            }
        });

        Collection essentialCycles = essentialCycles();

        boolean[][] u = new boolean[cyclesArray.length][edgeList.size()];

        boolean[][] a = getCycleEdgeIncidenceMatrix(cyclesArray);
        boolean[][] ai = inverseBinaryMatrix(a, cyclesArray.length);

        for (int i = 0; i < cyclesArray.length; i++) {
            for (int j = 0; j < cyclesArray.length; j++) {
                u[i][j] = ai[j][i];
            }
        }

        UndirectedGraph h = new SimpleGraph();
        h.addAllVertices(cycles);

        ConnectivityInspector connectivityInspector = new ConnectivityInspector(h);

        int left = 0;
        for (int right = 0; right < weight.length; right++) {
            if ((right < weight.length - 1) && (weight[right + 1] == weight[right])) continue;

            // cyclesArray[left] to cyclesArray[right] have same weight

            // First test (compute pre-classes):
            // Check if there is a cycle that can replace a[i] as well as a[j] in a basis
            // This is done by finding a cycle C with <C,u[i]>=1 and <C,u[j]>=1

            for (int i = left; i <= right; i++) {
                if (essentialCycles.contains((SimpleCycle) cyclesArray[i])) continue;

                for (int j = i + 1; j <= right; j++) {
                    if (essentialCycles.contains((SimpleCycle) cyclesArray[j])) continue;

                    // check if cyclesArray[i] and cyclesArray[j] are already in the same class
                    if (connectivityInspector.pathExists(cyclesArray[i], cyclesArray[j])) continue;

                    boolean sameClass = false;

                    AuxiliaryGraph2 auxGraph = new AuxiliaryGraph2(graph, u[i], u[j]);

                    for (Iterator it = graph.vertexSet().iterator(); it.hasNext();) {
                        Object vertex = it.next();

                        // check if the vertex is incident to an edge with u[edge] == 1
                        boolean shouldSearchCycle = false;

                        Collection incidentEdges = graph.edgesOf(vertex);

                        Iterator edgeIterator = incidentEdges.iterator();
                        while (edgeIterator.hasNext()) {
                            Edge edge = (Edge) edgeIterator.next();
                            int index = getEdgeIndex(edge);
                            if (u[i][index] || u[j][index]) {
                                shouldSearchCycle = true;
                                break;
                            }
                        }

                        if (shouldSearchCycle) {

                            Object auxVertex00 = auxGraph.auxVertex00(vertex);
                            Object auxVertex11 = auxGraph.auxVertex11(vertex);

                            List auxPath = BFSShortestPath.findPathBetween(auxGraph, auxVertex00, auxVertex11);

                            double pathWeight = auxPath.size();

                            if (pathWeight == weight[left]) {
                                sameClass = true;
                                break;
                            }
                        }
                    }

                    if (sameClass) {
                        h.addEdge(cyclesArray[i], cyclesArray[j]);
                    }
                }
            }

            // Second test (compute equivalence classes):
            // Check if there are two cycle Ci, Cj that can replace a[i], a[j]
            // and have a common cycle a[k] in their basis representation
            // This is done by finding a cycle a[k] with <u[k],u[i]>=1 and <u[k],u[j]>=1

            for (int i = left; i <= right; i++) {
                if (essentialCycles.contains((SimpleCycle) cyclesArray[i])) continue;

                for (int j = i + 1; j <= right; j++) {
                    if (essentialCycles.contains((SimpleCycle) cyclesArray[j])) continue;

                    // check if cyclesArray[i] and cyclesArray[j] are already in the same class
                    if (connectivityInspector.pathExists(cyclesArray[i], cyclesArray[j])) continue;

                    boolean sameClass = false;

                    for (int k = 0; ((SimpleCycle) cyclesArray[k]).weight() < weight[left]; k++) {

                        AuxiliaryGraph2 auxGraph = new AuxiliaryGraph2(graph, u[i], u[k]);

                        boolean shortestPathFound = false;
                        for (Iterator it = graph.vertexSet().iterator(); it.hasNext();) {
                            Object vertex = it.next();

                            Object auxVertex00 = auxGraph.auxVertex00(vertex);
                            Object auxVertex11 = auxGraph.auxVertex11(vertex);

                            List auxPath = BFSShortestPath.findPathBetween(auxGraph, auxVertex00, auxVertex11);

                            double pathWeight = auxPath.size();

                            if (pathWeight == weight[left]) {
                                shortestPathFound = true;
                                break;
                            }
                        }

                        if (!shortestPathFound) continue;

                        auxGraph = new AuxiliaryGraph2(graph, u[j], u[k]);

                        for (Iterator it = graph.vertexSet().iterator(); it.hasNext();) {
                            Object vertex = it.next();

                            Object auxVertex00 = auxGraph.auxVertex00(vertex);
                            Object auxVertex11 = auxGraph.auxVertex11(vertex);

                            List auxPath = BFSShortestPath.findPathBetween(auxGraph, auxVertex00, auxVertex11);

                            double pathWeight = auxPath.size();

                            if (pathWeight == weight[left]) {
                                sameClass = true;
                                break;
                            }
                        }

                        if (sameClass) break;
                    }

                    if (sameClass) {
                        h.addEdge(cyclesArray[i], cyclesArray[j]);
                    }
                }
            }

            left = right + 1;
        }

        return connectivityInspector.connectedSets();
    }

    public  SimpleCycleBasis(List<SimpleCycle> cycles, List edgeList, UndirectedGraph graph);
    public  SimpleCycleBasis(UndirectedGraph graph);

}