11
$\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.

Improve this question
$\endgroup$
9
  • $\begingroup$ could you post the code somewhere, on github, say? I can't get it from their ftp (sic!) server :-( $\endgroup$
    – Dima Pasechnik
    Commented Jan 25, 2023 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$
    – Licheng Zhang
    Commented Jan 25, 2023 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$
    – AccidentalFourierTransform
    Commented Jan 25, 2023 at 13:15
  • $\begingroup$ A similar link: mathematica.stackexchange.com/questions/241169/… $\endgroup$
    – Licheng Zhang
    Commented Jan 25, 2023 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$
    – Dima Pasechnik
    Commented Jan 25, 2023 at 20:50

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Licheng Zhang
    Commented Jan 25, 2023 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$
    – Brendan McKay
    Commented Jan 25, 2023 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$
    – Dima Pasechnik
    Commented Jan 25, 2023 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$
    – Brendan McKay
    Commented Jan 25, 2023 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$
    – Dima Pasechnik
    Commented Jan 26, 2023 at 10:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .