Contract edge in graph

[AJonsson]

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.

[AJonsson]

Initial patch for review

[AJonsson]

Duplicate of #7159 . That ticket is about vertex merging, but it is basically the same thing.

[AJonsson]

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.

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

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

[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

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

[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 ! :-)

[AJonsson]

Ok, will look closer into a modification of #7159 to be added after that ticket has been merged to Sage.

[ncohen]

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

[AJonsson]

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.

[bascorp]

 куплю мобильный телефон

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

[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

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

[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

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

[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

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

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

[brunellus]

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

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

[davidloeffler]

Apply trac_7304_contract_edge.patch

(for patchbot)

[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?)

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

[brunellus]

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

[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?

[jdemeyer]

Please fill in your real name as Author.

[ncohen]

Ok.... Which is the patch that needs to be reviewed ? Is it trac_7304_contract_edge.patch ?

Nathann