Get Handle Algorithm
20/3/2014
CE-653 - PTnet Theory and some Algorithms
21
}N is strongly-connected FC-Net with S, S’ ≤ P U T
}S ∩ S’ = Ø, p in S, t in S’, t is in •p, Outputs handle H = (x0, x1, …, xn-2, t, p) or 0
}Num(v) values:
}num(v) == -1 è v in S, start point of handle, num(v) ==0  è v in S’, not visited before
}num(v) > 0 è v has been visited before and either (a) no handle was found or
(b) has been reached again. In both cases v cannot belong to the handle
Algorithm Get_Handle(S, S’, F, t, p)
Algorithm handle-DFS(v)
// S ∩ S’ = ø, p in S, t in S’ and t is in •p //
i = 1; Stack = empty;
forall x in S’ num(x) = 0;
forall x in S num(x) = -1;
push(Stack, p);
if (handle-DFS(t) == 0)
{
  return NULL;
  printf(“No handle exists\n”);
}
else
{
  return Stack; // Stack contains Handle //
}
num(v) = i; i = i + 1;
push(Stack, v);
forall (w in •v)
  if (num(w) == -1) // start node of handle //
  {
     push(Stack, w);
     return 1;
  }
forall (w in •v)
  if (num(w) == 0) // new non-start node //
     if (dfs(w) == 1) return 1;
pop(Stack, v);
return 0;