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

Question

考虑一个有向图，如下所示:

其中，(A) 最初，实心黑边被断言:

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

然后 (B) transitive closure然后计算添加以下(虚线)边:

• 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)可能对于“更大”的图来说变得非常昂贵。

EDIT: Extended the code with a first attempt (!) of implementing the topological constraint that was mentioned in the original question. It basically follows the same concept as the simple approach: For each edge, it checks whether the vertices of the edge are still connected if the edge was removed. However, this check whether the vertices are connected is not done with a simple BFS, but with a "constrained" BFS. This BFS skips all vertices whose topological index is greater than the topological index of the end vertex of the edge.

Although this delivers the same result as the simple approach, the topological sort and the implied constraint are somewhat brain-twisting and its feasibility should be analyzed in a more formal way. This means: I am NOT sure whether the result is correct in every case.

IF the result is correct, it could indeed be more efficient. The program prints the number of vertices that are scanned during the simple BFS and during the constrained BFS. The number of vertices for the constrained BFS is lower, and this advantage should become greater when the graph becomes larger: The simple BFS will basically always have have to scan all edges, resulting in the worst case of O(e), and a complexity of O(e*e) for the whole algorithm. The complexity of the topological sorting depends on the structure of the graph, but should be linear for the graphs in question. However, I did not explicitly analyze what the complexity of the constrained BFS will be.

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;
    }



}