How can I simplify the description of the routes while they still are unique?

Question

If I for an example have a graph like this:

                     -- 528a - 526 -
                    /               \
380 - 404 - 420 - 522 - 530 - 526a - 686 - 564
                          \                /
                           ------ 540 -----

Traverseing it from start (380) to end (564) results in following routes

 1. 380 404 420 422 522 528a 526  686 564 
 2. 380 404 420 422 522 530  526a 686 564
 3. 380 404 420 422 522 530  540  564

How can I simplify the description of the routes while they still are unique? In other words: Find nodes between start and end that define the route together with start and end?

In this example I want it to boil down to this result.

 1. 380 404 420 422 522 528a 526  686 564  =>  380 528a 564 OR 380 526 564 
 2. 380 404 420 422 522 530  526a 686 564  =>  380 526a 564 
 3. 380 404 420 422 522 530  540  564      =>  380 540  564

I'm looking for an algorithm that not doing trial and error by traversing the graph.

Thank you for any help or tips

Answer 1

Idea:

• Record the start node as permanent.

• After the path has split:

  • Remove the last recorded node if it's not permanent and

  • Record the current node.

• If the path merges, make the last node permanent.

• Record the end node.

To check if a path splits, you'll need to check how many children a node has (most graph implementations should store this).

To check if a path merges, you'll need to check how many parents a node has (which most graph implementations probably won't store).

The idea with making nodes permanent is to prevent removing 2 or 3 here:

    2       5
  /   \   /   \
1 - 3 - 4 - 6 - 7

I also must add that I'm not particularly sure why you are recording the start and end nodes, since these are the same for all your examples, unless they can be different for other examples.

Examples:

Graph:
                     -- 528a - 526 -
                    /               \
380 - 404 - 420 - 522 - 530 - 526a - 686 - 564
                          \                /
                           ------ 540 -----

Input: 380 404 420 422 522 528a 526 686 564

Splits before 528a, so record it.
Make 528a permanent at 686.

Output: 380 528a 564


Input: 380 404 420 422 522 530  526a 686 564

Splits before 530, so record it.
Splits before 526a, so remove 530 and record 526a.
Make 526a permanent at 686.

Output: 380 526a 564


Input: 380 404 420 422 522 530  540 564

Splits before 530, so record it.
Splits before 540, so remove 530 and record 540.
Make 540 permanent at 564.

Output: 380 540 564