JWalker

An extremely generic Java library for applying A* and other built-in search algorithms to user-defined graphs.

Overview

• Generic: Suitable for literally any problem that can be solved with a search algorithm
• Customizable: Define custom graphs and heuristics
• Efficient: The built-in algorithms use an efficient Fibonacci heap, borrowed from jheaps
• Lightweight: No external dependencies

The jwalker-examples repository contains example projects to demonstrate how easy it is to use JWalker to solve any search problem.

🤌 How to use

Define your own custom graph by creating a class that implements the Graph interface, along with a separate class for the nodes in your graph.

Once you have a graph, you are ready to use the Dijkstra or Breadth-First Search built-in algorithms to find an optimal path from a starting node to a target node.

If you want to use an informed search algorithm such as A* or Best-First Search, you need to provide a heuristic for your nodes by implementing the Heuristic functional interface.

⚡Quick example

The following code snippet uses the built-in A* algorithm to find an optimal solution for an instance of the N-Puzzle problem.

The example graph, node and heuristic classes are borrowed from the jwalker-examples repository.

import eth.epieffe.jwalker.Edge;
import eth.epieffe.jwalker.Graph;
import eth.epieffe.jwalker.Heuristic;
import eth.epieffe.jwalker.Visit;
import eth.epieffe.jwalker.Visits;

Graph<NPuzzle> graph = NPuzzleGraph.INSTANCE;
Heuristic<NPuzzle> heuristic = NPuzzleHeuristics::manhattanSum;
Visit<NPuzzle> visit = Visits.aStar(graph, heuristic);
NPuzzle node = NPuzzle.newInstance(1, 3, 8, 4, 6, 7, 5, 2, 0);
List<Edge<NPuzzle>> path = visit.run(node);

See the implementation of the example classes at NPuzzle, NPuzzleGraph and NPuzzleHeuristics.

💾 Installation

If you use Maven, add the following dependency in your pom.xml file:

<dependency>
    <groupId>io.github.epieffe</groupId>
    <artifactId>jwalker</artifactId>
    <version>1.0.1</version>
</dependency>

If you use Gradle, add the following dependency in your build.gradle file:

implementation 'io.github.epieffe:jwalker:1.0.1'

Built-in algorithms

Here we describe the built-in search algorithms. Users might also add new algorithms by implementing the corresponding Java interface.

🧠 Visits

A Visit traverses a graph to find a path from a provided node to a target node. Some visits are guaranteed to find a path with the lowest cost possible, while other visits sacrifice path optimality in exchange for efficiency.

built-in visits:

• A* (Wikipedia)
• Best First (Wikipedia)
• BFS (Wikipedia)
• Dijkstra (Wikipedia)

🔎 Local searches

A LocalSearch starts from one or more randomly generated nodes and navigates the graph until a node deemed optimal is found or a time bound is elapsed. It is used to solve computationally hard optimization problems. Unlike visits, a local search does not return a path, but only one node is returned.

The returned node is not guaranteed to be optimal, subsequent runs might find a better node.

built-in local searches:

• Steepest Descent (Wikipedia)