Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source
Source file strongly_connected_components.ml
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200(**************************************************************************)(* *)(* OCaml *)(* *)(* Pierre Chambart, OCamlPro *)(* Mark Shinwell and Leo White, Jane Street Europe *)(* *)(* Copyright 2013--2016 OCamlPro SAS *)(* Copyright 2014--2016 Jane Street Group LLC *)(* *)(* All rights reserved. This file is distributed under the terms of *)(* the GNU Lesser General Public License version 2.1, with the *)(* special exception on linking described in the file LICENSE. *)(* *)(**************************************************************************)open!StdlibmoduleIntSet=Set.Make(structtypet=intletcompare=compareend)moduleKosaraju:sigtypecomponent_graph={sorted_connected_components:intlistarray;component_edges:intlistarray}valcomponent_graph:intlistarray->component_graphend=structlettransposegraph=letsize=Array.lengthgraphinlettransposed=Array.makesize[]inletaddsrcdst=transposed.(src)<-dst::transposed.(src)inArray.iteri~f:(funsrcdsts->List.iter~f:(fundst->adddstsrc)dsts)graph;transposedletdepth_first_order(graph:intlistarray):intarray=letsize=Array.lengthgraphinletmarked=Array.makesizefalseinletstack=Array.makesize~-1inletpos=ref0inletpushi=stack.(!pos)<-i;incrposinletrecauxnode=ifnotmarked.(node)then(marked.(node)<-true;List.iter~f:auxgraph.(node);pushnode)infori=0tosize-1doauxidone;stackletmarkordergraph=letsize=Array.lengthgraphinletgraph=transposegraphinletmarked=Array.makesizefalseinletid=Array.makesize~-1inletcount=ref0inletrecauxnode=ifnotmarked.(node)then(marked.(node)<-true;id.(node)<-!count;List.iter~f:auxgraph.(node))infori=size-1downto0doletnode=order.(i)inifnotmarked.(node)then(auxorder.(i);incrcount)done;id,!countletkosarajugraph=letdfo=depth_first_ordergraphinletcomponents,ncomponents=markdfographinncomponents,componentstypecomponent_graph={sorted_connected_components:intlistarray;component_edges:intlistarray}letcomponent_graphgraph=letncomponents,components=kosarajugraphinletid_scc=Array.makencomponents[]inletcomponent_graph=Array.makencomponentsIntSet.emptyinletadd_component_depnodeset=letnode_deps=graph.(node)inList.fold_left~f:(funsetdep->IntSet.addcomponents.(dep)set)~init:setnode_depsinArray.iteri~f:(funnodecomponent->id_scc.(component)<-node::id_scc.(component);component_graph.(component)<-add_component_depnodecomponent_graph.(component))components;{sorted_connected_components=id_scc;component_edges=Array.map~f:IntSet.elementscomponent_graph}endmoduletypeS=sigmoduleId:sigtypetmoduleMap:Map.Swithtypekey=tmoduleSet:Set.Swithtypeelt=tendtypedirected_graph=Id.Set.tId.Map.ttypecomponent=|Has_loopofId.tlist|No_loopofId.tvalconnected_components_sorted_from_roots_to_leaf:directed_graph->componentarrayvalcomponent_graph:directed_graph->(component*intlist)arrayendmoduleMake(Id:sigtypetmoduleMap:Map.Swithtypekey=tmoduleSet:Set.Swithtypeelt=tend)=structmoduleId=Idtypedirected_graph=Id.Set.tId.Map.ttypecomponent=|Has_loopofId.tlist|No_loopofId.ttypenumbering={back:intId.Map.t;forth:Id.tarray}letnumbergraph=letsize=Id.Map.cardinalgraphinletbindings=Id.Map.bindingsgraphinleta=Array.of_listbindingsinletforth=Array.map~f:fstainletback=letback=refId.Map.emptyinfori=0tosize-1doback:=Id.Map.addforth.(i)i!backdone;!backinletinteger_graph=Array.initsize~f:(funi->let_,dests=a.(i)inId.Set.fold(fundestacc->letv=tryId.Map.finddestbackwithNot_found->assertfalseinv::acc)dests[])in{back;forth},integer_graphletcomponent_graphgraph=letnumbering,integer_graph=numbergraphinlet{Kosaraju.sorted_connected_components;component_edges}=Kosaraju.component_graphinteger_graphinArray.mapi~f:(funcomponentnodes->matchnodeswith|[]->assertfalse|[node]->((ifList.memnode~set:integer_graph.(node)thenHas_loop[numbering.forth.(node)]elseNo_loopnumbering.forth.(node)),component_edges.(component))|_::_->(Has_loop(List.map~f:(funnode->numbering.forth.(node))nodes),component_edges.(component)))sorted_connected_componentsletconnected_components_sorted_from_roots_to_leafgraph=Array.map~f:fst(component_graphgraph)end