Graph-algo

From Neo4j Wiki

This is a component that offers implementations of common graph algorithms on top of Neo4j. It is mostly focused around finding paths, like finding the shortest path between two nodes, but it also contains a few different centrality measures, like betweenness centrality for nodes. The initial implementation was part of a master thesis project, so for a more advanced theoretical background the report should be available.

1 Including it into your project
2 Overview
3 Path finding algorithms
4 Centrality algorithms and graph measures
5 Other algorithms
6 Examples

[edit] Including it into your project

You need to make sure that the jar file for this component is in your classpath (just like Neo4j). The easiest way to achieve this is to use Maven. When you have added the neo4j m2 repository (http://m2.neo4j.org/) as described in the Getting Started Guide, you can add this to your pom.xml:

<dependency> 
	<groupId>org.neo4j</groupId>
	<artifactId>neo4j-graph-algo</artifactId>
	<version>0.6-SNAPSHOT</version>
</dependency>

...and it should be available, ready to use!

[edit] Overview

There exists a number of algorithms and more are being added. To get a complete overview including the latest changes and documentation of algorithm complexities please see the API. Also, if we don't have the algorithm you would like, feel free to contact us.

[edit] Path finding algorithms

The Neo4j Graph Algorithms package contains the following algorithms for finding paths:

Find all paths between two nodes, limited by a specified path length.
Find all simple paths between two nodes. Similar to finding all paths, except the same node is not allowed multiple times in the same path.
Find the shortest path between two nodes.
Dijkstras algorithm for finding the paths with lowest cost between two nodes.
The A* search algorithm for finding the paths with lowest cost between two nodes in a graph where the cost from each node to the target can be estimated.

[edit] Centrality algorithms and graph measures

In this family of algorithms we have:

Further, some of these might be done in parallel.

All of these compute measures of centrality, computing a value for each node. The exceptions are diameter and radius, since they give one value/measure for an entire network.