MATLAB: Maximum common subgraph of two vertex-labeled graphs

graphmaximum common subgraph

I am doing a research project and I need to find the maximum common subgraph of two vertex-labeled graphs, does Matlab have functions to do this?

Best Answer

There might not be any direct function in MATLAB to solve your problem.

There are however basic graph data structures available here which you can use to build your solution/algorithm, also, you can refer to MatlabBGL and gaimc for already existing graph algorithms to build upon.

Related Solutions

MATLAB: How to use “graphmaxflow” function for undirected graphs in matlab

In MATLAB R2015b, you can easily create and analyze graphs. See the following documentation for more info:

http://www.mathworks.com/help/matlab/graph-and-network-algorithms.html

Note that there is a maxflow function which you can use to compute the maximum flow and associated minimum cut:

http://www.mathworks.com/help/matlab/ref/graph.maxflow.html

MATLAB: Select edges that connect subgraphs together

This works for your sample data set (which does not include nodes 12:14 as shown in the plot. Please test test this, I'm not a graph theory expert so there may be cases where this does not work.

M = [1 2; 2 3; 1 3; 4 5; 5 6; 6 7; 4 7;2 4; 5 7; 5 8;11 8; 8 9; 9 10; 10 11];
g = graph(M(:, 1), M(:, 2));
h = plot(g);
bcg = biconncomp(g).'; % biconnected components
[count, group] = groupcounts(bcg); % How many of each?
edgeidx = ismember(bcg, group(count==1)); % Edges with one count
g.Edges(edgeidx, 1) % Extract
ans =
  2×1 table
    EndNodes
    ________
     2    4 
     5    8

Best Answer

Related Solutions

MATLAB: How to use “graphmaxflow” function for undirected graphs in matlab

MATLAB: Select edges that connect subgraphs together

Related Question