Существует ли установленный алгоритм поиска избыточных ребер в графе?
Например, я хотел бы найти, что a- > d и a- > e являются избыточными, а затем избавиться от них, например:
= > 
Редактировать: Стриланк был достаточно хорош, чтобы читать мои мысли для меня. "Избыточное" было слишком сильным слова, так как в приведенном выше примере ни a- > b, ни a- > c не считается избыточным, но a- > d является.
Вы хотите вычислить наименьший граф, который поддерживает достижимость вершины.
Это называется переходным сокращением графика. Статья в Википедии должна начать вас по правильной дороге.
Подграф данного графа, который не содержит "избыточных ребер", называется " охватывающим деревом этого графа. Для любого заданного графа возможны несколько связующих деревьев.
Итак, для того, чтобы избавиться от избыточных ребер, все, что вам нужно сделать, это найти любое связующее дерево вашего графика. Вы можете использовать любой глубину-первый поиск или width-first- поиск и продолжить поиск, пока вы не посетили каждую вершину графика.
Отметьте это: Минимальное связующее дерево
Несколько способов атаковать это, но сначала вам нужно будет определить проблему немного точнее. Во-первых, график, который у вас здесь, ацикличен и направлен: всегда ли это будет?
Затем вам нужно определить, что вы подразумеваете под "избыточным краем". В этом случае вы начинаете с графика, который имеет два пути a- > c: один через b и один прямой. Из этого я делаю вывод, что "избыточным" вы имеете в виду нечто подобное. Пусть G = V, E > - граф, V - множество вершин и E & sube; V & times; V - множество ребер. Кажется, вы определяете все ребра из v i в v j короче, чем самый длинный край как "избыточный". Так что проще всего было бы использовать поиск по глубине сначала, перечислить пути, и когда вы найдете новый, который дольше, сохраните его как лучшего кандидата.
Я не могу представить, для чего вы хотите. Ты можешь сказать?
У меня была аналогичная проблема, и я решил ее решить следующим образом:
Моя структура данных состоит из словаря dependends, от идентификатора node до списка узлов, которые зависят от него (т.е. его последователей в DAG). Обратите внимание, что это работает только для DAG - это направленный ациклический граф.
Я не вычислил точную его сложность, но он проглотил мой график в несколько тысяч секунд.
_transitive_closure_cache = {}
def transitive_closure(self, node_id):
"""returns a set of all the nodes (ids) reachable from given node(_id)"""
global _transitive_closure_cache
if node_id in _transitive_closure_cache:
return _transitive_closure_cache[node_id]
c = set(d.id for d in dependents[node_id])
for d in dependents[node_id]:
c.update(transitive_closure(d.id)) # for the non-pythonists - update is update self to Union result
_transitive_closure_cache[node_id] = c
return c
def can_reduce(self, source_id, dest_id):
"""returns True if the edge (source_id, dest_id) is redundant (can reach from source_id to dest_id without it)"""
for d in dependents[source_id]:
if d.id == dest_id:
continue
if dest_id in transitive_closure(d.id):
return True # the dest node can be reached in a less direct path, then this link is redundant
return False
# Reduce redundant edges:
for node in nodes:
dependents[node.id] = [d for d in dependents[node.id] if not can_reduce(node.id, d.id)]
Так как статья в Википедии, упомянутая @Craig, дает только хит реализации, я публикую свою реализацию с потоками Java 8:
Map<String, Set<String>> reduction = usages.entrySet().stream()
.collect(toMap(
Entry::getKey,
(Entry<String, Set<String>> entry) -> {
String start = entry.getKey();
Set<String> neighbours = entry.getValue();
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>(neighbours);
while (!queue.isEmpty()) {
String node = queue.remove();
usages.getOrDefault(node, emptySet()).forEach(next -> {
if (next.equals(start)) {
throw new RuntimeException("Cycle detected!");
}
if (visited.add(next)) {
queue.add(next);
}
});
}
return neighbours.stream()
.filter(s -> !visited.contains(s))
.collect(toSet());
}
));
Я думаю, что это самый простой способ сделать это, на самом деле представить себе, как это будет выглядеть в реальной работе, представьте, если у вас есть суставы, Like
(A- > B) (B- > C) (A- > C), предположим, что расстояние между близкими графами равно 1, поэтому
(A- > B) = 1, (B- > C) = 1, (A- > C) = 2.
Итак, вы можете удалить сустав (A- > C).
Другими словами, свести к минимуму.
Это только моя идея, как я думаю об этом в начале. В сети есть различные статьи и источники, вы можете смотреть на них и глубже.
Ресурсы, которые помогут вам:
Алгоритм удаления избыточных краев на двойном графике недвоичного CSP
Структура графических данных и алгоритмы основного графика
Google Books, Об обнаружении минимальных двух связанных подграфов