2
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – bill s
    May 31, 2013 at 13:55
  • $\begingroup$ 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. $\endgroup$
    – Stefano6884
    May 31, 2013 at 14:50

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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] $\endgroup$
    – Daniel Lichtblau
    May 31, 2013 at 21:50
  • $\begingroup$ 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... (: $\endgroup$
    – Stefano6884
    Jun 10, 2013 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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