find all continuous path segments in an undirected graph

Question

I have an undirected graph, like the following:

.      C
.    /   \   
.   B      F
.  /      / \
. A      D   E

The edges are:

A-B
B-C
C-F
D-F
E-F

I want to identify every continuous path segment in this graph, which is: (nodes of each path given in alphabetical order)

A, B, C, D, E, F, AB, BC, CF, DF, EF, ABC, BCF, CDF, CEF, DEF, ABCF, BCDF, BCEF, CDEF, ABCDF, ABCEF, BCDEF, and ABCDEF

Is there a name for this task? Any relevant algorithms?

Thanks!

Answer 1

Perhaps I'm overinterpreting the example and its presentation in the Question, but if the problem is determining all simple (no retracing edges) paths in an undirected cycle-free connected graph, i.e. a tree, there is a simple Answer.

Given there are $n$ nodes in the tree, any pair of (not necessarily distinct) nodes uniquely determines a simple path (trivial in the case of identical nodes). Thus there are $n$ trivial paths (no edges) and $\binom{n}{2}$ nontrivial paths (at least one edge), for a total of $\frac{n(n+1)}{2}$ paths. This agrees with the example, having $n=6$ nodes and $24$ paths.

If the task were to generate all pairs paths, then Johnson's algorithm, with all edges having weight 1, would be attractive. More discussion of that task in this previous Question.