MATLAB Answers

How do I stop incidence function rearranging the edges of a graph?

1 view (last 30 days)
Hi,
I am using the graph function to create a graph from two lists of nodes. I then use the incidence function, to find the incidence matrix of this graph, but it autmoatically rearranges the edges. For example if I have the following node lists
s =
1
2
3
4
1
2
3
4
5
6
7
8
9
6
7
8
9
10
11
12
13
14
11
12
13
14
15
16
17
18
19
16
17
18
19
20
21
22
23
24
t =
2
3
4
5
6
7
8
9
10
7
8
9
10
11
12
13
14
15
12
13
14
15
16
17
18
19
20
17
18
19
20
21
22
23
24
25
22
23
24
25
I get the following incidence matrix by incidence(Graph(s,t))
Columns 1 through 27
-1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 1 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 1 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 -1 -1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 -1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 -1 -1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 -1 -1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 -1 -1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Columns 28 through 40
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
-1 -1 0 0 0 0 0 0 0 0 0 0 0
1 0 -1 -1 0 0 0 0 0 0 0 0 0
0 0 1 0 -1 -1 0 0 0 0 0 0 0
0 0 0 0 1 0 -1 -1 0 0 0 0 0
0 0 0 0 0 0 1 0 -1 0 0 0 0
0 1 0 0 0 0 0 0 0 -1 0 0 0
0 0 0 1 0 0 0 0 0 1 -1 0 0
0 0 0 0 0 1 0 0 0 0 1 -1 0
0 0 0 0 0 0 0 1 0 0 0 1 -1
0 0 0 0 0 0 0 0 1 0 0 0 1
How do I keep the columns of this resulting matrix in the same order as the edge lists? For example the second element of the first node list is 2, the second element of the second node list is 3, but for some reason the incidence function makes this the third column of the incidence matrix instead of the second column. And in place it makes what should be the fifth column into the second. How do I stop it doing this?
Thanks in advance,
Richard

Accepted Answer

Christine Tobler
Christine Tobler on 30 Nov 2020
The reordering isn't happening when the incidence of the graph is computed, but instead at the moment that the graph is constructed: The graph and digraph classes always standardize the order of the edges, the original order isn't preserved in the object.
If you just need the incidence matrix based on s and t, and using original ordering, you can compute this directly:
nn = max([s(:); t(:)]); % number of nodes
ne = length(s); % number of edges
inc = sparse([s(:) t(:)], (1:ne)'*[1 1], ones(ne,1)*[-1 1], nn, ne);
If you need the graph itself, too, you can make the original order of the edges to be stored as the Weight variable in the graph's Edges table.
g = graph(s, t, 1:length(s)); % Verify that g.Edges.Weight contains the original placement of each edge in the (s, t) inputs
inc2 = incidence(g);
inc2(:, g.Edges.Weight) = inc2;
isequal(inc, inc2)

More Answers (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!