search

elh / feynman-781

Simple graph generator for Feynman diagrams*
MIT License
2 stars 0 forks source link
graph graph-generation

readme

Feynman diagram generator ⚛️

A simple generator of "Feynman diagram" permutations (as defined by problem 781). Incrementally builds isomorphically unique graphs in a compact adjacency representation using backtracking at over 13M results a second on my 2020 Macbook.

Implemented quickly to play around with program optimizations (see https://github.com/elh/feynman-781/issues/16), graph traversals, and to try out Rust for the first time. 🦀

Problem 781?

This is NOT a solution for the problem whose math is left as an exercise for the reader. Good luck.

This does not leverage any simplification needed to directly calculate the goal F(50000), but actually generates graph permutation and counts them. This is clearly not scalable, but is fun! I was, at the time, interested in tiny chess engines and there is a similar underlying problem of rapidly generating states. The enumeration and visualization of small N graphs sparked ideas for the solution, but let's keep those to ourselves. 🤫

Let F(n) be the number of connected graphs with blue edges (directed) and red edges (undirected) containing:

  • two vertices of degree 1, one with a single outgoing blue edge and the other with a single incoming blue edge.
  • vertices of degree 3, each of which has an incoming blue edge, a different outgoing blue edge and a red edge.

(example where N = 4)

example graph

Usage

make run to generate graphs. See Makefile for other dev tools. Configure MAX_N to try larger graphs and see Cargo features for debug configs.