Find guaranteed ancestors in directed graph

user_5736983 0
Viewed 352

I'm trying to implement an algorithm to find what I call 'guaranteed ancestors' in a directed graph. I have a list of nodes which each can point to zero, one or multiple child nodes.

Below you see an example of a simple graph. I've marked all circles with a unique number.

Let's imagine we're trying to determine which nodes I'm guaranteed to have visited before reaching node 13 starting at node 0.

enter image description here

My thoughts when solving this simple example by hand is starting in node 13 and working my way back, which nodes am I guaranteed to visit no matter which direction I go. The first node I notice obeying this property is node 10, since no matter if I choose to visit node 11 or node 12, then I'm guaranteed to eventually reach node 13. Similarly I can conclude I have to visit node 9 if I want to reach node 13. Working all the way up the graph I conclude that node 13 has node 0, 1, 9, 10 as it's guaranteed anchestors.

I'm not sure what such an algorithm is called, but I'm sure there is a name for this specific search.

Here is the constraints you can assume about my graph.

  1. There is a single defined "head/root" node, which is the only node without any other nodes pointing to it.
  2. The graph is acyclic (Ideally the algorithm would be able to handle cycles too, but I have a different check, verifying that the graph is acyclic, so this is not a must.)
  3. There is no "dead" nodes, eg. nodes which can't be reached from the head/root node.

This has to run on more complicated graphs with up to 500 nodes and many nodes with multiple "parents", which could be connected back and forth. Runtime is a priority as well - I assume we should be able to solve this problem in linear time complexity.

I've tried simplifying the problem to the point where I tried making an algorithm which could determine if a single node was a guaranteed anchestor of another node, which I believe is pretty simple to determine in O(n), however if I want a complete list of all guaranteed anchestors I assume I'd have to run this algorithm for every node, leaving me with O(n^2).

Does anyone know the correct name of the algorithm I'm describing?

directed-acyclic-graphs graph-theory graph-algorithm algorithm
2 Answers
  1. Assign a weight of 1 to every edge
  2. Run Dijkstra to find shortest path between head and root.
  3. Assign weight of 2 * ( edge count of graph ) to every edge in path
  4. Run Dijkstra to find cheapest path
  5. Identify edges that are present in both paths. ( they could not be avoided although very expensive )
  6. The nodes at both ends of every edge identified in 5 will be critical - i.e they must ALL be visted by any route between head and root.

Consider an example:

enter image description here

The first Dijkstra run would return a path containing node 1 or 2 ( they both belong on 5 hop paths. The second run would return a path containing the other of those two nodes

user_165820

This is almost what the definition of an articulation or cut vertex is in an undirected graph. See Biconnected component:

a cut vertex is any vertex whose removal increases the number of connected components.

The difference is that your graph is directed, and that you consider the root also as such a vertex.

So my suggestion is to temporarily consider the graph to be undirected, and to apply a depth-first algorithm to identify such cut vertices, and include the root.

The algorithm is given as pseudo code in the same Wikipedia article. I have rewritten it in JavaScript, so it can be run here for the graph that you have given as example:

function buildAdjacencyList(n, edges) {
    // Indexes in adj represent node identifiers. 
    // Values in adj are lists of neighbors: start out with empty lists
    let adj = [];
    for (let i = 0; i < n; i++) adj.push([]);
    for (let [start, end] of edges) {
        adj[start].push(end  );
        adj[end  ].push(start); // make edge bidirectional
    }
    return adj;
}

function markArticulationPoints(nodes, node, depth) {
    node.visited = true;
    node.depth = depth;
    node.low = depth;
    for (let neighborId of node.neighbors) {
        let neighbor = nodes[neighborId];
        if (!neighbor.visited) {
            neighbor.parent = node;
            markArticulationPoints(nodes, neighbor, depth + 1);
            if (neighbor.low >= node.depth) node.isArticulation = true;
            if (neighbor.low < node.low) node.low = neighbor.low;
        } else if (neighbor != node.parent && neighbor.depth < node.low) {
            node.low = neighbor.depth;
        }
    }
}
    
function getArticulationPoints(adj, root) {
    // Create object for each node, having meta data for algorithm
    let nodes = [];
    for (let i = 0; i < adj.length; i++) {
        nodes.push({
            neighbors: adj[i],
            visited: false,
            depth: Infinity,
            low: Infinity,
            parent: -1,
            isArticulation: i == root // root is considered articulation point
        });
    }

    markArticulationPoints(nodes, nodes[root], 0); // start DFS algorithm
    
    // Collect articulation points from meta data
    let result = [];
    for (let i = 0; i < adj.length; i++) {
        if (nodes[i].isArticulation) result.push(i);
    }
    return result;
}
        
// Build adjacency list for example graph, but with undirected edges
let adj = buildAdjacencyList(14, [
    [0, 1],
    [1, 2],
    [1, 3],
    [2, 4],
    [2, 5],
    [4, 5],
    [4, 6],
    [3, 7],
    [7, 8],
    [6, 9],
    [8, 9],
    [9, 10],
    [10, 11],
    [10, 12],
    [11, 13],
    [12, 13]
]);

let result = getArticulationPoints(adj, 0);

console.log("Articluation points:", ...result);

user_54598390
Related