How to recognise DiGraph equivalence

asked 2011-09-27 14:35:00 +0200

GaryMak
107 ●9 ●14 ●25

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?

Thanks

edit retag flag offensive close merge delete

add a comment

answered 2011-09-27 15:09:41 +0200

Nathann
1615 ●2 ●15 ●36

Hellooo !!!

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 :-)

Nathann

edit flag offensive delete link

Comments

Hi 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. Gary

GaryMak ( 2011-09-27 15:57:02 +0200 )edit

Hello ! 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)

Nathann ( 2011-10-12 13:00:32 +0200 )edit

Oops sorry I only just saw this - thank you!

GaryMak ( 2011-12-05 07:36:37 +0200 )edit

add a comment

How to recognise DiGraph equivalence

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

How to recognise DiGraph equivalence edit

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

How to recognise DiGraph equivalence