8.5 Querying the Reduced Graph State

A couple of reduced graph state operations are also specified in Section 8.1. Their implementations tend to fall out trivially from the data structures used for minimum degree vertex tracking.

The in_graph operator is realized by the mapping λ\lambda. If the degree of vertex vv is greater than zero, then vv is in VGV^{{\prime}}(G^{{\prime}}). Algorithm 21 formalizes this observation.

Algorithm 21: Determine if a Vertex is in the Reduced Graph
in_graph(vv)
   if evaluate(λ,v\lambda,v)>0>0
      vv is in graph
   else
      vv is not in graph

In a similar vein, the minimum_degree operation is realized by the list operation first. By definition, first(LL) gets the minimum degree vertex. Recall that the minimum degree vertex list LL orders the vertices by ascending degree.