MinimumDiameterSpanningTree { public Tree<V, E> getMinimumDiameterSpanningTree() { PointOnEdge<V, E> center = new AbsoluteOneCenter<V, E>(d_graph, d_edgeLength, d_distance, d_vertexComparator).getCenter(); DelegateTree<V,E> tree = new DelegateTree<V, E>(); double dc = center.getDistance() - 0.5 * l(center.getEdge()); int vc = d_vertexComparator == null ? 0 : d_vertexComparator.compare(center.getVertex0(), center.getVertex1()); if (dc < 0.0 || (dc == 0.0 && vc <= 0)) { tree.setRoot(center.getVertex0()); tree.addChild(center.getEdge(), center.getVertex0(), center.getVertex1()); } else { tree.setRoot(center.getVertex1()); tree.addChild(center.getEdge(), center.getVertex1(), center.getVertex0()); } for (V v : d_graph.getVertices()) { if (v.equals(center.getVertex0()) || v.equals(center.getVertex1())) { continue; } double d0 = d_distance.getDistance(center.getVertex0(), v).doubleValue(); double d1 = d_distance.getDistance(center.getVertex1(), v).doubleValue(); double d = (d0 + center.getDistance()) - (d1 + l(center.getEdge()) - center.getDistance()); if (d < 0 || (d == 0 && vc <= 0)) { addPath(tree, center.getVertex0(), v); } else { addPath(tree, center.getVertex1(), v); } } return tree; } MinimumDiameterSpanningTree(final UndirectedGraph<V, E> graph);  MinimumDiameterSpanningTree(final UndirectedGraph<V, E> graph, Comparator<V> vertexComparator);  MinimumDiameterSpanningTree(final UndirectedGraph<V, E> graph, final Transformer<E, Number> edgeLength);  MinimumDiameterSpanningTree(final UndirectedGraph<V, E> graph, final Transformer<E, Number> edgeLength, 
			final DijkstraShortestPath<V, E> shortestPath);  MinimumDiameterSpanningTree(final UndirectedGraph<V, E> graph, final Transformer<E, Number> edgeLength,
			final DijkstraShortestPath<V, E> shortestPath, final Comparator<V> vertexComparator);  MinimumDiameterSpanningTree(final UndirectedGraph<V, E> graph, final Transformer<E, Number> edgeLength, 
			final Distance<V> distance, final ShortestPath<V, E> shortestPath);  MinimumDiameterSpanningTree(final UndirectedGraph<V, E> graph, final Transformer<E, Number> edgeLength, 
			final Distance<V> distance, final ShortestPath<V, E> shortestPath, Comparator<V> vertexComparator); Tree<V, E> getMinimumDiameterSpanningTree();  }
@Test public void testMinDiamTree() { Collection<String> vertices = Arrays.asList("A", "B", "C", "D", "E"); final UndirectedGraph<String, Integer> g = new UndirectedSparseGraph<String, Integer>(); GraphUtil.addVertices(g, vertices); g.addEdge(1, "A", "B"); g.addEdge(2, "A", "C"); g.addEdge(3, "A", "D"); g.addEdge(4, "A", "E"); g.addEdge(5, "B", "C"); g.addEdge(6, "C", "D"); g.addEdge(7, "D", "E"); Tree<String, Integer> tree = new MinimumDiameterSpanningTree<String, Integer>(g).getMinimumDiameterSpanningTree(); assertEquals("A", tree.getRoot()); assertEquals(new Integer(1), tree.findEdge("A", "B")); assertEquals(new Integer(2), tree.findEdge("A", "C")); assertEquals(new Integer(3), tree.findEdge("A", "D")); assertEquals(new Integer(4), tree.findEdge("A", "E")); assertEquals(4, tree.getEdgeCount()); }
@Test public void testWithVertexComparator() { UndirectedGraph<String, Integer> graph = new UndirectedSparseGraph<String, Integer>(); graph.addEdge(1, "F", "C"); graph.addEdge(2, "B", "C"); graph.addEdge(3, "B", "D"); graph.addEdge(4, "C", "D"); graph.addEdge(5, "A", "E"); graph.addEdge(6, "A", "F"); graph.addEdge(7, "E", "F"); Tree<String, Integer> tree = new MinimumDiameterSpanningTree<String, Integer>(graph, new Comparator<String>() { public int compare(String o1, String o2) { return o1.compareTo(o2); } }).getMinimumDiameterSpanningTree(); assertEquals("C", tree.getRoot()); assertNotNull(tree.findEdge("C", "F")); assertNotNull(tree.findEdge("C", "B")); assertNotNull(tree.findEdge("C", "D")); assertNotNull(tree.findEdge("F", "E")); assertNotNull(tree.findEdge("F", "A")); }
@Test public void testWithLongShortestPaths() { UndirectedGraph<String, Integer> graph = new UndirectedSparseGraph<String, Integer>(); graph.addEdge(1, "CBGGEM", "CBPPTX"); graph.addEdge(2, "CBGGEM", "DDPGEM"); graph.addEdge(3, "CBGGEM", "DDPVNR"); graph.addEdge(4, "CBPPTX", "DDPDOC"); graph.addEdge(5, "CBPPTX", "DDPPTX"); graph.addEdge(6, "CBPPTX", "DDPETO"); graph.addEdge(7, "CBPPTX", "DDPGEM"); graph.addEdge(8, "CBPPTX", "DDPIRI"); graph.addEdge(9, "CBPPTX", "DDPVNR"); graph.addEdge(10, "DDPGEM", "DDPPTX"); graph.addEdge(11, "DDPGEM", "DDPPEM"); graph.addEdge(12, "DDPGEM", "DDPVNR"); graph.addEdge(13, "DDPGEM", "DDPIRI"); graph.addEdge(14, "DDPDOC", "DDPVNR"); graph.addEdge(15, "DDPDOC", "DDPPTX"); graph.addEdge(16, "DDPDOC", "DDPGEM"); graph.addEdge(17, "DDPPTX", "DDPVNR"); graph.addEdge(18, "DDPETO", "DDPPTX"); graph.addEdge(19, "DDPETO", "DDPGEM"); graph.addEdge(20, "DDPIRI", "DDPVNR"); graph.addEdge(21, "CBPDOC", "DDPVNR"); graph.addEdge(22, "CBPPEM", "DDPPEM"); new MinimumDiameterSpanningTree<String, Integer>(graph, new Comparator<String>() { public int compare(String o1, String o2) { return o1.compareTo(o2); } }).getMinimumDiameterSpanningTree(); }