Opened 3 years ago

Closed 3 years ago

#21415 closed enhancement (fixed)

Iterator over all orientations of a graph

Reported by: tscrim Owned by:
Priority: major Milestone: sage-7.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 3 years ago by tscrim

  • Cc jmantysalo added

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 3 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 3 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 3 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 3 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 3 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 3 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 3 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 3 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:

44e925fImplementing iterator over all orientations of a graph.
Last edited 3 years ago by tscrim (previous) (diff)

comment:10 follow-up: Changed 3 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 3 years ago by jmantysalo (previous) (diff)

comment:11 in reply to: ↑ 10 ; follow-up: Changed 3 years ago by tscrim

Replying to jmantysalo:

  • 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: Changed 3 years ago by jmantysalo

  • Reviewers set to Jori Mäntysalo

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.

comment:13 Changed 3 years ago by git

  • Commit changed from 44e925fa54823f18f3c4d39fba05ed2bb98874f4 to 5e46a141d339093286d8c25d0f7c59fe18a72168

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

5e46a14Addressing reviewer comments.

comment:14 Changed 3 years ago by git

  • Commit changed from 5e46a141d339093286d8c25d0f7c59fe18a72168 to 253347e51c6aa5cf87807b83cdde750bae902078

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

253347eAdding another test and using Python3 next.

comment:15 in reply to: ↑ 12 Changed 3 years ago by tscrim

Replying to jmantysalo:

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.

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

comment:16 Changed 3 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 3 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 3 years ago by git

  • Commit changed from 253347e51c6aa5cf87807b83cdde750bae902078 to ce4841826cdcc83a1b88d17f3d3a62d8a8f4b1c3

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

ce48418Fixing loops and documenting multiple edges behavior.

comment:19 Changed 3 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 3 years ago by jmantysalo

  • Status changed from positive_review to needs_work

comment:21 Changed 3 years ago by tscrim

  • Status changed from needs_work to positive_review

I just forgot to set it back. Thanks!

comment:22 Changed 3 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.