# PermuteSubgraph not working? (Combinatorica)

I am trying to write a code to perform the QAP partialling analysis (here's a paper to know more) but the part in which I "scramble" the graph with PermuteSubgraph does nothing, I am actually not pretty sure of how I should use this command, as the guide says almost nothing and no example could be found..

Let's say that I create a graph by writing its adjacency matrix and using the AdjacencyGraph command

Needs["Combinatorica"]
a = {{0, 1, 0, 0, 0}, {1, 0, 1, 0, 0}, {0, 1, 0, 1, 1}, {0, 0, 1, 0,
1}, {0, 0, 1, 1, 0}};

ag = AdjacencyGraph[{1, 2, 3, 4, 5}, a, VertexLabels -> "Name"]


Problem is: according to what I found on the manual, it should be sufficient to write

PermuteSubgraph[ag, RandomSubset[Range[5]]]


to obtain some permutation of some random subgraph of my graph... But this does nothing!!

Please notice that what I would like to end with is the adjacency matrix of "each possible" permutation of the original graph, so if there is a way to obtain these "permuted adjacency matrices" without having to produce the graphs, that's a plus. (the quotes are because I will be dealing with really large networks, and then I may be able to take only a few of these permutations..)

Thank you in advance for the help,
- Stefano

• If you want all permutations, there is the Permutation command: Permutations[{1, 2, 3, 4}] lists all permutations of the elements 1,2,3,4. You could then take the matrix form of each of these. May 31, 2013 at 13:55
• Hi bill, I know about the Permutation command but how can I use it in this case? I'm not sure I understood what you mean by "take the matrix form of each of these" tho. Anyways, a permutation of a graph involves that if I switch node 2 with node 3, the 2nd and 3rd row and column of the adjacency matrix are switched too..so just applying a permutation to the adjacency matrix isn't useful as it just works on the rows - or I should write some function to permute, transpose and apply the same permutation again..but this could be more painful than what it looks like. May 31, 2013 at 14:50

You can use Permute to permute the rows or to permute both the rows and columns. For example, here is a matrix and a permutation of that matrix that swaps the 5th and 7th rows/columns.

m = RandomInteger[{0, 10}, {7, 7}];
perm = {1, 2, 3, 4, 7, 6, 5};
permm = Transpose[Permute[Transpose[Permute[m, perm]], perm]]


You can see this by

{m // MatrixForm, permm // MatrixForm}


For your larger problem, generate all the permutations, and then apply this function to the adjacency matrix a for each permutation.

a = {{0, 1, 0, 0, 0}, {1, 0, 1, 0, 0}, {0, 1, 0, 1, 1},
{0, 0, 1, 0, 1}, {0, 0, 1, 1, 0}};
allPerms = Permutations[{1, 2, 3, 4, 5}];
pm[mat_, perm_] := Transpose[Permute[Transpose[Permute[mat, perm]], perm]];


The application is then

allAdj = (pm[a, #] &) /@ allPerms


and you have all your adjacency matrices. As requested, this avoids producing all the graphs.

• Could just do m[[perm,perm]]. Caveat: I never remember if this is using the permutation, or its inverse. In this example they are the same, since the permutation is just a 2-cycle. In general if you need to reverse the permutation, can do simply iperm = Ordering[perm]` May 31, 2013 at 21:50
• Thank you Bill, it actually worked really well - and easily shown how absolutely unfeasible my approach is for large networks, but that's another point... (: Jun 10, 2013 at 8:07