2024-07-06 17:30:11 +0100 | received badge | ● Famous Question
(source)
|
2024-07-06 17:30:11 +0100 | received badge | ● Notable Question
(source)
|
2024-07-06 17:30:11 +0100 | received badge | ● Popular Question
(source)
|
2015-04-20 23:35:16 +0100 | answered a question | Add generator to a group? Combine generators of two groups? Thank you Vincent, that's what I am looking for.
I did the test to compare the speed, I did it first for small groups repeat 5000 times, then for large groups. test on small groups repeat 5000 times.
Runing time for ClosureGroup(H,J) is 0:00:25.837925
Runing time for ClosureGroup(H,w) is 0:00:21.571264
Runing time for PermutationGroup(H.gens()+J.gens()) is 0:00:00.943834
Runing time for PermutationGroup(H.gens()+list(w)) is 0:00:00.810795
test on large groups only 1 time.
Runing time for ClosureGroup(H,J) is 0:01:09.245275
Runing time for ClosureGroup(H,w) is 0:01:10.550019
Runing time for PermutationGroup(H.gens()+J.gens()) is 0:00:00.001400
Runing time for PermutationGroup(H.gens()+list(w)) is 0:00:00.000649
Notes: 25.837925 means 25 seconds, 0:01:09.245275 means 1 minutes and 9 seconds.
H and J are groups, w is a generator of a group, somehow PermutationGroup(H.gens()+J.gens()) is way faster than ClosureGroup , maybe ClosureGroup is doing some extra validation or computation? Here is the python/sage code: from sage.all import *
from datetime import datetime
case = 'small'
#case = 'large'
if case == 'small':
H = PermutationGroup([(2,3),(4,5)])
J = PermutationGroup([(1,2),(3,4,5)])
W = PermutationGroup([(1,4)])
w = W.gen(0)
iteration = 5000
print 'test on small groups repeat {0} times.'.format(iteration)
elif case == 'large':
H = CyclicPermutationGroup(200)
J = AlternatingGroup(200)
W = AlternatingGroup(200)
#J = DihedralGroup(10000)
#W = DihedralGroup(10000)
w = W.gen(1)
iteration = 1
print 'test on large groups only {0} time.'.format(iteration)
start = datetime.now()
for i in range(iteration):
P1_gap = gap.ClosureGroup(H,J) # close two group
P1 = PermutationGroup(gap_group=P1_gap)
print 'Runing time for ClosureGroup(H,J) is {0}'.format(str(datetime.now() - start))
start = datetime.now()
for i in range(iteration):
P2_gap = gap.ClosureGroup(H,w) # close one group with one generator
P2 = PermutationGroup(gap_group=P2_gap)
print 'Runing time for ClosureGroup(H,w) is {0}'.format(str(datetime.now() - start))
start = datetime.now()
for i in range(iteration):
P3 = PermutationGroup(H.gens()+J.gens())
print 'Runing time for PermutationGroup(H.gens()+J.gens()) is {0}'.format(str(datetime.now() - start))
start = datetime.now()
for i in range(iteration):
P4 = PermutationGroup(H.gens()+list(w))
print 'Runing time for PermutationGroup(H.gens()+list(w)) is {0}'.format(str(datetime.now() - start))
|
2015-04-20 01:28:16 +0100 | received badge | ● Scholar
(source)
|
2015-04-18 22:50:47 +0100 | asked a question | Add generator to a group? Combine generators of two groups? Hi guys, I am wondering how to efficiently do the following two things in Sage add a generator h to a existing group G to create a new group, e.g. from sage: h = (3,4)
sage: G = PermutationGroup([(1,2),(1,3)])
how to get a new group N with generators [(1,2),(1,3),(3,4)]. I can do this by using G.gens() and adding (3,4) to the list and calling PermutationGroup() ,
but it looks awkward, is there a more efficient way? create a new group from generators of two existing group, e.g. from sage: G = PermutationGroup([(1,2),(1,3)])
sage: H = PermutationGroup([(3,4)])
how to get a new group N with generators [(1,2),(1,3),(3,4)]? Currently I can do this by : N = PermutationGroup(G.gens()+H.gens()) Thanks,
Kevin |
2015-03-11 12:05:45 +0100 | received badge | ● Student
(source)
|
2015-03-10 20:20:58 +0100 | answered a question | checking isomorphism for weighted bipartite graph Thank 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. |
2015-03-10 07:14:29 +0100 | received badge | ● Editor
(source)
|
2015-03-10 07:13:07 +0100 | asked a question | 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? |