| Downloads | Javadoc | Latest Release: 2.3.3.37.5
GraphAware Algorithms is a library of graph algorithms for Neo4j.
When using Neo4j in the standalone server mode,
you will need the GraphAware Neo4j Framework and GraphAware Neo4j Algorithms .jar files (both of which you can download here) dropped
into the plugins
directory of your Neo4j installation. After Neo4j restart, you will be able to use the REST APIs of the Algorithms.
Java developers that use Neo4j in embedded mode and those developing Neo4j server plugins, unmanaged extensions, GraphAware Runtime Modules, or Spring MVC Controllers can include use the Algorithms as a dependency for their Java project.
Releases are synced to Maven Central repository. When using Maven for dependency management, include the following dependency in your pom.xml.
<dependencies>
...
<dependency>
<groupId>com.graphaware.neo4j</groupId>
<artifactId>algorithms</artifactId>
<version>2.3.3.37.5</version>
</dependency>
...
</dependencies>
To use the latest development version, just clone this repository, run mvn clean install
and change the version in the
dependency above to 2.3.3.37.6-SNAPSHOT.
The version number has two parts. The first four numbers indicate compatibility with Neo4j GraphAware Framework. The last number is the version of the Algorithms library. For example, version 2.1.3.10.2 is version 2 of the library compatible with GraphAware Neo4j Framework 2.1.3.10.
It is often required for testing and implementation to work with a randomly generated graph. Getting one isn't as simple as it sounds - care has to be taken when generating relationships in order to obtain the desired network shape. A lot of research has gone into networks in the past decades; we have taken some of it and implemented a number of random graph generators. For a theoretical introduction, please take a look at the following blog posts:
In order to use the graph generators from Java, get the library following the instructions above and have a look at the Javadoc and tests. This will give you a really good idea of how the generators can be used. Provided implementations include:
- Erdos-Renyi Model
- Barabasi-Albert Model
- Watts-Strogatz Model
- Configuration Model
You have to choose two things: the shape of the network (one of the models above) and its contents (what labels will nodes get? what properties? what types of relationships will you generate?).
To choose the contents of the network, you can plug in your own implementations of NodeCreator
and RelationshipCreator
to create nodes and relationships
with types, labels, and properties of your choosing. You can use the provided SocialNetworkNodeCreator
and
SocialNetworkRelationshipCreator
to get started quickly.
For now, the provided REST API allows you to create social networks only with FRIEND_OF relationships and randomly generated English names and uniformly assigned genders for people nodes.
-
POST
tohttp://your-server:7474/graphaware/algorithm/generator/social/watts-strogatz/{numberOfNodes}/{meanDegree}/{beta}
will return a201 CREATED
status when your Watts-Strogatz network has been successfully created. Please refer toWattsStrogatzConfig
for explanation of the parameters you need to provide. -
POST
tohttp://your-server:7474/graphaware/algorithm/generator/social/erdos-renyi/{numberOfNodes}/{numberOfEdges}
will return a201 CREATED
status when your Erdos-Renyi network has been successfully created. Please refer toErdosRenyiConfig
for explanation of the parameters you need to provide. -
POST
tohttp://your-server:7474/graphaware/algorithm/generator/social/barabasi-albert/{numberOfNodes}/{edgesPerNewNode}
will return a201 CREATED
status when your Barabasi-Albert network has been successfully created. Please refer toBarabasiAlberConfig
for explanation of the parameters you need to provide.
This library allows to find a given number of shortest paths between two nodes. It is different from standard shortest path finding, because it allows to specify the desired number of results. Provided that there are enough paths between the two nodes in the graph, this path finder will first return all the shortest paths, then all the paths one hop longer, then two hops longer, etc., until enough paths have been returned.
Please note that nodes that are on a path with certain length will not be considered for paths with greater lengths.
For example, given the following graph:
(1)->(2)->(3)
(1)->(4)->(5)->(3)
(4)->(2)
the shortest path from (1) to (3) is (1)->(2)->(3) and has a length of 2. If more paths are needed, the next path returned will be (1)->(4)->(5)->(3) with a length of 3. Note that there is another path of length 3: (1)->(4)->(2)->(3), but it is not returned, since (2)->(3) is contained in a shorter path.
When deployed in server mode, issue a POST request to http://your-server-address:7474/graphaware/algorithm/path/increasinglyLongerShortestPath
with the following JSON minimal payload
{
"startNode": 0,
"endNode": 2
}
in order to find all paths between nodes with ID 0 and 2, sorted by increasing length.
You can also optionally specify the following:
- maximum path depth (
maxDepth
), 3 by default - maximum number of results (
maxResults
), unlimited by default - cost property (
costProperty
), which must be a number-valued relationship property that indicates the cost of the path, none by default - sort order (
sortOrder
):- LENGTH_ASC (By increasing length. Ordering of paths with the same lengths is unspecified. This is the default.)
- LENGTH_ASC_THEN_COST_ASC (By increasing length, then by increasing cost. The cost property must be specified.)
- LENGTH_ASC_THEN_COST_DESC (By increasing length, then by decreasing cost. The cost property must be specified.)
- whether to include node labels in the result (
includeNodeLabels
) set to true or false, default is true - which node properties to include in the result (
nodeProperties
) as an array of Strings, default is all - which relationship properties to include in the result (
relationshipProperties
) as an array of Strings, default is all - which relationships to traverse by supplying one of the following (default is all relationships in both directions):
- the direction in which to traverse relationships (
direction
), INCOMING, OUTGOING, or BOTH - relationship types and directions for each (
typesAndDirections
array withtype
and optionallydirection
)
- the direction in which to traverse relationships (
An example input with most of these parameters would look like this:
{
"startNode": 0,
"endNode": 2,
"costProperty": "cost",
"sortOrder": "LENGTH_ASC_THEN_COST_DESC",
"maxDepth": 2,
"maxResults": 10,
"includeNodeLabels": true,
"nodeProperties": [
"name"
],
"relationshipProperties": [
"cost"
],
"typesAndDirections": [
{
"type": "R1"
},
{
"type": "R2",
"direction": "INCOMING"
}
]
}
The output depends on the specification, but could look something like this:
[
{
"nodes": [
{
"id": 0,
"labels": ["L1", "L2"],
"name": "one"
},
{
"id": 1,
"labels": ["L2"],
"name": "two"
},
{
"id": 2,
"labels": ["L1", "L2"],
"name": "three"
}
],
"relationships": [
{
"id": 0,
"type": "R1",
"direction": "OUTGOING",
"cost": 5
},
{
"id": 1,
"type": "R2",
"direction": "OUTGOING",
"cost": 1
}
]
}
]
For the Java API, please refer to the Javadoc of NumberOfShortestPathsFinder
and PathFinderInput
.
Copyright (c) 2014 GraphAware
GraphAware is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.