Re: Graph datatype addition

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