High-Level Pseudo-Code Description of Branch and Bound Tree Search

The following are parameters:

The model graph has node set VM and edge set EM.
The image graph has node set VD and edge set ED
h is the partial mapping so far, initially empty.
h_error is the error of the partial mapping so far, initially zero.

Global variables to the search are:

best_map is the best mapping so far, initially empty.
bound_error is the error of the best mapping so far.

 
treesearch(VM,VD,EM,ED,h,h_error)
   {
   v = first(VM)		/* try next node of VM */
   for each w in VD
      {
      h' = h union {(v,w)}	/* add (v,w) to h to get h' */
      h'_error = h_error	/* h'_error will be the error of h' */

      for each edge (vi,vj) with vi < vj in EM /* check each edge once */
         {
         if one of vi or vj is v and the other is in domain(h')
         then
            if (h'(vi),h'(vj)) is NOT in ED  /* matching edge not there */
            then h'_error = h'_error + 1     /* so add 1 to the error */
         }

      if h'_error < bound_error  /* mapping is OK so far */
      then {
           VM' = VM - v          /* VM' is the new node set for the model */
           VD' = VD - w          /* VD' is the new node set for the image */
           if isempty(VM')       /* check if we have a full mapping */
              {
              best_map = h'      /* update the best mapping so far */
              bound_error = h'_error /* update the bound, too */
              }
           else treesearch(VM',VD',EM,ED,h',h'_error) /* go down the tree */
           }

      /* If you get here, h'_error >= bound_error, so this h' is not pursued */
      /* and it continues in the outer loop, trying another match w for v */
      }
   }