Output Data Formats
Table of Contents
Overview
The format of the output data is determined by two factors. The first is the extension after the period on the API call.
For example, a call to find.xml will result in the output being returned in XML format and similarly a call to
find.json will return JSON. The second (as of version 1.0.0 of the application) is the value passed into the output_format parameter. Currently
there are two possible values that are supported namely nhsbtv1 and nhsbtv2. A value of nhsbtv1 will
return the data in the original data format, and is the default value should this parameter not be specified. A value of
nhsbtv2 will return an extended set of attributes of use primarily when the maximum exchange size is greater than
3. A discussion of the exact differences when using nhsbtv1 and nhsbtv2 can be found
here for XML and here for JSON.
XML
Output
XML can be used to format the data output by the service. With SOAP requests this is the only option, however using the REST API allows the output format to be specified (see the REST section of this guide).
Below we give an example of a set of input parameters to the find API call (for both SOAP and REST)
and show the resulting data output by the service using these parameters.
data{ "data" : { "1" : { "sources" : [1], "dage" : 65, "matches" : [ { "recipient" : 2, "score" : 3}, { "recipient" : 3, "score" : 1}, { "recipient" : 4, "score" : 2} ]}, "2" : { "sources" : [2], "dage" : 45, "matches" : [ { "recipient" : 1, "score" : 2}, { "recipient" : 5, "score" : 1} ]}, "3" : { "sources" : [3], "dage" : 25, "matches" : [ { "recipient" : 1, "score" : 1}, { "recipient" : 5, "score" : 1} ]}, "4" : { "sources" : [4], "dage" : 55, "matches" : [ { "recipient" : 2, "score" : 3}, { "recipient" : 3, "score" : 2}, { "recipient" : 5, "score" : 4} ]}, "5" : { "sources" : [5], "dage" : 30, "matches" : [ { "recipient" : 2, "score" : 1}, { "recipient" : 4, "score" : 2} ]}, "6" : { "sources" : [3], "dage" : 25, "matches" : [ { "recipient" : 1, "score" : 1}, { "recipient" : 5, "score" : 1} ]} } }operationoptimal
<data>
<algorithm>Optimal set of exchanges with respect to the optimality criteria</algorithm>
<output>
<all_cycles>
<cycle id="0" backarcs="0" weight="11.05" alt="">
<pair><p>1</p><d>1</d><tb>0.025</tb><dif>3</dif><s>3</s></pair>
<pair><p>2</p><d>2</d><tb>0.025</tb><dif>3</dif><s>2</s></pair>
</cycle>
<cycle id="1" backarcs="0" weight="2.018" alt="2">
<pair><p>1</p><d>1</d><tb>0.009</tb><dif>0</dif><s>1</s></pair>
<pair><p>3</p><d>3</d><tb>0.009</tb><dif>0</dif><s>1</s></pair>
</cycle>
<cycle id="2" backarcs="0" weight="2.018" alt="1">
<pair><p>1</p><d>1</d><tb>0.009</tb><dif>0</dif><s>1</s></pair>
<pair><p>3</p><d>6</d><tb>0.009</tb><dif>0</dif><s>1</s></pair>
</cycle>
<cycle id="3" backarcs="0" weight="8.0605" alt="">
<pair><p>2</p><d>2</d><tb>0.03025</tb><dif>3</dif><s>1</s></pair>
<pair><p>5</p><d>5</d><tb>0.03025</tb><dif>3</dif><s>1</s></pair>
</cycle>
<cycle id="4" backarcs="0" weight="6.0405" alt="">
<pair><p>4</p><d>4</d><tb>0.02025</tb><dif>0</dif><s>4</s></pair>
<pair><p>5</p><d>5</d><tb>0.02025</tb><dif>0</dif><s>2</s></pair>
</cycle>
<cycle id="5" backarcs="1" weight="16.097" alt="">
<pair><p>1</p><d>1</d><tb>0.036</tb><dif>3</dif><s>2</s></pair>
<pair><p>4</p><d>4</d><tb>0.036</tb><dif>3</dif><s>3</s></pair>
<pair><p>2</p><d>2</d><b>0</b><tb>0.025</tb><dif>3</dif><s>2</s></pair>
</cycle>
<cycle id="6" backarcs="1" weight="8.061" alt="7">
<pair><p>1</p><d>1</d><tb>0.036</tb><dif>3</dif><s>2</s></pair>
<pair><p>4</p><d>4</d><tb>0.016</tb><dif>0</dif><s>2</s></pair>
<pair><p>3</p><d>3</d><b>1</b><tb>0.009</tb><dif>0</dif><s>1</s></pair>
</cycle>
<cycle id="7" backarcs="1" weight="8.061" alt="6">
<pair><p>1</p><d>1</d><tb>0.036</tb><dif>3</dif><s>2</s></pair>
<pair><p>4</p><d>4</d><tb>0.016</tb><dif>0</dif><s>2</s></pair>
<pair><p>3</p><d>6</d><b>2</b><tb>0.009</tb><dif>0</dif><s>1</s></pair>
</cycle>
<cycle id="8" backarcs="2" weight="12.0865" alt="">
<pair><p>2</p><d>2</d><b>3</b><tb>0.03025</tb><dif>3</dif><s>1</s></pair>
<pair><p>5</p><d>5</d><b>4</b><tb>0.02025</tb><dif>0</dif><s>2</s></pair>
<pair><p>4</p><d>4</d><<tb>0.036</tb><dif>3</dif><s>3</s></pair>
</cycle>
<cycle id="9" backarcs="1" weight="8.0785" alt="10">
<pair><p>3</p><d>3</d><tb>0.04225</tb><dif>3</dif><s>1</s></pair>
<pair><p>5</p><d>5</d><b>4</b><tb>0.02025</tb><dif>0</dif><s>2</s></pair>
<pair><p>4</p><d>4</d><tb>0.016</tb><dif>0</dif><s>2</s></pair>
</cycle>
<cycle id="10" backarcs="1" weight="8.0785" alt="9">
<pair><p>3</p><d>6</d><tb>0.04225</tb><dif>3</dif><s>1</s></pair>
<pair><p>5</p><d>5</d><b>4</b><tb>0.02025</tb><dif>0</dif><s>2</s></pair>
<pair><p>4</p><d>4</d><tb>0.016</tb><dif>0</dif><s>2</s></pair>
</cycle>
</all_cycles>
<exchange_data>
<entry weight="14.1045"
two_way_exchanges="1"
total_transplants="5"
three_way_exchanges="1">
<description>(COIN) Optimal set of exchanges</description>
<exchanges><cycle>1</cycle><cycle>8</cycle></exchanges>
</entry>
</exchange_data>
</output>
</data>
The <algorithm> element contains a description of the algorithm that was run. In this
case, as we ran the algorithm with operation optimal, the text states that we have returned an optimal
matching as defined in the optimality criteria section.
Next, <all_cycles> contains the set of all possible cycles for this data set. An
individual cycle is represented by a <cycle> element. For example:
<cycle id="6" backarcs="1" weight="8.061" alt="7">
<pair>
<p>1</p>
<d>1</d>
<tb>0.036</tb>
<dif>3</dif>
<s>2</s>
</pair>
<pair>
<p>4</p>
<d>4</d>
<tb>0.016</tb>
<dif>0</dif>
<s>2</s>
</pair>
<pair>
<p>3</p>
<d>3</d>
<b>1</b>
<tb>0.009</tb>
<dif>0</dif>
<s>3</s>
</pair>
</cycle>
Here we have a three-way exchange (as the cycle element contains three <pair> elements), and this
cycle has a (group) id of 6. The id here is used to uniquely identify the cycle. The cycle also
has a single backarc (backarcs="1" attribute) and has weight 8.061 (weight="8.061" attribute). The final
attribute of the <cycle> element is alt: this holds a comma separated list of alternative
cycles to this one. An alternative cycle is a cycle with the the same set of patients, but contains
at least one different donor (this can only happen if at least one of the patients has multiple donors). In
the example, there is only one alternative cycle to 6, which is the cycle with id 7. If there were multiple
choices of alternative cycles then the attribute would take the form alt="5,9,10".
The final attribute that may be included with a <cycle> element is altruistic. This
attribute holds a boolean value that indicates whether the cycle contains an altruistic donor. If the attribute is not
specified then we take this to mean that there are no altruistic donors in the cycle.
The <pair> elements that form the content of <cycle> hold
information about the participants in a cycle, whether it contains an embedded pairwise exchange (and if so specifies
the id of the embedded exchange ) or if any of the donors are altruistic
(the order of the <pair> elements indicate the direction of the cycle).
In our example above the cycle with id 4 is a three-way exchange involving patients 1, 4 and 3. We identify the
patients by inspecting the value of each <p> element of a <pair>. A patient's
respective donor is found in the sibling element <d> of the patient. Furthermore,
we can establish if a backarc exists between two (donor,patient) pairs by checking for the existence of the <b>
element of a pair. If a <pair> element contains a <b> tag this indicates
that an embedded two-way exists between this (donor,patient) pair and the next pair in the list
(or the first in the case where the last <pair> contains the <b> element).
The value stored in this <b> element holds the group id of the embedded pairwise exchange.
We note that the embedded pairwise exchange need not be between the donors who make up the three-way exchange.
If it is indeed not made up of donors from the three-way exchange it will hold the id of the pairwise exchange
with the largest score. The final three items in the <pair> element hold the tie breaker
calculation (<tb>), the donor-to-donor age difference points (<dif>), and the
original score passed into the algorithms (<s>) between
this (donor, patient) pair and the next (donor,patient) pair on the list. So in the example above we have that
the donor-to-donor age difference points between the first two pairs in the three-cycle (that is, the pairs containing donors
1 and 4) is 3 and the tie breaker score between these pairs is 0.036 with the original score passed into the algorithms
between these two (donor,patient) pairs being 2.
So looking at cycle 6 above we have that donor 1 for patient 1 gives a kidney to patient 4, patient 4's
donor with id 4 then gives a kidney to patient 3, whose donor with id 3 gives a kidney to patient 1, completing
the three-way exchange. We note that in the final <pair> element <b> has the
value 1, this indicates that there exists an embedded two-way between patient 1 and patient 3 and this embedded
two-way has id 2.
It is also possible that a <pair> element may contain a child element <a>.
An example is shown below:
<cycle id="15" backarcs="1" weight="12.0845" alt="" altruistic="true">
<pair>
<d>12</d>
<b>false</b>
<a>true</a>
<tb>0.04225</tb>
<dif>3</dif>
<s>3</s>
</pair>
<pair>
<p>4</p>
<d>4</d>
<tb>0.04225</tb>
<dif>3</dif>
<s>3</s>
</pair>
</cycle>
The element <a> in the first <pair> element above
indicates that donor 12 is an altruistic donor. We note that since the donor is altruistic, the <pair>
need not contain a <p> element.
The set of exchanges returned by the service can be found within <exchange_data>.
This element consists of a single item named entry that has four attributes. The first
attribute, weight, holds the total weight of the set of cycles that make up this exchange set.
The attributes two_way_exchanges and three_way_exchanges hold the number
of two-way and three-way exchanges in this set of exchanges respectively. The attribute total_transplants
holds the total number of transplants that would take place if each of the two-way and
three-way exchanges were to go ahead.
The first child element (<description>) of <entry> contains information about the
algorithm that was run - in the example above the COIN Integer Programming algorithm was used to find the optimal
set of exchanges. The ids of the cycles that make up the optimal set of exchanges
are found in the <cycle> elements of <exchanges>. We therefore have in the
example above that the set of exchanges consists of one pairwise and one 3-way exchange, the pairwise exchange has
id 1 (line 56) and the 3-way exchange has id 8 (line 57). That is, the pairwise consists of patients 1 and 3
with donors 1 and 3 respectively, and the 3-way consists of patients 2, 5, and 4 with donors 2, 5 and 4
respectively. The pairwise has weight 2.018 and the 3-way has weight 12.0865 with two embedded pairwise exchanges
(with ids 3 and 4 respectively).
nhsbtv2 Output
Rather than go through every detail of nhsbtv2 format, we simply
highlight the differences between this format and that returned using nhsbtv1.
Both output formats contain largely the same amount of data. The goal
of the nhsbtv2 format was to accommodate the inclusion of cycles larger than size 3 and also return
some useful information for statistics.
Below is an example of <cycle> element found in nhsbtv2.
<cycle id="234" backarcs="2" weight="60.58698" alt="">
<match>
<pair>
<p>32</p>
<d>34</d>
<tb>0.02704</tb>
<dif>3</dif>
<s>0</s>
</pair>
<pair>
<p>61</p>
<d>60</d>
<b>141</b>
<tb>0.03969</tb>
<dif>3</dif>
<s>18.5</s>
</pair>
<pair>
<p>22</p>
<d>23</d>
<tb>0.02025</tb>
<dif>0</dif>
<s>36</s>
</pair>
</match>
<embedded>
<item>
<size>2</size>
<ids>141,142</ids>
</item>
</embedded>
</cycle>
As we can see the contents of the <cycle> element have changed with the introduction of two tags
<match> and <embedded>. The entire contents of the <cycle>
element in nhsbtv1 have then been moved to the <match> element. Therefore, the only
real new element here is the <embedded> tag. The <embedded> element allows us to
identify the set of embedded cycles within this cycle. So in the example above, we have two embedded cycles of size (<size>)
2 (i.e. embedded pairwise exchanges). We can then identify the specific cycles by looking at the <ids>
element which contains the comma separated string 141,142. Therefore the two embedded pairwise exchanges
are those with ids 141 and 142. An example of a cycle that contains with more than one type of embedded exchange is shown below:
<embedded>
<item>
<size>2</size>
<ids>141,142</ids>
</item>
<item>
<size>3</size>
<ids>156</ids>
</item>
</embedded>
Here we have two different types of embedded exchanges (as we have two <item> elements).
The first <item> contains embedded exchanges of size 2, of which there are two,
with ids 141 and 142. The second <item> holds embedded exchanges of size 3 - as identified by
the <size> element. However, in this case we have only a single embedded 3-way, namely that
with id 156.
The second change to the output can be seen within the <exchange_data> section. An example
is shown below.
<entry weight="884.25505" two_way_exchanges="1" three_way_exchanges="1"
four_way_exchanges="1" total_transplants="9">
<description>
(COIN) iteration to maximise the number of effective pairwise exchanges using lemon,
iteration to maximise the total number of transplants,
iteration to minimise the number of 3-way exchanges,
iteration to maximise the total number of backarcs,
iteration to maximise the total weight
</description>
<exchanges>
<cycle>63</cycle>
<cycle>74</cycle>
<cycle>87</cycle>
</exchanges>
<unused_altruistics>1567,3423</unused_altruistics>
</entry>
The first thing to notice is that we have an attribute four_way_exchanges that we have not
seen in any previous examples. As the v2/find.* API calls support finding cycles larger than
3-ways we have introduced totals for other cycle sizes that are included in the solution. In the case
above we see an example of this with the four_way_exchanges attribute of the <entry>
element - here we must have asked for a maximum cycle size of 4. Similar attributes are added depending
on the maximum size of cycle that was required.
The final change to observe is that we return a comma separated list of donor ids in the <unused_altruistics>
element. These donor ids correspond to the set of altruistic donors who were not used as part of the matching run.
That is, the donors are not contained in any of the result cycles. So in the example above, altruistic donors
with ids 1567 and 3423 were not participants in the cycles with ids 63, 74 and 87.
Column Generation Output
In order to use column generation you must run the kidney_nhs command line application, which
is discussed here.
Column generation is necessary when it becomes impractical to identify all cycles for a particular instance.
As such, the XML output by kidney_nhs application may be different to that which is returned using the
kidney_server web service.
We first note that the kidney_nhs command line application need not return XML in the new format
described in this section. The data will only be returned in this format if the application itself determines
if column generation is necessary - this process is described in the col_gen_detect description in the
Config section. However, should column generation
be used the XML data will be returned in the format described below.
We start by showing an example of the XML returned by the kidney_nhs application.
<data>
<algorithm>
Optimal set of exchanges with respect to the optimality criteria
</algorithm>
<output>
<cycles>
<cycle id="2" backarcs="1" weight="2.018" alt="">
<pair><p>1</p><d>1</d><tb>0.009</tb><dif>0</dif><s>1</s></pair>
<pair><p>3</p><d>3</d><tb>0.009</tb><dif>0</dif><s>1</s></pair>
</cycle>
<cycle id="3" backarcs="0" weight="8.0605" alt="">
<pair><p>2</p><d>2</d><tb>0.03025</tb><dif>3</dif><s>1</s></pair>
<pair><p>5</p><d>5</d><tb>0.03025</tb><dif>3</dif><s>1</s></pair>
</cycle>
<cycle id="4" backarcs="0" weight="6.0405" alt="">
<pair><p>4</p><d>4</d><tb>0.02025</tb><dif>0</dif><s>4</s></pair>
<pair><p>5</p><d>5</d><tb>0.02025</tb><dif>0</dif><s>2</s></pair>
</cycle>
<cycle id="1" backarcs="2" weight="12.0865" alt="">
<pair><p>2</p><d>2</d><b>3</b><tb>0.03025</tb><dif>3</dif><s>1</s></pair>
<pair><p>5</p><d>5</d><b>4</b><tb>0.02025</tb><dif>0</dif><s>2</s></pair>
<pair><p>4</p><d>4</d><tb>0.036</tb><dif>3</dif><s>3</s></pair>
</cycle>
</cycles>
<exchange_data>
<entry weight="14.1045" two_way_exchanges="1" total_transplants="5"
three_way_exchanges="1">
<description>
(ABACUS) iteration to maximise the number of effective pairwise exchanges using
lemon, iteration to maximise the total number of transplants, iteration to
maximise the number of pairwise exchanges, iteration to maximise the total
number of backarcs, iteration to maximise the total weight
</description>
<exchanges>
<cycle>1</cycle>
<cycle>2</cycle>
</exchanges>
</entry>
</exchange_data>
</output>
</data>
From the example above we can see that the output no longer contains an <all_cycles>
XML element. Instead this has been replaced by a <cycles> element that contains only
those cycles that either form part of an optimal matching, or are an alternative/embedded cycle of a
cycle that is in the optimal set of exchanges. We note that it is sufficient to check
for the existence of the <all_cycles> element in the data to determine which format
has been returned.
In the example above the
optimal set of exchanges consists of the two cycles, namely those with ids 1 and 2, both of which can be found in
the <cycles> element. Additionally, the cycle with id 1 has two embedded pairwise exchanges,
namely those with ids 3 and 4, and as a result both of these appear as a child in the
<cycles> element.
The format of the individual cycle elements can be controlled with the --format switch
of the kidney_nhs application and
as with the web API can either be nhsbtv1 or nhsbtv2 and has a similar impact
on the <cycle> elements as that described in the nhsbtv2 Output
section.
So as we can see the format is almost identical to that produced by the web API the only difference being that we no longer can list all possible cycles of an instance and so we only list those cycles that actually belong to the optimal set of exchanges, or that are referenced by those cycles as an alternative or embedded cycle.
Errors
If an error occurs during the processing of a request then an error message is normally sent back to the user. A sample error message is shown below:
<data>
<algorithm>
Optimal set of exchanges
</algorithm>
<error>
Unrecognised operation passed to program, must be one of optimal,
maxcard, or pairs.
</error>
</data>
The <algorithm> element will provide a description of the algorithm being run. More
important is the <error> element which provides a text-based description of the
actual error that took place.
JSON
In addition to XML, the REST API also supports JSON as an output format. JSON provides a more concise way of modelling the output data and can save a significant number of bytes especially for large datasets.
Output
Below we give an example of a set of input parameters to the find.json REST API call
and show the resulting data output by the service using these parameters.
data{ "data" : { "1" : { "sources" : [1], "dage" : 65, "matches" : [ { "recipient" : 2, "score" : 3}, { "recipient" : 3, "score" : 1}, { "recipient" : 4, "score" : 2} ]}, "2" : { "sources" : [2], "dage" : 45, "matches" : [ { "recipient" : 1, "score" : 2}, { "recipient" : 5, "score" : 1} ]}, "3" : { "sources" : [3], "dage" : 25, "matches" : [ { "recipient" : 1, "score" : 1}, { "recipient" : 5, "score" : 1} ]}, "4" : { "sources" : [4], "dage" : 55, "matches" : [ { "recipient" : 2, "score" : 3}, { "recipient" : 3, "score" : 2}, { "recipient" : 5, "score" : 4} ]}, "5" : { "sources" : [5], "dage" : 30, "matches" : [ { "recipient" : 2, "score" : 1}, { "recipient" : 4, "score" : 2} ]}, "6" : { "sources" : [3], "dage" : 25, "matches" : [ { "recipient" : 1, "score" : 1}, { "recipient" : 5, "score" : 1} ]} } }operationoptimal
{ "algorithm" : "Optimal set of exchanges with respect to the optimality criteria",
"output" :
{ "all_cycles": {
"0": {"cycle": [{"p": 1,"d": 1,"tb": 0.025,"dif": 3,"s": 3},
{"p": 2,"d": 2,"tb": 0.025,"dif": 3,"s": 2}],
"backarcs": 0,
"weight": 11.05,
"alt": []},
"1": {"cycle": [{"p": 1,"d": 1,"tb": 0.009,"dif": 0,"s": 1},
{"p": 3,"d": 3,"tb": 0.009,"dif": 0,"s": 1}],
"backarcs": 0,
"weight": 2.018,
"alt": [2]},
"2": {"cycle": [{"p": 1,"d": 1,"tb": 0.009,"dif": 0,"s": 1},
{"p": 3,"d": 6,"tb": 0.009,"dif": 0,"s": 1}],
"backarcs": 0,
"weight": 2.018,
"alt": [1]},
"3": {"cycle": [{"p": 2,"d": 2,"tb": 0.03025,"dif": 3,"s": 1},
{"p": 5,"d": 5,"tb": 0.03025,"dif": 3,"s": 1}],
"backarcs": 0,
"weight": 8.0605,
"alt": []},
"4": {"cycle": [{"p": 4,"d": 4,"tb": 0.02025,"dif": 0,"s": 4},
{"p": 5,"d": 5,"tb": 0.02025,"dif": 0,"s": 2}],
"backarcs": 0,
"weight": 6.0405,
"alt": []},
"5": {"cycle": [{"p": 1,"d": 1,"tb": 0.036,"dif": 3,"s": 2},
{"p": 4,"d": 4,"tb": 0.036,"dif": 3,"s": 3},
{"p": 2,"d": 2,"b": 0,"tb": 0.025,"dif": 3,"s": 2}],
"backarcs": 1,
"weight": 16.097,
"alt": []},
"6": {"cycle": [{"p": 1,"d": 1,"tb": 0.036,"dif": 3,"s": 2},
{"p": 4,"d": 4,"tb": 0.016,"dif": 0,"s": 2},
{"p": 3,"d": 3,"b": 1,"tb": 0.009,"dif": 0,"s": 1}],
"backarcs": 1,
"weight": 8.061,
"alt": [7]},
"7": {"cycle": [{"p": 1,"d": 1,"tb": 0.036,"dif": 3,"s": 2},
{"p": 4,"d": 4,"tb": 0.016,"dif": 0,"s": 2},
{"p": 3,"d": 6,"b": 2,"tb": 0.009,"dif": 0,"s": 1}],
"backarcs": 1,
"weight": 8.061,
"alt": [6]},
"8": {"cycle": [{"p": 2,"d": 2,"b": 3,"tb": 0.03025,"dif": 3,"s": 1},
{"p": 5,"d": 5,"b": 4,"tb": 0.02025,"dif": 0,"s": 2},
{"p": 4,"d": 4,"tb": 0.036,"dif": 3,"s": 3}],
"backarcs": 2,
"weight": 12.0865,
"alt": []},
"9": {"cycle": [{"p": 3,"d": 3,"tb": 0.04225,"dif": 3,"s": 1},
{"p": 5,"d": 5,"b": 4,"tb": 0.02025,"dif": 0,"s": 2},
{"p": 4,"d": 4,"tb": 0.016,"dif": 0,"s": 2}],
"backarcs": 1,
"weight": 8.0785,
"alt": [10]},
"10": {"cycle": [{"p": 3,"d": 6,"tb": 0.04225,"dif": 3,"s":: 1},
{"p": 5,"d": 5,"b": 4,"tb": 0.02025,"dif": 0,"s": 2},
{"p": 4,"d": 4,"tb": 0.016,"dif": 0,"s": 2}],
"backarcs": 1,
"weight": 8.0785,
"alt": [9]}},
"exchange_data": [
{ "description": "(COIN) Optimal set of exchanges",
"exchanges": [1,8],
"weight": 14.1045,
"two_way_exchanges": 1,
"total_transplants": 5,
"three_way_exchanges": 1 } ]
}
}
As we can see the algorithm element contains a description of the algorithm that was run. In this
case as we ran the algorithm with operation optimal, the text indicates that we have returned a set of optimal
exchanges as defined in the optimality criteria section.
Next, all_cycles contains the set of all possible cycles for this data set. Each key in this
object corresponds to a group id for the cycle, and this id is used to uniquely identify a cycle. In the example
output above we can see that the first element in all_cycles represents a cycle with id 0. At this
node we hold information about cycle 0, in particular we can see the (donor,patient) pairs that are involved in
a cycle (the cycle key), the number of backarcs in the cycle (the backarcs key),
the weight of the cycle (the weight key)
and whether there are any cycles that are alternatives to this one (the alt key). The contents of both
the backarcs and weight keys are obvious, therefore we concentrate on the
cycle and alt keys.
The cycle key holds information about the patients (the p key) and their corresponding donors
(the d key) that are involved in a cycle. Taking the cycle with id 5 as an example, we can see that cycle 5 is
a 3-way exchange, as the cycle array consists of three elements, and involves patients 1, 4 and 2 - as these
are the values stored against each key p in the array. The order that the (donor,patient) pairs appear
in the array is important and indicates the direction of the exchange. Furthermore, we observe that each p element
has a sibling d that holds the id of their donor. If the cycle is a 3-way exchange then the object
may also contain a b element. This element indicates the presence of an embedded two-way. As an example
of the use of the keys d and b we use cycle 5 again above.
Here we can see that the donors for patients 1, 4, and 2 are donors with ids 1, 4 and 2 respectively
(the donor ids need not be the same as the
patient ids, they just happen to be in this example). Cycle 5 also contains an embedded pairwise exchange between
(donor,patient) pairs (1,1) and (2,2). This can be seen in the output by observing the fact that the last
element in the cycle array has the value 0 for b. This means that there exists an embedded pairwise exchange
between the corresponding (donor,patient) pair in the array and the next (donor,patient) pair in the array, or in this case
as this is the last pair, it's between the final pair and the first. In particular, we can identify the embedded
pairwise exchange from the value stored in b, so for cycle 5 we have that the embedded pairwise
exchange has id 0. We note that an embedded pairwise exchange need not contain any of the donors from the original
cycle. The final three elements in the objects that make up the cycle array are tb, dif and s
The value held against the tb key holds the tie breaker calculation between this element and the
next in the array, similarly dif holds the donor-to-donor age difference points between these two
elements. Finally s holds the original score between this element and the next in the array, this is the
same score that was passed in as part of the input data.
As in the case of key b, the values of tb, dif and s for the last
element in the array describe the tie breaker calculation and donor-to-donor age difference between the final
element and the first.
Each cycle also contains the key alt that holds an array of ids. These integers correspond to the
ids of other cycles within the all_cycles structure that are an alternative to this one. That is,
there exists an alternative where the same set of patients are involved in the exchange, but the alternative contains
at least one different donor (this can only happen if at least one of the patients has multiple donors). This
information is useful if, say, a donor becomes ill and cannot provide a kidney for transplantation.
To find an alternative donor (or in fact cycle) we need only look at the alt array to see if
there are any possible alternatives to the current cycle.
It may be the case that the cycle is tagged with the altruistic key as shown below.
"15": {"cycle": [{"d": 12,"a": true,"tb": 0.02025,"dif": 0,"s": 2},
{"p": 3,"d": 3,"tb": 0.02025,"dif": 0,"s": 1}],
"backarcs": 0,
"weight": 2.018,
"altruistic": true,
"alt": [2]},
The altruistic key on the object above indicates that the cycle with id 15
contains an altruistic donor. We can identify this altruistic donor by inspecting the cycle
object and observing the the first object in the array now includes a key a with value true. In general,
if the donor is not altruistic then there will be no a key in the object; similarly if the cycle does
not contain an altruistic donor, then the altruistic key will not be present.
Therefore looking at the example above, we can see that
the donor with id 1 is an altruistic donor (note there is no p element here) whereas donor 3
is just a regular donor. We now describe the actual set of exchanges returned by the service.
The calculated set of exchanges are returned as part of the exchange_data array - at the moment this array will
only consist of a single object. In the example above this object provides a description of
the optimality criteria used, the total weight of the exchange set (weight), the number of pariwise exchanges
(two_way_exchanges), the number of 3-way exchanges(three_way_exchanges),
and the total number of transplants (total_transplants) that would take place
if all pairwise and 3-way exchanges were to go ahead. The final member of this object holds the key
information about the optimal set of cycles. In the example above, we can see that exchanges
contains the array [1,8]. This means that for this dataset there are two cycles in the optimal
set of exchanges, namely the cycle with id 1 and the cycle with id 7. Looking at the information on the cycles held in the
all_cycles object, we can see that the cycle with id 1 is a pairwise exchange and contains patients 1 and 3 with donors 1 and 3 respectively.
There is an alternative to this cycle, cycle 2, that contains donors 1 and 6 for patients 1 and 3 respectively.
Cycle 8 is a 3-way exchange that contains patients 2, 5 and 4 and donors 2, 5 and 4 respectively. Here donor 2 for patient
2 gives a kidney to patient 5, patient 5's donor with id 5 gives a kidney to patient 4, and patient 4's donor
with id 4 gives a kidney to patient 2.
nhsbtv2 Output
The changes to the JSON output when nhsbtv2 is used
are relatively straightforward. There are far less changes to the structure than those described in the
XML section. We dive in showing an example of an element from the all_cycles object.
"234": {
"cycle": [
{
"p": 32,
"d": 34,
"tb": 0.02704,
"dif": 3,
"s": 0
},
{
"p": 61,
"d": 60,
"b": 141,
"tb": 0.03969,
"dif": 3,
"s": 18.5
},
{
"p": 22,
"d": 23,
"tb": 0.02025,
"dif": 0,
"s": 36
}
],
"backarcs": 1,
"weight": 60.58698,
"alt": [ ],
"embedded": {
"2": [141,143]
}
}
The only difference here is the addition of a new key embedded. The embedded
key holds an object whose keys correspond to the size n of an embedded cycle, and the values to an array containing
ids of the embedded n-ways. In the example above we have that the 3-cycle with id 234 has two
embedded 2-ways. In particular, the three cycle has the 2-cycles with ids 141 and 143 embedded within it. An
example of an embedded object for a cycle with both embedded 2-cycles and embedded 3-cycles is shown below.
"embedded": {
"2": [141,143]
"3": [156]
}
So in addition to have two embedded 2-ways like the previous example this also says that the cycle
corresponding to this embedded key also has an embedded 3-way exchange. This new format is
required to support reporting embedded cycles where the max_cycle_size option is used in
the v2/find.* API calls.
The second change is the addition of additional keys to the exchange_data object. An example of
the new exchange_data format is shown below.
"exchange_data": [{
"description": "(COIN) iteration to maximise the number of effective pairwise exchanges using lemon,
iteration to maximise the total number of transplants,
iteration to minimise the number of 3-way exchanges,
iteration to maximise the total number of backarcs,
iteration to maximise the total weight",
"exchanges": [
63,
74,
87 ],
"weight": 884.25505,
"two_way_exchanges": 1,
"three_way_exchanges": 1,
"four_way_exchanges": 1,
"total_transplants": 9,
"unused_altruistics": [1567,3423] }]
New in this example is the inclusion of the four_way_exchanges key. As expected this holds the
number of 4-way exchanges in the result. This method of specifying the total number of n-way exchanges is
extended for the general case, .i.e. if we had set the max_cycle_size as 5 then we would have a key
called five_way_exchanges contained in the exchange_data object.
Finally we have the new unused_altruistics array. This holds the ids of those altruistic donors
that do not belong to any of the cycles in the solution. So in the example above we have that altruistic donors
with donor ids 1567 and 3423 have not been used, i.e. they do not belong to any of the cycles with ids 63, 74 or 87.
Column Generation Output
In order to use column generation you must run the kidney_nhs command line application, which
is discussed here.
Column generation is necessary when it becomes impractical to identify all cycles for a particular instance.
As such, the json output by kidney_nhs application may be different to that which is returned using the
kidney_server web service.
We first note that the kidney_nhs command line application need not return JSON in the new format
described in this section. The data will only be returned in this format if the application itself determines
if column generation is necessary - this process is described in the col_gen_detect description in the
Config section. However, should column generation
be used the JSON data will be returned in the format described below.
We start by showing an example of the JSON returned by the kidney_nhs application.
{"algorithm": "Optimal set of exchanges with respect to the optimality criteria",
"output": {
"cycles": {
"1": { "cycle": [{ "p": 1, "d": 1, "tb": 0.009, "dif": 0, "s": 1},
{ "p": 3, "d": 3, "tb": 0.009, "dif": 0, "s": 1}],
"backarcs":1,
"weight":2.018,
"alt":[]},
"2": { "cycle":[{"p": 2, "d": 2, "b": 3, "tb": 0.03025, "dif": 3,"s": 1},
{"p": 5, "d": 5, "b": 4,"tb": 0.02025,"dif":0,"s":2},
{"p": 4, "d": 4, "tb": 0.036, "dif":3, "s": 3}],
"backarcs": 2,
"weight": 12.0865,
"alt": []},
"3":{"cycle":[{"p": 2, "d": 2, "tb": 0.03025, "dif": 3, "s": 1},
{"p": 5, "d": 5, "tb": 0.03025, "dif": 3, "s": 1}],
"backarcs": 0,
"weight": 8.0605,
"alt": []},
"4":{"cycle":[{"p": 4, "d": 4, "tb": 0.02025, "dif": 0, "s": 4},
{"p": 5, "d": 5, "tb": 0.02025, "dif": 0, "s": 2}],
"backarcs": 0,
"weight": 6.0405,
"alt": []}
},
"exchange_data": [
{
"description": "(ABACUS) iteration to maximise the number of effective pairwise
exchanges using lemon, iteration to maximise the total number of
transplants, iteration to maximise the number of pairwise exchanges,
iteration to maximise the total number of backarcs, iteration to
maximise the total weight",
"exchanges": [1,2],
"weight": 14.1045,
"two_way_exchanges": 1,
"total_transplants": 5,
"three_way_exchanges": 1
}
]
}
}
From the example above we can see that the output no longer contains an all_cycles
key in the JSON object. Instead this has been replaced by a cycles key that contains only
those cycles that either form part of the identified optimal set of exchanges, or are an alternative/embedded cycle of a
cycle that is in the optimal set of exchanges. We note that it is sufficient to check
for the existence of the all_cycles key in the data to determine the format of the data returned.
In the example above the
optimal set of exchanges consists of the two cycles, namely those with ids 1 and 2, both of which can be found in
the cycles object. Additionally, the cycle with id 1 has two embedded pairwise exchanges,
namely those with ids 3 and 4, and as a result both of these appear as an element in the
cycles object.
The format of the individual cycle elements can be controlled with the --format switch
of the kidney_nhs application and
as with the web API can either be nhsbtv1 or nhsbtv2 and has a similar impact
on the value of the cycle keys as that described in the nhsbtv2 Output
section.
So as we can see the format is almost identical to that produced by the web API the only difference being that we no longer can list all possible cycles of an instance and so we only list those cycles that actually belong to the optimal set of exchanges, or that are referenced by those cycles as an alternative or embedded cycle.
Errors
If an error occurs during the processing of a request then an error message is normally sent back to the user. A sample error message is shown below:
{ "algorithm" : "Set of all possible exchanges from pairwise up to the optimal solution",
"output" : "Unrecognised operation passed to program, must be one of optimal,
maxcard, or pairs" }
The algorithm element provides a description of the algorithm being run. More
important is the error value, this will provide a text based description of the
actual error that took place