julien-boudry/condorcet

Condorcet is a PHP Class to computing many Condorcet voting methods


README

Condorcet Class

A PHP library implementing the Condorcet voting system and others Condorcet methods like the Schulze method. And also also a powerfull election manager.

This library provide you :

  • Computing Pairwise, Natural Condorcet Winner or Loser
  • Algorithms implements (fully or partially) the criteria of the Marquis de Condorcet (Schulze, Copeland, RankedPair, Kemeny-Young, MiniMax Family... see below)
  • Advanced Management for votes and candidates, Condorcet is also a powerful election manager.
  • Support many inputs types (string, complex strings, array, json) or full object management (Candidate and Vote are objects).
  • Management for inter-elections candidates and votes. And others tools for simulate scenarios.
  • Support for storing elections (serializing Election object, exports datas, checksuming...)
  • Ready to be extend, or support your own algorithms (modular architecture).
  • Optionally use provided or external driver to support and storing data for very large election (millions of votes). STILL EXPERIMENTAL
  • Many smarts tools to manage election.
  • [...]

This class is not designed for high performances or very high fiability exigence. Since v0.98, an experimental support is provided for ver high number of voters (millions).

Summary

  1. Project Overview
    a. Contributors and License
    b. Project State and Specifications
    c. Supported Condorcet Methods
    d. Related projects / They use Condorcet
  2. How to use it?
    a. Condorcet Wiki Manual
    b. Class & Methods reference
    c. Examples Have a look on Examples !
    d. Really quick and simple example
  3. Roadmap for futher releases

Contributors and License

Created by: Julien Boudry (born 22/10/1988 - France) @JulienBoudry - (complete list of contributors)
License: MIT (read de LICENSE file at the root folder) Including code, examples, logo and documentation

As a courtesy, I will thank you to inform me about your project using this code, produced with love and selflessness. You can also offer me a bottle of good wine.
Or finance my studies: 1LhZZVxmNCTPWftKFTUKbRiUKzA67RPWez

Project State and Specifications

Versions

Supported Version:

  • Stable Version: 1.0.x
    • PHP Requirement: PHP 5.6 with Ctype, MB_String, Json common extensions. (tested up to PHP 7.0)
  • Development Version: 1.1.x
    • PHP Requirement: PHP 7 with Ctype, MB_String, Json common extensions.

To date, we have a stable version, and support is provided.

  • v0.9x series is no longer supported. But bug report are welcome, code base can be close to v1.x series.
  • Some support and fix can be done for 0.14 version on demand. Since v0.90, you should consider than it's a new projet (api, engine).

External testers are more than welcome!

Autoloading:

This project is consistent with the standard PSR-4 and can be loaded easily and without modification in most frameworks or Composer autoloader. Namespace \Condorcet is used. The examples also provides easy example of implementation using an optional Condorcet autoloader. If you don't want to use composer or other standard PSR-4 autoloader.

Coding standards:

The code is very close to the respect of PSR-1 (lacks only the naming of methods), and freely influenced by PSR-2 when it is not unnecessarily authoritarian.

Performance:
  • Complex scenario with all algorithms chained, multiple elections sharing votes & candidates scenarios and hundred of votes.
    • Memory usage : less than 2M
    • Execution time : less than 80ms
  • Complex scenario with three algorithms chained (Natural Condorcet, Schulze, Copeland), multiple elections sharing votes & candidates scenarios and hundred of votes.
    • Memory usage : less than 2M
    • Execution time : less than 30ms

Benchmark on a modern machine (linux - x64 - php 7.0 - cli).

Kemeny-Youg case :
  • use Kemeny-Young 6 candidates : 5MB - 150ms
  • use Kemeny-Young 7 candidates : 32MB - 600ms
  • use Kemeny-Young 8 candidates : 135MB - 2500ms
Massive election case :

If you need to manage election with more than 50 000 votes. You can consider putting in place an modular external driver or the provided driver to store data out of the RAM, into SQL database for example (it's support hundreds of millions votes). Have a look to the manual

Extending PHP memory_limit allows you to manage hundreds thousands votes, but it can be a bit slower than outsource this data (PHP don't like that) and it's not extensive to infinity.
However, the quality of the external system chosen does not change much performance. From a certain point: slowdowns being overwhelmingly intrinsically linked to internal processing side Condorcet engine.

  • use simple Vote 6 Candidates / 100 000 Votes with SQLite : 27s (MySQL for example is not faster, actual limit is Condorcet PHP engine)
Supported Condorcet Methods

More information on Condorcet Wiki

Add new one?

This class is designed to be easily extensible with new algorithms (they don't need share the same namespace). A modular schematic is already used for all algorithms provided, so you can easily help, do not forget to make a pull request!
More explanations in the documentation below

Related projects / They use Condorcet
  • From August 2014: Condorcet.Vote Web services to create and store online Condorcet election. Including intérractives and collaborative features.
    It is based in large part on this project, and uses the library as a real election manager for computing, storage & stats.
  • Mahler-S2-BlindTest-Condorcet (french interface) Web wrapper to compute and show result for classical music blind challenge with the Condorcet Class full potential (can also be used and adapted for any elections).
    Look like the examples provided here, but better : Gustav Mahler blind listening test

How to use it?

I have undertaken and continues to undertake efforts to reform and improve the documentation. Thereof is not yet satisfactory plainement nor perfectly updated. Your help is welcome! Consider reading the functional examples that are very explicit, test your even the entire function package, and especially to ask questions!

Condorcet Wiki Manual

Living and learning examples, giving an overview but not exhaustive of the possibilities of the library.

Class & Methods reference

The precise documentation of methods is not a wiki. It can be found in the form of Markdown in the "doc" folder for each release.

Examples

Great overview With html output basics examples Specifics examples Really quick and simple example

OK : sacrifice to the local tradition of lazy.

  use Condorcet\Condorcet;
  use Condorcet\Election;
  use Condorcet\Candidate;
  use Condorcet\Vote;

  $myElection1 = new Election () ;

  // Create your own candidate object
  $candidate1 = new Candidate ('Candidate 1'); 
  $candidate2 = new Candidate ('Candidate 2');
  $candidate3 = new Candidate ('Candidate 3');

  // Register your candidates
  $myElection1->addCandidate($candidate1);
  $myElection1->addCandidate($candidate2);
  $myElection1->addCandidate($candidate3);
  $candidate4 = $myElection1->addCandidate('Candidate 4');

  // Add some votes, by some ways
  $myElection1->addVote( array(
                              $candidate2, // 1
                              [$candidate1, $candidate4] // 2 - Tie
                              // Last rank is optionnal. Here it's : $candidate3
  ));

  $myElection1->addVote('Candidate 2 > Candidate 3 > Candidate 4 = Candidate 1'); // last rank can also be omitted

  $myElection1->parseVotes(
              'tagX || Candidate 1 > Candidate 2 = Candidate 4 > Candidate 3 * 4
              tagX, tagY || Candidate 3 > Candidate 1 * 3'
  ); // Powerfull, it add 7 votes

  $myElection1->addVote( new Vote ( array(
                                        $candidate4,
                                        $candidate2
                                        // You can ignore the over. They will be at the last rank in the contexte of each election.
  )  ));


  // Get Result

    // Natural Condorcet Winner
    $myWinner = $myElection1->getWinner(); // Return a candidate object
          echo 'My winner is ' . $myWinner->getName() . '<br>' ;

    // Natural Condorcet Loser
    $myLoser = $myElection1->getLoser(); // Return a candidate object
          echo 'My loser is ' . $myLoser->getName() ;

    // Schulze Ranking
    $myResultBySchulze = $myElection1->getResult('Schulze'); // Return a multi-dimensional array, filled with objects Candidate (multi-dimensional if tie on a rank)
      # Echo it easily 
      Condorcet::format($myResultBySchulze);

    // Get Schulze advanced computing data & stats
    $mySchulzeStats = $myElection1->getResultStats('Schulze');

    // Get Copeland Ranking
    $myResultByCopeland = $myElection1->getResult('Copeland');

    // Get Pairwise
    $myPairwise = $myElection1->getPairwise();

  // How long computation time behind us?
  $timer = $myElection1->getGlobalTimer();

  // SHA-2 checksum and sleep
  $myChecksum = $myElection1->getChecksum();
  $toStore = serialize($myElection1);  // You can now unset your $candidate1 & co. On wake up, Condorcet election will build distinct with new reference.


  # And many many more than that. Read the doc. & look advanced examples.
Condorcet PHP Implementation

This example of implementation in others project can very nice or strange... They can be current, or otherwise affect older versions of Condorcet.

Roadmap for futher releases

  • Better cache system to prevent any full computing of the Pairwise on new vote / remove vote
  • Improve & test Ranked pair implementation (help needed!)
  • Add tie breaking on Schulze Core, by the official way recommended by Markus Schulze. (help needed!)
  • In future results could be provided as a new object Coondorcet\Result rather than an array. Will be fun.
  • Very soon, Condorcet will only support PHP 7 and use his news features (special branch already in test).
  • Looking for testers!
  • Research reference librarians!!