All subgraphs


May 2010

I am new to the forum and hope I am posting this in the correct place.

I need to find all the subgraphs (fragments) of a given number of nodes. The graph is not directional or weighted (yet). For now I just need to find all subgraphs of a given length. I tried DFS, and with some modification it can find all paths of the specified length (4 for example). However, it misses what I would refer to as fragments.

In the example below (hope it came out correct) I get (for length of 4) 1-2-3-6, 1-2-3-4, etc. However, I miss fragments that contain a branch like 6-3-2-4 (2 and 4 don't connect, rather they both connect to 3).

I'm struggling with a reasonable way to find all such subgraphs. Any ideas?

1 4 - 5
| |
2 - 3 - 6 - 7