helper.contract_tree

helper.contract_tree(T, node_set)[source]

Helper function for valid_minor.

Contract the tree T to contain only the nodes in node_set:
  1. contract all edges containing no nodes in node_set,
  2. contract all edges containing s and a node not in node_set,
  3. contract all edges containing o and a node not in node_set,
  4. contract all edges containing d and a node not in node_set, and
  5. contract all edges containing t and a node not in node_set.
Parameters:
  • T (graph) – The current spanning tree of the PDP instance.
  • node_set (set) – Set of nodes to be in sub-tree of T.
Returns:

T_con – Contraction of T which contains only nodes in node_set.
Return type:

graph