Instance module#

Module defining the basic classes used to represent a participatory budgeting election. The Project and the Instance classes are defined here.

class Instance(init: Collection[Project] = (), budget_limit: int | float | mpq | None = None, categories: set[str] | None = None, targets: set[str] | None = None, file_path: str | None = None, file_name: str | None = None, parsing_errors: bool | None = None, meta: dict | None = None, project_meta: dict | None = None)[source]#

Bases: set[Project]

Participatory budgeting instances. An instance contains the projects that are voted on, together with other information about the election such as the budget limit. Importantly, the ballots submitted by the voters is not part of the instance. See the module profile for how to handle the voters. Note that Instance is a subclass of the Python class set, and can be used as a set is.

Parameters:

  • init (Iterable[Project], optional) – An iterable of Project that constitutes the initial set of projects for the instance. In case an Instance object is passed, the additional attributes are also copied (except if the corresponding keyword arguments have been given).

  • budget_limit (Numeric, optional) – The budget limit of the instance, that is, the maximum amount of money a set of projects can use to be feasible.

  • categories (set[str], optional) – The set of categories that the projects can be assigned to. These can be “Urban greenery” or “Public transport” for instance. Defaults to {}.

  • targets (set[str], optional) – The set of target groups that the project can be targeting. These can be “Citizens above 60 years old” or “Residents of district A” for instance. Defaults to {}.

  • file_path (str, optional) – If the instance has been parsed from a file, the path to the file. Defaults to “”.

  • file_name (str, optional) – If the instance has been parsed from a file, the name of the file. Defaults to “”.

  • parsing_errors (bool, optional) – Boolean indicating if errors were encountered when parsing the file. Defaults to None.

  • meta (dict, optional) – All kinds of relevant information for the instance, stored in a dictionary. Keys and values are typically strings. Defaults to dict().

  • project_meta (dict[Project, dict], optional) – All kinds of relevant information about the projects, stored in a dictionary. Keys are Project and values are dictionaries. Defaults to dict().

budget_limit#

The budget limit of the instance, that is, the maximum amount of money a set of projects can use to be feasible.

Type:

Numeric

categories#

The set of categories that the projects can be assigned to. These can be “Urban greenery” or “Public transport” for instance.

Type:

set[str]

targets#

The set of target groups that the project can be targeting. These can be “Citizens above 60 years old” or “Residents of district A” for instance.

Type:

set[str]

file_path#

If the instance has been parsed from a file, the path to the file.

Type:

str

file_name#

If the instance has been parsed from a file, the name of the file.

Type:

str

parsing_errors#

Boolean indicating if errors were encountered when parsing the file.

Type:

bool

meta#

All kinds of relevant information for the instance, stored in a dictionary. Keys and values are typically strings.

Type:

dict

project_meta#

All kinds of relevant information about the projects, stored in a dictionary. Keys are Project and values are dictionaries.

Type:

dict[Project: dict]

budget_allocations() → Generator[Collection[Project]][source]#

Returns a generator for all the feasible budget allocations of the instance.

Returns:

The generator.

Return type:

Generator[Iterable[Project]

copy(*args)#

Return a shallow copy of a set.

difference(*args)#

Return the difference of two or more sets as a new set.

(i.e. all elements that are in this set but not the others.)

difference_update(*args)#

Remove all elements of another set from this set.

get_project(project_name: str) → Project[source]#

Iterates over the instance to find a project with the given name. If found, the project is returned, otherwise a KeyError exception is raised.

Returns:

The project.

Return type:

Project

intersection(*args)#

Return the intersection of two sets as a new set.

(i.e. all elements that are in both sets.)

intersection_update(*args)#

Update a set with the intersection of itself and another.

is_exhaustive(projects: Collection[Project], available_projects: Collection[Project] | None = None) → bool[source]#

Tests if a given collection of projects is exhaustive. A collection of projects is said to be exhaustive if no additional project could be added without violating the budget limit. Note that a collection of projects can be exhaustive, but not feasibility.

Parameters:

  • projects (Iterable[Project]) – The collection of projects.

  • available_projects (Iterable[Project], optional) – Only these projects are considered when testing for exhaustiveness. Defaults to None, i.e., considering all projects.

Returns:

True if the collection of project is exhaustive, False otherwise.

Return type:

bool

is_feasible(projects: Collection[Project]) → bool[source]#

Tests if a given collection of projects is feasible for the instance, meaning that the total cost of the projects does not exceed the budget limit of the instance.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

True if the collection of project cost less than the budget limit, False otherwise.

Return type:

bool

is_trivial() → bool[source]#

Tests if the instance is trivial, meaning that either all projects can be selected without exceeding the budget limit, or that no project can be selected.

Returns:

True if the instance is trivial, False otherwise.

Return type:

bool

symmetric_difference(*args)#

Return the symmetric difference of two sets as a new set.

(i.e. all elements that are in exactly one of the sets.)

symmetric_difference_update(*args)#

Update a set with the symmetric difference of itself and another.

union(*args)#

Return the union of sets as a new set.

(i.e. all elements that are in either set.)

class Project(name: str = '', cost: int | float | mpq = 0, categories=None, targets=None)[source]#

Bases: object

Represents a project, that is, the entity that is voted upon in a participatory budgeting election.

Parameters:

  • name (str, optional) – The name of the project. This is used as the identifier of a project. It should be unique with a collection of projects, though this is not enforced. Defaults to “”.

  • cost (Numeric, optional) – The cost of the project. Defaults to 0.

  • categories (set[str], optional) – The categories that the project is a member of. These categories can “Urban greenery” or “Public transport” for instance. Defaults to {}.

  • targets (set[str], optional) – The target groups that the project is targeting. These can be “Citizens above 60 years old” or “Residents of district A” for instance. Defaults to {}.

name#

The name of the project. This is used as the identifier of a project. It should be unique with a collection of projects, though this is not enforced.

Type:

str

cost#

The cost of the project.

Type:

Numeric

categories#

The categories that the project is a member of. These categories can “Urban greenery” or “Public transport” for instance.

Type:

set[str]

targets#

The target groups that the project is targeting. These can be “Citizens above 60 years old” or “Residents of district A” for instance.

Type:

set[str]

get_random_instance(num_projects: int, min_cost: int, max_cost: int) → Instance[source]#

Generates a random instance. Costs and budget limit are integers. The costs are selected uniformly at random between min_cost and max_cost. The budget limit is sample form a uniform between the minimum cost of a project and the total cost of all the projects. The parameters are rounded up to the closest int.

Parameters:

  • num_projects (int) – The number of projects in the instance.

  • min_cost (int) – The minimum cost of a project.

  • max_cost (int) – The maximum cost of a project.

Returns:

The randomly-generated instance.

Return type:

Instance

max_budget_allocation_cardinality(projects: Collection[Project], budget_limit: int | float | mpq) → int[source]#

Returns the maximum number of projects that can be chosen with respect to the budget limit.

Parameters:

  • projects (iterable[Project]) – An iterable of projects.

  • budget_limit (Numeric) – the budget limit

Returns:

The maximum number of projects that can be chosen with respect to the budget limit.

Return type:

int

max_budget_allocation_cost(projects: Collection[Project], budget_limit: int | float | mpq) → int | float | mpq[source]#

Returns the maximum total cost over all subsets of projects with respect to the budget limit.

Parameters:

  • projects (iterable[Project]) – An iterable of projects.

  • budget_limit (Numeric) – the budget limit

Returns:

The maximum total cost over all subsets of projects with respect to the budget limit.

Return type:

int

total_cost(projects: Collection[Project]) → int | float | mpq[source]#

Returns the total cost of a collection of projects, summing the cost of the projects.

Parameters:

projects (iterable[Project]) – An iterable of projects.

Returns:

The total cost

Return type:

Numeric