(* get sort from vNS.ml *)

exception Repeated_Vertex;;
exception Messed_index;;
let pe vl = match (let rec mpa l th = (match l with
       [] -> ([], [])
     | (a, b)::c -> (if th >= b then raise Repeated_Vertex;
     (match (mpa c b) with (sl, l) -> (b::sl, (ref false, a)::l))))
     in (mpa (sort (fun x y -> match (x, y) with
   ((_, b), (_, d)) -> b < d)
  (let rec numr l n = match l with [] -> [] |
    a::b -> (n, a)::(numr b (n + 1))
  in numr vl 0)) (-1))) with (svl, spl) ->
         (let ar = Array.of_list spl in
 (let rec dp i p = (if i < 0 then p else let next = dp (i-1) in
  (match ar.(i) with (a, n) -> (if !a then (next (not p)) else (  
    (let rec lop v = (match ar.(v) with (w, x) -> (
      (if !w then raise Messed_index); w := true;
          (if v = i then () else lop x))) in (lop n));          
         next p))))
 in ((dp ((Array.length ar) - 1) false), svl)));;
(* false is even parity *)

(* test
pe [5; 3; 4; 7; 2];; (* (false, [2; 3; 4; 5; 7]) *)
pe [2; 5; 4; 7; 1];; (* (true, [1; 2; 4; 5; 7]) *)
pe [];; (* (false, []) *)
pe [4];; (* (false, [4]) *)
pe [4; 7];; (* (false, [4; 7]) *)
pe [7; 4];; (* (true, [4; 7]) *)
*)