McSplit+BSam

Improved lower bound for maximum common subgraph algorithms.

Prerequisites

• C++ compiler
• Make (optional)

Build and Test

Linux

Use the following command to build this program in Linux operating system.

$ mkdir bin
$ make build

MacOS

Use the following command to build this program in macOS.

$ mkdir bin
$ make macbuild

Testing the Program

$ make test

Expected output.

$ make test
./bin/run.o min_max ./data/tests/case1/pattern ./data/tests/case1/target -l -q -t 100
6, 1, 1.9416e-05, 3.2708e-05, 51, 6, 24, 6, 6, 1.4875e-05, 13, 17, 0, 1, 0
./bin/run.o min_max ./data/tests/case2/pattern ./data/tests/case2/target -l -q -t 100
9, 1, 9.7083e-05, 0.000100083, 353, 334, 203, 7, 7, 2.925e-05, 29, 42, 0, 0, 0

The output provides comma-separated values for the following attributes:

1. The size of the maximum induced common subgraph.
2. Indicates whether the common subgraphs are isomorphic (1 for yes, 0 for no).
3. Time taken (in seconds) to find the optimal solution.
4. Time taken (in seconds) to verify the optimality by completing the search.
5. Total number of recursive calls (branches) made to complete the search.
6. Number of recursive calls (branches) required to find the optimal solution.
7. Number of recursive calls (branches) that were pruned.
8. Incumbent size after the first heuristic iteration.
9. Incumbent size after the second heuristic iteration.
10. Time taken (in seconds) to run the proposed heuristic.
11. Number of branches taken during the first heuristic.
12. Number of branches taken during the second heuristic.
13. Indicates whether the first heuristic terminated early due to a pruning condition.
14. Indicates whether the second heuristic terminated early due to a pruning condition.
15. Indicates whether the search was terminated prematurely (1) or completed fully (0).

Apply Proposed Bound to RL Extensions

Follow the steps in this doc.