CODEWITHSUNDEEP
pythongraph
Sujin
Sujin

Reputation: 273

Asking for advice to list all the longest path using adjacency list python

I am writing to ask the recommendation and suggestion for finding and list the longest path due to I am a newbie for graph structure.

enter image description here

according to my purpose is to find the longest path in the directed acyclic graph. I have found this blog and apply some parts of code to fit with my data. https://www.geeksforgeeks.org/longest-path-in-a-directed-acyclic-graph-dynamic-programming/

    def dfs(node, adj, dp, vis): 

        # Mark as visited 
        vis[node] = True

        # Traverse for all its children 
        for i in range(0, len(adj[node])): 

            # If not visited 
            if not vis[adj[node][i]]: 
                dfs(adj[node][i], adj, dp, vis) 

            # Store the max of the paths 
            dp[node] = max(dp[node], 1 + dp[adj[node][i]]) 

    # to add an edge 
n = len(adj_Matrix)

## change to adjacency list to decrease the space that have kept zero.

adj = [[] for i in range(n + 1)] 

for i in range(len(adj_Matrix)):
    for j in range(len(adj_Matrix)):
        if(adj_Matrix[i][j] == 1):
            adj[i].append(j)


    # Function that returns the longest path 
    def findLongestPath(adj, n): 

        # Dp array 
        dp = [0] * (n + 1) 

        # Visited array to know if the node 
        # has been visited previously or not 
        vis = [False] * (n + 1) 

        # Call DFS for every unvisited vertex 
        for i in range(1, n + 1): 
            if not vis[i]: 
                dfs(i, adj, dp, vis) 

        ans = 0

        # Traverse and find the maximum of all dp[i] 
        for i in range(1, n + 1): 
            ans = max(ans, dp[i]) 

        return ans

the code returns the result 10 as my directed paths but I would like to ask for your advice about how can I get the list of all the longest paths in this issue? any recommended blogs I need to study?

for example, according to the blog, the result returns with the max value from the array but I would like to see the result return the list of the longest path in each node like:

node 1: 1->3->2->4
node 2: 2->4
node 3: 3->2->4
node 4: Null

thank you in advance for all suggestions

Upvotes: 2

Views: 1021

Answers (1)

wxker
wxker

Reputation: 1896

Store the path together with the length in dp

def dfs(node, adj, dp, vis): 
    # Mark as visited 
    vis[node] = True
    # Traverse for all its children 
    for i in range(0, len(adj[node])): 
        # If not visited 
        if not vis[adj[node][i]]: 
            dfs(adj[node][i], adj, dp, vis) 
        # Store the max of the paths 
        dp[node] = max(dp[node], [node] + dp[adj[node][i]], key=lambda x: len(x))

# Function that returns the longest path 
def findLongestPath(adj, n): 
    # Dp array 
    dp = [[x] for x in range(n + 1)]
    # Visited array to know if the node 
    # has been visited previously or not 
    vis = [False] * (n + 1) 
    # Call DFS for every unvisited vertex 
    for i in range(1, n + 1): 
        if not vis[i]: 
            dfs(i, adj, dp, vis) 
    # Traverse and find the maximum of all dp[i] 
    return max([dp[i] for i in range(1, n + 1)], key=lambda x: len(x))

dp now stores all the longest paths from each node. To retrieve a list of all these paths, we can slightly modify the function.

def findLongestPathFromEachNode(adj, n): 
    # Dp array 
    dp = [[x] for x in range(n)]
    # Visited array to know if the node 
    # has been visited previously or not 
    vis = [False] * (n + 1) 
    # Call DFS for every unvisited vertex 
    for i in range(1, n + 1): 
        if not vis[i]: 
            dfs(i, adj, dp, vis) 
    # Traverse and find the maximum of all dp[i]
    return dp[1:]

Upvotes: 3

Related Questions