Opened 4 years ago
Closed 4 years ago
#21415 closed enhancement (fixed)
Iterator over all orientations of a graph
Reported by:  tscrim  Owned by:  

Priority:  major  Milestone:  sage7.4 
Component:  graph theory  Keywords:  
Cc:  jmantysalo  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Jori Mäntysalo 
Report Upstream:  N/A  Work issues:  
Branch:  ce48418 (Commits)  Commit:  ce4841826cdcc83a1b88d17f3d3a62d8a8f4b1c3 
Dependencies:  Stopgaps: 
Description
I was asked if Sage provides code to iterate over all orientations of a graph. We should add this to Sage.
Change History (22)
comment:1 Changed 4 years ago by
 Cc jmantysalo added
comment:2 Changed 4 years ago by
Seems reasonable. So this needs just definition, examples and so on. The graph may not have multiple edges nor loops, but it can have weight (or other labels) assigned to edges.
I can see no easy way to optimize this, product
already does what is possible.
comment:3 Changed 4 years ago by
Something like this for docstring?
""" Return an iterator over orientations of the graph. An *orientation* of an undirected graph is a directed graph such that every edge is assigned a direction. Hence there are `2^s` oriented digraphs for a graph with `s` edges. EXAMPLES:: sage: G = Graph([[1,2,3], [(1, 2, 'a'), (1, 3, 'b')]], format='vertices_and_edges') sage: it = G.all_orientations() sage: D = it.next() sage: D.edges() # Random order for orientations [(1, 2, 'a'), (1, 3, 'b')] sage: D = it.next() sage: D.edges() # Random order for orientations [(2, 1, 'a'), (1, 3, 'b')] TESTS:: sage: G = Graph() sage: G_ = [g for g in G.all_orientations()] sage: len(G_) 1 sage: G_[0] Digraph on 0 vertices sage: G = Graph(5) sage: it = G.all_orientations() sage: G_ = next(it) sage: G_.size() 0 """
Should the name be all_orientations()
or just orientations()
?
comment:4 Changed 4 years ago by
orientations
is probably better. I was thinking of actually making one function for the iterator and one for the list. What do you think?
comment:5 Changed 4 years ago by
Also, the docstring looks good. We will just have to add some tests for multiedges and/or loops. However, the order of the iterator and edges should be consistent when the vertices have a total ordering (like the integers).
comment:6 Changed 4 years ago by
I didn't know that sort=True
is the default for edges
. Actually I didn't even know about the option. But that is good, we can have easier examples.
Many graph functions already have both list and iterator versions, so I guess it makes sense to have both. But if unsure, add only iterator. Python seems to be changing more iteratorstyle, range
vs. xrange
, but I don't know if it should affect us.
comment:7 Changed 4 years ago by
See also this ask question. The suggested solution is of course not optimal since we create list and then check membership (the idea was to show how to easily reuse existing code), but it deals with data structure, embedding, etc.
comment:8 Changed 4 years ago by
The solution proposed in this ask question is certainly more expensive than the solution proposed above. However, the decoration of the method (data structure, etc.) is interesting.
I suggest to avoid a method able to return all orientations at once: too huge list. An iterator seem much more appropriate.
Also, we may have an option to iterate over a random ordering of the orientations, for instance using this simple trick
E = [[(u,v,l), (v,u,l)] if randint(0,1) else [(v,u,l), (u,v,l)] for u,v,l in G.edges()]
Another option is to use gray codes or revolving door principles to ensure that two consecutive orientations have very little modifications. It will not change the validity of the method, just the ordering. So we may save some time using the copy method of digraph and then applying the minor changes instead of creating a completely new graph. See e.g. the doc on gray code of simpy and discussion on sagecombinatdevel. Admittedly more tricky to code.
comment:9 Changed 4 years ago by
 Branch set to public/graphs/orientations_iter21415
 Commit set to 44e925fa54823f18f3c4d39fba05ed2bb98874f4
 Status changed from new to needs_review
I would say Python is not switching to more iterator style perse, but having default behavior that is more practical for the typical programming purpose.
I put the code into a branch, taking some from the ask answer, and kept only an iterator because of how big is does get.
New commits:
44e925f  Implementing iterator over all orientations of a graph.

comment:10 followup: ↓ 11 Changed 4 years ago by
 Status changed from needs_review to needs_work
implementation
is missing from theINPUT
block.
 "optional" at documentation of parameter
sparse
is strange, anddata_structure
does not have it; that is inconsistent.
 Spaces in the line after oneline description (and that makes index of functions quite bad).
 Is it meaningful to copy name of original graph? Sounds strange to have a directed Petersen graph.
Otherwise it seems to work, attributes for allowing loops and/or multiedges works and so on.
comment:11 in reply to: ↑ 10 ; followup: ↓ 12 Changed 4 years ago by
Replying to jmantysalo:
implementation
is missing from theINPUT
block.
This is not included in any documentation. I am following suit.
 "optional" at documentation of parameter
sparse
is strange, anddata_structure
does not have it; that is inconsistent.
sparse
is there as a shorthand for (the necessary) data_structure
, so it is optional.
 Spaces in the line after oneline description (and that makes index of functions quite bad).
Will fix.
 Is it meaningful to copy name of original graph? Sounds strange to have a directed Petersen graph.
Should we add "directed" to the front of the name or just drop it altogether? I don't have a preference on this.
Otherwise it seems to work, attributes for allowing loops and/or multiedges works and so on.
I will also add tests for nonsimple graphs.
comment:12 in reply to: ↑ 11 ; followup: ↓ 15 Changed 4 years ago by
 Reviewers set to Jori Mäntysalo
Replying to tscrim:
implementation
is missing from theINPUT
block.This is not included in any documentation. I am following suit.
OK.
 "optional" at documentation of parameter
sparse
is strange, anddata_structure
does not have it; that is inconsistent.
sparse
is there as a shorthand for (the necessary)data_structure
, so it is optional.
I do not understand. Both parameters are optional, as both have a default value. But whatever, won't block me from giving review.
 Is it meaningful to copy name of original graph? Sounds strange to have a directed Petersen graph.
Should we add "directed" to the front of the name or just drop it altogether? I don't have a preference on this.
No, not "directed". Maybe "An orientation of ..." or nothing. I can't say either.
Otherwise it seems to work, attributes for allowing loops and/or multiedges works and so on.
I will also add tests for nonsimple graphs.
OK. I can review this.
comment:13 Changed 4 years ago by
 Commit changed from 44e925fa54823f18f3c4d39fba05ed2bb98874f4 to 5e46a141d339093286d8c25d0f7c59fe18a72168
Branch pushed to git repo; I updated commit sha1. New commits:
5e46a14  Addressing reviewer comments.

comment:14 Changed 4 years ago by
 Commit changed from 5e46a141d339093286d8c25d0f7c59fe18a72168 to 253347e51c6aa5cf87807b83cdde750bae902078
Branch pushed to git repo; I updated commit sha1. New commits:
253347e  Adding another test and using Python3 next.

comment:15 in reply to: ↑ 12 Changed 4 years ago by
Replying to jmantysalo:
Replying to tscrim:
 "optional" at documentation of parameter
sparse
is strange, anddata_structure
does not have it; that is inconsistent.
sparse
is there as a shorthand for (the necessary)data_structure
, so it is optional.I do not understand. Both parameters are optional, as both have a default value. But whatever, won't block me from giving review.
How I see it, data_structure
is necessary, even though it has a default value, but sparse
is not.
 Is it meaningful to copy name of original graph? Sounds strange to have a directed Petersen graph.
Should we add "directed" to the front of the name or just drop it altogether? I don't have a preference on this.
No, not "directed". Maybe "An orientation of ..." or nothing. I can't say either.
I added "An orientation of" when a name is specified.
I've addressed all of the mentioned issues.
comment:16 Changed 4 years ago by
Seems good and tests passed, documentation builds etc.
But only now, when you added a test for multigraphs, I really thinked about this; sorry about being late. What about orientations of Graph({1: [2, 2]}, multiedges=True)
? The code gives 4, but only 3 different. Same applies to graphs with loops.
I don't know how we should address this. But at a minimun this should be documented.
comment:17 Changed 4 years ago by
Actually, the loop is wrong; for that, either orientation is equivalent. However, for the multiedges, you just can't distinguish them. I think it would be much harder to code that, so I will just document the behavior.
comment:18 Changed 4 years ago by
 Commit changed from 253347e51c6aa5cf87807b83cdde750bae902078 to ce4841826cdcc83a1b88d17f3d3a62d8a8f4b1c3
Branch pushed to git repo; I updated commit sha1. New commits:
ce48418  Fixing loops and documenting multiple edges behavior.

comment:19 Changed 4 years ago by
 Status changed from needs_work to positive_review
OK, I am happy with these. Please mark as positive_review if you are ready; as you did not put this to needs_review, I am not sure if you still want to make some changes.
comment:20 Changed 4 years ago by
 Status changed from positive_review to needs_work
comment:21 Changed 4 years ago by
 Status changed from needs_work to positive_review
I just forgot to set it back. Thanks!
comment:22 Changed 4 years ago by
 Branch changed from public/graphs/orientations_iter21415 to ce4841826cdcc83a1b88d17f3d3a62d8a8f4b1c3
 Resolution set to fixed
 Status changed from positive_review to closed
Here is some code that does it: