Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- let get_maximal_strongly_connected_component graph =
- List.filter (* remove singleton with no self loops *)
- (function
- | [u] -> GraphInnermost.Dp_graph.mem_edge graph u u
- | _ -> true
- )
- (C.scc_list graph)
- let copy_graph g =
- let result = GraphInnermost.Dp_graph.create () in
- GraphInnermost.Dp_graph.fold_edges_e
- (fun e _ -> GraphInnermost.Dp_graph.add_edge_e result e)
- g
- (); result
- let induced_subgraph g l =
- let s = List.fold_left (fun s x -> RuleSet.add x s) RuleSet.empty l in
- let result_g = copy_graph g in
- GraphInnermost.Dp_graph.fold_vertex (fun v () ->
- if RuleSet.mem (GraphInnermost.Dp_graph.V.label v) s
- then ()
- else GraphInnermost.Dp_graph.remove_vertex result_g v
- ) g (); result_g
- let niveau = ref 0
- let string_of_niveau () =
- ("\n"^(String.make (!niveau) '\t'))
- let compute graph str =
- let rec compute_aux graph str =
- incr niveau;
- let vertex_disj_list = GraphInnermost.Dp_graph.fold_vertex
- (fun v strlist ->
- let label = GraphInnermost.Dp_graph.V.label v in
- let subgraph = copy_graph graph in
- GraphInnermost.Dp_graph.remove_vertex subgraph v;
- let l =
- (compute_One_2 subgraph label str) ::
- (List.map
- (fun a ->
- let a = List.map GraphInnermost.Dp_graph.V.label a in
- compute_aux (induced_subgraph subgraph a) str
- )
- (get_maximal_strongly_connected_component subgraph)
- )
- in
- Printf.printf "(noeud : '%s', cc : %d)\n" (Debug.pprint_rule label) (List.length l);
- ("("^(Util.string_of_strlist l " and\n ")^")")
- ::strlist
- )
- graph
- []
- in
- decr niveau;
- print_string "\n" ;
- "("^(Util.string_of_strlist vertex_disj_list " or\n\n ")^")"
- in
- Util.string_of_strlist
- (List.map
- (fun a ->
- let a = List.map GraphInnermost.Dp_graph.V.label a in
- compute_aux (induced_subgraph graph a) str
- )
- (get_maximal_strongly_connected_component graph)
- )
- " and\n\n\n"
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement