citiususc / hipster

Hipster4j is a lightweight and powerful heuristic search library for Java and Android. It contains common, fully customizable algorithms such as Dijkstra, A* (A-Star), DFS, BFS, Bellman-Ford and more.

A powerful and friendly heuristic search library implemented in Java.

What's Hipster4j?

The aim of Hipster4j is to provide an easy to use yet powerful and flexible type-safe Java library for heuristic search. Hipster relies on a flexible model with generic operators that allow you to reuse and change the behavior of the algorithms very easily. Algorithms are also implemented in an iterative way, avoiding recursion. This has many benefits: full control over the search, access to the internals at runtime or a better and clear scale-out for large search spaces using the heap memory.

You can use Hipster4j to solve from simple graph search problems to more advanced state-space search problems where the state space is complex and weights are not just double values but custom defined costs.

Features

The current version of the library comes with some very well-known and wide used search algorithms. We're working to add more algorithms soon:

• Search algorithms:
  • Uninformed search:
    • DFS: Depth-First-Search.
    • BFS: Breadth-First-Search.
    • Dijkstra's algorithm.
    • Bellman-Ford.
  • Informed search:
    • A star (A*).
    • IDA star (IDA*), Iterative Deepening A*.
    • AD star (AD*): Anytime Dynamic A*.
  • Local search:
    • Hill-Climbing.
    • Enforced-Hill-Climbing.
  • Multiobjective search
    • Multiobjective LS algorithm. Original paper: Martins, E. D. Q. V., & Santos, J. L. E. (1999). "The labeling algorithm for the multiobjective shortest path problem". Departamento de Matematica, Universidade de Coimbra, Portugal, Tech. Rep. TR-99/005 (see an example)
• 3rd party adapters:
  • Java Universal/Graph (JUNG) adapter.

If you don't find the algorithm or the feature you are looking for, please consider contributing to Hipster!. You can open a new issue or better fork this repository and create a pull request with your contribution.

Getting started

The easiest way to use Hipster is adding it as a dependency with your favourite dependency manager. Maven users can include the library using the following snippet:

Snapshots

You can use the latest (unstable) version of Hipster under development. Just add the following dependency into your pom.xml:

<!-- Use sonatype oss public for snapshots -->
<repositories>
  <repository>
    <id>sonatype-oss-public</id>
    <url>https://oss.sonatype.org/content/groups/public/</url>
    <snapshots>
      <enabled>true</enabled>
    </snapshots>
  </repository>
</repositories>

<dependencies>
  <!-- 
    Add this dependency under your pom.xml <dependencies> section to add
    all the dependencies of Hipster to your project. Add hipster-core
    instead of hipster-all for basic functionality.
  -->
  <dependency>
    <groupId>es.usc.citius.hipster</groupId>
    <artifactId>hipster-all</artifactId>
    <version>1.0.2-SNAPSHOT</version>
  </dependency>
</dependencies>

Releases

Current stable release is v1.0.1. See the milestones to check the current development status.

<dependencies>
  <!--
    Add this dependency under your pom.xml <dependencies> section to add
    all the dependencies of Hipster to your project. Add hipster-core
    instead of hipster-all for core functionality.
  -->
  <dependency>
    <groupId>es.usc.citius.hipster</groupId>
    <artifactId>hipster-all</artifactId>
    <version>1.0.1</version>
  </dependency>
</dependencies>

Quick Example

Let's solve the graph used in this Wikipedia article about Shortest paths.

Although Hipster is graph agnostic, we include some useful classes to create a graph or a directed graph and the search problem. We create a graph using the GraphBuilder class and then we use the GraphSearchProblem to create the required components to solve it using Dijkstra's algorithm:

// Create a simple weighted directed graph with Hipster where
// vertices are Strings and edge values are just doubles
HipsterDirectedGraph<String,Double> graph = 
    GraphBuilder.<String,Double>create()
     .connect("A").to("B").withEdge(4d)
     .connect("A").to("C").withEdge(2d)
     .connect("B").to("C").withEdge(5d)
     .connect("B").to("D").withEdge(10d)
     .connect("C").to("E").withEdge(3d)
     .connect("D").to("F").withEdge(11d)
     .connect("E").to("D").withEdge(4d)
     .createDirectedGraph();

// Create the search problem. For graph problems, just use
// the GraphSearchProblem util class to generate the problem with ease.
SearchProblem p = GraphSearchProblem
                           .startingFrom("A")
                           .in(graph)
                           .takeCostsFromEdges()
                           .build();
                           
// Search the shortest path from "A" to "F"
System.out.println(Hipster.createDijkstra(p).search("F"));

Output result: `Total solutions: 1 Total time: 6 ms Total number of iterations: 6

• Solution 1:

• States: [A, C, E, D, F]
• Actions: [2.0, 3.0, 4.0, 11.0]
• Search information: WeightedNode{state=F, cost=20.0, estimation=0.0, score=20.0}`

But that's not all. Hipster comes with different problem examples that illustrate how Hipster can be used to solve a wide variety of problems (not only graph search).

What's next?

If you want to learn how to solve a problem by searching with Hipster, check the wiki and the JavaDoc documentation. We also suggest you to check this presentation for a quick introduction.

License & Citation

This software is licensed under the Apache 2 license, quoted below.

Copyright 2013 Centro de Investigación en Tecnoloxías da Información (CITIUS),
University of Santiago de Compostela (USC).

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

   http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.

Citation

This library was presented in the "9th Iberian Conference on Information Systems and Technologies (CISTI), 2014". If you use this library in your research projects, we encourage you to please cite our work:

Rodriguez-Mier, P., Gonzalez-Sieira, A., Mucientes, M., Lama, M. & Bugarin, A. (2014). Hipster: An Open Source Java Library for Heuristic Search. 9th Iberian Conference on Information Systems and Technologies (CISTI).

@inproceedings{RodriguezMier2014,
  author = {Rodriguez-Mier, Pablo and Gonzalez-Sieira, Adrian and Mucientes, Manuel and and Lama, Manuel and Bugarin, Alberto},
  booktitle = {9th Iberian Conference on Information Systems and Technologies (CISTI 2014)},
  month = jun,
  volume = 1,
  title = {{Hipster: An Open Source Java Library for Heuristic Search}},
  pages = {481--486},
  isbn = "978-989-98434-2-4"
  address = "Barcelona",
  year = {2014}
}

hipster's Issues

Complete javadoc documentation for hipster.algorithm (core)

Complete javadoc documentation for hipster.collection

Creation of gh-pages for hipster static web content

Implement SMA*

http://en.wikipedia.org/wiki/SMA*

Implementation of the Focussed D* algorithm

Link: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.6615

Implementation of the breadth-first-search algorithm

Implementation of the bidirectional heuristic path algorithm (BHPA)

Complete javadoc documentation for hipster.algorithm.node.impl (core)

Customize doclava css for javadoc

Complete javadoc documentation for hipster.algorithm.function.impl

Add test for HashQueue

Implement AO* (AND/OR search)

Complete javadoc documentation for hipster.function (core)

Floyd–Warshall algorithm for all-pair shortest paths

Complete javadoc documentation for hipster.algorithm.impl (core)

Implementation of the D* algorithm

Link: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41.8257&rep=rep1&type=pdf

Implement Tabu search

Create a package for local search algorithms and implement the Tabu search.

Complete javadoc documentation for hipster.util.parallel (core)

Move examples to a hipster-examples package

IterativeSetCover does not fulfill the iterator contract

hasNext method is used to compute the next element. This can cause lots of problems. For instance, if there are 3 solutions, these lines will fail:

iterator.next(); // try to obtain first solution
iterator.next(); // try second solution
iterator.next(); // try with third one

Maze search examples with realtime output printing

Implementation of the ARA* algorithm

Link: http://books.nips.cc/papers/files/nips16/NIPS2003_CN03.pdf

Fix A* cost comparator

Nodes are compared by g instead of f cost.

Implementation of the D* Lite algorithm

Link: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1435479&tag=1

Move common algorithm code to abstract classes

Algorithms like Dijkstra, A* etc share lots of lines in common. Create abstract classes to extend basic behaviour and reuse same data structures and components.

8-Puzzle example with different heuristics

Implement manhattan distance heuristic for 8-puzzle using A*

SetCoverIterator fails when there is only one element

Add unit test to check this case

Input:

Set<Set<String>> sets = new HashSet<String>();
sets.add(Collections.singleton("A"));

Expected output:

List<Set<String>> result = compute();
assertEquals(1, result.size());
assertEquals("A", result.get(0).iterator().next());

Complete javadoc documentation for hipster.algorithm.multiobjective (core)

Complete javadoc documentation for hipster.util.maze (core)

Rename Algorithms class to Hipster

Implement AD* replanning test

Implement IDA* algorithm

http://www.cis.temple.edu/~giorgio/cis587/readings/more-search.html#2

Complete javadoc documentation for hipster.algorithm.node (core)

Implement the iterative deepening depth-first search (IDDFS)

Create README.md with markdown

Cannot access the heuristic from HeuristicNode

Add getHeuristic method to HeuristicNode interface.

Insert pluginManagement in parent pom

Plugins such as javadoc / sources / ... should be defined in the parent pom using pluginDependency tag to let each sub-module decide whether to use it or not.

Complete javadoc documentation for hipster.algorithm.node.adstar (core)

Prepare the release of the 0.1.0 version

Bump POM versions to 0.1.0. Integrate the changes in a new branch release-0.1.0. Merge back to master and tag.

Complete javadoc documentation for hipster.algorithm.combinatorial (core)

Change factory.node to factory.makeNode

I think makeNode is more clear

Generate maven site with markdown with reflow maven skin

Generate the full site for deployment using a bootstrap maven skin:
http://andriusvelykis.github.io/reflow-maven-skin/

To generate maven site with markdown: http://stackoverflow.com/questions/14829190/how-to-use-markdown-for-maven-project-site

Create README.md with markdown

Document the project using markdown. The documentation must include project goals, example usage, how to contribute, organization info, etc.

Pretty 8-puzzle string representation

Override toString method to print 8-puzzle states in a pretty way, transformin the plain array {1,0,2,3,4,5,6,7,8} into something like:
| 1 0 2 |
| 3 4 5 |
| 6 7 8 |

Complete javadoc documentation for hipster.algorithm.problem (core)

Publish 1.0.0-rc1 artifacts to the central repository

Reorganize maven modules

New maven modules organization:

• hipster-core: same as the current maven module. In the future may split into api, collections and algorithms.
• hipster-examples: examples moved from core example packages.
• hipster-jung: distribution pom for hipster with jung adapters.
• hipster-jgrapht: distribution pom for hipster with jgrapht adapters.

Clean algorithm factory duplications

Some algorithm factories are identical for similar algorithms (for example, A factory and IDA factory). NOTE: This implies the reuse of factories and there are incompatibilities between generic nodes.

Method search(SearchListener) from Algorithms does not stop

Complete javadoc documentation for hipster.algorithm.factory (core)