I am using the NetworkX library for Python in my application that does some graph processing. One task is to call the all_simple_paths() function of NetworkX to give me all non-looping paths in the graph (up to a certain max. length of paths). This is working well.
Using this list of all simple paths in the graph the task is now to find a number of n paths out of this list, where each of these n paths should be as different from all other n paths as possible. Or in other words: any two paths from the resulting n paths should have as few common nodes as possible. Or in even other words: each path in the resulting n paths should be as unique as possible.
Can you guys think of any (non brute force) algorithm to achieve this?
You could create a similarity or distance between two paths based on the number of edges that they share. Then apply a clustering algorithm to find n clusters, and pick one representative from each cluster, perhaps in a greedily fashion to minimise (in the case of similarities) edge weights between representatives.
How to find n most different paths in a graph?