proposition: Lemma vcopy1_edge_copy_list_copy_extended_copy: forall root es es_done e0 es_later (g1 g2 g3 g2' g3' g4 g4'': Graph), vvalid g1 root -> WeakMarkGraph.unmarked g1 root -> es = es_done ++ e0 :: es_later -> (forall e, In e es <-> out_edges g1 root e) -> NoDup es -> vcopy1 root g1 g2 g2' -> edge_copy_list g1 es_done (g2, g2') (g3, g3') -> copy (dst g1 e0) g3 g4 g4'' -> disjointed_guard (vvalid g4'') (vvalid g3') (evalid g4'') (evalid g3') -> exists g4': Graph, extended_copy (dst g1 e0) (g3, g3') (g4, g4') /\ guarded_labeled_graph_equiv (vvalid g4'') (evalid g4'') g4'' g4' /\ guarded_labeled_graph_equiv (vvalid g3') (evalid g3') g3' g4'.
proof: Proof. intros. unfold reachable_vertices_at. pose proof vcopy1_edge_copy_list_spec root es es_done _ g1 g2 g3 g2' g3' H H0 H1 H2 H3 H4 H5. destruct H8. pose proof LocalGraphCopy.copy_extend_copy g1 g3 g4 g3' g4'' root es es_done e0 es_later (WeakMarkGraph.marked g1) H H0 H2 H3 H1. spec H10; [intro v; destruct (node_pred_dec (WeakMarkGraph.marked g1) v); auto |]. cbv zeta in H10. pose proof WeakMarkGraph.triple_mark1_componded_mark_list root (map (dst g1) es_done) (map (dst g1) (e0 :: es_later)) (map (dst g1) es) g1 g3 H H0. spec H11; [apply out_edges_step_list; auto |]. spec H11; [rewrite <- map_app; f_equal; auto |]. spec H11; [split_relation_list (g1 :: g2 :: g2 :: nil) |]. 1: apply WeakMarkGraph.eq_do_nothing; auto. 1: destruct H4 as [? [? ?]]; auto. 1: apply WeakMarkGraph.eq_do_nothing; auto. 1: auto. cbv iota zeta in H11. destruct H11 as [_ ?]. rewrite <- H11 in H10. spec H10; [destruct H6 as [? [? ?]]; auto |]. spec H10; [auto |]. spec H10; [intros v; rewrite <- (app_same_set H11); destruct (node_pred_dec (WeakMarkGraph.marked g3) v); auto |]. destruct H10 as [g4' [? [? ?]]]. rewrite <- H11 in H10. exists g4'. split; [| split]; auto. destruct H6 as [? [? ?]]; split; [| split]; auto. 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.lib.Morphisms_ext 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.graph_gen CertiGraph.graph.graph_relation CertiGraph.graph.subgraph2 CertiGraph.graph.dag CertiGraph.graph.weak_mark_lemmas CertiGraph.graph.graph_morphism CertiGraph.graph.local_graph_copy CertiGraph.msl_application.Graph Coq.Logic.Classical