Re: [Haskell-cafe] Graph type

13 Jun 2010

      I love this list ... thanks Roman.

I take it that there is nothing obviously inefficient about this approach to
graph - as in the graph type.

On Mon, Jun 14, 2010 at 12:02 AM, Roman Cheplyaka  wrote:
...
* C K Kashyap  [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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
-- 
Regards,
Kashyap