@Test @SuppressWarnings("unchecked") public void addEdge() throws NoSuchMethodException, IllegalAccessException, InstantiationException, InvocationTargetException { DirectedAcyclicGraph<String> graph = new DirectedAcyclicGraph<String>(); graph.addEdge(null, null); Constructor constructor = Vertex.class.getDeclaredConstructors()[0]; constructor.setAccessible(true); Vertex<String> helloVertex = (Vertex<String>) constructor.newInstance("hello"); graph.addEdge(helloVertex, null); assertFalse(graph.hasVertex(helloVertex.getValue())); graph.addEdge(null, helloVertex); assertFalse(graph.hasVertex(helloVertex.getValue())); Vertex<String> hello1Vertex = (Vertex<String>) constructor.newInstance("hello1"); graph.addEdge(helloVertex, hello1Vertex); assertFalse(graph.hasVertex(helloVertex.getValue())); assertFalse(graph.hasVertex(hello1Vertex.getValue())); helloVertex = graph.addVertex("hello"); graph.addEdge(helloVertex, hello1Vertex); assertFalse(graph.hasVertex(hello1Vertex.getValue())); hello1Vertex = graph.addVertex("hello1"); graph.addEdge(helloVertex, hello1Vertex); assertTrue(graph.hasEdge(helloVertex, hello1Vertex)); try { graph.addEdge(hello1Vertex, helloVertex); fail("Expected a Graph.CycleException"); } catch (Graph.CycleException gce) { List<Vertex<?>> cycle = gce.getCycle(); assertEquals(3, cycle.size()); assertEquals(helloVertex, cycle.get(0)); assertEquals(hello1Vertex, cycle.get(1)); assertEquals(helloVertex, cycle.get(2)); List<Vertex<?>> path = gce.getPath(); assertEquals(0, path.size()); } Vertex<String> hello2Vertex = graph.addVertex("hello2"); Vertex<String> hello3Vertex = graph.addVertex("hello3"); graph.addEdge(hello1Vertex, hello2Vertex); assertTrue(graph.hasEdge(hello1Vertex, hello2Vertex)); graph.addEdge(hello2Vertex, hello3Vertex); assertTrue(graph.hasEdge(hello2Vertex, hello3Vertex)); try { graph.addEdge(hello3Vertex, hello2Vertex); fail("Expected a Graph.CycleException"); } catch (Graph.CycleException gce) { List<Vertex<?>> cycle = gce.getCycle(); assertEquals(3, cycle.size()); assertEquals(hello2Vertex, cycle.get(0)); assertEquals(hello3Vertex, cycle.get(1)); assertEquals(hello2Vertex, cycle.get(2)); List<Vertex<?>> path = gce.getPath(); assertEquals(3, path.size()); assertEquals(helloVertex, path.get(0)); assertEquals(hello1Vertex, path.get(1)); assertEquals(hello2Vertex, path.get(2)); } }
@Override public void addEdge(Vertex<T> from, Vertex<T> to) throws CycleException { if ((from == null) || (to == null) || !vertices.containsKey(from.getValue()) || !vertices.containsKey(to.getValue())) { return; } from.addEdgeTo(to); to.addEdgeFrom(from); List<Vertex<T>> cycle = CycleDetector.introducesCycle(to); if (cycle != null) { removeEdge(from, to); List<Vertex<T>> path = getAnyPathToRoot(to); String message = String.format("Edge between '%s' and '%s' would introduce a cycle into the graph.", from.getValue().toString(), to.getValue().toString()); throw new CycleException(message, cycle, path); } }
DirectedAcyclicGraph implements Graph<T> { @Override public void addEdge(Vertex<T> from, Vertex<T> to) throws CycleException { if ((from == null) || (to == null) || !vertices.containsKey(from.getValue()) || !vertices.containsKey(to.getValue())) { return; } from.addEdgeTo(to); to.addEdgeFrom(from); List<Vertex<T>> cycle = CycleDetector.introducesCycle(to); if (cycle != null) { removeEdge(from, to); List<Vertex<T>> path = getAnyPathToRoot(to); String message = String.format("Edge between '%s' and '%s' would introduce a cycle into the graph.", from.getValue().toString(), to.getValue().toString()); throw new CycleException(message, cycle, path); } } }
DirectedAcyclicGraph implements Graph<T> { @Override public void addEdge(Vertex<T> from, Vertex<T> to) throws CycleException { if ((from == null) || (to == null) || !vertices.containsKey(from.getValue()) || !vertices.containsKey(to.getValue())) { return; } from.addEdgeTo(to); to.addEdgeFrom(from); List<Vertex<T>> cycle = CycleDetector.introducesCycle(to); if (cycle != null) { removeEdge(from, to); List<Vertex<T>> path = getAnyPathToRoot(to); String message = String.format("Edge between '%s' and '%s' would introduce a cycle into the graph.", from.getValue().toString(), to.getValue().toString()); throw new CycleException(message, cycle, path); } } DirectedAcyclicGraph(); }
DirectedAcyclicGraph implements Graph<T> { @Override public void addEdge(Vertex<T> from, Vertex<T> to) throws CycleException { if ((from == null) || (to == null) || !vertices.containsKey(from.getValue()) || !vertices.containsKey(to.getValue())) { return; } from.addEdgeTo(to); to.addEdgeFrom(from); List<Vertex<T>> cycle = CycleDetector.introducesCycle(to); if (cycle != null) { removeEdge(from, to); List<Vertex<T>> path = getAnyPathToRoot(to); String message = String.format("Edge between '%s' and '%s' would introduce a cycle into the graph.", from.getValue().toString(), to.getValue().toString()); throw new CycleException(message, cycle, path); } } DirectedAcyclicGraph(); @Override Vertex<T> addVertex(T of); @Override void addEdge(Vertex<T> from, Vertex<T> to); @Override void removeEdge(Vertex<T> from, Vertex<T> to); @Override Vertex<T> getVertex(T of); @Override boolean hasVertex(T of); @Override boolean hasEdge(Vertex<T> from, Vertex<T> to); @Override boolean isCyclic(); @Override List<Vertex<T>> getVertices(); @Override List<Vertex<T>> getRootVertices(); @Override String toString(); }
DirectedAcyclicGraph implements Graph<T> { @Override public void addEdge(Vertex<T> from, Vertex<T> to) throws CycleException { if ((from == null) || (to == null) || !vertices.containsKey(from.getValue()) || !vertices.containsKey(to.getValue())) { return; } from.addEdgeTo(to); to.addEdgeFrom(from); List<Vertex<T>> cycle = CycleDetector.introducesCycle(to); if (cycle != null) { removeEdge(from, to); List<Vertex<T>> path = getAnyPathToRoot(to); String message = String.format("Edge between '%s' and '%s' would introduce a cycle into the graph.", from.getValue().toString(), to.getValue().toString()); throw new CycleException(message, cycle, path); } } DirectedAcyclicGraph(); @Override Vertex<T> addVertex(T of); @Override void addEdge(Vertex<T> from, Vertex<T> to); @Override void removeEdge(Vertex<T> from, Vertex<T> to); @Override Vertex<T> getVertex(T of); @Override boolean hasVertex(T of); @Override boolean hasEdge(Vertex<T> from, Vertex<T> to); @Override boolean isCyclic(); @Override List<Vertex<T>> getVertices(); @Override List<Vertex<T>> getRootVertices(); @Override String toString();  }