Классификация краев во время поиска по бегу на ориентированном графе

Мне трудно найти способ правильно классифицировать ребра при первом поиске по ориентированному графу.

Во время поиска по ширине или глубине вы можете классифицировать ребра, встреченные с 4 классами:

ДЕРЕВО
НАЗАД
Перекрестная
ВПЕРЕД

Skiena [1] дает реализацию. Если вы перемещаетесь по краю от v1 до v2, вот способ вернуть класс во время DFS в java, для справки. Карта родителей возвращает родительскую вершину для текущего поиска и метод timeOf(), время, в которое была обнаружена вершина.

if ( v1.equals( parents.get( v2 ) ) ) { return EdgeClass.TREE; }
    if ( discovered.contains( v2 ) && !processed.contains( v2 ) ) { return EdgeClass.BACK; }
    if ( processed.contains( v2 ) )
    {
        if ( timeOf( v1 ) < timeOf( v2 ) )
        {
            return EdgeClass.FORWARD;
        }
        else
        {
            return EdgeClass.CROSS;
        }
    }
    return EdgeClass.UNCLASSIFIED;

Моя проблема заключается в том, что я не могу получить это правильно для первого поиска Breadth на ориентированном графе. Например:

Следующий график - это цикл - это нормально:

A -> B
A -> C
B -> C

BFSing из A, B будет обнаружен, затем C. Ребра eAB и eAC являются краями TREE, а когда eBC пересекается последним, B и C обрабатываются и обнаруживаются, и это ребро должным образом классифицируется как CROSS.

Но простой цикл не работает:

A -> B
B -> C
C -> A

Когда край eCA пересекается последним, A обрабатывается и обнаруживается. Таким образом, этот край неправильно помечен как CROSS, должен ли он быть краем BACK.

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

Как вы реализуете правильную классификацию полей для BFS на ориентированном графе?

[1] http://www.algorist.com/

ИЗМЕНИТЬ

Здесь реализована реализация, полученная из ответа @redtuna. Я просто добавил проверку не для получения родительского корня. У меня есть тесты JUnits, которые показывают, что он работает для направленных и неориентированных графов, в случае цикла, прямой линии, вилки, стандартного примера, одного края и т.д.

@Override
public EdgeClass edgeClass( final V from, final V to )
{
    if ( !discovered.contains( to ) ) { return EdgeClass.TREE; }

    int toDepth = depths.get( to );
    int fromDepth = depths.get( from );

    V b = to;
    while ( toDepth > 0 && fromDepth < toDepth )
    {
        b = parents.get( b );
        toDepth = depths.get( b );
    }

    V a = from;
    while ( fromDepth > 0 && toDepth < fromDepth )
    {
        a = parents.get( a );
        fromDepth = depths.get( a );
    }

    if ( a.equals( b ) )
    {
        return EdgeClass.BACK;
    }
    else
    {
        return EdgeClass.CROSS;
    }

}

Ответ 1

Как вы реализуете правильную классификацию полей для BFS на направленный граф?

Как вы уже установили, просмотр node в первый раз создает ребро дерева. Проблема с BFS вместо DFS, как сказал Дэвид Эйзенстат, заключается в том, что задние края нельзя отличить от перекрестных, основанных только на порядке обхода.

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

Самый простой (но интенсивно использующий память) способ - связать каждый node с набором его предшественников. Это можно сделать тривиально, когда вы посещаете узлы. При поиске недревесного края между узлами a и b рассмотрите их предшественники. Если вы являетесь надлежащим подмножеством другого, то у вас есть задний край. В противном случае это перекрестный край. Это происходит непосредственно из определения перекрестного края: это край между узлами, где ни один из них не является предком или потомком другого на дереве.

Лучше всего связать только номер "глубина" с каждым node вместо набора. Опять же, это легко сделать при посещении узлов. Теперь, когда вы найдете недревесное ребро между a и b, начните с более глубокого из двух узлов и следуйте за ребрами дерева назад, пока не вернетесь на ту же глубину, что и другая. Так, например, предположим, что глубже. Затем вы повторно вычисляете a = parent (a) до глубины (a) = depth (b).

Если в этот момент a = b, вы можете классифицировать край как задний край, потому что, согласно определению, один из узлов является предком другого на дереве. В противном случае вы можете классифицировать его как перекрестный ребро, потому что мы знаем, что ни node не является предком или потомком другого.

псевдокод:

  foreach edge(a,b) in BFS order:
    if !b.known then:
      b.known = true
      b.depth = a.depth+1
      edge type is TREE
      continue to next edge
    while (b.depth > a.depth): b=parent(b)
    while (a.depth > b.depth): a=parent(a)
    if a==b then:
      edge type is BACK
    else:
      edge type is CROSS

Ответ 2

Ключевое свойство DFS здесь состоит в том, что, учитывая два узла u и v, интервал [u.discovered, u.processed] является подынтервалом [v.discovered, v.processed] тогда и только тогда, когда u является потомок v. Время в BFS не имеет этого свойства; вам нужно сделать что-то еще, например, вычислить интервалы через DFS на дереве, создаваемом BFS. Тогда псевдокод классификации - это 1. проверить принадлежность к дереву (край дерева). 2. проверить, содержит ли хвост хвост (задний край). 3. проверить, что хвостовой интервал содержит головку (передний край). 4. в противном случае объявить перекрестный край.

Ответ 3

Вместо timeof() вам нужно другое свойство вершины, которое содержит расстояние от корня. Назовите это distance.

Вы должны обработать вершину v следующим образом:

for (v0 in v.neighbours) {
    if (!v0.discovered) {
        v0.discovered = true; 
        v0.parent = v;
        v0.distance = v.distance + 1;
    }
}
v.processed = true;

После обработки вершины a v vertex вы можете запустить следующий алгоритм для каждого ребра (от v1 до v2) v:

if (!v1.discovered) return EdgeClass.BACK;  
else if (!v2.discovered) return EdgeClass.FORWARD; 
else if (v1.distance == v2.distance) return EdgeClass.CROSS;
else if (v1.distance > v2.distance) return EdgeClass.BACK;
else {
    if (v2.parent == v1) return EdgeClass.TREE;
    else return EdgeClass.FORWARD;
}