Repository: neo4j-contrib/neo4j-apoc-procedures
Pull request #11 (2016-04-23 08:48:53)

first batch of graph algo functions
For now a wrapper for GraphAlgoFactory.dijkstra is available.

Note: I've refactored the existing parsing of relationship types and directions from PathExplorer into a reusable class together with tests.


Patch:
diff --git a/build.gradle b/build.gradle
index 921abf9b9..579065909 100644
--- a/build.gradle
+++ b/build.gradle
@@ -4,12 +4,12 @@ sourceCompatibility = 1.8
 
 repositories {
     mavenLocal()
-    maven { url "http://m2.neo4j.org/snapshots" }
+//    maven { url "http://m2.neo4j.org/snapshots" }
     mavenCentral()
 }
 project.ext {
-//    neo4j_version = "3.0.0-M04"
-    neo4j_version = "3.0.0-SNAPSHOT"
+    neo4j_version = "3.0.0-RC1"
+//    neo4j_version = "3.0.0-SNAPSHOT"
 }
 
 dependencies {
diff --git a/readme.adoc b/readme.adoc
index aece0656c..60f523c30 100644
--- a/readme.adoc
+++ b/readme.adoc
@@ -319,6 +319,24 @@ call apoc.path.expand(p,"ACTED_IN>|PRODUCED<|FOLLOWS<","+Movie|Person",1,2) yiel
 return p, pp 
 ----
 
+=== Graph Alorithms (work in progress)
+
+Provides a wrapper around GraphAlgoFactory.
+
+* `CALL apoc.algo.dijkstra(startNode, endNode, relAndDirections, costProperty)` - run dijkstra with a relationship property as cost function,
+`relAndDirections` is a path expander specification from above.
+* `CALL apoc.algo.dijkstraWithDefaultWeight(startNode, endNode, relAndDirections, costProperty, defaultCost)` - run dijkstra with a relationship property as cost function. If the relationship property does not exist, use the specified default value instead.
+
+Example: find the weighted shortest path based on relationship property `d` from `A` to `B` following just `:ROAD` relationships
+
+[source,cypher]
+----
+MATCH (from:Loc{name:'A'}), (to:Loc{name:'D'})
+CALL apoc.algo.dijkstra(from, to, 'ROAD', 'd') yield path as path, weight as weight
+RETURN path, weight
+MATCH (n:Person)
+----
+
 == Plans
 
 * move apoc.get to apoc.nodes and apoc.rels
@@ -335,7 +353,7 @@ return p, pp
 * virtual graph from collection of nodes and rels, handle node-uniqueness with pk
 * RDF / Ontology loader
 * Encryption / decryption of single properties or a subset or all properties (provide decryption key as param or config)
-* Graph Algorithms (Stefan, Max?)
+* (in progress) Graph Algorithms (Stefan, Max?)
 * custom expanders, e.g. with dynamic rel-type suffixes and prefixes
 * Path Finding / Expansion (Kees)
 * Use Cypher as scripting language `{cypher:"RETURN a*10+b",params:{a:3,b:5}}` for algorithms, parallelization and custom expansion
diff --git a/src/main/java/apoc/algo/Algo.java b/src/main/java/apoc/algo/Algo.java
new file mode 100644
index 000000000..294801a3f
--- /dev/null
+++ b/src/main/java/apoc/algo/Algo.java
@@ -0,0 +1,76 @@
+package apoc.algo;
+
+import apoc.Description;
+import apoc.path.RelationshipTypeAndDirections;
+import org.neo4j.graphalgo.GraphAlgoFactory;
+import org.neo4j.graphalgo.PathFinder;
+import org.neo4j.graphalgo.WeightedPath;
+import org.neo4j.graphdb.*;
+import org.neo4j.helpers.collection.Pair;
+import org.neo4j.procedure.Name;
+import org.neo4j.procedure.Procedure;
+
+import java.util.stream.Stream;
+import java.util.stream.StreamSupport;
+
+public class Algo {
+
+    @Procedure
+    @Description("apoc.algo.dijkstra(startNode, endNode, 'KNOWS|WORKS_WITH<|IS_MANAGER_OF>', 'distance') YIELD yield, weight - run dijkstra with relationship property name as cost function")
+    public Stream<WeightedPathResult> dijkstra(
+            @Name("startNode") Node startNode,
+            @Name("endNode") Node endNode,
+            @Name("relationshipTypesAndDirections") String relTypesAndDirs,
+            @Name("weightPropertyName") String weightPropertyName) {
+
+        PathFinder<WeightedPath> algo = GraphAlgoFactory.dijkstra(
+                buildPathExpander(relTypesAndDirs),
+                weightPropertyName
+        );
+        return streamWeightedPathResult(startNode, endNode, algo);
+    }
+
+    @Procedure
+    @Description("apoc.algo.dijkstraWithDefaultWeight(startNode, endNode, 'KNOWS|WORKS_WITH<|IS_MANAGER_OF>', 'distance', 10) YIELD yield, weight - run dijkstra with relationship property name as cost function and a default weight if the property does not exist")
+    public Stream<WeightedPathResult> dijkstraWithDefaultWeight(
+            @Name("startNode") Node startNode,
+            @Name("endNode") Node endNode,
+            @Name("relationshipTypesAndDirections") String relTypesAndDirs,
+            @Name("weightPropertyName") String weightPropertyName,
+            @Name("defaultWeight") double defaultWeight) {
+
+        PathFinder<WeightedPath> algo = GraphAlgoFactory.dijkstra(
+                buildPathExpander(relTypesAndDirs),
+                (relationship, direction) -> ((Number) (relationship.getProperty(weightPropertyName, defaultWeight))).doubleValue()
+        );
+        return streamWeightedPathResult(startNode, endNode, algo);
+    }
+
+    private PathExpander<Object> buildPathExpander(String relationshipsAndDirections) {
+        PathExpanderBuilder builder = PathExpanderBuilder.empty();
+        for (Pair<RelationshipType, Direction> pair : RelationshipTypeAndDirections.parse(relationshipsAndDirections)) {
+            if (pair.first()==null) {
+                builder = PathExpanderBuilder.allTypes(pair.other());
+            } else {
+                builder = builder.add(pair.first(), pair.other());
+            }
+        }
+        return builder.build();
+    }
+
+    private Stream<WeightedPathResult> streamWeightedPathResult(@Name("startNode") Node startNode, @Name("endNode") Node endNode, PathFinder<WeightedPath> algo) {
+        Iterable<WeightedPath> allPaths = algo.findAllPaths(startNode, endNode);
+        return StreamSupport.stream(allPaths.spliterator(), false)
+                .map(WeightedPathResult::new);
+    }
+
+    public static class WeightedPathResult { // TODO: derive from PathResult when access to derived properties is fixed for yield
+        public Path path;
+        public double weight;
+
+        public WeightedPathResult(WeightedPath weightedPath) {
+            this.path = weightedPath;
+            this.weight = weightedPath.weight();
+        }
+    }
+}
diff --git a/src/main/java/apoc/path/PathExplorer.java b/src/main/java/apoc/path/PathExplorer.java
index dc87c4059..4ead47983 100644
--- a/src/main/java/apoc/path/PathExplorer.java
+++ b/src/main/java/apoc/path/PathExplorer.java
@@ -1,27 +1,17 @@
 package apoc.path;
 
-import java.util.*;
-import java.util.stream.Stream;
-
+import apoc.Description;
 import apoc.result.PathResult;
-import org.neo4j.graphdb.Direction;
-import org.neo4j.graphdb.GraphDatabaseService;
-import org.neo4j.graphdb.Label;
-import org.neo4j.graphdb.Node;
-import org.neo4j.graphdb.Path;
-import org.neo4j.graphdb.PathExpanderBuilder;
-import org.neo4j.graphdb.RelationshipType;
-import org.neo4j.graphdb.traversal.Evaluation;
-import org.neo4j.graphdb.traversal.Evaluator;
-import org.neo4j.graphdb.traversal.Evaluators;
-import org.neo4j.graphdb.traversal.TraversalDescription;
-import org.neo4j.graphdb.traversal.Uniqueness;
+import org.neo4j.graphdb.*;
+import org.neo4j.graphdb.traversal.*;
+import org.neo4j.helpers.collection.Pair;
 import org.neo4j.logging.Log;
 import org.neo4j.procedure.Context;
 import org.neo4j.procedure.Name;
 import org.neo4j.procedure.Procedure;
 
-import apoc.Description;
+import java.util.*;
+import java.util.stream.Stream;
 
 
 public class PathExplorer {
@@ -73,12 +63,6 @@ public class PathExplorer {
 		throw new Exception("Unsupported data type for start parameter a Node or an Identifier (long) of a Node must be given!");
 	}
 
-	private Direction directionFor(String type) {
-		if (type.contains("<")) return Direction.INCOMING;
-		if (type.contains(">")) return Direction.OUTGOING;
-		return Direction.BOTH;
-	}
-
 	private Stream<PathResult> explorePathPrivate(Iterable<Node> startNodes
 			                   , String pathFilter
 			                   , String labelFilter
@@ -92,20 +76,18 @@ public class PathExplorer {
 		int to = new Long(maxLevel).intValue();
 		TraversalDescription td = db.traversalDescription().breadthFirst();
 		// based on the pathFilter definition now the possible relationships and directions must be shown
-		if (pathFilter !=null ) {
-			String[] defs = pathFilter.split("\\|");
-			if (!defs[0].isEmpty()) {
-				for (String def : defs) {
-					Direction direction = directionFor(def);
-					RelationshipType relType = new DynRelationshipType(def);
-					if (relType.name().isEmpty()) {
-						td = td.expand(PathExpanderBuilder.allTypes(direction).build());
-					} else {
-						td = td.relationships(relType, direction);
-					}
-				}
-			} // else td = td.expand(StandardExpander.DEFAULT); }
-		} // else { td = td.expand(StandardExpander.DEFAULT); }
+
+		Iterable<Pair<RelationshipType, Direction>> relDirIterable = RelationshipTypeAndDirections.parse(pathFilter);
+
+		for (Pair<RelationshipType, Direction> pair: relDirIterable) {
+			if (pair.first() == null) {
+				td = td.expand(PathExpanderBuilder.allTypes(pair.other()).build());
+			} else {
+				td = td.relationships(pair.first(), pair.other());
+			}
+
+		}
+
 		LabelEvaluator labelEvaluator = new LabelEvaluator(labelFilter);
 		td = td.evaluator(Evaluators.fromDepth(from))
 				.evaluator(Evaluators.toDepth(to))
@@ -114,23 +96,6 @@ public class PathExplorer {
 		// uniqueness should be set as last on the TraversalDescription
 		return td.traverse(startNodes).stream().map( PathResult::new );
 	}
-	
-	public class DynRelationshipType implements RelationshipType {
-		private String name;
-		public DynRelationshipType(String sname) {
-			if (sname.startsWith(":")) {
-				sname = sname.substring(1);
-			}
-			if (sname.endsWith(">") || sname.endsWith("<")) {
-				sname = sname.substring(0, sname.length() -1);
-			}
-			this.name = sname;
-		}
-		public String name() {
-			return this.name;
-		}
-		
-	}
 
 	public static class InfoContainer
 	{	
diff --git a/src/main/java/apoc/path/RelationshipTypeAndDirections.java b/src/main/java/apoc/path/RelationshipTypeAndDirections.java
new file mode 100644
index 000000000..e1c7e3d96
--- /dev/null
+++ b/src/main/java/apoc/path/RelationshipTypeAndDirections.java
@@ -0,0 +1,46 @@
+package apoc.path;
+
+import org.neo4j.graphdb.Direction;
+import org.neo4j.graphdb.RelationshipType;
+import org.neo4j.helpers.collection.Pair;
+
+import java.util.ArrayList;
+import java.util.Collection;
+
+import static org.neo4j.graphdb.Direction.*;
+
+/**
+ * helper class parsing relationship types and directions
+ */
+
+public abstract class RelationshipTypeAndDirections {
+
+	public static Iterable<Pair<RelationshipType, Direction>> parse(String pathFilter) {
+		Collection<Pair<RelationshipType, Direction>> relsAndDirs = new ArrayList<>();
+		if (pathFilter == null) {
+			relsAndDirs.add(Pair.of(null, BOTH));
+		} else {
+			String[] defs = pathFilter.split("\\|");
+			for (String def : defs) {
+				relsAndDirs.add(Pair.of(relationshipTypeFor(def), directionFor(def)));
+			}
+		}
+		return relsAndDirs;
+	}
+
+	private static Direction directionFor(String type) {
+		if (type.contains("<")) return INCOMING;
+		if (type.contains(">")) return OUTGOING;
+		return BOTH;
+	}
+
+	private static RelationshipType relationshipTypeFor(String name) {
+		if (name.startsWith(":")) {
+			name = name.substring(1);
+		}
+		if (name.endsWith(">") || name.endsWith("<")) {
+			name = name.substring(0, name.length() -1);
+		}
+		return name.isEmpty() ? null : RelationshipType.withName(name);
+	}
+}


Test patch:
diff --git a/src/test/java/apoc/algo/AlgoTest.java b/src/test/java/apoc/algo/AlgoTest.java
new file mode 100644
index 000000000..080195745
--- /dev/null
+++ b/src/test/java/apoc/algo/AlgoTest.java
@@ -0,0 +1,86 @@
+package apoc.algo;
+
+import apoc.util.TestUtil;
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+import org.neo4j.graphdb.GraphDatabaseService;
+import org.neo4j.test.TestGraphDatabaseFactory;
+
+import java.util.List;
+
+import static apoc.util.TestUtil.testCall;
+import static org.junit.Assert.assertEquals;
+
+public class AlgoTest {
+
+   	private GraphDatabaseService db;
+
+   	@Before
+   	public void setUp() throws Exception {
+   		db = new TestGraphDatabaseFactory().newImpermanentDatabase();
+   		TestUtil.registerProcedure(db, Algo.class);
+   	}
+
+   	@After
+   	public void tearDown() {
+   		db.shutdown();
+   	}
+
+    @Test
+    public void testDijekstra() {
+        db.execute("CREATE " +
+                "(a:Loc{name:'A'}), " +
+                "(b:Loc{name:'B'}), " +
+                "(c:Loc{name:'C'}), " +
+                "(d:Loc{name:'D'}), " +
+                "(a)-[:ROAD {d:100}]->(d), " +
+                "(a)-[:RAIL {d:5}]->(d), " +
+                "(a)-[:ROAD {d:10}]->(b), " +
+                "(b)-[:ROAD {d:20}]->(c), " +
+                "(c)-[:ROAD {d:30}]->(d), " +
+                "(a)-[:ROAD {d:20}]->(c) ");
+        testCall(db,
+            "MATCH (from:Loc{name:'A'}), (to:Loc{name:'D'}) " +
+            "CALL apoc.algo.dijkstra(from, to, 'ROAD>', 'd') yield path as path, weight as weight " +
+            "RETURN path, weight" ,
+            row ->  {
+                assertEquals(50.0, row.get("weight")) ;
+                assertEquals(5, ((List)(row.get("path"))).size()) ; // 3nodes, 2 rels
+            }
+        );
+        testCall(db,
+            "MATCH (from:Loc{name:'A'}), (to:Loc{name:'D'}) " +
+            "CALL apoc.algo.dijkstra(from, to, '', 'd') yield path as path, weight as weight " +
+            "RETURN path, weight" ,
+            row ->  {
+                assertEquals(5.0, row.get("weight")) ;
+                assertEquals(3, ((List)(row.get("path"))).size()) ; // 2nodes, 1 rels
+            }
+        );
+    }
+
+    @Test
+    public void testDijekstraWithDefaultWeight() {
+        db.execute("CREATE " +
+                "(a:Loc{name:'A'}), " +
+                "(b:Loc{name:'B'}), " +
+                "(c:Loc{name:'C'}), " +
+                "(d:Loc{name:'D'}), " +
+                "(a)-[:ROAD {d:100}]->(d), " +
+                "(a)-[:RAIL {d:5}]->(d), " +
+                "(a)-[:ROAD {d:10}]->(b), " +
+                "(b)-[:ROAD {d:20}]->(c), " +
+                "(c)-[:ROAD]->(d), " +
+                "(a)-[:ROAD {d:20}]->(c) ");
+        testCall(db,
+                "MATCH (from:Loc{name:'A'}), (to:Loc{name:'D'}) " +
+                        "CALL apoc.algo.dijkstraWithDefaultWeight(from, to, 'ROAD>', 'd', 10.5) yield path as path, weight as weight " +
+                        "RETURN path, weight",
+                row -> {
+                    assertEquals(30.5, row.get("weight"));
+                    assertEquals(5, ((List) (row.get("path"))).size()); // 3nodes, 2 rels
+                }
+        );
+    }
+}
diff --git a/src/test/java/apoc/path/RelationshipTypeAndDirectionsTest.java b/src/test/java/apoc/path/RelationshipTypeAndDirectionsTest.java
new file mode 100644
index 000000000..c32b79ea1
--- /dev/null
+++ b/src/test/java/apoc/path/RelationshipTypeAndDirectionsTest.java
@@ -0,0 +1,57 @@
+package apoc.path;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+import org.neo4j.graphdb.Direction;
+import org.neo4j.graphdb.RelationshipType;
+import org.neo4j.helpers.collection.Pair;
+
+import java.util.Arrays;
+
+import static org.junit.Assert.assertEquals;
+import static org.neo4j.graphdb.Direction.*;
+import static org.neo4j.graphdb.RelationshipType.withName;
+import static org.neo4j.helpers.collection.Iterables.iterable;
+
+@RunWith(Parameterized.class)
+public class RelationshipTypeAndDirectionsTest {
+
+    @Parameters(name = "{index}: {0} -> {1}")
+    public static Iterable<Object[]> data() {
+          return Arrays.asList(new Object[][] {
+                  {null, iterable(Pair.of(null, BOTH))},
+                  {"", iterable(Pair.of(null, BOTH))},
+                  {">", iterable(Pair.of(null, OUTGOING))},
+                  {"<", iterable(Pair.of(null, INCOMING))},
+                  {"SIMPLE", iterable(Pair.of(withName("SIMPLE"), BOTH))},
+                  {"SIMPLE>", iterable(Pair.of(withName("SIMPLE"), OUTGOING))},
+                  {"SIMPLE<", iterable(Pair.of(withName("SIMPLE"), INCOMING))},
+//                  {"<SIMPLE", iterable(Pair.of(withName("SIMPLE"), INCOMING))},
+//                  {">SIMPLE", iterable(Pair.of(withName("SIMPLE"), OUTGOING))},
+//                  {"<SIMPLE>", iterable(Pair.of(withName("SIMPLE"), BOTH))},
+                  {"TYPE1|TYPE2", iterable(
+                          Pair.of(withName("TYPE1"), BOTH),
+                          Pair.of(withName("TYPE2"), BOTH))
+                  },
+                  {"TYPE1>|TYPE2<", iterable(
+                          Pair.of(withName("TYPE1"), OUTGOING),
+                          Pair.of(withName("TYPE2"), INCOMING))
+                  },
+             });
+      }
+
+    @Parameter(value = 0)
+    public String input;
+
+    @Parameter(value = 1)
+    public Iterable<Pair<RelationshipType, Direction>> expected;
+
+    @Test
+    public void parse() throws Exception {
+        assertEquals(expected, RelationshipTypeAndDirections.parse(input));
+    }
+
+}
\ No newline at end of file