%% -	alg: archangels delegate angels to install direction signs on a chart of roads, to allow people at each of the nodes to congregate at a single point on the chart, following the shortest paths. note: type of sign for destination point.
%% -	Two signs may be needed at a point

%% (1. convert chart to graph)
%% 2a. find leg lengths
%% 2b. convert chart to directed chart
%% 3. test directed chart

%% 1. convert chart to graph

%% placesigns([[

%% find_segment_lengths([[[1,3],[2,3]],[[2,3],[3,3]],[[2,3],[2,5]],[[2,5],
%%	[3,5]],[[3,5],[3,3]],[[3,3],[3,1]],[[3,3],[4,3]],[[4,3],[4,2]],[[4,3],
%%	[4,4]],[[4,4],[5,4]]],Chart).
%% Graph = [[[[1,3],[2,3]],1],...

find_segment_lengths( [], Chart, Chart ). 
find_segment_lengths( [ Item | Items ] , Chart1 , Chart2 ) :-
	Item = [Point1, Point2], Point1 = [X1, Y1], Point2 = [X2, Y2],
	Delta_X is X2 - X1, Delta_Y is Y2 - Y1, 
        Delta_X_Squared is Delta_X ^ 2, Delta_Y_Squared is Delta_Y ^ 2,
	Segment_Length_Squared is Delta_X_Squared + Delta_Y_Squared,
	Segment_Length is sqrt( Segment_Length_Squared ),	
	append( Item, [ Segment_Length ], New_Item),
	append( Chart1 , [ New_Item ] , Chart3 ),
	find_segment_lengths( Items, Chart3, Chart2 ).

%% follow a path and add signs point back towards the end point
%% if a path connects to another path back to the end point, point to the shortest path
%% the paths done from the point are re-checked
%% if the end-point is found again, the paths are re-checked.

%% output path for each person
%% chart_to_directed_chart(Origin,
%% Origin - point the people must arrive at
%% chart_to_directed_chart([1,3],[[[[1,3],[2,3]],1]],[],[[[2,3],[1,3]]]).
chart_to_directed_chart(_,[],Chart,Chart).
chart_to_directed_chart(End_Point,Items,Chart1,Chart2) :-