Finding correspondence via maximum cliques in large graphs
Project description
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 S1 and
S2.
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
cliquematch
requirespybind11
(v2.2 or newer) for its setup:
pip3 install pybind11
-
cliquematch
requiresEigen
(v3.3.7 or newer) as part of its setup. -
A
C++11
compatible compiler must be available for the installation:- On Linux, gcc is called with
--std=c++11
(builds withgcc 4.8.2
formanylinux1
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.
- On Linux, gcc is called with
-
Compilation Flags:
setup.py
compiles thecliquematch
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 to1
when benchmarking the core cliquematch algorithm.
-
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for cliquematch-1.2.0-cp39-cp39-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2e4165b38b4d40e920c8e66c07fc647f53289f8fffeeaa4cafb0f97bc907d057 |
|
MD5 | ac50fa0d27b65b70d6e41e4ff3fd7ad1 |
|
BLAKE2b-256 | 0ead92665009c409669204785322fe6810b8244a91b424f8104cf9bfa081169d |
Hashes for cliquematch-1.2.0-cp39-cp39-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ee21e4a1d46535ad680c9b709516dbb130434526fe53a5fdfacef8c4e62a2fd9 |
|
MD5 | f4c80d633c1adb10d5dbe4866b081297 |
|
BLAKE2b-256 | 9de8645556d53eff2cf2f237f6a595f435d6dee2cc24b954296dab9724770880 |
Hashes for cliquematch-1.2.0-cp39-cp39-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3090a268bceef36fd421af4c59d0e75224b1dbd4076f4f59c79b721e9e826624 |
|
MD5 | fbb9ffaad49e44b8bbdfa5c588463540 |
|
BLAKE2b-256 | cf992b28f911a101cdb6189d91b95f96c92816fee374c25e553cc3ea53d91267 |
Hashes for cliquematch-1.2.0-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c591327f1b4f579ac1097bc7479dc98da9bf48cef8f09064882f78bb802ec218 |
|
MD5 | 4093a50a433106cef74ec12a46df655b |
|
BLAKE2b-256 | 23f45ea9f795b07868a9b65268eec1fa31993b52cecf9cfc7defd34cda32d74e |
Hashes for cliquematch-1.2.0-cp38-cp38-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 63ab27fdfdf0bdd10620b0daa89865b46d57c374517eefb4e6e78277caeb22eb |
|
MD5 | 59dec3416c0d3bb75771098aba51fca2 |
|
BLAKE2b-256 | 02d6821ddb03a52e7ba8e45677731872e34bca27a9aac284099a872041deea18 |
Hashes for cliquematch-1.2.0-cp38-cp38-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0bf620db15da777b1268dfb22fdb249b20c1a2f29b4a84a8bce58463c82bb231 |
|
MD5 | 5a95aaf5dd12739a620840af697836e5 |
|
BLAKE2b-256 | 5d5ef66621d6bfb4bc3b9c68d375648158781a40021df442aa917fa1193ab851 |
Hashes for cliquematch-1.2.0-cp38-cp38-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b927d124a33e7dda4128b8c025861f6320b0febea85d19c82394cb7114a2fb21 |
|
MD5 | 0107ea01c365ee6497eb94d78efbb151 |
|
BLAKE2b-256 | 0b93602b5475db8e44fd763a31d25e836f434c4cbf90502b2a8cc9189ae508d2 |
Hashes for cliquematch-1.2.0-cp38-cp38-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 69fd0c4f7df91039f7c695083dc7726ed7159a3e1fb01e01c1f6463b0584e572 |
|
MD5 | 27c86a8af70d788ac62260dd95f13d5c |
|
BLAKE2b-256 | 771b00e24258b8085da94279927faa113ed0c56682ec40f9896ab3f1ab524058 |
Hashes for cliquematch-1.2.0-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8bda43aa9df950911fb137de1ede385bec924ae334f916f6578de86ffcbbf401 |
|
MD5 | 5c6b9a055c489b20f073ded7ee5c0b29 |
|
BLAKE2b-256 | 54782fab9154d599e6625c552b1a3304f4853765a4083e3576c86e8dd0fbc0e9 |
Hashes for cliquematch-1.2.0-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f0c8730bc32504a50c0dcfc4aa5da884715283505c0dfee668b9dedc3acf5bbc |
|
MD5 | fb84396826357b8cc316524c8188c868 |
|
BLAKE2b-256 | 509122a78a4330a0644585516edc9e0b68234d3403ef9e3106be0747be5703b7 |
Hashes for cliquematch-1.2.0-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 202106c200d855aa3fa18eae81047d995cbfbc04fa18e6019140c6fa45f38c4c |
|
MD5 | 0908894f6bee9ad1a9d4d9451c8177dd |
|
BLAKE2b-256 | 01e3dc08776a2aad15062d14552785b92470e1a00b05b15a18d1b82500860e0d |
Hashes for cliquematch-1.2.0-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3c7e3981acc0228b3e7f27b169976e3a1ac4c971ebd6e75e9838b6a235eeeddc |
|
MD5 | 313d52adaa3424f4cff86d945f05fdcf |
|
BLAKE2b-256 | a4b8ae3c70ec32ab34239d9b477521bc961392ac20b550a5feaf79febf9d1b2c |
Hashes for cliquematch-1.2.0-cp37-cp37m-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | de608849148db2a77f7d51c4d5e613f23094b795f372c54af8a71e5495145994 |
|
MD5 | 4dc82671a113d510c8503b2b23d7d665 |
|
BLAKE2b-256 | f23f59eab6b21cfc8e9f46fc010faf845bbe4d0136fe3a2bdeb1a2625c380540 |
Hashes for cliquematch-1.2.0-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4d4bf7c159023733dbf952fb6ee1369fb25ce22e7b2e4aa1863d70df6456ccdd |
|
MD5 | a39429f53ab01afe6960d20549a8a15a |
|
BLAKE2b-256 | 91e84f273caf843f40e1cbaf760eb4bff39defd6fe64ca28d2b465c3991e03ac |
Hashes for cliquematch-1.2.0-cp36-cp36m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c571644c5fb4c7aaf4ede1baf72acb17e39d5a0a2305e7cf66e6f6c7163a67cd |
|
MD5 | e64942bf6b0bba561e20f07821038859 |
|
BLAKE2b-256 | 05c336aee972e26834b715b38d473d7a9ce31d0a9f69f4f940c534bbeb2dacc2 |
Hashes for cliquematch-1.2.0-cp36-cp36m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bb1066d5ddcd379083d9cbb354fa9bd666d6b4b905020534982d491c96c06a8c |
|
MD5 | 5602f2c663673ddcf005dcca7894e471 |
|
BLAKE2b-256 | cf29ff9a8d94b9e9a2c6e86ef5ed50540151a4f700e2026d026b4b00e094d8aa |
Hashes for cliquematch-1.2.0-cp36-cp36m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a0f3665e02c0f7ebba8e404e3b18fecbf3225c150705c20c704e769d80a982db |
|
MD5 | 576fbe1ab2cc133e4c853587e343b5a3 |
|
BLAKE2b-256 | 46f3042cad927a30faa78737514673f5e0b0e8f1b9e41ea824ab8f627449f7fb |
Hashes for cliquematch-1.2.0-cp36-cp36m-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b6b5144b41bd9c8102333abcfd2c2ee56f8046fb8f06ec862c2220864cd068d0 |
|
MD5 | d6c1e630d276e6c844b11e045ec003d9 |
|
BLAKE2b-256 | 574ba900eec499539694f0c7f1d042f58ffd93d29c880f26c1f4fb6335d7e8e2 |
Hashes for cliquematch-1.2.0-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2b2e7b90ce85bb3b6106a555b1e1178bcdfd07e4b524161317140a4159553ce3 |
|
MD5 | 8cb21669debab101343f1051463d40da |
|
BLAKE2b-256 | dc4dab098fac8eb7bc56209d588cde7ab82435391259b4db1d79b1c388241f9d |
Hashes for cliquematch-1.2.0-cp35-cp35m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d14eb403aa89db9cd8d760a7ddcb11d2fb13e384cc295d2442a91b9be3c87071 |
|
MD5 | 6195d726b8fbffd9a074358f7877cf61 |
|
BLAKE2b-256 | e537aeee2551e07b8231b632194ed815828a6d1e658796dca396bb941e2c3523 |
Hashes for cliquematch-1.2.0-cp35-cp35m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a5ed232c9cd1021ddf58c064475a7a4cec68c338c35ae71ad00f1aac9768f568 |
|
MD5 | 3dd31b229b391fa4b4ee335297789a0e |
|
BLAKE2b-256 | 6628db0a37a6c7f80bcc9df23c63e8aa812ab9d0ab5a31414c80323a4f00d2b0 |
Hashes for cliquematch-1.2.0-cp35-cp35m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dea2321d673c98b8b6a2b1cf895d09e574517f34961341c35c64a3dbabb98918 |
|
MD5 | c67f48a3dad98091f5e86a42ef8003cc |
|
BLAKE2b-256 | 739a8ebdc80c36496375a0de35d3be861776df7952cb3e54e6515794cc257469 |
Hashes for cliquematch-1.2.0-cp35-cp35m-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8994b99a50abbc7cf005d4739fb2f2b3d51ea69b803fa9cc6dd54af44787a2cf |
|
MD5 | 83cdea602d5af7aa146ee7d950ab405d |
|
BLAKE2b-256 | 0822bc2af75f346dadbcf6109c92552c633f12dd544132b9c19dc5446f5e9940 |
Hashes for cliquematch-1.2.0-cp27-cp27mu-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 439c19af6e07f45ae69d92e8b1df47683d351a1fb6182d90e44d08141a5c2afc |
|
MD5 | 71fbe15ecb8a8bf820922ce2af61f318 |
|
BLAKE2b-256 | 7e316e0df2c6d9c9b00636acefca061e995696eb7fb801c46113e117852948e6 |
Hashes for cliquematch-1.2.0-cp27-cp27mu-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b9f83caa9efd116d62ea8aa324360fcc1ab3b7a290ee46a483ba20ccd60fb5fc |
|
MD5 | ded3dddb6cdadce38c03a7993a330c7c |
|
BLAKE2b-256 | 21a0a728cd6c6611fa748b6cc539ec0b2884a6cf8a2b8fffae3c8f2c87d8b729 |
Hashes for cliquematch-1.2.0-cp27-cp27mu-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1ddbae583823fba9abf4326262fad21fb0e2bffd6db3e52a5b49e70f419856dd |
|
MD5 | a4b5bff2a3cb1c2956c0676c4d1b6a89 |
|
BLAKE2b-256 | 16a206e3a26e7cd34d22ae21cd30774750c468d26dad319c8813268cef25427e |
Hashes for cliquematch-1.2.0-cp27-cp27m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 642605d1741b00508aa1b6288a2960b63efb76b4ea7c1a67c1c9b663ea57aeb4 |
|
MD5 | 0a205dbb1c57281c94bc6de2a37fa5c7 |
|
BLAKE2b-256 | 5806585181f000a64b60fe26f9b4f9088672da092deba5981cf81c658ca886a0 |
Hashes for cliquematch-1.2.0-cp27-cp27m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 68e202733ac6b2ac8b86759ea31946418b0fc6db8ca15474952dfb9e5611c471 |
|
MD5 | 7164b565060a492cacd2935d2d269131 |
|
BLAKE2b-256 | 20ae844fda72023ba1106a7d43709db8b26d759b7b1f20a268cf2f2042fd023d |
Hashes for cliquematch-1.2.0-cp27-cp27m-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 254e81513807b52744663935f12d0ae53409c88aa64ae299c85194f752874b20 |
|
MD5 | 1824ade13732742d3dfa87439ddfd136 |
|
BLAKE2b-256 | 339c0ea8b6392f94efa702902714bd262fbf95ac58885d255b298eb639832e89 |