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
- 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.
- 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 chain: bool
Returns True if this exchange represents a chain.
- 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.
- 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
- 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
- number_ndds()
Count the number of non-directed donors in this graph.
- Return type:
int
- Returns:
The number of non-directed donors.
- exchangeEdges(exchange)
Return the edges in the given 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.
- 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
- 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 cycleindex_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 alternatesuk_variant (
int
) – Whether to limit alternate and embedded exchanges to those that NHSBT expect
- Return type:
None