[Haskell-cafe] Graph type

[C K Kashyap]

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 <roma at ro-che.info> wrote:

> * 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
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



-- 
Regards,
Kashyap
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100613/c64e6041/attachment.html