Visio Guy
Solutionspecific Visio Discussions => Network Diagramming => Topic started by: cliff50 on September 05, 2020, 11:41:29 PM

Has anyone tried or had experience with coding algorithms to find the shortest path between two shapes .
Consider a page full of circle shapes .. each circle is connected by a line to one or more other circles ... the layout of circles and lines on the page is entirely random.
I am contemplating how to best produce a shortest path between any of the two circles. ( a list or change color of lines on page)
Similar to the old paper based game, where you scribe a pencil through a maze from a starting point to a destination point.
Shortest path being defined as the least number of circle\ lines stepped across the page, to produce a consecutive path from circle point of departure to circle point of destination.
I know how to VBA code in Visio .. however, I am trying to think of a logical coding approach that will deliver a consistent result , regardless of the random arrangement of lines and circles.
The only given is > every every line connects two circles. number of circles (no limit) .. number of lines (no limit)
thank you for your thoughts

since a given line may have N segments, probably should look at electrical signal routing algorithms
https://en.wikipedia.org/wiki/Routing_(electronic_design_automation)
https://www.electronicsforu.com/resources/coolstuffmisc/opensourcecircuitdesignsoftware
https://www.electronicslab.com/top10freepcbdesignsoftware2019/
https://en.wikipedia.org/wiki/Physical_design_(electronics)#Routing

See also http://visguy.com/vgforum/index.php?topic=5936.msg23919#msg23919

There's also this: http://visguy.com/vgforum/index.php?topic=6373.msg26266#msg26266 (http://visguy.com/vgforum/index.php?topic=6373.msg26266#msg26266) regarding shortest path with variants.

Dykstra / open shortest path first are direct lines approach. I assume that if you have 3 shapes in a row, you want to find
the shortest path between the end shapes.
So a direct line approach would mean that shortest path between end shapes is a line thru the middle shape.
Is that what you want? If so, Dykstra is father of this kind of approach.
However if you want the path between end shapes to NOT pass thru or under the middle shape than I think you need
consider the algorithms around physical design of cards or VLSI.
It all depends on what you are looking for.

BTW, straight line is pretty simple in this context
2D
Xdistand = xpin of this shape  xpin of other shape
Ydistance = ypin of this shape  ypin of other shape
distance = sqrt(xdistance^2 + ydistance ^2)
build a table of distance by shape for this shape
table would give you a "star blast" of varying length lines from this shape.
use the shape id as key ==> distance to that shape.
This could be a moderate VBA project.
if more of path around middle shapes
may also need to look at/for the place n route algorithms in visio.
not sure visio does this in VBA or C++

OK ... let me elaborate.
Shortest path in terms of least number of steps (nodes\circles) ..
I am dabbling with the conundrum of how to "document" rerouting in an MPLS network.
In essence. each electronic node is represented as a circle shape the data bitstreams are represented by a line shape ... each circle (node) is connected to an adjacent circle via a bitstream (line) .
In real life . MPLS networks are interconnected nodes which form a mesh over a wide area (WAN) .
There is a need to document the interconnectivity of this mesh as a diagram which can "trace" rerouted paths when ever a link connection (line) is broken .
in real life when a link is broken , the Nodes use tables to establish the shortest detour around the break in terms of #1 node transitions (LCR (least cost routing)..
my premise is that a visio manifestion of a MPLS network can be constructed so that link disruptions can be modelled in such a way to produce reports of how the rerouting shall occur around the break in the MPLS network.
I assume Visio attached to an ODBC data source is the best way forward.
By using the "connection collection " in the shapesheet .. underlying data tables can be populated to rapidly determine which rerouted path uses the minimum number of nodes to detour around a broken link.
An MPLS model that delivers predicted path detours and anticipated service performance would be key to successful management of this type of network.
I have developed a rudimentary manifestation of this and am open to critique and feedback . Others may have passed this way before.

if this more of the number of hops thru intermediates shapes to get to target shape.
so path "cost" = number of shapes hopped (A==> B==> C would have a cost of 2).
So the question is not trying find a path around those shapes....but trying to find a path thru the shapes.

Did you look at the link I sent...even try it???
It takes a bunch of nodes arbitrarily interconnected via some sort of mesh and finds the shortest path between any two arbitrary nodes.
If you are trying to create a static table that ranks all paths between A and Z according to length, that could be very large table depending upon the size of the network. It would be humongous. The size is simple permutation calculation. Then add in the number of arbitrary two node combinations...Well forget it. The table is so large it's useless.
With an accurate Visio diagram, you can choose two point in the active mesh, and the code will find the shortest path. It's a simple solution based upon intervening number of nodes. The algorithm could be embellished to include traffic volume limitations...but the code quickly becomes quite complex.

Vojo .. yes , my interpretation of least cost routing is "minimum number of nodes along the detour "
WapperDude Yes i have tried your solution (in your link) using my Visio pro 2016 and your solution delivered the desired result (many thanks).
I tried using the examples you supplied ... (my feedback for you) > very quick response time. and the colouration very intuitive.
I will apply it to a real world WAN map ( approx 350 nodes) and see how it goes. (feedback for you).
Aside : others may interpret LCR (least cost routing) in terms of distance (miles or kilometres) ... hence a path along A>B>C>D>E although it involves 5 nodes, it accumulates distance on each link for a total of only 20 miles.. and yet A>X>E involves 3 nodes but travels a grand total of 30 miles.
From the perspective of communication transmission systems, the tyranny of distance infers a propagational delay. (albeit at the speed of light)
I think you infer that calculations concerning link distances can be coded into your algorithms.
Moving forward ... application of this concept is to produce reports that measure the "robustness" of MPLS based network.
cheers
Cliff

my point is that cost "thru nodes" can be drastically different than cost "around nodes"
For example, picture this
B
A C E
D
Cost to got thru C to get to E is much smaller than looping around B or D to get to E.
For the latter, you cant just do sqrt((ExAx)^2+(EyAy)^2) because the Y component could be as small as 0
you would need to do A to offset B + offset B to E to get to get true cost of that path.
What if
B
A C E
D
A, offset B, E has a different cost than A, offset D, E...so need true cost of each path to find shortest.
these examples ignore the possibility that B,C,D are spread out enough that you can go thru one of the gaps
maybe what you need to do is
1) realign nodes to the nearest 20mm or introduce fixed gaps for very close nodes (ie bring some order to node location)
2) compute lowest cost that should be different enough that some of the cases can be dismissed quickly.
3) maybe draw a multi segment line you can see what your algorithm pickrf as lowest cost path
maybe add curves at the bends for appearance (pretty simple for multi segment lines  1 shape sheet cell).
or maybe calculate straight line from start node to end node...add some line ends and may place on a layer "below" node layer
so that as line pass below intermediate node, user knows line did not terminate on that intermediate node.
This a very complex problem but there are many many academic papers that have looked at this problem for 50 years.
Good luck.
good luck

WapperDude
attached on Page 1 .. actual MPLS network mesh
circles =Node (locations)
lines = bitstreams.
I am not getting a consistent result . is this because there are too many nodes ?.
I see yellow coloration but not any green (I think green indicates the shortest path ).
the code seems to enumerate the number of links , however .... ?

Will take a look at it.

Seems to be working fine. Methodology:
1) Select two nodes
2) Select path type (3rd choice is probably most appropriate)
3) Select Calculate Shortest Path
5) Hit continue
6) Close the Popup summary window

Wapperdude ... yes it seems to be working now ..
Green denotes the shortest path ?
What does the Yellow denote ?
The image was only half populated with node location (because of 500 mb posting limit on this forum )
is there a link count limit in the code anywhere ? , because i want to test it out on the full network image.
Trying get my head around how the search occurs.. does your code examine every possibilty from origin to destination ?
Also .. what is the point of "bail out " ergo, > should no path be able to be discovered between origin and destination .. does that mean a loop counter has been exceeded .

Yes. Green is shortest path.
Yellow are the immediate paths from the starting node.
No, there is no inherent limit coded in. Whatever tops out will be for "outside" reasons.
Generally, yes. But, it only visits each path once. It is based upon Dijkstra's algorithm. The original link provides more detail, and the code actually has a lot of comments.
The bailout, only occurs if you select either incoming or outgoing paths, which implies a specific direction. If there's no way to get to the destination, then result is zero paths of the type selected will get you to Rome.

Wapperdude ... for the minute your solution is fit for purpose ... (purpose being MPLS network evaluation tool).
I am unsure though ... why you went the extra mile and include directional capability. Perhaps this could be a model of street navigation (one way streets etc).
you must have been thinking outside the box ;)
~ cheers
Cliff

Just seemed like the right thing to do. Another application could also be electronic circuits: fundamentally, outputs drive inputs. So, that's an exploitable feature. Visio also has an unsung feature, the Dcell, for connection points. That can be utilized to distinguish types of i/o: inputs, outputs, tristate, power, etc.

Wapperdude ... I realized the yellow coloration is crucial to a consistent outcome. I am unsure if the distancing calculation is incorporated into the outcome in any way ... it appears not .. but I will follow the "yellow brick road"

Colored paths have secondary purpose... they indicate when a path has been counted. The algorithm is based upon single traverse.