Short Version:
Is there a way to uniquely specify the set of graphs that can represent juggling patterns of length $n$ (or of any length less than $n$, if that's easier)? A necessary condition (but not sufficient, see the addendum) is that the graphs have a closed walk of length $n$ that visits every vertex and uses every edge at least once. See my other question here for more on counting these "walk covers". These graphs must be directed, connected, bridgeless, and have at most $n$ edges, but these conditions alone are not nearly sufficient.
Independent of whether one can uniquely specify these graphs, is there an efficient way to generate them? I wrote some Mathematica code using the nauty suite, specifically the geng, directg, and pickg tools from the gtools package, but it generates many invalid graphs, so I've been forced to filter out the ones that don't have walk covers of length $n$, which is rather slow.
Long Version:
Apologies in advance for any misuse of terminology. I am a physics grad student who only recently became interested in this topic.
I've been investigating juggling patterns, which can be related to closed walks in a directed bridgeless non-simple graph known as the juggling state graph, where the vertices represent various arrangements of the balls in the air, and the edges represent throws that connect these states. This graph is "minimally" non-simple, as it only has one self-loop, connecting the so-called "ground state" to itself. For more on the juggling state graph, see here.
A prime juggling pattern is one that does not repeat any states and thus cannot be "factored" into smaller sequences. These patterns therefore correspond to loops in the juggling state graph, where the walk in the graph corresponding to the juggling pattern traverses the loop only once. A composite juggling pattern can be factored into smaller prime patterns. The subgraphs corresponding to composite patterns can take a variety of shapes. For example, here are the possible subgraphs that can represent composite juggling patterns of length $n=4$:
And here are the subgraphs for composite juggling patterns of length $n=5$:
Note that the number of edges need not equal $n$, as repeating edges is allowed. More (up to $n = 8$) can be seen here.
My first question is, is there a way to specify these graphs with some terminology from graph theory? The answer might just be "the set of all graphs with a nonzero number of walk covers of length $n$," but I'm hoping there's a smarter way to get at the same list. There's definitely some combinatorial way to look at this, since each graph corresponds to a partition of $n$, but it's not a one-to-one mapping. (For example, the second, fifth, and sixth graphs for $n=5$ above all correspond to the partition 6 = 1 + 2 + 2).
Whether or not one can succinctly identify these graphs, I would also like to find a better way to generate them. I have very limited knowledge of the IGraph/M Mathematica package, as well as the gtools package of the nauty suite, and I put together something that seems to work, but is rather slow for large $n$.
Here's a detailed explanation of my process. The various gtools programs don't seem to be able to generate non-simple graphs, so I have to manually add a self-loop to every vertex of every graph at the end. They also don't seem to be able to generate directed graphs from scratch, so I have to make undirected graphs to serve as the skeletons for the directed graphs.
For juggling patterns of length $n$, I first generate the undirected skeletons. These are all the connected undirected graphs with $V$ vertices and $E$ edges, with $2 \leq V \leq n-1$ and $1 \leq E < k$, where $k = \text{min}(2V,n)$. This can be done by repeated using the geng script, iterating over $V$. For example, here are the skeletons for $n = 5$:
The fourth, fifth, and sixth won't actually end up forming any valid subgraphs for $n = 5$, but I don't know how to filter these out with geng. I then pipe this output into the directg program, which takes the skeletons and orients their edges in all possible ways. This produces many graphs (81, 590, and 4400 for $n=5$, 6, and 7), even after I limit the edge number to $\text{min}(2V,n)$. The vast majority of these graphs are not strongly connected, i.e., they have at least one vertex that has in-degree or out-degree equal to zero, and thus are invalid. I can filter these out with the pickg program, but it would presumably be faster if I could stop directg from generating them in the first place.
I then add a self-loop to every vertex, removing any isomorphic graphs in the process. This is one of the slower parts of the code, though unless I'm mistaken about the inability of gtools to produce non-simple graphs, there's probably not a better way to do it.
I now have a set of strongly connected directed graphs with the right number of edges and vertices to potentially represent a juggling pattern of length $n$. But as it turns out, as $n$ increases, the fraction of the graphs that actually do so becomes quite small (54/243, 170/1109, and 496/5605 for $n=7$, 8, and 9). Some of the invalid graphs are obvious, such as a single $k$-cycle where $k$ is not a factor of $n$, but many are not. For example, here are some of the invalid graphs for $n=5$:
Extracting these relatively few valid graphs is also quite slow, as I have to test each graph to see if it has a walk cover of length $n$. My code for this test is pretty fast (thanks to user Onir's solution to my previous question here), but when it's applied to thousands of graphs with many edges, it slows things down a lot, even if it's mostly outputting zeros.
Thus my second question is, is there a way to filter out these invalid graphs without just testing to see if they have the right number of walk covers, possibly getting the gtools package to not generate them in the first place?
Addendum:
It turns out that requiring the number of walk covers of the subgraph of length $n$ to be non-zero is necessary but not sufficient to guarantee the existence of a juggling pattern for that subgraph, as the subgraph must actually appear inside the juggling state graph. For example, it turns out that all the two-cycles in a juggling state graph form a "chain" connected to the ground state. Thus graphs like the following won't actually ever appear in a juggling state graph:
There are others that don't ever show up, but exactly why isn't as clear. For example:
Presumably the three-cycles in a juggling state graph are also always arranged in a particular way to exclude these subgraphs.
I didn't want to bring this up in the main question, since it relies on the actual structure of the juggling state graph, and focusing on just finding graphs with non-zero walks seemed more manageable. But it is worth noting that this is not strictly sufficient.