Given a graph G,
enumerate all connected, vertex-induced subgraphs of G
up to a given size limit.
A subgraph S of G induced by the vertices
{v_{i1}, ..., v_{im}}
of G consists of those vertices with
⟨v_{ip}, v_{iq}⟩
being an edge in S iff it is an edge in G.
G may be undirected or directed;
in the latter case generate weakly connected subgraphs.
Note that a (sub-)graph must have at least one vertex
although having zero edges (the empty graph) is just fine.
First enumerate all subgraphs containing the
seed vertex v_{0}.
Next enumerate all subgraphs containing the
seed vertex v_{1} but not v_{0}.
Then enumerate all subgraphs containing the
seed vertex v_{2} but neither v_{0} nor v_{1},
and so on.
Given a seed, the process is recursive.
At each stage a vertex that is a neighbour of the current subgraph,
and that has not yet been considered,
is eligible to be added to the subgraph.
An eligible vertex, v, may be added or not added to the subgraph;
those are the two options for v and they are both explored recursively.
If v is added to the subgraph it may cause other vertices to become
neighbours of the enlarged subgraph.
The process backtracks whenever
the maximum size is reached or
there are no eligible vertices to add.
The current subgraph is processed whenever a new vertex is added to it.
-- L. A., Fri. 5th, Wed. 10th Sept. 2014.
Also search for [enumerate subgraph] in the
[Bib].