find the shortest path between two shapes

[cliff50]

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

[vojo]

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/cool-stuff-misc/open-source-circuit-design-software

https://www.electronics-lab.com/top-10-free-pcb-design-software-2019/

https://en.wikipedia.org/wiki/Physical_design_(electronics)#Routing

[Croc]

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

[wapperdude]

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

[vojo]

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.

[vojo]

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++
   

[cliff50]

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"  re-routing 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" re-routed 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 re-routing 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 re-routed 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.

[vojo]

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.

[wapperdude]

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.

[cliff50]

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

[vojo]

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((Ex-Ax)^2+(Ey-Ay)^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

[cliff50]

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 .... ?

[wapperdude]

Will take a look at it.

[wapperdude]

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 Pop-up summary window

[cliff50]

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 .