MATLAB Answers

0

Delete and add new edges in a graph

Asked by Deepa Maheshvare on 11 Sep 2019 at 8:59
Latest activity Edited by Deepa Maheshvare on 14 Sep 2019 at 15:09
Hello,
I am trying to add new nodes between two nodes that already exist in a graph.
For example, I have a graph with two nodes labelled '1' and '2'
If I have to add 4 nodes between nodes labelled '1' and '2' , the edge between nodes 1 and 2 is deleted, new nodes are added to the graph,
new edges are added.
The following code performs the above-mentioned steps.
NNode = 2;
tail = 1:NNode-1;
head = 2:NNode;
Graph = graph(tail,head);
plot(Graph);
Graph.Nodes.Name = cellstr(string(1:height(Graph.Nodes))');
% Add new nodes
nnew = 4 % number of new nodes
Graph = rmedge(Graph,1,2)
Graph = addnode(Graph, nnew)
Graph.Nodes.Name
to_add = vertcat('1',Graph.Nodes.Name(end-nnew+1:end),'2')
for node = 1:length(to_add)-1
head = to_add(node)
tail = to_add(node+1)
Graph = addedge(Graph,head,tail);
end
plot(Graph)
Graph.Nodes
Graph.Edges
I_inv = full(incidence(Graph))'
The following is the output of Graph.Edges
EndNodes
__________________
'1' 'Node3'
'2' 'Node6'
'Node3' 'Node4'
'Node4' 'Node5'
'Node5' 'Node6'
There is a problem that occurs while adding new edges. I am adding the last edge as addedge(Graph, 'Node6', '2').
However, in the above table we can see the head node is '2' and tail node is 'Node6'. Whereas, the edge was added the other way round.
Because of this the way in which incidence matrix is computed differs.
For example, the incidencematrix of the following graph is different from the above,
NNode = 6;
tail = 1:NNode-1;
head = 2:NNode;
Graph = graph(tail,head);
Although both graphs are the same and have 6 nodes.
Any suggestions on how to aviod this problem ? I would like to retain the result of Graph.Edges to be in the order in which the head and tail nodes are added to the Graph.

  0 Comments

Sign in to comment.

Products


Release

R2018b

1 Answer

Answer by Steven Lord
on 11 Sep 2019 at 13:41
Edited by Steven Lord
on 11 Sep 2019 at 13:42
 Accepted Answer

A graph object is undirected. A digraph object is directed.
Construct your network graph using digraph instead of graph on the fourth line of your code.
By the way, the addedge function has two capabilities you might find useful.
  1. The s (source) and t (target) inputs can be vectors to add multiple edges at once.
  2. If the source and/or target inputs reference nodes that don't yet exist, addedge adds them.
So you could do this with something like:
% Make a digraph and plot it for later reference
G = digraph(triu(ones(3)));
figure;
plot(G)
% How many nodes does G have?
N = numnodes(G);
% Add 2 new nodes
newnodes = [N+1 N+2];
% Add the edges between 1 and N+1, N+1 and N+2, and N+2 and 2
%
% I'm doing this in a copy of G, rather than G itself so you can go back
% and compare G and G2. But you can modify G itself if you want.
%
% Because of the way I created G, it's a weighted digraph, so I need
% to give the new edges weights. I chose to weight them all pi.
% Scalar expansion lets me specify a scalar weight to be used for each new edge.
G2 = addedge(G, [1 newnodes], [newnodes 2], pi);
% Eliminate the edge from 1 to 2
G2 = rmedge(G2, 1, 2);
% Plot the new digraph
figure;
plot(G2)

  8 Comments

There was a node that wasn't connected to any edge, node 1 in the data file. I have removed it.This consequently renumbered rest of the node. I am sharing my code for your kind reference.
file = %input file;
fields = fieldnames(file);
edges=[];
for i = 1:numel(fields)
edge = file.(fields{i});
edges = [edges;edge];
end
Graph = digraph(edges(:,1),edges(:,2));
Graph = rmnode(Graph,1);
Graph.Edges
Graph.Nodes
subplot(2,1,1)
plot(Graph)
G = graph(edges(:,1),edges(:,2));
G = rmnode(G,1);
subplot(2,1,2)
plot(G)
The output generated from the above is this.
I agree with you, the nodes 8, 1, 2, 20, 14, and 5 have an indegree of zero. But for my network, I'd like to generate a directed graph with indegree of zero at node 24, of the graph that results after removing a node , and outdegree of zero at node 28. (i.e the flow has to be directed from 24 to 28) It will be really nice if MATLAB has an option where this can be specified.
Or, for an undirected graph, it would be nice if MATLAB retains the same order of head and tail nodes while saving the graph property in Graph.Edges. I really don't want the head and tail nodes to be reversed when MATLAB saves the network structure in Graph.Edges. I'd like to know if there is a way to do this.
Steven Lord
on 14 Sep 2019 at 14:56
If the order of the edges matters, use a directed digraph instead of an undirected graph. By constructing an undirected graph you are saying the order of the endpoints of the edges does not matter. Since the order of the endpoints does matter for you, use digraph.
Thanks a lot for the response. I really understand I can use digraph to preserve the order of nodes. It works very well when I add new nodes and edges. But , I don't see it to be useful for my input data. The digraph that is generated by MATLAB doesn't represent the flow direction in the real system. Therefore, the only thing that I can do is to find out a way to preserve the order of nodes in undirected graph.

Sign in to comment.