Building Hamiltonian Graphs from LCF Notation


Updated November 14th, 2012

  • Uses Ember.js to handle UI events, the graph model, and fragment URLs
  • Improved performance to handle much larger graphs (draws a total of 50,000 vertices and edges before warning about performance)
  • Numbers in the LCF code are modifiable using arrow keys
  • Added random LCF code generation
  • Added freeze frame
  • Added gallery of graphs
  • Updated Bootstrap to handle larger graphs and support full screen display
  • Added vertex and edge count

I found this Wolfram MathWorld article on LCF notation after researching bilinear interpolation. The article inspired me to build a LCF notation parser that would create the graphs using d3.js. Originally, I only planned on displaying the circular graph without animation.  Adding the graph construction animation was definitely a wow milestone, but, after I enabled the forces on the links, it turned into a woah moment. The 3D structure of the graph actually reveals itself without having to build in any 3D calculations. This was a really fun project to build and it’s still exciting to watch it build a torus.

The The On-Line Encyclopedia of Integer Sequences is a good place to look for number series that result in interesting graphs.

Image of February 5th, 2012 Version

  • Snf

    Super  Amazing!

  • jD

    This is a brilliant piece of code…
    It is a joy to play with it!.

    jD @ http://pragmatikroo.blogspot.com
     

  • http://jamesscottbrown.com James Scott-Brown

    The link to “watch it build a torus” does not work: I get the error message “Cannot GET /1703449?lcfCode=[10]100&animationSpeed=1&lockVertices=0″

  • http://jamesscottbrown.com James Scott-Brown

    The link to “watch it build a torus” does not work: I get the error message “Cannot GET /1703449?lcfCode=[10]100&animationSpeed=1&lockVertices=0″

  • http://jamesscottbrown.com James Scott-Brown

    The link to “watch it build a torus” does not work: I get the error message “Cannot GET /1703449?lcfCode=[10]100&animationSpeed=1&lockVertices=0″

  • http://jamesscottbrown.com James Scott-Brown

    The link to “watch it build a torus” does not work: I get the error message “Cannot GET /1703449?lcfCode=[10]100&animationSpeed=1&lockVertices=0″

  • http://jamesscottbrown.com James Scott-Brown

    The link to “watch it build a torus” does not work: I get the error message “Cannot GET /1703449?lcfCode=[10]100&animationSpeed=1&lockVertices=0″

  • http://jamesscottbrown.com James Scott-Brown

    The link to “watch it build a torus” does not work: I get the error message “Cannot GET /1703449?lcfCode=[10]100&animationSpeed=1&lockVertices=0″

  • http://twitter.com/patrickm145 Patrick Martin

    Amazing! I love watching this stuff render.

  • http://www.facebook.com/peter.stephenson.58 Peter Stephenson

    Love watching this in slow-mo! But edge counts seem off. For example, for Tutte 12-cage (126 vertices), I think edge count should be 189
    ( (126*3)/2 ) rather than 188.

    • http://www.christophermanning.org/ Christopher Manning

      Thank you for noticing that! The duplicate edge detection that prevents drawing multiple edges that connect the same vertices was not continuously checking the Hamiltonian path as it was being constructed. So, in larger graphs, there could be duplicate or missing edges on the Hamiltonian path. I’ve updated the code and it now correctly displays the 189 edges you mentioned.

      Thanks again for the feedback and I am glad you enjoyed the project.