1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
package org.eclipse.jetty.deploy.graph;
import junit.framework.Assert;
import org.junit.Test;
public class GraphTest
{
final Node nodeA = new Node("A");
final Node nodeB = new Node("B");
final Node nodeC = new Node("C");
final Node nodeD = new Node("D");
final Node nodeE = new Node("E");
@Test
public void testPath()
{
Path path = new Path();
Assert.assertEquals(0,path.nodes());
Assert.assertEquals(null,path.firstNode());
Assert.assertEquals(null,path.lastNode());
path.add(new Edge(nodeA ,nodeB));
Assert.assertEquals(2,path.nodes());
Assert.assertEquals(nodeA,path.firstNode());
Assert.assertEquals(nodeB,path.lastNode());
path.add(new Edge(nodeB ,nodeC));
Assert.assertEquals(3,path.nodes());
Assert.assertEquals(nodeA,path.firstNode());
Assert.assertEquals(nodeC,path.lastNode());
}
@Test
public void testPoint()
{
Graph graph = new Graph();
graph.addNode(nodeA);
Assert.assertEquals(1,graph.getNodes().size());
Assert.assertEquals(0,graph.getEdges().size());
Path path = graph.getPath(nodeA,nodeA);
Assert.assertEquals(0,path.nodes());
}
@Test
public void testLine()
{
Graph graph = new Graph();
graph.addEdge(new Edge(nodeA,nodeB));
Assert.assertEquals(2,graph.getNodes().size());
Assert.assertEquals(1,graph.getEdges().size());
Path path = graph.getPath(nodeA,nodeB);
Assert.assertEquals(2,path.nodes());
}
@Test
public void testTriangleDirected()
{
Graph graph = new Graph();
graph.addEdge(new Edge(nodeA,nodeB));
graph.addEdge(new Edge(nodeA,nodeC));
graph.addEdge(new Edge(nodeB,nodeC));
Assert.assertEquals(3,graph.getNodes().size());
Assert.assertEquals(3,graph.getEdges().size());
Path path = graph.getPath(nodeA,nodeB);
Assert.assertEquals(2,path.nodes());
path = graph.getPath(nodeA,nodeC);
Assert.assertEquals(2,path.nodes());
path = graph.getPath(nodeB,nodeC);
Assert.assertEquals(2,path.nodes());
}
@Test
public void testSquareDirected()
{
Graph graph = new Graph();
graph.addEdge(new Edge(nodeA,nodeB));
graph.addEdge(new Edge(nodeB,nodeC));
graph.addEdge(new Edge(nodeA,nodeD));
graph.addEdge(new Edge(nodeD,nodeC));
Assert.assertEquals(4,graph.getNodes().size());
Assert.assertEquals(4,graph.getEdges().size());
Path path = graph.getPath(nodeA,nodeC);
Assert.assertEquals(3,path.nodes());
path = graph.getPath(nodeC,nodeA);
Assert.assertEquals(null,path);
}
@Test
public void testSquareCyclic()
{
Graph graph = new Graph();
graph.addEdge(new Edge(nodeA,nodeB));
graph.addEdge(new Edge(nodeB,nodeC));
graph.addEdge(new Edge(nodeC,nodeD));
graph.addEdge(new Edge(nodeD,nodeA));
Assert.assertEquals(4,graph.getNodes().size());
Assert.assertEquals(4,graph.getEdges().size());
Path path = graph.getPath(nodeA,nodeB);
Assert.assertEquals(2,path.nodes());
path = graph.getPath(nodeA,nodeC);
Assert.assertEquals(3,path.nodes());
path = graph.getPath(nodeA,nodeD);
Assert.assertEquals(4,path.nodes());
graph.addNode(nodeE);
path = graph.getPath(nodeA,nodeE);
Assert.assertEquals(null,path);
}
}
|