helper.valid_minor

helper.valid_minor(T, node_set)[source]

Helper function for two_tree_traversal.

Determines if node_set produces an s-t oriented sub-tree of T.

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:

False if sub-tree satisfies:

  1. all 3 edges of subset contain s, or
  2. all 3 edges of subset contain t, or
  3. subset contains both edges (s, d) and (t, o)

True otherwise
Return type:

bool