Advertisement
Guest User

Untitled

a guest
Jul 20th, 2017
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
OCaml 2.14 KB | None | 0 0
  1. let get_maximal_strongly_connected_component graph =
  2.     List.filter                        (* remove singleton with no self loops *)
  3.       (function
  4.         | [u] -> GraphInnermost.Dp_graph.mem_edge graph u u
  5.         |  _  -> true
  6.       )
  7.       (C.scc_list graph)
  8.  
  9. let copy_graph g =
  10.   let result = GraphInnermost.Dp_graph.create () in
  11.   GraphInnermost.Dp_graph.fold_edges_e
  12.   (fun e _ -> GraphInnermost.Dp_graph.add_edge_e result e)
  13.   g
  14.   (); result
  15.  
  16. let induced_subgraph  g l =
  17.   let s = List.fold_left (fun s x -> RuleSet.add x s) RuleSet.empty l in
  18.   let result_g = copy_graph g in
  19.   GraphInnermost.Dp_graph.fold_vertex (fun v () ->
  20.     if RuleSet.mem (GraphInnermost.Dp_graph.V.label v) s
  21.     then ()
  22.     else GraphInnermost.Dp_graph.remove_vertex result_g v
  23.   ) g (); result_g
  24.  
  25.  
  26. let niveau = ref 0
  27.  
  28. let string_of_niveau () =
  29.   ("\n"^(String.make (!niveau) '\t'))
  30.  
  31. let compute graph str =
  32.   let rec compute_aux graph str =
  33.     incr niveau;
  34.     let vertex_disj_list  = GraphInnermost.Dp_graph.fold_vertex
  35.       (fun v strlist ->
  36.         let label =  GraphInnermost.Dp_graph.V.label v in
  37.  
  38.         let subgraph = copy_graph graph in
  39.         GraphInnermost.Dp_graph.remove_vertex subgraph v;
  40.         let l =
  41.           (compute_One_2 subgraph label str) ::
  42.             (List.map
  43.               (fun a ->
  44.                 let a = List.map GraphInnermost.Dp_graph.V.label a in
  45.                   compute_aux (induced_subgraph subgraph a) str
  46.               )
  47.               (get_maximal_strongly_connected_component subgraph)
  48.             )
  49.         in
  50.         Printf.printf "(noeud : '%s', cc : %d)\n" (Debug.pprint_rule label) (List.length l);
  51.         ("("^(Util.string_of_strlist l " and\n ")^")")
  52.         ::strlist
  53.       )
  54.       graph
  55.       []
  56.     in
  57.     decr niveau;
  58.     print_string "\n" ;
  59.     "("^(Util.string_of_strlist  vertex_disj_list " or\n\n ")^")"
  60.   in
  61.   Util.string_of_strlist
  62.     (List.map
  63.       (fun a ->
  64.                 let a = List.map GraphInnermost.Dp_graph.V.label a in
  65.                 compute_aux (induced_subgraph graph a) str
  66.       )
  67.       (get_maximal_strongly_connected_component graph)
  68.     )
  69.     " and\n\n\n"
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement