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

[se seman]

--- Danny Ayers <danny666 at virgilio.it> wrote:
> Hi, 
Hello!

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

Yes, exactly.
 
> 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. 

No, the costs(weighs) between a pair of nodes depend
on a lot o f factors (capacity, delay,congestion...).
Take FOAF as a example, the costs between two friends
depond on how much you know that friend. If you know
this friend very much, that cost should be very small.
Otherwise it will become large.
So giving two rutes, A-2->B-3->C and A-8->C, we might
prefer the first choice even though there are two hops
between A and C. But currently, FOAF vocabulary has
not given such item to describe such property and I
can not find other items can be considered as the
factors related with the cost between two friends. So
I will assume the cost between two persons are same at
this moment and leave the 'cost' parameter in the
future work. 



>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

Basiclly, I will choose Bellman-Ford's shortest path
algorithm.
 

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

Thanks!

Best,
Gao Wei
 
> > -----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