Opened 2 years ago
Closed 22 months ago
#22206 closed enhancement (fixed)
Generation of strong orientations of a graph
Reported by:  pvalicov  Owned by:  

Priority:  major  Milestone:  sage7.6 
Component:  graph theory  Keywords:  graphs, orientations 
Cc:  Merged in:  
Authors:  Petru Valicov, Kolja Knauer  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  47f0e7e (Commits)  Commit:  47f0e7e9a162a476b47db6e44f7af5fafd52a346 
Dependencies:  Stopgaps: 
Description
Change History (54)
comment:1 Changed 2 years ago by
 Branch set to u/pvalicov/generation_of_strong_orientations_of_a_graph
comment:2 Changed 2 years ago by
 Commit set to e3498e042ef040a7465c44bdf9d9646c706579fe
comment:3 Changed 2 years ago by
 Keywords graphs orientations added
 Type changed from PLEASE CHANGE to enhancement
comment:4 Changed 2 years ago by
 Component changed from PLEASE CHANGE to graph theory
comment:5 followup: ↓ 6 Changed 2 years ago by
Hello, welcome !
 always have a blankline after a line ending with
::
 every function needs to have doctests
comment:6 in reply to: ↑ 5 ; followup: ↓ 7 Changed 2 years ago by
Hello, thanks for pointing out. I submit the corrected version. For inner functions, there must be also a doctest or a simple description is enough?
Replying to chapoton:
Hello, welcome !
 always have a blankline after a line ending with
::
 every function needs to have doctests
comment:7 in reply to: ↑ 6 Changed 2 years ago by
Replying to pvalicov:
Hello, thanks for pointing out. I submit the corrected version. For inner functions, there must be also a doctest or a simple description is enough?
doctests for every function that is not inside a function, as explained here : http://doc.sagemath.org/html/en/developer/coding_basics.html
Replying to chapoton:
Hello, welcome !
 always have a blankline after a line ending with
::
 every function needs to have doctests
comment:8 Changed 2 years ago by
see the patchbot report (colored icon at top right) for the coverage: 2 functions are missing documentation
patchbot also says: do not use xrange, but range (if you want an iterator, use from six.moves import range
)
comment:9 Changed 2 years ago by
 Commit changed from e3498e042ef040a7465c44bdf9d9646c706579fe to aa8401d76c0319c63568bb98a690f004ee0e4987
Branch pushed to git repo; I updated commit sha1. New commits:
aa8401d  Doctests added, some minor corrections

comment:10 Changed 2 years ago by
 Commit changed from aa8401d76c0319c63568bb98a690f004ee0e4987 to 464df4c26470f343d7427c7429a42e603d4914f3
Branch pushed to git repo; I updated commit sha1. New commits:
464df4c  xrange replaced by range (for Python 3)

comment:11 Changed 2 years ago by
 Commit changed from 464df4c26470f343d7427c7429a42e603d4914f3 to 8ba75c01f228e4d632661d8a7c2391be7b1f5e2d
Branch pushed to git repo; I updated commit sha1. New commits:
8ba75c0  Comments corrections

comment:12 Changed 23 months ago by
 the main function still has no documentation
 when calling a reference, you must write
[CGMRV16]_
with an underscore
comment:13 Changed 23 months ago by
 Commit changed from 8ba75c01f228e4d632661d8a7c2391be7b1f5e2d to 9988011593a882e2c1394bdd914dddb13c51b275
Branch pushed to git repo; I updated commit sha1. New commits:
9988011  Corrections for documentation of functions

comment:14 Changed 23 months ago by
Dear Kolja and Petru,
a few comments on your code:
 ticket #22247 should allow you to avoid a (costly) call to
self.edge_connectivity()
Dg = DiGraph([self.vertices(), self.edges()])
could be simplyDg = DiGraph(self)
 when you do
treeEdges = [(edge[0],edge[1]) for edge in self.edges() if edge in te]
, all edges inte
are inself
. So to remove the labels, you can dotreeEdges = [(u,v) for u,v,_ in te]
 You can initialize
existingAedges
directly usingexistingAedges = [0]*len(A)
 avoid
bitChanged >>= 1; bit += 1;
and put each instruction in a separate line  use
yield Dg.copy()
. Indeed, the instructionyield Dg
will in fact return a pointer. SinceDg
is modified in your method, what you have returned will also be modified.
Best,
David.
comment:15 Changed 23 months ago by
Ticket #22254 which improves the computation of bridges might also be useful. The proposed implementation avoids a call to strong_orientation
...
comment:16 followup: ↓ 18 Changed 23 months ago by
Hi David,
Thanks for the comments. Cannot use
Dg = DiGraph(self)
because it will doubly orient all the edges of self, and we want Dg to be a simple directed graph.
For ticket #22247 can I already use the code even if it was not validated yet in sage ?
Petru
comment:17 Changed 23 months ago by
 Commit changed from 9988011593a882e2c1394bdd914dddb13c51b275 to 2698bf5a09163061b2eef9823a4669b8be92bbb7
Branch pushed to git repo; I updated commit sha1. New commits:
2698bf5  Few code improvements.

comment:18 in reply to: ↑ 16 Changed 23 months ago by
Thanks for the comments. Cannot use
Dg = DiGraph(self)
because it will doubly orient all the edges of self, and we want Dg to be a simple directed graph.
Right, I forgot that issue ;)
For ticket #22247 can I already use the code even if it was not validated yet in sage ?
I'm not a git guru, but I think you can safely rebase your ticket on top of #22247 (or #22254). Don't forget to indicate the dependency.
comment:19 Changed 23 months ago by
 Commit changed from 2698bf5a09163061b2eef9823a4669b8be92bbb7 to b8852622e28e7d6e1f2aa083dc6a8f97cf186d5f
Branch pushed to git repo; I updated commit sha1. New commits:
d25993d  trac #22247: add method is_biconnected to graph

498db89  trac #22247: connect to graph_classes

3979aea  trac #22247: add link to blocks_and_cuts_tree to seealso section

29a546f  Merge branch 'u/dcoudert/22247' of git://trac.sagemath.org/sage into t/22206/generation_of_strong_orientations_of_a_graph

b885262  Biconnectivity test added using the code from ticket #22247. Thanks !

comment:20 Changed 22 months ago by
I don't know how to ensure that the last (minor) modifications made on #22247 will be taken into account in this patch. Hope someone will be able to answer that question.
You should set this ticket to needs_review
if belive it is ready for review.
comment:21 Changed 22 months ago by
 Status changed from new to needs_review
comment:22 Changed 22 months ago by
some minor comments:
 Add a space in each method between the one line description of the method and the long description, e.g., after
Returns an iterator over all strong orientations of self.
 Ensure that comments are in 80 columns mode (sorry for that).
Dg = DiGraph([self.vertices(), self.edges()], pos=self.get_pos())
to keep the position of nodes.Dg.delete_edge((u,v))
could beDg.delete_edge(u,v)
 indentation for
yield orientation
is excessive. should be 4 spaces
comment:23 Changed 22 months ago by
 Commit changed from b8852622e28e7d6e1f2aa083dc6a8f97cf186d5f to b1ee4b4a363247fcfdbb838f19680f18d502ef1a
Branch pushed to git repo; I updated commit sha1. New commits:
b1ee4b4  Minor corrections. Thanks David !

comment:24 Changed 22 months ago by
 Line
an undirected graph. It is an adaptation of the algorithm published in [CGMRV16]_.
has length 82 and so must be cut. Sorry.  There is an empty line after
def all_strong_orientations_iterator(self):
. Remove it. Otherwise we cannot build the documentation (use./sage docbuild reference/graphs html
to rebuilt only that part of the doc).  Line
# if the graph has a bridge or is disconnected, then it cannot be strongly oriented
is too long
We have a method strong_orientation
returning a random strong orientation, and method all_strong_orientations_iterator
. Wouldn't it be better to rename your method strong_orientations_iterator
?
comment:25 Changed 22 months ago by
You could also rebase on 7.6.beta2
comment:26 Changed 22 months ago by
 Commit changed from b1ee4b4a363247fcfdbb838f19680f18d502ef1a to 80a0ba406fbc279fc941b7cbd953794b93cb7683
Branch pushed to git repo; I updated commit sha1. New commits:
80a0ba4  Method name changed for consistency

comment:27 followup: ↓ 28 Changed 22 months ago by
 Status changed from needs_review to needs_work
I discovered some limitations that must be fixed and may be documented (at least to recall that the number of orientations could be huge).
1 I don't know what's going on here. I tried many times and sometimes its working well, sometimes not. I have put the graph6 strings of the graphs so that you can try it and track&solve the issue.
sage: G = graphs.RandomBarabasiAlbert(30, 2) sage: G.graph6_string() ']ZgZCOWg@OD?c?G@?oA?C_?D??SO?@?A??_AC??OO?A???o?G?OG@??A?A??P???A_???CC???' sage: %time D = next(G.strong_orientations_iterator()) CPU times: user 1.39 s, sys: 663 ms, total: 2.06 s Wall time: 2.37 s sage: sage: G = graphs.RandomBarabasiAlbert(30, 2) sage: G.graph6_string() ']\\cl@_W_`_S?GA?KOC?c?GO?P?@C???`AA??C?G?_@??A?OC_??_???aO???C??@_??A???o??' sage: %time D = next(G.strong_orientations_iterator())  StopIteration Traceback (most recent call last) ... StopIteration:
2 Here we have too big numbers, but it can be easily fixed replacing the for i in range(0, 2**(len(A)1))
loop with a while loop.
sage: G = graphs.RandomBarabasiAlbert(100, 2) sage: %time D = next(G.strong_orientations_iterator())  OverflowError Traceback (most recent call last) ... /Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/strong_orientations_generator.pyc in strong_orientations_iterator(self) 131 # of G by orienting properly the treeedges 132 previousWord = 0 > 133 for i in range(0, 2**(len(A)1)): 134 word = (i >> 1) ^ i 135 bitChanged = word ^ previousWord OverflowError: range() result has too many items sage: G.graph6_string() 'b\\MOp_WGS_D?g?a?B?C?O?Q?H??OO?_?CGC?c??@A??A?@??OG?G_????G?G???P?OO??_@???A??@@O?????@?_??C@???P?????'
3 Concerning the _all_strong_orientations_of_a_mixed_graph
method (you should remove the all
), I don't know how many number of recursive calls can be done before reaching the stack limit. So we might have a problem here too. This will certainly appear after you have fixed the previous issues.
comment:28 in reply to: ↑ 27 ; followup: ↓ 30 Changed 22 months ago by
I changed the for loop into a while loop, as well as the name of the helper method (will submit it). The second and the third graphs in your tests are not biconnected, so there is no strong orientation possible for these graphs. That's why the next() method of the iterator throws an exception (which is the normal behaviour). Replying to dcoudert:
I discovered some limitations that must be fixed and may be documented (at least to recall that the number of orientations could be huge).
1 I don't know what's going on here. I tried many times and sometimes its working well, sometimes not. I have put the graph6 strings of the graphs so that you can try it and track&solve the issue.
sage: G = graphs.RandomBarabasiAlbert(30, 2) sage: G.graph6_string() ']ZgZCOWg@OD?c?G@?oA?C_?D??SO?@?A??_AC??OO?A???o?G?OG@??A?A??P???A_???CC???' sage: %time D = next(G.strong_orientations_iterator()) CPU times: user 1.39 s, sys: 663 ms, total: 2.06 s Wall time: 2.37 s sage: sage: G = graphs.RandomBarabasiAlbert(30, 2) sage: G.graph6_string() ']\\cl@_W_`_S?GA?KOC?c?GO?P?@C???`AA??C?G?_@??A?OC_??_???aO???C??@_??A???o??' sage: %time D = next(G.strong_orientations_iterator())  StopIteration Traceback (most recent call last) ... StopIteration:2 Here we have too big numbers, but it can be easily fixed replacing the
for i in range(0, 2**(len(A)1))
loop with a while loop.sage: G = graphs.RandomBarabasiAlbert(100, 2) sage: %time D = next(G.strong_orientations_iterator())  OverflowError Traceback (most recent call last) ... /Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/strong_orientations_generator.pyc in strong_orientations_iterator(self) 131 # of G by orienting properly the treeedges 132 previousWord = 0 > 133 for i in range(0, 2**(len(A)1)): 134 word = (i >> 1) ^ i 135 bitChanged = word ^ previousWord OverflowError: range() result has too many items sage: G.graph6_string() 'b\\MOp_WGS_D?g?a?B?C?O?Q?H??OO?_?CGC?c??@A??A?@??OG?G_????G?G???P?OO??_@???A??@@O?????@?_??C@???P?????'3 Concerning the
_all_strong_orientations_of_a_mixed_graph
method (you should remove theall
), I don't know how many number of recursive calls can be done before reaching the stack limit. So we might have a problem here too. This will certainly appear after you have fixed the previous issues.
comment:29 Changed 22 months ago by
 Commit changed from 80a0ba406fbc279fc941b7cbd953794b93cb7683 to e440a3ff45b507f56e164798f0b0ddb9ae93370b
Branch pushed to git repo; I updated commit sha1. New commits:
e440a3f  Changed for loop to a while loop + the name of the helper method

comment:30 in reply to: ↑ 28 ; followup: ↓ 31 Changed 22 months ago by
Replying to pvalicov:
I changed the for loop into a while loop, as well as the name of the helper method (will submit it). The second and the third graphs in your tests are not biconnected, so there is no strong orientation possible for these graphs. That's why the next() method of the iterator throws an exception (which is the normal behaviour).
Right, first time I realize that the BA generator could return graphs that are not biconnected.
3 Concerning the
_all_strong_orientations_of_a_mixed_graph
method (you should remove theall
), I don't know how many number of recursive calls can be done before reaching the stack limit. So we might have a problem here too. This will certainly appear after you have fixed the previous issues.
So far no stackoverflow error, but slow on large graphs. This was expected.
sage: G = graphs.RandomBarabasiAlbert(100, 2) sage: %time D = next(G.strong_orientations_iterator()) CPU times: user 81.3 ms, sys: 11.8 ms, total: 93.1 ms Wall time: 84.6 ms sage: G = graphs.RandomBarabasiAlbert(1000, 2) sage: %time D = next(G.strong_orientations_iterator()) CPU times: user 1min, sys: 364 ms, total: 1min Wall time: 1min 1s sage: G = graphs.RandomBarabasiAlbert(2000, 2) sage: %time D = next(G.strong_orientations_iterator()) CPU times: user 7min 53s, sys: 3.85 s, total: 7min 57s Wall time: 8min 4s
The patch passes all tests on src/sage/graphs/
but I have an issue with the documentation. I tried make docclean && make
and got
[dochtml] [graphs ] reading sources... [100%] sage/graphs/weakly_chordal [dochtml] [graphs ] /Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/graph.py:docstring of sage.graphs.graph.Graph.topological_minor:0: WARNING: Literal block expected; none found. [dochtml] Error building the documentation. [dochtml] Traceback (most recent call last): [dochtml] File "/Users/dcoudert/sage/local/lib/python/runpy.py", line 174, in _run_module_as_main [dochtml] "__main__", fname, loader, pkg_name) [dochtml] File "/Users/dcoudert/sage/local/lib/python/runpy.py", line 72, in _run_code [dochtml] exec code in run_globals [dochtml] File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage_setup/docbuild/__main__.py", line 2, in <module> [dochtml] main() [dochtml] File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage_setup/docbuild/__init__.py", line 1667, in main [dochtml] builder() [dochtml] File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage_setup/docbuild/__init__.py", line 316, in _wrapper [dochtml] getattr(get_builder(document), 'inventory')(*args, **kwds) [dochtml] File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage_setup/docbuild/__init__.py", line 510, in _wrapper [dochtml] build_many(build_ref_doc, L) [dochtml] File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage_setup/docbuild/__init__.py", line 252, in build_many [dochtml] ret = x.get(99999) [dochtml] File "/Users/dcoudert/sage/local/lib/python/multiprocessing/pool.py", line 567, in get [dochtml] raise self._value [dochtml] OSError: [graphs ] /Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/graph.py:docstring of sage.graphs.graph.Graph.topological_minor:0: WARNING: Literal block expected; none found. [dochtml]
Are you able to build the doc ? may be the problem comes from something else...
comment:31 in reply to: ↑ 30 Changed 22 months ago by
Replying to dcoudert:
Replying to pvalicov:
I changed the for loop into a while loop, as well as the name of the helper method (will submit it). The second and the third graphs in your tests are not biconnected, so there is no strong orientation possible for these graphs. That's why the next() method of the iterator throws an exception (which is the normal behaviour).
Right, first time I realize that the BA generator could return graphs that are not biconnected.
3 Concerning the
_all_strong_orientations_of_a_mixed_graph
method (you should remove theall
), I don't know how many number of recursive calls can be done before reaching the stack limit. So we might have a problem here too. This will certainly appear after you have fixed the previous issues.So far no stackoverflow error, but slow on large graphs. This was expected.
sage: G = graphs.RandomBarabasiAlbert(100, 2) sage: %time D = next(G.strong_orientations_iterator()) CPU times: user 81.3 ms, sys: 11.8 ms, total: 93.1 ms Wall time: 84.6 ms sage: G = graphs.RandomBarabasiAlbert(1000, 2) sage: %time D = next(G.strong_orientations_iterator()) CPU times: user 1min, sys: 364 ms, total: 1min Wall time: 1min 1s sage: G = graphs.RandomBarabasiAlbert(2000, 2) sage: %time D = next(G.strong_orientations_iterator()) CPU times: user 7min 53s, sys: 3.85 s, total: 7min 57s Wall time: 8min 4sThe patch passes all tests on
src/sage/graphs/
but I have an issue with the documentation. I triedmake docclean && make
and got[dochtml] [graphs ] reading sources... [100%] sage/graphs/weakly_chordal [dochtml] [graphs ] /Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/graph.py:docstring of sage.graphs.graph.Graph.topological_minor:0: WARNING: Literal block expected; none found. [dochtml] Error building the documentation. [dochtml] Traceback (most recent call last): [dochtml] File "/Users/dcoudert/sage/local/lib/python/runpy.py", line 174, in _run_module_as_main [dochtml] "__main__", fname, loader, pkg_name) [dochtml] File "/Users/dcoudert/sage/local/lib/python/runpy.py", line 72, in _run_code [dochtml] exec code in run_globals [dochtml] File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage_setup/docbuild/__main__.py", line 2, in <module> [dochtml] main() [dochtml] File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage_setup/docbuild/__init__.py", line 1667, in main [dochtml] builder() [dochtml] File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage_setup/docbuild/__init__.py", line 316, in _wrapper [dochtml] getattr(get_builder(document), 'inventory')(*args, **kwds) [dochtml] File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage_setup/docbuild/__init__.py", line 510, in _wrapper [dochtml] build_many(build_ref_doc, L) [dochtml] File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage_setup/docbuild/__init__.py", line 252, in build_many [dochtml] ret = x.get(99999) [dochtml] File "/Users/dcoudert/sage/local/lib/python/multiprocessing/pool.py", line 567, in get [dochtml] raise self._value [dochtml] OSError: [graphs ] /Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/graph.py:docstring of sage.graphs.graph.Graph.topological_minor:0: WARNING: Literal block expected; none found. [dochtml]Are you able to build the doc ? may be the problem comes from something else...
I get the same errors as you and as far as I see from the error message, the problem comes from the docstring of the topological_minor
. Since it's my first submission, just to be clear: besides the file containing the function, the only changes I made in the rest of sage hierarchy was adding in sage/src/sage/graphs/graph.py an additional category and these lines of code :
from sage.graphs.strong_orientations_generator import strong_orientations_iterator Graph.strong_orientations_iterator = strong_orientations_iterator
Did I forget something?
comment:32 followup: ↓ 34 Changed 22 months ago by
 Reviewers set to David Coudert
Right, you should add sage/graphs/strong_orientations_generator
to file src/doc/en/reference/graphs/index.rst
. This way the file will be well visible in html documentation.
I have no clue where the error with topological_minor
comes from. May be some cache has to be clear or... don't know. May be the patchbot will provide extra information after adding above line and setting the ticket to needs review.
comment:33 Changed 22 months ago by
 Commit changed from e440a3ff45b507f56e164798f0b0ddb9ae93370b to b567f6089a3e8ffceeaf3d2a8bc523e546ddf333
Branch pushed to git repo; I updated commit sha1. New commits:
b567f60  Documentation errors fixed

comment:34 in reply to: ↑ 32 Changed 22 months ago by
Replying to dcoudert:
Right, you should add
sage/graphs/strong_orientations_generator
to filesrc/doc/en/reference/graphs/index.rst
. This way the file will be well visible in html documentation.I have no clue where the error with
topological_minor
comes from. May be some cache has to be clear or... don't know. May be the patchbot will provide extra information after adding above line and setting the ticket to needs review.
Thanks for that. There were some errors in the documentation and now it should work.
comment:35 Changed 22 months ago by
 Status changed from needs_work to needs_review
comment:36 Changed 22 months ago by
Now everything is working well: passes all tests and the documentation builds properly and look nice.
I have only very minor comments
 at the beginning of the module, you have
O(m*n)
but O(m) is without`
 You can check the source code of
src/sage/graphs/graph_decompositions/vertex_separation.pyx
to see how to get some titles in bold, or some titles with a blue background. This is not very important.
After that we will be done.
comment:37 followup: ↓ 39 Changed 22 months ago by
Some comments.
strong_orientations_iterator
should not haveself
as an input. Moreover,self
is not listed as an input. You should have
strong_orientations_iterator
in the actualgraph.py
as a proper method. This makes code maintenance easier.  References should go in the master reference file.
 I suspect your name is not
YOUR NAME
.  You should use
.. NOTE::
blocks.  You missed a latex formatting around an
O(m)
in theALGORITHM
part ofstrong_orientations_generator.py
. Similarly, you should remove the*
from the earlier one.  The
INPUT
block should be formatted as:INPUT:  ``D``g  the mixed graph; the undirected edges are doubly oriented  ``V``  the set of vertices  ``E``  the set of undirected edges (these edges are oriented in both ways); no labels are allowed
 All of your conditionals have an extra space, i.e., change
if cond :
toif cond:
.  This change needs to be reverted:

new file src/sage/graphs/strong_orientations_generator.py
diff git a/src/sage/graphs/strong_orientations_generator.py b/src/sage/graphs/strong_orientations_generator.py new file mode 100644 index 0000000..932fa85
 + def _strong_orientations_of_a_mixed_graph(Dg, V, E): 175 177  an iterator which will produce all strong orientations of the input 176 178 partially directed graph. 177 179 178 EXAMPLES: :180 EXAMPLES: 179 181 180 182 sage: from sage.graphs.strong_orientations_generator import _strong_orientations_of_a_mixed_graph 181 183 sage: g = graphs.CycleGraph(5)

comment:38 Changed 22 months ago by
 Commit changed from b567f6089a3e8ffceeaf3d2a8bc523e546ddf333 to ece584c431dd41f54336cec4eaa08ab69515ea8a
Branch pushed to git repo; I updated commit sha1. New commits:
ece584c  Minor documentation and code changes

comment:39 in reply to: ↑ 37 Changed 22 months ago by
Replying to tscrim:
Some comments.
strong_orientations_iterator
should not haveself
as an input. Moreover,self
is not listed as an input. You should have
strong_orientations_iterator
in the actualgraph.py
as a proper method. This makes code maintenance easier.
I thought that because of the helper function _strong_orientations_of_a_mixed_graph
will make the code in graph.py
more polluted. I followed the same pattern as for other graph algorithms which are in the folder src/sage/graphs'. Do you think it is still necessary to refactor the code and add it to
graph.py` ?
 References should go in the master reference file.
 I suspect your name is not
YOUR NAME
. You should use
.. NOTE::
blocks. You missed a latex formatting around an
O(m)
in theALGORITHM
part ofstrong_orientations_generator.py
. Similarly, you should remove the*
from the earlier one. The
INPUT
block should be formatted as:INPUT:  ``D``g  the mixed graph; the undirected edges are doubly oriented  ``V``  the set of vertices  ``E``  the set of undirected edges (these edges are oriented in both ways); no labels are allowed All of your conditionals have an extra space, i.e., change
if cond :
toif cond:
. This change needs to be reverted:
new file src/sage/graphs/strong_orientations_generator.py
diff git a/src/sage/graphs/strong_orientations_generator.py b/src/sage/graphs/strong_orientations_generator.py new file mode 100644 index 0000000..932fa85
 + def _strong_orientations_of_a_mixed_graph(Dg, V, E): 175 177  an iterator which will produce all strong orientations of the input 176 178 partially directed graph. 177 179 178 EXAMPLES: :180 EXAMPLES: 179 181 180 182 sage: from sage.graphs.strong_orientations_generator import _strong_orientations_of_a_mixed_graph 181 183 sage: g = graphs.CycleGraph(5)
comment:40 followup: ↓ 41 Changed 22 months ago by
I agree that it is good to have the helper function a separate file to reduce clutter. However, the main method strong_orientations_iterator
should be in the class itself (and contain the import statement out to the helper function).
comment:41 in reply to: ↑ 40 ; followup: ↓ 42 Changed 22 months ago by
Replying to tscrim:
I agree that it is good to have the helper function a separate file to reduce clutter. However, the main method
strong_orientations_iterator
should be in the class itself (and contain the import statement out to the helper function).
Sorry for being too insistent (and thanks for the effort) but then I don't understand the point of having files like tutte_polynomial.py
, schnyder.py
, lovasz_theta.py
, line_graph.py
, partial_cube.py
etc. in the src/sage/graphs/
?
The reason I followed the same way of coding by doing the import of the main function (i.e. strong_orientations_iterator
) in graph.py
is because I thought that importing the entire function makes somehow the entire code of the class Graph
easier as this class is already quite big in terms of lines of code.
comment:42 in reply to: ↑ 41 Changed 22 months ago by
Replying to pvalicov:
Replying to tscrim:
I agree that it is good to have the helper function a separate file to reduce clutter. However, the main method
strong_orientations_iterator
should be in the class itself (and contain the import statement out to the helper function).Sorry for being too insistent (and thanks for the effort) but then I don't understand the point of having files like
tutte_polynomial.py
,schnyder.py
,lovasz_theta.py
,line_graph.py
,partial_cube.py
etc. in thesrc/sage/graphs/
?
Some of them are better justified because they need larger volumes of code (such as helper classes), and even still I do not agree with the design choice of having it be a separate file. In particular, IMO the lovasz_theta.py
does not deserve a separate file.
The reason I followed the same way of coding by doing the import of the main function (i.e.
strong_orientations_iterator
) ingraph.py
is because I thought that importing the entire function makes somehow the entire code of the classGraph
easier as this class is already quite big in terms of lines of code.
It's taking a bucket of water from the ocean. Plus, find (and code folding) makes this argument far less effective to me, especially compared to having to search through other seemingly random files. However, since there does seem to be some practice of doing this, I won't oppose this, but it is not a good practice IMO (and it only works because it is Python).
comment:43 Changed 22 months ago by
The helper function is roughly 50 lines of codes. Putting it in a separated file while the main method is in graph.py
makes no sense to me. Either we decide to put every thing in graph.py
, or we agree to create this new file with the aim of gathering all methods related to orientations in it. For instance, we could move method strong_orientation
in this file. May be it could be named strong_orientations.py
rather than strong_orientations_generator.py
to be more general.
comment:44 Changed 22 months ago by
I am not an expert in Sage but I think that having a file like strong_orientations.py
regrouping everything would be clearer. More generally I would say that a file like orientations.py
containing the orientations
method, all methods related to strong orientations and future methods that one could naturally expect like acyclic_orientations
(I was thinking submitting it too), is a good idea. So what should I do? Do I leave my submission as it is for now ? And the factorisation, if it is accepted, will be another ticket (I don't know how to do it yet) ?
comment:45 Changed 22 months ago by
I'm in favor of having a special file for all kinds of orientations.
So, unless someone has strong arguments against it, I suggest to rename the file orientations.py
, rewrite the file header to explain that this file contains methods related to graph orientations and move the description of the strong orientation generator inside the method.
The top description of the file could be something like:
r""" Orientations This module implements several methods to compute orientations of undirected graphs subject to specific constraints (e.g., acyclic, strongly connected, etc.). It also implements some iterators over all these orientations. **This module contains the following methods** .. csvtable:: :class: contentstable :widths: 30, 70 :delim:  :meth:`strong_orientations_iterator`  Return an iterator over all strong orientations of a graph `G` Authors   Kolja Knauer, Petru Valicov (20170110)  initial version Methods  """
See file src/sage/graphs/graph_decomposition/vertex_separation.pyx
for example.
In another ticket, we can move related methods to this new file, and at the same time fix minor issues such as:
sage: G = Graph(1) sage: next(G.orientations()) Digraph on 0 vertices
comment:46 Changed 22 months ago by
 Commit changed from ece584c431dd41f54336cec4eaa08ab69515ea8a to 3ec3ae6b1d971987fdbc4af6f002ebc9783fc3a5
Branch pushed to git repo; I updated commit sha1. New commits:
3ec3ae6  The `orientations.py` file created, comments and some more tests added

comment:47 Changed 22 months ago by
 you forgot to update file
src/doc/en/reference/graphs/index.rst
:sage/graphs/strong_orientations_generator
>sage/graphs/orientations
. After that I can try to build the doc.
 Because we use this definition "A biconnected graph is a connected graph on two or more vertices that is not broken into disconnected pieces by deleting any single vertex.", we have the following issue:
sage: G = graphs.CompleteGraph(2) sage: next(G.strong_orientations_iterator())  IndexError Traceback (most recent call last) <ipythoninput121a1d14901a2b> in <module>() > 1 next(G.strong_orientations_iterator()) /Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/orientations.pyc in strong_orientations_iterator(G) 155 156 previousWord = word; > 157 if existingAedges[bit] == 0: 158 Dg.reverse_edge(A[bit]) 159 existingAedges[bit] = 1 IndexError: list index out of range
To fix that you can certainly ensure that the graph has at least 3 vertices and is biconnected. Add a doctest for this case please.
comment:48 Changed 22 months ago by
 Commit changed from 3ec3ae6b1d971987fdbc4af6f002ebc9783fc3a5 to 005a780cb41b4be63e1115b4bb61716d1c9c1715
comment:49 Changed 22 months ago by
 Commit changed from 005a780cb41b4be63e1115b4bb61716d1c9c1715 to 4506eabab1fca6889786a64b7c7fc4f66dc60326
Branch pushed to git repo; I updated commit sha1. New commits:
4506eab  Doctest for a complete graph on 2 vertices

comment:50 followup: ↓ 52 Changed 22 months ago by
 Remove
REFERENCES
since references are somewhere else.  Add an empty line after
ALGORITHM:
 in the text, I suggest to rewrite "and then launches
_strong_orientations_of_a_mixed_graph
which is the helper function corresponding to the generation algorithm described in" as "and then launches a helper function corresponding to the generation algorithm described in". The reason is that method named like_blah
are not displayed in the html documentation.
Almost done. Passes all tests and the rest of the doc displays nicely.
comment:51 Changed 22 months ago by
 Commit changed from 4506eabab1fca6889786a64b7c7fc4f66dc60326 to 47f0e7e9a162a476b47db6e44f7af5fafd52a346
Branch pushed to git repo; I updated commit sha1. New commits:
47f0e7e  Few remarks in comments

comment:52 in reply to: ↑ 50 Changed 22 months ago by
Thanks, I've done everything. One comment: since we have a separate file to all kind of orientations stuff, wouldn't it be better to gather all the references in this file as it is done in other files or we keep everything in the master reference file? It is done this way in several files in src/sage/graphs
.
Replying to dcoudert:
 Remove
REFERENCES
since references are somewhere else. Add an empty line after
ALGORITHM:
 in the text, I suggest to rewrite "and then launches
_strong_orientations_of_a_mixed_graph
which is the helper function corresponding to the generation algorithm described in" as "and then launches a helper function corresponding to the generation algorithm described in". The reason is that method named like_blah
are not displayed in the html documentation.Almost done. Passes all tests and the rest of the doc displays nicely.
comment:53 Changed 22 months ago by
 Status changed from needs_review to positive_review
Some months ago, It has been decided to put all references in the master file. So all references that are currently in the graph module will eventually be moved to the master file. This is to avoid duplications (references and keys).
For me this patch is now good to go. Congratulation for your first contribution !
comment:54 Changed 22 months ago by
 Branch changed from u/pvalicov/generation_of_strong_orientations_of_a_graph to 47f0e7e9a162a476b47db6e44f7af5fafd52a346
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Added the generation of strong orientations
Enumeration of strong orientations added
Generation of strong orientations
Merge branch 'strong_orientations' into t/22206/generation_of_strong_orientations_of_a_graph