Opened 7 years ago

Closed 7 years ago

Last modified 6 years ago

#13440 closed enhancement (fixed)

Adding reverse_edge() function to DiGraph

Reported by: egunawan Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.8
Component: graph theory Keywords: digraph, sd40
Cc: gmoose05, dcoudert, ncohen Merged in: sage-5.8.beta0
Authors: Emily Gunawan Reviewers: Gregg Musiker, Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Attachments (6)

trac13440-reverse-edge.patch (5.7 KB) - added by egunawan 7 years ago.
trac_13440-rev_edge-gm.patch (5.7 KB) - added by gmoose05 7 years ago.
trac_13440-rev_edge-gm (6.5 KB) - added by egunawan 7 years ago.
Ignore other attachments
trac_13440-reverse-edge.patch (13.5 KB) - added by egunawan 7 years ago.
Modified reverse_edge and reverse_edges methods per Nathann's comments
trac_13440-review.patch (20.1 KB) - added by ncohen 7 years ago.
trac_13440-second-review.patch (2.0 KB) - added by gmoose05 7 years ago.

Download all attachments as: .zip

Change History (49)

comment:1 Changed 7 years ago by egunawan

  • Reviewers set to gmoose05

Changed 7 years ago by egunawan

comment:2 Changed 7 years ago by egunawan

Regarding trac13440-reverse-edge.patch (the second patch attached on Nov 28): Emily: edge_label() takes two parameters only, the in-edge and out-vertex, but it returns a list if the digraph allows multiedges and returns a single value if the digraph does not allow multiedges, so I put two separate cases for multiedge digraph and single-edge digraph.

Gregg: - One other small comment: I would add one or two more examples to include other cases such as weighted graphs, with parallel edges, with examples where the input is a 3-tuple rather than a 2-tuple, just to cover the cases the method can handle.

Emily: What does it mean when weighted = True? I think it means something other than allowing edges to have labels? I added some examples/ tests for digraph where weighted = True anyway in this patch.

comment:3 Changed 7 years ago by gmoose05

  • Description modified (diff)
  • Status changed from new to needs_review

comment:4 Changed 7 years ago by gmoose05

  • Description modified (diff)

comment:5 Changed 7 years ago by gmoose05

New patch added (supersedes old patches). Some syntax issues with EXAMPLES and other tiny changes. Thanks to Hugh Thomas for catching some of these.

Changed 7 years ago by gmoose05

comment:6 Changed 7 years ago by gmoose05

  • Status changed from needs_review to positive_review

comment:7 Changed 7 years ago by dcoudert

  • Cc dcoudert added
  • Description modified (diff)
  • Status changed from positive_review to needs_work

Hello,

this patch is interesting, but further improvements are needed:

  1. Use self.copy() instead of copy(self), and don't import copy.
  2. You must add optional parameter inplace=False allowing to perform changes inside the input digraph. This is particularly important for reverse_edges since the current implementation performs as many digraph copies as the number of edges to reverse. This is not good at all. So the reverse_edge function should start with: tempG = self if inplace else self.copy() And the reverse_edges function must always called the reverse_edge with inplace=True.
  3. The documentation must be improved. Take a look at the add_edge method for instance. And also check the final layout.

Also, concerning trac:

  • You must put full names and not login for Author and Reviewer.
  • I have change the ticket to clarify the file to use
  • you should not add new files but overwrite old version if it is an improved version

comment:8 Changed 7 years ago by gmoose05

  • Authors changed from egunawan to Emily Gunawan
  • Reviewers changed from gmoose05 to Gregg Musiker

Dear David, Thank you for your feedback, and for editing the description to make it clearer which patch file to use. I have updated the author and reviewer names accordingly.

As for you point about overwriting old versions, for the most part we have been doing that, but for one such replacement, there was a small typo in the patch name that wasn't noticed until after the upload. Is there a mechanism to delete a patch off of trac or to still do a replacement after this? Thanks, Gregg

comment:9 Changed 7 years ago by dcoudert

Someone with admin rights can certainly do that (so not me). However, it is not a big issue. The most important is to ensure one can easily understand which file(s) to apply and in which order.

comment:10 Changed 7 years ago by ncohen

  • Cc ncohen added

comment:11 follow-up: Changed 7 years ago by ncohen

If I may express a personal opinion, I really think that adding methods that replace the two lines of code you have to write -- when you know the digraph you deal with -- is not really what we need right now, considering the length of the list of DiGraph?'s functions.... These methods spend more time checking the input (labelled ? Multigraph ?) than actually doing what they are asked to do, even do unnecessary operations (your code begins by checking that the edge given as an argument actually exists in the graph....).

And as usual when dealing with this mess of options, you have the usual corner-cases which have no good solution in general

Example :

sage: d = DiGraph()
sage: d.add_edge(1,2)
sage: d.add_edge(2,1)
sage: d.edges()
[(1, 2, None), (2, 1, None)]
sage: dd= d.reverse_edge((1,2)) 
sage: dd.edges()
[(2, 1, None)]

As there is no good way to fix this, it makes the function unreliable (you have no idea what the output could be unless you read the code) --> it is better (and faster) to rewrite your own than to use a method whose behaviour could be unexpected (also called : wrong). Like with the merge_* methods, and many others ....

Of course, it is just my personal opinion...

Nathann

Changed 7 years ago by egunawan

Ignore other attachments

comment:12 Changed 7 years ago by egunawan

  • Description modified (diff)
  • Status changed from needs_work to needs_review

comment:13 follow-up: Changed 7 years ago by egunawan

Following David Coudert's comment,

  1. I replaced copy(self) with self.copy()
  2. I added optional parameter inplace=False
  3. I haven't changed the style of previous documentation to one that is similar to add_edge documentation. I will discuss with Gregg Musiker.

comment:14 in reply to: ↑ 13 Changed 7 years ago by gmoose05

Replying to egunawan:

Following David Coudert's comment,

  1. I replaced copy(self) with self.copy()
  2. I added optional parameter inplace=False
  3. I haven't changed the style of previous documentation to one that is similar to add_edge documentation. I will discuss with Gregg Musiker.

The new documentation looks good to me. David, if you have further suggestions, we are all ears.

Gregg

comment:15 in reply to: ↑ 11 Changed 7 years ago by gmoose05

Replying to ncohen:

If I may express a personal opinion, I really think that adding methods that replace the two lines of code you have to write -- when you know the digraph you deal with -- is not really what we need right now, considering the length of the list of DiGraph?'s functions.... These methods spend more time checking the input (labelled ? Multigraph ?) than actually doing what they are asked to do, even do unnecessary operations (your code begins by checking that the edge given as an argument actually exists in the graph....).

And as usual when dealing with this mess of options, you have the usual corner-cases which have no good solution in general

Example :

sage: d = DiGraph()
sage: d.add_edge(1,2)
sage: d.add_edge(2,1)
sage: d.edges()
[(1, 2, None), (2, 1, None)]
sage: dd= d.reverse_edge((1,2)) 
sage: dd.edges()
[(2, 1, None)]

As there is no good way to fix this, it makes the function unreliable (you have no idea what the output could be unless you read the code) --> it is better (and faster) to rewrite your own than to use a method whose behaviour could be unexpected (also called : wrong). Like with the merge_* methods, and many others ....

Of course, it is just my personal opinion...

Nathann

I see some of your points Nathann regarding this ticket, however some users might still find it useful. I should mention that the main reason we decided to write this ticket was that reversal of a single edge or group of edges is a function that we will need to use over and over again in a future patch for the Cluster Algebra and Quiver package. We discussed this at Sage Days 40 and it appeared that other users present would also utilize this command, although I am not sure how many avid graphs sage developers were at this meeting. Also Ticket #7720 seemed to request a command for reversing an edge in place as well.

There are indeed a few more cases to deal with than we first anticipated, given the flexibility of inputs for digraphs, which made the code longer than we first thought it would be, but if the reverse_edge() method is called within another subroutine, breaking into such cases appear unavoidable anyway. Although we are open to suggestion.

As far as the issue "it makes the function unreliable" goes, the example you wrote out is not an issue with the reverse_edge() code but just a manifestation of the fact that the DiGraph? d being used does not allow multiple edges. For instance, d.add_edge(1,2); d.add_edge(1,2) would cause the same behavior. We now have an example in the documentation clarifying the expected output for the user.

In summary, given that this method will be needed for other sage code anyway, we were interested in getting the opinions from those developing the graphs code. Is it better to have reverse_edge() and reverse_edges() in digraph where they are methods for the digraph class, or as _reverse_edge() and _reverse_edges() as auxiliary commands in separate sage code?

Thanks, Gregg

comment:16 Changed 7 years ago by dcoudert

The reverse edge function should raise an error if one tries to reverse an edge that is not in the graph. The tempG line should be moved after the if.

Also, it would be convenient to accept G.reverse_edge(u,v,some_label,inplace=True) . See the G.add_edge function for more details on how to do this.

Then the reverse_edges should be like:

tempG = self if inplace else self.copy() 
for e in edges: 
    tempG.reverse_edge(e,inplace=True) 
if not inplace: 
    return tempG 

I think these methods are useful, although the behavior is not perfect. But as long as the documentation is clear...

I let Nathann answered other comments.

comment:17 follow-up: Changed 7 years ago by dcoudert

  • Status changed from needs_review to needs_work

comment:18 in reply to: ↑ 17 Changed 7 years ago by egunawan

Replying to dcoudert:

  1. reverse_edge now takes input parameters the way add_edge does (with optional inplace parameter, but 'inplace=True' or 'inplace=False' has to be specified)
  2. reverse_edge raises an error if input edge u,v doesn't exist.
  3. the last comment about reverse_edges.

comment:19 Changed 7 years ago by egunawan

  • Status changed from needs_work to needs_review

comment:20 follow-ups: Changed 7 years ago by dcoudert

  • Status changed from needs_review to needs_work

Not working for digraphs with labels on edges

sage: d = digraphs.Circuit(6)
sage: d.reverse_edges(d.edges()).edges()
[(0, 5, None),
 (1, 0, None),
 (2, 1, None),
 (3, 2, None),
 (4, 3, None),
 (5, 4, None)]
sage: d = digraphs.Kautz(2,3)
sage: d.reverse_edges(d.edges()).edges()
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-15-99c7e6f964ef> in <module>()
----> 1 d.reverse_edges(d.edges()).edges()

/home/dcoudert/Soft/sage-5.7.beta2/local/lib/python2.7/site-packages/sage/graphs/digraph.pyc in reverse_edges(self, edges, inplace)
   1997         tempG = self if inplace else self.copy()
   1998         for e in edges:
-> 1999             tempG.reverse_edge(e,inplace=True)
   2000         if not inplace:
   2001             return tempG

/home/dcoudert/Soft/sage-5.7.beta2/local/lib/python2.7/site-packages/sage/graphs/digraph.pyc in reverse_edge(self, u, v, label, inplace)
   1943         
   1944         if not self.has_edge(u,v,label):
-> 1945             raise ValueError, "Input edge must exist in the digraph."
   1946            
   1947         tempG = self if inplace else self.copy() 

ValueError: Input edge must exist in the digraph.

comment:21 in reply to: ↑ 20 ; follow-up: Changed 7 years ago by egunawan

In Kautz digraph example, one of the edges, ('101', '010', '0'), was deleted by reverse_edge because Kautz does not allow parallel edges:

sage: d = digraphs.Kautz(2,3)
sage: d.allows_multiple_edges()
False
sage: d.has_edge('101', '010', '0')
True
sage: d.has_edge('010', '101', '1')
True
sage: d.reverse_edge('010', '101', '1', inplace=True)
sage: d.has_edge('101', '010', '0')
False
sage: d.has_edge('101', '010', '1')
True


Replying to [comment:20 dcoudert]:
> Not working for digraphs with labels on edges

comment:22 in reply to: ↑ 21 Changed 7 years ago by egunawan

Should I change the code to change digraph self to allow parallel edges? Thank you.

When the Kautz digraph is defined to allow parallel edges, reverse_edges() and reverse() both return a digraph with the same edges:

sage: d = digraphs.Kautz(2,3)
sage: d1 = DiGraph({}, multiedges=True)
sage: d1.add_edges(d.edges())
sage: d1r = d1.reverse_edges(d1.edges())
sage: d.reverse().edges() == d1r.edges()
True

comment:23 follow-up: Changed 7 years ago by dcoudert

That's right!

Could you check the documentation (sage -docbuild reference html)

/pathtosage/sage-5.7.beta2/local/lib/python2.7/site-packages/sage/graphs/digraph.py:docstring of sage.graphs.digraph.DiGraph.reverse_edge:26: WARNING: Literal block expected; none found.
/pathtosage/sage-5.7.beta2/local/lib/python2.7/site-packages/sage/graphs/digraph.py:docstring of sage.graphs.digraph.DiGraph.reverse_edge:36: WARNING: Literal block expected; none found.
/pathtosage/sage-5.7.beta2/local/lib/python2.7/site-packages/sage/graphs/digraph.py:docstring of sage.graphs.digraph.DiGraph.reverse_edge:50: WARNING: Literal block expected; none found.
/pathtosage/sage-5.7.beta2/local/lib/python2.7/site-packages/sage/graphs/digraph.py:docstring of sage.graphs.digraph.DiGraph.reverse_edge:70: WARNING: Literal block expected; none found.
/pathtosage/sage-5.7.beta2/local/lib/python2.7/site-packages/sage/graphs/digraph.py:docstring of sage.graphs.digraph.DiGraph.reverse_edge:82: WARNING: Literal block expected; none found.
/pathtosage/sage-5.7.beta2/local/lib/python2.7/site-packages/sage/graphs/digraph.py:docstring of sage.graphs.digraph.DiGraph.reverse_edges:14: WARNING: Literal block expected; none found.
/pathtosage/sage-5.7.beta2/local/lib/python2.7/site-packages/sage/graphs/digraph.py:docstring of sage.graphs.digraph.DiGraph.reverse_edges:25: WARNING: Literal block expected; none found.

You should also make the first line of comments of the methods looks like other sage methods (I know it's boring).

comment:24 in reply to: ↑ 23 Changed 7 years ago by egunawan

Replying to dcoudert:

Thank you for the reply. For reverse_edge (not reverse_edges), is the following behavior OK?

If ``self`` does not allow multiple edges (such as the following example),
        then function may delete the input edge::
       
            sage: D = DiGraph( [(1,2), (2,1)] )
            sage: D.edges()
            [(1, 2, None), (2, 1, None)]
            sage: re = D.reverse_edge(1,2)
            sage: re.edges()
            [(2, 1, None)]

comment:25 in reply to: ↑ 20 Changed 7 years ago by egunawan

Hi David,

To clarify my questions:
1. Inside reverse_edge() and reverse_edges() methods, should the input digraph be set to multiedges=true by default?
2. Should there be an optional parameter for whether these methods will set the input digraph to allow multiple edges? So maybe it would look like reverse_edge(self, u, v=None, label=None, inplace=False, change_to_allow_multiedges=False)

        If ``self`` does not allow multiple edges (such as the following example),
        then function currently will delete the input edge::
        
            sage: D = DiGraph( [(1,2), (2,1)] )
            sage: D.edges()
            [(1, 2, None), (2, 1, None)]
            sage: re = D.reverse_edge(1,2)
            sage: re.edges()
            [(2, 1, None)]

Thank you

comment:26 follow-up: Changed 7 years ago by dcoudert

Well, I'm not sure which is the best behavior but I don't like the idea of deleting an edge. So it could be better to set the flag to True when a multiedge is created.

Nathann is right when he said that the method cannot answer all expected behaviors. It will be different for flow problems than for orientation problems.

comment:27 in reply to: ↑ 26 Changed 7 years ago by egunawan

Methods now force digraph to allow parallel edges, unless you specify in parameter multiedges = False. I also fixed the formatting issue in documentation, and I think I made the first line of comments of the methods looks like other sage methods. Thanks

comment:28 Changed 7 years ago by egunawan

  • Status changed from needs_work to needs_review

comment:29 follow-up: Changed 7 years ago by ncohen

  • Description modified (diff)
  • Status changed from needs_review to needs_work

Hellooooooooo !

Several remarks :

  • By default we should have inplace = False, as this is how all graph methods (add_vertices, add_edges,delete_vertices/edges) currently behave.
  • The default multiedges = True is not a good behaviour. Just picture somebody reversing the edges of an oriented graph (i.e. a graph without 2-cycles). All these operations are totally neutral with respect to multiple edges, and meanwhile the graph would be set to allow multiple edges for no reason at all. I think that the default should be multiedges = False, but that is not a good idea either. I think that the best behaviour is to say "unless the user explicitely told me what he wants to do let's not do things he may not want to see happen". Here's how it can be implemented.
  • By default, multiedges = None.

If (2,1) is to be reversed and (1,2) exists with multiedges = None, then an exception is raised "You have a choice to make there !". This can only be done if multiedges = True (in which case there will be two edges (2,1)) or multiedges = False (in which case the edge (1,2) will be removed).

Note that there is another problem with that :

sage: D = DiGraph( [(1,2,None), (2,1,"label")] )
sage: D.edges()
[(1, 2, None), (2, 1, 'label')]
sage: D.reverse_edge(2, 1, 'label', multiedges = False)

This should not be possible because *even though there is no edge (1,2,label)* it is impossible to reverse edge (2,1) without destroying some information :

sage: D = DiGraph( [(1,2,None), (2,1,"label")] )
sage: D.edges()
[(1, 2, None), (2, 1, 'label')]
sage: D.add_edge(1,2,'hey')
sage: D.edges()
[(1, 2, 'hey'), (2, 1, 'label')]

So this should also raise an exception unless the graph allows multiple edges already, or unless the user explicely said multiedges = True (in which case the graph will be set to allow multiple edges anyway)

  • In the documentation, edge is not an input of the methods, so it is a bit weird to see it appear in the list. The list of "accepted forms" is sufficient, so I guess that the edge entry can be removed, as it's rather confusing.
  • The output of these methods is not always a digraph, but that's what the OUTPUT section says.

Nathann

Changed 7 years ago by egunawan

Modified reverse_edge and reverse_edges methods per Nathann's comments

comment:30 Changed 7 years ago by egunawan

  • Status changed from needs_work to needs_review

Modified reverse_edge and reverse_edges methods per Nathann's comments http://trac.sagemath.org/sage_trac/ticket/13440#comment:29

comment:31 in reply to: ↑ 29 Changed 7 years ago by egunawan

Thank you for the comments. I modified the methods accordingly in the latest patch that I've attached.

I assumed that you meant to write that we should have inplace = True (not inplace = False as you wrote above) as this is how all graph methods (add_vertices, add_edges,delete_vertices/edges) currently behave. Is that true? Please correct me if that was not a typo. Thank you.

Replying to ncohen:

  • By default we should have inplace = False, as this is how all graph methods (add_vertices, add_edges,delete_vertices/edges) currently behave.

comment:32 Changed 7 years ago by ncohen

Apply trac_13440-reverse-edge.patch

comment:33 follow-up: Changed 7 years ago by ncohen

  • Description modified (diff)
  • Reviewers changed from Gregg Musiker to Gregg Musiker, Nathann Cohen

Hellooooooooooooooooooooooooooooooooooooo !!

Well... Here is a patch (to be added on top of yours) that does several modifications:

  • When it does not make code harder to read, we try to keep lines of code and documentation to a maximum length of 80 characters. I have no idea why and I find that stupid, but people throw stones at you otherwise.
  • Added some backticks around python keywords.
  • Changed some explanations in the documentation
  • Removed trailing whitespaces (we don't like that. At least that's what I've been told.

I also changed some part of the method's behaviour, so tell me what you think of it : my understanding is that setting "multiedges" to False means "I'm ok with loss of information". Besides, here's the current behaviour of add_edge in a graph with labels on the edges :

sage: g = Graph()           
sage: g.add_edge(1,2,'label')
sage: g.edges()
[(1, 2, 'label')]
sage: g.add_edge(1,2,'labelllllll')
sage: g.edges()                    
[(1, 2, 'labelllllll')]

So I thought that it would make more sense, when multiedges = False, to overwrite the label of edge (1,2) when (2,1) is to be reversed. Here's an example I added in the docstring :

Note that in the following graph, specifying ``multiedges = False`` will                                                                                                               
result in overwriting the label of `(1,2)` with the label of `(2,1)`::                                                                                                                 
                                                                                                                                                                                               
    sage: D = DiGraph( [(1, 2, 'B'), (2, 1,'A'), (2, 3, None)] )                                                                                                                       
    sage: D.edges()                                                                                                                                                                    
    [(1, 2, 'B'), (2, 1, 'A'), (2, 3, None)]                                                                                                                                           
    sage: D.reverse_edge(2,1, multiedges=False)                                                                                                                                        
    sage: D.edges()                                                                                                                                                                    
    [(1, 2, 'B'), (2, 3, None)]    

What do you think of it ?

If you agree with this second patch (and as I agree with yours), you can set this ticket to positive_review :-)

And thank you for this patch... Even if I first complained about it. It's good that it made me think a bit about the kind of functions a software like Sage should contain :-)

Nathann

Changed 7 years ago by ncohen

comment:34 in reply to: ↑ 33 Changed 7 years ago by egunawan

Thank you very much for the modifications. I agree with this second patch. After Gregg looks at it, if he doesn't have more comments he can set this ticket to positive review.

Changed 7 years ago by gmoose05

comment:35 Changed 7 years ago by gmoose05

  • Description modified (diff)

comment:36 Changed 7 years ago by gmoose05

Dear Nathann, Emily, and David,

Greetings from Sage Days 45. Thank you again Nathann for the review patch, these modifications looked great to me! Looking over it this evening, I found a few small issues, but I fixed them and uploaded them as a second review patch. I'll wait for you to get a chance to take a look but barring any further issues, I am also ready for a positive review.

Just to summarize my changes:

i) inplace=True is the default so Fixed this typo in the Examples,

ii) In the example

 Note that in the following graph, specifying ``multiedges = False`` will
 result in overwriting the label of `(1,2)` with the label of `(2,1)`::

       sage: D = DiGraph( [(1, 2, 'B'), (2, 1,'A'), (2, 3, None)] )
       sage: D.edges()
       [(1, 2, 'B'), (2, 1, 'A'), (2, 3, None)]
       sage: D.reverse_edge(2,1, multiedges=False)
       sage: D.edges()
       [(1, 2, 'B'), (2, 3, None)]

the computational behavior differed from the description. (By the way, I also like the choice to overwrite the label.) This alerted me to small typo in the code (in the multiedges=False) case. This code and the example are now fixed.

Gregg

comment:37 Changed 7 years ago by ncohen

GLoooooooooooppppsss. You are totally right !

Well, if everybody agrees with this we can set the ticket to positive_review ? I'm all for it :-)

Nathann

comment:38 Changed 7 years ago by gmoose05

  • Status changed from needs_review to positive_review

comment:39 Changed 7 years ago by gmoose05

Great! Thanks again for all your help.

Best wishes, Gregg

comment:40 Changed 7 years ago by ncohen

Yeahhhhhhhhhhhhhhhhhh !

Nathann

comment:41 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.7 to sage-5.8

comment:42 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.8.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:43 Changed 6 years ago by gmoose05

  • Keywords sd40 added
Note: See TracTickets for help on using tickets.