ModelGraph { public List<ModelNode> topologicalSort() { DependencyMap dependencyMap = new DependencyMap(modelNodes); Queue<ModelNode> unprocessed = new LinkedList<>(); unprocessed.addAll(roots); List<ModelNode> sortedList = new ArrayList<>(); while (!unprocessed.isEmpty()) { ModelNode sortedNode = unprocessed.remove(); sortedList.add(sortedNode); for (ModelNode node : modelNodes) { if (dependencyMap.dependsOn(node, sortedNode)) { dependencyMap.removeDependency(node, sortedNode); if (!dependencyMap.hasDependencies(node)) { unprocessed.add(node); } } } } for (ModelNode node : modelNodes) { if (dependencyMap.hasDependencies(node)) { throw new IllegalArgumentException("Unable to sort graph because it contains cycles"); } } return sortedList; } ModelGraph(List<ModelNode> modelNodes, List<ModelNode> roots); List<ModelNode> topologicalSort();  }
@Test public void require_that_instance_can_be_created() { ModelGraph graph = new ModelGraphBuilder().addBuilder(new GraphMock.BC()).addBuilder(new GraphMock.BB()).addBuilder(new GraphMock.BA()).build(); List<ModelNode> nodes = graph.topologicalSort(); MockRoot root = new MockRoot(); GraphMock.A a = (GraphMock.A) nodes.get(0).createModel(ConfigModelContext.create(root.getDeployState(), null, null, root, "first")); GraphMock.B b = (GraphMock.B) nodes.get(1).createModel(ConfigModelContext.create(root.getDeployState(), null, null, root, "second")); GraphMock.B b2 = (GraphMock.B) nodes.get(1).createModel(ConfigModelContext.create(root.getDeployState(), null, null, root, "second2")); GraphMock.C c = (GraphMock.C) nodes.get(2).createModel(ConfigModelContext.create(root.getDeployState(), null, null, root, "third")); assertNotNull(a); assertNotNull(b); assertNotNull(b2); assertNotNull(c); assertThat(a.getId(), is("first")); assertThat(b.getId(), is("second")); assertThat(b2.getId(), is("second2")); assertThat(c.getId(), is("third")); assertThat(b.a, is(a)); assertNotNull(c.b); assertThat(c.b.size(), is(2)); assertTrue(c.b.contains(b)); assertTrue(c.b.contains(b2)); }
@Test public void require_that_collections_can_be_empty() { ModelGraph graph = new ModelGraphBuilder().addBuilder(new GraphMock.BC()).addBuilder(new GraphMock.BA()).build(); List<ModelNode> nodes = graph.topologicalSort(); MockRoot root = new MockRoot(); GraphMock.A a = (GraphMock.A) nodes.get(0).createModel(ConfigModelContext.create(root.getDeployState(), null, null, root, "first")); GraphMock.C c = (GraphMock.C) nodes.get(1).createModel(ConfigModelContext.create(root.getDeployState(), null, null, root, "second")); assertThat(c.a, is(a)); assertTrue(c.b.isEmpty()); }