6 degrees of separation

[cegme]

Here is a problem for you @virup @clintpgeorge @supriyan,

Given two papers how would you write a db query to find the "shortest" path between them.

Vertices are papers and edges and citations/references. We can think of the edges as being undirected. It is certainly possible that no path exists between two papers.

Can you implement a solution to this?

[virup]

If we assume that there is a link between the two papers and the link is no greater than N (lets say N = 3), we can hard code it in the query itself.

given: from paper id = fpid to paper id = tpid

Aassuming the reference table as: reference(pid:int, refid:int)

For degree two (N = 2), we will have :

select B.pid from reference A, reference B where A.refid = B.pid and A.pid = fpid and B.refid = tpid

We can extend it to N = 3, and higher

Will that approach work?

Viru

On Fri, Sep 14, 2012 at 1:48 PM, Christan Grant notifications@github.comwrote:

Here is a problem for you @virup https://github.com/virup @clintpgeorgehttps://github.com/clintpgeorge @supriyan https://github.com/supriyan,

Given two papers how would you write a db query to find the "shortest" path between them.

Vertices are papers and edges and citations/references. We can think of the edges as being undirected. It is certainly possible that no path exists between two papers.

Can you implement a solution to this?

— Reply to this email directly or view it on GitHubhttps://github.com/cegme/grisham/issues/17.

[cegme]

Hard coding will not give you full credit lol.

...Let's say you are using Postgres 9.1

On Friday, September 14, 2012, Viru Kanjilal wrote:

If we assume that there is a link between the two papers and the link is no greater than N (lets say N = 3), we can hard code it in the query itself.

given: from paper id = fpid to paper id = tpid

Aassuming the reference table as: reference(pid:int, refid:int)

For degree two (N = 2), we will have :

select B.pid from reference A, reference B where A.refid = B.pid and A.pid = fpid and B.refid = tpid

We can extend it to N = 3, and higher

Will that approach work?

Viru

— Reply to this email directly or view it on GitHubhttps://github.com/cegme/grisham/issues/17#issuecomment-8570100.

Christan Grant <><

[supriyan]

Why is it important to have a SQL query for this? If the data is available in the database, cant we employ an algorithm to get the shortest path? That algorithm may make use of SQL queries.

-Sup

On Fri, Sep 14, 2012 at 2:01 PM, Christan Grant notifications@github.comwrote:

Hard coding will not give you full credit lol.

...Let's say you are using Postgres 9.1

On Friday, September 14, 2012, Viru Kanjilal wrote:

If we assume that there is a link between the two papers and the link is no greater than N (lets say N = 3), we can hard code it in the query itself.

given: from paper id = fpid to paper id = tpid

Aassuming the reference table as: reference(pid:int, refid:int)

For degree two (N = 2), we will have :

select B.pid from reference A, reference B where A.refid = B.pid and A.pid = fpid and B.refid = tpid

We can extend it to N = 3, and higher

Will that approach work?

Viru

— Reply to this email directly or view it on GitHub< https://github.com/cegme/grisham/issues/17#issuecomment-8570100>.

Christan Grant <><

— Reply to this email directly or view it on GitHubhttps://github.com/cegme/grisham/issues/17#issuecomment-8570275.

Supriya Nirkhiwale 4337 NW 35th Terrace Gainesville, FL 32605 USA

[cegme]

Hey the Issues is closed. Check out the solution @virup and I came up with here: https://gist.github.com/3725408