Contraction of edges in a graph.

[sagetrac-lkeough]

Contracts edges in a graph so that we can compute the Tutte polynomial (#1314)

This version of contracting edges is different from #7304 (this code will keep resulting multiedges and remove contracted edge).

CC: @sagetrac-jeremy-l-martin @dcoudert

Component: graph theory

Keywords: SD40

Author: Lauren Keough, Jeremy Martin

Reviewer: Marshall Hampton, David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/13239

[sagetrac-lkeough]

Author: Lauren Keough, Jeremy Martin

[sagetrac-lkeough]

Attachment: trac_13239.patch.gz

[sagetrac-lkeough]

Changed keywords from none to SD40

[sagetrac-mhampton]

Reviewer: Marshall Hampton

[dcoudert]

Changed reviewer from Marshall Hampton to Marshall Hampton, David Coudert

[dcoudert]

comment:4

Hello,

I don't understand this new patch. If the behavior of the contract_edge function proposed in patch #7304 is not adapted to your purpose, you could add extra parameters (inplace = False, keep_multiedges, etc.)

Furthermore, it works only for undirected graphs. So it should at least be in graph.py and not in generic_graph.py.

In the following example, arc (3,0) becomes arc (0,3)

sage: D = digraphs.RandomDirectedGNP(5,.5)
sage: h = D.contraction((0,1))
sage: D.edges(labels=None)
[(0, 1), (0, 2), (0, 3), (1, 0), (1, 3), (1, 4), (2, 0), (3, 0), (3, 1), (3, 4), (4, 2)]
sage: h.edges(labels=None)
[(0, 0), (0, 2), (0, 2), (0, 3), (0, 3), (0, 3), (0, 3), (0, 4), (2, 4), (3, 4)]

D.

[sagetrac-lkeough]

comment:5

Replying to @dcoudert:

Hello,

I don't understand this new patch. If the behavior of the contract_edge function proposed in patch #7304 is not adapted to your purpose, you could add extra parameters (inplace = False, keep_multiedges, etc.)

#7304 will keep multiedges if you do G.allow_multiedges . However, we also need to do G.allow_loops (for the tutte polynomial), but if we do that then the patch leaves the contracted edge (rather than deleting it which is what we want). I suppose I could use their code and then add a line to mine that deletes that loop.

I'm not really sure what the best option is here. 7304 already has a lot of parameters and adding another might be very confusing. And I'm also not sure what most people mean by contracting an edge - I thought the definition I have written in this code was "the" definition, but it's becoming more apparent that it isn't at all! Perhaps I could just include this code in the Tutte polynomial code and not as a separate function? I'm very open to advice on this!

Furthermore, it works only for undirected graphs. So it should at least be in graph.py and not in generic_graph.py.

Okay, I will definitely move to graph.py unless I can figure out how to make it work for digraphs.

In the following example, arc (3,0) becomes arc (0,3)

sage: D = digraphs.RandomDirectedGNP(5,.5)
sage: h = D.contraction((0,1))
sage: D.edges(labels=None)
[(0, 1), (0, 2), (0, 3), (1, 0), (1, 3), (1, 4), (2, 0), (3, 0), (3, 1), (3, 4), (4, 2)]
sage: h.edges(labels=None)
[(0, 0), (0, 2), (0, 2), (0, 3), (0, 3), (0, 3), (0, 3), (0, 4), (2, 4), (3, 4)]

D.

[dcoudert]

comment:6

If the #7304 function is not adapted to your purpose, it could be better to include the code in your function instead of creating a new one.

May be some people from Sage Days could give good advise.

[sagetrac-lkeough]

comment:7

Replying to @dcoudert:

If the #7304 function is not adapted to your purpose, it could be better to include the code in your function instead of creating a new one.

May be some people from Sage Days could give good advise.

A couple of graph theorists at Sage Days said they would prefer to have a function by the name of contraction that does what I described in the documentation for this one. It is very easy to adapt their code and call it contraction. I'm going to try both things and time them to see which is faster. Thanks!