Алгоритм поиска избыточных краев в графе или дереве

Ответ 1

Вы хотите вычислить наименьший граф, который поддерживает достижимость вершины.

Это называется переходным сокращением графика. Статья в Википедии должна начать вас по правильной дороге.

Ответ 2

Подграф данного графа, который не содержит "избыточных ребер", называется " охватывающим деревом этого графа. Для любого заданного графа возможны несколько связующих деревьев.

Итак, для того, чтобы избавиться от избыточных ребер, все, что вам нужно сделать, это найти любое связующее дерево вашего графика. Вы можете использовать любой глубину-первый поиск или width-first- поиск и продолжить поиск, пока вы не посетили каждую вершину графика.

Ответ 3

Отметьте это: Минимальное связующее дерево

Ответ 4

Несколько способов атаковать это, но сначала вам нужно будет определить проблему немного точнее. Во-первых, график, который у вас здесь, ацикличен и направлен: всегда ли это будет?

Затем вам нужно определить, что вы подразумеваете под "избыточным краем". В этом случае вы начинаете с графика, который имеет два пути a- > c: один через b и один прямой. Из этого я делаю вывод, что "избыточным" вы имеете в виду нечто подобное. Пусть G = V, E > - граф, V - множество вершин и E & sube; V & times; V - множество ребер. Кажется, вы определяете все ребра из v _i в v _j короче, чем самый длинный край как "избыточный". Так что проще всего было бы использовать поиск по глубине сначала, перечислить пути, и когда вы найдете новый, который дольше, сохраните его как лучшего кандидата.

Я не могу представить, для чего вы хотите. Ты можешь сказать?

Ответ 5

У меня была аналогичная проблема, и я решил ее решить следующим образом:

Моя структура данных состоит из словаря 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)]

Ответ 6

Так как статья в Википедии, упомянутая @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());
                        }
                ));

Ответ 7

Я думаю, что это самый простой способ сделать это, на самом деле представить себе, как это будет выглядеть в реальной работе, представьте, если у вас есть суставы, Like

(A- > B) (B- > C) (A- > C), предположим, что расстояние между близкими графами равно 1, поэтому

(A- > B) = 1, (B- > C) = 1, (A- > C) = 2.

Итак, вы можете удалить сустав (A- > C).

Другими словами, свести к минимуму.

Это только моя идея, как я думаю об этом в начале. В сети есть различные статьи и источники, вы можете смотреть на них и глубже.

Ресурсы, которые помогут вам:

Алгоритм удаления избыточных краев на двойном графике недвоичного CSP

Структура графических данных и алгоритмы основного графика

Google Books, Об обнаружении минимальных двух связанных подграфов

Уменьшение графика

Резервные деревья для предварительно запланированного восстановления в произвольных хэш-избыточных или красно-избыточных графах