Logo

Output Data Formats

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} ]}

  }
}
          
operation
optimal
<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} ]}
  }
}
        
operation
optimal
{ "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

v1.0.0