Opened 10 years ago

Closed 2 years ago

Last modified 2 years ago

#7304 closed enhancement (fixed)

Contract edge in graph

Reported by: AJonsson Owned by: rlm
Priority: major Milestone: sage-8.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 3-tuple (u,v,'label'). The last allows us to use an element from G.edges() for contraction.

Attachments (2)

trac_7304.patch (3.4 KB) - added by AJonsson 10 years ago.
Initial patch for review
trac_7304_contract_edge.patch (5.7 KB) - added by brunellus 8 years ago.

Download all attachments as: .zip

Change History (94)

Changed 10 years ago by AJonsson

Initial patch for review

comment:1 Changed 10 years ago by AJonsson

  • Status changed from new to needs_review
  • Type changed from defect to enhancement

comment:2 follow-up: Changed 10 years ago by AJonsson

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

  • Milestone changed from sage-4.2.1 to sage-duplicate/invalid/wontfix

comment:4 Changed 10 years ago by AJonsson

  • Milestone changed from sage-duplicate/invalid/wontfix to sage-4.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 deletion-contraction 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 AJonsson

  • Status changed from new to needs_review

comment:6 in reply to: ↑ 2 ; follow-up: Changed 10 years ago by mvngu

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 AJonsson

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 follow-up: Changed 10 years ago by 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

comment:9 Changed 10 years ago by ncohen

  • Status changed from needs_review to needs_info

comment:10 in reply to: ↑ 8 Changed 10 years ago by AJonsson

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 ncohen

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 AJonsson

  • 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 follow-up: Changed 10 years ago by ncohen

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

  • Summary changed from [With patch, needs review] Contract edge in graph to Contract edge in graph

Replying to ncohen:

should we keep this ticket open, or close it and open a new one with your modification of #7159 ?

Let's keep it open, otherwise we would just open an almost identical ticket. I will see if I get the time to finish the function sometime next week.

comment:16 Changed 9 years ago by Stefan

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 ncohen

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 follow-up: Changed 9 years ago by Stefan

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 matroid-theoretic 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 ncohen

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 follow-ups: Changed 9 years ago by Stefan

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 ncohen

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 ; follow-up: Changed 9 years ago by 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.

comment:23 in reply to: ↑ 22 Changed 9 years ago by Stefan

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 brunellus

  • Cc brunellus added
  • Status changed from needs_work to needs_review

So, what do you say to my patch? It provides

  1. loops handling (see #9807)
  2. contract_edge option
  3. inplace option

comment:25 Changed 8 years ago by brunellus

  • Dependencies set to #7304

comment:26 Changed 8 years ago by brunellus

  • Dependencies changed from #7304 to #9362

comment:27 Changed 8 years ago by davidloeffler

Apply trac_7304_contract_edge.patch

(for patchbot)

comment:28 Changed 8 years ago by boothby

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 boothby

  • Reviewers set to Tom Boothby
  • Status changed from needs_review to needs_work

comment:30 Changed 8 years ago by boothby

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 brunellus

Thanks for the review! I will update the patch right now.

Changed 8 years ago by brunellus

comment:32 Changed 8 years ago by brunellus

  • Status changed from needs_work to needs_review

comment:33 Changed 8 years ago by lkeough

  • Cc lkeough added

comment:34 Changed 8 years ago by lkeough

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 jdemeyer

Please fill in your real name as Author.

comment:36 Changed 7 years ago by ncohen

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

  • Milestone changed from sage-5.11 to sage-5.12

comment:38 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:39 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:40 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:41 Changed 3 years ago by zgershkoff

  • Branch set to u/zgershkoff/contract_edge_in_graph

comment:42 Changed 3 years ago by zgershkoff

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

6df8bdcwrote new contract_edge() and contract_edges() methods

comment:43 Changed 3 years ago by git

  • Commit changed from 6df8bdc98331cd415bc070dcb8800e56164cc1e6 to aa2690391fd4414420ad01d139001fc503376ada

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

aa26903typo in documentation

comment:44 Changed 3 years ago by git

  • Commit changed from aa2690391fd4414420ad01d139001fc503376ada to dbb7ff70ec56905ea7c24d1063c770d0b40b2173

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

dbb7ff7input sanitizing + added test

comment:45 Changed 3 years ago by git

  • Commit changed from dbb7ff70ec56905ea7c24d1063c770d0b40b2173 to 028505636ecf15db5586d15d04e02d0e9c21adf8

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

0285056test formatting

comment:46 Changed 3 years ago by zgershkoff

  • Status changed from needs_review to needs_work

Let's wait until I speed up contract_edges().

comment:47 Changed 3 years ago by git

  • Commit changed from 028505636ecf15db5586d15d04e02d0e9c21adf8 to 944899fe4af9415ba5690c2ba8aa15d31e026108

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

944899fcontract_edges using union find

comment:48 Changed 3 years ago by git

  • Commit changed from 944899fe4af9415ba5690c2ba8aa15d31e026108 to 676b63638cf7d4286f7df9611430db9491605149

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

676b636Made it shorter. Some doctests fail, pending #23290

comment:49 Changed 3 years ago by zgershkoff

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

  • Commit changed from 676b63638cf7d4286f7df9611430db9491605149 to 9301125efecae5e4a78d5e02cc0332f501425b92

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

9301125Reduced number of calls to root() submethod

comment:51 Changed 3 years ago by zgershkoff

  • Authors set to Zachary Gershkoff

comment:52 follow-up: Changed 3 years ago by dcoudert

Some comments for contract_edges:

  • instead of dropping non-edges, 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 use DS.root_to_elements_dict() instead of vertices = [v for v in vertices if v!= destination[v]]

comment:53 Changed 3 years ago by git

  • Commit changed from 9301125efecae5e4a78d5e02cc0332f501425b92 to 665f1dc4df118914a4ddcc64d76eb845bc511062

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

665f1dcMore efficient building of vertex and edge iterables

comment:54 in reply to: ↑ 52 ; follow-up: Changed 3 years ago by zgershkoff

Replying to dcoudert:

Some comments for contract_edges:

  • instead of dropping non-edges, 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 use DS.root_to_elements_dict() instead of vertices = [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 non-roots, 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 follow-up: Changed 3 years ago by 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 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 dcoudert

It's nice that sage already has an implementation of this algorithm, but I find it lacking. If I want a list of non-roots, 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.

vertices = [v for v in vertices if v != DS.find(v)] should give you non-roots, no?

comment:57 Changed 3 years ago by git

  • Commit changed from 665f1dc4df118914a4ddcc64d76eb845bc511062 to 94aa44f6ea86e2a25510ebec6e7290d26b52779b

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

94aa44fusing DisjointSet

comment:58 Changed 3 years ago by zgershkoff

Ah, right. I misread the description of that method.

comment:59 in reply to: ↑ 55 Changed 3 years ago by dcoudert

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

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 zgershkoff

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 git

  • Commit changed from 94aa44f6ea86e2a25510ebec6e7290d26b52779b to bca2aad2ea72241adcbaa08e56a12d1e74210de3

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

bca2aadImproved documentation and directed case

comment:62 Changed 3 years ago by git

  • Commit changed from bca2aad2ea72241adcbaa08e56a12d1e74210de3 to a686c55681e31ab7237c9e2c18577b3ba6e0974d

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

a686c55Typo in documentation

comment:63 follow-ups: Changed 3 years ago by dcoudert

Another round of comments.

In method contract_edge

  • in the INPUT block, some lines are for contract_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): with for 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 2-tuples 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 like if not edge_list: return or if 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 zgershkoff

Replying to dcoudert:

Another round of comments.

In method contract_edge

  • in the INPUT block, some lines are for contract_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): with for 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 git

  • Commit changed from a686c55681e31ab7237c9e2c18577b3ba6e0974d to 4c97d713e8d18d71f6a7d1b6496939fb80817f7e

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

2931fb4resolution when the label is unspecified
8590722adding methods to index`
f58b59bRevert "resolution when the label is unspecified"
4c97d71some innocuous changes

comment:66 in reply to: ↑ 63 Changed 3 years ago by zgershkoff

I have a few more questions.

  • Is return preferred over return None? I've changed them to just return.
  • 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 2-tuples and 3-tuples 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 git

  • Commit changed from 4c97d713e8d18d71f6a7d1b6496939fb80817f7e to 0bdd5272076311e182fa4ac9beb56e4558278ee8

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

0bdd527raise exception if tuple lengths are inconsistent

comment:68 follow-up: Changed 3 years ago by dcoudert

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 zgershkoff

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 git

  • Commit changed from 0bdd5272076311e182fa4ac9beb56e4558278ee8 to a77404f72f68416fa81af947dff29a5b95acb078

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

35a7201Tabs instead of spaces. I blame the editor.
412dc90moved loops from vertices before the vertices get deleted
ff571d6efficiency improvements; bug fix when input is [None]
a77404fMerge branch 't/23290/ff571d6699ab233eedaf3b9d4a417ef6a1f6c56f' into t/7304/contract_edge_in_graph

comment:71 Changed 3 years ago by zgershkoff

I took the liberty of moving #23290 into this since it's closed. All tests pass now.

comment:72 follow-up: Changed 3 years ago by 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)

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 method has_edge.

comment:73 in reply to: ↑ 72 Changed 3 years ago by zgershkoff

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 method has_edge.

That also makes sense.

comment:74 Changed 3 years ago by git

  • Commit changed from a77404f72f68416fa81af947dff29a5b95acb078 to 29dd861eef950472241a9866cedd56d4b6b4474a

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

29dd861efficiency improvements

comment:75 Changed 3 years ago by zgershkoff

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 zgershkoff

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 dcoudert

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 git

  • Commit changed from 29dd861eef950472241a9866cedd56d4b6b4474a to a4444882aef97b611da18172b0d04ebe1bde1977

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

a444488additional tests

comment:79 Changed 3 years ago by git

  • Commit changed from a4444882aef97b611da18172b0d04ebe1bde1977 to 438381446f2ab4ee75055e7282dbf75e94a5abae

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

4383814redundancy in tests

comment:80 Changed 3 years ago by zgershkoff

  • Milestone changed from sage-6.4 to sage-8.0

I added tests for labeled edges, and for attempting to contract non-edges. I think that covers it.

comment:81 Changed 3 years ago by dcoudert

Final comments (sorry for that).

For method contract_edge:

  • at the top of the generic_graph.py file, could you ensure that the description of contract_edge is the same as in the method. I propose to put: Contract an edge from `u` to `v`. Note that I use Contract and not Contracts.
  • Then in the method, split the first line to Contract an edge from `u` to `v` and then have a next paragraph with This method returns silently if the edge does not exist.

For method contract_edges:

  • at the top of the generic_graph.py file, for contract_edges: use Contract instead of Contracts
  • 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 before With 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 git

  • Commit changed from 438381446f2ab4ee75055e7282dbf75e94a5abae to 645c3e7bf8d011846fc6fcadd753200382414940

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

645c3e7Documentation fixes

comment:83 Changed 3 years ago by git

  • Commit changed from 645c3e7bf8d011846fc6fcadd753200382414940 to 50a884f5a8aa1af7448f15ed292c1c936788f0bd

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

50a884fa bit of extra whitespace...

comment:84 Changed 3 years ago by zgershkoff

Done. Thanks for walking me through it.

comment:85 Changed 3 years ago by dcoudert

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

  • Commit changed from 50a884f5a8aa1af7448f15ed292c1c936788f0bd to 6f2a583a1705c1addb076c84479a693664ad058f

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

6f2a583proper demarcation of variables

comment:87 Changed 3 years ago by zgershkoff

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

I checked and the documentation looks good. So we are done.

comment:89 Changed 2 years ago by vbraun

  • Dependencies changed from #9362, #23290 to #23290

comment:90 Changed 2 years ago by vbraun

If you depend on a pre-git ticket then the release script will never figure out that the dependencies are merged FYI

comment:91 Changed 2 years ago by vbraun

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

  • Authors changed from Zachary Gershkoff to Zach Gershkoff
  • Commit 6f2a583a1705c1addb076c84479a693664ad058f deleted
Note: See TracTickets for help on using tickets.