001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2002-2006, GeoTools Project Managment Committee (PMC)
005: * (C) 2002, Refractions Reserach Inc.
006: *
007: * This library is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU Lesser General Public
009: * License as published by the Free Software Foundation;
010: * version 2.1 of the License.
011: *
012: * This library is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * Lesser General Public License for more details.
016: */
017: package org.geotools.graph.util;
018:
019: import java.util.List;
020: import java.util.Map;
021:
022: import junit.framework.TestCase;
023:
024: import org.geotools.graph.GraphTestUtil;
025: import org.geotools.graph.build.GraphBuilder;
026: import org.geotools.graph.build.basic.BasicGraphBuilder;
027: import org.geotools.graph.structure.Graph;
028: import org.geotools.graph.structure.GraphVisitor;
029: import org.geotools.graph.structure.Graphable;
030: import org.geotools.graph.structure.Node;
031: import org.geotools.graph.util.graph.GraphPartitioner;
032:
033: public class GraphPartitionerTest extends TestCase {
034:
035: private GraphBuilder m_builder;
036:
037: public GraphPartitionerTest(String name) {
038: super (name);
039: }
040:
041: protected void setUp() throws Exception {
042: super .setUp();
043:
044: m_builder = createBuilder();
045: }
046:
047: /**
048: * Create a graph in which every node is connected and partition.
049: *
050: * Expected: 1. There should only be one partition.
051: */
052: public void test_0() {
053: int nnodes = 100;
054: GraphTestUtil.buildNoBifurcations(builder(), nnodes);
055:
056: GraphPartitioner partitioner = new GraphPartitioner(builder()
057: .getGraph());
058: partitioner.partition();
059:
060: List partitions = partitioner.getPartitions();
061:
062: assertTrue(partitions.size() == 1);
063:
064: //ensure every node in the original graph is in the new graph
065: final Graph g = (Graph) partitions.get(0);
066: assertTrue(g.getNodes().size() == builder().getGraph()
067: .getNodes().size());
068: assertTrue(g.getEdges().size() == builder().getGraph()
069: .getEdges().size());
070:
071: GraphVisitor visitor = new GraphVisitor() {
072: public int visit(Graphable component) {
073: assertTrue(g.getNodes().contains(component));
074: return 0;
075: }
076: };
077: builder().getGraph().visitNodes(visitor);
078: }
079:
080: /**
081: * Create a balanced binary tree and then remove the root node and partition.
082: * <BR>
083: * <BR>
084: * Expected: 1. Two graphs should be created. One for each subtree of
085: * original.
086: *
087: */
088: public void test_1() {
089: int k = 4;
090: Object[] obj = GraphTestUtil.buildPerfectBinaryTree(builder(),
091: k);
092: Node root = (Node) obj[0];
093: Map id2node = (Map) obj[1];
094:
095: Node lc = (Node) id2node.get("0.0");
096: Node rc = (Node) id2node.get("0.1");
097:
098: builder().removeNode(root);
099:
100: GraphPartitioner parter = new GraphPartitioner(builder()
101: .getGraph());
102: parter.partition();
103:
104: List partitions = parter.getPartitions();
105:
106: assertTrue(partitions.size() == 2);
107:
108: Graph left = (Graph) partitions.get(0);
109: Graph right = (Graph) partitions.get(1);
110:
111: if (!left.getNodes().contains(lc)) {
112: //swap
113: left = (Graph) partitions.get(1);
114: right = (Graph) partitions.get(0);
115: }
116:
117: assertTrue(left.getNodes().contains(lc));
118: assertTrue(right.getNodes().contains(rc));
119:
120: assertTrue(left.getNodes().size() == Math.pow(2, k) - 1);
121: assertTrue(left.getEdges().size() == Math.pow(2, k) - 2);
122: assertTrue(right.getNodes().size() == Math.pow(2, k) - 1);
123: assertTrue(right.getEdges().size() == Math.pow(2, k) - 2);
124:
125: GraphVisitor visitor = new GraphVisitor() {
126: public int visit(Graphable component) {
127: assertTrue(component.getObject().toString().startsWith(
128: "0.0"));
129: return 0;
130: }
131: };
132: left.visitNodes(visitor);
133:
134: visitor = new GraphVisitor() {
135: public int visit(Graphable component) {
136: assertTrue(component.getObject().toString().startsWith(
137: "0.1"));
138: return 0;
139: }
140: };
141: right.visitNodes(visitor);
142: }
143:
144: protected GraphBuilder createBuilder() {
145: return (new BasicGraphBuilder());
146: }
147:
148: protected GraphBuilder builder() {
149: return (m_builder);
150: }
151:
152: }
|