5

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

在此处输入图像描述

其中，(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) 时。这看起来是否正确，和/或是否有更有效的方法？

4

1 回答 1

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



}
于 2014-05-28T23:28:43.450 回答