How to generating all flats of the cycle matroid of a graph?

Question

If $M$ is a matroid, I can use M.flats(k) in SageMath to list all the flats of rank $k$. But I hope that there is an algorithm or program to list all flats of the cycle matroid of a graph. And do not use the language of matroids in this process. In the paper "GRAPH COMPOSITIONS I: BASIC ENUMERATION", a composition of G is defined as a partition of V(G) into vertex sets of connected induced subgraphs of G. All the compositions of a graph G exactly corresponds to the flats of M(G)。 So my problem may be changed to "how to list all the compositions of a graph G".

Answer 1

Give the edges of the graph distinct weights. Then the flats are in 1-1 correspondence with the minimal forests, where a forest is defined to be minimal if no other lower-weight forest spans the same components.

You can define a tree structure on the minimal forests, where the parent of a minimal forest is obtained by deleting its heaviest edge. The root of this tree structure is the forest of single-vertex trees. Then the children of each minimal forest F are formed by choosing two components of F, and adding the lightest edge between them, as long as it is heavier than the previous heaviest edge.

Finding the parent of a given minimal forest is obviously easy. And you can list all the children of a given minimal forest in linear time, by labeling each heavy-enough edge by the pair of components it connects, radix sorting the edges by these pairs of labels, and for each set of edges with the same pair of labels, keeping only the lightest one.

One can then find all minimal forests by traversing the tree structure starting from the root. At any given tree, the next tree is found by going to the first child (if there are any children) or following parent links back up the tree structure until finding a parent for which we are not backtracking from the last child, and then going to the next child. Each link in the tree structure takes time linear in the input graph size to traverse, so the total time is linear per generated minimal forest. You only need enough space to remember two forests (the one you are at now and the one you just came from).

In the same linear time per generated object you can generate the flats themselves, not just the minimal forest. For any given minimal forest, the corresponding flat is the set of edges that connect pairs of vertices in the same tree of the forest. So label all vertices with which tree they are in and loop through all the edges checking which of them have the same label at both endpoints.

(This is an instance of "reverse search"; for the general design of enumeration algorithms with this technique, see Avis & Fukuda, "Reverse search for enumeration", Disc. Appl. Math. 1996. I don't know offhand of references for the specific problem of enumerating flats of graphs.)

Answer 2

Matroids: A Geometric Introduction page 55 gives the theoretic result in purely graph theoretic terms in the last two sentences of this quote:

While it is pretty easy to pick out the flats from the picture of the geometry, it is a bit more difficult to find the flats of a graphic matroid from its graphic representation. To describe the flats of a graphic matroid, we consider a graph G = (V, E) and a subset F of the edges E. Note that the graph (V,F) has various connected components. Then, loosely speaking, F forms a flat in a graphic matroid if adding any edge to F reduces this number of connected components. More precisely, we let Π be a partition of the vertices of G, and then let FΠ be those edges of the graph both of whose endpoints are contained in the same part of the partition. Then FΠ forms a flat of M(G).

It shouldn't be hard for you to implement this for graphs. But doing that misses the point of matroid theory which tells us that we can write the code once in the more general setting and then apply it to graphs as a particular case.