#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: |
Description (last modified by )
Adding reverse_edge() function to DiGraph?
Apply:
Attachments (6)
Change History (49)
comment:1 Changed 10 years ago by
- Reviewers set to gmoose05
Changed 9 years ago by
comment:2 Changed 9 years ago by
comment:3 Changed 9 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:4 Changed 9 years ago by
- Description modified (diff)
comment:5 Changed 9 years ago by
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 9 years ago by
comment:6 Changed 9 years ago by
- Status changed from needs_review to positive_review
comment:7 Changed 9 years ago by
- Cc dcoudert added
- Description modified (diff)
- Status changed from positive_review to needs_work
Hello,
this patch is interesting, but further improvements are needed:
- Use self.copy() instead of copy(self), and don't import copy.
- You must add optional parameter
inplace=False
allowing to perform changes inside the input digraph. This is particularly important forreverse_edges
since the current implementation performs as many digraph copies as the number of edges to reverse. This is not good at all. So thereverse_edge
function should start with:tempG = self if inplace else self.copy()
And thereverse_edges
function must always called thereverse_edge
withinplace=True
. - 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 9 years ago by
- 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 9 years ago by
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 9 years ago by
- Cc ncohen added
comment:11 follow-up: ↓ 15 Changed 9 years ago by
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
comment:12 Changed 9 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
comment:13 follow-up: ↓ 14 Changed 9 years ago by
Following David Coudert's comment,
- I replaced copy(self) with self.copy()
- I added optional parameter inplace=False
- 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 9 years ago by
Replying to egunawan:
Following David Coudert's comment,
- I replaced copy(self) with self.copy()
- I added optional parameter inplace=False
- 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 9 years ago by
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 9 years ago by
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: ↓ 18 Changed 9 years ago by
- Status changed from needs_review to needs_work
comment:18 in reply to: ↑ 17 Changed 9 years ago by
Replying to dcoudert:
- 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)
- reverse_edge raises an error if input edge u,v doesn't exist.
- the last comment about reverse_edges.
comment:19 Changed 9 years ago by
- Status changed from needs_work to needs_review
comment:20 follow-ups: ↓ 21 ↓ 25 Changed 9 years ago by
- 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: ↓ 22 Changed 9 years ago by
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 9 years ago by
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: ↓ 24 Changed 9 years ago by
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 9 years ago by
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 9 years ago by
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: ↓ 27 Changed 9 years ago by
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 9 years ago by
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 9 years ago by
- Status changed from needs_work to needs_review
comment:29 follow-up: ↓ 31 Changed 9 years ago by
- 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 withmultiedges = None
, then an exception is raised "You have a choice to make there !". This can only be done ifmultiedges = True
(in which case there will be two edges(2,1)
) ormultiedges = 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 theedge
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
comment:30 Changed 9 years ago by
- 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 9 years ago by
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 9 years ago by
Apply trac_13440-reverse-edge.patch
comment:33 follow-up: ↓ 34 Changed 9 years ago by
- 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 9 years ago by
comment:34 in reply to: ↑ 33 Changed 9 years ago by
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 9 years ago by
comment:35 Changed 9 years ago by
- Description modified (diff)
comment:36 Changed 9 years ago by
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 9 years ago by
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 9 years ago by
- Status changed from needs_review to positive_review
comment:39 Changed 9 years ago by
Great! Thanks again for all your help.
Best wishes, Gregg
comment:40 Changed 9 years ago by
Yeahhhhhhhhhhhhhhhhhh !
Nathann
comment:41 Changed 9 years ago by
- Milestone changed from sage-5.7 to sage-5.8
comment:42 Changed 9 years ago by
- Merged in set to sage-5.8.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
comment:43 Changed 9 years ago by
- Keywords sd40 added
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.