Counting Graphs with a Prescribed Degree Sequence (Scala Version)

Description of the problem

Earlier I explained the mathematical theory behind counting isomorphism classes of graphs that have a prescribed degree sequence. In that post, I also implemented a lisp version of the counting algorithm. Today, I am going to write a scala version of the same code.

Implementation

Scala does not have a framework/library to implement general memoization, but you can hand-roll one. I found the following on StackOverflow:

import scala.collection.mutable

def memoFix[A, B](f: (A => B) => A => B): A => B =
  val cache = mutable.HashMap[A, B]()
  lazy val g: A => B = a => cache.getOrElseUpdate(a, f(g)(a))
  g

def memoFix[A, B](f: (A => B) => A => B): A => B

which is the typed version of the hand-rolled lisp version I wrote long time ago.

After this, we can easily port the lisp code as follows:

val graphCount: List[Int] => BigInt = memoFix { self => ds =>
  ds match
    case List(1, 1)           => BigInt(1)
    case _ if ds.length < 3   => BigInt(0)
    case _ if ds.sum % 2 != 0 => BigInt(0)
    case first :: rest =>
      rest.indices.toList.combinations(first).map { is =>
        val idxSet = is.toSet
        self(rest.zipWithIndex
          .map((d, i) => if idxSet(i) then d - 1 else d)
          .filter(_ > 0).sorted)
      }.sum
}

val graphCount: List[Int] => BigInt = Lambda/0x000000005c5c4a08@3606eee9

Let us test this on the same examples:

graphCount(List(4, 4, 4, 4, 4))
graphCount(List(1, 1, 2, 2, 2))
graphCount(List(1, 1, 1, 1, 1, 1))
graphCount(List(3, 3, 3, 3, 3))
graphCount(List(3, 3, 3, 3, 3, 3))
graphCount(List(1,1,1,1,1,1,1,2,2,3,3,3,4,4,5,7))

val res0: BigInt = 1
val res1: BigInt = 7
val res2: BigInt = 15
val res3: BigInt = 0
val res4: BigInt = 70
val res5: BigInt = 21065283747

Now, for the large interesting examples. I’ll start with A001205 the number of 2-regular graphs on n vertices, n = 3..12

(3 to 12).map(n => graphCount(List.fill(n)(2)))

val res6: IndexedSeq[BigInt] = Vector(1, 3, 12, 70, 465, 3507, 30016, 286884, 3026655, 34944085)

Next, A002829 the number of 3-regular graphs on 2n vertices, n = 2..11

(2 to 11).map(n => graphCount(List.fill(2*n)(3)))

val res7: IndexedSeq[BigInt] = Vector(1, 70, 19355, 11180820, 11555272575, 19506631814670, 50262958713792825, 187747837889699887800, 976273961160363172131825, 6840300875426184026353242750)

A005815 the number of 4-regular graphs on n vertices, n = 5..15

(5 to 15).map(n => graphCount(List.fill(n)(4)))

val res8: IndexedSeq[BigInt] = Vector(1, 15, 465, 19355, 1024380, 66462606, 5188453830, 480413921130, 52113376310985, 6551246596501035, 945313907253606891)

and finally A338978 the number of 5-regular graphs on 2n vertices, n = 3..14

(3 to 14).map(n => graphCount(List.fill(2*n)(5)))

val res9: IndexedSeq[BigInt] = Vector(1, 3507, 66462606, 2977635137862, 283097260184159421, 52469332407700365320163, 17647883828569858659972268092, 10148613081040117624319536901932188, 9494356410654311931931879706070629989407, 13859154719468565627065764000731047706917194485, 30467359843410315617245696171806527102000553683468790, 97852745740262121632666427672231508891042342116161424342990)