Shortest invariant meeting point on the directed graph with loops

user_14874226 0
Viewed 168

I have directed graph with loops. Here is the example:

{
 0: [1,2],
 1: [1,3],
 2: [3],
 3: [4],
 4: []
}
  • Edge 0 flows into 1 and 2
  • Edge 1 flows into itself and into 3
  • Edge 2 flows into 3
  • And edge 3 flows into edge 4 (without any reason so much)

If some imagionary actor will stand on the edge 0, and will start moving, no matter what he will arive to the edge 3 (let's ignore infinite loops).

Is there an algorithm, where it is possible to supply such graph with some edge (0 from example), and it will give me shortest invariant meeting point (3 from example)?

algorithm python
1 Answers

If I understand right, the following algorithm can handle your request. However, it may not be the efficient algorithm which may you find.

get g as DAG (Directed and Asyclic)
get s as start node
get d as destination node

arr(paths) <= find All Paths From s to d 

if(paths.size <=1) print("There is no meeting point")

intersects = paths[0]

for(int i=1; i< paths.size(); i++) { 
    intersetcs <= find intersection nodes between paths i and intersects 
}

foreach (node: intersects) {
    if(node has no outgoing)
        intersects.remove(node);
}

print(intersects)

output of program for your example:

path 0 : [0, 1, 3, 4]
path 1 : [0, 2, 3, 4]
meeting points: [0, 3]

another output of program:

g:{
 0: [1,2],
 1: [3,4],
 2: [3,4],
 3: [5],
 4: [5],
 5: [6,7],
 6: [],
 7: []
}
s=0, d=7

path 0: [0, 1, 3, 5, 7]
path 1: [0, 1, 4, 5, 7]
path 2: [0, 2, 3, 5, 7]
path 3: [0, 2, 4, 5, 7]
meeting points: [0, 5]

At last an example without meeting points:


g:{
 0: [1,2],
 1: [2,3],
 2: [5],
 3: [4],
 4: [5],
 5: []
}

s=0, d=5
path 0: [0, 1, 3, 4, 5]
path 1: [0, 1, 2, 5]
path 2: [0, 2, 5]
meeting points: [0]

I provide you an example in Java too based this algorithm.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

// A directed graph using
// adjacency list representation
public class Graph {

    // No. of vertices in graph
    private int v;

    // adjacency list
    private ArrayList<Integer>[] adjList;

    // Constructor
    public Graph(int vertices)
    {

        // initialise vertex count
        this.v = vertices;

        // initialise adjacency list
        initAdjList();
    }

    // utility method to initialise
    // adjacency list
    @SuppressWarnings("unchecked")
    private void initAdjList()
    {
        adjList = new ArrayList[v];

        for (int i = 0; i < v; i++) {
            adjList[i] = new ArrayList<>();
        }
    }

    // add edge from u to v
    public void addEdge(int u, int v)
    {
        // Add v to u list.
        adjList[u].add(v);
    }

    // Prints all paths from
    // s to d
    public void printAllPaths(int s, int d)
    {
        boolean[] isVisited = new boolean[v];
        ArrayList<Integer> pathList = new ArrayList<>();

        // add source to path[]
        pathList.add(s);

        // Call recursive utility
        printAllPathsUtil(s, d, isVisited, pathList);
    }

    List<List<Integer>> allPaths = new ArrayList<>();

    private void printAllPathsUtil(Integer u, Integer d, boolean[] isVisited, List<Integer> localPathList)
    {

        if (u.equals(d)) {
            //System.out.println(localPathList);
            allPaths.add(new ArrayList<>(localPathList));
            // if match found then no need to traverse more till depth
            return;
        }

        // Mark the current node
        isVisited[u] = true;

        // Recur for all the vertices adjacent to current vertex
        for (Integer i : adjList[u]) {
            if (!isVisited[i]) {
                // store current node in path[]
                localPathList.add(i);
                printAllPathsUtil(i, d, isVisited, localPathList);

                // remove current node in path[]
                localPathList.remove(i);
            }
        }

        // Mark the current node
        isVisited[u] = false;
    }


    // Driver program
    public static void main(String[] args)
    {
        // Create a sample graph
        Graph g = new Graph(6);
        /*g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 3);
        g.addEdge(3, 4);*/

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(1, 2);
        g.addEdge(2, 5);
        g.addEdge(3, 4);
        g.addEdge(4, 5);
        // arbitrary source
        int s = 0;

        // arbitrary destination
        int d = 5;
        System.out.println(
                "Following are all different paths from "
                        + s + " to " + d);
        g.printAllPaths(s, d);

        System.out.println(g.allPaths);
        findMeetingPoint(g);

        /*for (int d=0; d<=4; d++) {
            System.out.println(
                    "Following are all different paths from "
                            + s + " to " + d);
            g.printAllPaths(s, d);
        }*/
    }

    private static void findMeetingPoint(Graph g) {
        if(g.allPaths.size()<=1) {
            System.out.println("No meeting point");
            return;
        }
        Set<Integer> intersects = new HashSet<>();
        Set<Integer> meetPoints = new HashSet<>();

        intersects.addAll(g.allPaths.get(0));

        for(int i=1; i<g.allPaths.size(); i++) {
            intersects.retainAll (g.allPaths.get(i));
        }

        for (Integer node: intersects) {
            if(g.adjList[node].size()==0)
                intersects.remove(node);
        }

        System.out.println(intersects);


    }
}

EDITTED 1 :

code which can handle cycles:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

// A directed graph using
// adjacency list representation
public class Graph {

    // No. of vertices in graph
    private int v;

    // adjacency list
    private ArrayList<Integer>[] adjList;

    // Constructor
    public Graph(int vertices)
    {

        // initialise vertex count
        this.v = vertices;

        // initialise adjacency list
        initAdjList();
    }

    // utility method to initialise
    // adjacency list
    @SuppressWarnings("unchecked")
    private void initAdjList()
    {
        adjList = new ArrayList[v];

        for (int i = 0; i < v; i++) {
            adjList[i] = new ArrayList<>();
        }
    }

    // add edge from u to v
    public void addEdge(int u, int v)
    {
        // Add v to u list.
        if(u != v)
            adjList[u].add(v);
    }

    // Prints all paths from
    // s to d
    public void printAllPaths(int s, int d)
    {
        boolean[] isVisited = new boolean[v];
        ArrayList<Integer> pathList = new ArrayList<>();

        // add source to path[]
        pathList.add(s);

        // Call recursive utility
        printAllPathsUtil(s, d, isVisited, pathList);
    }

    List<List<Integer>> allPaths = new ArrayList<>();

    private void printAllPathsUtil(Integer u, Integer d, boolean[] isVisited, List<Integer> localPathList)
    {

        if (u.equals(d)) {
            System.out.println(localPathList);
            allPaths.add(new ArrayList<>(localPathList));
            // if match found then no need to traverse more till depth
            return;
        }

        // Mark the current node
        isVisited[u] = true;

        // Recur for all the vertices adjacent to current vertex
        for (Integer i : adjList[u]) {
            if (!isVisited[i]) {
                // store current node in path[]
                localPathList.add(i);
                printAllPathsUtil(i, d, isVisited, localPathList);

                // remove current node in path[]
                localPathList.remove(i);
            }
        }

        // Mark the current node
        isVisited[u] = false;
    }


    // Driver program
    public static void main(String[] args)
    {
        // Create a sample graph
        Graph g = new Graph(5);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 1);
        g.addEdge(1, 3);
        g.addEdge(2, 3);
        g.addEdge(3, 4);

       /* g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(1, 2);
        g.addEdge(2, 5);
        g.addEdge(3, 4);
        g.addEdge(4, 5);*/
        // arbitrary source
        int s = 0;

        // arbitrary destination
        int d = 4;
        System.out.println(
                "Following are all different paths from "
                        + s + " to " + d);
        g.printAllPaths(s, d);
        findMeetingPoint(g);

        //System.out.println(g.allPaths);

        /*for (int d=0; d<=4; d++) {
            System.out.println(
                    "Following are all different paths from "
                            + s + " to " + d);
            g.allPaths.clear();
            g.printAllPaths(s, d);
            findMeetingPoint(g);
        }*/
    }

    private static void findMeetingPoint(Graph g) {
        if(g.allPaths.size()<=1) {
            System.out.println("No meeting point");
            return;
        }
        Set<Integer> intersects = new HashSet<>();
        Set<Integer> meetPoints = new HashSet<>();

        intersects.addAll(g.allPaths.get(0));

        for(int i=1; i<g.allPaths.size(); i++) {
            intersects.retainAll (g.allPaths.get(i));
        }

        for (Integer node: intersects) {
            if(g.adjList[node].size()==0)
                intersects.remove(node);
        }

        System.out.println("Meeting points: " + intersects);


    }
}

EDITTED 2 :

code which can handle cycles and without a defined destination:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

// A directed graph using
// adjacency list representation
public class Graph {

    // No. of vertices in graph
    private int v;

    // adjacency list
    private ArrayList<Integer>[] adjList;

    // Constructor
    public Graph(int vertices)
    {

        // initialise vertex count
        this.v = vertices;

        // initialise adjacency list
        initAdjList();
    }

    // utility method to initialise
    // adjacency list
    @SuppressWarnings("unchecked")
    private void initAdjList()
    {
        adjList = new ArrayList[v];

        for (int i = 0; i < v; i++) {
            adjList[i] = new ArrayList<>();
        }
    }

    // add edge from u to v
    public void addEdge(int u, int v)
    {
        // Add v to u's list.
        if(u != v)
            adjList[u].add(v);
    }

    // Prints all paths from
    // 's' to 'd'
    public void printAllPaths(int s)
    {
        boolean[] isVisited = new boolean[v];
        ArrayList<Integer> pathList = new ArrayList<>();

        // add source to path[]
        pathList.add(s);

        // Call recursive utility
        printAllPathsUtil(s, isVisited, pathList);
    }

    List<List<Integer>> allPaths = new ArrayList<>();

    private void printAllPathsUtil(Integer u, boolean[] isVisited, List<Integer> localPathList)
    {

        if (adjList[u].isEmpty()) {
            System.out.println(localPathList);
            allPaths.add(new ArrayList<>(localPathList));
            // if match found then no need to traverse more till depth
            return;
        }

        // Mark the current node
        isVisited[u] = true;

        // Recur for all the vertices adjacent to current vertex
        for (Integer i : adjList[u]) {
            if (!isVisited[i]) {
                // store current node in path[]
                localPathList.add(i);
                printAllPathsUtil(i, isVisited, localPathList);

                // remove current node in path[]
                localPathList.remove(i);
            }
        }

        // Mark the current node
        isVisited[u] = false;
    }


    // Driver program
    public static void main(String[] args)
    {
        // Create a sample graph
        Graph g = new Graph(8);
        /*g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 1);
        g.addEdge(1, 3);
        g.addEdge(2, 3);
        g.addEdge(3, 4);*/

        /*g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(1, 2);
        g.addEdge(2, 5);
        g.addEdge(3, 4);
        g.addEdge(4, 5);*/

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(1, 4);
        g.addEdge(2, 3);
        g.addEdge(2, 4);
        g.addEdge(3, 5);
        g.addEdge(4, 5);
        g.addEdge(5, 6);
        g.addEdge(5, 7);

        // arbitrary source
        int s = 0;

        // arbitrary destination
        System.out.println(
                "Following are all different paths from "
                        + s );
        g.printAllPaths(s);
        findMeetingPoint(g);
    }

    private static void findMeetingPoint(Graph g) {
        if(g.allPaths.size()<=1) {
            System.out.println("No meeting point");
            return;
        }
        Set<Integer> intersects = new HashSet<>();
        Set<Integer> meetPoints = new HashSet<>();

        intersects.addAll(g.allPaths.get(0));

        for(int i=1; i<g.allPaths.size(); i++) {
            intersects.retainAll (g.allPaths.get(i));
        }

        for (Integer node: intersects) {
            if(g.adjList[node].size()==0)
                intersects.remove(node);
        }

        System.out.println("Meeting points: " + intersects);

    }
}

input as:


g:{
 0: [1,2],
 1: [1,3,4],
 2: [3,4],
 3: [5],
 4: [5],
 5: [6,7],
 6: [],
 7: []
}
s=0

and output as:

Following are all different paths from 0
[0, 1, 3, 5, 6]
[0, 1, 3, 5, 7]
[0, 1, 4, 5, 6]
[0, 1, 4, 5, 7]
[0, 2, 3, 5, 6]
[0, 2, 3, 5, 7]
[0, 2, 4, 5, 6]
[0, 2, 4, 5, 7]
Meeting points: [0, 5]

You can use this link which provide Python code to find all paths, but need change like the proposed algorithm.

user_25274580
Related