kep_solver.graph module

Describes a number of classes related to the compatibility graph.

class Vertex(index, represents)

Bases: object

A vertex in a digraph representing a donor (directed or non-directed).

__init__(index, represents)

property index: int

Get the index (in the graph) of this vertex.

Returns:

the index

isNdd()

True if this vertex corresponds to a non-directed donor.

Return type:

bool

Returns:

True if this vertex corresponds to a non-directed donor

property donor: Donor

Return the donor associated with this vertex.

Returns:

the associated donor

addEdgeIn(edge)

Add an edge leading in to this vertex.

Parameters:

edge (Edge) – the edge

Return type:

None

addEdgeOut(edge)

Add an edge leading out from this vertex.

Parameters:

edge (Edge) – the edge

Return type:

None

property edgesIn: list[Edge]

Return the list of edges leading in to this vertex.

Returns:

the list of edges leading in to this vertex.

property edgesOut: list[Edge]

Return the list of edges leading out from this vertex.

Returns:

the list of edges leading out of this vertex.

adjacent()

Return the neighbours of this vertex

Return type:

list[Vertex]

Returns:

the list of neighbouring vertices

static sink()

Return type:

Vertex

class Exchange(_id, vertices)

Bases: object

An exchange is either a cycle or a chain. This class lets us embed information (like embedded exchanges, or alternates) into the exchange.

__init__(_id, vertices)

property id: str

The ID of the exchange.

property vertices: tuple[Vertex, ...]

The vertices in this exchange.

property chain: bool

Returns True if this exchange represents a chain.

allDonors()

Get all of the donors involved in this exchange.

Return type:

list[Donor]

allRecipients()

Get all of the recipients.

Return type:

list[Recipient]

allPairs()

Get all the donor,recipient pairs in this exchange, in order.

Return type:

list[tuple[Donor, Optional[Recipient]]]

hasParticipant(participant)

Return True if this exchange involves the given participant.

Parameters:

participant (Donor | Recipient) – The participant in question

Return type:

bool

Returns:

True if and only if the participant is involved in this exchange.

hasTransplant(transplant)

Return True if this exchange involves the given transplant.

Parameters:

transplant (Transplant) – The transplant in question

Return type:

bool

Returns:

True if and only if the transplant is in this exchange.

transplantPairs()

Get the pairs of transplant-donor, transplant-recipient corresponding to this exchange.

Return type:

list[tuple[Donor, Recipient]]

backarc_exchanges_uk()

Return the exchanges that contain backarcs from this exchange (by the UK definition of backarc).

A backarc, by UK counting, is only defined for exchanges with three transplants (i.e., three donors). Let the three donors be A, B, and C. A backarc exists if A (respectively B and C) can donate to the paired recipient of C (respectively A and B).

Return type:

list[Exchange]

Returns:

A list containing each Exchange object that has a backarc from this Exchange.

num_backarcs_uk()

Return the number of backarcs in this exchange (by the UK definition of backarc).

A backarc, by UK counting, is only defined for exchanges with three transplants (i.e., three donors). Let the three donors be A, B, and C. A backarc exists if A (respectively B and C) can donate to the paired recipient of C (respectively A and B).

Return type:

int

Returns:

The number of backarcs in this Exchange.

property alternates: list[Exchange]

Return the alternate exchanges for this exchange. An alternate exchange is one that still matches exactly the same set of recipients, but possibly with either different donors (if some recipients are paired with multiple donors) or perhaps different donors and recipients are paired together.

Note that this attribute is only populated if the function build_alternates_and_embeds is run.

add_alternate(alt)

Add an alternate exchange. An alternate exchange is one that still matches exactly the same set of recipients, but possibly with either different donors (if some recipients are paired with multiple donors) or perhaps different donors and recipients are paired together.

Parameters:

alt (Exchange) – The alternate exchange.

Return type:

None

add_alternates(alts)

Add alternate exchanges. An alternate exchange is one that still matches exactly the same set of recipients, but possibly with either different donors (if some recipients are paired with multiple donors) or perhaps different donors and recipients are paired together.

Parameters:

alts (Iterable[Exchange]) – The alternate exchanges.

Return type:

None

property embedded: list[Exchange]

Returns the exchanges embedded in this exchange. An embedded exchange is one that still matches some of the recipients within this exchange, but does not match any recipients not in this exchange.

Note that this attribute is only populated if the function build_alternates_and_embeds is run.

add_embedded(embed)

Add an embedded exchange. An embedded exchange is one that still matches some of the recipients within this exchange, but does not match any recipients not in this exchange.

Parameters:

embed (Exchange) – The embedded exchange.

Return type:

None

add_embeddeds(embeds)

Adds embedded exchanges. An embedded exchange is one that still matches some of the recipients within this exchange, but does not match any recipients not in this exchange.

Parameters:

embeds (Iterable[Exchange]) – The embedded exchanges.

Return type:

None

class Edge(donor, start, end)

Bases: object

An edge in a digraph, representing a potential transplant. An edge is always associated with a donor.

__init__(donor, start, end)

property donor: Donor

Return the donor associated with this transplant.

Returns:

The associated donor

property start: Vertex

Return the start point of this edge.

Returns:

the start Vertex of this edge

property end: Vertex

Return the end-point of this edge.

Returns:

the end Vertex of this edge

addProperty(name, value)

Add an arbitrary property to this edge. This can be used for e.g. a score value associated with the transplant.

Parameters:

name (str) – the name of the property

Return type:

None

getProperty(name)

Get a property of this transplant.

Parameters:

name (str) – the name of the property

Return type:

Any

Returns:

the associated value, which may have any type

class CompatibilityGraph(instance=None)

Bases: object

A Compatibility Graph is a digraph representing a KEP instance. Note that each vertex is a donor. Each edge corresponds to a potential transplant, and thus is associated with a donor that is paired with the recipient at beginning of the arc.

__init__(instance=None)

property size: int

The number of vertices in the graph.

Returns:

the number of vertices

property vertices: list[Vertex]

The vertices in the graph.

Returns:

the vertices

edges()

The edges in the graph.

Return type:

list[Edge]

Returns:

the edges

number_ndds()

Count the number of non-directed donors in this graph.

Return type:

int

Returns:

The number of non-directed donors.

hasDonor(donor)

Return True if the given donor is represented in this graph.

Return type:

bool

hasRecipient(recipient)

Return True if the given donor is represented in this graph.

Return type:

bool

exchangeEdges(exchange)

Return the edges in the given exchange.

Parameters:

exchange (Exchange) – The exchange in question

Return type:

list[Edge]

Returns:

The edges in this exchange.

addDonor(donor)

Add a vertex representing a donor.

Parameters:

donor (Donor) – a donor to be added to the graph.

Return type:

None

donorVertex(donor)

Get the vertex associated with a donor.

Parameters:

donor (Donor) – the donor to find

Return type:

Vertex

Returns:

the vertex associated with the donor

addEdges(donor, recip, properties)

Add edges to the digraph corresponding to some potential transplant, optionally with some additional properties. Note that since the graph uses donors to represent vertices, if the given recipient has multiple donors then one edge will be added for each paired donor

Parameters:

• donor (Donor) – the donor in the transplant

• recip (Recipient) – the recipient in the transplant

• properties (dict[str, Any]) – an optional dictionary mapping property names (as strings) to properties

findChains(maxChainLength, index_offset=0)

Finds and returns all chains in this graph. Note that this is specifically chains, and does not include cycles.

Parameters:

• maxchainLength – the maximum length of any chain

• index_offset (int) – By default, chains are given IDs starting at zero. By setting this parameter to a non-zero value, IDs start at this number. This can help avoid ID clashes.

Return type:

list[Exchange]

Returns:

a list of chains, where each chain is represented as a list of vertices

findCycles(maxCycleLength, index_offset=0, considerConnectedComponents=False)

Finds and returns all cycles in this graph. Note that this is specifically cycles, and does not include chains.

Parameters:

• maxCycleLength (int) – the maximum length of any cycle

• index_offset (int) – By default, chains are given IDs starting at zero. By setting this parameter to a non-zero value, IDs start at this number. This can help avoid ID clashes.

• considerConnectedComponents (bool) – If True, we use Tarjan’s algorithm to first split the graph into strongly connected components and never follow edges that go between strongly connected components. This is valid as any cycle must exist completely within one strongly connected cycle, but the overhead of calculating strongly connected components is generally not worth it. If False, we instead are allowed to follow any edge.

Return type:

list[Exchange]

Returns:

a list of cycles, where each cycle is represented as a list of vertices

dot()

Return a string that represents this graph in DOT format.

Return type:

str

build_alternates_and_embeds(exchanges, uk_variant=0)

Finds and adds alternate and embedded exchanges based on the given exchanges. An alternate exchange is one that still matches exactly the same set of recipients, but possibly with either different donors (if some recipients are paired with multiple donors) or perhaps different donors and recipients are selected for transplant. An embedded exchange is one that matches some (but not all) of the recipients within this exchange, but still does not match any recipients not in this exchange. Note that in both cases, if the exchange is a chain, we require that any alternate or embedded exchanges that are also chains must still be initiated by the same non-directed donor.

Note that if uk_variant is either 1 or 2, then alternate exchanges are limited to those that have the recipients in the same order. If uk_variant is 1, then all embedded exchanges are returned, whereas if uk_variant is 2, then only embedded exchanges that do not use new (alternate) donors are included.

Parameters:

• exchanges (list[Exchange]) – The exchanges to search for alternates

• uk_variant (int) – Whether to limit alternate and embedded exchanges to those that NHSBT expect

Return type:

None