How to Find Shortest Path Back to Self in a Graph/Adjacency Matrix - NetworkX

user_5819072 0
Viewed 153

I've got a problem where I need to find a connected loop within an adjacency matrix. I'd like to find a loop that connects back to the original node over x hops. shortest_path algorithms provided by NetworkX do not provide an option for a node to be the same source and target.

For an example, this is the graph, and I'd like to find three colors with the largest distance between each other:

enter image description here

This might be represented similar to:

erdos-renyi graph

SOLUTIONS THAT DIDN'T WORK

Modification of shortest path algorithm (route from a node to itself)

There is a post here that mentions potentially setting weights or distances to infinite along the diagonal, but it doesn't appear networkx.all_shortest_paths, and any of the pathing algoirthms respect the self-loops as seen below:

enter image description here

networkx python
1 Answers

The only way I could figure out how to do this was using simple_cycles and then iterating through all cycles/loops to figure out what the distance might be:

cycles = [p for p in nx.simple_cycles(G)]

num_nodes = 3
for nodes in cycles: 
  if (len(nodes) != num_nodes): 
    continue
  print(nodes)
  total = 0
  node_pairs = list(walk_list(nodes,2,1))

  for pair in node_pairs: 
    if len(pair) == 2: 
      total += G[pair[0]][pair[1]]['weight']
    else: 
      total+= G[pair[0]][nodes[0]]['weight']


  print(f"Total Distance: {total}")

Does someone have a better solution?

user_58190720
Related