* C K Kashyap
Hi, I am trying to write a routine that would generate a graph - where each vertex would be a string.
type Graph v = [(v,[v])] -- list of tuples of vertices and adjacent vertices list
addEdgeToGraph :: Graph -> String -> String -> Graph
I am having trouble coming up with the body of this function - that takes the original graph, and an edge (string -> string) and the produces the new graph.
If you know that the vertices already exist and you need only to add an edge, then you just go through all the vertices, compare current vertex to given ones and if they match add a vertex. \begin{code} addEdgeToGraph :: Graph String -> String -> String -> Graph String addEdgeToGraph gr v1 v2 = map modify gr where modify (v,vs) | v == v1 = (v,v2:vs) modify (v,vs) | v == v2 = (v,v1:vs) modify x = x \end{code} Otherwise it is possible that one (or both) vertex doesn't exist yet, so you first need to "try" the first version, and if at least one of the vertex is not found, add it to the list. You can use fold for this. \begin{code} addEdgeToGraph' :: Graph String -> String -> String -> Graph String addEdgeToGraph' gr v1 v2 = let (newgr, (foundV1, foundV2)) = foldr modify ([],(False,False)) gr in (if foundV1 then [] else [(v1,[v2])]) ++ (if foundV2 then [] else [(v2,[v1])]) ++ newgr where modify (v,vs) (lst,(_,foundV2)) | v == v1 = ((v,v2:vs):lst, (True,foundV2)) modify (v,vs) (lst,(foundV1,_)) | v == v2 = ((v,v1:vs):lst, (foundV1,True)) modify v (lst,f) = (v:lst,f) \end{code} -- Roman I. Cheplyaka :: http://ro-che.info/ "Don't let school get in the way of your education." - Mark Twain