Optimal routing for building feeders in the form of a radial network

5 ビュー (過去 30 日間)
SNM Nima
SNM Nima 2022 年 12 月 22 日
編集済み: John D'Errico 2023 年 1 月 23 日
I want to write a code in MATLAB to determine the optimal route for the construction of feeders in the radial network. I don't have an algorithm to start my work and write it. Can anyone guide me to write it?
For example, I want to show the bottom right figure in the output!

回答 (1 件)

John D'Errico
John D'Errico 2023 年 1 月 23 日
編集済み: John D'Errico 2023 年 1 月 23 日
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);
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.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by