#8273: Enumeration of cycles in directed graphs
----------------------------+-----------------------------------------------
Reporter: abmasse | Owner: rlm
Type: defect | Status: new
Priority: major | Milestone: sage-4.3.3
Component: graph theory | Keywords: cycle, enumeration
Author: abmasse | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
In many graph-theoretical problems, it is important to understand the
cycles structure of undirected graphs as well as directed ones. Therefore,
I suggest three functions that allow one to iterate over all cycles of a
directed graph (I might be interested in writing some functions for
undirected graphs, but I prefer to have these ones validated before I do
so).[[BR]]
[[BR]]
The first and main function is called `cycles_iterator(...)` and allows
one to iterate over all cycles satisfying conditions according to the
following parameters:
- `simple` (a boolean). When set to True, only the starting and ending
vertex may be repeated in the cycle[[BR]]
- `distinct` (also a boolean). When set to True, then all equivalent
cycles are merged into one cycle. Equivalent cycles are cycles differing
only from their starting vertex, such as `[0,1,2,0]` and
`[1,2,0,1]`.[[BR]]
- `initial_vertices` (an iterable). Specify the only allowed starting
vertices of the cycles.[[BR]]
- `max_length` (an integer). The maximum length of cycles. Useful
especially when a graph contains a very large number of cycles and one
wants to compute smaller ones.
The two other function are merely calling `cycles_iterator(...)` with some
of the above parameters fixed.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8273>
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.
