Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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

share|improve this question
    
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. –  bill s May 31 '13 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. –  Stefano6884 May 31 '13 at 14:50

1 Answer 1

up vote 1 down vote accepted

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}

enter image description here

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.

share|improve this answer
    
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] –  Daniel Lichtblau May 31 '13 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... (: –  Stefano6884 Jun 10 '13 at 8:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.