Sparse matrix re-ordering
조회 수: 3 (최근 30일)
이전 댓글 표시
Hello everyone,
I have a question I'd like to ask.
When you have a (sparse) matrix, you can plot the graph and find the degree of nodes. When some re-ordering is applied, the sequence of the nodes changes form the lowest degree to the highest degree.
Example: suppose I have a 10 node system with the following degrees: 3-3-5-3-5-2-6-3-1-3. (Node:1-2-3-4-5-6-7-8-9-10)
Now I apply a re-ordering based on the degrees, and my node sequence now becomes: 9-6-1-2-4-8-10-3-5-7.
How do I find the updated matrix from this new sequence? Is there a specific MATLAB function, or do I need to write some code?
Any help is really appreciated.
Romeo
댓글 수: 1
James Tursa
2020년 3월 11일
Maybe I am not understanding the question, but why can't you just use the sort( ) function? Can you give a complete example using MATLAB variables of inputs and desired outputs?
채택된 답변
the cyclist
2020년 3월 13일
I tried to generalize your code as follows.
A = [-1 -2 0 4 0 0 0 1 0 0;
3 2 0 0 0 0 -4 0 0 3;
0 0 5 7 -6 0 3 4 0 1;
2 0 1 1 -1 0 0 0 0 0;
0 0 2 4 -1 8 6 0 0 3;
0 0 0 0 2 -2 4 0 0 0;
0 3 -3 0 1 9 5 -3 -6 0;
-1 0 2 0 0 0 4 -5 0 0;
0 0 0 0 0 0 -1 0 2 0;
0 2 2 0 5 0 0 0 0 7];
% Store the graph info for the original array, in the first element of a
% new cell array
G{1} = graph(A,'upper');
N = length(A);
% Initialize the output as an empty vector that we will append to
output = nan(N,1);
original = 1:N;
for i = 1:N
% Find the degree list (and store for later inspection)
deg{i} = degree(simplify(G{i}));
% Sort the degree list
[deg{i},k] = sort(deg{i},'ascend');
% Remove lowest degree from graph, and store new graph
G{i+1} = rmnode(G{i},k(1));
% Add lowest degree position to output
output(i) = original(k(1));
% Delete the lowest degree position from the original list
original(k(1)) = [];
end
However, I don't get the same final output as you state. (The first few match with yours.)
I can't determine whose is incorrect. I tried to comment my code very carefully, so that you could follow what I did, and find a coding mistake.
댓글 수: 4
the cyclist
2020년 3월 24일
I actually did nothing other than modify your code to
- use cell arrays elements such as deg{1} instead of dynamically named variables such as deg_1.
- take advantage of those cell arrays, so that the loop could be written in a general way
To be frank, I never really tried to understand your actual algorithm, and I don't know much about graphs. I can take a look, but I don't know how much help I'll be.
추가 답변 (2개)
the cyclist
2020년 3월 11일
[sorted_nodes,index_to_sorting_order] = sort(nodes)
댓글 수: 2
the cyclist
2020년 3월 12일
It seems to me that you have all the information you need, from the original sorting and associated index. But, maybe I am misunderstanding. So, let's take a simple example, where we can do everything you want "by hand". Suppose your original node list is
nodes = [3 3 4 2];
Then my solution gives you the following information:
[sorted_nodes,index_to_sorting_order] = sort(nodes)
sorted_nodes =
2 3 3 4
index_to_sorting_order =
4 1 2 3
Can you tell us what exactly you expect for the output? (Please use MATLAB syntax to define it, if possible, and not just a description in words.) Don't worry about the algorithm to get there. Just what does the output needs to be.
Romeo Tahal
2020년 3월 12일
댓글 수: 2
the cyclist
2020년 3월 12일
편집: the cyclist
2020년 3월 12일
Of all of those variables you generated, which ones did you really need as output? (As opposed to variables that you just happened to generate because you needed them for later calculation.)
For example, do you only need that the input is the matrix A, and the output is
output = [9 6 1 10 4 2 3 5 7 8]
?
Or do you need the entire sequence of deg1, deg2, etc, and Gupd, Gupd1, etc?
This is exactly why I asked for you to tell us what is the output you need, and not the algorithm. (But it is handy to see how you got there, I suppose.)
참고 항목
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!