Computing nearest vertex neighbors in a DAG completed by transitive-closure

Question

Consider a directed graph, like this:

Where, (A) initially, the solid black edges are asserted:

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

Then (B) the transitive closure has then been computed to add the following (dashed) edges:

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

For any vertex in this final graph, how can I efficiently compute the 'immediate' neighbors accessible by some edge which aren't accessible by a different, longer path? The output I want is shown in (A). I am not distinguishing between edges which were asserted (bold) or inferred (dashed).

Is there a well-known name to this problem, and is there a straightforward way of achieving this with JGraphT?

---

Thoughts:

Perhaps this is possible by using a topological sort of the vertices, e.g. 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)
      }
    }
  } 
}

Basically, I'm thinking that (v0 → v1) is a solution when no other longer path (v0 → ... v2 ... → v1) exists where v0 > v2 > v1 in the topological sort. Does this look correct, and/or is there a more efficient way?

Answer 1

The approach mentioned in the comments, implemented with JGraphT:

It simply iterates over all edges, removes each edge temporarily, and checks whether the vertices of the edge are still connected (using a simple Breadth-First-Search). If they are no longer connected, then the edge is added to the result set (before it is re-inserted into the graph).

This is rather trivial, so I assume that there is a more sophisticated solution. Particularly the checks for the existence of a path (even with a simple BFS) might become prohibitively expensive for "larger" graphs.

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



}