ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 12 Oct 2011 12:55:41 +0200Vertex connecitivity incomplete (pun intended)https://ask.sagemath.org/question/8358/vertex-connecitivity-incomplete-pun-intended/I am no graph theory expert, but the textbook I am learning from, and the Wikipedia article "Connecitivy (graph theory)" (which doesn't use my book as a reference, i.e., there are at least 2 books saying this) both say the vertex connectivity of a complete graph on n vertices is n-1. But, if you try to do graphs.CompleteGraph(whatever).vertex_connectivity(), it says
"There can be no vertex cut in a complete graph."
I looked at the code, and the fix is simple: Take
if g.is_clique():
raise ValueError("There can be no vertex cut in a complete graph.")
and make it
if g.is_clique():
return g.order()-1
But, I don't know how this fixing stuff works.
Second question, why does it return answers in the form 1.0 when the only possible values of this are integers?
Thirdly, there are a couple typos in the commenting of the code:
In a grid, the vertex connectivity is equal to the
minimum degree, in which case one of the two sets it
of cardinality `1`::
should be "two sets IS of"
For directed graphs, the strong connexity is tested
through the dedicated function::
I believe should be "strong vertex connectivity". Maybe connexity is okay but I am guessing it's a typo.
Fourthly, can we make "graph theory" a tag?Sun, 09 Oct 2011 10:36:07 +0200https://ask.sagemath.org/question/8358/vertex-connecitivity-incomplete-pun-intended/Comment by parzan for <p>I am no graph theory expert, but the textbook I am learning from, and the Wikipedia article "Connecitivy (graph theory)" (which doesn't use my book as a reference, i.e., there are at least 2 books saying this) both say the vertex connectivity of a complete graph on n vertices is n-1. But, if you try to do graphs.CompleteGraph(whatever).vertex_connectivity(), it says </p>
<p>"There can be no vertex cut in a complete graph."</p>
<p>I looked at the code, and the fix is simple: Take</p>
<pre><code>if g.is_clique():
raise ValueError("There can be no vertex cut in a complete graph.")
</code></pre>
<p>and make it</p>
<pre><code>if g.is_clique():
return g.order()-1
</code></pre>
<p>But, I don't know how this fixing stuff works.</p>
<p>Second question, why does it return answers in the form 1.0 when the only possible values of this are integers?</p>
<p>Thirdly, there are a couple typos in the commenting of the code:</p>
<p>In a grid, the vertex connectivity is equal to the
minimum degree, in which case one of the two sets it
of cardinality <code>1</code>::</p>
<p>should be "two sets IS of"</p>
<p>For directed graphs, the strong connexity is tested
through the dedicated function::</p>
<p>I believe should be "strong vertex connectivity". Maybe connexity is okay but I am guessing it's a typo.</p>
<p>Fourthly, can we make "graph theory" a tag?</p>
https://ask.sagemath.org/question/8358/vertex-connecitivity-incomplete-pun-intended/?comment=21163#post-id-21163Oops, I am a moron for thinking that "graph" is only the combinatorist's graph :)Sun, 09 Oct 2011 12:40:32 +0200https://ask.sagemath.org/question/8358/vertex-connecitivity-incomplete-pun-intended/?comment=21163#post-id-21163Comment by G-Sage for <p>I am no graph theory expert, but the textbook I am learning from, and the Wikipedia article "Connecitivy (graph theory)" (which doesn't use my book as a reference, i.e., there are at least 2 books saying this) both say the vertex connectivity of a complete graph on n vertices is n-1. But, if you try to do graphs.CompleteGraph(whatever).vertex_connectivity(), it says </p>
<p>"There can be no vertex cut in a complete graph."</p>
<p>I looked at the code, and the fix is simple: Take</p>
<pre><code>if g.is_clique():
raise ValueError("There can be no vertex cut in a complete graph.")
</code></pre>
<p>and make it</p>
<pre><code>if g.is_clique():
return g.order()-1
</code></pre>
<p>But, I don't know how this fixing stuff works.</p>
<p>Second question, why does it return answers in the form 1.0 when the only possible values of this are integers?</p>
<p>Thirdly, there are a couple typos in the commenting of the code:</p>
<p>In a grid, the vertex connectivity is equal to the
minimum degree, in which case one of the two sets it
of cardinality <code>1</code>::</p>
<p>should be "two sets IS of"</p>
<p>For directed graphs, the strong connexity is tested
through the dedicated function::</p>
<p>I believe should be "strong vertex connectivity". Maybe connexity is okay but I am guessing it's a typo.</p>
<p>Fourthly, can we make "graph theory" a tag?</p>
https://ask.sagemath.org/question/8358/vertex-connecitivity-incomplete-pun-intended/?comment=21164#post-id-21164@ parzan I'm a moron. Yea, thanks for doing that. They probably shouldn't be merged. If I think graph, there's the calculus meaning and the graph theory meaning. If my problem has to do with graph theory, I'd probably use graph theory. If I'm talking about the graph of some function, I'd probably use graph.Sun, 09 Oct 2011 12:20:38 +0200https://ask.sagemath.org/question/8358/vertex-connecitivity-incomplete-pun-intended/?comment=21164#post-id-21164Comment by parzan for <p>I am no graph theory expert, but the textbook I am learning from, and the Wikipedia article "Connecitivy (graph theory)" (which doesn't use my book as a reference, i.e., there are at least 2 books saying this) both say the vertex connectivity of a complete graph on n vertices is n-1. But, if you try to do graphs.CompleteGraph(whatever).vertex_connectivity(), it says </p>
<p>"There can be no vertex cut in a complete graph."</p>
<p>I looked at the code, and the fix is simple: Take</p>
<pre><code>if g.is_clique():
raise ValueError("There can be no vertex cut in a complete graph.")
</code></pre>
<p>and make it</p>
<pre><code>if g.is_clique():
return g.order()-1
</code></pre>
<p>But, I don't know how this fixing stuff works.</p>
<p>Second question, why does it return answers in the form 1.0 when the only possible values of this are integers?</p>
<p>Thirdly, there are a couple typos in the commenting of the code:</p>
<p>In a grid, the vertex connectivity is equal to the
minimum degree, in which case one of the two sets it
of cardinality <code>1</code>::</p>
<p>should be "two sets IS of"</p>
<p>For directed graphs, the strong connexity is tested
through the dedicated function::</p>
<p>I believe should be "strong vertex connectivity". Maybe connexity is okay but I am guessing it's a typo.</p>
<p>Fourthly, can we make "graph theory" a tag?</p>
https://ask.sagemath.org/question/8358/vertex-connecitivity-incomplete-pun-intended/?comment=21165#post-id-21165I retagged according to your last sentence - if you don't like it you can change it back. Currently there are "graph", "graphs" and "graph_theory" tags - perhaps they should all be merged.Sun, 09 Oct 2011 12:04:44 +0200https://ask.sagemath.org/question/8358/vertex-connecitivity-incomplete-pun-intended/?comment=21165#post-id-21165Comment by G-Sage for <p>I am no graph theory expert, but the textbook I am learning from, and the Wikipedia article "Connecitivy (graph theory)" (which doesn't use my book as a reference, i.e., there are at least 2 books saying this) both say the vertex connectivity of a complete graph on n vertices is n-1. But, if you try to do graphs.CompleteGraph(whatever).vertex_connectivity(), it says </p>
<p>"There can be no vertex cut in a complete graph."</p>
<p>I looked at the code, and the fix is simple: Take</p>
<pre><code>if g.is_clique():
raise ValueError("There can be no vertex cut in a complete graph.")
</code></pre>
<p>and make it</p>
<pre><code>if g.is_clique():
return g.order()-1
</code></pre>
<p>But, I don't know how this fixing stuff works.</p>
<p>Second question, why does it return answers in the form 1.0 when the only possible values of this are integers?</p>
<p>Thirdly, there are a couple typos in the commenting of the code:</p>
<p>In a grid, the vertex connectivity is equal to the
minimum degree, in which case one of the two sets it
of cardinality <code>1</code>::</p>
<p>should be "two sets IS of"</p>
<p>For directed graphs, the strong connexity is tested
through the dedicated function::</p>
<p>I believe should be "strong vertex connectivity". Maybe connexity is okay but I am guessing it's a typo.</p>
<p>Fourthly, can we make "graph theory" a tag?</p>
https://ask.sagemath.org/question/8358/vertex-connecitivity-incomplete-pun-intended/?comment=21156#post-id-21156Maybe neither of us are morons :) Just little mistakes.Sun, 09 Oct 2011 15:42:55 +0200https://ask.sagemath.org/question/8358/vertex-connecitivity-incomplete-pun-intended/?comment=21156#post-id-21156Answer by Nathann for <p>I am no graph theory expert, but the textbook I am learning from, and the Wikipedia article "Connecitivy (graph theory)" (which doesn't use my book as a reference, i.e., there are at least 2 books saying this) both say the vertex connectivity of a complete graph on n vertices is n-1. But, if you try to do graphs.CompleteGraph(whatever).vertex_connectivity(), it says </p>
<p>"There can be no vertex cut in a complete graph."</p>
<p>I looked at the code, and the fix is simple: Take</p>
<pre><code>if g.is_clique():
raise ValueError("There can be no vertex cut in a complete graph.")
</code></pre>
<p>and make it</p>
<pre><code>if g.is_clique():
return g.order()-1
</code></pre>
<p>But, I don't know how this fixing stuff works.</p>
<p>Second question, why does it return answers in the form 1.0 when the only possible values of this are integers?</p>
<p>Thirdly, there are a couple typos in the commenting of the code:</p>
<p>In a grid, the vertex connectivity is equal to the
minimum degree, in which case one of the two sets it
of cardinality <code>1</code>::</p>
<p>should be "two sets IS of"</p>
<p>For directed graphs, the strong connexity is tested
through the dedicated function::</p>
<p>I believe should be "strong vertex connectivity". Maybe connexity is okay but I am guessing it's a typo.</p>
<p>Fourthly, can we make "graph theory" a tag?</p>
https://ask.sagemath.org/question/8358/vertex-connecitivity-incomplete-pun-intended/?answer=12731#post-id-12731Helloooooooo !!!
My mistake, as usual :-)
So, to answer your points :
1) The connectivity of a clique on n vertices is n-1. Yes, you are right, all the textbooks say so, this is the convention, and I just thought that "it makes no sense to look for a vertex cut in a clique" when I coded this method. I'll fix that in a patch.
2) The answer returns 1.0 instead of the expected 1. The reason is that this method also handles weighted cut, but you are right when you say that it feels odd to get a non-integer value. This is actually fixed by patch 11367 which is *waiting for a reiew* right now. If you want to give it a review, it will finally be merged into Sage : I can write many patches but I can not review my own patches myself `:-)`
3) I will fix the typ in the same patch, Thanks !
4) Well, this is actually testing for strongconnectivity but I did not find it very hard, as this is what you expect to compute when you try to compute the connectivity of a directed graph. One can cast it to an undirected graph otherwise... Do you think it is a bad idea ?
NathannSun, 09 Oct 2011 12:58:57 +0200https://ask.sagemath.org/question/8358/vertex-connecitivity-incomplete-pun-intended/?answer=12731#post-id-12731Comment by G-Sage for <p>Helloooooooo !!!</p>
<p>My mistake, as usual :-)</p>
<p>So, to answer your points :</p>
<p>1) The connectivity of a clique on n vertices is n-1. Yes, you are right, all the textbooks say so, this is the convention, and I just thought that "it makes no sense to look for a vertex cut in a clique" when I coded this method. I'll fix that in a patch.</p>
<p>2) The answer returns 1.0 instead of the expected 1. The reason is that this method also handles weighted cut, but you are right when you say that it feels odd to get a non-integer value. This is actually fixed by patch 11367 which is <em>waiting for a reiew</em> right now. If you want to give it a review, it will finally be merged into Sage : I can write many patches but I can not review my own patches myself <code>:-)</code></p>
<p>3) I will fix the typ in the same patch, Thanks ! </p>
<p>4) Well, this is actually testing for strongconnectivity but I did not find it very hard, as this is what you expect to compute when you try to compute the connectivity of a directed graph. One can cast it to an undirected graph otherwise... Do you think it is a bad idea ?</p>
<p>Nathann</p>
https://ask.sagemath.org/question/8358/vertex-connecitivity-incomplete-pun-intended/?comment=21157#post-id-21157@Nathann How do I review a patch?Sun, 09 Oct 2011 15:31:42 +0200https://ask.sagemath.org/question/8358/vertex-connecitivity-incomplete-pun-intended/?comment=21157#post-id-21157Comment by G-Sage for <p>Helloooooooo !!!</p>
<p>My mistake, as usual :-)</p>
<p>So, to answer your points :</p>
<p>1) The connectivity of a clique on n vertices is n-1. Yes, you are right, all the textbooks say so, this is the convention, and I just thought that "it makes no sense to look for a vertex cut in a clique" when I coded this method. I'll fix that in a patch.</p>
<p>2) The answer returns 1.0 instead of the expected 1. The reason is that this method also handles weighted cut, but you are right when you say that it feels odd to get a non-integer value. This is actually fixed by patch 11367 which is <em>waiting for a reiew</em> right now. If you want to give it a review, it will finally be merged into Sage : I can write many patches but I can not review my own patches myself <code>:-)</code></p>
<p>3) I will fix the typ in the same patch, Thanks ! </p>
<p>4) Well, this is actually testing for strongconnectivity but I did not find it very hard, as this is what you expect to compute when you try to compute the connectivity of a directed graph. One can cast it to an undirected graph otherwise... Do you think it is a bad idea ?</p>
<p>Nathann</p>
https://ask.sagemath.org/question/8358/vertex-connecitivity-incomplete-pun-intended/?comment=21158#post-id-21158For your number 4, perhaps it's my lack of expertise. After your reply, I do recall the notion of strong connectivity, so the word "vertex" that I put above does not belong. But, there is a typo still, I think, because it says "connexity" instead of "connectivity". Any way, thanks for making this function in the first place and thanks for continuing to work on it. It makes things really simple when I'm working on stuff and a large portion of what I want is built in.Sun, 09 Oct 2011 15:30:55 +0200https://ask.sagemath.org/question/8358/vertex-connecitivity-incomplete-pun-intended/?comment=21158#post-id-21158Comment by Nathann for <p>Helloooooooo !!!</p>
<p>My mistake, as usual :-)</p>
<p>So, to answer your points :</p>
<p>1) The connectivity of a clique on n vertices is n-1. Yes, you are right, all the textbooks say so, this is the convention, and I just thought that "it makes no sense to look for a vertex cut in a clique" when I coded this method. I'll fix that in a patch.</p>
<p>2) The answer returns 1.0 instead of the expected 1. The reason is that this method also handles weighted cut, but you are right when you say that it feels odd to get a non-integer value. This is actually fixed by patch 11367 which is <em>waiting for a reiew</em> right now. If you want to give it a review, it will finally be merged into Sage : I can write many patches but I can not review my own patches myself <code>:-)</code></p>
<p>3) I will fix the typ in the same patch, Thanks ! </p>
<p>4) Well, this is actually testing for strongconnectivity but I did not find it very hard, as this is what you expect to compute when you try to compute the connectivity of a directed graph. One can cast it to an undirected graph otherwise... Do you think it is a bad idea ?</p>
<p>Nathann</p>
https://ask.sagemath.org/question/8358/vertex-connecitivity-incomplete-pun-intended/?comment=21133#post-id-21133I just updated the patch at this address : http://trac.sagemath.org/sage_trac/ticket/11910. I hope it fixes all the points you addressed ! The other patch I mentionned, 11367, just got reviewed by a colleague today, so only 11910 is left to check. Reviewing a patch is (at first) not trivial, so there is a manual for that just there : http://www.sagemath.org/doc/developer/. If you have any question, you can scream for help on the sage-devel google group or on our IRC channel http://www.sagemath.org/help-irc.htmlWed, 12 Oct 2011 12:55:41 +0200https://ask.sagemath.org/question/8358/vertex-connecitivity-incomplete-pun-intended/?comment=21133#post-id-21133