Я опубликовал финальный файл. В нем 48955 вершин и 258215 связей между ними.
Я пытался решать эту задачу используя матрицу смежности. В родительском топике. Но мне не хватило
памяти для массива. Произведения 50000 на 50000 давало величину в штуках больше чем индекс
массива в Java. И это только первое ограничение. И если массив я просто преодолел разбивая
матрицу на слои как торт. То второе ограничение - медленная скорость поиска смежных вершин
по матрице - я не преодолел.
Это - слабое место структуры данных и я полностью отказался от матрицы. Заменил ее на список
вершин где для каждой вершины есть списки входящих и исходящих ребер.
Фрагмент вершины
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.
public class Vertex implements Serializable {
static final long serialVersionUID = 1L;
// Key fields
private String id;
// Non-key fields
private List<Edge> outgoingEdges = new ArrayList<>();
private List<Edge> incomingEdges = new ArrayList<>();
public Vertex(@NotNull String id) {
this.id = id;
}
public Vertex() {
// For serialization
}
// Incoming edges
void addIncomingEdge(@NotNull Edge edge) {
checkArgument(edge.getV2() != this, "Unable to link edge " + edge.toString() + " because of illegal V2 value");
incomingEdges.add(edge);
}
