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.

- Version 3 (January 2016): 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

- 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 - PathLAD is described in:

Lars Kotthoff, Ciaran McCreesh, and Christine Solnon: Portfolios of Subgraph Isomorphism Algorithms. To appear in Learning and Intelligent OptimizatioN Conference (LION 10), 2016

Paper (pdf)

**LAD**is our solver;**Vflib**is a C++ graph matching library, developed at Mivia Lab of the University of Salerno;**Abscon**is a generic Constraint Programming solver developped in Java by C. Lecoutre and S. Tabary. We consider here the variant which maintains Arc Consistency and which chooses variables with respect to the minDom heuristic.

Graphs of this benchmark are scale-free networks that have been randomly generated using a power law distribution of degrees. There are 100 instances such that target graphs have between 200 and 1000 nodes and pattern graphs have 90% of the nodes of the target graphs.

Solver | Number of solved instances | Average CPU time per solved instance |
---|---|---|

LAD | 100 | 3.0 |

Vflib | 16 | 72.5 |

Abscon | 81 | 594.9 |

This benchmark is obtained from the first 50 graphs of the database of Larrosa and Valiente. These graphs have different properties (connected, biconnecetd, triconnected, bipartite, planar, ...) and have between 10 and 128 nodes. Using these graphs, we have generated 793 instances of the subgraph isomorphism problem by considering all couples of graphs that are not trivially solved.

Solver | Number of solved instances | Average CPU time per solved instance |
---|---|---|

LAD | 728 | 12.8 |

Vflib | 468 | 73.7 |

Abscon | 662 | 54.3 |

This benchmark contains 900 instances coming from the Graph Database. It contains instances with bounded valence graphs and modified bounded valence graphs (with valence in {3,6,9}). The number of nodes of the target graphs is in {200, 400, 800}, and the pattern graphs have between 20% and 60% of the nodes of the target graphs. It also contains instances with quadri-dimensional meshes (with rho in {0, 0.2, 0.4, 0.6}). The number of nodes of the target graphs is in {256, 625, 1296}, and the pattern graphs have between 20% and 60% of the nodes of the target graphs.

Solver | Number of solved instances | Average CPU time per solved instance |
---|---|---|

LAD | 900 | 1.07 |

Vflib | 882 | 0.12 |

Abscon | 890 | 40.60 |

This benchmark contains 270 random instances coming from the Graph Database. It contains instances with randomly generated graphs such that the uniform probability of adding an edge is in {0.01, 0.05, 0.1}. The number of nodes of the target graphs is in {200, 400, 600}, and the pattern graphs have between 20% and 60% of the nodes of the target graphs.

Solver | Number of solved instances | Average CPU time per solved instance |
---|---|---|

LAD | 190 | 287.8 |

Vflib | 3 | 1735.9 |

Abscon | 183 | 409.5 |