I love this list ... thanks Roman.<br><br>I take it that there is nothing obviously inefficient about this approach to graph - as in the graph type.<br><br><br><div class="gmail_quote">On Mon, Jun 14, 2010 at 12:02 AM, Roman Cheplyaka <span dir="ltr">&lt;<a href="mailto:roma@ro-che.info">roma@ro-che.info</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">* C K Kashyap &lt;<a href="mailto:ckkashyap@gmail.com">ckkashyap@gmail.com</a>&gt; [2010-06-13 22:45:44+0530]<br>

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