Here is a better version:
def fundamental_cycle(G, T, e):
"""
Finds the unique cycle associated to the
spanning tree T of G and the edge e of G not in T.
INPUT:
G - a connected graph
T - a spanning tree
e - an edge of G not in T
OUTPUT:
the unique circuit in the graph T+e
EXAMPLES:
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: fundamental_cycle(G, TG, e)
[(3, 12, None), (2, 3, None), (1, 2, None),
(0, 1, None), (0, 13, None), (12, 13, None)]
"""
mst = G.min_spanning_tree()
u = e[0]
v = e[1]
P = T.shortest_path(u,v)
Pu = P+[u]
cycle = []
for i in range(len(P)):
E1 = G.edges_incident(Pu[i])
E2 = G.edges_incident(Pu[i+1])
cycle = cycle+[e for e in E1 if e in E2]
return cycle
On Sun, Feb 28, 2010 at 7:44 AM, David Joyner <wdjoy...@gmail.com> wrote:
> I'll answer my own question:-)
>
> There is an easily written function which does this:
>
>
...
>
>
> On Sun, Feb 28, 2010 at 5:42 AM, David Joyner <wdjoy...@gmail.com> wrote:
>> Hi:
>>
>> I'm trying to compute fundamental circuits of a
>> graph in Sage and am getting stuck. Is this implemented?
>>
...
>>
>> - David Joyner
>>
>
--
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
