#22206 closed enhancement (fixed)

Generation of strong orientations of a graph

Reported by: pvalicov Owned by:
Priority: major Milestone: sage-7.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 20 months ago by pvalicov

  • Branch set to u/pvalicov/generation_of_strong_orientations_of_a_graph

comment:2 Changed 20 months ago by git

  • Commit set to e3498e042ef040a7465c44bdf9d9646c706579fe

Branch pushed to git repo; I updated commit sha1. New commits:

ba0d43aAdded the generation of strong orientations
e5b1320Enumeration of strong orientations added
1a7d6b5Generation of strong orientations
e3498e0Merge branch 'strong_orientations' into t/22206/generation_of_strong_orientations_of_a_graph

comment:3 Changed 20 months ago by pvalicov

  • Authors set to Petru Valicov and Kolja Knauer
  • Keywords graphs orientations added
  • Type changed from PLEASE CHANGE to enhancement

comment:4 Changed 20 months ago by pvalicov

  • Component changed from PLEASE CHANGE to graph theory

comment:5 follow-up: Changed 20 months ago by chapoton

Hello, welcome !

  • always have a blankline after a line ending with ::
  • every function needs to have doctests

comment:6 in reply to: ↑ 5 ; follow-up: Changed 20 months ago by 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?

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 20 months ago by chapoton

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
Last edited 20 months ago by chapoton (previous) (diff)

comment:8 Changed 20 months ago by chapoton

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 20 months ago by git

  • Commit changed from e3498e042ef040a7465c44bdf9d9646c706579fe to aa8401d76c0319c63568bb98a690f004ee0e4987

Branch pushed to git repo; I updated commit sha1. New commits:

aa8401dDoctests added, some minor corrections

comment:10 Changed 20 months ago by git

  • Commit changed from aa8401d76c0319c63568bb98a690f004ee0e4987 to 464df4c26470f343d7427c7429a42e603d4914f3

Branch pushed to git repo; I updated commit sha1. New commits:

464df4cxrange replaced by range (for Python 3)

comment:11 Changed 20 months ago by git

  • Commit changed from 464df4c26470f343d7427c7429a42e603d4914f3 to 8ba75c01f228e4d632661d8a7c2391be7b1f5e2d

Branch pushed to git repo; I updated commit sha1. New commits:

8ba75c0Comments corrections

comment:12 Changed 20 months ago by chapoton

  • the main function still has no documentation
  • when calling a reference, you must write [CGMRV16]_ with an underscore

comment:13 Changed 20 months ago by git

  • Commit changed from 8ba75c01f228e4d632661d8a7c2391be7b1f5e2d to 9988011593a882e2c1394bdd914dddb13c51b275

Branch pushed to git repo; I updated commit sha1. New commits:

9988011Corrections for documentation of functions

comment:14 Changed 20 months ago by dcoudert

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 simply Dg = DiGraph(self)
  • when you do treeEdges = [(edge[0],edge[1]) for edge in self.edges() if edge in te], all edges in te are in self. So to remove the labels, you can do treeEdges = [(u,v) for u,v,_ in te]
  • You can initialize existingAedges directly using existingAedges = [0]*len(A)
  • avoid bitChanged >>= 1; bit += 1; and put each instruction in a separate line
  • use yield Dg.copy(). Indeed, the instruction yield Dg will in fact return a pointer. Since Dg is modified in your method, what you have returned will also be modified.

Best,

David.

comment:15 Changed 20 months ago by dcoudert

Ticket #22254 which improves the computation of bridges might also be useful. The proposed implementation avoids a call to strong_orientation...

comment:16 follow-up: Changed 20 months ago by pvalicov

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 20 months ago by git

  • Commit changed from 9988011593a882e2c1394bdd914dddb13c51b275 to 2698bf5a09163061b2eef9823a4669b8be92bbb7

Branch pushed to git repo; I updated commit sha1. New commits:

2698bf5Few code improvements.

comment:18 in reply to: ↑ 16 Changed 20 months ago by dcoudert

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 20 months ago by git

  • Commit changed from 2698bf5a09163061b2eef9823a4669b8be92bbb7 to b8852622e28e7d6e1f2aa083dc6a8f97cf186d5f

Branch pushed to git repo; I updated commit sha1. New commits:

d25993dtrac #22247: add method is_biconnected to graph
498db89trac #22247: connect to graph_classes
3979aeatrac #22247: add link to blocks_and_cuts_tree to seealso section
29a546fMerge branch 'u/dcoudert/22247' of git://trac.sagemath.org/sage into t/22206/generation_of_strong_orientations_of_a_graph
b885262Biconnectivity test added using the code from ticket #22247. Thanks !

comment:20 Changed 20 months ago by dcoudert

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 20 months ago by pvalicov

  • Status changed from new to needs_review

comment:22 Changed 20 months ago by dcoudert

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 be Dg.delete_edge(u,v)
  • indentation for yield orientation is excessive. should be 4 spaces

comment:23 Changed 20 months ago by git

  • Commit changed from b8852622e28e7d6e1f2aa083dc6a8f97cf186d5f to b1ee4b4a363247fcfdbb838f19680f18d502ef1a

Branch pushed to git repo; I updated commit sha1. New commits:

b1ee4b4Minor corrections. Thanks David !

comment:24 Changed 20 months ago by dcoudert

  • 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 20 months ago by dcoudert

You could also rebase on 7.6.beta2

comment:26 Changed 20 months ago by git

  • Commit changed from b1ee4b4a363247fcfdbb838f19680f18d502ef1a to 80a0ba406fbc279fc941b7cbd953794b93cb7683

Branch pushed to git repo; I updated commit sha1. New commits:

80a0ba4Method name changed for consistency

comment:27 follow-up: Changed 20 months ago by dcoudert

  • 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/site-packages/sage/graphs/strong_orientations_generator.pyc in strong_orientations_iterator(self)
    131     # of G by orienting properly the tree-edges
    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 ; follow-up: Changed 20 months ago by 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). 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/site-packages/sage/graphs/strong_orientations_generator.pyc in strong_orientations_iterator(self)
    131     # of G by orienting properly the tree-edges
    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:29 Changed 20 months ago by git

  • Commit changed from 80a0ba406fbc279fc941b7cbd953794b93cb7683 to e440a3ff45b507f56e164798f0b0ddb9ae93370b

Branch pushed to git repo; I updated commit sha1. New commits:

e440a3fChanged for loop to a while loop + the name of the helper method

comment:30 in reply to: ↑ 28 ; follow-up: Changed 20 months ago by 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 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.

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 doc-clean && make and got

[dochtml] [graphs   ] reading sources... [100%] sage/graphs/weakly_chordal
[dochtml] [graphs   ] /Users/dcoudert/sage/local/lib/python2.7/site-packages/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/site-packages/sage_setup/docbuild/__main__.py", line 2, in <module>
[dochtml]     main()
[dochtml]   File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 1667, in main
[dochtml]     builder()
[dochtml]   File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/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/site-packages/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/site-packages/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/site-packages/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 20 months ago by pvalicov

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 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.

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 doc-clean && make and got

[dochtml] [graphs   ] reading sources... [100%] sage/graphs/weakly_chordal
[dochtml] [graphs   ] /Users/dcoudert/sage/local/lib/python2.7/site-packages/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/site-packages/sage_setup/docbuild/__main__.py", line 2, in <module>
[dochtml]     main()
[dochtml]   File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 1667, in main
[dochtml]     builder()
[dochtml]   File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/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/site-packages/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/site-packages/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/site-packages/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 follow-up: Changed 20 months ago by dcoudert

  • 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 20 months ago by git

  • Commit changed from e440a3ff45b507f56e164798f0b0ddb9ae93370b to b567f6089a3e8ffceeaf3d2a8bc523e546ddf333

Branch pushed to git repo; I updated commit sha1. New commits:

b567f60Documentation errors fixed

comment:34 in reply to: ↑ 32 Changed 20 months ago by pvalicov

Replying to dcoudert:

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.

Thanks for that. There were some errors in the documentation and now it should work.

comment:35 Changed 20 months ago by pvalicov

  • Status changed from needs_work to needs_review

comment:36 Changed 20 months ago by dcoudert

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 follow-up: Changed 20 months ago by tscrim

  • Authors changed from Petru Valicov and Kolja Knauer to Petru Valicov, Kolja Knauer

Some comments.

  • strong_orientations_iterator should not have self as an input. Moreover, self is not listed as an input.
  • You should have strong_orientations_iterator in the actual graph.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 the ALGORITHM part of strong_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 : to if 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): 
      175177    - an iterator which will produce all strong orientations of the input
      176178      partially directed graph.
      177179
      178     EXAMPLES::
       180    EXAMPLES:
      179181
      180182        sage: from sage.graphs.strong_orientations_generator import _strong_orientations_of_a_mixed_graph
      181183        sage: g = graphs.CycleGraph(5)

comment:38 Changed 20 months ago by git

  • Commit changed from b567f6089a3e8ffceeaf3d2a8bc523e546ddf333 to ece584c431dd41f54336cec4eaa08ab69515ea8a

Branch pushed to git repo; I updated commit sha1. New commits:

ece584cMinor documentation and code changes

comment:39 in reply to: ↑ 37 Changed 20 months ago by pvalicov

Replying to tscrim:

Some comments.

  • strong_orientations_iterator should not have self as an input. Moreover, self is not listed as an input.
  • You should have strong_orientations_iterator in the actual graph.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 the ALGORITHM part of strong_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 : to if 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): 
      175177    - an iterator which will produce all strong orientations of the input
      176178      partially directed graph.
      177179
      178     EXAMPLES::
       180    EXAMPLES:
      179181
      180182        sage: from sage.graphs.strong_orientations_generator import _strong_orientations_of_a_mixed_graph
      181183        sage: g = graphs.CycleGraph(5)

comment:40 follow-up: Changed 20 months ago by 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).

comment:41 in reply to: ↑ 40 ; follow-up: Changed 20 months ago by 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 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 20 months ago by tscrim

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 the src/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) 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.

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 20 months ago by dcoudert

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 20 months ago by pvalicov

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 20 months ago by dcoudert

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**

.. csv-table::
    :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 (2017-01-10) -- 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 20 months ago by git

  • Commit changed from ece584c431dd41f54336cec4eaa08ab69515ea8a to 3ec3ae6b1d971987fdbc4af6f002ebc9783fc3a5

Branch pushed to git repo; I updated commit sha1. New commits:

3ec3ae6The `orientations.py` file created, comments and some more tests added

comment:47 Changed 20 months ago by dcoudert

  • 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)
    <ipython-input-12-1a1d14901a2b> in <module>()
    ----> 1 next(G.strong_orientations_iterator())
    
    /Users/dcoudert/sage/local/lib/python2.7/site-packages/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 20 months ago by git

  • Commit changed from 3ec3ae6b1d971987fdbc4af6f002ebc9783fc3a5 to 005a780cb41b4be63e1115b4bb61716d1c9c1715

Branch pushed to git repo; I updated commit sha1. New commits:

b8be659Documentation + small not 2-connected graphs issues fixed
005a780removed useless ;

comment:49 Changed 20 months ago by git

  • Commit changed from 005a780cb41b4be63e1115b4bb61716d1c9c1715 to 4506eabab1fca6889786a64b7c7fc4f66dc60326

Branch pushed to git repo; I updated commit sha1. New commits:

4506eabDoctest for a complete graph on 2 vertices

comment:50 follow-up: Changed 20 months ago by 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:51 Changed 20 months ago by git

  • Commit changed from 4506eabab1fca6889786a64b7c7fc4f66dc60326 to 47f0e7e9a162a476b47db6e44f7af5fafd52a346

Branch pushed to git repo; I updated commit sha1. New commits:

47f0e7eFew remarks in comments

comment:52 in reply to: ↑ 50 Changed 20 months ago by pvalicov

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 20 months ago by dcoudert

  • 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 19 months ago by vbraun

  • 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
Note: See TracTickets for help on using tickets.