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.Tue, 10 Mar 2015 14:20:58 -0500checking isomorphism for weighted bipartite graphhttp://ask.sagemath.org/question/26130/checking-isomorphism-for-weighted-bipartite-graph/Hi, guys,
I am working on a problem involving checking if two weighted bipartite graphs are isomorphic.
I saw I can define a weighted graph in sage like this:
sage: X = Matrix([(0,0,1,1),(0,0,1,2),(0,1,1,0)])
sage: XX = BipartiteGraph(X,weighted=True)
sage: Y = Matrix([(1,0,2,0),(1,0,0,1),(1,0,1,0)])
sage: YY = BipartiteGraph(Y,weighted=True)
sage: W = Matrix([(1,0,2,0),(1,0,0,1),(1,0,2,0)])
sage: WW = BipartiteGraph(Z,weighted=True)
I swapped rows and columns of matrix defining X to get Y, so Y is isomorphic to X,
But since my graphs are weighted, I changed one element in Y from 1 to 2 to get W,
yet it still tell me XX and WW are isomorphic
sage: YY.is_isomorphic(XX)
True
sage: ZZ.is_isomorphic(XX)
True
Are there other functions I can use to check isomorphism for weighted bipartite graph?Tue, 10 Mar 2015 01:13:07 -0500http://ask.sagemath.org/question/26130/checking-isomorphism-for-weighted-bipartite-graph/Answer by Nathann for <p>Hi, guys,
I am working on a problem involving checking if two weighted bipartite graphs are isomorphic.
I saw I can define a weighted graph in sage like this:</p>
<pre><code>sage: X = Matrix([(0,0,1,1),(0,0,1,2),(0,1,1,0)])
sage: XX = BipartiteGraph(X,weighted=True)
sage: Y = Matrix([(1,0,2,0),(1,0,0,1),(1,0,1,0)])
sage: YY = BipartiteGraph(Y,weighted=True)
sage: W = Matrix([(1,0,2,0),(1,0,0,1),(1,0,2,0)])
sage: WW = BipartiteGraph(Z,weighted=True)
</code></pre>
<p>I swapped rows and columns of matrix defining X to get Y, so Y is isomorphic to X,
But since my graphs are weighted, I changed one element in Y from 1 to 2 to get W,
yet it still tell me XX and WW are isomorphic</p>
<pre><code>sage: YY.is_isomorphic(XX)
True
sage: ZZ.is_isomorphic(XX)
True
</code></pre>
<p>Are there other functions I can use to check isomorphism for weighted bipartite graph?</p>
http://ask.sagemath.org/question/26130/checking-isomorphism-for-weighted-bipartite-graph/?answer=26139#post-id-26139The documentation of is_isomorphic tells you that it handles labels on the edges. In order to solve your problem, try to convert your weights into edge labels.
Nathann Tue, 10 Mar 2015 12:29:01 -0500http://ask.sagemath.org/question/26130/checking-isomorphism-for-weighted-bipartite-graph/?answer=26139#post-id-26139Answer by skylibrary for <p>Hi, guys,
I am working on a problem involving checking if two weighted bipartite graphs are isomorphic.
I saw I can define a weighted graph in sage like this:</p>
<pre><code>sage: X = Matrix([(0,0,1,1),(0,0,1,2),(0,1,1,0)])
sage: XX = BipartiteGraph(X,weighted=True)
sage: Y = Matrix([(1,0,2,0),(1,0,0,1),(1,0,1,0)])
sage: YY = BipartiteGraph(Y,weighted=True)
sage: W = Matrix([(1,0,2,0),(1,0,0,1),(1,0,2,0)])
sage: WW = BipartiteGraph(Z,weighted=True)
</code></pre>
<p>I swapped rows and columns of matrix defining X to get Y, so Y is isomorphic to X,
But since my graphs are weighted, I changed one element in Y from 1 to 2 to get W,
yet it still tell me XX and WW are isomorphic</p>
<pre><code>sage: YY.is_isomorphic(XX)
True
sage: ZZ.is_isomorphic(XX)
True
</code></pre>
<p>Are there other functions I can use to check isomorphism for weighted bipartite graph?</p>
http://ask.sagemath.org/question/26130/checking-isomorphism-for-weighted-bipartite-graph/?answer=26140#post-id-26140Thank you for your help, I wasn't able to find the documentation for is_isomorphic yesterday, now I finally got it.
In fact, I don't even need to do the edge labeling, when I do WW = BipartiteGraph(Z,weighted=True), the numbers in the matrix are treated as weights, so I can get the result I want by just doing WW.is_isomorphic(XX,edge_labels=True).
In fact, I am interested in a more general isomorphism test.
For example, in X = Matrix([(1,1,2,2),(1,1,2,3),(1,2,2,1)]), I not only want to be able to treat swapping rows and columns as equivalent (which equivalent to change the labeling of nodes on the left and right of the biparitite graph separately), I can also do bijections on each rows. So for row one of X, (1,1,2,2) can be replaced with (2,2,1,1), for row two of X, (1,1,2,3) can be replaced with (1,1,3,2) (2,2,3,1) (2,2,1,3) (3,3,1,2) (3,3,2,1). I am wondering if there exist algorithms to do that directly?
Right now the only way I can think of is to first list all combinations of bijections, in this example. there are 2 * 6 * 2 = 24 equivalent cases, then for each of them, I do a isomorphism test with the original matrix, if at least one graph out of 24 is isomorphism with the original graph, I consider them equivalent. However, this approach will become intractable even the size of the matrix is not that big.Tue, 10 Mar 2015 14:20:58 -0500http://ask.sagemath.org/question/26130/checking-isomorphism-for-weighted-bipartite-graph/?answer=26140#post-id-26140