cliquematch 1.0.0

Finding correspondence via maximum cliques in large graphs

cliquematch

Finding correspondence via maximum cliques in large graphs

The cliquematch package is used to to find a maximum clique in large sparse undirected graphs as quickly as possible. It also provides a framework with generic classes for implementing applications of the maximum clique problem: finding a (sub)set of corresponding elements between two sets S₁ and S₂.

Usage

cliquematch is used for loading a large graph and finding a maximum clique in it. For example, we load cond-mat-2003.mtx, and find a maximum clique.

import cliquematch
G = cliquematch.Graph.from_file("cond-mat-2003.mtx")
G.time_limit = 1
print(G)
# cliquematch.core.Graph object at 0x559e7da730c0
# (n_vertices=31163,n_edges=120029,lower_bound=1,upper_bound=4294967295,
# time_limit=1,use_heuristic=False,use_dfs=True,search_done=False)
G.get_max_clique()
# [9986, 9987, 10066, 10068, 10071, 10072, 10074, 10076,
# 10077, 10078, 10079, 10080, 10081, 10082, 10083, 10085,
# 10287, 10902, 10903, 10904, 10905, 10906, 10907, 10908, 10909]

The search can be tuned in terms of size/time bounds, and reset if necessary. If required, use_heuristic can be set to True to find a large clique quickly.

Correspondence graphs

Many applications of maximum cliques involve construction of a correspondence graph to find corresponding subsets between two given sets. cliquematch also contains classes for correspondence graphs:

• This image matching algorithm can be implemented using cliquematch like this.
• Simple molecular alignment can be implemented like this.

The correspondence graph classes are generated using C++ template programming. cliquematch can be extended with custom correspondence graphs: they can be prototyped using the existing classes, and/or implemented in C++ for performance.

Installation Instructions

Installing from a wheel

PyPI wheels are available for Linux and Windows. MacOS builds are tested but wheels are not provided.

pip install cliquematch

Installing from source

1. cliquematch requires pybind11 (v2.2 or newer) for its setup:

pip3 install pybind11

2. cliquematch requires Eigen (v3.3.7 or newer) as part of its setup.

   • You can clone the repo via git clone --recursive to get Eigen.
   • If you already have an existing version of Eigen, or have downloaded it separately, set the EIGEN_DIR environment variable to the folder containing Eigen before compilation.

3. A C++11 compatible compiler must be available for the installation:

   • On Linux, gcc is called with --std=c++11 (builds with gcc 4.8.2 for manylinux1 wheels).
   • On Windows, Visual Studio 2015 Update 3 (MSVC 14.0 runtime) or later is needed.
   • Note: Installing under Windows+MinGW has not been tested.

4. Compilation Flags: setup.py compiles the cliquematch extension with two additional flags.

   • STACK_DFS (1 by default): If nonzero, cliquematch uses an explicit stack for the depth-first clique search; otherwise it uses recursive function calls. Primarily for debugging purposes.

   • BENCHMARKING (0 by default): Set to 1 when benchmarking the core cliquematch algorithm.