# 1 "bench.mll" open Format let g = ref [] # 8 "bench.ml" let __ocaml_lex_tables = { Lexing.lex_base = "\000\000\253\255\254\255\000\000\010\000\000\000\001\000\001\000\ \020\000\044\000\255\255"; Lexing.lex_backtrk = "\255\255\255\255\255\255\001\000\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255"; Lexing.lex_default = "\002\000\000\000\000\000\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\000\000"; Lexing.lex_trans = "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\005\000\007\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \005\000\007\000\003\000\008\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\005\000\006\000\007\000\000\000\ \004\000\004\000\004\000\004\000\004\000\004\000\004\000\004\000\ \004\000\004\000\004\000\004\000\004\000\004\000\004\000\004\000\ \004\000\004\000\004\000\004\000\009\000\009\000\009\000\009\000\ \009\000\009\000\009\000\009\000\009\000\009\000\010\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\009\000\009\000\009\000\009\000\ \009\000\009\000\009\000\009\000\009\000\009\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \001\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000"; Lexing.lex_check = "\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\005\000\007\000\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \005\000\007\000\000\000\007\000\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\004\000\005\000\006\000\255\255\ \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\ \003\000\003\000\004\000\004\000\004\000\004\000\004\000\004\000\ \004\000\004\000\004\000\004\000\008\000\008\000\008\000\008\000\ \008\000\008\000\008\000\008\000\008\000\008\000\009\000\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\009\000\009\000\009\000\009\000\ \009\000\009\000\009\000\009\000\009\000\009\000\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \000\000\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255"; Lexing.lex_base_code = "\000\000\000\000\000\000\000\000\010\000\000\000\000\000\000\000\ \000\000\000\000\007\000"; Lexing.lex_backtrk_code = "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000"; Lexing.lex_default_code = "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000"; Lexing.lex_trans_code = "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\004\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \001\000\001\000\001\000\001\000\001\000\001\000\001\000\001\000\ \001\000\001\000\001\000\001\000\001\000\001\000\001\000\001\000\ \001\000\001\000\001\000\001\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ \000\000\000\000\000\000"; Lexing.lex_check_code = "\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\007\000\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \003\000\003\000\003\000\003\000\003\000\003\000\003\000\003\000\ \003\000\003\000\004\000\004\000\004\000\004\000\004\000\004\000\ \004\000\004\000\004\000\004\000\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\ \255\255\255\255\255\255"; Lexing.lex_code = "\255\002\255\255\003\255\255\001\003\000\002\255"; } let rec scan lexbuf = lexbuf.Lexing.lex_mem <- Array.create 4 (-1) ; __ocaml_lex_scan_rec lexbuf 0 and __ocaml_lex_scan_rec lexbuf __ocaml_lex_state = match Lexing.new_engine __ocaml_lex_tables __ocaml_lex_state lexbuf with | 0 -> let # 11 "bench.mll" x # 188 "bench.ml" = Lexing.sub_lexeme lexbuf (lexbuf.Lexing.lex_start_pos + 1) lexbuf.Lexing.lex_mem.(0) and # 11 "bench.mll" y # 193 "bench.ml" = Lexing.sub_lexeme lexbuf lexbuf.Lexing.lex_mem.(1) (lexbuf.Lexing.lex_curr_pos + -1) in # 12 "bench.mll" ( g := (int_of_string x, int_of_string y) :: !g; scan lexbuf ) # 197 "bench.ml" | 1 -> # 14 "bench.mll" ( scan lexbuf ) # 202 "bench.ml" | 2 -> # 16 "bench.mll" ( () ) # 207 "bench.ml" | __ocaml_lex_state -> lexbuf.Lexing.refill_buff lexbuf; __ocaml_lex_scan_rec lexbuf __ocaml_lex_state ;; # 18 "bench.mll" module Make (S : Set.S with type elt = int) (M : Map.S with type key = int) = struct let add1 x y g = let sx = try M.find x g with Not_found -> S.empty in M.add x (S.add y sx) g let add x y g = add1 x y (add1 y x g) let parse f = g := []; let c = open_in f in let lb = Lexing.from_channel c in scan lb; close_in c; List.fold_left (fun g (x,y) -> add x y g) M.empty !g let show_file f = ignore (Sys.command (sprintf "dot -Tps %s > tmp.ps && gv tmp.ps" f)) let print_colors cm = M.iter (fun i c -> printf "%d -> %d@." i c) cm let graphviz_colors = [| "blue1"; "brown"; "burlywood"; "cadetblue"; "chartreuse"; "chocolate"; "coral"; "cornflowerblue"; "cornsilk4"; "cyan3"; "darkgoldenrod3"; "darkolivegreen1"; "darkorange1"; "darkorchid1"; "darkseagreen"; "darkslateblue"; |] let color i = if i < 0 then "white" else let n = Array.length graphviz_colors in if i < n then graphviz_colors.(i) else sprintf "gray%d" (i - n) let show_colors g cm = let c = open_out "tmp.dot" in let fmt = formatter_of_out_channel c in fprintf fmt "graph{graph [size=\"7,11!\"] node [style=filled];@\n"; M.iter (fun i _ -> let ci = try M.find i cm with Not_found -> -2 in if ci >= 0 then fprintf fmt "\"%d\" [color=\"%s\"];" i (color ci) else if ci = -1 then fprintf fmt "\"%d\" [style=dashed];" i else fprintf fmt "\"%d\" [style=solid];" i ) g; M.iter (fun i si -> S.iter (fun j -> if j < i then fprintf fmt "\"%d\" -- \"%d\"@\n" i j) si) g; fprintf fmt "}@."; close_out c; let cmd = "dot -Tps tmp.dot > tmp.ps && gv --media=bbox tmp.ps" in ignore (Sys.command cmd) let show_graph g = show_colors g M.empty let check1 g c = let nb = ref 0 in let nb_spill = ref 0 in M.iter (fun i si -> incr nb; let ci = M.find i c in if ci = -1 then incr nb_spill else if S.exists (fun j -> let cj = M.find j c in cj <> -1 && ci = cj) si then raise Exit) g; let r = float !nb_spill /. float !nb in printf "coloração ok / %d spilled para %d / relação = %.2f" !nb_spill !nb r; r let bench1 k color = let n = ref 0 in let sum = ref 0. in printf "coloração com k = %d@." k; let test f = let f = Filename.concat "tests" f in if Filename.check_suffix f ".dot" then begin printf " %s: " f; let g = parse f in let cm = color k g in let r = check1 g cm in printf "@."; sum := !sum +. r; incr n end in try Array.iter test (Sys.readdir "tests"); printf "média = %.2f@." (!sum /. float !n) with Exit -> printf "má coloração !@." let show1 k color f = let g = parse f in let cm = color k g in show_colors g cm;; let check2 g c = let nb = ref 0 in let colors = ref S.empty in M.iter (fun i si -> incr nb; let ci = M.find i c in colors := S.add ci !colors; if S.exists (fun j -> let cj = M.find j c in ci = cj) si then raise Exit) g; let nb_colors = S.cardinal !colors in let r = float nb_colors /. float !nb in printf "coloração ok / %d cores para %d vértices / relação = %.2f" nb_colors !nb r; r let bench2 color = let n = ref 0 in let sum = ref 0. in printf "coloração com uma infinidade de cores@."; let test f = let f = Filename.concat "tests" f in if Filename.check_suffix f ".dot" then begin printf " %s: " f; let g = parse f in let cm = color g in let r = check2 g cm in printf "@."; sum := !sum +. r; incr n end in try Array.iter test (Sys.readdir "tests"); printf "média = %.2f@." (!sum /. float !n) with Exit -> printf "má coloração !@." let show2 spill f = let g = parse f in let cm = spill g in show_colors g cm;; end # 384 "bench.ml"