Graph-algo

From NeoWiki

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, and different centrality measures, like betweenness centrality for nodes. The 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 Shortest path 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>graph-algo</artifactId>
	<version>0.1-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] Shortest path algorithms

These algorithms have been implemented:

Findpath
Breadth First Search
Dijkstra(Single target)(Multiple targets)
Floyd Warshall

The only algorithms currently optimized to find the shortest path(s) between two given nodes are FindPath and Dijkstra. None of them can handle relationships with negative weights. Floyd Warshall can be used to solve the all-pairs shortest-paths problem i.e. find the shortest paths between all pairs of nodes in a network. Both Breadth First Search and Dijkstra can be used to solve the single source shortest path problem, i.e. find the shortest path(s) from one given node to all other nodes. BFS is limited to unweighted networks, and Dijkstra cannot handle relationships with negative weights.

[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.