Simple, performant graph generator for Feynman diagrams* ⚛️

Overview

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 #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.

Comments
  • Clean up Rust best practices

    Clean up Rust best practices

    clean up rust bread and butter. h/t lopopolo

    • run using cargo
    • safe conversion to usize
    • do not repeat the generate calls
    • derive Default and Clone traits on Graph
    • control debug printing via Cargo features
    • run cargo fmt with check flag in CI
    • run cargo clippy to fail on warnings in CI
    opened by elh 0
  • improve iteration of edge candidate vertices

    improve iteration of edge candidate vertices

    track j_0 and k_0 cursors to the first vertices we need to consider for the directed and undirected edges.

    now well under arbitrary goal of 1s for N=16 or 12.2M edges! done with all of the initial performance TODOs i had.

    case	n	result	dur_ms	dur_pretty
    F(2)	2	1	0	587.00ns
    F(4)	4	5	0	1.55µs
    F(6)	6	35	0	6.34µs
    F(8)	8	319	0	37.51µs
    F(10)	10	3559	0	314.48µs
    F(12)	12	46841	3	3.91ms
    F(14)	14	709601	52	52.95ms
    F(16)	16	12156445	899	899.53ms
    
    opened by elh 0
  • j can never be 1. that could cause a cycle connected to the source

    j can never be 1. that could cause a cycle connected to the source

    case	n	result	dur_ms	dur_pretty
    F(2)	2	1	0	729.00ns
    F(4)	4	5	0	2.33µs
    F(6)	6	35	0	10.47µs
    F(8)	8	319	0	63.37µs
    F(10)	10	3559	0	509.20µs
    F(12)	12	46841	6	6.69ms
    F(14)	14	709601	69	69.19ms
    
    F(16)	16	12156445	1176	1.18s
    
    opened by elh 0
  • build as a release build for 10x performance...

    build as a release build for 10x performance...

    haha 🙃. obvious find upon first look at any Rust-specific performance tips. well, i hit my goal performance. prior work was still a good exercise in algorithmic and data access performance. need to take a closer look for other low hanging fruit.

    case	n	result	dur_ms	dur_pretty
    F(2)	2	1	0	570.00ns
    F(4)	4	5	0	1.52µs
    F(6)	6	35	0	6.46µs
    F(8)	8	319	0	40.98µs
    F(10)	10	3559	0	350.72µs
    F(12)	12	46841	4	4.68ms
    F(14)	14	709601	84	84.26ms
    
    
    F(16)	16	12156445	1295	1.30s
    F(18)	18	232349755	25600	25.60s
    
    opened by elh 0
  • safely(?) cast integer types without invoking from/into fn

    safely(?) cast integer types without invoking from/into fn

    case	n	result	dur_ms	dur_pretty
    F(2)	2	1	0	8.03µs
    F(4)	4	5	0	13.64µs
    F(6)	6	35	0	88.39µs
    F(8)	8	319	0	757.44µs
    F(10)	10	3559	7	7.83ms
    F(12)	12	46841	76	76.42ms
    F(14)	14	709601	1199	1.20s
    
    
    F(16)	16	12156445	22036	22.04s
    
    opened by elh 0
  • tightly pack vertices array by defining as 2D array instead of Vec of arrays

    tightly pack vertices array by defining as 2D array instead of Vec of arrays

    get better data locality. hit my arbitrary goal of >500K permutations per second! decently satisfied with that. lets timebox some attempts to get to 1M per second

    case	n	result	dur_ms	dur_pretty
    F(2)	2	1	0	4.98µs
    F(4)	4	5	0	8.63µs
    F(6)	6	35	0	53.44µs
    F(8)	8	319	0	656.73µs
    F(10)	10	3559	6	6.37ms
    F(12)	12	46841	79	79.95ms
    F(14)	14	709601	1281	1.28s
    
    
    F(16)	16	12156445	23447	23.45s
    
    opened by elh 0
  • assign into vertices array cell by cell

    assign into vertices array cell by cell

    no need to track prior state to restore during backtrack

    case	n	result	dur_ms	dur_pretty
    F(2)	2	1	0	15.69µs
    F(4)	4	5	0	28.91µs
    F(6)	6	35	0	153.20µs
    F(8)	8	319	1	1.07ms
    F(10)	10	3559	13	13.59ms
    F(12)	12	46841	155	155.33ms
    F(14)	14	709601	1929	1.93s
    
    
    F(16)	16	12156445	34252	34.25s
    
    opened by elh 0
  • reduce edges considered for undirected edges

    reduce edges considered for undirected edges

    undirected edges can only connect to unseen but connected vertices or single new unconnected vertex

    case	n	result	dur_ms	dur_pretty
    F(2)	2	1	0	14.20µs
    F(4)	4	5	0	25.81µs
    F(6)	6	35	0	139.61µs
    F(8)	8	319	1	1.73ms
    F(10)	10	3559	12	12.81ms
    F(12)	12	46841	163	163.48ms
    F(14)	14	709601	2220	2.22s
    
    
    F(16)	16	12156445	38673	38.67s
    
    opened by elh 0
  • remove unneeded check if generated graph is valid solution

    remove unneeded check if generated graph is valid solution

    we already only generate valid graphs! i initially expected work to be required to ensure that edges were wired up correctly due to the possibility of sink vertices being anywhere in the set.

    case	n	result	dur_ms	dur_pretty
    F(2)	2	1	0	11.31µs
    F(4)	4	5	0	21.89µs
    F(6)	6	35	0	137.53µs
    F(8)	8	319	1	1.46ms
    F(10)	10	3559	19	19.22ms
    F(12)	12	46841	285	285.95ms
    F(14)	14	709601	4737	4.74s
    
    opened by elh 0
  • documenting: the example cases for N=4

    documenting: the example cases for N=4

    just documenting

    // currently testing the solutions given in the example problem
    let gs: Vec<Graph> = vec![
        // where N = 0
        Graph {
            vertices: vec![[Some(1), None, None], [None, Some(0), None]],
        },
        // where N = 2
        Graph {
            vertices: vec![
                [Some(1), None, None],
                [Some(2), Some(0), Some(2)],
                [Some(3), Some(1), Some(1)],
                [None, Some(2), None],
            ],
        },
        // where N = 4
        Graph {
            vertices: vec![
                [Some(1), None, None],
                [Some(2), Some(0), Some(2)],
                [Some(3), Some(1), Some(1)],
                [Some(4), Some(2), Some(4)],
                [Some(5), Some(3), Some(3)],
                [None, Some(4), None],
            ],
        },
        Graph {
            vertices: vec![
                [Some(1), None, None],
                [Some(2), Some(0), Some(3)],
                [Some(3), Some(1), Some(4)],
                [Some(4), Some(2), Some(1)],
                [Some(5), Some(3), Some(2)],
                [None, Some(4), None],
            ],
        },
        Graph {
            vertices: vec![
                [Some(1), None, None],
                [Some(2), Some(0), Some(4)],
                [Some(3), Some(1), Some(3)],
                [Some(4), Some(2), Some(2)],
                [Some(5), Some(3), Some(1)],
                [None, Some(4), None],
            ],
        },
        Graph {
            vertices: vec![
                [Some(1), None, None],
                [Some(2), Some(0), Some(3)],
                [None, Some(1), None],
                [Some(4), Some(5), Some(1)],
                [Some(5), Some(3), Some(5)],
                [Some(3), Some(4), Some(4)],
            ],
        },
        Graph {
            vertices: vec![
                [Some(1), None, None],
                [Some(2), Some(0), Some(4)],
                [Some(3), Some(1), Some(5)],
                [None, Some(2), None],
                [Some(5), Some(5), Some(1)],
                [Some(4), Some(4), Some(2)],
            ],
        },
    ];
    
    for g in gs {
        let n = g.vertices.len() - 2;
        println!(
            "g(n={}) is_valid: {}, is_solution: {:?}!\t{:?}",
            n,
            g.is_valid(),
            g.is_solution(n as u16),
            g.vertices
        );
    }
    
    opened by elh 0
  • documenting: initial timings

    documenting: initial timings

    initial timings on 9/1:

    case	n	result	dur_ms	dur_pretty
    F(0)	0	0	0	11.16µs
    F(2)	2	1	0	42.01µs
    F(4)	4	5	0	108.55µs
    F(6)	6	35	1	1.10ms
    F(8)	8	319	12	12.55ms
    F(10)	10	3559	161	161.66ms
    F(12)	12	46841	2258	2.26s
    F(14)	14	709601	40126	40.13s
    
    opened by elh 0
  • Documenting: Optimizing the brute force

    Documenting: Optimizing the brute force

    Improvements made in PRs for N=16. Normalized for debug v. release builds. Measured using release build.

    Run                                  ms       % faster    graphs/sec
    --------------------------------------------------------------------
    Initial run                          34112                356K/sec
    Remove is_solution check (#3)        3449     889%        3.5M/sec
    Check fewer undirected edges (#4)    1310     163%        9.3M/sec
    Assign cell by cell (#5)             1294     1%          9.4M/sec
    Tightly pack array (#7)              1310     -1%         9.3M/sec
    j_0 and k_0 cursors (#12)            930      41%         13.1M/sec
    

    Using a tightly packed multidimensional array instead of a vector of arrays was a meaningful performance improvement in debug mode but does not matter in release mode. Perhaps Rust compiler is already optimizing!

    . . .

    Runs Run N=16

    opened by elh 0
Owner
eugene huang
a roving gopher
eugene huang
A simple and elegant, pipewire graph editor

pw-viz A simple and elegant, pipewire graph editor This is still a WIP, node layouting is kinda jank at the moment. Installation A compiled binary is

null 169 Sep 25, 2022
GraphScope: A One-Stop Large-Scale Graph Computing System from Alibaba

A One-Stop Large-Scale Graph Computing System from Alibaba GraphScope is a unified distributed graph computing platform that provides a one-stop envir

Alibaba 1.9k Sep 26, 2022
Graph data structure library for Rust.

petgraph Graph data structure library. Supports Rust 1.41 and later. Please read the API documentation here Crate feature flags: graphmap (default) en

null 1.9k Sep 27, 2022
A graph library for Rust.

Gamma A graph library for Rust. Gamma provides primitives and traversals for working with graphs. It is based on ideas presented in A Minimal Graph AP

Metamolecular, LLC 118 Sep 1, 2022
🦀 Rust Graph Routing runtime for Apollo Federation 🚀

Apollo Router The Apollo Router is a configurable, high-performance graph router for a federated graph. Getting started Follow the quickstart tutorial

Apollo GraphQL 403 Sep 27, 2022
A graph crate with simplicity in mind

A graph crate with simplicity in mind. Prepona aims to be simple to use (for users of the crate) and develop further (for contributors). Nearly every

Mohamad Amin Rayej 74 Jul 20, 2022
Graph API client writen in Rust

graph-rs Now available on stable Rust at crates.io graph-rs-sdk = "0.1.0" 0.1.0 and above use stable Rust. Anything before 0.1.0 uses nightly Rust. M

Sean Reeise 42 Sep 11, 2022
Rust library for of graph ensembles

Rust library for random graph ensembles Minimal Rust version: 1.55.0 Implements simple sampling and monte carlo (or rather markov-) steps, that can be

Yannick Feld 1 Dec 27, 2021
A Graph implemented using nothing but `Vec`s in rust

VecGraph A Graph implemented using nothing but Vecs in rust. Details The graph is implemented using two Vecs: nodes and edges. nodes stores "nodes". w

null 1 Jan 27, 2022
A cool, fast maze generator and solver written in Rust

MazeCruncher Welcome to maze cruncher! Download Standalone Here Usage To get started, just run the standalone .exe in target/release or compile and ru

null 69 Sep 20, 2022
Kiss3d - Keep it simple, stupid 3d graphics engine for Rust.

Kiss3d - Keep it simple, stupid 3d graphics engine for Rust.

Sébastien Crozet 1.2k Sep 27, 2022
Easy c̵̰͠r̵̛̠ö̴̪s̶̩̒s̵̭̀-t̶̲͝h̶̯̚r̵̺͐e̷̖̽ḁ̴̍d̶̖̔ ȓ̵͙ė̶͎ḟ̴͙e̸̖͛r̶̖͗ë̶̱́ṉ̵̒ĉ̷̥e̷͚̍ s̷̹͌h̷̲̉a̵̭͋r̷̫̊ḭ̵̊n̷̬͂g̵̦̃ f̶̻̊ơ̵̜ṟ̸̈́ R̵̞̋ù̵̺s̷̖̅ţ̸͗!̸̼͋

Rust S̵̓i̸̓n̵̉ I̴n̴f̶e̸r̵n̷a̴l mutability! Howdy, friendly Rust developer! Ever had a value get m̵̯̅ð̶͊v̴̮̾ê̴̼͘d away right under your nose just when

null 293 Sep 22, 2022
A library that can be used as a building block for high-performant graph algorithms.

graph A library that can be used as a building block for high-performant graph algorithms. Graph provides implementations for directed and undirected

Martin Junghanns 53 Sep 15, 2022
Egui node graph is a featureful, customizable library to create node graph applications using egui

Egui node graph is a featureful, customizable library to create node graph applications using egui. The library takes care of presenting a node graph to your users, and allows customizing many aspects of the interaction, creating the semantics you want for your specific application.

null 266 Sep 29, 2022
Diagrams as code

diagwiz -- ASCII diagrams as code Warning: This project is in early experimental stage. Functionality is subject to change and YMMV. Feel free to open

Krzysztof Jagiełło 41 Sep 16, 2022
Rust crate for creating beautiful interactive Chord Diagrams

Chord PRO Released Chord PRO is the full-featured chord visualization API, producing beautiful interactive visualizations, e.g. those featured on the

Dr. Shahin Rostami 25 Sep 10, 2022
A library to generate syntax diagrams for Rust macros.

Live demo (code) A browser add-on for Firefox, Chrome and Edge A library to generate syntax ("railroad") diagrams for Rust's macro_rules!(). Diagrams

null 460 Sep 21, 2022
Untree converts tree diagrams produced by tree back into directory file structures.

Untree: Undoing tree for fun and profit Untree converts tree diagrams produced by tree back into directory file structures. Let's say you have the fol

Alecto Irene Perez 92 Jun 24, 2022
Sūshì is a simple but customizable static site generator / blog generator written in Rust

sūshì Sūshì is a simple but customizable static site generator / blog generator written in Rust. Installation Install with Cargo (Recommended) cargo i

MrNothing233 2 Mar 20, 2022
Simple and performant hot-reloading for Rust

reloady Simple, performant hot-reloading for Rust. Requires Rust nightly and only works on Linux for now. installing CLI To install the CLI helper car

Anirudh Balaji 24 Aug 5, 2022