What packages for subgraph enumeration are available?

Question

In learning about network motifs, I discover claims that Mfinder (circa 2004) is the "the first motif-mining tool" (Kashani et al. 2009). Motifs are connected induced subgraphs that occur more frequently than in "similar random graphs" (these graphs may be directed or undirected).

While Mfinder might be the first specifically aimed at finding motifs, I suspect there will have been earlier packages that could count the number of induced subgraphs isomorphic to a small graph H in a large graph G.

Question: What are some earlier packages that enable counting the number of induced subgraphs in G that are isomorphic to some given small graph H?

After Mfinder a range of motif finding packages have been developed. The ones I've heard of are MAVisto, FanMod, NoMoFinder, an unnamed package by Grochow and Kellis and Kavosh. I'd also be interested in hearing about any other packages that can perform subgraph enumeration.

Answer 1

Sagemath has three methods that can let you :

* detect a small subgraph -- induced or not, you can chose
  http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.subgraph_search
* iterate the different occurences
  http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.subgraph_search_iterator
* count them
  http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.subgraph_search_count

All three are about labelled occurences, so if you count the number of occurences of a $C_6$ in a $C_6$, you will find

sage: g = graphs.CycleGraph(6)
sage: g.subgraph_search_count(g)
12

Hopefully, you can divide the number by the cardinality of the automorphism group

sage: g.subgraph_search_count(g)/g.automorphism_group().order()
1