9
$\begingroup$

I know the following problem is famous:

  • For a given degree sequence $L$ that is graphic, find an (efficient) algorithm to generate all of the nonisomorphic realizations of $L$.

This algorithm is sometimes helpful when we gather experimental evidence for conjectures (or as part of a proof).

There are many such articles, but the implementation of algorithms seems very few. I recently saw the following article, which provides the software gradpart.

But because the code was written around 1995, it is difficult for today's compilers to make it (due to the constant updating of the C++ standard).

I read the author's description and it looks like it can quickly generate all nonisomorphic graphs by a given degree sequence.

enter image description here

In this example you can see a degree-partition with 50 vertices. Here we have 2 vertices of degree 1, 10 vertices of degree 2, 8 vertices of degree 3,... . Because of the use of the homomorphism-principle, during the generation we may obtain situations, where the operating group is trivial. So we get the possibility to describe large sets of pairwise non-isomorphic solutions implicitly. In this way in the shown example, we computed 34824038400 graphs in about 25 seconds and are also able to store these graphs with a very small amount of space.

I know nauty is great, but it seems not to offer this feature (except for generating regular graphs). Especially for cases with a slightly higher number of vertices (e.g. more than 15 vertices)

It is not clear if there is an alternative math software, or if there is a later version of gradpart for using it today. If there is an updated version of the software gradpart, we would love to see it play a role in the discovery of theorems.

$\endgroup$
8
  • $\begingroup$ could you post the code somewhere, on github, say? I can't get it from their ftp (sic!) server :-( $\endgroup$ Jan 25 at 12:26
  • $\begingroup$ Ok, I have put it in GitHub: github.com/lichengzhang1/gradpart. The original linked file can be downloaded after modification (accidentally found) : ftp.mathe2.uni-bayreuth.de/gruener/gradpart.tar.gz $\endgroup$
    – lcz
    Jan 25 at 12:43
  • 1
    $\begingroup$ FWIW, I asked a similar question on Mathematica here: mathematica.stackexchange.com/q/170268/34893 where I also proposed a simple attempt, although it is a very inefficient one. $\endgroup$ Jan 25 at 13:15
  • $\begingroup$ A similar link: mathematica.stackexchange.com/questions/241169/… $\endgroup$
    – lcz
    Jan 25 at 13:26
  • 1
    $\begingroup$ Thanks - the README (LIESMICH - in German) basically says that one can make Gradpart in order not to build the GUI. That's a relief. However, the C++ dialect is very, very old, and apparently the code does not even use C++ STL (indeed, STL only appeared in 1994, and this code dates back to 1996). Instead there are home-made templates (in *.t files). $\endgroup$ Jan 25 at 20:50

1 Answer 1

8
$\begingroup$

As far as I am aware, there is no such program. Also, it needs care to interpret gradpart's claims. Gradpart can make counts greater than one graph per machine instruction, which proves that it doesn't individually construct each graph in memory. Instead it makes data structures which represent large subclasses of graphs. The mapping from these data structures to lists of graphs is relatively routine, but it isn't carried out.

$\endgroup$
6
  • $\begingroup$ Thank you for the reminder. I have not been able to use this software successfully, and thus I cannot check this. I don't know if Gradpart give a implementation for generating all non-isomorphic graphs with a given degree sequence. Perhaps I misunderstood their statement. $\endgroup$
    – lcz
    Jan 25 at 5:57
  • 1
    $\begingroup$ @lcz I can't compile it either, and there is no documentation in the package. As far as I am aware (and I can be wrong) this program counts graphs rather than generates them. I'll post more here if I learn more. $\endgroup$ Jan 25 at 11:46
  • 1
    $\begingroup$ One probably would need to strip off its GUI to make it build. A 35-y.o. GUI in C++ is certainly easier to do from scratch than to build :-) $\endgroup$ Jan 25 at 12:20
  • 1
    $\begingroup$ @lcz Ok, I am told it could write the graphs. However that must have been much slower than counting them for the examples given. $\endgroup$ Jan 25 at 12:35
  • $\begingroup$ Probably modifying nauty to do the job (it should not be much harder than enumeration of the regular graphs) is more productive than trying to resurrect that code. (I commented above that the code provides a way to skip building GUI). $\endgroup$ Jan 26 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.