Author Topic: find the shortest path between two shapes  (Read 32950 times)

0 Members and 1 Guest are viewing this topic.

wapperdude

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 4837
  • Ideas Visio-lized into solutions
Re: find the shortest path between two shapes
« Reply #15 on: September 23, 2020, 01:06:00 AM »
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 bail-out, 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.
Visio 2019 Pro

cliff50

  • Full Member
  • ***
  • Posts: 225
Re: find the shortest path between two shapes
« Reply #16 on: September 23, 2020, 05:16:30 AM »
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
« Last Edit: September 23, 2020, 05:19:34 AM by cliff50 »

wapperdude

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 4837
  • Ideas Visio-lized into solutions
Re: find the shortest path between two shapes
« Reply #17 on: September 23, 2020, 09:17:56 AM »
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 D-cell, for connection points.  That can be utilized to distinguish types of i/o:  inputs, outputs, tri-state, power, etc.

Visio 2019 Pro

cliff50

  • Full Member
  • ***
  • Posts: 225
Re: find the shortest path between two shapes
« Reply #18 on: October 01, 2020, 04:51:29 AM »
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"

wapperdude

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 4837
  • Ideas Visio-lized into solutions
Re: find the shortest path between two shapes
« Reply #19 on: October 01, 2020, 08:16:36 AM »
Colored paths have secondary purpose... they indicate when a path has been counted.  The algorithm is based upon single traverse.
Visio 2019 Pro

Surrogate

  • Hero Member
  • *****
  • Posts: 1803
    • ShapeSheet™ Knowledge Base
Re: find the shortest path between two shapes
« Reply #20 on: December 16, 2020, 03:47:58 AM »
few days ago i find this demo by Cliff A.
Perfect !

cliff50

  • Full Member
  • ***
  • Posts: 225
Re: find the shortest path between two shapes
« Reply #21 on: December 18, 2020, 01:28:51 PM »
modified version of wapperdudes solution.
my study of MPLS reveals there needs to be  conditional filters attached to the algorithm to determine if a physical path en route is available.
The filters are dedicated to resolving the following :
Bandwidth , Load balancing , or availability ( network impacts).

 The directional component of the links in the original solution are not necessary in the study.
I feel the "logical" assignment of bandwidth on the physical links are mission critical for designing these type of networks.
work in progress.
cheers
Cliff
« Last Edit: December 18, 2020, 01:39:11 PM by cliff50 »

Nikolay

  • Hero Member
  • *****
  • Posts: 1285
    • UnmanagedVisio
Re: find the shortest path between two shapes
« Reply #22 on: December 18, 2020, 05:20:12 PM »
few days ago i find this demo by Cliff A.

Just wondering why this video about finding shortest paths is marked 18+ ?! You have to verify your age to watch it. Well, I did and watched it to the end, but there are just lines, circles and rectangles. Am I missing something? ;D ;D ;D
« Last Edit: December 18, 2020, 05:26:54 PM by Nikolay »

cliff50

  • Full Member
  • ***
  • Posts: 225
Re: find the shortest path between two shapes
« Reply #23 on: December 18, 2020, 05:57:59 PM »
Nikolay,
I am no expert on posting youtube.(hence button +18).

The video is a demonstration of MPLS (multi path label switching) style of Network , using the developer version of Visio (professional).

From a transmission/network/bandwidth perspective the following abstract applies:
Evolution of topology PDH -> SDH-> MPLS.

PDH linear by nature, its bandwidth could be readily drawn on paper.
SDH non  linear, its bandwidth is "static" and configurable. When a link is impacted, alternate routing paths pre configured by human hand.
MPLS non linear , its bandwidth is dynamic . Alternate bandwidth is automatically configured using an algorithm based upon shortest path(least number of nodes).

The algorithm is very similar to Dijkstra's shortest path algorithm.

Regards the image interpretation.
the circles ostensibly represent Routers, the lines represent the physical connections between the routers. ( transmission links)
the numbers on the line represent how much bandwidth is spare on the link.

regards the audience.
a demonstration to show the possibilities, using the Visio platform, issues of MPLS bandwidth design and control.

any feedback appreciated.

regards
Cliff A.
« Last Edit: December 18, 2020, 06:00:19 PM by cliff50 »

Nikolay

  • Hero Member
  • *****
  • Posts: 1285
    • UnmanagedVisio
Re: find the shortest path between two shapes
« Reply #24 on: December 19, 2020, 04:56:47 AM »
Dear Cliff, thank you for clarifying.
What I meant is that the video may be simply not accessible to most people because not everyone would go through age verification Now you see blank screen and "age verification required" button (with credit card or photo document). 18+ video usually means "adult" (porn) content, therefore it may be positioned incorrectly by youtube. "Only circles and rectangles" was meant merely as as a joke referring to "adult video" category, sorry.
« Last Edit: December 19, 2020, 05:13:33 AM by Nikolay »

cliff50

  • Full Member
  • ***
  • Posts: 225
Re: find the shortest path between two shapes
« Reply #25 on: December 19, 2020, 02:11:01 PM »
Hi Nikolay,

Please, no need to apologize , I am the one in error. I didn't realize\ understand the consequences of the restriction 18 +
Thanks to your prudent observation -> I have amended the status.  update-> https://youtu.be/znFO-PDOCp0

I really appreciate your and your fellow Visio artisans, contributions to this forum.

best wishes for the Christmas season Sir.
Cliff  :)
« Last Edit: December 19, 2020, 02:35:45 PM by cliff50 »