test_class.declarator: g
test_class.modifier: private static
test_class.original_string: private static SimpleGraph      g;
test_class.type: SimpleGraph
test_class.var_name: g
test_class.declarator: basis
test_class.modifier: private static
test_class.original_string: private static SimpleCycleBasis basis;
test_class.type: SimpleCycleBasis
test_class.var_name: basis
test_class.file: legacy/src/test/java/org/openscience/cdk/ringsearch/cyclebasis/SimpleCycleBasisTest.java
test_class.identifier: SimpleCycleBasisTest
test_class.superclass: extends CDKTestCase
test_case.body: @Test
      public void testEquivalenceClasses() {
          Assert.assertEquals(4, basis.equivalenceClasses().size());
      }
test_case.class_method_signature: SimpleCycleBasisTest.testEquivalenceClasses()
test_case.full_signature: @Test public void testEquivalenceClasses()
test_case.identifier: testEquivalenceClasses
test_case.invocations: assertEquals size equivalenceClasses
test_case.modifiers: @Test public
test_case.parameters: ()
test_case.return: void
test_case.signature: void testEquivalenceClasses()
focal_class.declarator: edgeList
focal_class.modifier: private
focal_class.original_string: private List              edgeList;
focal_class.type: List
focal_class.var_name: edgeList
focal_class.declarator: cycles
focal_class.modifier: private
focal_class.original_string: private List<SimpleCycle> cycles;
focal_class.type: List<SimpleCycle>
focal_class.var_name: cycles
focal_class.declarator: graph
focal_class.modifier: private
focal_class.original_string: private UndirectedGraph   graph;
focal_class.type: UndirectedGraph
focal_class.var_name: graph
focal_class.declarator: isMinimized = false
focal_class.modifier: private
focal_class.original_string: private boolean           isMinimized = false;
focal_class.type: boolean
focal_class.var_name: isMinimized
focal_class.declarator: edgeIndexMap
focal_class.modifier: private
focal_class.original_string: private HashMap           edgeIndexMap;
focal_class.type: HashMap
focal_class.var_name: edgeIndexMap
focal_class.file: legacy/src/main/java/org/openscience/cdk/ringsearch/cyclebasis/SimpleCycleBasis.java
focal_class.identifier: SimpleCycleBasis
focal_class.class_method_signature: SimpleCycleBasis.SimpleCycleBasis(List<SimpleCycle> cycles, List edgeList, UndirectedGraph graph)
focal_class.full_signature: public  SimpleCycleBasis(List<SimpleCycle> cycles, List edgeList, UndirectedGraph graph)
focal_class.identifier: SimpleCycleBasis
focal_class.modifiers: public
focal_class.parameters: (List<SimpleCycle> cycles, List edgeList, UndirectedGraph graph)
focal_class.signature:  SimpleCycleBasis(List<SimpleCycle> cycles, List edgeList, UndirectedGraph graph)
focal_class.class_method_signature: SimpleCycleBasis.SimpleCycleBasis(UndirectedGraph graph)
focal_class.full_signature: public  SimpleCycleBasis(UndirectedGraph graph)
focal_class.identifier: SimpleCycleBasis
focal_class.modifiers: public
focal_class.parameters: (UndirectedGraph graph)
focal_class.signature:  SimpleCycleBasis(UndirectedGraph graph)
focal_class.class_method_signature: SimpleCycleBasis.createMinimumCycleBasis()
focal_class.full_signature: private void createMinimumCycleBasis()
focal_class.identifier: createMinimumCycleBasis
focal_class.modifiers: private
focal_class.parameters: ()
focal_class.return: void
focal_class.signature: void createMinimumCycleBasis()
focal_class.class_method_signature: SimpleCycleBasis.getCycleEdgeIncidenceMatrix()
focal_class.full_signature:  boolean[][] getCycleEdgeIncidenceMatrix()
focal_class.identifier: getCycleEdgeIncidenceMatrix
focal_class.parameters: ()
focal_class.return: boolean[][]
focal_class.signature: boolean[][] getCycleEdgeIncidenceMatrix()
focal_class.class_method_signature: SimpleCycleBasis.getCycleEdgeIncidenceMatrix(Object[] cycleArray)
focal_class.full_signature:  boolean[][] getCycleEdgeIncidenceMatrix(Object[] cycleArray)
focal_class.identifier: getCycleEdgeIncidenceMatrix
focal_class.parameters: (Object[] cycleArray)
focal_class.return: boolean[][]
focal_class.signature: boolean[][] getCycleEdgeIncidenceMatrix(Object[] cycleArray)
focal_class.class_method_signature: SimpleCycleBasis.minimize(int startIndex)
focal_class.full_signature: private void minimize(int startIndex)
focal_class.identifier: minimize
focal_class.modifiers: private
focal_class.parameters: (int startIndex)
focal_class.return: void
focal_class.signature: void minimize(int startIndex)
focal_class.class_method_signature: SimpleCycleBasis.constructKernelVector(int size, boolean[][] a, int i)
focal_class.full_signature: static boolean[] constructKernelVector(int size, boolean[][] a, int i)
focal_class.identifier: constructKernelVector
focal_class.modifiers: static
focal_class.parameters: (int size, boolean[][] a, int i)
focal_class.return: boolean[]
focal_class.signature: boolean[] constructKernelVector(int size, boolean[][] a, int i)
focal_class.class_method_signature: SimpleCycleBasis.weightVector()
focal_class.full_signature: public int[] weightVector()
focal_class.identifier: weightVector
focal_class.modifiers: public
focal_class.parameters: ()
focal_class.return: int[]
focal_class.signature: int[] weightVector()
focal_class.class_method_signature: SimpleCycleBasis.edges()
focal_class.full_signature: public List edges()
focal_class.identifier: edges
focal_class.modifiers: public
focal_class.parameters: ()
focal_class.return: List
focal_class.signature: List edges()
focal_class.class_method_signature: SimpleCycleBasis.cycles()
focal_class.full_signature: public List cycles()
focal_class.identifier: cycles
focal_class.modifiers: public
focal_class.parameters: ()
focal_class.return: List
focal_class.signature: List cycles()
focal_class.class_method_signature: SimpleCycleBasis.inverseBinaryMatrix(boolean[][] m, int n)
focal_class.full_signature: static boolean[][] inverseBinaryMatrix(boolean[][] m, int n)
focal_class.identifier: inverseBinaryMatrix
focal_class.modifiers: static
focal_class.parameters: (boolean[][] m, int n)
focal_class.return: boolean[][]
focal_class.signature: boolean[][] inverseBinaryMatrix(boolean[][] m, int n)
focal_class.class_method_signature: SimpleCycleBasis.essentialCycles()
focal_class.full_signature: public Collection essentialCycles()
focal_class.identifier: essentialCycles
focal_class.modifiers: public
focal_class.parameters: ()
focal_class.return: Collection
focal_class.signature: Collection essentialCycles()
focal_class.class_method_signature: SimpleCycleBasis.relevantCycles()
focal_class.full_signature: public Map relevantCycles()
focal_class.identifier: relevantCycles
focal_class.modifiers: public
focal_class.parameters: ()
focal_class.return: Map
focal_class.signature: Map relevantCycles()
focal_class.class_method_signature: SimpleCycleBasis.equivalenceClasses()
focal_class.full_signature: public List equivalenceClasses()
focal_class.identifier: equivalenceClasses
focal_class.modifiers: public
focal_class.parameters: ()
focal_class.return: List
focal_class.signature: List equivalenceClasses()
focal_class.class_method_signature: SimpleCycleBasis.createEdgeIndexMap(List edgeList)
focal_class.full_signature: private HashMap createEdgeIndexMap(List edgeList)
focal_class.identifier: createEdgeIndexMap
focal_class.modifiers: private
focal_class.parameters: (List edgeList)
focal_class.return: HashMap
focal_class.signature: HashMap createEdgeIndexMap(List edgeList)
focal_class.class_method_signature: SimpleCycleBasis.getEdgeIndex(Edge edge)
focal_class.full_signature: private int getEdgeIndex(Edge edge)
focal_class.identifier: getEdgeIndex
focal_class.modifiers: private
focal_class.parameters: (Edge edge)
focal_class.return: int
focal_class.signature: int getEdgeIndex(Edge edge)
focal_class.class_method_signature: SimpleCycleBasis.printIncidenceMatrix()
focal_class.full_signature: public void printIncidenceMatrix()
focal_class.identifier: printIncidenceMatrix
focal_class.modifiers: public
focal_class.parameters: ()
focal_class.return: void
focal_class.signature: void printIncidenceMatrix()
focal_method.body: 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();
      }
focal_method.class_method_signature: SimpleCycleBasis.equivalenceClasses()
focal_method.full_signature: public List equivalenceClasses()
focal_method.identifier: equivalenceClasses
focal_method.invocations: weightVector toArray size sort weight weight weight weight essentialCycles size getCycleEdgeIncidenceMatrix inverseBinaryMatrix addAllVertices contains contains pathExists iterator vertexSet hasNext next edgesOf iterator hasNext next getEdgeIndex auxVertex00 auxVertex11 findPathBetween size addEdge contains contains pathExists weight iterator vertexSet hasNext next auxVertex00 auxVertex11 findPathBetween size iterator vertexSet hasNext next auxVertex00 auxVertex11 findPathBetween size addEdge connectedSets
focal_method.modifiers: public
focal_method.parameters: ()
focal_method.return: List
focal_method.signature: List equivalenceClasses()