When you describe a path, you probably imagine something like “X -Y-> Z” to describe a “Y” relationship between two objects, “X” and “Z”. Describing the path result that you want to see this way is simple and intuitive, but representing this result programmatically through a navigation API can be rather difficult unless you have a supported path syntax that can capture this intuitive expressiveness. Imagine querying using this type of syntax to find paths of a certain pattern: consider paths across multiple social network datasets where you would like to find the pattern “[Person]-[Friends(how==’Facebook’)]->[Person]”, which represents a “Friends” connection between two people on Facebook™. Consider a code dependency between an application and library expressed as “[Application]-[Dependency(type==’compile’)]->[Library(language==’C++’)]” which may represent a compile-level dependency on a certain native library.

This intuitive way of describing a path was the motivation for the new path matching syntax in InfiniteGraph 3.2!

Describing the Problem

Imagine using a social network dataset and trying to represent the path “Person - Likes -> Person” in code. In the absence of any supported path syntax through the navigation API, you are limited to using complex custom code blocks to validate what is really a very simple path.

Image 1: Simple “Likes” Relationship

Simple Path Example

For example, the following custom qualifier could be used to limit the results to the “Likes” relationship between two people.

Code Sample 1: Using a Custom Result Qualifier

final long personTypeId = myGraphDb.getTypeId(Person.class.getName());
final long likesTypeId = myGraphDb.getTypeId(Likes.class.getName());
Qualifier resultQualifier = new Qualifier(){
   public boolean qualify(Path currentPath)
      if(currentPath.size() != 2)
         return false;
          // verify begins with Person
          Hop startHop = currentPath.get(0);
          VertexHandle startVertex = startHop.getVertexHandle();
          if(startVertex.getTypeId() == personTypeId)
             // verify ends with Person
             Hop finalHop = currentPath.getFinalHop();
             VertexHandle targetVertex = finalHop.getVertexHandle();
             if(targetVertex.getTypeId() == personTypeId)
                // verify relationship is Likes
                EdgeHandle targetEdge = finalHop.getEdgeHandle();
                if(targetEdge.getTypeId == likesTypeId)
                   return true;
          return false;

Before InfiniteGraph 3.0, custom qualification was the only way to qualify path results. Custom qualification is extremely powerful because it allows you to execute whatever kind of logic is necessary to qualify a resulting path, but at the same time, it does not perform as well as it needed in some situations. In the 3.0 release of InfiniteGraph, we offered a number of Java constructs to perform a high performance navigation including Policies (which allow you to globally configure your navigation behavior) and the GraphVIew (to limit the types of vertices and edges that would be traversed). With these devices, you could achieve similar path qualification, as shown.

Code Sample 2: Using Navigation Constructs

// limits the path depth to 2
PolicyChain myPolicies = new PolicyChain(new MaximumPathDepthPolicy(2));

// filters out all types except "Person" and "Likes"
GraphView myView = myGraphDb.createGraphView();
myView.excludeClass(BaseVertex.class); // excludes all vertex types
myView.includeClass(Person.class);        // adds back "Person" type
myView.excludeClass(BaseEdge.class);   // excludes all edge types
myView.includeClass(Likes.class);         // adds back "Likes" type
Navigator myNavigator = myStartVertex.navigate(
         null /** No Custom Path Qualifier **/, 
         null /** No Custom Result Qualifier **/, 

This approach provides better navigational performance and is much simpler, but it can quickly become too complex for more realistic path qualifications and may not work for all use cases. Imagine the case where you want to qualify a path based on types for certain positions in the path like “[Student]-[Knows]->[Teacher]-[WorksAt]->[School(name==’AcmePrepSchool’)]”. Here you want the second vertex in the path to have a “Teacher” type rather than a “Student” or “Parent”.

Qualifying Results Using InfiniteGraph’s Path-Match Syntax

Now, with the release of InfiniteGraph 3.2, you can describe a path pattern using a sequence of Vertex and Edge types. Used within the context of navigation, you can execute a high performance navigation using the path pattern for qualifying path results or paths themselves. Here are some simple examples of navigators that qualify path results.

  1. We can filter the results from a dataset to only return paths that include employees that work at my company that volunteer at a school.
    Code Sample 3: Result Qualification Using Path-Match Syntax
    Company myCompany = ...; // use query or index lookup to find
    String matchPattern = "[Company]-[Works]->[Employees]-[Volunteers]->[School]";
    Navigator navigator = myCompany.navigate(myGraphView, matchPattern, myPolicies, myResultHandler);
    navigator.start(); // begins the navigation and passes the filtered results to the result handler
  2. Or imagine being on LinkedIn™,considering your career options, and beginning a search by finding all of the people over 40 who work in management at my company and are Facebook™ friends with people age 30 or older who work in management at Apple, Inc.™.
    Code Sample 4: Complex Result Qualification Using Path-Match Syntax
    Company myCompany = ...; // use query or index lookup to find
    String matchPattern = "[Company]-[Works(department=='Management')]->[Person(age > 40)]-[Friends(source=='Facebook')]->[Person(age >= 30)]-[Works(department=='Management')]->[Company(name=='Apple, Inc')]";
    Navigator navigator = myCompany.navigate(myGraphView, matchPattern, myPolicies, myResultHandler);
    navigator.start(); // begins the navigation and passes the filtered results to the result handler

As you can see, this syntax can be incredibly expressive and powerful for qualifying results in navigational queries.

Extensions: |, OR, AND, NOT and …

If you want to allow different options for a type of edge, you can express it using a vertical bar (|) similar to this [Person]-[Knows|Likes|WorksWith(relationship=="social")]->[Person]. Also, you can use these extensions to qualify combinations of paths (using AND/OR) or disqualify paths (using NOT). Finally, if you don’t care about the pattern that begins or ends your path, you can use the any-length (...) operator, which indicates that any sequence is matched. For example, the pattern [City]-[LocatedWithin]->[Restaurant(name==\"Applebee's\")]... can be used to describe a path that begins at an Applebee’s restaurant located within some city and can conclude with any path sequence. You might want to use this type of result qualification when you know a piece of a pattern and want to do more analysis or do some data collection about what may have happened around an event.

Pruning Paths

So far, we have focused exclusively on result qualification using the path-match syntax, but this syntax can also be used to filter paths during navigation. This will dramatically improve the performance of your navigation by excluding types and paths that are not relevant for your navigation. This means that these types and paths will not be traversed further after they are found (although they will still be returned as results). You can prune paths by calling excludePath on the GraphView instance.

Here is an example of qualifying paths using the path matching syntax. For a navigation that begins at a person and has a number of various relationships with other people including family, romantic, professional and restaurants, this qualification does not pursue paths with patterns that include a “Family”, “MetWith”, “Likes” relationship between two people OR “Travels” and favorite “Likes” between a person and a restaurant.

Code Sample 5: Path Qualification Using Path-Match Syntax

			GraphView view = testGraphDB.createGraphView().

This navigation may still return unique results of paths that include these patterns because results are returned first, then the path qualifier is consulted to determine whether to continue down that path. The purpose of path qualification is not to exclude results, but to prune paths. For optimized use, a GraphView (to exclude paths), Policies (to configure depth and/or max results) and a Path-Match predicate string (to qualify results) would be given in addition to the path qualifier. This would optimize the performance of the navigational query, as well as, return the desired result set. See the wiki for more information on the difference between result and path qualification or read this blog to learn about the importance of path qualification.


We are excited to offer this path-matching qualification feature so that applications built on top of IG 3.2 can use this new expressive query syntax to perform some advanced qualification through our navigation API. As always if you have any feedback or questions, feel free to check out our google group and for more information about Objectivity or InfiniteGraph, feel free to also visit our website or contact Objectivity support at Happy Trails!

Share on FacebookTweet about this on TwitterShare on Google+Share on LinkedIn