Opened 7 years ago

Closed 7 years ago

#15550 closed enhancement (fixed)

Implement the Kirchhoff-Symanzik polynomial for graphs

Reported by: chapoton Owned by:
Priority: minor Milestone: sage-6.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 chapoton)

This is a polynomial in several variables, useful in the study of Feynman diagrams.

Done using a determinant (like in the matrix-tree 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 chapoton

  • Description modified (diff)
  • Type changed from enhancement to task

comment:2 Changed 7 years ago by chapoton

  • 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 chapoton

  • Branch changed from u/ncohen/15550 to u/chapoton/15550
  • Commit set to 87702b4df58f7226297886d9fc505e8bec4e5cdc

New commits:

87702b4trac #15550 now allows to change name of variables
d979b9bTrac #15550 the code should now be correct
3448aafcorrect integration as a method
c0a712fTrac #15550 implement the Kirchhoff-Symanzik polynomial

comment:4 Changed 7 years ago by ncohen

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 ncohen

  • Status changed from needs_review to needs_work

comment:6 follow-up: Changed 7 years ago by chapoton

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 ncohen

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 2-cycle. In which case that is your certificate. I think that fixing that is still better than re-implementing 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 git

  • Commit changed from 87702b4df58f7226297886d9fc505e8bec4e5cdc to 13a16d42a8c1c17b6726487b7e2f1aa311c7b51c

Branch pushed to git repo; I updated commit sha1. New commits:

13a16d4trac #15550 some changes after suggestions

comment:9 follow-up: Changed 7 years ago by chapoton

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 ncohen

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 git

  • Commit changed from 13a16d42a8c1c17b6726487b7e2f1aa311c7b51c to dd2e9e9fc3a7f4db42c41044925441983228a78f

Branch pushed to git repo; I updated commit sha1. New commits:

dd2e9e9Trac #15550 implement the Kirchhoff-Symanzik polynomial

comment:12 Changed 7 years ago by chapoton

Here is a smashed thing. And hopefully simpler, too.

comment:13 Changed 7 years ago by ncohen

(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 chapoton

  • 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 ncohen

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 chapoton

  • Authors set to Frédéric Chapoton

comment:17 Changed 7 years ago by git

  • Commit changed from dd2e9e9fc3a7f4db42c41044925441983228a78f to d48ef924a46280b92cc14c8f5c8fd7b58af37736

Branch pushed to git repo; I updated commit sha1. New commits:

d48ef92Trac #15550 implement the Kirchhoff-Symanzik polynomial

comment:18 Changed 7 years ago by git

  • Commit changed from d48ef924a46280b92cc14c8f5c8fd7b58af37736 to 8d28b23a6146142b8571e6ce97f5561688b4f6f7

Branch pushed to git repo; I updated commit sha1. New commits:

8d28b23trac #15550 details

comment:19 Changed 7 years ago by ncohen

  • 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 git

  • Commit changed from 8d28b23a6146142b8571e6ce97f5561688b4f6f7 to e68f25d800b1fe775821c663b7899060b74211db

Branch pushed to git repo; I updated commit sha1. New commits:

e68f25dtrac #15550 + cycle_basis for unidirected graph with multiple edges

comment:21 follow-up: Changed 7 years ago by chapoton

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 chapoton

  • Status changed from needs_info to needs_review

comment:23 follow-up: Changed 7 years ago by chapoton

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 ncohen

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 ncohen

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 git

  • Commit changed from e68f25d800b1fe775821c663b7899060b74211db to 7eefb7f5d7703df4fee1d026ec742626e72134bf

Branch pushed to git repo; I updated commit sha1. New commits:

7eefb7ftrac #15550 add an 'output' keyword to cycle_basis and other methods

comment:27 Changed 7 years ago by chapoton

  • Status changed from needs_review to needs_work

Hello

Thank you Nathann for spending time on this, and sorry for not answering well-enough.

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 git

  • Commit changed from 7eefb7f5d7703df4fee1d026ec742626e72134bf to d3f1ed98a794375b318198ade0af8f85228289ce

Branch pushed to git repo; I updated commit sha1. New commits:

d3f1ed9trac #15550 now result cycles given as a list of true edges

comment:29 Changed 7 years ago by git

  • Commit changed from d3f1ed98a794375b318198ade0af8f85228289ce to a3005a99f42302b4ae670d642cb719030f02a74d

Branch pushed to git repo; I updated commit sha1. New commits:

a3005a9Trac #15550 implement the Kirchhoff-Symanzik polynomial

comment:30 Changed 7 years ago by chapoton

  • 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 ncohen

  • 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 git

  • Commit set to 11f9ec629663de71d7578dc1c5f7034238715c11

Branch pushed to git repo; I updated commit sha1. New commits:

11f9ec6Trac #15550: Review, small changes to the doc
a3005a9Trac #15550 implement the Kirchhoff-Symanzik polynomial

comment:33 Changed 7 years ago by ncohen

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 ncohen

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 git

  • Commit changed from 11f9ec629663de71d7578dc1c5f7034238715c11 to 8b7505a5bac55f1bafd6f4b2ab27c755751c5a61

Branch pushed to git repo; I updated commit sha1. New commits:

8b7505aTrac #15550: Review, small changes to the doc
a3005a9Trac #15550 implement the Kirchhoff-Symanzik polynomial

comment:36 Changed 7 years ago by chapoton

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 ncohen

  • Status changed from needs_review to positive_review

comment:38 Changed 7 years ago by vbraun

Doesn't merge, please resolve.

comment:39 Changed 7 years ago by ncohen

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 vbraun

Conflicts with beta4

comment:41 Changed 7 years ago by ncohen

  • Commit changed from 8b7505a5bac55f1bafd6f4b2ab27c755751c5a61 to 197a285efe203a92c3719e35a2b730616d56f94b

Rebased ! (though there was no automatic git message)

Nathann


New commits:

197a285trac #15550: rebase on 6.1.beta4

comment:42 Changed 7 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.