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 (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:
(http://antor.ua.ac.be/system/files/img.jpg)
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/ (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 ?
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.
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...
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
My knolege in coding is reallly bad. I will not manage to deal witch such task. This is why i ask for help...
So, you're asking someone to do this for you? Is this a job project, a class project?
Wapperdude
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
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 (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.
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 :/
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.
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 (http://en.wikipedia.org/wiki/Shortest_path_problem)
Cheers,
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
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
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! ;)
Fare enough :)
Ill do my best :) hope it will not take me too long :)
Yacine, really good job!
Something like this..
There is trully a lot of place for improvement.
Not in the code (for me) but in visual interpretation.
But i really like the approach. :)
Of there are more ideas - please share :) !
Hi Andrei,
I unfortunetaly could not run your upload. Why is it a jpln? can you upload a vsd?
I on the other hand could not hold on myself and continued to play.
The main thing to make the solution viable is certainly the ergonomy. Having to select two nodes, then start the macro is too complicated.
Instead, the new nodes have a menu in which you can set whether they are the source or the target node.
This menu changes the custom properties of the page, which then triggers the path routine.
This customisation is written in setup routines. Start first the page setup routine manually.
The pages gets a menu to setup the shapes. So later additions of shapes is possible.
Cheers,
Yacine
Sorry. You remember when i told you that i use my phone to have i.access.
This must be the file.
I'll check yours when i reach work (where i have visio...)
I`m back again :)
Here is the real file.
This is the entire diagram i`m working with.
This code have a little modification :)
it is not drawing only one path. The first shape you select is the start point, and every next you select is recognized as an end point. the algorithm draws after that all the paths.
Now i have a questions:
every shape have an start and end prop.row
How can the code understand what is start and what is end.
every time i try to create a cycle that goes through all shapes and look for that prop.row and adds it to selection - something turns wrong
Any idea for a solution.
Good morning Andrei,
The trick is to trigger a macro by changing the value of a cell.
In the enclosed example it is one of the custom properties startshape and endshape of the page.
These cells are changed by selecting one of the options start/end of a shape in the drawing.
I think it is a bad idea to set custom properties, as you would need to reset them.
Rather use action menus as shown in the example.
Good morning Yachine.
I'll use excel to define start and end of the diagram. One start and several ends.
This is most easy for me with prop.rowS
I know i need reset all properties. But i cannot do.
I was thinking for sth like
Sub add_selection()
Dim val As String
For Each shp In ActivePage.Shapes
If shp.OneD = False Then
If Not shp.CellExists("prop.start", visSectionProp) Then
End If
Else
If shp.Cells("prop.start").FormulaU = True Then
visSelect
Else
End If
End If
Next shp
End Sub
But it gives an errr
I did not really understand your problem.
If you want to reset the shapes, then you should reset all the starts and ends to false, without additional conditions. Isn't it?
If shp.CellExists("prop.start", visSectionProp) Then
shp.Cells("prop.start").FormulaU = False
End If
If shp.CellExists("prop.end", visSectionProp) Then
shp.Cells("prop.end").FormulaU = False
End If
This is the reseting .
First i want to select the one that have start = true
then to select all shapes that have end = true :)
My problem is selection :)