Я строю программу на Java, которая имитирует сеть движущихся узлов. Когда узлы сталкиваются, существует определенная вероятность того, что они установят соединение. Я пытаюсь сохранить все узлы на графике таким образом, чтобы сделать связанные компоненты очевидными, поэтому я храню его в виде набора списков, где каждый список является компонентом, а набор содержит все компоненты. (Каждый компонент должен иметь размер больше 1.)
Полный код на github: https://github.com/IceCreamYou/ViralSpread
Но вот важная часть:
// Store the components in the "temp" variable while we calculate them.
// Each list is a component; the set contains all components.
HashSet<LinkedList<Person>> temp = new HashSet<LinkedList<Person>>();
// hardConnections is a set of all connections between the nodes.
// Each connection appears only once (e.g. if there is a connection from A to B
// there will not be a connection from B to A -- however each connection is
// considered bidirectional).
for (Person[] connection : hardConnections) {
// Each element of hardConnections is an array
// containing two connected nodes.
// "Person" is the node class.
Person a = connection[0], b = connection[1];
boolean bFound = false, aFound = false;
// If we've already added one of the nodes to a component,
// add the other one to it.
for (LinkedList<Person> component : temp) {
boolean bInComponent = false, aInComponent = false;
for (Person p : component) {
if (p.samePosition(b)) {
bInComponent = true;
}
if (p.samePosition(a)) {
aInComponent = true;
}
}
if (bInComponent && !aInComponent) {
component.add(a);
bFound = true;
break;
}
else if (!bInComponent && aInComponent) {
component.add(b);
aFound = true;
break;
}
else if (bInComponent && aInComponent) {
aFound = true;
bFound = true;
break;
}
}
// If neither node is in a component, create a new component containing both nodes.
if (!bFound && !aFound) {
LinkedList<Person> newComponent = new LinkedList<Person>();
newComponent.add(b);
newComponent.add(a);
temp.add(newComponent);
}
}
components = temp;
p.samePosition () проверяет, имеют ли узлы одинаковую позицию X и Y. Я использую этот метод вместо equals () на тот случай, если проблема связана с ошибками проверки на равенство, хотя я ничего не переопределил в классе Person (включая equals (), hashCode () и т. Д.).
Кажется, это работает большую часть времени. К сожалению, иногда после добавления нового соединения в компонент из существующего компонента этот код вычисляет новый отдельный компонент как два компонента неправильных размеров.
Я знаю, что проблема также может заключаться в том, что я неправильно вычисляю соединения. Тем не менее, соединения отображаются правильно на экране, и их правильное количество (в наборе, а не только на счет), поэтому ошибки, вероятно, нет. Но на всякий случай вот код, который вычисляет соединения. Он немного менее универсален, чем приведенный выше код, поэтому, вероятно, его сложнее читать.
// "infected" and "infector" are the nodes.
// sameColor is true if the nodes have the same type.
// Nodes with the same type should retain their connections
// (which are also to nodes of the same type) while if the nodes have different types
// then the "infected" node will lose its connections because
// it will no longer be the same type as those connections.
// Note that nodes of different types should never have connections to each other.
boolean sameColor = (infected.getVirus().equalsVirus(infector.getVirus()));
boolean sameColorConnectionExists = false;
// As above, hardConnections is a set of connections between nodes (the Person class)
Iterator<Person[]> it = hardConnections.iterator();
while (it.hasNext()) {
Person[] connection = it.next();
if (sameColor) {
if ((infected.equals(connection[0]) && infector.equals(connection[1])) ||
(infected.equals(connection[1]) && infector.equals(connection[0]))) {
sameColorConnectionExists = true;
}
}
// Remove connections to the connected person.
else if (infected.equals(connection[0]) || infected.equals(connection[1])) {
it.remove();
}
}
// Create a new connection if the nodes were of different types or
// if they are the same type but no connection exists between them.
if (!sameColor || !sameColorConnectionExists) {
hardConnections.add(new Person[] {infected, infector});
}
// After this function returns, the infected node is changed to the type of the infector.
По сути, происходит то, что мы проходим через набор соединений и удаляем все соединения с зараженным узлом, которые не принадлежат узлам того же типа. Затем, если связь между зараженным и заражающим узлами не существует, мы добавляем ее.
Я не могу понять, где ошибка здесь ... любая помощь (или даже другие советы / комментарии по самому проекту) будет оценена. Если вы посмотрите на код в github, то этот код находится в функциях Statistics.java updateConnections () и updateComponents (). updateConnections () вызывается из Person.java в TransferVirus ().
Спасибо.
UPDATE
Я выводил отладочную информацию, пытаясь выяснить, что происходит. Я выделил одно столкновение, которое вызывает неправильную фрагментацию. В данных, приведенных ниже, первая часть показывает края графика, а вторая часть показывает связанные компоненты и сколько узлов в них. Как вы можете видеть, после второго столкновения есть дополнительный «темно-серый» компонент, которого там быть не должно. Есть только один «темно-серый» компонент, и он имеет 4 узла. (Снимок экрана: http://screencast.com/t/f9PIzjuk)
----
blue:(489, 82) blue:(471, 449)
blue:(416, 412) blue:(471, 449)
pink:(207, 172) pink:(204, 132)
dark gray:(51, 285) dark gray:(635, 278)
dark gray:(635, 278) dark gray:(746, 369)
dark gray:(51, 285) dark gray:(737, 313)
dark gray:(737, 313) dark gray:(635, 278)
cyan:(2, 523) cyan:(473, 273)
3 blue
2 pink
4 dark gray
2 cyan
----
blue:(514, 79) blue:(535, 435)
dark gray:(725, 326) dark gray:(717, 365)
blue:(404, 404) blue:(535, 435)
pink:(197, 186) pink:(236, 127)
dark gray:(35, 283) dark gray:(619, 271)
dark gray:(619, 271) dark gray:(717, 365)
dark gray:(35, 283) dark gray:(725, 326)
dark gray:(725, 326) dark gray:(619, 271)
cyan:(1, 505) cyan:(490, 288)
3 blue
2 pink
4 dark gray
2 dark gray
2 cyan
----
Подумав больше о том, какая информация мне нужна для того, чтобы отладить ее без получения огромного количества информации, я получил такой снимок во время моделирования:
red:(227, 344) red:(257, 318)
red:(643, 244) red:(437, 140)
red:(437, 140) red:(257, 318)
orange:(573, 485) orange:(255, 143)
orange:(255, 143) orange:(20, 86)
red:(227, 344) red:(437, 140)
orange:(727, 494) orange:(573, 485)
3 red
red:(257, 318)
red:(227, 344)
red:(437, 140)
4 orange
orange:(255, 143)
orange:(573, 485)
orange:(20, 86)
orange:(727, 494)
2 red
red:(437, 140)
red:(643, 244)
Если вы будете следовать логике здесь:
- Посмотрите на первое соединение. Компонентов еще нет, поэтому создайте новый с помощью
red:(227, 344), red:(257, 318).
- Посмотрите на второе соединение. Существует только один компонент, и ни один из узлов в компоненте не соответствует ни одному из узлов в соединении, поэтому создайте второй компонент с
red:(227, 344), red:(257, 318). Это неправильно, поскольку в списке есть другие узлы, которые соединяют узлы в текущем соединении с исходным компонентом.
- Посмотрите на третье соединение. Второй узел соответствует узлу в первом компоненте, поэтому добавьте первый узел к первому компоненту.
- ... и т. Д.
Итак, теперь я знаю, что мой алгоритм поиска подключенных компонентов на самом деле неверен. Я думаю, мне нужно провести некоторое исследование по этому вопросу. Моя первая мысль заключается в следующем подходе:
- Создать копию списка соединений.
- Когда мы смотрим на первую пару, у нас еще нет компонентов, поэтому добавьте узлы в первом соединении к новому (первому) компоненту и удалите это соединение из копии.
- Посмотрите на каждое последующее соединение. Если один из узлов в соединении находится в первом компоненте:
- Добавить его узлы к компоненту
- Удалить это соединение из копии
- Вернитесь к последнему соединению с узлами, которые мы добавили к компоненту, и проверьте каждое соединение между этим соединением и текущим соединением, чтобы увидеть, подключаются ли они сейчас к компоненту. Если это так, добавьте их в компонент и удалите их из копии. Делать это рекурсивно.
- Когда мы дойдем до конца, повторите процесс, начиная с (теперь уменьшенной) копии вместо списка всех соединений.
Буду признателен за любые мысли об этом подходе.