Delete and add new edges in a graph

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.

Answer 1

[Steven Lord]

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)

[Deepa Maheshvare]

This solution works fine for simple graphs. For graphs like this , I would like to generate a digraph with indegree = 0 at the entry (node labelled 24) and outdegree =0 at the exit( node labelled 28) . However, the outdegree of both the nodes mentioned above is 0. Any suggestions on how to resolve this problem?

[Deepa Maheshvare]

If it is not possible to define where the source node and sink node occurs in a digraph, I would like to know if it is possible to store the edges in Graph.Edges(column1 and column2- head and tail) in the order in which the nodes are added in Graph = addedge(Graph,head,tail).

[Steven Lord]

The graph in that figure does not look like a directed digraph. It looks like an undirected graph. Based on your description it sounds like you want material to travel only from node 24 to node 19 and not the other way around. To see the difference, compare these two plots.

>> G = graph(bucky);
>> figure;
>> plot(G);
>> title('Undirected');

>> D = digraph(bucky);
>> figure;
>> plot(D);
>> title('Directed');

If you constructed the graph in the figure you posted by passing source and target vectors into graph, change your call to graph into a call to digraph and try plotting that digraph to see if it looks more like you expect. If you initialized the network as an empty graph and kept adding edges, initialize it to an empty digraph and add edges instead.

You can see that it's not possible to ask the question "What is the outdegree of node 1 of G?" because the edges don't have a direction.

>> outdegree(G, 1)
Error using graph/outdegree (line 494)
Out-degree of nodes is not supported for undirected graphs. Use degree instead.

It is possible to ask for the outdegree of node 1 of D.

>> outdegree(D, 1)
ans =
     3

You could even write your own helper function to identify source and sink nodes in your digraph.

>> isSource = @(D, node) indegree(D, node) == 0;
>> isSink = @(D, node) outdegree(D, node) == 0;

None of the nodes in the bucky digraph are sources or sinks.

[Deepa Maheshvare]

Thanks a lot for the response. Unfortunately, the directed graph created from the input of source and target nodes present in a mat file. The flow of material doesn't occur from one

end to the other end. As a result , there is no node ( 24 / 28) with outdegree zero. I am not sure how to solve this problem. The undirected graph gave the right incidence marix with the head and tail node in right position. The problem is when new nodes and edges are added between two nodes that already exist. The order of head and tail is reversed in MATLAB.

[Steven Lord]

The data from the MAT-file doesn't look like it corresponds to the digraph in the figure file. In the figure file, by inspection node 27 has indegree 3 (one edge to it from 25 and two edges to it from 26) and outdegree 0 while in your data node 27 has edges coming into it (Edge34 is [22 27]) and going out from it (Edge38 is [27 28] and so is Edge39.) I'm also not sure where your edge weight data is stored.

Though taking a closer look, I think this is just a node renaming issue. You have 40 numbered variables, Edge0 through Edge39 (as an aside, that pattern is discouraged) and the GraphPlot object from the figure file has 40 values in its EdgeLabel property. The set of Edge* variables contains 28 unique numbers from 2 to 29 and the GraphPlot from the figure file has 28 nodes.

The isisomorphic and isomorphism functions for digraph objects may help determine if that's the case when used on the digraph created from your Edge* variables and on the digraph that you plotted to create the figure file. I tried mapping the nodes myself and it looked promising; Edge0 corresponds to the edge between nodes 1 and 3 in the GraphPlot, Edge1 is the edge between 1 and 11, etc.

Finally, looking at the figure I see that there are several source and sink nodes in that digraph. The nodes plotted at the top of the layered layout (8, 1, 2, 20, 14, and 5) have no edges entering them and so are sources. Nodes 3, 28, 24, 15, and 27 each have no edges exiting them and so are sinks.

[Deepa Maheshvare]

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]

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.

[Deepa Maheshvare]

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.