On Fri, Jun 19, 2015 at 09:31:21PM +0000, Simon King wrote: > Hi! > > Let D be a digraph, potentially with multiple edges and loops. Let v be > a vertex. > > How should one test whether v is contained in a cycle (including loops)? > > Is it correct that v is in a cycle or loop if and only if > (len(D.strongly_connected_component_containing_vertex(v))>1) or (v in > D.neighbors_out(v)) > ? > Is there a better way to test it?
Some variants; same theoretical worst case complexity; not necessarily better in practice: - duplicate the vertex, and search for a path from the first copy to the second one. - search for a path from one of the out neighbors of v to v Cheers, Nicolas -- Nicolas M. ThiƩry "Isil" <nthi...@users.sf.net> http://Nicolas.Thiery.name/ -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel. For more options, visit https://groups.google.com/d/optout.