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 <r...@ro-che.info> wrote:
> * C K Kashyap <ckkash...@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@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
--
Regards,
Kashyap
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
