Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

shortest path #1875

Closed
deluxxx opened this issue Dec 6, 2013 · 3 comments
Closed

shortest path #1875

deluxxx opened this issue Dec 6, 2013 · 3 comments
Assignees
Labels

Comments

@deluxxx
Copy link

deluxxx commented Dec 6, 2013

Hello,
I need return all my friends of friends and (short road) I created schema where I have relationships :
I have 10 users and relationships :
Mirek known - > Sylwia
Mirek known -> Marcin known - > Seba
Mirek known -> Jarek
Mirek known -> Edek known -> Kaszczuk known -> Ana known -> unknown
Mirek known -> Damian known Edek known -> Kaszczuk known -> Ana known -> unknown

And I need all friends of friends Mirek #28:2184
so that is :
Seba #28:2191
Kaszczuk #28:2189

When I use that functions
select shortestPath(#28:2184,#28:2189).asString()

is OK [v(User)[#28:2184], v(User)[#28:2185], v(User)[#28:2189]]

But when I use that :
select $path, $depth from (traverse in,out,in_Friend,out_Friend from #28:2184 while $depth <= 4) where @Class='User'

To seba is ok : #28:2184.out_Friend[idx:1].#26:1229.in.#28:2183.out_Friend[idx:1].#26:1246.in.#28:2191
but to kaszczuk go around : #28:2184.out_Friend[idx:0].#26:1227.in.#28:2182.out_Friend[idx:1].#26:1235.in.#28:2185.out_Friend[idx:2].#26:1240.in.#28:2189
screenshot from 2013-12-06 11 31 47
screenshot from 2013-12-06 11 32 46
screenshot from 2013-12-06 11 34 27

@lvca
Copy link
Member

lvca commented Dec 11, 2013

What's the problem? depth level > 4?

By the way this query is too expensive if you only look only for friendships. Try rather this:

select $path, $depth from (traverse both('Friend') from #28:2184 while $depth <= 4)

By using both() it jumps the edges, just traverse them.

@ghost ghost assigned lvca Dec 11, 2013
@deluxxx
Copy link
Author

deluxxx commented Dec 19, 2013

Hello, I'm sorry you had to wait so long,
I have graph relationship all edges here are friend bidirectional.
I need something like traverse + shortestPath

untitled diagram

I need friends of friends. Level 2 friendship.

We start in Mirek
SHOULD BE :
First level friends are :
Damian , Edyta , Jarek, Marcin , Sylwia

Second level friends are :
Kasczuk , Seba

Third level friends are :
Ana

Fourth level friends are :
Abdul

When I execute query :
select $path, $depth from (traverse both('Friend') from #28:1342 while $depth <= 4)

but we have different :
Edyta should be to first level but she is in second level.
Kaszczuk should be to second level but she is on third level.

screenshot from 2013-12-19 14 38 59

@lvca
Copy link
Member

lvca commented Dec 19, 2013

By default OrientDB uses depth-first strategy, while for your case the breadth-first is more correct. Try:

select $path, $depth from (traverse both('Friend') from #28:1342 while $depth <= 4 strategy BREADTH_FIRST)

Fore more info: https://github.com/orientechnologies/orientdb/wiki/Java-Traverse#traversing-strategies

@lvca lvca closed this as completed Dec 19, 2013
@lvca lvca modified the milestone: 1.6.3 Aug 5, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Development

No branches or pull requests

2 participants