visualize the shortest path in a chart

Started by kiler40, September 18, 2014, 04:42:51 AM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

kiler40

Greetings All,
from some time i`l looking for a solution to show the shortest path in a graph with End points, nods and connectors.

I was looking in some old topics
http://visguy.com/vgforum/index.php?topic=5201.msg20562#msg20562
and i feel that this is somewhere where i want to be... but still cant understand it all
Yachine and Jumpy were speaking for a possible solution. but my knowledge in Visio is not sophisticated enough yet :)

Basically this is what i want to have:

select start side, select end side and make the line red.

i also look at this
http://www.visguy.com/2009/04/08/path-analysis-in-visio/
But i really cant understand how it works. everytime it is creating the same thing...

In the comments of the article, there is a part wit "ConnectedShapes and GluedShapes API methods" but i also cant find more about it.

Can someone help me on this ?

Jumpy

Finding the shortest path is some heavy duty stuff. There are algorythms for that (all navigation assistents are based on that), but I don't think it's easy to adapt that to visio. Even if I where able to understand that algorytms in the first place.

kiler40

I'm lost for days to combine such algorithm to something drawn in Visio... And i really need this for my project. It is like the last part of the puzzle...

aledlund

The code in this article
http://www.visguy.com/2009/04/08/path-analysis-in-visio/
for path analysis (and it does support shortest path) was adapted from a book by Michael
McMillan "Data Structures and Algorithms using Visual Basic.Net" which you can purchase 
over here
http://www.amazon.com/Structures-Algorithms-Using-Visual-Basic-NET/dp/0521547652/ref=sr_1_1?s=books&ie=UTF8&qid=1411044748&sr=1-1&keywords=data+structures+and+algorithms+in+visual+basic.net

al Edlund

kiler40

My knolege in coding is reallly bad. I will not manage to deal witch such task. This is why i ask for help...

wapperdude

So, you're asking someone to do this for you?  Is this a job project, a class project?

Wapperdude
Visio 2019 Pro

kiler40

No. I'm asking for some directions.
It is not a project. I do this at work almost every day by hand for the last 3 years :)
But everything is becoming bigger and bigger so im looking for some automation.
Another problem is that at work i dont have internet access and browsing for info can happen only through my phone. And this is hard to do.
In a previous topic (that i put in the first post) Yachine was speaking about shapes that can recognize to what they are connected.
Also Jumpy was speaking about using the shape data of the page and dependson-function.
Im just asking for some info in this direction and support :)

Thanks in advance

wapperdude

OK.  When you said your project, kinda raised a red flag, well, for me anyway.

I haven't researched path analysis algorithms. so, at this point I can only outline an approach:
  1.)  At this post, you can find code that will go from a starting point and give you all of the sequentially connected shapes:  http://visguy.com/vgforum/index.php?topic=5928.msg23850;topicseen#msg23850.  You'll have to adapt it, because you want the connectors between the shapes along the path.  It is the sum of their lengths that give total distance.
  2.)  Also, in your case, you could add a condition that no node may appear twice along the same path.

It's kind of brute force approach.  I'm sure there are smarter techniques that eliminate obvious potential routes based on simple mathematics.  But, I don't want to think that hard right now.

HTH
Wapperdude

PS.  I have not seen the solution as the file was saved in V2010 format, which I don't have.  I'm sure you could request that it be saved as V2007 if that's what you're using.
Visio 2019 Pro

kiler40

Ok. This is really nice.
Most important is that in my case there are no alternative route. Only one and need to be vizualized :)
In the thread you have post linc Croc shares a code that shows all the links. Maybe this will do. The question now is how to check all connection and leave only what is needed.

I use visio 2010. There is a solution file saved in visio 2013 :/

wapperdude

Hopefully I understand your last question correctly, so, once you have all of the potential paths identified, then, you need to determine their length by summing the individual connector lengths along that path.  I think the easiest was is to create a running sum as each path is traveled.  Then, perhaps this is saved in an array, or you have two totals, the length of the current path and the 2nd would be the shortest of the previous path.  You might do something like store the previous path, perhaps highlight it by color change, or write it into Excel.  By default, the 1st path is automatically stored. Then go thru the 2nd path, if it's total length is shorter than previous path, it becomes the path stored, and move on to next path.  By end of the process, the shortest path will be stored and highlighted.
Visio 2019 Pro

Yacine

#10
QuoteSo, you're asking someone to do this for you?  Is this a job project, a class project?
Hi Wayne,
Andrei is that crazy guy who makes those even more crazy electric wiring diagrams for cars.
He had some time ago that interesting path problem, that to my shame I did not solve, despite my promise.
(http://visguy.com/vgforum/index.php?topic=5201.msg20562#msg20562)
The link to his drawing is broken, but I found a copy in my download directory.
It's worth a look.

@Andrei,
I don't think your problem is "so" difficult. Since your first post, I did 2 researches on google and find several links to shortest path algorithms implemented in excel.
Since excel also uses only simple VBA, it should be fairly simple to translate this to visio.

Building up a vba structure with points and distances, should be the least of your problems - our new "connections champion" will certainly be eager to help you.

For the algorithm however, dude, you need to learn to code in VBA! There's not that much magic in it.  ;)

As for the most often used algorithm, I found Dijkstra to be very often implemented
http://en.wikipedia.org/wiki/Shortest_path_problem

Cheers,
Yacine
Yacine

Yacine

Hi Andrei,
here's the promised adaptation of Dijkstra's algorithm.
There's still plenty of room for improvement, but that should get you started.
The macro to run is "DijkstraTest2". You need to select the 2 shapes for which you want the shortest path.
Cheers,
Yacine
Yacine

kiler40

This is awesome !
now i had time just to do a quick check of the file
but the question is how to make the lines between the nodes change.
the nodes i don`t need to change.
i`ll have a deep (as much as i can understand) look in the file as soon as i can... but some more help please :)


Thank you so much for the help !

Andrei

Yacine

#13
Quotehow to make the lines between the nodes change
I run into the same problem and thought I should leave it up to you ;) .

Basically, you would need to look for the consecutive nodes combination of the path string in the Conns array. Once found, format the according connector shape.
A For-Next loop, leaving either the beginning or the end to be handled separately (because of Conns (n) and (n-1) or (n+1)).

Andrei, I look forward to download your solution!  ;)
Yacine

kiler40

Fare enough :)
Ill do my best :) hope it will not take me too long :)