GraphCanon

• 1. Installation
• 2. Changes
• 3. Examples
• 4. Executables
• 5. Library Reference

Introduction

This is the documentation for the GraphCanon library and its associated executables. The library provides an algorithm framework for graph canonicalization, graph isomorphism, and computation of automorphism groups of graphs, using a customizable individualization-refinement algorithm.

The library was initially written as part of the paper A Generic Framework for Engineering Graph Canonization Algorithms [DOI | TR].

The library can for example be used for

• finding a canonical order of the vertices of a given graph,

• finding the automorphism group of a given graph,

• using a canonical vertex order to create a view of a graph with canonical iteration order,

• lexicographical comparison of such permuted graph views, e.g., for isomorphism testing.

Graphs with vertices labelled with elements from a totally ordered set are handled by a user-supplied less-predicate (as you would provide to std::sort). The library also supports graphs where edges are similarly labelled, though for obtaining efficient implementations this may require substantial work from the user.

Handling of permutation groups is done using the PermGroup library which is currently under heavy development.

The package additionally contains a program graph-canon, which makes many variations of the core algorithm available from the command line. The program also facilitates extraction of additional data from the algorithm run, e.g., visualization data for the GraphCanon Visualizer.

Indices and Tables

• Index

Table of Contents

• 1. Installation
  • 1.1. From a Git Repository
  • 1.2. As Dependency of Another CMake Project
  • 1.3. From a Source Archive
  • 1.4. Dependencies
• 2. Changes
  • 2.1. v0.5 (2020-01-12)
    • 2.1.1. Incompatible Chagnes
    • 2.1.2. New Features
    • 2.1.3. Bugs Fixed
    • 2.1.4. Other
  • 2.2. v0.4 (2019-05-27)
    • 2.2.1. Incompatible Changes
    • 2.2.2. New Features
    • 2.2.3. Other
  • 2.3. v0.3 (2018-09-04)
  • 2.4. v0.2 (2018-02-05)
• 3. Examples
  • 3.1. Basic Library Usage
    • 3.1.1. Computing the Canonical Form
    • 3.1.2. Deciding Graph Ismorphism and Total Ordering of Graphs
    • 3.1.3. Finding the Automorphism Group
    • 3.1.4. Investigating the Details of an Algorithm Configuration
    • 3.1.5. Vertex Labelled Graphs
• 4. Executables
  • 4.1. dimacs
  • 4.2. graph-canon
    • 4.2.1. General Options
    • 4.2.2. Graph Loading Options
    • 4.2.3. Algorithm Configuration Options
    • 4.2.4. Program Execution Options
    • 4.2.5. Options Specific for Benchmark Mode
    • 4.2.6. Options Specific for Test Mode
  • 4.3. graph-canon-run
    • 4.3.1. Graph Database
    • 4.3.2. Listing Mode
    • 4.3.3. Execution Mode
  • 4.4. graph-canon-dreadnaut
  • 4.5. graph-canon-bliss
  • 4.6. download-graph-collections
• 5. Library Reference
  • 5.1. aut
    • 5.1.1. implicit_size_2.hpp
    • 5.1.2. perm_moved_points.hpp
    • 5.1.3. pruner_base.hpp
    • 5.1.4. pruner_basic.hpp
    • 5.1.5. pruner_schreier.hpp
  • 5.2. canonicalization.hpp
  • 5.3. compare.hpp
  • 5.4. dimacs_graph_io.hpp
  • 5.5. edge_handler
    • 5.5.1. all_equal.hpp
    • 5.5.2. edge_handler.hpp
  • 5.6. invariant
    • 5.6.1. cell_split.hpp
    • 5.6.2. coordinator.hpp
    • 5.6.3. partial_leaf.hpp
    • 5.6.4. quotient.hpp
  • 5.7. ordered_graph.hpp
  • 5.8. refine
    • 5.8.1. degree_1.hpp
    • 5.8.2. refine.hpp
    • 5.8.3. WL_1.hpp
  • 5.9. shorthands.hpp
  • 5.10. sorting_utils.hpp
  • 5.11. tagged_list.hpp
  • 5.12. target_cell
    • 5.12.1. f.hpp
    • 5.12.2. fl.hpp
    • 5.12.3. flm.hpp
    • 5.12.4. flmcr.hpp
  • 5.13. tree_traversal
    • 5.13.1. bfs-exp.hpp
    • 5.13.2. bfs-exp-m.hpp
    • 5.13.3. dfs.hpp
  • 5.14. util.hpp
  • 5.15. visitor
    • 5.15.1. compound.hpp
    • 5.15.2. debug.hpp
    • 5.15.3. stats.hpp
    • 5.15.4. visitor.hpp