simplecyclebasis.java

化学图形处理软件

			}
			
			if (isEssential) {
				result.add((SimpleCycle)cycles.get(i));
			}
			
		}
		
		return result;
	}
	
	
	public Map relevantCycles() {
		Map result = new HashMap();
		
		boolean[][] a = getCycleEdgeIncidenceMatrix();
		
		boolean[][] ai = inverseBinaryMatrix(a, cycles.size());
		
		for (int i=0; i<cycles.size(); i++) {
			
			// Construct kernel vector u from a column of the inverse of a
			boolean[] u = new boolean[edgeList.size()];
			for (int j=0; j<cycles.size(); j++) {
				u[j] = ai[j][i];
			}
			
			// Construct auxiliary graph gu
			AuxiliaryGraph gu = new AuxiliaryGraph(graph, u);
			
			Iterator vertexIterator = graph.vertexSet().iterator();
			while (vertexIterator.hasNext()) {
				Object vertex = vertexIterator.next();
				
				Collection incidentEdges = graph.edgesOf(vertex);
				
				// check if the vertex is incident to an edge with u[edge] == 1
				boolean shouldSearchCycle = false;
				
				for (Iterator it = incidentEdges.iterator(); it.hasNext();) {
					Edge edge = (Edge) it.next();
					int index = getEdgeIndex(edge);
					if (u[index]) {
						shouldSearchCycle = true;
						break;
					}
				}
				
				if (shouldSearchCycle) {
					
					Object auxVertex0 = gu.auxVertex0(vertex);
					Object auxVertex1 = gu.auxVertex1(vertex);
					
					// Search for shortest paths
					
					for (Iterator minPaths = new MinimalPathIterator(gu, auxVertex0, auxVertex1); minPaths.hasNext();) {
						List auxPath = (List) minPaths.next();
						List edgesOfNewCycle = new ArrayList(auxPath.size());
						
						Iterator edgeIterator = auxPath.iterator();
						while (edgeIterator.hasNext()) {
							Edge auxEdge = (Edge) edgeIterator.next();
							
							// Get the edge corresponding to the aux. edge
							Edge e = (Edge) gu.edge(auxEdge);
							
							edgesOfNewCycle.add(e);
							
						}
						
						
						SimpleCycle cycle = new SimpleCycle(graph, edgesOfNewCycle);
						
						if (cycle.weight() > ((SimpleCycle)cycles.get(i)).weight()) {
							break;
						}
						
						result.put(cycle, (SimpleCycle)cycles.get(i));
					}
					
				}
				
			}
		}
		
		return result;
	}
	
	
	public List equivalenceClasses() {
		int[] weight = weightVector();
		
		Object[] cyclesArray = (Object[]) cycles.toArray();
		Arrays.sort(cyclesArray, new Comparator() {
			public int compare(Object o1, Object o2) {
				return (int) (((SimpleCycle)o1).weight() - ((SimpleCycle)o2).weight());
			}
		});
		
		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, edgeList, 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, edgeList, 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, edgeList, 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();
	}
	
	private HashMap createEdgeIndexMap(List edgeList) {
		HashMap map = new HashMap();
		for (int i=0; i<edgeList.size(); i++) {
			map.put(edgeList.get(i), new Integer(i));
		}
		return map;
	}
	
	private int getEdgeIndex(Edge edge) {
		return ((Integer) edgeIndexMap.get(edge)).intValue();
	}
	
	private class AuxiliaryGraph extends SimpleGraph {
		
        private static final long serialVersionUID = 857337988734567429L;
        // graph to aux. graph
		HashMap vertexMap0 = new HashMap();
		HashMap vertexMap1 = new HashMap();
		
		HashMap auxVertexMap = new HashMap();
		
		// aux. edge to edge
		Map auxEdgeMap = new HashMap();
		
		Graph g;
		boolean[] u;
		
		AuxiliaryGraph(Graph graph, boolean[] u) {
			g = graph;
			this.u = u;
		}
		
		public List edgesOf( Object auxVertex ) {
			
			Object vertex = auxVertexMap.get(auxVertex);
			
			for (Iterator edgeIterator = g.edgesOf(vertex).iterator(); edgeIterator.hasNext();) {
				Edge edge = (Edge) edgeIterator.next();
				int j = getEdgeIndex(edge);
				
				Object vertex1 = edge.getSource();
				Object vertex2 = edge.getTarget();
				
				if (u[j]) {
					Object vertex1u = auxVertex0(vertex1);
					Object vertex2u = auxVertex1(vertex2);
					Edge auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
					
					vertex1u = auxVertex1(vertex1);
					vertex2u = auxVertex0(vertex2);
					auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
				} else {
					Object vertex1u = auxVertex0(vertex1);
					Object vertex2u = auxVertex0(vertex2);
					Edge auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
					
					vertex1u = auxVertex1(vertex1);
					vertex2u = auxVertex1(vertex2);
					auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
				}
				
			}
			
			return super.edgesOf(auxVertex);
		}
		
		Object auxVertex0(Object vertex) {
			if (vertexMap0.get(vertex) == null) {
				Object newVertex0 = vertex + "-0";
				vertexMap0.put(vertex, newVertex0);
				addVertex(newVertex0);
				auxVertexMap.put(newVertex0, vertex);
				return newVertex0;
			}
			return vertexMap0.get(vertex);
		}
		
		Object auxVertex1(Object vertex) {
			if (vertexMap1.get(vertex) == null) {
				Object newVertex1 = vertex + "-1";
				vertexMap1.put(vertex, newVertex1);
				addVertex(newVertex1);
				auxVertexMap.put(newVertex1, vertex);
				return newVertex1;
			}
			return vertexMap1.get(vertex);
		}
		
		Object edge(Object auxEdge) {
			return auxEdgeMap.get(auxEdge);
		}
	}
	
	private class AuxiliaryGraph2 extends SimpleGraph {
		
        private static final long serialVersionUID = 5930876716644738726L;
        
        // graph to aux. graph
		private HashMap vertexMap00 = new HashMap();
		private HashMap vertexMap01 = new HashMap();
		private HashMap vertexMap10 = new HashMap();
		private HashMap vertexMap11 = new HashMap();
		
		private HashMap auxVertexMap = new HashMap();
		
		// aux. edge to edge
		private Map auxEdgeMap = new HashMap();
		
		private Graph g;
		private boolean[] ui;
		private boolean[] uj;
		
		AuxiliaryGraph2(Graph graph, List edgeList, boolean[] ui, boolean[] uj) {
			g = graph;
			this.ui = ui;
			this.uj = uj;
		}
		
		Object auxVertex00(Object vertex) {
			if (vertexMap00.get(vertex) == null) {
				Object newVertex = vertex + "-00";
				vertexMap00.put(vertex, newVertex);
				addVertex(newVertex);
				auxVertexMap.put(newVertex, vertex);
				return newVertex;
			}
			return vertexMap00.get(vertex);
		}
		
		Object auxVertex01(Object vertex) {
			if (vertexMap01.get(vertex) == null) {
				Object newVertex = vertex + "-01";
				vertexMap01.put(vertex, newVertex);
				addVertex(newVertex);
				auxVertexMap.put(newVertex, vertex);
				return newVertex;
			}
			return vertexMap01.get(vertex);
		}
		
		Object auxVertex10(Object vertex) {
			if (vertexMap10.get(vertex) == null) {
				Object newVertex = vertex + "-10";
				vertexMap10.put(vertex, newVertex);
				addVertex(newVertex);
				auxVertexMap.put(newVertex, vertex);
				return newVertex;
			}
			return vertexMap10.get(vertex);
		}
		
		Object auxVertex11(Object vertex) {
			if (vertexMap11.get(vertex) == null) {
				Object newVertex = vertex + "-11";
				vertexMap11.put(vertex, newVertex);
				addVertex(newVertex);
				auxVertexMap.put(newVertex, vertex);
				return newVertex;
			}
			return vertexMap11.get(vertex);
		}
		
		public List edgesOf( Object auxVertex ) {
			
			Object vertex = auxVertexMap.get(auxVertex);
			
			for (Iterator edgeIterator = g.edgesOf(vertex).iterator(); edgeIterator.hasNext();) {
				Edge edge = (Edge) edgeIterator.next();
				int k = getEdgeIndex(edge);
				
				Object vertex1 = edge.getSource();
				Object vertex2 = edge.getTarget();				
				
				if (!ui[k] && !uj[k]) {
					Object vertex1u = auxVertex00(vertex1);
					Object vertex2u = auxVertex00(vertex2);
					Edge auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
					
					vertex1u = auxVertex01(vertex1);
					vertex2u = auxVertex01(vertex2);
					auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
					
					vertex1u = auxVertex10(vertex1);
					vertex2u = auxVertex10(vertex2);
					auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
					
					vertex1u = auxVertex11(vertex1);
					vertex2u = auxVertex11(vertex2);
					auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
				} else if (ui[k] && !uj[k]) {
					Object vertex1u = auxVertex00(vertex1);
					Object vertex2u = auxVertex10(vertex2);
					Edge auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
					
					vertex1u = auxVertex01(vertex1);
					vertex2u = auxVertex11(vertex2);
					auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
					
					vertex1u = auxVertex10(vertex1);
					vertex2u = auxVertex00(vertex2);
					auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
					
					vertex1u = auxVertex11(vertex1);
					vertex2u = auxVertex01(vertex2);
					auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
				} else if (!ui[k] && uj[k]) {
					Object vertex1u = auxVertex00(vertex1);
					Object vertex2u = auxVertex01(vertex2);
					Edge auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
					
					vertex1u = auxVertex01(vertex1);
					vertex2u = auxVertex00(vertex2);
					auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
					
					vertex1u = auxVertex10(vertex1);
					vertex2u = auxVertex11(vertex2);
					auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
					
					vertex1u = auxVertex11(vertex1);
					vertex2u = auxVertex10(vertex2);
					auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
				} else if (ui[k] && uj[k]) {
					Object vertex1u = auxVertex00(vertex1);
					Object vertex2u = auxVertex11(vertex2);
					Edge auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
					
					vertex1u = auxVertex01(vertex1);
					vertex2u = auxVertex10(vertex2);
					auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
					
					vertex1u = auxVertex10(vertex1);
					vertex2u = auxVertex01(vertex2);
					auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
					
					vertex1u = auxVertex11(vertex1);
					vertex2u = auxVertex00(vertex2);
					auxEdge = addEdge(vertex1u, vertex2u);
					auxEdgeMap.put(auxEdge, edge);
				}
			}
			return super.edgesOf(auxVertex);
		}
	}
}