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.
