CODEWITHSUNDEEP
pythonalgorithmgraphdepth-first-search
AndrejCoding
AndrejCoding

Reputation: 127

Python: Depth-First-Search (DFS) output post-order number

I want to find out which tuple-node with the same tuple elements (e.g. (1,1), (2,2) or (i, i)) is the source in a particular graph, i.e. which node has the highest post-order number. I want to find the source by applying DFS to it and take the number with the highest post-order number as my source node for further usage. Assume, you have the following graph:

graph={
    (1,1): [(1,2),(2,2)],
    (1,2): [(1,3)],
    (1,3): [(1,2),(2,3)],
    (2,2): [(3,3)],
    (2,3): [],
    (3,3): [(2,2)],
}

Now I have this iterative dfs function (I have to do it iteratively because I have a massive stack). I was not sure how to extend it to return the node with the highest post-order number.

def dfs_iterative_starting(graph, n):
    # n is the number different numbers (e.g. (1,1), (2,2) or (i,i))
    # array in which I'll save the post-order numbers. The index indicates the node, e.g. index 1 -> (1,1)
    arr = [0]*(n+1)
    # starting node is (1,1)
    stack, path = [(1,1)], []
    # counter for the post-order number
    counter = 1
    while stack:
        vertex = stack.pop()
        if vertex in path:
            continue
        path.append(vertex)

        # counting post-order number????
        i, j = vertex
        if i == j:
            arr[i] = counter
        for neighbor in graph[vertex]:
            stack.append(neighbor)

            # counting post-order number????
            k, j = neighbor
            counter += 1
            if k == j:
                arr[k] = counter
    print(arr)
    return arr.index(max(arr))

For the above-mentioned example, it returns 2 even though the correct answer would be 1. If I print arr, I get the following list [0, 1, 5, 4]

Upvotes: 1

Views: 889

Answers (1)

גלעד ברקן
גלעד ברקן

Reputation: 23945

In the recursive implementation, we'd have a subsequent operation to add to the post-order list the node whose neighbours we first explore. This has to be pushed to the stack first. It might help to distinguish what to do with the stack element. Here's one example:

JavaScript code (sorry, on smartphone and have no access to Python):

function f(graph){
  let stack = [['(1,1)', 'explore']];
  let path = new Set();
  let post_order = [];

  while (stack.length){
    let [vertex, action] = stack.pop();

    if (action == 'mark'){
      post_order.push(vertex);
      continue;
    }

    path.add(vertex);
    stack.push([vertex, 'mark']);

    for (let neighbour of graph[vertex]){
      if (!path.has(neighbour))
        stack.push([neighbour, 'explore']);
    }
  }
  
  console.log('Path: ' + JSON.stringify(Array.from(path)));
  
  return post_order;
}

var g = {
    '(1,1)': ['(1,2)','(2,2)'],
    '(1,2)': ['(1,3)'],
    '(1,3)': ['(1,2)','(2,3)'],
    '(2,2)': ['(3,3)'],
    '(2,3)': [],
    '(3,3)': ['(2,2)'],
}

/*
(1,1) -> (1,2) <-> (1,3) -> (2,3)
 \
 (2,2) <-> (3,3)
*/

console.log(JSON.stringify(f(g)));

Upvotes: 1

Related Questions