add simple cycle enumeration by k shortest simple path algorithm #40145
Conversation
|
I think that the algorithm is not what we want: If I understand well, with the current proposal, you start an iterator from each edge of the graph, so some cycles may be reported more than once. The correct algorithm should be like:
We now get a collection of iterators that you can put in a priority queue to enumerate the cycles in the right order. |
src/sage/graphs/digraph.py
Outdated
| if not rooted: | ||
| for v in starting_vertices: | ||
| if v < edge[0]: | ||
| h.delete_vertex(v) | ||
| if v == edge[1]: | ||
| return |
There was a problem hiding this comment.
Thanks for your comments!
I understand your algorithm intends not to output the same cycle more than once. My implemented algorithm also try to do that by deleting vertices (if rooted=False). If rooted=True, it outputs the same cycle with a different start vertex but I think it is a correct behavior.
How do you think about it?
There was a problem hiding this comment.
The goal of my algorithm is not only to output a cycle only once. It is also to work on smaller digraphs. Indeed, once en iterator has been initialized for edge e, that edge is removed from the digraph, the digraph is decomposed into strongly connected components, and we proceed in each SCC.
This algorithm shall initialize fewer iterators (only 1 if the input digraph is a circuit for instance), and each iterator will operate in smaller digraphs.
Consider the following:
def simple_cycle_iter(hh, e):
return hh._all_simple_cycles_iterator_edge(e,
max_length=max_length,
remove_acyclic_edges=False,
weight_function=weight_function,
by_weight=by_weight,
check_weight=check_weight,
report_weight=True)
SCCC = h.strongly_connected_components_subgraphs()
iterators= {}
while SCCS:
hh = SCCS.pop()
if not hh.size():
continue
e = next(hh.edge_iterator())
iterators[e] = simple_cycle_iter(hh, e)
hh.delete_edge(e)
SCCS.extend(hh.strongly_connected_components_subgraphs())There was a problem hiding this comment.
I understand it. I will modify the current algorithm to new one.
|
I think it works well for a graph with a loop, but for a graph with a multiedge, g = DiGraph(multiedges=True)
g.add_edges([('a', 'b'), ('b', 'c'), ('b', 'c')])
it = g.shortest_simple_paths(source='a', target='c', algorithm='Feng')
next(it)
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-8-bc1ab118995a> in ?()
----> 1 next(it)
sage/graphs/path_enumeration.pyx in ?()
--> 556 self = self.to_simple(to_undirected=False, keep_label='min', immutable=False)
~/Documents/gsoc2025/sage/sage/src/sage/graphs/generic_graph.py in ?(self, to_undirected, keep_label, immutable)
19790 g = Graph(self, immutable=False)
19791 else:
19792 g = self.copy(immutable=False)
19793 g.allow_loops(False)
> 19794 g.allow_multiple_edges(False, keep_label=keep_label)
19795 if immutable is None:
19796 immutable = self.is_immutable()
19797 if immutable:
~/Documents/gsoc2025/sage/sage/src/sage/graphs/generic_graph.py in ?(self, new, check, keep_label)
3942 else:
3943 # This edge has already been seen: we have to remove
3944 # something from the graph.
3945 oldl = seen[u, v]
-> 3946 if (keep_min and l < oldl) or (keep_max and l > oldl):
3947 # Keep the new edge, delete the old one
3948 self.delete_edge(u, v, oldl)
3949 seen[u, v] = l
TypeError: '<' not supported between instances of 'NoneType' and 'NoneType'Is it expected behavior? If not, changing sage/src/sage/graphs/path_enumeration.pyx Line 1100 in d617df4 will fix this issue. |
|
Documentation preview for this PR (built with commit acb7e42; changes) is ready! 🎉 |
|
changing to |
|
Thank your for review. I fixed typo in documentation. |
Add another algorithm of enumearting simple cycles in digraph, which is based on k shortest simple path algorithm.
For each edge e=uv, delete e from the original graph and enumerate vu simple path in increasing length order by k shortest simple path algorithm to obtain simple cycles that contain e in increasing length order.
Using iterators for each edge e and priority queue makes it possible to enumerate simple cycles in increasing length order.
📝 Checklist
⌛ Dependencies
#40114