proposition: Lemma dag_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_dag_vertices_at x g2: pred) |-- reachable_dag_vertices_at r g2 * (ALL g':Graph, !! (mark r g2 g') --> (reachable_dag_vertices_at r g' -* reachable_dag_vertices_at x g')).
proof: Proof. intros. pose proof @graph_ramify_right _ _ g g1 g2 x l r H H0 H1 H2. unfold reachable_dag_vertices_at. normalize. destruct H1 as [? _]. destruct H2 as [_ ?]. rewrite <- H2, <- H1 in H4. assert (localDag g2 r). 1: { rewrite <- H2, <- H1. eapply local_dag_step; eauto. eapply gamma_step; eauto. } rewrite prop_true_andp by auto. match goal with | |- _ |-- _ * ?A => replace A with (ALL g' : Graph , (!!mark r g2 g':pred) --> (vertices_at (reachable g' r) g' -* vertices_at (reachable g' x) g')) end. 2: { apply allp_congr; intros g3. apply imp_prop_ext; [reflexivity |]. intros [_ ?]. rewrite prop_true_andp by (rewrite <- H6; auto). rewrite prop_true_andp by (rewrite <- H6, <- H2, <- H1; auto). reflexivity. } 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 CertiGraph.msl_application.GraphBin_Mark Coq.Logic.Classical