proposition: Lemma frr_rgc_aux: forall from to roots1 g1 roots2 g2, from <> to -> graph_has_gen g1 to -> copy_compatible g1 -> roots_graph_compatible roots1 g1 -> forward_roots_relation from to roots1 g1 roots2 g2 -> forall done, roots_graph_compatible done g1 -> roots_graph_compatible done g2 /\ roots_graph_compatible roots2 g2.
proof: Proof. induction 5; intros; auto. pose proof fr_roots_graph_compatible 0 from to (inl 0) g1 g2 (r:: done ++ roots1) H0 ltac:(simpl; list_solve) H1 H3 H. simpl in H6. rewrite upd_Znth0, Znth_0_cons in H6. spec H6. change (?A :: ?B) with ([A]++B) in H2|-*. rewrite !roots_graph_compatible_app in *. destruct H2; split; auto. assert (graph_has_gen g2 to) by (erewrite <- fr_graph_has_gen; eauto). assert (copy_compatible g2) by (eapply fr_copy_compatible; try apply H3; eauto). change (?A :: ?B) with ([A]++B) in H6|-*. rewrite !roots_graph_compatible_app in *. destruct H6 as [? [? ?]]. specialize (IHforward_roots_relation H7 H8 H10 (done+:: upd_root from to g1 r)). rewrite !roots_graph_compatible_app in *. destruct IHforward_roots_relation; auto. destruct H11. split; auto. Qed.
imports: Coq.ZArith.ZArith Coq.Program.Basics compcert.lib.Integers compcert.common.Values VST.veric.base VST.veric.Clight_lemmas VST.veric.val_lemmas VST.veric.shares VST.msl.seplog VST.msl.shares VST.zlist.sublist VST.floyd.coqlib3 VST.floyd.functional_base VST.floyd.data_at_rec_lemmas CertiGraph.lib.Coqlib CertiGraph.lib.EquivDec_ext CertiGraph.lib.List_ext CertiGraph.graph.graph_model CertiGraph.graph.graph_gen CertiGraph.graph.path_lemmas CertiGraph.graph.subgraph2 CertiGraph.graph.graph_relation CertiGraph.graph.graph_isomorphism CertiGraph.graph.reachable_ind CertiGraph.CertiGC.GCGraph