Thanks Roman.<br>I think I'll try out Data.Graph in that case.<br><br><div class="gmail_quote">On Mon, Jun 14, 2010 at 8:53 AM, Ivan Lazar Miljenovic <span dir="ltr"><<a href="mailto:ivan.miljenovic@gmail.com">ivan.miljenovic@gmail.com</a>></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;"><div class="im">C K Kashyap <<a href="mailto:ckkashyap@gmail.com">ckkashyap@gmail.com</a>> writes:<br>
<br>
> I love this list ... thanks Roman.<br>
><br>
> I take it that there is nothing obviously inefficient about this approach to<br>
> graph - as in the graph type.<br>
<br>
</div>Sure there is (using p = |V|, q = |E|):<br>
<br>
* Finding a particular node is O(p).<br>
<br>
* Adding an edge to an already existing node is also O(p).<br>
<br>
* Finding reverse edges is O(q) (probably more actually since you'd be<br>
checking every node that you have and then checking if the other end<br>
is in the list of relationships).<br>
<br>
etc.<br>
<br>
The main advantage of your type is that it's O(1) to add a new node +<br>
successor edges.<br>
<br>
Now, depending upon what you're wanting to do, this may suffice.<br>
However, there are a couple of alternatives:<br>
<br>
* Use Data.Graph from containers<br>
<br>
* Use either Data.Graph.Inductive.Tree or<br>
Data.Graph.Inductive.PatriciaTree (which has better performance but<br>
doesn't allow multiple edges) from fgl.<br>
<br>
* If you still want a custom type, then something like "Map v (Set v)"<br>
would be much more efficient than using [(v, [v])] (this could be<br>
improved at the expense of disk space and more bookkeeping by using<br>
"Map v (Set v, Set v)" to store both successor and predecessor edges).<br>
<div><div></div><div class="h5"><br>
><br>
><br>
> On Mon, Jun 14, 2010 at 12:02 AM, Roman Cheplyaka <<a href="mailto:roma@ro-che.info">roma@ro-che.info</a>> wrote:<br>
><br>
>> * C K Kashyap <<a href="mailto:ckkashyap@gmail.com">ckkashyap@gmail.com</a>> [2010-06-13 22:45:44+0530]<br>
>> > Hi,<br>
>> > I am trying to write a routine that would generate a graph - where each<br>
>> > vertex would be a string.<br>
>> ><br>
>> > type Graph v = [(v,[v])] -- list of tuples of vertices and adjacent<br>
>> > vertices list<br>
>> ><br>
>> > addEdgeToGraph :: Graph -> String -> String -> Graph<br>
>> ><br>
>> > I am having trouble coming up with the body of this function - that takes<br>
>> > the original graph, and an edge (string -> string) and the produces the<br>
>> new<br>
>> > graph.<br>
>><br>
>> 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 -> String -> String -> 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't exist yet, so<br>
>> you first need to "try" 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' :: Graph String -> String -> String -> Graph String<br>
>> addEdgeToGraph' 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,<br>
>> (True,foundV2))<br>
>> modify (v,vs) (lst,(foundV1,_)) | v == v2 = ((v,v1:vs):lst,<br>
>> (foundV1,True))<br>
>> modify v (lst,f) = (v:lst,f)<br>
>> \end{code}<br>
>><br>
>> --<br>
>> Roman I. Cheplyaka :: <a href="http://ro-che.info/" target="_blank">http://ro-che.info/</a><br>
>> "Don't let school get in the way of your education." - Mark Twain<br>
>> _______________________________________________<br>
>> 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>
>><br>
<br>
--<br>
</div></div><font color="#888888">Ivan Lazar Miljenovic<br>
<a href="mailto:Ivan.Miljenovic@gmail.com">Ivan.Miljenovic@gmail.com</a><br>
<a href="http://IvanMiljenovic.wordpress.com" target="_blank">IvanMiljenovic.wordpress.com</a><br>
</font></blockquote></div><br><br clear="all"><br>-- <br>Regards,<br>Kashyap<br>