proposition: Lemma graph_ramify_right: forall (g g1 g2: Graph) x l r, vvalid g x -> vgamma g x = (false, l, r) -> mark1 x g g1 -> mark l g1 g2 -> (reachable_vertices_at x g2: pred) |-- reachable_vertices_at r g2 * (ALL g': Graph, !! (mark r g2 g') --> (reachable_vertices_at r g' -* reachable_vertices_at x g')).
proof: Proof. intros. apply (mark_list_mark_ramify g g2 _ _ (l :: nil) _ nil); auto. + intros; apply classic. + simpl. eapply gamma_step_list; eauto. + split_relation_list ((lg_gg g1) :: nil); auto. unfold mark_list. simpl map. split_relation_list (@nil (LabeledGraph _ _ bool unit unit)); auto. + unfold Included, Ensembles.In; intros. apply vvalid_vguard. rewrite Intersection_spec in H3; destruct H3. apply reachable_foot_valid in H3; auto. + unfold Included, Ensembles.In; intros. apply vvalid_vguard. rewrite Intersection_spec in H4; destruct H4. apply reachable_foot_valid in H4. destruct H3 as [_ [? _]]. rewrite <- H3; auto. Qed.
imports: CertiGraph.lib.Ensembles_ext Coq.Lists.List VST.msl.seplog VST.msl.log_normalize VST.msl.Coqlib2 CertiGraph.lib.Coqlib CertiGraph.lib.EquivDec_ext CertiGraph.lib.relation_list CertiGraph.msl_ext.log_normalize CertiGraph.msl_ext.iter_sepcon 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 CertiGraph.msl_application.Graph_Mark CertiGraph.msl_application.GraphBin Coq.Logic.Classical