I would like to draw a network that connects a set of specific points while following an existing street network and while following “the shortest walk” component.
(1) My first step is to create a Delaunay network between points to find out pairs of points (end and start points):
(2) I would like to transpose these paths into the real street network by using shortest walk. However I don’t manage to get all the paths, but only once per pair. Is there a way to do all pairs at once? I get this error message “1. The start and end positions are equal”
(3) I would like to store all the shortest paths and merge them to get one network that connects all points and follow the existing street network. Finally I will use a minimum spanning tree to ensure that the overall length of the network is minimized.
Please find the graph attached.
example_shortest_walk.gh (31.8 KB)
Thanks for your help!
Your final goal is shortest paths between certain points? This seems like a complicated way to approach it.
What’s step #1 for? You seem to be adding diagonals not part of the original graph, which you would then have to figure out cost information for and then translate back to the real network.
Your points are sitting on an existing graph, so I would think you want to consider just adding them to the existing graph and modifying the path costs accordingly. Find the closest point on the existing graph (edge or vertex). If it’s a vertex, it’s already part of the graph. If its an edge, cut the edge and add a vertex, splitting the cost along the edge as appropiate (proportional to distance if that’s your metric.
The points you want to travel between are now part of the graph. Compute shortest paths, which it seems like you already know how to do.
Thank you for the reply! I want to create a network that connects a set of predefined points in a way that the overall network length is minimized (minimum spanning tree). This network needs to follow existing streets.
I have detailed below my process a bit better:
1. Delaunay triangulation of the predefined points: The output from this is multiple pairs of points connected by the Delaunay triangulation. (Euclidean distance)
2. Routing (what I am trying but fail to do in the example graph): I want to find the shortest path between each pair of points, taking into account the road network. This step outputs the real distance between the pair of points, including the geometry of all the shortest paths between the pair of points.
3. Remove edges of the initial street network which are not being used by the shortest paths of step 2. This outputs the “useful” edges of the original street network.
4. Apply minimum spanning tree to the “useful” street network to find the final MST network that connects all points and where the overall length is minimized.
I am now trying to do step 2 but don’t manage to compute all shortest paths at once.
This is a classic A Star routing puzzle (Dijkstra is dead - long time ago).
I’ll describe the procedure (via code [V stands for vertex]).
- Given any valid Graph do the VV connectivity Tree (alter ego to an Adjacency Matrix).
- Using solely the VV detect possible Islands (Recursion is required for that).
- On per Island basis (meaning: using the related “sub” VV Tree and the V List):
3.1. Either solve it on per From/To basis (the classic way):
3.2 Or solve it on per From/ToAll basis (the unusual way):
If by accident you are familiar with coding (C#) I could provide various hints/tips - but not the solution (strictly internal stuff that one).
BTW: PMST is NOT a A-Star from all to target: Compare these (i.e. a classic/standard MST does not take into account the target) :
Hi @MD_9 ,
If I understand you correctly, take a look at this and let me know what you think.
Not quite finished yet but you can see it in it’s current state.
-Need to have the starting points split the road network to make perfectly complete “path” possiblilities.
-This uses a modified C# script based on the work of @w.radaczynski from his Megrachne plugin component (currently only Rhino 8, sorry) you could use Megrachne components themselves to produce this, I just found it was easier in this case to combine it into one single component.
Model Space (Click this snip for a Video Of Script In Action):
20230901_example_shortest_walk_Response01b.gh (52.4 KB)
Thank you @PeterFotiadis PFotiad0! Unfortunately I don’t know C# so it’s difficult for me to reproduce such a logic.
@michaelvollrath: I am looking at ways to reproduce the A* component you have used in your logic using Megrachne plugin but do not get through “1. Solution exception:Index was outside the bounds of the array.”:
Is there another way to reproduce this step without Rhino8?
EDIT: I cleaned my street network better on QGIS to have smoother lines and ensured that all intersections have a point. Then reapplied your flow, but get the error message:
I came across this as well and couldn’t remember if it was user error on my end or if the Megarachne solver didn’t have logic in place for handling nulls/impossible paths. In the modified version I share we have the logic we need to hopefully not throw that error.
But in actuality I had some issue trying to set it up with Megarachne and it was a lot slower setting up the graph than the single component with the Megarachne logic combined inside of it and data tree access.
Here’s the same script but with the R7 C# script component so it should work in Rhino 7 now.
The R7 version is about 2 seconds slower in the A* solver but still works as expected.
Good, that should help, cleaner the lines, the better.
Hope this helps!
20230904_example_shortest_walk_Response01c_R7.gh (49.3 KB)
Hey in Megarachne the input for the A* component shouldn’t be a whole tree, but:
- for Graph: 1 Graph
- for Start Vertex Index: 1 vertex
- for End Vertex Index: 1 vertex
Same as component that creates a Graph should take Graph Parts as a list (not as a tree) if you want to create 1 Graph from it
In the Frankenstein C# component of your work, I switched it to Tree Access for this one since he has 52 possible starting points each with 52 possible paths to solve resulting in 2,704 unique paths to solve for
Since I need to also apply the minimum spanning tree to link all points (eg. see my initial post), I ended up with one more solution, using SpiderWeb component DataTreetoGraph, which allows me to allocate the real costs (road network) of each edge connecting pairs.
The process is a very clumsy though, because I need compute two times the shortest path component, which slows down tremendously the workflow when I look at larger areas…
slow_solution_forum.gh (52.0 KB)
Hi @MD_9 ,
If I understand you correctly… You are grouping each possible point into its minimal spanning tree and then want to solve the shortest path within each MST, is that correct?
I guess my question is, why solve shortest path on the front end? Is this because the MST needs all possible connections first?
Are you trying to create “waypoints” along a route, where you need to solve the shortest path from 0 to 1, then 1 to 2, then 2 to 3, continuing on until you’ve exhausted the waypoints within each MST list?
yes exactly (your first option) - I need to first compute the shortest path with the “real” road network to use the real costs of the paths when using the MST. Running a second time the shortest path is not really necessary but I could not find a more elegant way of retranslating the MST network back to the real road network.
Thanks @MD_9 ,
Could you please elaborate on what you mean by this ^?
When you say translate do you mean geometrically, data matching, cost analysis, etc?
I mean geometrically, as shown below
Thanks, could you please internalize these inputs?
I don’t have all the plugins but I have an idea that should work without them
Yes! See attached
forum_final_step.gh (44.2 KB)