(* get sort from vNS.ml *)

exception Repeated_Vertex;;
exception Logic_error;;
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 Logic_error; 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]) *)
*)