Пометьте ребро числом циклов, в котором оно участвует - PullRequest
Новая
       43

Пометьте ребро числом циклов, в котором оно участвует

0 голосов
/ 30 ноября 2018

Учитывая график G = (V, E), используя DFS, как мне пометить каждое ребро числом простых циклов, в которых оно участвует?Я уже помечаю узлы пост-заказом, когда извлекаю сильно связанные компоненты из графика, так что, возможно, я смогу каким-то образом использовать эту информацию.,Кто-нибудь может указать мне правильное направление?

Ответы [ 2 ]

0 голосов
/ 04 декабря 2018

Я закончил тем, что добавил дополнительные Map<Node, Stack<Edge>> из previousEdges, чтобы отследить, какой край пройти назад в обратном направлении.Затем функция unwindStack пересекает этот связанный список, увеличивая Edge.cycles до тех пор, пока не достигнет Node, завершившего цикл (loopNode): 

private void labelEdges(Node currentNode, Set<Node> component) {

    onStack.put(currentNode, Boolean.TRUE);

    for (Edge outEdge : currentNode.getEdges()) {
        Node nextNode = outEdge.getEnd();
        if (component.contains(nextNode)) {

            // put the edge on the previousEdges stack
            if (!previousEdges.containsKey(nextNode)) {
                previousEdges.put(nextNode, new Stack<>());
            }
            previousEdges.get(nextNode).push(outEdge);

            if (onStack.getOrDefault(nextNode, false)) {
                // found loop
                unwindStack(nextNode, nextNode);
                // pop the previousEdge off the stack, so that we undo any
                // overwriting of history for another branch.
                previousEdges.get(nextNode).pop();

            }
            else {
                // recursively call this function
                labelEdges(nextNode, component);
            }
        }
    }
    onStack.put(currentNode, Boolean.FALSE);
}

private void unwindStack(Node currentNode, Node loopNode) {
    Edge previousEdge;
    try {
        previousEdge = previousEdges.get(currentNode).peek();
    } catch (EmptyStackException e) {
        previousEdge = null;
    }
    if (previousEdge != null) {
        // increment edgeCycles entry by 1
        edgeCycles.merge(previousEdge, 1, Integer::sum);
        Node previousNode = previousEdge.getStart();
        if (previousNode != loopNode) {
            unwindStack(previousNode, loopNode);
        }
    }
}
0 голосов
/ 03 декабря 2018

Трудно дать вам полный ответ, не видя весь ваш код, но я думаю, что это поможет.Обратите внимание, что ссылки приведены для неориентированных графиков.

Я думаю, вам следует разделить задачу на две части:

1. Поиск всех циклов в графике (сохраните ихв хеш-таблице или аналогичном)

2. Определение того, какой из этих циклов содержит определенный узел.

Решение для 1: Для первогошаг, есть много алгоритмов онлайн, как этот , который будет работать с незначительными изменениями или этот , который считает количество циклов, и вы можете изменить его, чтобы сохранить циклыон находит.

Решение для 2: Это зависит от того, как вы сохраняете циклы, но это простой алгоритм поиска.

Обратите внимание, что это решение не является оптимальным, если вы хотите найти ответ только для одного узла один раз, но это действительно хорошо, если вы хотите найти число циклов для любого данного узла и любогоданное время.

...