Opened 7 years ago
Closed 7 years ago
#15550 closed enhancement (fixed)
Implement the KirchhoffSymanzik polynomial for graphs
Reported by:  chapoton  Owned by:  

Priority:  minor  Milestone:  sage6.1 
Component:  graph theory  Keywords:  symanzik polynomial 
Cc:  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  public/15550 (Commits)  Commit:  197a285efe203a92c3719e35a2b730616d56f94b 
Dependencies:  Stopgaps: 
Description (last modified by )
This is a polynomial in several variables, useful in the study of Feynman diagrams.
Done using a determinant (like in the matrixtree theorem)
Also implements cycle_basis for graphs with multiple edges
and add an 'output' parameter to 'cycle_basis', 'is_tree' and 'is_forest'
Change History (42)
comment:1 Changed 7 years ago by
 Description modified (diff)
 Type changed from enhancement to task
comment:2 Changed 7 years ago by
 Branch set to u/ncohen/15550
 Description modified (diff)
 Status changed from new to needs_review
 Type changed from task to enhancement
comment:3 Changed 7 years ago by
 Branch changed from u/ncohen/15550 to u/chapoton/15550
 Commit set to 87702b4df58f7226297886d9fc505e8bec4e5cdc
comment:4 Changed 7 years ago by
Hello Frederic !
I think you could replace your "quasitree_to_cycle" function by a call to Graph.is_forest(certificate=True)
. Could you also merge all these patches into one ? It would make it a bit easier to review ^^;
Nathann
comment:5 Changed 7 years ago by
 Status changed from needs_review to needs_work
comment:6 followup: ↓ 7 Changed 7 years ago by
Hello Nathann,
thanks for the suggestion. But is_forest
does not work correctly on graphs with multiple edges:
sage: G=graphs.CycleGraph(6) sage: G.is_forest() False sage: G.is_forest(certificate=True) (False, [5, 4, 3, 2, 1, 0]) sage: G = Graph([(1,2,'a'),(1,2,'b')]) sage: G.is_forest(certificate=True) sage: G.is_forest() False
and moreover I need the cycle as a sequence of signed edges.
comment:7 in reply to: ↑ 6 Changed 7 years ago by
thanks for the suggestion. But
is_forest
does not work correctly on graphs with multiple edges:
Oh. Well, multiple edges actually make no difference, unless you have a 2cycle. In which case that is your certificate. I think that fixing that is still better than reimplementing it with a weird name.
and moreover I need the cycle as a sequence of signed edges.
What does that mean ? Can't that be obtained with the certificate of is_forest
?
Nathann
comment:8 Changed 7 years ago by
 Commit changed from 87702b4df58f7226297886d9fc505e8bec4e5cdc to 13a16d42a8c1c17b6726487b7e2f1aa311c7b51c
Branch pushed to git repo; I updated commit sha1. New commits:
13a16d4  trac #15550 some changes after suggestions

comment:9 followup: ↓ 10 Changed 7 years ago by
Hello Nathann,
I have now made good use of the is_tree
function.
Would you prefer if I put my auxiliary function inside the new method ? I do not see how to avoid it completely. I need to choose an arbitray orientation of the graph, and for this I am using the way the edges are given by a pair (i,j). Then I need to know how every cycle is oriented, some arrows being in the wrong direction.
Is this really necessary to smash all my commits (not patches) into one ? I would prefer not to.
comment:10 in reply to: ↑ 9 Changed 7 years ago by
Hellooooooooo !
Would you prefer if I put my auxiliary function inside the new method ?
Your auxiliary method will not be in your final patch, that's for sure, because even if it were actually useful for your code it has no general use and has nothing to do has a Graph function. At the very least it should be made private. This being said, you still haven't explained to me what exactly this function does (neither is it explained in the function's docstring), so I do not understand how to help you remove it yet. Please tell me what exactly it does. Right now its docstring reads "return the only cycle of a graph with one cycle", and that's exactly what is_forest
does for you, thus something is missing.
I do not see how to avoid it completely. I need to choose an arbitray orientation of the graph, and for this I am using the way the edges are given by a pair (i,j). Then I need to know how every cycle is oriented, some arrows being in the wrong direction.
I do not know what you need this orientation for, but using the orientation given by edges()
can be tricky. There is absolutely no certainty that the orientation of the edges given by edges()
is consistent with the one given by edges_incident()
.
Is this really necessary to smash all my commits (not patches) into one ? I would prefer not to.
It would make your patch clearer. There are 5 commits in your patch right now and most of what one does is undone in the other. This being said merging commits is *very easy* to do in git : you have to "rebase" your ticket's branch upon "develop" using the 'i' flag, for "interactive". In only one command you can merge commits together (I think 'git' uses the keyword 'meld' instead). That's actually quite cool :P
Nathann
comment:11 Changed 7 years ago by
 Commit changed from 13a16d42a8c1c17b6726487b7e2f1aa311c7b51c to dd2e9e9fc3a7f4db42c41044925441983228a78f
Branch pushed to git repo; I updated commit sha1. New commits:
dd2e9e9  Trac #15550 implement the KirchhoffSymanzik polynomial

comment:12 Changed 7 years ago by
Here is a smashed thing. And hopefully simpler, too.
comment:13 Changed 7 years ago by
(please set the ticket back to needs_review
when it needs a review. Otherwise it does not appear in the list of tickets needing a review and nobody reads them. And I 'lost' tickets several times like that, finding them again years later, just because they were still in needs_work
:P
)
Nathann
comment:14 Changed 7 years ago by
 Status changed from needs_work to needs_review
Yes, sorry.
I have made the auxiliary method into a private method, but it is now very small, so it could be put inside the main function. Tell me what you prefer and I will change accordingly.
comment:15 Changed 7 years ago by
Well, if it is 10 lines long I think it would be better to move it inside of your main function. But it would be very nice if you could explain what exactly it does, because I have to understand the code if I want to review it ^^;
Nathann
comment:16 Changed 7 years ago by
comment:17 Changed 7 years ago by
 Commit changed from dd2e9e9fc3a7f4db42c41044925441983228a78f to d48ef924a46280b92cc14c8f5c8fd7b58af37736
Branch pushed to git repo; I updated commit sha1. New commits:
d48ef92  Trac #15550 implement the KirchhoffSymanzik polynomial

comment:18 Changed 7 years ago by
 Commit changed from d48ef924a46280b92cc14c8f5c8fd7b58af37736 to 8d28b23a6146142b8571e6ce97f5561688b4f6f7
Branch pushed to git repo; I updated commit sha1. New commits:
8d28b23  trac #15550 details

comment:19 Changed 7 years ago by
 Status changed from needs_review to needs_info
I am still trying to understand this code (and it would clearly help if you could add comments to it). You are buildng a cycle basis for a graph, and we have a function named Graph.cycle_basis
. The problem is that it does not work for graphs with multiedges. Shouldn't your code move there ? If there are differences in speed, it would be cool to keep the two implementations available.
Nathann
comment:20 Changed 7 years ago by
 Commit changed from 8d28b23a6146142b8571e6ce97f5561688b4f6f7 to e68f25d800b1fe775821c663b7899060b74211db
Branch pushed to git repo; I updated commit sha1. New commits:
e68f25d  trac #15550 + cycle_basis for unidirected graph with multiple edges

comment:21 followup: ↓ 24 Changed 7 years ago by
I have now added some code to cycle_basis
But one cannot reconstruct a cycle from its support in a graph with multiple edges, so I cannot use that, unless I change the output of cycle_basis to a list of edges.
When you tell me you want more explanations, do you mean
 here in trac
 as comments in the code
 in the doc of the code ?
comment:22 Changed 7 years ago by
 Status changed from needs_info to needs_review
comment:23 followup: ↓ 25 Changed 7 years ago by
Did you know that:
http://git.sagemath.org/sage.git/diff/?h=u/chapoton/15550&id2=develop
This is a way to see all the changes at once.. No need to smash commits..
comment:24 in reply to: ↑ 21 Changed 7 years ago by
Hello !
I have now added some code to cycle_basis
But one cannot reconstruct a cycle from its support in a graph with multiple edges, so I cannot use that, unless I change the output of cycle_basis to a list of edges.
Well, the best way would be to add a flag to cycle_basis
to ask precisely this : how should the output be given ? While saying that of course the "vertex" output cannot be used if the graph has multiple edges.
When you tell me you want more explanations, do you mean
 here in trac
 as comments in the code
 in the doc of the code ?
I would personally like it very much if you could answer the questions I ask here with real words and not only with git commits. Then, the problem is the following : the code is clearly not documented properly, as I cannot understand what it does, and I can swear this review costed me a lot of time already.
I would like to understand clearly the orientation that you pick, and all steps that you use to build the matrix, then to compute the coefficients. Besides, this should be written somewhere, in the docstring or as comments in the code.
Nathann
comment:25 in reply to: ↑ 23 Changed 7 years ago by
Did you know that:
http://git.sagemath.org/sage.git/diff/?h=u/chapoton/15550&id2=develop
This is a way to see all the changes at once.. No need to smash commits..
I knew. Git can also be used directly to output such things. But it does not help at all either when every commits contradicts the previous ones. Several commits can be very useful when each of the commit does some meaningful task, that actually helps the review. Commiting the mistakes one makes while writing the patch does not.
I swear, I write and review things like #15623 these days, which contain far too many commits already without showing all mistakes done during the development :P
Nathann
comment:26 Changed 7 years ago by
 Commit changed from e68f25d800b1fe775821c663b7899060b74211db to 7eefb7f5d7703df4fee1d026ec742626e72134bf
Branch pushed to git repo; I updated commit sha1. New commits:
7eefb7f  trac #15550 add an 'output' keyword to cycle_basis and other methods

comment:27 Changed 7 years ago by
 Status changed from needs_review to needs_work
Hello
Thank you Nathann for spending time on this, and sorry for not answering wellenough.
I have now added a 'output' keyword to 'cycle_basis', 'is_tree' and 'is_forest'.
Still I am not satisfied, because when output is set to 'edge', the cycle is not returned as a list of triples (vertex,vertex,label), but as a list of pairs [vertex,vertex]. It cannot therefore be recognized as an edge, i.e does not belongs to G.edges().
I will try later to correct that.
comment:28 Changed 7 years ago by
 Commit changed from 7eefb7f5d7703df4fee1d026ec742626e72134bf to d3f1ed98a794375b318198ade0af8f85228289ce
Branch pushed to git repo; I updated commit sha1. New commits:
d3f1ed9  trac #15550 now result cycles given as a list of true edges

comment:29 Changed 7 years ago by
 Commit changed from d3f1ed98a794375b318198ade0af8f85228289ce to a3005a99f42302b4ae670d642cb719030f02a74d
Branch pushed to git repo; I updated commit sha1. New commits:
a3005a9  Trac #15550 implement the KirchhoffSymanzik polynomial

comment:30 Changed 7 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
Rewriting history again, here is a working version.
comment:31 Changed 7 years ago by
 Branch changed from u/chapoton/15550 to public/15550
 Commit a3005a99f42302b4ae670d642cb719030f02a74d deleted
 Reviewers set to Nathann Cohen
Wow. Very good patch, thank you very much for this work :)
All I could add are small modifications to the doc. I added one commit to your branch. If you agree with that, you can set the ticket to positive_review
.
Happy new yeaaaaaaaaar !
Nathann
comment:32 Changed 7 years ago by
 Commit set to 11f9ec629663de71d7578dc1c5f7034238715c11
comment:33 Changed 7 years ago by
Oops, soorry I forgot. I noticed that the cycle_basis
function does not work for disconnected graphs. I'll fix that in a second.
Nathann
comment:34 Changed 7 years ago by
Hmmmmm... It was actually slightly more complicated than that. This, and supper in between.
Technically :
 networkx refuses to work on a graph that allows multiple edges, even if it does not contain any
cycle_basis
now handles disconnected graphs
Aaaaaaaaand I found a bug with those cursed multiple edges again :
sage: g = Graph({0:{1:[1,1]}}, multiedges=True) sage: g.edges() [(0, 1, 1), (0, 1, 1)] sage: (2*g).edges() [(0, 1, 1), (2, 3, 1)]
I hate these things...
Anyway, branch updated. Tell me what you think !
Nathann
comment:35 Changed 7 years ago by
 Commit changed from 11f9ec629663de71d7578dc1c5f7034238715c11 to 8b7505a5bac55f1bafd6f4b2ab27c755751c5a61
comment:36 Changed 7 years ago by
Happy new year to you too, and thanks for the review !
Review patch looks good to me. If you agree, please set to positive review.
comment:37 Changed 7 years ago by
 Status changed from needs_review to positive_review
comment:38 Changed 7 years ago by
Doesn't merge, please resolve.
comment:39 Changed 7 years ago by
Hmmmm... It merges with 6.1.beta3, so it must be conflicting with some other patch you already merged.
Nathann
comment:40 Changed 7 years ago by
Conflicts with beta4
comment:41 Changed 7 years ago by
 Commit changed from 8b7505a5bac55f1bafd6f4b2ab27c755751c5a61 to 197a285efe203a92c3719e35a2b730616d56f94b
Rebased ! (though there was no automatic git message)
Nathann
New commits:
197a285  trac #15550: rebase on 6.1.beta4

comment:42 Changed 7 years ago by
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #15550 now allows to change name of variables
Trac #15550 the code should now be correct
correct integration as a method
Trac #15550 implement the KirchhoffSymanzik polynomial