Opened 5 years ago

Closed 5 years ago

# Iterator over all orientations of a graph

Reported by: Owned by: tscrim major sage-7.4 graph theory jmantysalo Travis Scrimshaw Jori Mäntysalo N/A ce48418 ce4841826cdcc83a1b88d17f3d3a62d8a8f4b1c3

### Description

I was asked if Sage provides code to iterate over all orientations of a graph. We should add this to Sage.

### comment:1 Changed 5 years ago by tscrim

Here is some code that does it:

```def all_orientations(G):
from itertools import product
E = [[(u,v,label), (v,u,label)] for u,v,label in G.edges()]
verts = G.vertices()
for edges in product(*E):
yield DiGraph([verts, edges], format='vertices_and_edges')
```

### comment:2 Changed 5 years ago by jmantysalo

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 5 years ago by jmantysalo

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 5 years ago by tscrim

`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 5 years ago by tscrim

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 5 years ago by jmantysalo

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 iterator-style, `range` vs. `xrange`, but I don't know if it should affect us.

### comment:7 Changed 5 years ago by tmonteil

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 5 years ago by dcoudert

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 sage-combinat-devel. Admittedly more tricky to code.

### comment:9 Changed 5 years ago by tscrim

• Authors set to Travis Scrimshaw
• Branch set to public/graphs/orientations_iter-21415
• Commit set to 44e925fa54823f18f3c4d39fba05ed2bb98874f4
• Status changed from new to needs_review

I would say Python is not switching to more iterator style per-se, 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.`
Last edited 5 years ago by tscrim (previous) (diff)

### comment:10 follow-up: ↓ 11 Changed 5 years ago by jmantysalo

• Status changed from needs_review to needs_work
• `implementation` is missing from the `INPUT` block.
• "optional" at documentation of parameter `sparse` is strange, and `data_structure` does not have it; that is inconsistent.
• Spaces in the line after one-line 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.

Last edited 5 years ago by jmantysalo (previous) (diff)

### comment:11 in reply to: ↑ 10 ; follow-up: ↓ 12 Changed 5 years ago by tscrim

• `implementation` is missing from the `INPUT` block.

This is not included in any documentation. I am following suit.

• "optional" at documentation of parameter `sparse` is strange, and `data_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 one-line 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 non-simple graphs.

### comment:12 in reply to: ↑ 11 ; follow-up: ↓ 15 Changed 5 years ago by jmantysalo

• Reviewers set to Jori Mäntysalo

• `implementation` is missing from the `INPUT` block.

This is not included in any documentation. I am following suit.

OK.

• "optional" at documentation of parameter `sparse` is strange, and `data_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 non-simple graphs.

OK. I can review this.

### comment:13 Changed 5 years ago by git

• Commit changed from 44e925fa54823f18f3c4d39fba05ed2bb98874f4 to 5e46a141d339093286d8c25d0f7c59fe18a72168

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

 ​5e46a14 `Addressing reviewer comments.`

### comment:14 Changed 5 years ago by git

• 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 5 years ago by tscrim

• "optional" at documentation of parameter `sparse` is strange, and `data_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.

Last edited 5 years ago by tscrim (previous) (diff)

### comment:16 Changed 5 years ago by jmantysalo

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 5 years ago by tscrim

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 5 years ago by git

• 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 5 years ago by jmantysalo

• 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 5 years ago by jmantysalo

• Status changed from positive_review to needs_work

### comment:21 Changed 5 years ago by tscrim

• Status changed from needs_work to positive_review

I just forgot to set it back. Thanks!

### comment:22 Changed 5 years ago by vbraun

• Branch changed from public/graphs/orientations_iter-21415 to ce4841826cdcc83a1b88d17f3d3a62d8a8f4b1c3
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.