Opened 11 years ago

Last modified 6 weeks ago

#13239 needs_info enhancement

Contraction of edges in a graph.

Reported by: lkeough Owned by: jason, ncohen, rlm
Priority: major Milestone:
Component: graph theory Keywords: SD40
Cc: jeremy.l.martin, dcoudert Merged in:
Authors: Lauren Keough, Jeremy Martin Reviewers: Marshall Hampton, David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

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

Attachments (1)

trac_13239.patch (2.5 KB) - added by lkeough 11 years ago.

Download all attachments as: .zip

Change History (13)

comment:1 Changed 11 years ago by lkeough

Authors: Lauren Keough, Jeremy Martin
Cc: jeremy.l.martin added
Status: newneeds_review

Changed 11 years ago by lkeough

Attachment: trac_13239.patch added

comment:2 Changed 11 years ago by lkeough

Keywords: SD40 added

comment:3 Changed 11 years ago by mhampton

Reviewers: Marshall Hampton
Status: needs_reviewpositive_review

comment:4 Changed 11 years ago by dcoudert

Cc: dcoudert added
Reviewers: Marshall HamptonMarshall Hampton, David Coudert
Status: positive_reviewneeds_info

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.

comment:5 in reply to:  4 Changed 11 years ago by lkeough

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.

comment:6 Changed 11 years ago by 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.

comment:7 in reply to:  6 Changed 11 years ago by lkeough

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!

comment:8 Changed 9 years ago by jdemeyer

Milestone: sage-5.11sage-5.12

comment:9 Changed 9 years ago by vbraun_spam

Milestone: sage-6.1sage-6.2

comment:10 Changed 9 years ago by vbraun_spam

Milestone: sage-6.2sage-6.3

comment:11 Changed 8 years ago by vbraun_spam

Milestone: sage-6.3sage-6.4

comment:12 Changed 6 weeks ago by mkoeppe

Milestone: sage-6.4
Note: See TracTickets for help on using tickets.