MrSlippery

Hamiltonian Cycle Finder with KLEE

Mar 21st, 2016
354
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <klee/klee.h>
  2.  
  3. typedef unsigned char byte;
  4.  
  5. #define N 5
  6.  
  7. byte a[N * N]=
  8. {
  9. /*   A B C D E*/
  10. /*A*/1,1,1,1,1,
  11. /*B*/1,1,0,0,1,
  12. /*C*/1,0,1,1,1,
  13. /*D*/1,0,1,1,0,
  14. /*E*/1,1,1,0,1
  15. };
  16.  
  17. int ham_cycle(byte *path)
  18. {
  19.         byte i;
  20.         byte visited[N + 1] = { 0 };
  21.  
  22.         if (path[N] != path[0]) {
  23.                 return 0;
  24.         }
  25.  
  26.         for (i = 0; i < N; i++) {
  27.                 if (path[i] >= N) {
  28.                         return 0;
  29.                 }
  30.                 if (visited[path[i]]) {
  31.                         return 0;
  32.                 }
  33.                 visited[path[i]]++;
  34.         }
  35.  
  36.         for (i = 0; i < N; i++) {
  37.                 byte x = path[i];
  38.                 byte y = path[i + 1];
  39.                 if (!a[x + y * N]) {
  40.                         return 0;
  41.                 }
  42.         }
  43.         return 1;
  44. }
  45.  
  46. int main(int argc, char *argv[])
  47. {
  48.         byte i;
  49.         byte cycle[N + 1];
  50.  
  51.         klee_make_symbolic(&cycle[0], sizeof(byte) * (N + 1), "cycle");
  52.         klee_assert(!ham_cycle(cycle));
  53.         return 0;
  54. }
Advertisement