Shortest walk In a network of curves

I have a surface divided with uv points and connected all points with a curve hence forming a network of curve which node can i use to find the Shortest distance between any two points on the network…?

Edit: I want the shortest path of travel via the curves in the network.

Look into the Lunchbox nodes for ShortestPath. Note you need a single node for the start and end, which shouldn’t be a curve in the network.

Good solve for your pipe routing. :smiley:

Hi @JacobSmall,
Thanks for the suggestion,Its a better solution that i am getting now, but it still needs improvement.
I am getting a shortest path but I may need all shortest paths to choose the one with minimum turn,No body would like to have so many turns in their pipes :frowning:

Here is a small update to this,
I found a way to list all the paths,but this graph simply crashes when I set the grid sizing to more than 5 grids and I don’t know the reason it works fast enough for 4 grids though.

new try latest.dyn (144.3 KB)

Here is the code I have copied from somewhere but its difficult to optimize it for running lesser no.of times giving only all the shortest outputs

I’ve got multiple unresolved nodes in your graph - can you annotate the custom nodes using monocle for me?

Try this. (Doesn’t always work as expected though)
shrtPth-20191029.dyn (12.6 KB)

Shortest Path (minimizing bends)…

Shortest Path (otherwise)…

//Shortest Path
def ner(st,en,dr,cr:var[]..[])
{
	c1 = List.FilterByBoolMask(cr,st.DistanceTo(cr)==0)["in"];
	e1 = List.Flatten(List.SetDifference(List.Transpose([c1.StartPoint,c1.EndPoint])<1>,st),-1);
	c2 = List.SortByKey(c1, e1.DistanceTo(en))["sorted list"];
	e2 = List.SortByKey(e1, e1.DistanceTo(en))["sorted list"];
	d2 = c2.TangentAtParameter(c2.ParameterAtPoint(e2));

	b2 = Vector.ByTwoPoints(c2.StartPoint,c2.EndPoint).IsParallel(dr);
	c3 = List.IsEmpty(List.FilterByBoolMask(c2,b2)["in"]) ? c2[0] : List.FilterByBoolMask(c2,b2)["in"][0];
	e3 = List.IsEmpty(List.FilterByBoolMask(e2,b2)["in"]) ? e2[0] : List.FilterByBoolMask(e2,b2)["in"][0];
	d3 = c3.TangentAtParameter(c3.ParameterAtPoint(e3));

	return [[c2[0],e2[0],d2[0]],[c3,e3,d3]];
};

def shPh1 (st,en,crvs:var[]..[])
{
	dr = Vector.ByTwoPoints(st,en);
	ds = st.DistanceTo(en);
	shPth1 = [Imperative]
	{
		ph = [];
		ct = 0;
		while (ds > 0)
		{
			cr = ner(st,en,dr,crvs)[0];
			ph[ct] = cr[0];
			st = cr[1];
			dr = cr[2];
			crvs = List.SetDifference(crvs,ph);
			ds = st.DistanceTo(en);
			ct = ct + 1;
		}
		return ph;
	}
	return shPth1;
};

def shPh2 (en1,en2,en,crvs:var[]..[])
{
	cv1 = Math.Sum(shPh1 (en1,en,crvs).Length);
	cv2 = Math.Sum(shPh1 (en2,en,crvs).Length);
	return cv1 >= cv2 ? 1 : 0;
};

def shPh3 (st1,en1,cvs:var[]..[])
{
	return = [Imperative]
	{
		cv1 = ner(st1,en1,Vector.ByTwoPoints(st1,en1),cvs);
		ne1 = cv1[shPh2 (cv1[0][1],cv1[1][1],en1,cvs)];
		ph = [ne1[0]];
		st = ne1[1];
		dr = ne1[2];
		ds = st.DistanceTo(en1);
		ct = 1;

		while (ds > 0)
		{
			cs = List.SetDifference(cvs,ph);
			cr = ner(st,en1,dr,cs);
			ne = cr[shPh2 (cr[0][1],cr[1][1],en1,cs)];
			ph[ct] = ne[0];
			st = ne[1];
			dr = ne[2];
			ds = st.DistanceTo(en1);
			ct = ct + 1;
		}
		return ph;
	}
};

//Sample Grid
a = 0..100..10;
p1 = Point.ByCoordinates(a<1>,a<2>);
p2 = List.Transpose(p1);
p3 = List.DropItems(List.Sublists(p1<1>,0..1,1)<1>,-1);
p4 = List.DropItems(List.Sublists(p2<1>,0..1,1)<1>,-1);
l1 = Line.ByBestFitThroughPoints(List.Flatten([p3,p4],2));

r1 = Rectangle.ByCornerPoints(Point.ByCoordinates([0,0,100,100],[0,100,100,0]));
r2 = Rectangle.ByCornerPoints(Point.ByCoordinates([30,30,70,70],[10,70,70,10]));
s1 = r1.Patch().TrimWithEdgeLoops([r1,r2]);
l2 = List.RemoveIfNot(List.Flatten(l1.Intersect(s1),-1),"Line");
3 Likes

Hi @Vikram_Subbaiah thanks for your time and sorry for the delay I have been on a Vacation last week,
The Image you shared looks great…!
Your code had some conflict with the Orchid package which says multiple definition for “List” I tried to rename your List,Vector to DSCore.List ect… but it returned a null value I even tried uninstalling Orchid the clash was resolved but still returns null,I am doing any thing wrong?

Also could you please add some comment so that I can read your code easily,I am not very comfortable with DS at least a brief description would help me create the same with nodes and wires.

Thank you so much…!

Hi @JacobSmall
Here is the annotated graph
new try latest_anno_.dyn (146.6 KB)

1 Like

Thanks @JacobSmall and @Vikram_Subbaiah,

Finally found a solution that takes all shortest paths and counts the least number bending,
Thanks to the Source code of NetworkX package.

#Thanks to NetworkX`
keys=IN[0]
values=IN[1]
G = dict(zip(keys,values)) 
       
source=IN[2]
target=IN[3]
path=[]
         
def predecessor(G,source,target=None,cutoff=None,return_seen=None):
    level=0                  # the current level
    nextlevel=[source]       # list of nodes to check at next level
    seen={source:level}      # level (number of hops) when seen in BFS
    pred={source:[]}         # predecessor dictionary
    while nextlevel:
        level=level+1
        thislevel=nextlevel
        nextlevel=[]
        for v in thislevel:
            for w in G[v]:
                if w not in seen:
                    pred[w]=[v]
                    seen[w]=level
                    nextlevel.append(w)
                elif (seen[w]==level):# add v to predecessor list if it
                    pred[w].append(v) # is at the correct level
        if (cutoff and cutoff <= level):
            break

    if target is not None:
        if return_seen:
            if not target in pred: return ([],-1)  # No predecessor
            return (pred[target],seen[target])
        else:
            if not target in pred: return []  # No predecessor
            return pred[target]
    else:
        if return_seen:
            return (pred,seen)
        else:
            return pred


def all_shortest_paths(G, source, target, weight=None, method='dijkstra'):
    method = 'unweighted' if weight is None else method
    if method == 'unweighted':
        pred = predecessor(G, source)
    else:
        raise ValueError('method not supported: {}'.format(method))

    if target not in pred:
        raise ValueError('Target {} cannot be reached'
                                'from Source {}'.format(target, source))

    stack = [[target, 0]]
    top = 0
    while top >= 0:
        node, i = stack[top]
        if node == source:
            yield [p for p, n in reversed(stack[:top + 1])]
        if len(pred[node]) > i:
            top += 1
            if top == len(stack):
                stack.append([pred[node][i], 0])
            else:
                stack[top] = [pred[node][i], 0]
        else:
            stack[top - 1][1] += 1
            top -= 1

OUT=all_shortest_paths(G, source, target, weight=None, method='dijkstra')

graph here : core version_0.3.dyn (183.9 KB)

2 Likes