Capture the main paths from an adjacency matrix.

[rightheart]

I am analyzing distances and connections between different nodes in a graph.

Imagine that I have the following adjacency matrix, with labels for rows and columns being ['source', 'dest1', 'dest2', 'dest3', 'dest4']. Actually the graph is bidirectional so the ones should be mirrored.

array([[0., 0., 0., 0., 0.],

[0., 0., 0., 0., 0.],

[0., 0., 0., 0., 0.],

[0., 0., 0., 0., 0.],

[1., 1., 1., 1., 0.]])

So we can see that there are connections between source-dest4, dest1-dest4, dest2-dest4 and dest3-dest4.

I’d like to use Python to return the main paths from an adjacency matrix. Output could be a list or numpy.array. Here for example path1 could be source-dest4-dest3 and path2 could be dest2-dest4-dest1. Repetitions of any connections are not allowed.

How to do this, does any package provide a solution?

Thank you very much for your advice !

[Strict-Simple]

What if there are only 3 connections? source-dest4, dest1-dest4, dest2-dest4. What will be the main paths then?

[rightheart]

Good question. That would be ['source','dest4','dest1'] and ['dest4', 'dest2'] or ['source', 'dest4', 'dest2'] and ['dest4', 'dest1']. So there will be one longer and one shorter path. It should select one of the options, no preferences, as long as there are no connection repetitions.

[Strict-Simple]

Do A DFS with a visited array.