1 25 40 package org.jgrapht.alg; 41 42 import java.util.*; 43 44 import junit.framework.*; 45 46 import org.jgrapht.*; 47 import org.jgrapht.graph.*; 48 49 50 55 public abstract class ShortestPathTestCase 56 extends TestCase 57 { 58 59 61 static final String V1 = "v1"; 62 static final String V2 = "v2"; 63 static final String V3 = "v3"; 64 static final String V4 = "v4"; 65 static final String V5 = "v5"; 66 67 69 DefaultWeightedEdge e12; 70 DefaultWeightedEdge e13; 71 DefaultWeightedEdge e15; 72 DefaultWeightedEdge e24; 73 DefaultWeightedEdge e34; 74 DefaultWeightedEdge e45; 75 76 78 81 public void testPathBetween() 82 { 83 List path; 84 Graph<String , DefaultWeightedEdge> g = create(); 85 86 path = findPathBetween(g, V1, V2); 87 assertEquals(Arrays.asList(new DefaultEdge [] { e12 }), path); 88 89 path = findPathBetween(g, V1, V4); 90 assertEquals(Arrays.asList(new DefaultEdge [] { 91 e12, 92 e24 93 }), path); 94 95 path = findPathBetween(g, V1, V5); 96 assertEquals(Arrays.asList(new DefaultEdge [] { 97 e12, 98 e24, 99 e45 100 }), path); 101 102 path = findPathBetween(g, V3, V4); 103 assertEquals(Arrays.asList(new DefaultEdge [] { 104 e13, 105 e12, 106 e24 107 }), path); 108 } 109 110 protected abstract List findPathBetween( 111 Graph<String , DefaultWeightedEdge> g, 112 String src, 113 String dest); 114 115 protected Graph<String , DefaultWeightedEdge> create() 116 { 117 return createWithBias(false); 118 } 119 120 protected Graph<String , DefaultWeightedEdge> createWithBias( 121 boolean negate) 122 { 123 Graph<String , DefaultWeightedEdge> g; 124 double bias = 1; 125 if (negate) { 126 g = 129 new SimpleDirectedWeightedGraph<String , DefaultWeightedEdge>( 130 DefaultWeightedEdge.class); 131 bias = -1; 132 } else { 133 g = 135 new SimpleWeightedGraph<String , DefaultWeightedEdge>( 136 DefaultWeightedEdge.class); 137 } 138 139 g.addVertex(V1); 140 g.addVertex(V2); 141 g.addVertex(V3); 142 g.addVertex(V4); 143 g.addVertex(V5); 144 145 e12 = Graphs.addEdge(g, V1, V2, bias * 2); 146 147 e13 = Graphs.addEdge(g, V1, V3, bias * 3); 148 149 e24 = Graphs.addEdge(g, V2, V4, bias * 5); 150 151 e34 = Graphs.addEdge(g, V3, V4, bias * 20); 152 153 e45 = Graphs.addEdge(g, V4, V5, bias * 5); 154 155 e15 = Graphs.addEdge(g, V1, V5, bias * 100); 156 157 return g; 158 } 159 } 160 | Popular Tags |