PHPackages skilla/maximal-cliques - PHPackages - PHPackages [Skip to content](#main-content)[PHPackages](/)[Directory](/)[Categories](/categories)[Trending](/trending)[Leaderboard](/leaderboard)[Changelog](/changelog)[Analyze](/analyze)[Collections](/collections)[Log in](/login)[Sign up](/register) 1. [Directory](/) 2. / 3. [Utility & Helpers](/categories/utility) 4. / 5. skilla/maximal-cliques ActiveLibrary[Utility & Helpers](/categories/utility) skilla/maximal-cliques ====================== Library to resolve Maximal Cliques in undirected graph 1.1.13(9y ago)42.8kGNUPHPPHP >=5.4.0 Since Sep 10Pushed 1y ago1 watchersCompare [ Source](https://github.com/skilla/maximal-cliques)[ Packagist](https://packagist.org/packages/skilla/maximal-cliques)[ RSS](/packages/skilla-maximal-cliques/feed)WikiDiscussions master Synced 1mo ago READMEChangelogDependencies (1)Versions (28)Used By (0) MaximalCliques ============== [](#maximalcliques) **PHP Library to resolve Maximal Cliques in undirected graph** A clique of a graph G is a complete subgraph of G. A maximal clique is a clique that cannot be extended by including one more adjacent vertex, meaning it is not a subset of a larger clique This implementation of Bron–Kerbosch's algorithm include three methods: - Basic resolution (obtainCompleteGraphsWithoutPivoting) - Pivoting resolution (obtainCompleteGraphsWithPivoting) - Vertex ordering resolution (obtainCompleteGraphsWithVertexOrdering) And three methods based on "obtainCompleteGraphsWithVertexOrdering" for advancing search and less time of resolution: - Only cliques that include a specific vertex (obtainCompleteGraphsWithVertexOrderingForVertex) - Only cliques whose degree is equal to or greater than the specified (obtainCompleteGraphsWithVertexOrderingWithMinimumDegree) - Only cliques that include a specific vertex and whose degree is equal to or greater than the specified (obtainCompleteGraphsWithVertexOrderingForVertexWithMinimumDegree) Finally, a function is included to collect the clique larger than those generated with one of the previous six functions. - (retrieveMaximalClique) The six implementations return a array of maximal cliques each represented in an array of vertex, "retrieveMaximalClique" returns a array of vertex. For a graph G whit 6 nodes: ``` 6 - 4 - 5 - 1 | | / | | / | |/ 3 - 2 ``` This will be composed of five maximal cliques: ``` [ [1,2,5], [2,3], [3,4], [4,5], [4,6] ] ``` Installation ------------ [](#installation) for php 5.3 or lower use: composer require "skilla/maximal-cliques:0.1.\*" for php 5.4 or higher composer require "skilla/maximal-cliques:dev-master" How to use ---------- [](#how-to-use) The source code includes "DataTransformerExample" class that implements the "DataTransformerInterface" interface. The purpose of this is to serve as a test and example. Copy this class and adapt their methods to be able to process the data as generated in your application. Then follow any of the examples used to test the class in "test / BronKerboschAlgorithmsTest.php" Performance ----------- [](#performance) Test 1 - 1,000 repetitions with the function "obtainCompleteGraphsWithoutPivoting". Using the same data as in the test. Vertex: 6 Edges: 7 Cliques: 5 Time: 0.347 seconds Memory: 786,432 bytes Test 2 - 1,000 repetitions with the function "obtainCompleteGraphsWithPivoting". Using the same data as in the test. Vertex: 6 Edges: 7 Cliques: 5 Time: 0.480 seconds Memory: 786,432 bytes Test 3 - 1,000 repetitions with the function "obtainCompleteGraphsWithVertexOrdering". Using the same data as in the test. Vertex: 6 Edges: 7 Cliques: 5 Time: 0.488 seconds Memory: 786,432 bytes Test 4 - One repetition with the function "obtainCompleteGraphsWithoutPivoting". Using 100 vertex. Vertex: 100 Edges: 2,507 Cliques: 17,215 Time: 228.430 seconds Memory: 19,398,656 bytes Test 5 - One repetition with the function "obtainCompleteGraphsWithPivoting". Using 100 vertex. Vertex: 100 Edges: 2,507 Cliques: 17,215 Time: 199.249 seconds Memory: 19,398,656 bytes Test 6 - One repetition with the function "obtainCompleteGraphsWithVertexOrderingForVertex". Using 100 vertex. Vertex: 100 Edges: 2,507 Cliques: 17,215 Time: 157.969 seconds Memory: 19,398,656 bytes Test 7 - One repetition with the function "obtainCompleteGraphsWithVertexOrderingForVertex". Using 100 vertex. Selected vertex: 23 Vertex: 100 Edges: 2,507 Cliques: 768 Time: 2.219 seconds Memory: 4,718,592 bytes Test 8 - One repetition with the function "obtainCompleteGraphsWithVertexOrderingWithMinimumDegree". Using 100 vertex. Selected degree: 5 Vertex: 100 Edges: 2,507 Cliques: 13,654 Time: 156.963 seconds Memory: 16,252,928 bytes Test 9 - One repetition with the function "obtainCompleteGraphsWithVertexOrderingForVertexWithMinimumDegree". Using 100 vertex. Selected vertex: 23 Selected degree: 5 Vertex: 100 Edges: 2,507 Cliques: 588 Time: 2.240 seconds Memory: 4,456,448 bytes ### Health Score 36 — LowBetter than 82% of packages Maintenance28 Infrequent updates — may be unmaintained Popularity25 Limited adoption so far Community7 Small or concentrated contributor base Maturity68 Established project with proven stability Bus Factor1 Top contributor holds 100% of commits — single point of failure How is this calculated?**Maintenance (25%)** — Last commit recency, latest release date, and issue-to-star ratio. Uses a 2-year decay window. **Popularity (30%)** — Total and monthly downloads, GitHub stars, and forks. Logarithmic scaling prevents top-heavy scores. **Community (15%)** — Contributors, dependents, forks, watchers, and maintainers. Measures real ecosystem engagement. **Maturity (30%)** — Project age, version count, PHP version support, and release stability. ### Release Activity Cadence Every ~1 days Total 26 Last Release 3517d ago Major Versions 0.1.0 → 1.1.92016-09-16 0.1.1 → 1.1.102016-09-20 0.1.5 → 1.1.112016-09-20 0.1.6 → 1.1.132016-09-29 PHP version history (2 changes)1.0.0PHP >=5.3.0 1.1.4PHP >=5.4.0 ### Community Maintainers ![](https://www.gravatar.com/avatar/fdf5a8fe6b39b693be50b0b97f999b378069ab191f8a3b3e00fbc4e9805f60bf?d=identicon)[skilla](/maintainers/skilla) --- Top Contributors [![skilla](https://avatars.githubusercontent.com/u/1517293?v=4)](https://github.com/skilla "skilla (24 commits)") --- Tags AlgorithmMaximal Cliquescomplete graphundirected graphBron Kerbosch ### Code Quality TestsPHPUnit ### Embed Badge ![Health badge](/badges/skilla-maximal-cliques/health.svg) ``` [![Health](https://phpackages.com/badges/skilla-maximal-cliques/health.svg)](https://phpackages.com/packages/skilla-maximal-cliques) ``` ### Alternatives [rubix/ml A high-level machine learning and deep learning library for the PHP language. 2.2k1.4M28](/packages/rubix-ml)[donatello-za/rake-php-plus Yet another PHP implementation of the Rapid Automatic Keyword Extraction algorithm (RAKE). 271865.1k10](/packages/donatello-za-rake-php-plus)[tga/simhash-php SimHash similarities algorithm implementation for PHP 5.3 15243.5k1](/packages/tga-simhash-php)[fisharebest/algorithm Implementation of standard algorithms in PHP. 7192.7k1](/packages/fisharebest-algorithm)[edgaras/strsim Collection of string similarity and distance algorithms in PHP including Levenshtein, Damerau-Levenshtein, Jaro-Winkler, and more 2423.0k](/packages/edgaras-strsim)[uestla/simplex-calculator Simple tool for linear programming problems solving 427.6k](/packages/uestla-simplex-calculator) PHPackages © 2026 [Directory](/)[Categories](/categories)[Trending](/trending)[Changelog](/changelog)[Analyze](/analyze)