[rdfweb-dev] The shorest way between friend and another friend

[Danny Ayers]

Hi,

'shortest path' is a standard problem of graph theory, and is pretty well
documented on the web, e.g.

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html

the graph you'd be looking at would feature the people as nodes and the
foaf:knows connections as edges.

If I remember correctly the usual way the graphs are represented in these
algorithms is with the edges having weights - a typical use for this might
be finding the shortest route between two cities, so the weight would be the
distance. I think most of the algorithms consider the weights to be the same
in both directions, but there certainly are algorithms out there that can
operate on A knows B when B doesn't know A - a quick google on 'digraph
shortest path' got this:

http://www.nist.gov/dads/HTML/bellmanford.html


I think everyone will be really interested in how you get on with this -
please keep us informed!

Cheers,
Danny.


> -----Original Message-----
> From: rdfweb-dev-bounces at vapours.rdfweb.org
> [mailto:rdfweb-dev-bounces at vapours.rdfweb.org]On Behalf Of se seman
> Sent: 21 April 2003 20:30
> To: rdfweb-dev at vapours.rdfweb.org
> Subject: [rdfweb-dev] The shorest way between friend and another friend
>
>
> Hi, friends
>
> I am thinking a problem about how to find the shorest
> way between friend and another friend in the FOAF
> network based on people's RDF file.
> It is different from the privious work of Codepiction
> Paths which is used to find the shortest way through
> codepict  pictures between friends.
> (http://rdfweb.org/people/damian/2002/02/foafnation/).
>
> In my opinion, I more care the 'knows' item in the
> FOAF vocabulary instead of the codipict pictures.
> http://xmlns.com/foaf/0.1/
>
> Using 'knows' item, people can make FOAF network. But
> the connetion between two friends might be single way
> or double way which means if A knows B according to
> A's RDF file, B may or may not know A according to B's
> RDF.
> That is different to Libby's codipict idea: if a
> picture shows two people A and B, then A and B will
> know each other which means the way between A and  B
> has not direction(arrow). I thought this method will
> not suit for the real RDF file which people write by
> themselves.
>
> So according to what I describled above, I would like
> to say finding a shortest way between 2 person in the
> FOAF net work based on people's RDF file is worth to
> do .
>
> Welcome any feedback about my idea from people here.
>
> Best
> Gao Wei
>
> __________________________________________________
> Do you Yahoo!?
> The New Yahoo! Search - Faster. Easier. Bingo
> http://search.yahoo.com
>
> _______________________________________________
> rdfweb-dev mailing list
> rdfweb-dev at vapours.rdfweb.org
> http://rdfweb.org/mailman/listinfo/rdfweb-dev