Re: Graph datatype addition

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?

Regards,

Atri

--
Regards,

Atri
l'apprenant

On Tue, Apr 30, 2013 at 10:58 AM, Jaime Casanova <jaime(at)2ndquadrant(dot)com> wrote:
> On Mon, Apr 29, 2013 at 10:51 PM, Peter Eisentraut <peter_e(at)gmx(dot)net> wrote:
>> On Sun, 2013-04-28 at 22:55 -0700, Atri Sharma wrote:
>>> If we add support for weighted graphs, we can probably add support for
>>> some common graph algorithms, such as Djikstra's algorithm, Bellman
>>> Ford algorithm, a MST making algorithm, network flow algorithms.
>>
>> You might find that pgRouting already does much of this.
>>
>
> actually, i was going to suggest to Atri to take a look at that,
> pgrouting is currently in develop of v2.0 which will rewrite some
> parts (including some of the algorithms).
>
> Maybe this datatype could fit better as part of pgrouting
>
> --
> Jaime Casanova www.2ndQuadrant.com
> Professional PostgreSQL: Soporte 24x7 y capacitación
> Phone: +593 4 5107566 Cell: +593 987171157

--
Regards,

Atri
l'apprenant