MATLAB: Product of two graphs in MATLAB

cartesian productedge-weightedgraphgraph theorygraphsnode-weighted

I have two undirected graphs G1 and G2, they are both node and -edge weighted graphs. I want to create a graph G which is the Cartesian product of G1 and G2. G1 has 4 nodes and G2 has 15 nodes. How can I do this using MATLAB?

Best Answer

Without weights, you can compute the graph product quite quickly:

A1 = adjacency(G1);
A2 = adjacency(G2);
I1 = speye(numnodes(G1));
I2 = speye(numnodes(G2));
Aprod = kron(A1, I2) + kron(I1, A2);
Gprod = graph(Aprod);

With weights, you need to construct the weighted adjacency matrix, which unfortunately is a bit cumbersome:

>> [i, j] = findedge(G1);
>> A1 = sparse(i, j, G1.Edges.Weight, numnodes(G1), numnodes(G1));
>> [i, j] = findedge(G2);
>> A2 = sparse(i, j, G2.Edges.Weight, numnodes(G2), numnodes(G2));
>> I1 = speye(numnodes(G1));
>> I2 = speye(numnodes(G2));
>> Aprod = kron(A1, I2) + kron(I1, A2);
>> Gprod = graph(Aprod, 'upper');

The node weights should be simpler again, but I'm not sure how you would want to treat these: Is the weight of a node representing the product of node i from G1 and node j from G2 going to be the product of these node's weights, or the sum?

Related Solutions

MATLAB: Add Edges to Network Graph Without Changing the Layout

plot the first graph.

Turn hold on.

plot the second graph, specifying the XData, YData, and (if plotting the graph in 3D) ZData properties using the values of the XData, YData, and (if necessary) ZData properties of the first graph. See the "Custom Graph Node Coordinates" example on the documentation page for the graph plot function for an example setting those properties on a plotted graph.

MATLAB: Delete and add new edges in a graph

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.

The s (source) and t (target) inputs can be vectors to add multiple edges at once.
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)

Best Answer

Related Solutions

MATLAB: Add Edges to Network Graph Without Changing the Layout

MATLAB: Delete and add new edges in a graph

Related Question