[Haskell-cafe] Graph type

[Roman Cheplyaka]

* C K Kashyap <ckkashyap at gmail.com> [2010-06-13 22:45:44+0530]
> 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