Weekly Notes for Week 40

• This weeks topics:
  • Details of GraphCanonicalization.
  • Individualisation Refinement Paradigm / Equitable partitions / search tree

• The graph grammar rule editor I showed in the last lecture can be found on github (repository fromNikolai Nøjgaard). The following sequence of command should work in order to make the editor work. Use at your own risk ;)

   git clone https://github.com/Nojgaard/mod-RuleMaker.git
   sudo apt install npm
   cd mod-RuleMaker/
   pip3 install websockets json_schema
   npm install
   npm run build
  

  After that you should be able start the rule editor webserver with npm run start. Open the file file:///home/mod/tmp/mod-RuleMaker/index.html in a web browser and you should be able to edit graph grammar rules.

• The examples of how to use wildcards (presented in the last lecture) can be found in blackboard (folder Material/assignment1).

• Reading Material:
  • For Canonicalization : still Chapter 4 of the PhD thesis by Jakob Lykke Andersen
  • McKay, B.D. and Piperno, A., Practical Graph Isomorphism, II, Journal of Symbolic Computation, 60 (2014), pp.94-112.
  • S. G. Hartke and A. Radcliffe. McKay’s canonical graph labeling algorithm. In Communicating Mathematics, volume 479 of Contemporary Mathematics, pages 99-111. American Mathematical Society, (2009). This article contains the example for the handwritten example I will use.
  • Link for visualising graph canonicalization as shown in the first lecture: http:// jakobandersen.github.io/graph_canon_vis
  • McKay, B.D. and Piperno, A., Practical Graph Isomorphism, II, Journal of Symbolic Computation, 60 (2014), pp.94-112.
  • S. G. Hartke and A. Radcliffe. McKay’s canonical graph labeling algorithm. In Communicating Mathematics, volume 479 of Contemporary Mathematics, pages 99-111. American Mathematical Society, (2009). This article contains the example for the handwritten example I will use.
  • For visualization of the nauty/traces : http://pallini.di.uniroma1.it/SearchTree.html