------------------------------------------------------------------------------------------------
-- the code works with just 4 vertices and assymetry was not yot tested
-- there might be any sort of bugs, any help appreciated xD
--
-- author: felipe gallois
------------------------------------------------------------------------------------------------

sl = [[0,1,10,10],[1,0,1,2],[10,1,0,10],[10,2,10,0]] -- test list(matrix) with 4 vertices
ssl = [[0,1,2,3],[1,0,1,2],[2,1,0,3],[3,2,3,0]] -- the same test list as above, but the shortest pathes already found

al = [[0,1,3,5],[2,0,4,1],[2,3,0,3],[1,3,1,0]] -- another test list with 4 vertices, this one is assymetric
sal = [[0,1,3,2],[2,0,2,1],[2,3,0,3],[1,3,1,0]] -- the same test list as above, but the shortest pathes already found

-- returns the lenght of the edge that unites two vertices
-- 'x' is the origin vertex
-- 'y' is the destination vertex
-- 'l' is the list(matrix) of distances
dist :: Int -> Int -> [[a]] -> a
dist x y l = l!!x!!y

-- returns the distance from one vertex to another, passing through others
-- 'x' is the list of vertices that the function will tour over
-- 'y' is the destination vertex
-- 'l' is the matrix list
dist_list (x:xs:xss) y l 
	| xss == [] = dist x xs l + dist xs y l
	| otherwise = (dist x xs l) + (dist_list (xs:xss) y l)

-- returns the shortest path between two vertices
-- 'x' is the origin vertex
-- 'y' is the destination vertex
-- 'l' is the list(matrix) of distances
shortest_path :: (Ord a, Num a) => Int -> Int -> [[a]] -> a
shortest_path x y l = minimum (all_paths_between [x] y l (filter (/= y) (filter (/= x) [0..((length l)-1)])))

-- returns a list with the length of all possible ways from one vertex to another
-- it gets the origin vertex as a single member of a list, the destination vertex as an Int
-- the matrix of distances and finally another list containing the remaining vertices of the matrix
-- 'x' is the origin vertex passed to the function as a single element list
-- 'a' is the destination vertex
-- 'l' is the matrix list
-- 'y' is the auxiliar matrix, which is used to retain the elements that are neither the origin nor the destination vertices
-- the implementation still works with just 4 vertices
all_paths_between :: Num a => [Int] -> Int -> [[a]] -> [Int] -> [a]
all_paths_between x a l [] = [dist_list x a l]
all_paths_between (x:xs) a l (y:ys)
	| length (x:xs) == 1 = [(dist x a l)] ++ (all_paths_between [x,y] a l ys) ++ (all_paths_between ([x] ++ dfilter) a l [y])
	| otherwise = [(dist_list (x:xs) a l)] ++ (all_paths_between ((x:xs) ++ [y]) a l ys)
		where dfilter = filter (/= y) ys