activity.matching.core

Implements the matching algorithm used to match attendees to occasions.

The algorithm used is based on Deferred Acceptance. The algorithm has a quadratic runtime.

Module Contents

Classes

AttendeeAgent	Acts on behalf of the attendee with the goal to get a stable booking
OccasionAgent	Represents the other side of the Attendee/Occasion pair.

Functions

deferred_acceptance(→ onegov.core.utils.Bunch)	Matches bookings with occasions.
deferred_acceptance_from_database(→ None)
is_stable(→ bool)	Returns true if the matching between attendees and occasions is

Attributes

ScoreFunction

activity.matching.core.ScoreFunction: typing_extensions.TypeAlias

class activity.matching.core.AttendeeAgent(id: uuid.UUID, bookings: Iterable[Booking], limit: int | None = None, minutes_between: float = 0, alignment: Literal[day, week, month] | None = None)

Bases: onegov.activity.matching.utils.HashableID

Acts on behalf of the attendee with the goal to get a stable booking with an occasion.

A booking/occasion pair is considered stable if there exists no other such pair which is preferred by both the attendee and the occasion.

In other words, if there’s no other occasion that would accept the attendee over another attendee.

property is_valid: bool

Returns True if the results of this agent are valid.

The algorithm should never get to this stage, so this is an extra security measure to make sure there’s no bug.

__slots__ = ('id', 'wishlist', 'accepted', 'blocked')

accepted: set[onegov.activity.Booking]

blocked: set[onegov.activity.Booking]

blocks(subject: onegov.activity.Booking, other: onegov.activity.Booking | onegov.activity.Occasion) → bool

accept(booking: onegov.activity.Booking) → None

Accepts the given booking.

deny(booking: onegov.activity.Booking) → None

Removes the given booking from the accepted bookings.

class activity.matching.core.OccasionAgent(occasion: onegov.activity.Occasion, score_function: ScoreFunction | None = None)

Bases: onegov.activity.matching.utils.HashableID

Represents the other side of the Attendee/Occasion pair.

While the attende agent will try to get the best possible occasion according to the wishses of the attendee, the occasion agent will try to get the best attendee according to the wishes of the occasion.

These wishes may include hard-coded rules or peferences defined by the organiser/admin, who may manually prefer certain attendees over others.

property full: bool

__slots__ = ('occasion', 'bookings', 'attendees', 'score_function')

bookings: set[onegov.activity.Booking]

attendees: dict[onegov.activity.Booking, AttendeeAgent]

score_function: ScoreFunction

preferred(booking: onegov.activity.Booking) → onegov.activity.Booking | None

Returns the first booking with a lower score than the given booking (which indicates that the given booking is preferred over the returned item).

If there’s no preferred booking, None is returned.

accept(attendee: AttendeeAgent, booking: onegov.activity.Booking) → None

deny(booking: onegov.activity.Booking) → None

match(attendee: AttendeeAgent, booking: onegov.activity.Booking) → bool

activity.matching.core.deferred_acceptance(bookings: Sequence[Booking], occasions: Iterable[Occasion], score_function: ScoreFunction | None = None, validity_check: bool = True, stability_check: bool = False, hard_budget: bool = True, default_limit: int | None = None, attendee_limits: dict[uuid.UUID, int] | None = None, minutes_between: float = 0, alignment: Literal[day] | None = None, sort_bookings: bool = True) → onegov.core.utils.Bunch

Matches bookings with occasions.

Score_function:

A function accepting a booking and returning a score. Occasions prefer bookings with a higher score over bookings with a lower score, if and only if the occasion is not yet full.

The score function is meant to return a constant value for each booking during the run of the algorithm. If this is not the case, the algorithm might not halt.

Validity_check:

Ensures that the algorithm doesn’t lead to any overlapping bookings. Runs in O(b) time, where b is the number of bookings per period.

Stability_check:

Ensures that the result does not contain any blocking pairs, that is it checks that the result is stable. This runs in O(b^3) time, so do not run this in production (it’s more of a testing tool).

Hard_budget:

Makes sure that the algorithm halts eventually by raising an exception if the runtime budget of O(a*b) is reached (number of attendees times the number of bookings).

Feel free to proof that this can’t happen and then remove the check ;)

Default_limit:

The maximum number of bookings which should be accepted for each attendee.

Attendee_limits:

The maximum number of bookings which should be accepted for each attendee. Keyed by the attendee id, this dictionary contains per-attendee limits. Those fall back to the default_limit.

Minutes_between:

The minutes between each booking that should be considered transfer-time. That is the time it takes to get from one booking to another. Basically acts as a suffix to each booking, extending it’s end time by n minutes.

Alignment:

Align the date range to the given value. Currently only ‘day’ is supported. When an alignment is active, all bookings are internally stretched to at least cover the alignment.

For example, if ‘day’ is given, a booking that lasts 4 hours is considered to last the whole day and it will block out bookings on the same day.

Note that the minutes_between parameter is independent of this. That is if there’s 90 minutes between bookigns and the bookings are aligned to the day, there can only be a booking every other day:

10:00 - 19:00 becomes 00:00 - 24:00 + 90mins.

Usually you probably do not want minutes_between combined with an alignment.

activity.matching.core.deferred_acceptance_from_database(session: sqlalchemy.orm.Session, period_id: uuid.UUID, *, score_function: ScoreFunction | None = None, validity_check: bool = True, stability_check: bool = False, hard_budget: bool = True) → None

activity.matching.core.is_stable(attendees: Iterable[AttendeeAgent], occasions: Collection[OccasionAgent]) → bool

Returns true if the matching between attendees and occasions is stable.

This runs in O(n^4) time, where n is the combination of bookings and occasions. So this is a testing tool, not something to run in production.