#7304 closed enhancement (fixed)
Contract edge in graph
Reported by:  AJonsson  Owned by:  rlm 

Priority:  major  Milestone:  sage8.0 
Component:  graph theory  Keywords:  
Cc:  brunellus, lkeough, dcoudert, tscrim, Stefan, yomcat  Merged in:  
Authors:  Zach Gershkoff  Reviewers:  Tom Boothby, David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  6f2a583 (Commits)  Commit:  
Dependencies:  #23290  Stopgaps: 
Description
This patch contract an edge (u,v) in a graph. In the resulting graph vertex u is merged into vertex v.
The variables u and v can be passed as variables, a tuple (u,v) or a 3tuple (u,v,'label'). The last allows us to use an element from G.edges() for contraction.
Attachments (2)
Change History (94)
Changed 10 years ago by
comment:1 Changed 10 years ago by
 Status changed from new to needs_review
 Type changed from defect to enhancement
comment:2 followup: ↓ 6 Changed 10 years ago by
 Resolution set to duplicate
 Status changed from needs_review to closed
Duplicate of #7159 . That ticket is about vertex merging, but it is basically the same thing.
comment:3 Changed 10 years ago by
 Milestone changed from sage4.2.1 to sageduplicate/invalid/wontfix
comment:4 Changed 10 years ago by
 Milestone changed from sageduplicate/invalid/wontfix to sage4.2.1
 Resolution duplicate deleted
 Status changed from closed to new
On second thought, reopening.
Merging vertices gives a slightly different result for certain cases that are important in deletioncontraction algorithms, so this function has a place to fill as well.
Example of case that contract_edge() handles differently:
If we have two vertices A, B, with two parallel edges between them, a merging of A and B results in a single vertex with no edge or loops. If we instead choose to contract one of the two parallel edges (and allow loops), we will end up with a single vertex which has a loop.
comment:5 Changed 10 years ago by
 Status changed from new to needs_review
comment:6 in reply to: ↑ 2 ; followup: ↓ 7 Changed 10 years ago by
Replying to AJonsson:
Duplicate of #7159 . That ticket is about vertex merging, but it is basically the same thing.
Anders, please don't close tickets. That's the job of the release manager. See this section of the Developer's Guide for conventions on closing tickets.
comment:7 in reply to: ↑ 6 Changed 10 years ago by
Replying to mvngu:
Anders, please don't close tickets. That's the job of the release manager. See this section of the Developer's Guide for conventions on closing tickets.
Whoops. Hadn't seen that section. Won't happen again.
comment:8 followup: ↓ 10 Changed 10 years ago by
I understand your point, but do you think it useful to have 2 different functions to merge vertices, instead of having just one with more options ? It could be a bit confusing...
Nathann
comment:9 Changed 10 years ago by
 Status changed from needs_review to needs_info
comment:10 in reply to: ↑ 8 Changed 10 years ago by
Replying to ncohen:
I understand your point, but do you think it useful to have 2 different functions to merge vertices, instead of having just one with more options ? It could be a bit confusing...
Nathann
I don't feel too strongly about it. As long as full functionality exists, it matters little to me if it is in one or two functions.
comment:11 Changed 10 years ago by
My advice exactly !
Could you then write a patch to modify #7159 as soon as it will be merged ? You could also directly modify the trac ticket as it is not merged yet, but then we would be looking for someone else to review it, as for #7814...
As you said, I do not mind as long as the two behaviours exist.. If you think your version of merging should be the default one, it's up to you ! :)
comment:12 Changed 10 years ago by
 Status changed from needs_info to needs_work
Ok, will look closer into a modification of #7159 to be added after that ticket has been merged to Sage.
comment:13 followup: ↓ 14 Changed 10 years ago by
 Report Upstream set to N/A
should we keep this ticket open, or close it and open a new one with your modification of #7159 ?
comment:14 in reply to: ↑ 13 Changed 10 years ago by
 Summary changed from [With patch, needs review] Contract edge in graph to Contract edge in graph
comment:15 Changed 10 years ago by
comment:16 Changed 9 years ago by
There's a spam link above here that needs removing.
As a matroid theorist, I look at deletion and contraction a bit differently. It bothers me that I cannot write something along the lines of
H = G.delete((1,2)).contract([(3,5),(6,7)])
without modifying G.
comment:17 Changed 9 years ago by
What would your code do ? Are your pairs edges or vertices ? Right now your have a merge_vertices commands in Graph that lets you contract any set of vertices.
Nathann
comment:18 followup: ↓ 19 Changed 9 years ago by
My pairs would be edges. In an even more ideal world, I would refer to them by their labels. For comparison, if M is a matroid with elements 'e', 'f', 'g', I currently have some experimental code allowing me to write
N = M / e? \ ['f', 'g']
resulting in the matroid with e contracted and f,g deleted. From a matroidtheoretic point of view, if you contract an edge, all edges parallel to it should turn into loops. The current merge_vertices doesn't do that, even if I call G.allow_loops(True) first. With this behavior, contracting a loop should probably equal deleting a loop.
Anyway, my main point is that I feel there should be methods for deletion and contraction that return a new graph, rather than modifying the graph itself.
Real use case: the other day I was wondering about maximal planar subgraphs of a small graph G. In that case you want to explore: first delete edge 'e', then delete edge 'f', then 'f' and 'g', then 'f' and 'h', and finally only edge 'h'. The current implementation makes such exploration of minors a bit cumbersome: you frequently make copies of G, which you then modify.
comment:19 in reply to: ↑ 18 Changed 9 years ago by
Anyway, my main point is that I feel there should be methods for deletion and contraction that return a new graph, rather than modifying the graph itself.
Would you be interested in mixing the two ? Like sometimes calling a delete_edge function which returns a graph, and some other times a method which modifies the graph ?
The current behaviour is necessary for many functions, and replacing it would mean a huge loss in efficiency. It is possible to add a keyword to all those methods so that a graph will be returned instead of modifying the current graph. I don't quite like this, as it would mean some additional tests for each of all those very fundamental functions, but then again...
On the other hand, if you are not interested in mixing the two type of operations, perhaps the best is to work on an immutable graph class. Many people have asked this already, and when working on an immutable graph class having a default behaviour of "returning an immutable copy of the graph modified as requested" does not seem too unnatural. What about this then ? :)
Nathann
comment:20 followups: ↓ 21 ↓ 22 Changed 9 years ago by
I'm not at all in favor of having two different behaviors encoded in one function. One option would be to implement the div and _backslash_ operators to do, respectively, contraction and deletion without changing the object.
comment:21 in reply to: ↑ 20 Changed 9 years ago by
I'm not at all in favor of having two different behaviors encoded in one function. One option would be to implement the div and _backslash_ operators to do, respectively, contraction and deletion without changing the object.
Got it !
This being said, I understand that's how matroid theory is written "on the paper", but do you think it would be possible to write useful code using only those symbols when any of them means copying the whole structure ? But perhaps I do not know how you intend to code it, and how much such operations could cost in memory and time ...
Nathann
comment:22 in reply to: ↑ 20 ; followup: ↓ 23 Changed 9 years ago by
Replying to Stefan:
I'm not at all in favor of having two different behaviors encoded in one function.
This is often the case. For example many graph functions in Sage have an inplace
option, which provides exactly this choice.
comment:23 in reply to: ↑ 22 Changed 9 years ago by
Replying to rlm:
Replying to Stefan:
I'm not at all in favor of having two different behaviors encoded in one function.
This is often the case. For example many graph functions in Sage have an
inplace
option, which provides exactly this choice.
Indeed it does! I'm not sure that this happens often, but so far I found subgraph() and relabel(). The former defaults to inplace=False; the latter defaults to inplace=True.
In that case it would be preferable not to have extra methods (the list is quite long enough as it stands). Defining the forward and backslashes might still be a neat addition.
Nathann, typical work with matroids is on relatively small ground sets. I don't expect intensive calculations on graphs with more than, say, a few dozen edges. We would wrap the graph in a GraphicMatroid? object anyway, so it's easy to compensate for any functionality in the graph code that is not entirely fit for our purpose. So you need not worry about our needs for the time being.
What remains is the question of contracting one edge from a parallel pair (see above).
comment:24 Changed 8 years ago by
 Cc brunellus added
 Status changed from needs_work to needs_review
So, what do you say to my patch? It provides
 loops handling (see #9807)
contract_edge
option
inplace
option
comment:25 Changed 8 years ago by
 Dependencies set to #7304
comment:26 Changed 8 years ago by
 Dependencies changed from #7304 to #9362
comment:27 Changed 8 years ago by
Apply trac_7304_contract_edge.patch
(for patchbot)
comment:28 Changed 8 years ago by
Brunellus,
This isn't quite there, and you haven't tested everything.
Graphs have a copy method  g = g.copy()
is faster than g=copy(g)
. There are two problems with the block
if vertices and vertices[0] is None: vertices[0] = g.add_vertex()
first off, this assumes that g.add_vertex()
returns the label of the added vertex. It does not. Second, it modifies vertices
for no good reason (what if the users passes in a tuple, set, or generator?)
comment:29 Changed 8 years ago by
 Reviewers set to Tom Boothby
 Status changed from needs_review to needs_work
comment:30 Changed 8 years ago by
Ah, I see that g.add_vertex() indeed returns the label for the current alpha of 5.0. Please update this to not modify the users's input with
vertices = list(vertices)
and use g.copy()
instead of copy, and I'll give this a positive review.
comment:31 Changed 8 years ago by
Thanks for the review! I will update the patch right now.
Changed 8 years ago by
comment:32 Changed 8 years ago by
 Status changed from needs_work to needs_review
comment:33 Changed 8 years ago by
 Cc lkeough added
comment:34 Changed 8 years ago by
I have been working on getting the Tutte polynomial into Sage (#1314). The Tutte polynomial needs contraction with keeping any resulting multiedges and loops (but removing the edge you contracted). It seems your code does this if you allow multiedges and loops and use the contract_edge feature.
I think they may have had this discussion above, but I can't tell what was concluded: Would adding an option like "simplegraph = True" be a reasonable thing to do?
comment:35 Changed 8 years ago by
Please fill in your real name as Author.
comment:36 Changed 7 years ago by
 Status changed from needs_review to needs_info
Ok.... Which is the patch that needs to be reviewed ? Is it trac_7304_contract_edge.patch ?
Nathann
comment:37 Changed 6 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:38 Changed 6 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:39 Changed 6 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:40 Changed 5 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:41 Changed 3 years ago by
 Branch set to u/zgershkoff/contract_edge_in_graph
comment:42 Changed 3 years ago by
 Cc dcoudert tscrim Stefan yomcat added
 Commit set to 6df8bdc98331cd415bc070dcb8800e56164cc1e6
 Status changed from needs_info to needs_review
I ended up writing some new methods for edge contraction. I didn't use either patch here. The first one didn't seem to respect edge labels, and allow_loops_multiedges
seems redundant since these are intrinsic to the graph, and the second one seemed too complicated to disentangle from merge_vertices
. I also didn't include an inplace
option for consistency with delete_edge
.
The contract_edges()
method was tough because if the user inputs a list of edges, the vertices need to be updated dynamically as the contractions occur and vertices are lost. I ended up using nested while loops to accomplish this. Maybe there's a faster way?
New commits:
6df8bdc  wrote new contract_edge() and contract_edges() methods

comment:43 Changed 3 years ago by
 Commit changed from 6df8bdc98331cd415bc070dcb8800e56164cc1e6 to aa2690391fd4414420ad01d139001fc503376ada
Branch pushed to git repo; I updated commit sha1. New commits:
aa26903  typo in documentation

comment:44 Changed 3 years ago by
 Commit changed from aa2690391fd4414420ad01d139001fc503376ada to dbb7ff70ec56905ea7c24d1063c770d0b40b2173
Branch pushed to git repo; I updated commit sha1. New commits:
dbb7ff7  input sanitizing + added test

comment:45 Changed 3 years ago by
 Commit changed from dbb7ff70ec56905ea7c24d1063c770d0b40b2173 to 028505636ecf15db5586d15d04e02d0e9c21adf8
Branch pushed to git repo; I updated commit sha1. New commits:
0285056  test formatting

comment:46 Changed 3 years ago by
 Status changed from needs_review to needs_work
Let's wait until I speed up contract_edges()
.
comment:47 Changed 3 years ago by
 Commit changed from 028505636ecf15db5586d15d04e02d0e9c21adf8 to 944899fe4af9415ba5690c2ba8aa15d31e026108
Branch pushed to git repo; I updated commit sha1. New commits:
944899f  contract_edges using union find

comment:48 Changed 3 years ago by
 Commit changed from 944899fe4af9415ba5690c2ba8aa15d31e026108 to 676b63638cf7d4286f7df9611430db9491605149
Branch pushed to git repo; I updated commit sha1. New commits:
676b636  Made it shorter. Some doctests fail, pending #23290

comment:49 Changed 3 years ago by
 Dependencies changed from #9362 to #9362, #23290
 Status changed from needs_work to needs_review
For the sake of not having two implementations for the same thing, I adapted brunellus's earlier patch and rewrote contract_edge()
to use merge_vertices()
. This depends on #23290 to resolve a defect in merge_vertices()
.
comment:50 Changed 3 years ago by
 Commit changed from 676b63638cf7d4286f7df9611430db9491605149 to 9301125efecae5e4a78d5e02cc0332f501425b92
Branch pushed to git repo; I updated commit sha1. New commits:
9301125  Reduced number of calls to root() submethod

comment:51 Changed 3 years ago by
comment:52 followup: ↓ 54 Changed 3 years ago by
Some comments for contract_edges
:
 instead of dropping nonedges, it is better to not add such edge to the list
 construct the list of vertices at the same time to add edges to the list
 Instead of implementing your own disjoint set methods, you can use
DisjointSet
 If you use
DS = DisjointSet(...)
, you can useDS.root_to_elements_dict()
instead ofvertices = [v for v in vertices if v!= destination[v]]
comment:53 Changed 3 years ago by
 Commit changed from 9301125efecae5e4a78d5e02cc0332f501425b92 to 665f1dc4df118914a4ddcc64d76eb845bc511062
Branch pushed to git repo; I updated commit sha1. New commits:
665f1dc  More efficient building of vertex and edge iterables

comment:54 in reply to: ↑ 52 ; followup: ↓ 56 Changed 3 years ago by
Replying to dcoudert:
Some comments for
contract_edges
:
 instead of dropping nonedges, it is better to not add such edge to the list
 construct the list of vertices at the same time to add edges to the list
Done.
 Instead of implementing your own disjoint set methods, you can use
DisjointSet
 If you use
DS = DisjointSet(...)
, you can useDS.root_to_elements_dict()
instead ofvertices = [v for v in vertices if v!= destination[v]]
It's nice that sage already has an implementation of this algorithm, but I find it lacking. If I want a list of nonroots, I can do vertices = [v for v in vertices if (v not in DS.root_to_elements_dict() )]
, but there doesn't seem to be an analog to my root()
method. So at the end, when I need to know what the root of a vertex is, I don't see any easy way to do that if I'm using DisjointSet
.
comment:55 followup: ↓ 59 Changed 3 years ago by
There's another issue I've been considering: if a user has loops on but multiedges off, then iterated contraction with contract_edge()
will never create loops, but giving the same input as a list to contract_edges()
could create loops because it will bypass when the edges are in parallel. On one hand, it seems like it should be consistent, but on the other hand, if a user has loops on and multiedges off, I don't know what business they have contracting edges, so I don't know what their desired output would be.
comment:56 in reply to: ↑ 54 Changed 3 years ago by
It's nice that sage already has an implementation of this algorithm, but I find it lacking. If I want a list of nonroots, I can do
vertices = [v for v in vertices if (v not in DS.root_to_elements_dict() )]
, but there doesn't seem to be an analog to myroot()
method. So at the end, when I need to know what the root of a vertex is, I don't see any easy way to do that if I'm usingDisjointSet
.
vertices = [v for v in vertices if v != DS.find(v)]
should give you nonroots, no?
comment:57 Changed 3 years ago by
 Commit changed from 665f1dc4df118914a4ddcc64d76eb845bc511062 to 94aa44f6ea86e2a25510ebec6e7290d26b52779b
Branch pushed to git repo; I updated commit sha1. New commits:
94aa44f  using DisjointSet

comment:58 Changed 3 years ago by
Ah, right. I misread the description of that method.
comment:59 in reply to: ↑ 55 Changed 3 years ago by
Replying to zgershkoff:
There's another issue I've been considering: if a user has loops on but multiedges off, then iterated contraction with
contract_edge()
will never create loops, but giving the same input as a list tocontract_edges()
could create loops because it will bypass when the edges are in parallel. On one hand, it seems like it should be consistent, but on the other hand, if a user has loops on and multiedges off, I don't know what business they have contracting edges, so I don't know what their desired output would be.
This is the main difficulty with such method: what's the good answer? what is the user expected ? It is really application dependent. For instance, in some cases you want to contract an edge unless it creates a loop.
I would say that as long as the behavior is clearly documented, it's fine. If the user wants something else, he can code his own method.
One remark. You could use edges_incident.extend( self.outgoing_edges(v) )
instead of out_edges=self.edge_boundary([v])
. You can also use self.incoming_edges(v)
.
comment:60 Changed 3 years ago by
Thanks for the comments. I think if I use both self.incoming_edges(v)
and self.outgoing_edges(v)
then I will get loops on v
twice, so I'm leaving out_edges=self.edge_boundary([v])
as it is, but I will extend edges_incident
by self.incoming_edges(v)
.
comment:61 Changed 3 years ago by
 Commit changed from 94aa44f6ea86e2a25510ebec6e7290d26b52779b to bca2aad2ea72241adcbaa08e56a12d1e74210de3
Branch pushed to git repo; I updated commit sha1. New commits:
bca2aad  Improved documentation and directed case

comment:62 Changed 3 years ago by
 Commit changed from bca2aad2ea72241adcbaa08e56a12d1e74210de3 to a686c55681e31ab7237c9e2c18577b3ba6e0974d
Branch pushed to git repo; I updated commit sha1. New commits:
a686c55  Typo in documentation

comment:63 followups: ↓ 64 ↓ 66 Changed 3 years ago by
Another round of comments.
In method contract_edge
 in the
INPUT
block, some lines are forcontract_edges
and so should be removed from here.  remove the
OUTPUT
block. It is useless here  If I call
G.contract_edge( (u, v) )
and that the graph has edge(u, v, 'label')
, then the method will do nothing. Is this the behavior you expect? If so, it should be documented.  you may replace
for e in self.edges_incident(v):
withfor x,y,l in self.edges_incident(v):
. I don't know which option is the best.
In method contract_edges
:
 The first line is too long. Usually, the first line is short, and followed with a longer description
 Again the
OUTPUT
block is useless  in the
TESTS
block, you have an indentation problem  If we pass a list of 2tuples but that all edges of the graph have non
None
labels, nothing will happen. If it's expected behavior, it should be documented  after the
for e in edges:
loop, you should add a termination test likeif not edge_list: return
orif not edge_list or not vertices: return
out_edges=self.edge_boundary([v])
>out_edges = self.edge_boundary([v])
edges_incident = edges_incident + self.edges_incident(v)
>edges_incident.extend(self.edges_incident(v))
for (u, v, label) in edges_incident:
>for u, v, label in edges_incident:
.
comment:64 in reply to: ↑ 63 Changed 3 years ago by
Replying to dcoudert:
Another round of comments.
In method
contract_edge
 in the
INPUT
block, some lines are forcontract_edges
and so should be removed from here. remove the
OUTPUT
block. It is useless here If I call
G.contract_edge( (u, v) )
and that the graph has edge(u, v, 'label')
, then the method will do nothing. Is this the behavior you expect? If so, it should be documented.
I can't reproduce this. self.has_edge(u,v)
works the same as self.has_edge(u,v,None)
. It seems though the last edge it has in memory between u
and v
gets contracted.
sage: edgelist = [(0,1,0), (0,1,9), (0,1,2), (0,2,2), (1,2,3)] sage: G = Graph(edgelist, loops=True, multiedges=True) sage: G.contract_edge(0,1); G.edges() [(0, 0, 0), (0, 0, 9), (0, 2, 2), (0, 2, 3)] sage: edgelist = [(0,1,0), (0,1,2), (0,1,9), (0,2,2), (1,2,3)] sage: G = Graph(edgelist, loops=True, multiedges=True) sage: G.contract_edge(0,1); G.edges() [(0, 0, 0), (0, 0, 2), (0, 2, 2), (0, 2, 3)]
 you may replace
for e in self.edges_incident(v):
withfor x,y,l in self.edges_incident(v):
. I don't know which option is the best.
I changed it to x,y,l
for consistency.
Why is x,y,l
preferred over (x,y,l)
? I don't see anything about this in PEP8, but I've been using the parentheses around the tuple a lot because I think it's easier to read that way.
comment:65 Changed 3 years ago by
 Commit changed from a686c55681e31ab7237c9e2c18577b3ba6e0974d to 4c97d713e8d18d71f6a7d1b6496939fb80817f7e
comment:66 in reply to: ↑ 63 Changed 3 years ago by
I have a few more questions.
 Is
return
preferred overreturn None
? I've changed them to justreturn
.  Where is the indentation error in
contract_edges()
? Is it the space in front of some of the edges in the output? That matches the output, and it makes the html display correctly.  I've noticed that there are problems for
contract_edges()
if the input is a mix of 2tuples and 3tuples as the example below shows, but this is kind of a GIGO situation and I don't know if I should bother addressing it.
sage: edgelist = [(0,1,0), (0,1,1), (0,1,2)] sage: G = Graph(edgelist, loops=True, multiedges=True) sage: G.contract_edges([(0,1,2), (0,1)]); G.edges() [(0, 0, 0)] sage: G = Graph(edgelist, loops=True, multiedges=True) sage: G.contract_edges([(0,1), (0,1,2)]); G.edges() [(0, 0, 0), (0, 0, 1)]
comment:67 Changed 3 years ago by
 Commit changed from 4c97d713e8d18d71f6a7d1b6496939fb80817f7e to 0bdd5272076311e182fa4ac9beb56e4558278ee8
Branch pushed to git repo; I updated commit sha1. New commits:
0bdd527  raise exception if tuple lengths are inconsistent

comment:68 followup: ↓ 69 Changed 3 years ago by
Something has changed in the tests for method contract_edge
. Now we are loosing loops. I don't know why
sage: edgelist = [(0,0,'a'), (0,1,'b'), (1,1,'c')] sage: G = Graph(edgelist, loops=True, multiedges=True) sage: G.contract_edge(0,1,'b'); G.edges() [(0, 0, 'a')] sage: D = DiGraph(edgelist, loops=True, multiedges=True) sage: D.contract_edge(0,1,'b'); D.edges() [(0, 0, 'a')]
In contract_edges
:
*if not edges:
> if not edge_list:
 indentation of tests
With loops in a digraph::
comment:69 in reply to: ↑ 68 Changed 3 years ago by
Replying to dcoudert:
Something has changed in the tests for method
contract_edge
. Now we are loosing loops. I don't know why
I think I put those tests in before I rewrote contract_edge
to use merge_vertices
. Maybe it's irrelevant to have those tests there now. Now that uses merge_vertices
, it's dependent on #23290 to keep the loops. I should have been clearer about that, sorry.
In
contract_edges
: *if not edges:
>if not edge_list:
 indentation of tests
With loops in a digraph::
Yes, I see it now. I'll fix those shortly.
comment:70 Changed 3 years ago by
 Commit changed from 0bdd5272076311e182fa4ac9beb56e4558278ee8 to a77404f72f68416fa81af947dff29a5b95acb078
Branch pushed to git repo; I updated commit sha1. New commits:
35a7201  Tabs instead of spaces. I blame the editor.

412dc90  moved loops from vertices before the vertices get deleted

ff571d6  efficiency improvements; bug fix when input is [None]

a77404f  Merge branch 't/23290/ff571d6699ab233eedaf3b9d4a417ef6a1f6c56f' into t/7304/contract_edge_in_graph

comment:71 Changed 3 years ago by
I took the liberty of moving #23290 into this since it's closed. All tests pass now.
comment:72 followup: ↓ 73 Changed 3 years ago by
Right, better to rebase on top of #23290.
In method contract_edge
, I suggest the following change. Do you agree ?
if self.allows_loops() and (not self.has_edge(u, u) or self.allows_multiple_edges()): # add loops for (x, y, l) in self.edges_incident(v): if set([x, y]) == set([u, v]): self.add_edge(u, u, l)
In method contract_edges
 the test
if len(set([len(e) for e in edges])) > 1:
is fun ;) if self.has_edge((u, v, label)):
>if self.has_edge(u, v, label):
. This is to avoid guessing the format in methodhas_edge
.
comment:73 in reply to: ↑ 72 Changed 3 years ago by
Replying to dcoudert:
Right, better to rebase on top of #23290.
In method
contract_edge
, I suggest the following change. Do you agree ?if self.allows_loops() and (not self.has_edge(u, u) or self.allows_multiple_edges()): # add loops for (x, y, l) in self.edges_incident(v): if set([x, y]) == set([u, v]): self.add_edge(u, u, l)
I think sage will fail silently if multiedges are off, but it makes sense in principle to check first. I changed the order of the tests because I figured checking a boolean with self.allows_multiple_edges()
is probably faster than looking for an edge.
In method
contract_edges
 the test
if len(set([len(e) for e in edges])) > 1:
is fun ;)if self.has_edge((u, v, label)):
>if self.has_edge(u, v, label):
. This is to avoid guessing the format in methodhas_edge
.
That also makes sense.
comment:74 Changed 3 years ago by
 Commit changed from a77404f72f68416fa81af947dff29a5b95acb078 to 29dd861eef950472241a9866cedd56d4b6b4474a
Branch pushed to git repo; I updated commit sha1. New commits:
29dd861  efficiency improvements

comment:75 Changed 3 years ago by
It occurs to me that in contract_edge
, loops will never be created unless there are already multiedges. Thus we only need to check if multiedges are allowed once when adding loops.
comment:76 Changed 3 years ago by
Nevermind. A digraph can have two arcs in different directions between a pair of vertices and still have multiedges disabled, so contraction can create a loop. I suppose it's better like it is, since if there's already a loop at u
, it will always be kept with its original label now.
comment:77 Changed 3 years ago by
The patch looks good to me, but I'm wondering if we have taken all cases into account (functionality and/or tests)
comment:78 Changed 3 years ago by
 Commit changed from 29dd861eef950472241a9866cedd56d4b6b4474a to a4444882aef97b611da18172b0d04ebe1bde1977
Branch pushed to git repo; I updated commit sha1. New commits:
a444488  additional tests

comment:79 Changed 3 years ago by
 Commit changed from a4444882aef97b611da18172b0d04ebe1bde1977 to 438381446f2ab4ee75055e7282dbf75e94a5abae
Branch pushed to git repo; I updated commit sha1. New commits:
4383814  redundancy in tests

comment:80 Changed 3 years ago by
 Milestone changed from sage6.4 to sage8.0
I added tests for labeled edges, and for attempting to contract nonedges. I think that covers it.
comment:81 Changed 3 years ago by
Final comments (sorry for that).
For method contract_edge
:
 at the top of the
generic_graph.py
file, could you ensure that the description ofcontract_edge
is the same as in the method. I propose to put:Contract an edge from `u` to `v`
. Note that I useContract
and notContracts
.  Then in the method, split the first line to
Contract an edge from `u` to `v`
and then have a next paragraph withThis method returns silently if the edge does not exist.
For method contract_edges
:
 at the top of the
generic_graph.py
file, forcontract_edges
: useContract
instead ofContracts
 improve the alignment of paragraph
If `e` is an edge that is...
 In the
INPUT
block, ``edges``  a list...
> ``edges``  a list...
. You will certainly have to put the last word (edges) on the next line to be in 80 columns format.  In the
TESTS:
block, just beforeWith loops in a digraph::
, remove the empty::
block. I was not able to build the documentation and it took me a while to understand that it was caused by this::
stuff.  I'm not sure the empty line
....:
is useful. You can remove it.
I hope it's the last round of corrections ;)
comment:82 Changed 3 years ago by
 Commit changed from 438381446f2ab4ee75055e7282dbf75e94a5abae to 645c3e7bf8d011846fc6fcadd753200382414940
Branch pushed to git repo; I updated commit sha1. New commits:
645c3e7  Documentation fixes

comment:83 Changed 3 years ago by
 Commit changed from 645c3e7bf8d011846fc6fcadd753200382414940 to 50a884f5a8aa1af7448f15ed292c1c936788f0bd
Branch pushed to git repo; I updated commit sha1. New commits:
50a884f  a bit of extra whitespace...

comment:84 Changed 3 years ago by
Done. Thanks for walking me through it.
comment:85 Changed 3 years ago by
 Reviewers changed from Tom Boothby to Tom Boothby, David Coudert
You have used from 'u' to 'v'
with '
instead of `
. I think that `
is more appropriate. It is nicer in the documentation and it avoids confusion with string.
You have to do the correction both at the top of the file and at the beginning of contract_edge
.
After that you can set the ticket to positive review (or I will do it later).
Best,
comment:86 Changed 3 years ago by
 Commit changed from 50a884f5a8aa1af7448f15ed292c1c936788f0bd to 6f2a583a1705c1addb076c84479a693664ad058f
Branch pushed to git repo; I updated commit sha1. New commits:
6f2a583  proper demarcation of variables

comment:87 Changed 3 years ago by
 Status changed from needs_review to positive_review
I can't personally verify that the documentation builds correctly (perhaps an error with the beta I have installed), but doctests pass, so I'll take your word for it. Thanks for the review.
comment:88 Changed 3 years ago by
I checked and the documentation looks good. So we are done.
comment:89 Changed 2 years ago by
 Dependencies changed from #9362, #23290 to #23290
comment:90 Changed 2 years ago by
If you depend on a pregit ticket then the release script will never figure out that the dependencies are merged FYI
comment:91 Changed 2 years ago by
 Branch changed from u/zgershkoff/contract_edge_in_graph to 6f2a583a1705c1addb076c84479a693664ad058f
 Resolution set to fixed
 Status changed from positive_review to closed
comment:92 Changed 2 years ago by
 Commit 6f2a583a1705c1addb076c84479a693664ad058f deleted
Initial patch for review