Iterator over all orientations of a graph

[tscrim]

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

CC: @jm58660

Component: graph theory

Author: Travis Scrimshaw

Branch/Commit: ce48418

Reviewer: Jori Mäntysalo

Issue created by migration from https://trac.sagemath.org/ticket/21415

[tscrim]

comment:1

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')

[jm58660]

comment:2

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.

[jm58660]

comment:3

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()?

[tscrim]

comment:4

orientations is probably better. I was thinking of actually making one function for the iterator and one for the list. What do you think?

[tscrim]

comment:5

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

[jm58660]

comment:6

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.

[sagetrac-tmonteil]

comment:7

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.

[dcoudert]

comment:8

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.

[tscrim]

Commit: 44e925f

[tscrim]

Author: Travis Scrimshaw

[tscrim]

Branch: public/graphs/orientations_iter-21415

[tscrim]

comment:9

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.

[jm58660]

comment:10

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

[tscrim]

comment:11

Replying to @jm58660:

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

[jm58660]

comment:12

Replying to @tscrim:

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

[jm58660]

Reviewer: Jori Mäntysalo

[sagetrac-git]

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

5e46a14

Addressing reviewer comments.

[sagetrac-git]

Changed commit from 44e925f to 5e46a14

[sagetrac-git]

Changed commit from 5e46a14 to 253347e

[sagetrac-git]

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

253347e

Adding another test and using Python3 next.

[tscrim]

comment:15

Replying to @jm58660:

Replying to @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.

[jm58660]

comment:16

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.

[tscrim]

comment:17

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.

[sagetrac-git]

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

ce48418

Fixing loops and documenting multiple edges behavior.

[sagetrac-git]

Changed commit from 253347e to ce48418

[jm58660]

comment:19

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.

[tscrim]

comment:21

I just forgot to set it back. Thanks!

[vbraun]

Changed branch from public/graphs/orientations_iter-21415 to ce48418