blob: dd97d4a5754e4196e66f2866f4604a8025572c68 (
plain)
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
|
import java.util.*;
class CountPaths {
Stack connectionPath = new Stack();
List<Stack> connectionPaths = new ArrayList<>();
static class Node {
int id;
List<Node> childs;
Node(int id) {
this.id = id;
childs = new ArrayList<>();
}
boolean equals(Node other) {
return this.id == other.id;
}
List<Node> nextNodes() {
return childs;
}
Node addNext(Node next) {
childs.add(next);
return this;
}
}
// See https://stackoverflow.com/questions/9535819/find-all-paths-between-two-graph-nodes
void findAllPaths(Node node, Node targetNode) {
for (Node nextNode : node.nextNodes()) {
if (nextNode.equals(targetNode)) {
Stack temp = new Stack();
for (Object node1 : connectionPath)
temp.add(node1);
connectionPaths.add(temp);
} else if (!connectionPath.contains(nextNode)) {
connectionPath.push(nextNode);
findAllPaths(nextNode, targetNode);
connectionPath.pop();
}
}
}
public static void main(String argv[]) {
Node v1 = new Node(1);
Node v2 = new Node(2);
Node v3 = new Node(3);
Node v4 = new Node(4);
Node v5 = new Node(5);
Node v6 = new Node(6);
Node v7 = new Node(7);
Node v8 = new Node(8);
Node v9 = new Node(9);
Node v10 = new Node(10);
Node v11 = new Node(11);
Node v12 = new Node(12);
Node v13 = new Node(13);
Node v14 = new Node(14);
Node v15 = new Node(15);
Node v16 = new Node(16);
v1.addNext(v2);
v2.addNext(v1).addNext(v4).addNext(v7);
v3.addNext(v4).addNext(v6);
v4.addNext(v2).addNext(v3).addNext(v9);
v5.addNext(v8).addNext(v14);
v6.addNext(v3).addNext(v4).addNext(v9).addNext(v10);
v7.addNext(v2).addNext(v9).addNext(v11);
v8.addNext(v5).addNext(v11).addNext(v15);
v9.addNext(v4).addNext(v6).addNext(v7).addNext(v10).addNext(v11);
v10.addNext(v6).addNext(v9).addNext(v11).addNext(v13);
v11.addNext(v7).addNext(v8).addNext(v9).addNext(v10).addNext(v12).addNext(v15);
v12.addNext(v11).addNext(v13);
v13.addNext(v10).addNext(v12).addNext(v16);
v14.addNext(v5).addNext(v8);
v15.addNext(v11).addNext(v16);
v16.addNext(v15).addNext(v13);
CountPaths p = new CountPaths();
p.findAllPaths(v13, v2);
System.out.println(p.connectionPaths.size());
p = new CountPaths();
p.findAllPaths(v13, v14);
System.out.println(p.connectionPaths.size());
}
}
|
