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: |
Attachments (1)
Change History (13)
comment:1 Changed 11 years ago by
Authors: | → Lauren Keough, Jeremy Martin |
---|---|
Cc: | jeremy.l.martin added |
Status: | new → needs_review |
Changed 11 years ago by
Attachment: | trac_13239.patch added |
---|
comment:2 Changed 11 years ago by
Keywords: | SD40 added |
---|
comment:3 Changed 11 years ago by
Reviewers: | → Marshall Hampton |
---|---|
Status: | needs_review → positive_review |
comment:4 follow-up: 5 Changed 11 years ago by
Cc: | dcoudert added |
---|---|
Reviewers: | Marshall Hampton → Marshall Hampton, David Coudert |
Status: | positive_review → needs_info |
comment:5 Changed 11 years ago by
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 follow-up: 7 Changed 11 years ago by
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 Changed 11 years ago by
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
Milestone: | sage-5.11 → sage-5.12 |
---|
comment:9 Changed 9 years ago by
Milestone: | sage-6.1 → sage-6.2 |
---|
comment:10 Changed 9 years ago by
Milestone: | sage-6.2 → sage-6.3 |
---|
comment:11 Changed 8 years ago by
Milestone: | sage-6.3 → sage-6.4 |
---|
comment:12 Changed 6 weeks ago by
Milestone: | sage-6.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)
D.