[Haskell-cafe] Graph type

[Ivan Lazar Miljenovic]

C K Kashyap <ckkashyap at gmail.com> writes:

> 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.

Sure there is (using p = |V|, q = |E|):

* Finding a particular node is O(p).

* Adding an edge to an already existing node is also O(p).

* Finding reverse edges is O(q) (probably more actually since you'd be
  checking every node that you have and then checking if the other end
  is in the list of relationships).

etc.

The main advantage of your type is that it's O(1) to add a new node +
successor edges.

Now, depending upon what you're wanting to do, this may suffice.
However, there are a couple of alternatives:

* Use Data.Graph from containers

* Use either Data.Graph.Inductive.Tree or
  Data.Graph.Inductive.PatriciaTree (which has better performance but
  doesn't allow multiple edges) from fgl.

* If you still want a custom type, then something like "Map v (Set v)"
  would be much more efficient than using [(v, [v])] (this could be
  improved at the expense of disk space and more bookkeeping by using
  "Map v (Set v, Set v)" to store both successor and predecessor edges).

>
>
> 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
>>

-- 
Ivan Lazar Miljenovic
Ivan.Miljenovic at gmail.com
IvanMiljenovic.wordpress.com