#8273: Enumeration of cycles in directed graphs
----------------------------+-----------------------------------------------
Reporter: abmasse | Owner: rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.3.3
Component: graph theory | Keywords: cycle, enumeration
Author: abmasse | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
Comment(by ncohen):
Hello !!!
It would be good to get (cheaply) rid of this "bug" happening when the
vertices are in no non-trivial strongly connected components... Perhaps
some other parameter meant to be used only internally, in this case too...
But this would mean a lot of them in the end :-)
I continued to read some parts of your code, and have some other remarks :
* you write :
{{{
sccs = self.strongly_connected_components()
from operator import add
vertices = reduce(add, sccs)
edges = reduce(add, [self.subgraph(scc).edges() for scc in sccs])
h = self.subgraph(vertices, edges)
}}}
Well, you seem trying to get rid of "bridges" -- edges whose removal
disconnect the graph. Obviously, there will be no cycle going through
them. Doing so, you create a lot of copies of the graph (the subgraph()
command), which could be costly... Here is another way to do it :
First, create the list of strongly connected components
{{{
sccs = self.strongly_connected_components()
}}}
Then, associate to each vertex the id of its connected component :
{{{
d = {}
for id, component in enumerate(sccs):
for v in component:
d[v] = id
}}}
Once it is done, create a copy of your first graph using the copy
command (these commands are low-level, written in Cython). Then remove the
bad edges :
{{{
h = self.copy()
h.delete_edges([ e for e in g.edge_iterator() if d[e[0]] !=
d[e[1]] ])
}}}
This way most of the work is done using dictionaries, and no heavy
structure like graphs.
* How is this :
{{{
vertices = reduce(add, sccs)
}}}
different from setting
{{{
vertices = self.vertices()
}}}
I think it comes from the same fact that you will have in sccs some
connected components equal to singletons.
* You write :
{{{
for vi in vertex_iterators.values():
try:
cycles.append(vi.next())
except(StopIteration):
pass
}}}
I do not know much about iterators, but... Well, the values of
vertex_iterators are iterators, so
{{{
for vi in vertex_iterators.values():
cycles.extend(list(vi))
}}}
should work, shouldn't it ?
* This :
{{{
while len(cycles) > 0:
}}}
Can be replaced by
{{{
while cycles:
}}}
* In this situation :
{{{
for i in range(len(cycles)):
if len(cycles[i]) < len(shortest_cycle):
shortest_cycle = cycles[i]
imin = i
}}}
You can write
{{{
for i, cycle_i in enumerate(cycles):
if len(cycle_i) < len(shortest_cycle):
shortest_cycle = cycle_i
imin = i
}}}
I have been told about this "enumerate" trick when working on Cython
files... This command is optimized in Cython, so writing Python code this
way will help if we are to Cythonize it later :-)
For example :
{{{
a = ['pie', 'cake', 'coffee']
list(enumerate(a))
[(0, 'pie'), (1, 'cake'), (2, 'coffee')]
}}}
Anyway, if you are trying to get the minimum element of such a list,
you could have also written :
{{{
i_min, cycle_min = min( enumerate(cycles), key = lambda x: len(x[1]) )
}}}
I'll give a look again at your next version of the patch... Each time I
get more used to what it does :-)
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8273#comment:4>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
