Sage: Ticket #15662: Ihara zeta function of graphs
https://trac.sagemath.org/ticket/15662
<p>
Let us implement the zeta function of graphs
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/15662
Trac 1.1.6chapotonFri, 10 Jan 2014 21:21:09 GMTstatus changed; commit, branch, author set
https://trac.sagemath.org/ticket/15662#comment:1
https://trac.sagemath.org/ticket/15662#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>b2c1e310c03477183cb3e793103711989955eb57</em>
</li>
<li><strong>branch</strong>
set to <em>u/chapoton/15662</em>
</li>
<li><strong>author</strong>
set to <em>Frédéric Chapoton</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=b2c1e310c03477183cb3e793103711989955eb57"><span class="icon"></span>b2c1e31</a></td><td><code>trac #15662 implement Ihara zeta function of graphs</code>
</td></tr></table>
TicketncohenTue, 14 Jan 2014 10:11:51 GMT
https://trac.sagemath.org/ticket/15662#comment:2
https://trac.sagemath.org/ticket/15662#comment:2
<p>
Yo !
</p>
<p>
Wikipedia says "a zeta function", and you cite a paper saying that there are many zeta functions defined on graph. Why shouldn't this method be renamed to <code>ihara_zeta_function</code> instead ?
</p>
<p>
Besides, I don't understand what you do with the edges of your graph : why do you inverse the first and second coordinate ? (you cannot even assume that the vertices are integers when you write code for graphs. So if you want to ensure that they are sorted in some way ....)
</p>
<p>
Nathann
</p>
TicketncohenTue, 14 Jan 2014 10:12:16 GMTstatus changed
https://trac.sagemath.org/ticket/15662#comment:3
https://trac.sagemath.org/ticket/15662#comment:3
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
TicketchapotonTue, 14 Jan 2014 11:12:43 GMT
https://trac.sagemath.org/ticket/15662#comment:4
https://trac.sagemath.org/ticket/15662#comment:4
<p>
Hello,
</p>
<p>
1) I am not quite sure about the name indeed. I would say that this is usually called the zeta function of a graph. But there are variants, some of them called weighted zeta functions. I think keeping the name starting with zeta is good for TAB completion.
</p>
<p>
2) The algorithm needs to duplicate every edge, by orienting the original one in a chosen direction, and the new one in the other direction. I take as orientation the one given by self.edges(). I then use the shift by the number of edges as the bijection between original edges and their duplicate-reverse.
</p>
<p>
3) Some people had needed that function and used another way to do it : see <a class="ext-link" href="http://mathoverflow.net/questions/122682/ihara-zeta-function-graph-theory-coefficients-using-a-line-graph"><span class="icon"></span>http://mathoverflow.net/questions/122682/ihara-zeta-function-graph-theory-coefficients-using-a-line-graph</a>
</p>
TicketncohenTue, 14 Jan 2014 11:37:44 GMT
https://trac.sagemath.org/ticket/15662#comment:5
https://trac.sagemath.org/ticket/15662#comment:5
<p>
Yoooooooooooo !
</p>
<blockquote class="citation">
<p>
1) I am not quite sure about the name indeed. I would say that this is usually called the zeta function of a graph. But there are variants, some of them called weighted zeta functions. I think keeping the name starting with zeta is good for TAB completion.
</p>
</blockquote>
<p>
Hmmmmm... Well, if the terminology isn't even set, should it become a Graph method ? I am trying to keep my graph functions out of the graph class when I believe that their are not of very wide use.
</p>
<p>
When you type "zeta function graphs" in Google (<a class="ext-link" href="http://goo.gl/SM8aLb"><span class="icon"></span>http://goo.gl/SM8aLb</a>) the first result I get is the following :
<a class="ext-link" href="http://math.ucsd.edu/~aterras/snowbird.pdf"><span class="icon"></span>http://math.ucsd.edu/~aterras/snowbird.pdf</a>
</p>
<p>
Which hints that there may be quite a lot of Zeta functions defined on graphs. And they do mention the one you implement, saying that it may be weighted too. What about <code>.zeta_ihara</code> if you want the name to begin with <code>zeta</code> ?
</p>
<blockquote class="citation">
<p>
2) The algorithm needs to duplicate every edge, by orienting the original one in a chosen direction, and the new one in the other direction.
</p>
</blockquote>
<p>
Like when you do <code>DiGraph(a_graph)</code> ?
</p>
<blockquote class="citation">
<p>
I take as orientation the one given by self.edges(). I then use the shift by the number of edges as the bijection between original edges and their duplicate-reverse.
</p>
</blockquote>
<p>
Oh. Well, I still do not understand what your two loops exactly do, but it looks like you are computing a bit too much. It feels like you are interested in the edges which share a vertex, except when they represent the same edge.
</p>
<p>
...
</p>
<p>
Hey, aren't you just computing the adjacency matrix of the line graph, which can be obtained by <code>G.line_graph().adjacency_matrix()</code> ?
</p>
<p>
Nathann
</p>
TicketncohenTue, 14 Jan 2014 12:22:53 GMT
https://trac.sagemath.org/ticket/15662#comment:6
https://trac.sagemath.org/ticket/15662#comment:6
<p>
Okay I read the Mathoverflow thread a bit, and I think that the shortest way for you is to do this :
</p>
<pre class="wiki">labeled_g = Graph()
labeled_g.add_edges([(u,v,i) for i,(u,v) in enumerate(g.edges(labels=False))]) # faster than giving the edges when the graph is being built. Don't ask.
for v in labeled_g:
for vv,u,i in labeled_g.edges_incident(v):
if v != vv: raise RuntimeError("Should Not Happen")
# do what you have to, now that you know the labels of your edges.
</pre>
TicketgitTue, 14 Jan 2014 17:20:15 GMTcommit changed
https://trac.sagemath.org/ticket/15662#comment:7
https://trac.sagemath.org/ticket/15662#comment:7
<ul>
<li><strong>commit</strong>
changed from <em>b2c1e310c03477183cb3e793103711989955eb57</em> to <em>55235f6a0d30333d2704303fbbeee7f8679114ec</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=55235f6a0d30333d2704303fbbeee7f8679114ec"><span class="icon"></span>55235f6</a></td><td><code>trac #15662 better algo and better doc</code>
</td></tr></table>
TicketncohenTue, 14 Jan 2014 18:41:41 GMTstatus, branch changed; commit deleted
https://trac.sagemath.org/ticket/15662#comment:8
https://trac.sagemath.org/ticket/15662#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
<em>55235f6a0d30333d2704303fbbeee7f8679114ec</em> deleted
</li>
<li><strong>branch</strong>
changed from <em>u/chapoton/15662</em> to <em>public/15662</em>
</li>
</ul>
<p>
Helloooooooo Frederic !
</p>
<p>
Thank you for this patch. I personally find it clearer, and at least it should be faster. I also added a small commit to this patch (sorry, I just cannot not remove a 'if' when I see a way <code>:-P</code>).
</p>
<p>
I still have a few questions : is it really the *inverse* of the Ihara function (as the documentation claims) or is that a mistake ?
</p>
<ul><li>If it is can you fix it in the docstring and in the function index at the top of the file
</li><li>If not, shouldn't it appear in the function's name too ?
</li></ul><p>
I cannot check from the Wikipedia page that the polynomial you implemented is indeed what it should be. Of course this is mainly because I don't get a word of what this polynomial represents, but I would like to check the correction anyway <code>^^;</code>
Could you help me a bit with that ? <code>:-P</code>
</p>
<p>
Thaaaaaaaaanks !
</p>
<p>
Nathann
</p>
TicketgitTue, 14 Jan 2014 18:42:25 GMTcommit set
https://trac.sagemath.org/ticket/15662#comment:9
https://trac.sagemath.org/ticket/15662#comment:9
<ul>
<li><strong>commit</strong>
set to <em>232c4824582e31b896a820778b94ae334276129d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=b2c1e310c03477183cb3e793103711989955eb57"><span class="icon"></span>b2c1e31</a></td><td><code>trac #15662 implement Ihara zeta function of graphs</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=55235f6a0d30333d2704303fbbeee7f8679114ec"><span class="icon"></span>55235f6</a></td><td><code>trac #15662 better algo and better doc</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=232c4824582e31b896a820778b94ae334276129d"><span class="icon"></span>232c482</a></td><td><code>trac #15662: Removing a 'if' in the algorithm</code>
</td></tr></table>
TicketgitTue, 14 Jan 2014 19:24:02 GMTcommit changed
https://trac.sagemath.org/ticket/15662#comment:10
https://trac.sagemath.org/ticket/15662#comment:10
<ul>
<li><strong>commit</strong>
changed from <em>232c4824582e31b896a820778b94ae334276129d</em> to <em>403fd968aefe0eaf3b9e72f4ec79ba8ac7d9aad5</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=403fd968aefe0eaf3b9e72f4ec79ba8ac7d9aad5"><span class="icon"></span>403fd96</a></td><td><code>trac #15662 added more doc and changed name again</code>
</td></tr></table>
TicketchapotonTue, 14 Jan 2014 19:27:53 GMT
https://trac.sagemath.org/ticket/15662#comment:11
https://trac.sagemath.org/ticket/15662#comment:11
<p>
Hello Nathann,
</p>
<p>
thanks for your interest and your help.
</p>
<p>
I have added to the doc one more reference where you can find the exact definition I am using.
</p>
<p>
You can also look at slide 9/10 in <a class="ext-link" href="http://math.ucsd.edu/~aterras/ihara%20zeta%20and%20QC.pdf"><span class="icon"></span>http://math.ucsd.edu/~aterras/ihara%20zeta%20and%20QC.pdf</a> for the definition in short
</p>
<p>
You can also find examples of values in there : <a class="ext-link" href="http://www.ams.org/journals/bull/2014-51-01/S0273-0979-2013-01426-5/S0273-0979-2013-01426-5.pdf"><span class="icon"></span>http://www.ams.org/journals/bull/2014-51-01/S0273-0979-2013-01426-5/S0273-0979-2013-01426-5.pdf</a>
</p>
TicketncohenWed, 15 Jan 2014 09:20:25 GMT
https://trac.sagemath.org/ticket/15662#comment:12
https://trac.sagemath.org/ticket/15662#comment:12
<p>
Helloooooooooo !!
</p>
<p>
Thanks for this pointer toward the definition we use ! I tried to compare what <a class="ext-link" href="http://www.ams.org/journals/bull/2014-51-01/S0273-0979-2013-01426-5/S0273-0979-2013-01426-5.pdf"><span class="icon"></span>http://www.ams.org/journals/bull/2014-51-01/S0273-0979-2013-01426-5/S0273-0979-2013-01426-5.pdf</a> gets for K_4 and it looks like what Sage's implementation gives is not the same ?... (we have a <code>(t + 1)^2 * (t - 1)^3</code>,they do not).
</p>
<p>
Nathann
</p>
TicketchapotonWed, 15 Jan 2014 10:36:36 GMT
https://trac.sagemath.org/ticket/15662#comment:13
https://trac.sagemath.org/ticket/15662#comment:13
<p>
Maybe just a matter of factorisation ? They do not give a fully factorised form, but some ad-hoc hand-made factorisation.
</p>
TicketncohenWed, 15 Jan 2014 10:41:15 GMT
https://trac.sagemath.org/ticket/15662#comment:14
https://trac.sagemath.org/ticket/15662#comment:14
<blockquote class="citation">
<p>
Maybe just a matter of factorisation ? They do not give a fully factorised form, but some ad-hoc hand-made factorisation.
</p>
</blockquote>
<p>
They are different.
</p>
<pre class="wiki">sage: g = graphs.CompleteGraph(4)
sage: p1 = g.ihara_zeta_function()
sage: ring = PolynomialRing(ZZ, 't')
sage: g = graphs.CompleteGraph(4)
sage: ring = PolynomialRing(ZZ, 't')
sage: t = ring.gen()
sage: p1 = g.ihara_zeta_function()
sage: p2 = (1-t^2)*(1-t)*(1-2*t)*(1+t+2*t^2)^3
sage: p1 == p2
False
</pre>
TicketchapotonWed, 15 Jan 2014 11:06:29 GMT
https://trac.sagemath.org/ticket/15662#comment:15
https://trac.sagemath.org/ticket/15662#comment:15
<p>
Their answer does not have the right degree. Maybe a typo in the article ?
</p>
<p>
For K5, there is a value in <a class="ext-link" href="http://math.ucsd.edu/~aterras/snowbird.pdf"><span class="icon"></span>http://math.ucsd.edu/~aterras/snowbird.pdf</a>, which also does not agree with ours (just missing a power in some factor), and also does not have the right degree. Another typo ?
</p>
<p>
Either we are wrong or we need to find a more serious place to look for the correct values.
</p>
TicketncohenWed, 15 Jan 2014 11:08:36 GMT
https://trac.sagemath.org/ticket/15662#comment:16
https://trac.sagemath.org/ticket/15662#comment:16
<p>
Yooooooooo !
</p>
<blockquote class="citation">
<p>
Their answer does not have the right degree. Maybe a typo in the article ?
</p>
</blockquote>
<p>
Noooooooo idea <code>O_o</code>
</p>
<blockquote class="citation">
<p>
For K5, there is a value in <a class="ext-link" href="http://math.ucsd.edu/~aterras/snowbird.pdf"><span class="icon"></span>http://math.ucsd.edu/~aterras/snowbird.pdf</a>, which also does not agree with ours (just missing a power in some factor), and also does not have the right degree. Another typo ?
</p>
<p>
Either we are wrong or we need to find a more serious place to look for the correct values.
</p>
</blockquote>
<p>
Hmmm... May be worth sending them an email to ask. They may like to learn that this is being implemented somewhere by the way <code>;-)</code>
</p>
<p>
Nathann
</p>
TicketchapotonWed, 15 Jan 2014 11:10:47 GMT
https://trac.sagemath.org/ticket/15662#comment:17
https://trac.sagemath.org/ticket/15662#comment:17
<p>
Sorry, I guess my argument about the degree is wrong.. It is not necessarily twice the number of edges..
</p>
TicketchapotonWed, 15 Jan 2014 11:17:02 GMT
https://trac.sagemath.org/ticket/15662#comment:18
https://trac.sagemath.org/ticket/15662#comment:18
<p>
you forgot the power of <code>(1-t^2)</code> when checking the K4 result in the Bull. AMS paper:
</p>
<pre class="wiki">sage: g=graphs.CompleteGraph(4)
sage: p1=g.ihara_zeta_function()
sage: p2=(1-t^2)**2*(1-t)*(1-2*t)*(1+t+2*t^2)^3
sage: p1==p2
True
</pre>
TicketncohenWed, 15 Jan 2014 11:23:49 GMT
https://trac.sagemath.org/ticket/15662#comment:19
https://trac.sagemath.org/ticket/15662#comment:19
<p>
Oh. Sorry <code>O_o</code>
</p>
<p>
I am trying to load the paper again but the ams's website is in a bad mood. Does the value for K_5 coincide with the snowbird paper too ? If so we just need to update the one-line description of the method in graph.py (which does not match the one in the function's docstring) and the patch can go !
</p>
<p>
Nathann
</p>
TicketchapotonWed, 15 Jan 2014 13:35:43 GMT
https://trac.sagemath.org/ticket/15662#comment:20
https://trac.sagemath.org/ticket/15662#comment:20
<p>
Nathann, it seems that you have not pulled the latest version (done yesterday evening) which corrects the names and minor details !
</p>
<p>
I really think that the results are correct. The only discrepancy with all the results in the literature is in the case of K5, where several people seems to have copy-pasted the same result. This could very-well be wrong everywhere.
</p>
TicketncohenWed, 15 Jan 2014 13:39:08 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/15662#comment:21
https://trac.sagemath.org/ticket/15662#comment:21
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
<p>
Yoooooooo !
</p>
<blockquote class="citation">
<p>
Nathann, it seems that you have not pulled the latest version (done yesterday evening) which corrects the names and minor details !
</p>
</blockquote>
<p>
<code>T_T</code>
</p>
<p>
Sorry again. I had noted somewhere in my head that this had to be done, and forgot that you had changed the name of the function since. Sorry for this second wrong information <code>:-P</code>
</p>
<blockquote class="citation">
<p>
I really think that the results are correct. The only discrepancy with all the results in the literature is in the case of K5, where several people seems to have copy-pasted the same result. This could very-well be wrong everywhere.
</p>
</blockquote>
<p>
Okayokay. Positive review then. What would you think of sending an email to those guys to ask them what they think of it ? It's good to let them know this is available somewhere, and can either let us fix a bug here or let them fix a bug in their paper.
</p>
<p>
Thanks for this patch ! Sorry for the long review and errors <code>^^;</code>
</p>
<p>
Nathann
</p>
TicketchapotonWed, 15 Jan 2014 14:29:29 GMT
https://trac.sagemath.org/ticket/15662#comment:22
https://trac.sagemath.org/ticket/15662#comment:22
<p>
Thanks for the review !
</p>
TicketvbraunThu, 16 Jan 2014 05:32:18 GMT
https://trac.sagemath.org/ticket/15662#comment:23
https://trac.sagemath.org/ticket/15662#comment:23
<p>
Merge conflict... please merge in 6.1.beta5 & resolve.
</p>
TicketgitThu, 16 Jan 2014 08:27:03 GMTstatus, commit changed
https://trac.sagemath.org/ticket/15662#comment:24
https://trac.sagemath.org/ticket/15662#comment:24
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
changed from <em>403fd968aefe0eaf3b9e72f4ec79ba8ac7d9aad5</em> to <em>10181d9dba18f37b031d3761bcfdcfc75bf4a8cf</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=10181d9dba18f37b031d3761bcfdcfc75bf4a8cf"><span class="icon"></span>10181d9</a></td><td><code>trac #15662: Rebase on 6.1.beta5</code>
</td></tr></table>
TicketncohenThu, 16 Jan 2014 08:27:32 GMTstatus changed
https://trac.sagemath.org/ticket/15662#comment:25
https://trac.sagemath.org/ticket/15662#comment:25
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Done. It conflicted with <code>kirchhoff_symanzik_polynomial</code>.
</p>
<p>
Nathann
</p>
TicketvbraunFri, 17 Jan 2014 04:16:19 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/15662#comment:26
https://trac.sagemath.org/ticket/15662#comment:26
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
Ticket