Hello, David ! As Nathann mentionned, I've already submitted a patch which allows one to enumerate paths and cycles in directed graphs with a lot of possible parameters (length, starting and ending vertices, etc.). Since it has received positive review, I'll submit another one for the next week, so that it is available in Sage 4.3.4 or, in the worse case, the next release. I'll keep you posted about that. Thanks for your interest in the matter ! Alex
On 28 fév, 15:35, David Joyner <wdjoy...@gmail.com> wrote: > On Sun, Feb 28, 2010 at 8:57 AM, Nathann Cohen <nathann.co...@gmail.com> > wrote: > > Hello !!!! > > > By the fundamental circuits, do you mean a base of the Cycle space ? > > If so, I have to admit I do not know how to do it... > > I just posted some code to compute the cycle space > tohttp://sage.math.washington.edu/home/wdj/research/coding-theory/cycle... > > > > > > > If you want to compute a shortest cycle in a graph, though, I do not > > think the girth function can do it at the moment, but I agree it would > > be useful to have for such functions an optional argument > > "certifitate", giving along with a boolean answer a proof which in > > this example would be a cycle. > > > If you only want to find a cycle in a graph when it is unique (a tree > > + an edge), you can also make use of the "cores" function : > > > sage: G = graphs.HeawoodGraph() > > sage: mst = G.min_spanning_tree() > > sage: TG = G.subgraph(edges=mst) > > sage: e = G.edges()[-1] > > sage: e in TG > > False > > > sage: TG.add_edge(e) > > sage: cycle = TG.subgraph([v for v,k in > > TG.cores(with_labels=True).items() if k>=2]) > > sage: cycle.is_isomorphic(graphs.CycleGraph(cycle.order())) > > True > > This is very clever. Thank you! > > > > > I do not know how both methods compare algorithmically, though :-) > > > By the way, you may be interested in a patch from Alexandre Blondin > > Massé that just got positively reviewed : > > >http://trac.sagemath.org/sage_trac/ticket/8273 > > > (he mentionned he may eventually write the same functions for undirected > > graphs) > > I hope he does! > > > > > Nathann > > > -- > > To post to this group, send email to sage-support@googlegroups.com > > To unsubscribe from this group, send email to > > sage-support+unsubscr...@googlegroups.com > > For more options, visit this group > > athttp://groups.google.com/group/sage-support > > URL:http://www.sagemath.org -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
