Optimise vertical position of nodes for shortest sum of paths

1 view (last 30 days)
Hi, I am doing a project which aims to optimise the layout of nodes.
I have a matrix of many paths. Each row of the matrix is a separate path. Each path specifies through which nodes a path has to go from start to finish.
MATRIX OF PATHS = [a b c d e; a b d e g; a c b e g; a b c f; a b c d; a b c d e; a b d e; a b c f g]
Each of these nodes has an assigned x coordinate, however, the y coordinate has to be chosen in the most optimal way. The y coordinate has to be an integer that is equal to or greater than 1, so: (1,2,3,4...). The most optimal way is such that minimises the total length of paths.
LIST OF NODES: a: x=1 b: x=2 c: x=3 d: x=3 e: x=4 f: x=4 g: x=5
  2 Comments
Michael Schumbach
Michael Schumbach on 28 Oct 2022
Edited: Michael Schumbach on 28 Oct 2022
There are no such constraints. The only constraints are the x coordinate of nodes, the paths stating the nodes through which the paths have to go (in the given order), and that y coordinate has to be an integer greater than or equal to one. Also, the nodes cannot overlap.

Sign in to comment.

Answers (2)

Bjorn Gustavsson
Bjorn Gustavsson on 28 Oct 2022
If this is a one-off calculation just brute-force search shouldn't be too bad, the y-position of the nodes should be within a small range of integer values spanning no more than 7, you have seven y-values to search for. This makes the maximum combinations to look through 7^7, check that they fullfill your condition of notoverlapping and then calculate the total distances and keep those shorter than or equal to the currently shortest. No need to think or read up on an efficient integer-programming optimization algorithm that will take far longer time. Something like this to get you started:
shortest_total_path = inf;
for a = 1:7
for b = 1:7
for c = 1:7
for d = 1:7
for e = 1:7
for f = 1:7
for g = 1:7
Paths = {[[a;1], [b;2], [c;3], [d;3], [e;4]],...
[[a;1], [b;2], [d;3], [e;4], [g;5]],...
[[a;1], [c;3], [b;2], [e;4], [g;5]],...
[[a;1], [b;2], [c;3], [f;4]],...
[[a;1], [b;2], [c;3], [d;3]],...
[[a;1], [b;2], [c;3], [d;3], [e;4]],...
[[a;1], [b;2], [d;3], [e;4]],...
[[a;1], [b;2], [c;3], [f;4], [g;5]]};
% Calculate sum of the lengths of the paths
% save the total length in an array of with all lengths
% compare to currently shortest
% save this path if it is shorter
end
end
end
end
end
end
end
If on the other hand this is a problem where you will have to solve this type of tasks many times over you'll have to read up on efficient algorithms.
HTH
  3 Comments

Sign in to comment.


Steven Lord
Steven Lord on 28 Oct 2022
If you have a graph or diagraph object representing your nodes and their connections, perhaps plotting the graph or digraph and using the layout function with the 'layered' layout option to determine on which level each node should be placed would help give you a starting point. You could then set the XData property of the object returned by the plot call to your known data and see how the plot looks.

Community Treasure Hunt

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

Start Hunting!

Translated by