Download the PHP package skilla/maximal-cliques without Composer

On this page you can find all versions of the php package skilla/maximal-cliques. It is possible to download/install these versions without Composer. Possible dependencies are resolved automatically.

FAQ

After the download, you have to make one include require_once('vendor/autoload.php');. After that you have to import the classes with use statements.

Example:
If you use only one package a project is not needed. But if you use more then one package, without a project it is not possible to import the classes with use statements.

In general, it is recommended to use always a project to download your libraries. In an application normally there is more than one library needed.
Some PHP packages are not free to download and because of that hosted in private repositories. In this case some credentials are needed to access such packages. Please use the auth.json textarea to insert credentials, if a package is coming from a private repository. You can look here for more information.

  • Some hosting areas are not accessible by a terminal or SSH. Then it is not possible to use Composer.
  • To use Composer is sometimes complicated. Especially for beginners.
  • Composer needs much resources. Sometimes they are not available on a simple webspace.
  • If you are using private repositories you don't need to share your credentials. You can set up everything on our site and then you provide a simple download link to your team member.
  • Simplify your Composer build process. Use our own command line tool to download the vendor folder as binary. This makes your build process faster and you don't need to expose your credentials for private repositories.
Please rate this library. Is it a good library?

Informations about the package maximal-cliques

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:

And three methods based on "obtainCompleteGraphsWithVertexOrdering" for advancing search and less time of resolution:

Finally, a function is included to collect the clique larger than those generated with one of the previous six functions.

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:

This will be composed of five maximal cliques:

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

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

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

All versions of maximal-cliques with dependencies

PHP Build Version
Package Version
Requires php Version >=5.4.0
Composer command for our command line client (download client) This client runs in each environment. You don't need a specific PHP version etc. The first 20 API calls are free. Standard composer command

The package skilla/maximal-cliques contains the following files

Loading the files please wait ...