Software

Available software:

• Galant (Graph Algorithm Animation Tool) — graph editing and graph algorithm animation, an updated version of GDR (see below) with almost all of GDR’s features and more, along with a modern user interface (GDR is black and white and editing is very crude). Technical report and documentation are included with the download.
• GDR — A graph editing and graph algorithm animation tool. The most recent version is
  GDR-1.2.9. This has added animations and bug fixes as of 2007/05/14. Current animations include: depth-first search, breadth-first search, biconnected components, two minimum spanning tree algorithms, shortest paths, state minimization
  in finite automata, and bipartite graph edge crossing minimization.
  The conference paper that describes the initial design and implementation of GDR is also available.
• ProofChecker — a program for designing and proving correctness of finite-state automata. ProofChecker is accessible to both sighted and non-sighted users.
• Enhanced implementation of a branch and reduce algorithm for vertex cover (derived from an earlier implementation by Akiba and Iwata).
  See the companion paper on graph profiling.
• Software for minimizing edge crossings and other objectives in multilayered graphs. See, e.g., a 2012 JEA paper.
• An implementation of a matroid parity algorithm for graphic matroids — see the 1986 paper by Gabow and Stallmann. There are some known bugs in the implementation and/or the paper, as documented in the repository. A corrected Python implementation by Benjamin Peyrill (benjamin.peyrille@grenoble-inp.fr) is available.
• Two-Layer edge-crossing minimization software, see a 2001 JEA paper.
• Software related to experiments with min-cost satisfiability problems, as reported most recently in a paper in Exp2007:
  • UmbraNova – software that implements int-dual (all-integer dual simplex), branch and bound, and local search, along with scripts to run the program on classes of instances
  • CPX-ILP – a driver program and scripts to run CPLEX
  • Utility scripts/programs – scripts and programs for translating formats, generating experimental data, etc.
  • An archive containing all of the above software is 2007-ExpCS-Stallmann-Software.zip