Solving Subgraph Isomorphism with an AllDifferent-based Filtering algorithm

LAD is a program (in C) for solving the subgraph isomorphism problem, the goal of which is to decide if there exists a copy of a pattern graph in a target graph. It can be used to solve induced or partial subgraph isomorphism problems. The user may specify additional compatibility relationships among the nodes. LAD is distributed under the CeCILL-B FREE SOFTWARE LICENSE.

Download:

• Version 4 (December 2025): LAD2025 (described in a paper to appear in Artificial Intelligence Journal) for non directed and non labelled graphs only
• Version 3 (December 2015): PathLAD (described in a paper presented at LION 2016) for both directed and undirected graphs
• Version 2 (June 2013): Improved version for both directed and undirected graphs and for labelled graphs
• Version 1: Basic version for non directed graphs

References

• LAD2025 is described in:
  Christine Solnon: LAD2025, a Constraint-Based Solver for the Subgraph Isomorphism Problem, to appear in Artificial Intelligence
• PathLAD is described in:
  Lars Kotthoff, Ciaran McCreesh, and Christine Solnon: Portfolios of Subgraph Isomorphism Algorithms. Learning and Intelligent OptimizatioN Conference (LION 10), 2016
  Paper (pdf)
• The algorithm used by LAD to solve the subgraph isomorphism problem is described in:
  Christine Solnon: AllDifferent-based Filtering for Subgraph Isomorphism. Artificial Intelligence, 174(12-13):850-864, August 2010, Elsevier.
  Draft version of the paper (pdf)   ScienceDirect

Acknowledgements