proposition: Lemma mark_neighbor_ramify: forall {A} (g1: Graph) (g2: A -> Graph) x y, (forall (g: Graph) x y, reachable g x y \/ ~ reachable g x y) -> vvalid g1 x -> step g1 x y -> Included (Intersection V (reachable g1 x) (Complement V (reachable g1 y))) (vguard g1) -> (forall a, mark y g1 (g2 a) -> Included (Intersection V (reachable g1 x) (Complement V (reachable g1 y))) (vguard (g2 a))) -> @derives Pred _ (reachable_vertices_at x g1) (reachable_vertices_at y g1 * (ALL a: A, !! mark y g1 (g2 a) --> (reachable_vertices_at y (g2 a) -* reachable_vertices_at x (g2 a)))).
proof: Proof. intros. assert (Included (reachable g1 y) (reachable g1 x)). 1: { hnf; unfold Ensembles.In; intros. apply step_reachable with y; auto. } apply vertices_at_ramif_xQ. eexists. split; [|split]. + apply Ensemble_join_Intersection_Complement; auto. + intros. destruct H5 as [_ ?]. rewrite <- H5; clear H5. apply Ensemble_join_Intersection_Complement; auto. + intros. apply GSG_PartialGraphPreserve; auto. - unfold Included, Ensembles.In; intros. rewrite Intersection_spec in H6; destruct H6 as [? _]. apply reachable_foot_valid in H6; auto. - destruct H5. rewrite H6; clear H6. unfold Included, Ensembles.In; intros. rewrite Intersection_spec in H6; destruct H6 as [? _]. apply reachable_foot_valid in H6; auto. - apply mark_partial_labeled_graph_equiv in H5. eapply si_stronger_partial_labeledgraph_simple; [| eassumption]. unfold Included, Ensembles.In; intros. rewrite Intersection_spec in H6. tauto. Qed.
imports: VST.msl.seplog VST.msl.log_normalize CertiGraph.lib.Coqlib CertiGraph.lib.Ensembles_ext CertiGraph.lib.EquivDec_ext CertiGraph.lib.List_ext CertiGraph.lib.relation_list CertiGraph.msl_ext.log_normalize CertiGraph.msl_ext.iter_sepcon CertiGraph.msl_ext.ramification_lemmas CertiGraph.graph.graph_model CertiGraph.graph.path_lemmas CertiGraph.graph.reachable_computable CertiGraph.graph.reachable_ind CertiGraph.graph.subgraph2 CertiGraph.graph.graph_gen CertiGraph.graph.dag CertiGraph.graph.weak_mark_lemmas CertiGraph.msl_application.Graph Coq.Logic.Classical