fact: Definition kruskal_spec := DECLARE _kruskal WITH gv: globals, sh: share, g: (@EdgeListGG size), orig_gptr : pointer_val, orig_eptr : pointer_val, glist: list (LE*EType) PRE [tptr t_wedgearray_graph] PROP (writable_share sh; readable_share sh; numE g <= MAX_EDGES; 0 < size <= Int.max_signed / 8; Permutation (graph_to_wedgelist g) glist ) PARAMS ((pointer_val_val orig_gptr)) GLOBALS (gv) SEP (mem_mgr gv; data_at sh tint (Vint (Int.repr MAX_EDGES)) (gv _MAX_EDGES); data_at sh (t_wedgearray_graph) (Vint (Int.repr (size)), (Vint (Int.repr (numE g)), pointer_val_val orig_eptr)) (pointer_val_val orig_gptr); data_at sh (tarray t_struct_edge MAX_EDGES) (map wedge_to_cdata glist ++ (Vundef_cwedges (MAX_EDGES - numE g))) (pointer_val_val orig_eptr) ) POST [tptr t_wedgearray_graph] EX msf_gptr msf_eptr: pointer_val, EX msf: (@EdgeListGG size), EX msflist: list (LE*EType), EX glist': list (LE*EType), PROP ( Permutation (graph_to_wedgelist g) glist'; (numE msf) <= MAX_EDGES; Permutation msflist (graph_to_wedgelist msf); minimum_spanning_forest msf g ) LOCAL (temp ret_temp (pointer_val_val msf_gptr)) SEP (mem_mgr gv; data_at sh tint (Vint (Int.repr MAX_EDGES)) (gv _MAX_EDGES); data_at sh (t_wedgearray_graph) (Vint (Int.repr (size)), (Vint (Int.repr (numE g)), pointer_val_val orig_eptr)) (pointer_val_val orig_gptr); data_at sh (tarray t_struct_edge MAX_EDGES) (map wedge_to_cdata glist' ++ (Vundef_cwedges (MAX_EDGES - numE g))) (pointer_val_val orig_eptr); malloc_token' sh (MAX_EDGES * sizeof t_struct_edge) (pointer_val_val msf_eptr); malloc_token' sh (sizeof t_wedgearray_graph) (pointer_val_val msf_gptr); data_at sh (t_wedgearray_graph) (Vint (Int.repr size), (Vint (Int.repr (numE msf)), pointer_val_val msf_eptr)) (pointer_val_val msf_gptr); data_at sh (tarray t_struct_edge MAX_EDGES) (map wedge_to_cdata msflist ++ (Vundef_cwedges (MAX_EDGES - numE msf))) (pointer_val_val msf_eptr) ).
imports: CertiGraph.unionfind.env_unionfind_arr CertiGraph.unionfind.uf_arr_specs VST.floyd.library RelationClasses CertiGraph.binheap.binary_heap_model CertiGraph.binheap.binary_heap_Zmodel Sorting CertiGraph.kruskal.WeightedEdgeListGraph CertiGraph.kruskal.env_kruskal_edgelist CertiGraph.kruskal.spatial_wedgearray_graph CertiGraph.graph.graph_model CertiGraph.floyd_ext.share