How can I calculate Shortest Path through Neo4j in my Spring Boot Example

[sngermiyanoglu]

Hi, 

I have a problem about calculating the shortest path through Neo4j in my Spring Boot example.

After adding some cities with its route, I want to calculate their shortest path in terms of their connection and their duration. However, these two methods which are defined in ShortestPathController cannot work.

1 ) getShortestPath throws this kind of error message

Neo.ClientNotification.Statement.UnboundedVariableLengthPatternWarning: The provided pattern is unbounded, consider adding an upper limit to the number of node hops.
MATCH p=shortestPath((a:City {name:$from})-[*]->(b:City {name:$to})) RETURN p

2 ) getShortestPathInTime throws this kind of error message shown below.

org.neo4j.driver.exceptions.ClientException: There is no procedure with the name `apoc.algo.dijkstra` registered for this database instance. Please ensure you've spelled the procedure name correctly and that the procedure is properly deployed.

Here is my Controller class shown below.

@RestController
@RequestMapping(path = "/api/v1/shortestpath")
public class ShortestPathController {

    private final ShortestPathService shortestPathService;

    public ShortestPathController(ShortestPathService shortestPathService) {
        this.shortestPathService = shortestPathService;
    }

    /* Sample Output (Not working)
    {
      "arrivalCity": "A",
      "departureCity": "B",
      "totalConnections": 1
    }
     */
    @GetMapping("/shortest-path")
    public Mono<PathShortestConnectionResponse> getShortestPath(@RequestBody PathRequest pathRequest) {

        return shortestPathService.getShortestPath(pathRequest.getFrom(), pathRequest.getDestination())
                .map(PathShortestConnectionResponse::new)
                .switchIfEmpty(Mono.error(new IllegalArgumentException("Error")));
    }

    /* Sample Output (Not working)
    {
      "arrivalCity": "A",
      "departureCity": "B",
      "totalHours": 5
    }
     */
    @GetMapping("/shortest-path-in-time")
    public Mono<PathShortestTimeResponse>  getShortestPathInTime(@RequestBody PathRequest pathRequest) {

        return shortestPathService.getShortestPathInTime(pathRequest.getFrom(), pathRequest.getDestination())
                .map(PathShortestTimeResponse::new)
                .switchIfEmpty(Mono.error(new IllegalArgumentException("Error")));
    }

    @ResponseStatus(
            value = HttpStatus.NOT_FOUND,
            reason = "Illegal arguments")
    @ExceptionHandler(IllegalArgumentException.class)
    public void illegalArgumentHandler() {

    }
}

Here is my Service class shown below.

@Service
@Transactional
@RequiredArgsConstructor
public class ShortestPathServiceImpl implements ShortestPathService {

    private final ShortestPathRepository shortestPathRepository;

    @Override
    public Mono<PathShortestConnectionResponse> getShortestPath(String from, String to) {

        final Flux<PathValue> rows = shortestPathRepository.shortestPath(from, to);
        return rows
                .map(it -> this.convert(it.asPath()))
                .take(1)
                .next()
                .switchIfEmpty(Mono.empty());

    }

    @Override
    public Mono<PathShortestTimeResponse> getShortestPathInTime(String from, String to) {

        final Flux<PathValue> rows = shortestPathRepository.shortestPathInTime(from, to);
        return rows
                .map(it -> this.convertTimePath(it.asPath()))
                .take(1)
                .next()
                .switchIfEmpty(Mono.empty());
    }


    private PathShortestConnectionResponse convert(org.neo4j.driver.types.Path connection) {

        String departureCity = connection.start().get("name").asString();
        String arriveCity = connection.end().get("name").asString();
        int length = connection.length();

        return new PathShortestConnectionResponse(departureCity, arriveCity, length);
    }

    private PathShortestTimeResponse convertTimePath(org.neo4j.driver.types.Path connection) {

        String departureCity = connection.start().get("name").asString();
        String arriveCity = connection.end().get("name").asString();
        Stream<Relationship> targetStream = StreamSupport.stream(connection.relationships().spliterator(), false);
        int totalInTime = targetStream.mapToInt(it -> it.get("duration").asInt()).sum();

        return new PathShortestTimeResponse(departureCity, arriveCity, totalInTime);
    }
}

Here is my Repository class shown below.

public interface ShortestPathRepository extends ReactiveNeo4jRepository<City, UUID> {

    @Query("MATCH p=shortestPath((a:City {name:$from})-[*]->(b:City {name:$to})) RETURN p")
    Flux<PathValue> shortestPath(@Param("from") String from, @Param("to") String to);

    @Query("MATCH (a:City {name: $from})\n"
            + "MATCH (b:City {name: $to})\n"
            + "CALL apoc.algo.dijkstra(a, b, 'ROUTES', 'duration')\n"
            + "YIELD path, weight\n"
            + "RETURN path\n"
            + "ORDER BY weight ASC LIMIT 1")
    Flux<PathValue> shortestPathInTime(@Param("from") String from, @Param("to") String to);
}

Here is my github repository : Link 

[bennu_neo]

Hi @sngermiyanoglu ,

Couple of considerations.

1. Version number 1 shows just a warning. If everything is properly modeled in the database, this should not be a problem.

2. Version number 2 shows an error probably because of the lack of a apoc jar in the database.

3. If you run the queries directly on the db, do you have any result?

4. This is probably the most important one. The model should be reviewed. The simplest version of your desired application consists of a relationship entity just with the duration property. Based on this one you can weight Dijksrtra. Instead you are creating an intermediate node with the label Route that adds no benefits to the model... yet.

[sngermiyanoglu]

Here are some screenshots: Link 

I updated my repository again. I tried to test all these two methods both in Postman and Neo4j Desktop but they couldn't work.

How can I add a relationship entity just with the duration property and How can I connect it with Route and City?

[sngermiyanoglu]

1 ) I get empty destinationCity as null value when I try to add a route

2 ) getShortestPath throws this kind of error message Neo.ClientNotification.Statement.UnboundedVariableLengthPatternWarning: The provided pattern is unbounded, consider adding an upper limit to the number of node hops. MATCH p=shortestPath((a:City {name:$from})-[*]->(b:City {name:$to})) RETURN p ^ Using shortest path with an unbounded pattern will likely result in long execution times. It is recommended to use an upper limit to the number of node hops in your pattern.

3 ) I cannot run all test methods in AppApplicationTests.java

4 ) I have no idea as I cannot run all test methods what if there are many cities and its route like this resource  (https://vladbatushkov.medium.com/one-month-graph-challenge-hero-city-cc4ffa51bb1b)

[gerrit_meier]

StackOverflow discussion and my answer (and repo link) for completion: https://stackoverflow.com/a/72583770/2650436

[sngermiyanoglu]

Thank you for your response. I updated my repository again. When I tried to add many cities with routes, there is a problem in calculation. Also, I have an issue (Could not autowire) in AppApplicationTests. How can I fix it?

[sngermiyanoglu]

I have some issues shown below

1 ) I get empty destinationCity as null value when I try to add a route.

2 ) getShortestPath throws this kind of error message

Neo.ClientNotification.Statement.UnboundedVariableLengthPatternWarning: The provided pattern is unbounded, consider adding an upper limit to the number of node hops.
    MATCH p=shortestPath((a:City {name:$from})-[*]->(b:City {name:$to})) RETURN p
                                              ^
Using shortest path with an unbounded pattern will likely result in long execution times. It is recommended to use an upper limit to the number of node hops in your pattern.

3 ) I cannot run all test methods in AppApplicationTests.java

4 ) I have no idea as I cannot run all test methods what if there are many cities and its route like this resource (Resource Link)