Skip to content

Latest commit

 

History

History
202 lines (167 loc) · 8.48 KB

README.md

File metadata and controls

202 lines (167 loc) · 8.48 KB
Raw

Condorcet Domain Library

Version Python 3.8 C++ License

Condorcet Domain Library (CDL) is a flexible lightweight header-only library written in C++ and offers Python Interfaces as a module that can be installed via pip, enabling users to seamlessly integrate with tools written in Python. CDL provides a wide range of functionalities pertaining to Condorcet Domains (CD) and forbidden permutation, including

  • Ordering k-tuples, and rule initialization and assignment;
  • Domain construction and size calculation;
  • find complete of never conditions that a domain satisfies;
  • Subset functions and domain types verification;
  • Hashing, identifying and generating non-isomorphic domains;
  • Native support for general forbidden permutation domains;
  • Support all 6 rules: 1N3, 3N1, 2N3, 2N1, 1N2 and 3N2;
  • and much more.

CDL supports all major operating systems, including Windows, MacOS and Linux distributions. Users can install it as a python module using pip install condorcet-domain. Note that the module name in Python script is cdl. See below for examples.

Directory structure:

  • algorithms: for testing and benchmarking many learning algorithms, like genetic algorithms, reinforcement learning algorithms, and local search algorithms, etc.
  • bind: export all the C++ classes and functions to a python module and provide the bash script install it.
  • core: the key functionality for manipulating tuple-rules and performing domain-related operations.
  • python: provides depth-first and breast-first Prioritised Restriction Search (PRS) search algorithms
  • tools: provide additional functions such as processing MUCDs from Condorcet domains, verifying the maximality of domains, as well as functions for running parallel calculations on median graph built from Condorcet domains.
  • hpc: contains example Bash scripts for running Python scripts using CDL on High Performance Computing machines.

Get started with Python

Working with Condorcet domains

from cdl import *

def alternating_scheme(triple):  # build the alternating scheme 
   i, j, k = triple
   if j % 2 == 0:
      return "2N1"
   else:
      return "2N3"

cd = CondorcetDomain(n=8)  # initialize the Condorcet domain object
# initialize the trs with the predefined alternating scheme 
trs = cd.init_trs()
trs = cd.init_trs_by_scheme(trs, alternating_scheme)
domain = cd.domain(trs)  # construct the Condorcet domain
size = cd.size(trs)  # calculate the size of the resulting Condorcet domain (222)
assert len(domain) == size  # True

# change the rule assigned to the triplet [2, 3, 4] from "2N3" to "3N1"
trs = cd.assign_rule(trs, [2, 3, 4], "3N1")
size = cd.size(trs) # the size of the new domain is 210.

cd.init_subset(sub_n=6)
substates = cd.subset_states(trs) # get a list of 28 subset states in 6 alternatives

# build a list of domains
domains = [cd.domain(cd.init_trs_random()) for _ in range(100)]
# filter out the isomorphic domains
non_isomorphic_cds = cd.non_isomorphic_domains(domains)

Working with Forbidden Permutations

# recreate the alternating scheme by forbidden permutations
def alternating_scheme(triple):  
    i, j, k = triple
    if j % 2 == 0:
        return [[2, 1, 3], [2, 3, 1]]
    else:
        return [[1, 3, 2], [3, 1, 2]]

fp = ForbiddenPermutation(n=8, k=3)  # initialize the Forbidden Permutation object
tls = fp.init_tls_by_scheme(alternating_scheme)
domain = fp.domain(tls)
size = fp.size(tls)  # 222
assert len(domain) == size
from cdl import ForbiddenPermutation

for n in range(5, 11):
    # initialize the ForbiddenPermutation object for 5-tuples
    fp = ForbiddenPermutation(n, 5) 
    tls = fp.init_tls()
    for tl in tls:
        # assign all the 5-tuples with the law [2, 5, 3, 1, 4]
        tls = fp.assign_laws(tls, tl.tuple, [[2, 5, 3, 1, 4]])
    print(fp.size(tls))

Installation for Python Program

Pip install CDL

Run

pip install condorcet-domain

in the terminal (command line). See CDL on PyPI

Build CDL from source for Linux or MacOS

  1. Open a terminal and download the CDL repository to your laptop by git clone https://github.com/sagebei/cdl.git
  2. Change working directory to the cdl/bind folder
  3. Install Python3 or anaconda, gcc, cmake if you have not. You might need to load the gcc and the cmake module by running module load gcc cmake if you are using a server machine.
    • Installing to an existing Python virtual environment: Run source install.sh \path\to\your\virtural_environment to install the library to an existing virtual environment in which you will import it. (This will download pybind11 libray that is essential to compile the code, and install the dgl library to the site-package folder in the virtual environment. Examples: source install.sh \opt\anaconda3 to install the library in the anaconda global environment, or source install.sh ~\PyCharmProjects\venv to install it in a virtual environment created in the PycharmProjects directory.)
    • Creat a new virtual environment: python -m venv /path/to/new/virtual/environment. Then follow the above instructions to install the CDL library in it.

Build CDL from source for Windows

  1. Install git, Python3 or anaconda, gcc, cmake if you have not. You might need to load the gcc and the cmake module by running module load gcc cmake if you are using a server machine.
  2. Open a Git Bash terminal, and change working directory to cdl/bind
  3. Run source windows_install.sh \path\to\your\virtural_environment. For example, source windows_install.sh /D/Anaconda3/Lib/site-packages/

Get started with C++

Working with Condorcet domains

#include "condorcet_domain.h"

std::string alternating_scheme(const Triple& triple)
{
    if ((triple[1] % 2) == 0)
        return "2N1";
    else
        return "2N3";
}

int main()
{
    CondorcetDomain cd(6);
    auto trs = cd.init_trs_by_scheme(cd.init_trs(), alternating_scheme);
    std::cout << (cd.size(trs) == cd.domain(trs).size()) << std::endl;

    CD domain = cd.domain(trs);
    CDS domains{};
    domains.push_back(domain);
    domains.push_back(domain);

    CDS new_cds = cd.non_isomorphic_domains(domains);
    return 0;
}

Working with Forbidden permutations

#include "forbidden_permutation.h"

std::vector<std::string> alternating_scheme(const Triple& triple)
{
    if ((triple[1] % 2) == 0)
        return {{2, 1, 3}, {2, 3, 1}};
    else
        return {{1, 3, 2}, {3, 1, 2}};
}

int main()
{
    ForbiddenPermutation fp(8, 3);
    TLS tls = fp.init_tls_by_scheme(alternating_scheme);
    std::cout << (fp.size(tls) == fp.domain(tls).size()) << std::endl;
    return 0;
}

Cite

Please cite our paper if you use CDL in a scientific publication.

@article{zhou2024cdl,
  title={CDL: A fast and flexible library for the study of permutation sets with structural restrictions},
  author={Zhou, Bei and Markstr{\"o}m, Klas and Riis, S{\o}ren},
  journal={SoftwareX},
  volume={28},
  pages={101951},
  year={2024},
  publisher={Elsevier}
}

List of publications used CDL

  1. Zhou, Bei, and Søren Riis. "New Record-Breaking Condorcet Domains on 10 and 11 Alternatives." arXiv preprint arXiv:2303.06524 (2023).
  2. Akello-Egwell, Dolica, Charles Leedham-Green, Alastair Litterick, Klas Markström, and Søren Riis. "Condorcet Domains of Degree at most Seven." arXiv preprint arXiv:2306.15993 (2023).
  3. Karpov, Alexander, Klas Markström, Søren Riis, and Bei Zhou. "Set-alternating schemes: A new class of large Condorcet domains." arXiv preprint arXiv:2308.02817 (2023).
  4. Karpov, Alexander, Klas Markström, Søren Riis, and Bei Zhou. "Local Diversity of Condorcet Domains." arXiv preprint arXiv:2401.11912 (2024).
  5. Markström, Klas, Søren Riis, and Bei Zhou. "Arrow's single peaked domains, richness, and domains for plurality and the Borda count." arXiv preprint arXiv:2401.12547 (2024).

Our Team

CDL is developed and maintained by Dr Bei Zhou and Dr Soren Riis in the theory group at Queen Mary University of London, and Professor Klas Markstrom from University of Umeå.