Opened 11 years ago

# Contraction of edges in a graph.

Reported by: Owned by: lkeough jason, ncohen, rlm major graph theory SD40 jeremy.l.martin, dcoudert Lauren Keough, Jeremy Martin Marshall Hampton, David Coudert N/A

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

### comment:1 Changed 11 years ago by lkeough

Authors: → Lauren Keough, Jeremy Martin jeremy.l.martin added new → needs_review

### comment:3 Changed 11 years ago by mhampton

Reviewers: → Marshall Hampton needs_review → positive_review

### comment:4 follow-up:  5 Changed 11 years ago by dcoudert

Cc: dcoudert added Marshall Hampton → Marshall Hampton, David Coudert positive_review → needs_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

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 follow-up:  7 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

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.11 → sage-5.12

### comment:9 Changed 9 years ago by vbraun_spam

Milestone: sage-6.1 → sage-6.2

### comment:10 Changed 9 years ago by vbraun_spam

Milestone: sage-6.2 → sage-6.3

### comment:11 Changed 8 years ago by vbraun_spam

Milestone: sage-6.3 → sage-6.4

### comment:12 Changed 6 weeks ago by mkoeppe

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