%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % find_path: % Compute paths 'Path' of length 'Length' in a directed weighted % graph 'E' having total cost within a given range 'CostMin' - 'CostMax'. % % The graph 'E' is described as a set of edges where each edge % is a term of the type '[Start,End,cost(Cost)]', where 'Start' and % 'End' are the vertices of the edge and 'Cost' is its weight % (an integer). % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % find_path1: % Compute paths 'Path' of length 'Length' in an undirected weighted % graph 'E' having total cost within a given range 'CostMin' - 'CostMax'. % % The graph 'E' is described as a set of edges where each edge % is a set of the type '{Start,End,cost(Cost)}', where 'Start' and % 'End' are the vertices of the edge and 'Cost' is its weight % (an integer). % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% find_path(E,Length,CostMin,CostMax,Path) :- group(Length,_Source,Path,Cost)! & subset(Path,E) & Cost in int(CostMin,CostMax). %group(?Length,?SourceNode,?Path,?TotalCost) %'Path' is a graph path starting from 'SourceNode' group(0,_Source,{},0). %of length 'Length' and total cost 'TotalCost' group(Length,Start,{[Start,End,cost(ThisCost)]\PathRem},TotalCost) :- Length > 0 & TotalCost is ThisCost + RemCost & [Start,End,cost(ThisCost)] nin PathRem & Length1 is Length - 1 & group(Length1,End,PathRem,RemCost). %%%%%%%%%%%%%%% Sample goals for find_path/5 %%%%%%%%%%%%%%%%% % % A sample graph: % graph(g1,{[a,b,cost(3)],[a,c,cost(2)],[b,c,cost(4)],[b,d,cost(5)],[c,d,cost(3)]}). % % Sample goals: /* {log}=> graph(g1,G) & find_path(G,3,1,10,Path). Path = {[a,b,cost(3)],[b,c,cost(4)],[c,d,cost(3)]} Another solution? (y/n) y no %%%%%%%%%%%%%% {log}=> graph(g1,G) & find_path(G,3,1,7,Path). no %%%%%%%%%%%%%% {log}=> graph(g1,G) & find_path(G,2,1,10,Path). Path = {[b,c,cost(4)],[c,d,cost(3)]} Another solution? (y/n) y Path = {[a,c,cost(2)],[c,d,cost(3)]} Another solution? (y/n)y Path = {[a,b,cost(3)],[b,d,cost(5)]} Another solution? (y/n)y Path = {[a,b,cost(3)],[b,c,cost(4)]} Another solution? (y/n)y no */ %%%%%%%%%%% find_path1(E,Length,CostMin,CostMax,Path) :- group1(Length,_Source,Path,Cost)! & subset(Path,E) & Cost in int(CostMin,CostMax). %group1(?Length,?SourceNode,?Path,?TotalCost) %'Path' is a graph path starting from 'SourceNode' group1(0,_Source,{},0). %of length 'Length' and total cost 'TotalCost' group1(Length,Start,{{Start,End,cost(ThisCost)}\PathRem},TotalCost) :- Length > 0 & TotalCost is ThisCost + RemCost & {Start,End,cost(ThisCost)} nin PathRem & Length1 is Length - 1 & group1(Length1,End,PathRem,RemCost). %%%%%%%%%%%%%%% Sample goals for find_path1/5 %%%%%%%%%%%%%%%%% % % A sample graph: % graph(g2,{{a,b,cost(3)},{a,c,cost(2)},{b,c,cost(4)},{b,d,cost(5)},{c,d,cost(3)}}). % % Sample goals: /* {log}=> graph(g2,G) & find_path1(G,3,1,10,Path). Path = {{a,c,cost(2)},{b,d,cost(5)},{c,d,cost(3)}} Another solution? (y/n)y Path = {{a,b,cost(3)},{b,c,cost(4)},{c,d,cost(3)}} Another solution? (y/n)y Path = {{a,b,cost(3)},{a,c,cost(2)},{c,d,cost(3)}} Another solution? (y/n)y Path = {{a,b,cost(3)},{a,c,cost(2)},{b,d,cost(5)}} Another solution? (y/n)y Path = {{a,b,cost(3)},{a,c,cost(2)},{b,c,cost(4)}} Another solution? (y/n)y no {log}=> %%%%%%%%%%%%%% {log}=> graph(g2,G) & find_path1(G,3,1,7,Path). no %%%%%%%%%%%%%% {log}=> graph(g2,G) & find_path1(G,2,1,6,Path). Path = {{a,c,cost(2)},{c,d,cost(3)}} Another solution? (y/n)|: y Path = {{a,c,cost(2)},{b,c,cost(4)}} Another solution? (y/n)y Path = {{a,b,cost(3)},{a,c,cost(2)}} Another solution? (y/n)y no */