ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 05 Dec 2011 00:36:37 -0600How to recognise DiGraph equivalencehttp://ask.sagemath.org/question/8348/how-to-recognise-digraph-equivalence/Hi -
I am trying to check that a "manual" calculation I did on posets is correct.
my starting point is a Matlab-generated upper-triangular 60x60 adjacency matrix M representing a DiGraph G or P=Poset(G); I have generated a minimal (ie covering relations only) 60x60 adjacency matrix from it in two ways. First by letting SAGE reduce it using PP=P.cover_relations(), and the other by reducing M "manually" in Matlab, then exporting that matrix Q to SAGE and using the same function on it to get it into the same format. I would like to show PP=Q in some sense.
I tried to check equality (==) between the graph objects, and the posets, and the graphs/posets obtained by re-setting the output of the cover_relations function to be a DiGraph all over again, and even setting those things to be adjacency matrices ... but even though I have laboriously checked that the 2 objects ARE indeed the same (by comparing the edges one-by-one), I nevertheless cannot get SAGE to agree!!
The output of the cover_relations function seems to be the sticking point - it is a sort-of matrix but not with any consistent ordering of the edges - hence even though the sets of edges are clearly the same, the different ordering seems to throw the comparison function off.
What am I missing please?
ThanksTue, 27 Sep 2011 07:35:00 -0500http://ask.sagemath.org/question/8348/how-to-recognise-digraph-equivalence/Answer by Nathann for <p>Hi -
I am trying to check that a "manual" calculation I did on posets is correct.</p>
<p>my starting point is a Matlab-generated upper-triangular 60x60 adjacency matrix M representing a DiGraph G or P=Poset(G); I have generated a minimal (ie covering relations only) 60x60 adjacency matrix from it in two ways. First by letting SAGE reduce it using PP=P.cover_relations(), and the other by reducing M "manually" in Matlab, then exporting that matrix Q to SAGE and using the same function on it to get it into the same format. I would like to show PP=Q in some sense.</p>
<p>I tried to check equality (==) between the graph objects, and the posets, and the graphs/posets obtained by re-setting the output of the cover_relations function to be a DiGraph all over again, and even setting those things to be adjacency matrices ... but even though I have laboriously checked that the 2 objects ARE indeed the same (by comparing the edges one-by-one), I nevertheless cannot get SAGE to agree!! </p>
<p>The output of the cover_relations function seems to be the sticking point - it is a sort-of matrix but not with any consistent ordering of the edges - hence even though the sets of edges are clearly the same, the different ordering seems to throw the comparison function off.</p>
<p>What am I missing please?</p>
<p>Thanks</p>
http://ask.sagemath.org/question/8348/how-to-recognise-digraph-equivalence/?answer=12694#post-id-12694Hellooo !!!
If you have noticed that the orderings in the vertices are not the same, then most probably the two graphs will not be equal. To be equal, if I am not mistaken, the two adjacency matrices of the graphs first need to be equal (element per element). Of course, they will not be if the rows have been reordered. Even when this is true, Sage may say that two graphs are not equal if one has labeled edges why the other doesn't (this is not your case), or if the names of the vertices are somehow different. Beware, because this can also happen in tricky cases, I suspect it may answer that the graphs are different if you have in one graph vertices which are Integer() object, and in the other vertices which are int objects.
Well. Anyway, whenever you have two graphs which you suspect may be "equivalent", you are probably looking for the is.isomorphic method. This will tell you whether there is a bijection between the vertices such that each edge is sent to an edge, and each nonedge to a nonedge.
It can also tell you *how* to permute the vertices such that this is true. For instance :
sage: g = graphs.PetersenGraph()
sage: h = graphs.KneserGraph(5,2)
sage: g.is_isomorphic(h, certify = True)
(True, {0: {4, 5}, 1: {1, 3}, 2: {2, 5}, 3: {1, 4}, 4: {2, 3}, 5: {1, 2}, 6: {2, 4}, 7: {3, 4}, 8: {3, 5}, 9: {1, 5}})
Tell me if that help `:-)`
NathannTue, 27 Sep 2011 08:09:41 -0500http://ask.sagemath.org/question/8348/how-to-recognise-digraph-equivalence/?answer=12694#post-id-12694Comment by GaryMak for <p>Hellooo !!!</p>
<p>If you have noticed that the orderings in the vertices are not the same, then most probably the two graphs will not be equal. To be equal, if I am not mistaken, the two adjacency matrices of the graphs first need to be equal (element per element). Of course, they will not be if the rows have been reordered. Even when this is true, Sage may say that two graphs are not equal if one has labeled edges why the other doesn't (this is not your case), or if the names of the vertices are somehow different. Beware, because this can also happen in tricky cases, I suspect it may answer that the graphs are different if you have in one graph vertices which are Integer() object, and in the other vertices which are int objects.</p>
<p>Well. Anyway, whenever you have two graphs which you suspect may be "equivalent", you are probably looking for the is.isomorphic method. This will tell you whether there is a bijection between the vertices such that each edge is sent to an edge, and each nonedge to a nonedge.</p>
<p>It can also tell you <em>how</em> to permute the vertices such that this is true. For instance :</p>
<pre><code>sage: g = graphs.PetersenGraph()
sage: h = graphs.KneserGraph(5,2)
sage: g.is_isomorphic(h, certify = True)
(True, {0: {4, 5}, 1: {1, 3}, 2: {2, 5}, 3: {1, 4}, 4: {2, 3}, 5: {1, 2}, 6: {2, 4}, 7: {3, 4}, 8: {3, 5}, 9: {1, 5}})
</code></pre>
<p>Tell me if that help <code>:-)</code></p>
<p>Nathann</p>
http://ask.sagemath.org/question/8348/how-to-recognise-digraph-equivalence/?comment=20759#post-id-20759Oops sorry I only just saw this - thank you!Mon, 05 Dec 2011 00:36:37 -0600http://ask.sagemath.org/question/8348/how-to-recognise-digraph-equivalence/?comment=20759#post-id-20759Comment by GaryMak for <p>Hellooo !!!</p>
<p>If you have noticed that the orderings in the vertices are not the same, then most probably the two graphs will not be equal. To be equal, if I am not mistaken, the two adjacency matrices of the graphs first need to be equal (element per element). Of course, they will not be if the rows have been reordered. Even when this is true, Sage may say that two graphs are not equal if one has labeled edges why the other doesn't (this is not your case), or if the names of the vertices are somehow different. Beware, because this can also happen in tricky cases, I suspect it may answer that the graphs are different if you have in one graph vertices which are Integer() object, and in the other vertices which are int objects.</p>
<p>Well. Anyway, whenever you have two graphs which you suspect may be "equivalent", you are probably looking for the is.isomorphic method. This will tell you whether there is a bijection between the vertices such that each edge is sent to an edge, and each nonedge to a nonedge.</p>
<p>It can also tell you <em>how</em> to permute the vertices such that this is true. For instance :</p>
<pre><code>sage: g = graphs.PetersenGraph()
sage: h = graphs.KneserGraph(5,2)
sage: g.is_isomorphic(h, certify = True)
(True, {0: {4, 5}, 1: {1, 3}, 2: {2, 5}, 3: {1, 4}, 4: {2, 3}, 5: {1, 2}, 6: {2, 4}, 7: {3, 4}, 8: {3, 5}, 9: {1, 5}})
</code></pre>
<p>Tell me if that help <code>:-)</code></p>
<p>Nathann</p>
http://ask.sagemath.org/question/8348/how-to-recognise-digraph-equivalence/?comment=21191#post-id-21191Hi Nathann - thanks a lot - that is_isomorphic fn does indeed work! Regarding your earlier explanation, the graphs are specified in the input stage as a series of edges in the form (23,45) etc, so I was expecting SAGE to understand the node labels as 1-60 (as indeed it seems to when one simply reads in the adjacency matrix and does nothing with it). Indeed it comes up with the very same pairs [a,b],[c,d] etc from the cover_relations() fn in both cases, just in a slightly different order. But then when I try to re-create the adjacency matrices from these square-bracket outputs, as you say the rows are all higgledy-piggledy. All a bit of a mystery to me I am afraid, but at least you've solved the problem! thanks again. GaryTue, 27 Sep 2011 08:57:02 -0500http://ask.sagemath.org/question/8348/how-to-recognise-digraph-equivalence/?comment=21191#post-id-21191Comment by Nathann for <p>Hellooo !!!</p>
<p>If you have noticed that the orderings in the vertices are not the same, then most probably the two graphs will not be equal. To be equal, if I am not mistaken, the two adjacency matrices of the graphs first need to be equal (element per element). Of course, they will not be if the rows have been reordered. Even when this is true, Sage may say that two graphs are not equal if one has labeled edges why the other doesn't (this is not your case), or if the names of the vertices are somehow different. Beware, because this can also happen in tricky cases, I suspect it may answer that the graphs are different if you have in one graph vertices which are Integer() object, and in the other vertices which are int objects.</p>
<p>Well. Anyway, whenever you have two graphs which you suspect may be "equivalent", you are probably looking for the is.isomorphic method. This will tell you whether there is a bijection between the vertices such that each edge is sent to an edge, and each nonedge to a nonedge.</p>
<p>It can also tell you <em>how</em> to permute the vertices such that this is true. For instance :</p>
<pre><code>sage: g = graphs.PetersenGraph()
sage: h = graphs.KneserGraph(5,2)
sage: g.is_isomorphic(h, certify = True)
(True, {0: {4, 5}, 1: {1, 3}, 2: {2, 5}, 3: {1, 4}, 4: {2, 3}, 5: {1, 2}, 6: {2, 4}, 7: {3, 4}, 8: {3, 5}, 9: {1, 5}})
</code></pre>
<p>Tell me if that help <code>:-)</code></p>
<p>Nathann</p>
http://ask.sagemath.org/question/8348/how-to-recognise-digraph-equivalence/?comment=21132#post-id-21132Hello ! This is because the vertices are sorted before being returned, that's a (bad) trick we use to keep sure the results of the functions are the same on any architecture... The problems boils down to the fact that when you iterate on the elements of a dictionary, the ordering itself depends on the architecture :-) (sorry about answering so late, I received no alert that you had answered on this thread ^^; sage-devel is still better than this website for many things :-p)Wed, 12 Oct 2011 06:00:32 -0500http://ask.sagemath.org/question/8348/how-to-recognise-digraph-equivalence/?comment=21132#post-id-21132