Routing

 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
import java.util.ArrayList;
public class Routing {
Network network;
int[] buf;
ArrayList<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();
int[][] matrix;
boolean[] include;
public Routing(Network network) {
if (network == null) { throw new RuntimeException(); }
this.network = network;
buf = new int[network.getElements().size()];
include = new boolean[network.getElements().size()];
for (int i = 0; i < include.length; i++) { include[i] = false; }
}
//ArrayList<ArrayList<PathElement>>
public ArrayList<ArrayList<PathElement>> getRoute(String ip1, String ip2) {
int index1 = -1, index2 = -1;
ArrayList<PathElement> elements = network.getElements();
for (int i = 0; i < elements.size(); i++) {
if (elements.get(i) instanceof ActiveElement) {
ActiveElement aEl = (ActiveElement)elements.get(i);
if (aEl.getIP().equals(ip1)) index1 = i;
if (aEl.getIP().equals(ip2)) index2 = i;
}
}
if (index1 == -1 || index2 == -1) { throw new RuntimeException("ip no exist"); }
matrix = this.getMatrix();
search(index1, index2, 1);
//теперь все пути добавленны в двумерный массив, смоделированный на ArrayList
//Составим теперь коллекцию коллекций из элементов PathElement'ов
ArrayList<ArrayList<PathElement>> collectionPath = new ArrayList<ArrayList<PathElement>>();
for (ArrayList<Integer> path : paths) {
collectionPath.add(new ArrayList<PathElement>());
for (int i : path) {
collectionPath.get(collectionPath.size()-1).add(elements.get(i));
}
}
return collectionPath;
}
private void search(int s, int f, int count) {
if (s == f) {
paths.add(new ArrayList<Integer>());
for (int i = 0; i < count; i++) {
paths.get(paths.size()-1).add(buf[i]);
}
} else {
for (int i = 0; i<network.getElements().size(); i++) {
if ((matrix[s][i] == 1 || matrix[i][s] == 1) && !include[i]) {
buf[count] = i;
include[i] = true;
search(i, f, count+1);
include[i] = false;
buf[count] = 0;
}
}
}
}
private int[][] getMatrix() {
ArrayList<PathElement> elements = network.getElements();
int len = elements.size();
int matrix[][] = new int[len][len];
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if (elements.get(i).isConnect(elements.get(j))) {
matrix[i][j] = 1;
} else {
matrix[i][j] = 0;
}
}
}
return matrix;
}
}