proposition: Lemma reachable_by_decidable (G: PreGraph V E) {is_null: DecidablePred V} {MA: MathGraph G is_null} {LF: LocalFiniteGraph G}: forall (p : DecidablePred V) x , {vvalid G x} + {~ vvalid G x} -> EnumCovered V (reachable G x) -> ReachDecidable G x p.
proof: Proof. intros. destruct H as [H | H]. 2: { right. intro; apply reachable_by_is_reachable in H0. apply reachable_head_valid in H0; tauto. } remember (predicate_subgraph G p) as pdg. destruct (node_pred_dec p x). + assert (vvalid pdg x) by (subst; split; auto). assert (EnumCovered V (reachable pdg x)). { subst. apply EnumCovered_strengthen with (reachable G x); auto. apply predicate_subgraph_reachable_included. } subst. intro y. destruct (@reachable_decidable_prime _ _ (predicate_sub_mathgraph _ p _) (predicate_sub_localfinitegraph _ p _) x H0 X0 y). - rewrite <- reachable_by_eq_subgraph_reachable in r. left; auto. - rewrite <- reachable_by_eq_subgraph_reachable in n. right; auto. + right. intro. apply reachable_by_head_prop in H0. tauto. Qed.
imports: Coq.Sets.Finite_sets Coq.Arith.Arith Coq.Logic.ProofIrrelevance Coq.Logic.FunctionalExtensionality Coq.Sorting.Permutation Coq.micromega.Lia CertiGraph.lib.Coqlib CertiGraph.lib.List_ext CertiGraph.lib.EquivDec_ext CertiGraph.lib.EnumEnsembles Coq.Lists.List VST.msl.Coqlib2 CertiGraph.graph.graph_model CertiGraph.graph.path_lemmas CertiGraph.graph.reachable_ind CertiGraph.graph.subgraph2 CertiGraph.graph.graph_gen CertiGraph.graph.MathGraph CertiGraph.graph.FiniteGraph