Sent from my iPad
On 02-May-2013, at 4:33, Misa Simic <misa.si...@gmail.com> wrote:
>
>
> On Wednesday, May 1, 2013, Atri Sharma wrote:
>> Hi all,
>>
>> Please find a probable prototype for the same:
>>
>> struct GraphNode
>> {
>> Oid NodeOid; // Oid of the row which is the node here. We will
>> store an identifier to it here rather than the complete row(with data)
>> itself.
>> AdjacencyList *list; // Pointer to the node's adjacency list.
>> };
>>
>> struct AdjacencyList
>> {
>> Oid[] neighbours_list;
>> };
>>
>> struct AdjacencyList is probably the 'hottest' data structure in our
>> entire implementation. We can think of making a cache of recently
>> accessed struct AdjacencyList instances, or the AdjacencyList(s) of
>> the neighbours of the recently accessed nodes, because, they are most
>> likely to be accessed in near future. Advice here, please?
>>
>> So.
>>
>> struct AdjacencyCache
>> {
>> Oid[] cache_values;
>> };
>>
>> push and pop functions for AdjacencyCache follow.
>>
>> We need a replacement and invalidation algorithm for the cache. I feel
>> a version of LRU should be good here.
>>
>> I have not given a prototype for operations and algorithm implementations.
>>
>> I feel,as suggested by Peter and Jaime, we can look at pgRouting code
>> for algorithm implementations.
>>
>> Florian's concerns are mitigated here to some extent,IMO. Since the
>> nodes and linkings are loosely coupled, and not represented as a
>> single representation, updating or changing of any part or adding a
>> new edge is no longer an expensive operation, as it only requires a
>> lookup of GraphNode and then its AdjacencyList. If we use the cache as
>> well, it will further reduce the lookup costs.
>>
>> I have not yet thought of the user visible layer as suggested by Jim.
>> Probably. once we are ok with the internal layer, we can move to the
>> user visible layer.
>>
>> Advice/Comments/Feedback please?
>
> Honestly - I think I dont understand proposal...
>
> Datatypes - are about values - what will be stored in that column in a
> table....
>
> Datatype - cant have any clue about "rows"
>
> How I understand what you described - you can achieve the same with pure SQL
> - struct are equvalent to graph tables... Instead od Oid column will store
> PKs of nodes table...
>
Yes, I agree.I need to think more.
Let me get back with a deeper proposal.
Regards,
Atri
