CODEWITHSUNDEEP
neo4jspring-data-neo4j-4neo4j-ogm
raj
raj

Reputation: 127

need to find shortest path between two nodes based on one of the node's property value -USING JAVA and 3.0.1 neo4j version

Assume My Graph is having the below paths

      (3)<--[IS_LOCATED_AT,9]--(8)--[CARRIES,77]-->(53)<--[CARRIES,76]--(7)--[IS_LOCATED_AT,8]-->(2)
      (3)<--[IS_LOCATED_AT,9]--(8)--[BELONGS_TO,7]-->(1)<--[BELONGS_TO,6]--(7)--[IS_LOCATED_AT,8]-->(2)
      (3)<--[IS_LOCATED_AT,9]--(8)--[BELONGS_TO,7]-->(55)<--[BELONGS_TO,61]--(7)--[IS_LOCATED_AT,8]-->(2)
      (3)<--[IS_LOCATED_AT,9]--(8)--[CARRIES,77]-->(57)<--[CARRIES,75]--(7)--[IS_LOCATED_AT,8]-->(2)

Assume paths having the below mentioned properties

     (53) node has the properties--{Name:A}

     (1) node has properties--{Name:B}

     (55) node has properties--{Name:C}

     (57) node has properties-- {Name:D}

Assume If I call the shortestpath between nodes (3) and (2) , I am getting the below output when called the below mentioned method.

assume current Output is:

        (3)<--[IS_LOCATED_AT,9]--(8)--[BELONGS_TO,7]-->(1)<--[BELONGS_TO,6]--(7)--[IS_LOCATED_AT,8]-->(2)
        (3)<--[IS_LOCATED_AT,9]--(8)--[BELONGS_TO,7]-->(55)<--[BELONGS_TO,61]--(7)--[IS_LOCATED_AT,8]-->(2)

But My requirement is 1)It should filter the paths based on node property before calling the shortestpath api assume my filter is {Name:D} which is a property of (57) node mentioned above

Then My output should be as below when called shortespath method menntioned below as the below path having node (57) having property {Name:D} .

Expected Output with filter

          (3)<--[IS_LOCATED_AT,9]--(8)--[CARRIES,77]-->(57)<--[CARRIES,75]--(7)--[IS_LOCATED_AT,8]-->(2)

I dont want to use cypher for this. Can anybody help me.

         public static Iterable<Path> shortestPath(Node sourceNode, Node destNode)
         {
            Integer depth=100;
            PathExpander<?> expander;
            List<Path> paths = new ArrayList<>();
              if ( orderedRelTypes == null )
                {
                   expander = PathExpanders.allTypesAndDirections();
                }
             else
               {
                  PathExpanderBuilder expanderBuilder =   PathExpanderBuilder.empty();

                  expanderBuilder = expanderBuilder

                  .add(MyRelationshipTypes.BELONGS_TO, Direction.BOTH)
                  .add(MyRelationshipTypes.CARRIES, Direction.BOTH)
                  .add(MyRelationshipTypes.IS_LOCATED_AT, Direction.BOTH);

                  expander = expanderBuilder.build();

                 }
              try (Transaction tx = graphDb.beginTx()) {


             PathFinder<Path> shortestPath = GraphAlgoFactory.shortestPath(
               expander, depth == null ? 100 : depth.intValue());
               Iterable<Path> pathss = shortestPath.findAllPaths(sourceNode, destNode);

               for(Path path1:pathss){
               paths.add(path1);

        System.out.println("result::::"+paths);
              }

            tx.success();
           }
          return paths;
         }
   }

Upvotes: 2

Views: 285

Answers (1)

Stefan Armbruster
Stefan Armbruster

Reputation: 39915

If the restriction applies to at least one node along the path (and not to every node) the snippet above will not work. The strategy to apply here would be as follows:

  1. use shortestPath.findAllPaths without filtering for the node property
  2. filter the shortest paths you've found in 1) if any of those contains a node with the given property. If yes: done, otherwise:
  3. use GraphAlgoFactory.pathsWithLength() and ask for paths of length+1 (where length is the length of the shortest paths from step 1)
  4. check if any of paths with length+1 fulfills the criteria (see 2). If not go back to 3 with length=length+1

An alternative way would be using GraphDatabaseService.bidirectionalTraversalDescription() and apply the property check within the collision evaluator. But I consider this approach way more complex than the strategy sketched above.

Upvotes: 1

Related Questions