CODEWITHSUNDEEP
pythongraphtreenetworkxvertices
Jon
Jon

Reputation: 612

How to find the paths between vertices with degree > 2 in a directed tree graph?

I have no training in graph theory, so my terminology is poor. I have a directed tree graph that has "redundant nodes." I am defining "redundant nodes" as those with degree=2 in my tree graph. I would like to find an efficient way to return all the paths between all non-redundant nodes, preferably using NetworkX (Python) tools. This really simple graphic demonstrates what I'm trying to achieve:

enter image description here

So given this graph, I'd like to return three paths (p1, p2, and p3) that represent the connections between 1->4, 5->4, and 4->7.

I can write an algorithm to do this "manually", in the sense that I start at nodes with degree=1 and "walk" along the graph until I hit another non-degree=2 node. However, I suspect that there is already a formalized way to do this kind of analysis, but I can't seem to figure it out.

For more context, my graphs are much larger and more complicated as they're representations of river networks, something like this:

enter image description here

But they're always trees, no cycles.

Upvotes: 1

Views: 353

Answers (2)

ravenspoint
ravenspoint

Reputation: 20616

LOOP over all nodes
    calculate degree
    IF degree == 2
       add to vector deg2
LOOP over all nodes in deg2 to get src
    LOOP over all nodes in deg2 starting at src+1 to get dst
        find path from src to dst ( dijsktra algorithm )

Upvotes: 1

Prune
Prune

Reputation: 77910

No, I'm afraid that you've already hit the most effective way to do your mini-paths. You can speed up the processing slightly by working backward from a confluence node, but that's about all you can improve. Doing so will let you remove intermediate nodes a little more effectively than simply looking for source nodes (which you still have to do). However, that algorithm is not as simple. For now, I suggest that you stick with the simple design you already have.

  • Put all nodes into a set to_visit.
  • while to_visit is not empty:
    • node = to_visit.pop()
    • if node has degree 1: # source node: find path to confluence
      • trace path until you hit a node of degree > 2.
      • delete all intermediate nodes from to_visit.
      • emit path.

Upvotes: 2

Related Questions