Более эффективный способ обрезать направленный ациклический график в JGrapht? ⇐ JAVA

[Anonymous]

Я ищу более эффективный способ обрезать направленный ациклический график (A DAG), построенный в JGrapht. < /p>

DAG представляет отношения между набором сетевых разговоров во времени. Родители разговора - это любые разговоры, которые завершились до начала разговора с детьми. Построить DAG относительно проста, но есть много ненужных отношений. Для эффективности я хочу обрезать DAG, чтобы у каждого ребенка было прямое отношение к минимальному количеству родителей (или, наоборот, поэтому у каждого родителя минимальное количество непосредственных детей). < /P>

Реализация, которую я использую сейчас (показано ниже) основана на коде, обнаруженном в Streme. Это работает для всех моих сценариев тестирования вручную тестирования. Однако в реальном наборе данных это часто довольно медленно. Сегодня я столкнулся с сценарием с 215 вершинами, но более 22 000 краев. Обрезка DAG заняла почти 8 минут времени на оборудовании серверного класса-терпимо для моего примера немедленного использования, но слишком медленно, чтобы масштабироваться для больших сценариев. и алгоритм поиска избыточных краев на графике или дереве. То есть мне нужно найти переходное восстановление или минимальное представление для моего DAG. Jgrapht, по -видимому, не содержит прямой реализации переходного сокращения для DAG, только переходного закрытия. < /p>

Я ищу предложения о том, как повысить эффективность реализации ниже, или, возможно, указатель на существующую реализацию транзитивного снижения для JGrapht, которую я мог бы использовать. < /p>

Примечание: < /em> Альтернативно, если есть другая графическая библиотека для Java, которая включает в себя собственную реализацию транзитивного сокращения, я мог бы переключиться на эту библиотеку. Мое использование jgrapht ограничено одним классом 200 линий, поэтому заменять его не должно быть затруднено, если интерфейс похож. Чтобы поддерживать интерфейс класса (сохраняется в базе данных), мне нужна реализация DAG, которая предоставляет способ получить родителей и детей данного узла - аналогично графам jgraphts.predecessorlistof () и graphs.successorlistof () .

и графики.import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.jgrapht.DirectedGraph;
import org.jgrapht.Graphs;
import org.jgrapht.alg.DijkstraShortestPath;

public static void prune(DirectedGraph dag) {
Deque todo = new ArrayDeque(dag.vertexSet());
Set seen = new HashSet();
while (!todo.isEmpty()) {
V v = todo.pop();
if (seen.contains(v)) {
continue;
}
seen.add(v);
List targets = Graphs.successorListOf(dag, v);
for (int i = 0; i < targets.size(); i++) {
for (int j = i; j < targets.size(); j++) {
V vi = targets.get(i);
V vj = targets.get(j);
List path = DijkstraShortestPath.findPathBetween(dag, vi, vj);
if (path != null && !path.isEmpty()) {
E edge = dag.getEdge(v, vj);
dag.removeEdge(edge);
}
}
}
}
}


Подробнее здесь: https://stackoverflow.com/questions/273 ... in-jgrapht