Retrieving all edges of specific type starting from given node

Question

I have a problem with graph traversal. My use case is not solvable using typical graph traversal algorithms (DFS, BFS). I want traverse nodes, starting from specific Node (N), where edge is of type ET. I want to retrieve all nodes with their &path from N to the node. This is possible using one of the Orient's strategies but I want to have all possible paths - not only one.

Sample:

For above graph there are two paths from R to C :

• Root -> A -> C
• Root -> B -> C

My graphs can be bit more comples but the idea is the same.

In OrientDB documentation I found that there's a method on Graph that returns all edges (getEdgesofClass(String class)). I thought that I might solve my problem If I could somehow specify the graph (subgraph of main graph - only nodes that are connected with Root node) that on which I want to call this method.

Thanks for all the input.

Answer 1

This answer is rather late ... but.

What you are trying is not possible in OrientDB with one query/mechanism. The reason being OrientDB does not visit a vertex once visited. Which is a practical design choice for the database. However, this leaves no easy way to get all paths from one vertex to another, if there are more than one path.

The shortextDistance() function will find the shortest distance between two vertices. In your case it will either give Root -> A -> C or Root -> B -> C, which absolutely goes nowhere to solve your problem.

Your best bet is TRAVERSE. If you traverse * from Root and select $path you will get the following paths (SELECT $PATH FROM(TRAVERSE * [rid or Root])), you will get the following (or the other way round):

1. Root-->A-->C
2. Root-->B

You will never get the Root-->B-->C (say). Reason being the 'C' vertex has been visited and will not be visited again.

Your best shot is to traverse the edges and vertices and form the path yourself.

TRAVERSE out(),outE() FROM [rid or Root] will give you all the vertices, Root, A, B and all the edges. With is you can form graphs with libraries like JGraphT, which has the functionality to find all paths (Refer: AllDirectedPaths).