通过传递闭包计算DAG中最近的顶点邻居

Question

考虑有向图,如下所示:

其中,(A)最初,实体黑边被断言:

• 0→{1,3}
• 1→{2}
• 3→{4}
• 4→{2}

然后(B)计算传递闭包以添加以下(虚线)边:

• 0→{2,4}
• 3→{2}

对于最终图形中的任何顶点,如何有效地计算某些边缘可访问的"直接"邻居,这些邻居无法通过不同的更长路径访问？我想要的输出显示在(A)中.我没有区分断言(粗体)或推断(虚线)的边缘.

这个问题是否有一个众所周知的名称,有没有一种直接的方法来实现这个JGraphT？

---

思考:

也许这可以通过使用拓扑排序的顶点来实现,例如TS = [0,1,3,4,2].

for(i=0, i<TS.len; i++) {
  var v0 = TS[i]
  for (j=i+1; i<TS.len; j++) {
    var v1 = TS[j]
    if (edge exists v0 -> v1) {
      var otherPath = false
      for (k=i+1; k<j; k++) {
        var v2 = TS[k]
        if (path exists v0 -> v2 && path exists v2 -> v1) {
          otherPath = true 
          break
        }
      }
      if (!otherPath) {
        record (v0 -> v1)
      }
    }
  } 
}

基本上,我认为(v0→v1)是一个解决方案,当没有其他更长的路径(v0→... v2 ...→v1)存在于拓扑排序中的v0> v2> v1时.这看起来是否正确,和/或是否有更有效的方法？

Answer 1

评论中提到的方法，用JGraphT实现：

它只是迭代所有边，暂时删除每条边，并检查边的顶点是否仍然连接（使用简单的广度优先搜索）。如果它们不再连接，则将边添加到结果集中（在将其重新插入到图中之前）。

这是相当微不足道的，所以我认为有一个更复杂的解决方案。特别是对于“较大”的图来说，检查路径是否存在（即使使用简单的 BFS）可能会变得极其昂贵。

编辑：通过第一次尝试（！）实现原始问题中提到的拓扑约束来扩展代码。它基本上遵循与简单方法相同的概念：对于每条边，如果删除边，它会检查该边的顶点是否仍然连接。然而，这种检查顶点是否连接的方法不是使用简单的 BFS 完成的，而是使用“约束”BFS 完成的。该 BFS 会跳过拓扑索引大于边末端顶点拓扑索引的所有顶点。

虽然这提供了与简单方法相同的结果，但拓扑排序和隐含的约束有点费脑力，应该以更正式的方式分析其可行性。这意味着：我不确定每种情况下的结果是否正确。

如果结果是正确的，那么效率确实会更高。该程序打印在简单 BFS 和约束 BFS 期间扫描的顶点数。受约束 BFS 的顶点数量较少，当图变大时，这种优势应该会变得更大：简单的 BFS 基本上总是必须扫描所有边，导致最坏情况的 O(e) 和复杂性整个算法的 O(e*e) 。拓扑排序的复杂性取决于图的结构，但对于所讨论的图应该是线性的。不过，我并没有明确分析约束 BFS 的复杂度会是多少。

import java.util.ArrayDeque;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import org.jgrapht.DirectedGraph;
import org.jgrapht.Graph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleDirectedGraph;
import org.jgrapht.traverse.BreadthFirstIterator;
import org.jgrapht.traverse.TopologicalOrderIterator;

public class TransitiveGraphTest
{
    public static void main(String[] args)
    {
        DirectedGraph<String, DefaultEdge> g = 
            createTestGraph();

        Set<DefaultEdge> resultSimple = compute(g);
        Set<DefaultEdge> resultTopological = computeTopological(g);

        System.out.println("Result simple      "+resultSimple);
        System.out.println("Visited            "+debugCounterSimple);
        System.out.println("Result topological "+resultTopological);
        System.out.println("Visited            "+debugCounterTopological);
    }

    private static int debugCounterSimple = 0;
    private static int debugCounterTopological = 0;


    //========================================================================
    // Simple approach: For each edge, check with a BFS whether its vertices
    // are still connected after removing the edge

    private static <V, E> Set<E> compute(DirectedGraph<V, E> g)
    {
        Set<E> result = new LinkedHashSet<E>();
        Set<E> edgeSet = new LinkedHashSet<E>(g.edgeSet());
        for (E e : edgeSet)
        {
            V v0 = g.getEdgeSource(e);
            V v1 = g.getEdgeTarget(e);
            g.removeEdge(e);
            if (!connected(g, v0, v1))
            {
                result.add(e);
            }
            g.addEdge(v0, v1);
        }
        return result;
    }

    private static <V, E> boolean connected(Graph<V, E> g, V v0, V v1)
    {
        BreadthFirstIterator<V, E> i = 
            new BreadthFirstIterator<V, E>(g, v0);
        while (i.hasNext())
        {
            V n = i.next();
            debugCounterSimple++;
            if (n.equals(v1))
            {
                return true;
            }
        }
        return false;

    }


    //========================================================================
    // Topological approach: For each edge, check whether its vertices
    // are still connected after removing the edge, using a BFS that
    // is "constrained", meaning that it does not traverse past 
    // vertices whose topological index is greater than the end
    // vertex of the edge

    private static <V, E> Set<E> computeTopological(DirectedGraph<V, E> g)
    {
        Map<V, Integer> indices = computeTopologicalIndices(g);
        Set<E> result = new LinkedHashSet<E>();
        Set<E> edgeSet = new LinkedHashSet<E>(g.edgeSet());
        for (E e : edgeSet)
        {
            V v0 = g.getEdgeSource(e);
            V v1 = g.getEdgeTarget(e);
            boolean constrainedConnected =
                constrainedConnected(g, v0, v1, indices);
            if (!constrainedConnected)
            {
                result.add(e);
            }
        }        
        return result;
    }

    private static <V, E> Map<V, Integer> computeTopologicalIndices(
        DirectedGraph<V, E> g)
    {
        Queue<V> q = new ArrayDeque<V>();
        TopologicalOrderIterator<V, E> i = 
            new TopologicalOrderIterator<V, E>(g, q);
        Map<V, Integer> indices = new LinkedHashMap<V, Integer>();
        int index = 0;
        while (i.hasNext())
        {
            V v = i.next();
            indices.put(v, index);
            index++;
        }
        return indices;
    }


    private static <V, E> boolean constrainedConnected(
        DirectedGraph<V, E> g, V v0, V v1, Map<V, Integer> indices)
    {
        Integer indexV1 = indices.get(v1);
        Set<V> visited = new LinkedHashSet<V>();
        Queue<V> q = new LinkedList<V>();
        q.add(v0);
        while (!q.isEmpty())
        {
            V v = q.remove();
            debugCounterTopological++;
            if (v.equals(v1))
            {
                return true;
            }
            Set<E> outs = g.outgoingEdgesOf(v);
            for (E out : outs)
            {
                V ev0 = g.getEdgeSource(out);
                V ev1 = g.getEdgeTarget(out);
                if (ev0.equals(v0) && ev1.equals(v1))
                {
                    continue;
                }
                V n = g.getEdgeTarget(out);
                if (visited.contains(n))
                {
                    continue;
                }
                Integer indexN = indices.get(n);
                if (indexN <= indexV1)
                {
                    q.add(n);
                }
                visited.add(n);
            }
        }
        return false;
    }

    private static DirectedGraph<String, DefaultEdge> createTestGraph()
    {
        DirectedGraph<String, DefaultEdge> g =
            new SimpleDirectedGraph<String, DefaultEdge>(DefaultEdge.class);

        String v0 = "0";
        String v1 = "1";
        String v2 = "2";
        String v3 = "3";
        String v4 = "4";

        g.addVertex(v0);
        g.addVertex(v1);
        g.addVertex(v2);
        g.addVertex(v3);
        g.addVertex(v4);

        g.addEdge(v0, v1);
        g.addEdge(v0, v3);
        g.addEdge(v1, v2);
        g.addEdge(v3, v4);
        g.addEdge(v4, v2);

        g.addEdge(v0, v2);
        g.addEdge(v0, v4);
        g.addEdge(v3, v2);

        return g;
    }



}