You probably need to use tools from graph theory. And there are a nice set of such tools in MATLAB.
help graph
GRAPH Undirected Graph
G = GRAPH builds an empty graph with no nodes and no edges.
G = GRAPH(A) uses the square symmetric matrix A as an adjacency matrix
and constructs a weighted graph with edges corresponding to the nonzero
entries of A. The weights of the edges are taken to be the nonzero
values in A. If A is logical then no weights are added.
G = GRAPH(A,NAMES) additionally uses NAMES as the names of
the nodes in G. NAMES must be a string vector or a cell array of
character vectors, and must have as many elements as size(A,1).
G = GRAPH(A,...,TYPE) uses only a triangle of A to construct the graph.
TYPE can be:
'upper' - Use the upper triangle of A.
'lower' - Use the lower triangle of A.
G = GRAPH(A,...,'omitselfloops') ignores the diagonal entries of the
adjacency matrix A and does not add self-loops to the graph.
G = GRAPH(S,T) constructs a graph with edges specified by the node
pairs (S,T). S and T must both be numeric, string vectors, or cell
arrays of character vectors. S and T must have the same number of elements or be
scalars.
G = GRAPH(S,T,WEIGHTS) also specifies edge weights with the numeric
array WEIGHTS. WEIGHTS must have the same number of elements as S and
T, or can be a scalar.
G = GRAPH(S,T,WEIGHTS,NAMES) additionally uses NAMES as the names of
the nodes in G. NAMES must be a string vector or a cell array of character
vectors. All nodes in S and T must also be present in NAMES.
G = GRAPH(S,T,WEIGHTS,NUM) specifies the number of nodes of the graph
with the numeric scalar NUM. NUM must be greater than or equal to the
largest elements in S and T.
G = GRAPH(S,T,...,'omitselfloops') does not add self-loops to the
graph. That is, any edge k such that S(k) == T(k) is not added.
G = GRAPH(EdgeTable) uses the table EdgeTable to define the graph. The
first variable in EdgeTable must be EndNodes, and it must be a
two-column array defining the edge list of the graph. EdgeTable can
contain any number of other variables to define attributes of the graph
edges.
G = GRAPH(EdgeTable,NodeTable) additionally uses the table NodeTable to
define attributes of the graph nodes. NodeTable can contain any number
of variables to define attributes of the graph nodes. The number of
nodes in the resulting graph is the number of rows in NodeTable.
G = GRAPH(EdgeTable,...,'omitselfloops') does not add self-loops to the
graph.
Example:
% Construct an undirected graph from an adjacency matrix.
% View the edge list of the graph, and then plot the graph.
A = [0 10 20 30; 10 0 2 0; 20 2 0 1; 30 0 1 0]
G = graph(A)
G.Edges
plot(G)
Example:
% Construct a graph using a list of the end nodes of each edge.
% Also specify the weight of each edge and the name of each node.
% View the Edges and Nodes tables of the graph, and then plot
% G with the edge weights labeled.
s = [1 1 1 2 2 3 3 4 5 5 6 7];
t = [2 4 8 3 7 4 6 5 6 8 7 8];
weights = [10 10 1 10 1 10 1 1 12 12 12 12];
names = {'A' 'B' 'C' 'D' 'E' 'F' 'G' 'H'};
G = graph(s,t,weights,names)
G.Edges
G.Nodes
plot(G,'EdgeLabel',G.Edges.Weight)
Example:
% Construct the same graph as in the previous example using two
% tables to specify edge and node properties.
s = [1 1 1 2 2 3 3 4 5 5 6 7]';
t = [2 4 8 3 7 4 6 5 6 8 7 8]';
weights = [10 10 1 10 1 10 1 1 12 12 12 12]';
names = {'A' 'B' 'C' 'D' 'E' 'F' 'G' 'H'}';
EdgeTable = table([s t],weights,'VariableNames',{'EndNodes' 'Weight'})
NodeTable = table(names,'VariableNames',{'Name'})
G = graph(EdgeTable,NodeTable)
graph properties:
Edges - Table containing edge information.
Nodes - Table containing node information.
graph methods:
numnodes - Number of nodes in a graph.
numedges - Number of edges in a graph.
findnode - Determine node ID given a name.
findedge - Determine edge index given node IDs.
edgecount - Determine number of edges between two nodes.
addnode - Add nodes to a graph.
rmnode - Remove nodes from a graph.
addedge - Add edges to a graph.
rmedge - Remove edges from a graph.
ismultigraph - Determine whether a graph has multiple edges.
simplify - Reduce multigraph to simple graph.
degree - Degree of nodes in a graph.
neighbors - Neighbors of a node in a graph.
outedges - Edges connected to a node in a graph.
reordernodes - Reorder nodes in a graph.
subgraph - Extract an induced subgraph.
adjacency - Adjacency matrix of a graph.
incidence - Incidence matrix of a graph.
laplacian - Graph Laplacian.
shortestpath - Compute shortest path between two nodes.
shortestpathtree - Compute single source shortest paths.
distances - Compute all pairs distances.
nearest - Compute nearest neighbors of a node.
bfsearch - Breadth-first search.
dfsearch - Depth-first search.
maxflow - Compute maximum flows in a graph.
conncomp - Compute connected components of a graph.
biconncomp - Compute biconnected components of a graph.
bctree - Block-cut tree of a graph.
minspantree - Compute minimum spanning tree of a graph.
centrality - Node centrality for graph G.
isisomorphic - Determine whether two graphs are isomorphic.
isomorphism - Compute an isomorphism between G and G2.
allpaths - Compute all paths between two nodes.
allcycles - Compute all cycles in graph.
cyclebasis - Compute fundamental cycle basis of graph.
hascycles - Determine whether a graph has cycles.
plot - Plot an undirected graph.
See also DIGRAPH
Documentation for graph
doc graph
help minspantree
--- help for graph/minspantree ---
MINSPANTREE Minimum spanning tree of a graph
[T, PRED] = minspantree(G) returns the minimum spanning tree T of
graph G, and the vector PRED of predecessors: PRED(I) is the node index
of the predecessor of node I.
[T, PRED] = minspantree(G, 'Method', METHODNAME) specifies the method
used to compute the minimum spanning tree:
'dense' starts at node rootVertex and adds edges to the tree
while traversing the graph. This is the default.
'sparse' Sorts all edges by weight, and adds them to the tree if
they don't cause any cycles.
[T, PRED] = minspantree(G, 'Root', rootVertex) specifies the root
vertex. If 'Method' is 'dense', this is the starting vertex;
if 'Method' is 'sparse', the root vertex is only used to compute
the PRED vector.
Default: rootVertex is Node 1
[T, PRED] = minspantree(G, 'Type', TYPE) specifies what is done if G
is not connected:
'tree' only one tree is returned, which contains rootVertex.
This is the default.
'forest' a forest of minimum spanning trees is returned.
Example:
% Create and plot a graph. Compute and highlight its minimum
% spanning tree.
s = [1 1 1 2 5 3 6 4 7 8 8 8];
t = [2 3 4 5 3 6 4 7 2 6 7 5];
weights = [100 10 10 10 10 20 10 30 50 10 70 10];
G = graph(s,t,weights);
G.Edges
p = plot(G,'EdgeLabel',G.Edges.Weight);
tree = minspantree(G);
tree.Edges
highlight(p,tree)
See also GRAPH, SHORTESTPATH, CONNCOMP
Documentation for graph/minspantree
doc graph/minspantree
Other uses of minspantree
digraph/minspantree
For example,
xy = randn(20,2);
Dxy = squareform(pdist(xy));
Gxy = graph(Dxy);
tree = minspantree(Gxy);
plot(tree)
The above tree was built purely based on the interpoint distances between nodes.
In the end though, no, you don't want to write the code yourself. Learn to find and use the tools in MATLAB. Here all you needed to know is how to use the tools for working with graphs.
