Say I have a undirected graph (can be cyclic or acyclic), where each node is asigned with an integer state. I want to find the path that:
As an example, I have a cyclic graph -5-4-5-7-2- (first 5 and last 2 are connected). If we start from the first 5 and end at the last 2, the sum of the changes of each move will be -1 + 1 + 2 + (-5) = -3. The graph can be described by an adjacency matrix as follows:
import numpy as np
node_states = [5, 4, 5, 7, 2]
# Adjacency matrix
#5 4 5 7 2
am = np.array([[0,1,0,0,1], # 5
[1,0,1,0,0], # 4
[0,1,0,1,0], # 5
[0,0,1,0,1], # 7
[1,0,0,1,0]])# 2
The expected output is
max_delta_sum_path = [2, 5, 4, 5, 7]
where the path has the largest sum 3 + (-1) + 1 + 2 = 5
Anyone knows if there is any relatively fast algorithm that can automatically find this path?
I think this is what you're looking for:
import numpy as np
node_states = [5, 4, 5, 7, 2]
# Adjacency matrix
#5 4 5 7 2
am = np.array([[0,1,0,0,1], # 5
[1,0,1,0,0], # 4
[0,1,0,1,0], # 5
[0,0,1,0,1], # 7
[1,0,0,1,0]])# 2
for i in range(len(node_states)):
for j in range(len(node_states)):
if am[i][j] == 1:
am[i][j] = node_states[i] - node_states[j] # go through ever entry in every list, and if it is 1 replace it with the traversal cost
"""
am = [[ 0 1 0 0 3]
[-1 0 -1 0 0]
[ 0 1 0 -2 0]
[ 0 0 2 0 5]
[-3 0 0 -5 0]]
"""
from itertools import permutations
def largest_sum(node_states, am):
largest = None
largest_journey = None
traversal_list = list(permutations(range(len(node_states)), len(node_states))) # store all possible permutations of node_states indexes
for trav in traversal_list: # go through each permuatation
costs = [] # track the cost of each traversal
for i in range(len(trav)):
if i == 0: # there are one less traversals than nodes so we are ignoring the first node
continue
if am[trav[i]][trav[i-1]] == 0: # traversal cannot happen if the traversal has no adjacency
continue
costs.append(am[trav[i]][trav[i-1]]) # use the updated am matrix to get our costs, and store them here
if len(costs) == len(node_states) - 1: # if one less traversal was made than we have nodes, we know all nodes were visited
costs_sum = sum(costs) # sum the costs for our total of travel
if largest is None or largest < costs_sum: # only keep this total if it was bigger than our old total
largest = costs_sum # track the new total
largest_trav = list(map(lambda x: node_states[x], trav)) # change our array of indexes (trav) into an array of node values
return largest_trav # when the looping is done, return our total
out = largest_sum(node_states, am)
print(out)
Output:
[2, 5, 4, 5, 7]