Replace Tutorial

Learn how to group and remove relationships in Thinkmap queries

Editors Note: Looking back in hindsight, times have changed, and grouping by gender is an unfortunate example for a tutorial. Please keep in mind this was written in 2012, and we had to work with the movie data that we licensed for these tutorials – which classified people as "actors" and "actresses" and did not provide any gender information for directors. This was built as an example to illustrate the capabilities of the technology and is in no way any kind of comment on gender roles or politics.

Introduction

In this tutorial, you will learn how to modify relationships and entities directly in a Thinkmap query via the $replace operator.

Thinkmap's $replace operator is incredibly powerful and ideal for any situation where a developer wants to modify the entities returned from a query before they officially become part of the result set. It effectively allows one to change their query results and/or graph dynamically.

Some example use cases are as follows: creating intermediary groups for situations where there are too many edges connected to a node, consolidating long graph traversals into a simple node -> edge -> node relationship, and performing map/reduce type operations across sections of a graph.

Getting Started

In this tutorial, we look at creating different types of groups and relationships with the $replace operator.

When centering on a movie, all actors, directors, and actresses are grouped by gender nodes that are attached directly to the movie in the center. In turn, the actors, directors, and actresses are connected to the appropriate gender group node.

Second, centering on a genre with more than 15 movies will show a series of intermediary groups that break up movies by their year. These groups will become part of the actual graph and can be centered and searched on like any type of node relationship. However, if there are less than 15 movies attached to the genre, then no grouping is performed.

Lastly, we create a movie_movie relationship for any two movies that share a common actor/actress/director. This new relationship consolidates the extended relationship of movie -> edge -> person -> edge -> movie into the more readable movie -> edge -> movie relationship.

We are now going to discuss the different parts of this example but you can at any time view the source of this page to see all the code that makes up this example.

Understanding Queries and Traversal Paths

Before we can cover how to use the $replace operator, it is best to discuss queries, traversal paths, and result sets.

One of the underlying strengths of Thinkmap is the query language which allows a simple, meaningful way to express what types of nodes and edges can be selected from a graph. User's can create an endless combination of choices, sequences, repeats and functions.

Every Thinkmap graph query, upon being executed, has two very important callback methods: onresult and oncomplete. It is these methods where most developers decide what to do with the data being returned by the query. The oncomplete function is called once the query has finished and returns a result set object representing the all the nodes and edges returned by the query. The onresult function is much more interesting and is called repeatedly with a single traversal path returned by the query.

A traversal path is an object which stores the state of a query through a graph. Every traversal path is associated with an entity, a depth, and the previous traversal path that came before it. When returned from a query, the traversal path passed to the onresult function will be the end of the path and calling prev continuously will return the center which has no previous path.

For instance, consider the following query:

      		graph.query(['movie','edge','person'])
      			 .execute(entity)
      			 .onresult(function(path) {
      				console.log(path.entity,path.depth);
      				console.log(path.prev.entity, path.prev.depth);	
      				console.log(path.prev.prev.entity, path.prev.prev.depth);	
      			 )}		
      	

Now in the case above, every time onresult is called, the output will always be in this order:

     		PERSON ENTITY, DEPTH 2
     		EDGE, DEPTH 1
     		MOVIE ENTITY, DEPTH 0
     	

Notice that even though the person is the last condition in the query, it is printed first. Moreover, to get the previous entity, we call prev on the path and then get the entity from it. For the movie, we have to call prev twice to go two levels back, thus bringing us to the root, which by default, has no previous path.

Now imagine if we had to find a specific entity in a path with repeating sequences, and etc.

   		 graph.query(['genre','edge','movie','edge','person',['edge','movie',[0,1]]])
   			  .execute(entity)
      	

For something like the above we could loop through the traversal path checking each entity and the depth to get to a particular point like so:

   		 graph.query(['genre','edge','movie','edge','person',['edge','movie',[0,1]]])
   			  .execute(entity)
   			  .onresult(function(path) {
   			 	var current = path; 
   			 	while (current) {
   			 		console.log(current.entity,current.depth);	
   			 		// keep going till we get to the root	
   			 		current = current.prev;
   			 	}
   			  })
      	

However, there is another option for looping through traversal paths with significantly less code: labels

Labels

Rather than manually trying to locate a specific entity in a traversal via a loop or calling prev continuously, we can use labels, a nice feature especially for complicated queries.

Labeling traversals is straightforward and allows for incredibly powerful graph operations. There are two ways to label a traversal path, either inline or via the $label operator

The labeling of traversals is done in the graph query itself for each condition

     		graph.query(['movie:m','edge:e','person:p']).execute();
     	

The other way to define operators is via the $label operator

    		graph.query([{$t:'movie',  $label: 'm'},
    					 {$t:'edge',   $label: 'e'},
    					 {$t:'person', $label: 'p'}])
    			  .execute(entity);	
    	

However, if only checking for type, the inline style is preferred.

So now that we defined these labels, how do we use them? We use them directly on the traversal when results are returned.

     		graph.query(['movie:m','edge:e','person:p'])
     			 .onresult(function(path) {
     				var movie = path.labeled('m').entity;
     				var edge = path.labeled('e').entity; 
     				var person = path.labeled('p').entity; 
     				//do something with the movie and person entity	
     			 })	
     	

As we can see, making use of labels allows us to pick out particular traversals and entities along the total traversal path. With this in mind, let's see how they can be used in the replacement operator.

The $Replace operator

The $replace operator in a Thinkmap query allows us to manipulate the traversal paths before they become part of the results, thus providing opportunities to dynamically change and modify entire relationships.

The $replace operator takes an array that has the following syntax

 $replace: [condition, groupingFunction, replacingFunction]

When used in a query it should look like this

graph.query(['movie',{$replace:[['edge','person'], groupFn, replaceFn]}]).execute()

The query used in the $replace follows the initial movie query and behaves just like all the Thinkmap queries you have seen to this point. The only difference is that each time a traversal path is accepted, it is passed to the grouping function.

The grouping function takes a traversal path and must return a key for that particular path. Paths that return the same key are mapped to the same group. These keys can be any type of object that can be serialized into a string.

Once the query part of the $replace operator has been exhausted and the grouping function has been called for each path, the replace function is called for every group. The replace function is passed all of the paths for the particular group along with the unique key assigned to that group by the grouping function.

More importantly the this object for the function has a couple of important properties and methods. First, it contains totalGroups and totalResults which store the total number of unique groups and the total number of paths among all the groups. These can be helpful in determining how to group or abandon it all together.

There is also a result method on the this object that is used for appending new results to the graph. This is the most import method that can be called in the replace function and is responsible for how the query results are modified. We will discuss this in more detail later once we see the $replace operator in action.

Grouping Genders - the typical model for using $replace

With all of the background out of the way, we can start to see how the $replace operator is used in this example. Let's start with seeing how we group the actors, directors, and actresses into gender groups.

First, it all starts with the query.

      	graph.query({$choice:[	
      		...	
			// group the actors, directors, and actress into a gender group
			['movie:m', {$replace:[ [ 'edge:e','person:p'],
			                         groupByGender, replaceByGender ]}],
     		...
      		]})
      		.execute(entity);	
      	

Above, the replace function uses a query for paths that end in 'edge' -> 'person'. We are also using inline labels that will be assigned to the traversal paths.

Now let's look at the groupByGender grouping function which is called every time a result path satisfies the query.

			// Group by the gender group. The "this" for this function is the
			// entity of the last path. The "data" is the data object(the properties)
			// for the last entity in the path. The "path" is the very end of
			// the path that satisifed the replaces condition.
		    function groupByGender(data, path) {
		    	// get the person
		    	var person = path.labeled('p').entity;
		    	// if the person is a director or actor, put them in the male group
		    	if(person.isType('actor') || person.isType('director')){
		    		return 'male';
		    	} else if(person.isType('actress')) {
		    		// else put them in the female group
		    		return 'female';
		    	} 
		    }
		

In the function above, the path is the last path in the result, which will be the person in our case (So we technically don't need to use the person label here as the path is already the one we want). The data is the data object for the entity of the last path (in this case the person) and the this is the entity of the last path.

Now that there are two possible groups, let's see how the replace function handles them.

		    // Replacement function that creates gender groups for males and females.
		    // The groups here are not added to the graph but only added as a result.
		    // This means that we can't center or search for these groups, unlike the
		    // genre movie groups.
		    function replaceByGender(paths, key) {
		    	// get the traversal path labeled m (will be the movie in the center)
		    	var traversalPath = paths[0].labeled("m");
		    	// get the movie entity in the traversal
		    	var movie = traversalPath.entity;
		    	// create the data for the gender group
				var data = {
					movie: movie.data.title,
					gender: key 
				};
				// create the gender group and edge between the movie and the group
				var gender = graph.createNode(data, "gendergroup");
		    	var edge = graph.createEdge(movie, gender);
		    	// build up the path that we will be appending to, in this case the
		    	// gender group will be the end and we will append the actors and 
		    	// actresses to it via an edge
		    	var nextPath = traversalPath.append(edge);
		    	// loop through each path appending every person and an edge
		    	// to the next path
		    	for (var i = 0; i < paths.length; i++) {
		    		// get the person which is labeled 'p'
		    		var person = paths[i].labeled('p').entity;
		    		// create an edge between the gender group and person
		    		var nextEdge = graph.createEdge(gender,person);
		    		// append the new edge and actor the the nextPath and append
		    		// that as a result
		    		this.result(nextPath.append(nextEdge).append(person));
		    	}
		    }
		

For most Thinkmap applications, the grouping outlined above is sufficient. It adjusts the results returned by the query by creating a series of intermediate nodes and edges. These results are appended to the first traversal state BUT ARE NOT ADDED TO THE GRAPH. This means we need to ensure that we can't center on them directly, as from the main graph's point of view, they don't exist and queries on them will return no results.

In fact, we ensure this by checking in our mouse listener for our display that gender groups can't be centered on.

     	display.addEventListener('click',function(evt) {
        	var entity = evt.entity;
        	// only center on nodes that are not gender groups as they 
        	// aren't stored in the graph
        	if(entity.isType('node') && !entity.isType('gendergroup')) {
        		makeCenter(entity);
        	}
        });
      	

Using this.Result() inside the Replace Function

We earlier touched on traversal paths and how they encapsulate the state of a particular visit through a graph. Once a traversal completes, meaning it satisifies a particular part of a query, it is passed to the onresult method and is stored as a result. However, it is important to realize that traversal paths that are passed to the replace function have not been added as a result yet. It is not until this.result() is called and passed a traversal path that a traversal path becomes a part of the result set.

Now because the traversal path is not part of the result set until this.result is called, we can remove, create, and build additional traversal paths before calling this.result. This is really where the strength of the $replace operator becomes apparent.

Appending To Traversal Paths

So how do we create and append to traversal paths? It is actually pretty simple. Every traversal path has a method called append which takes an entity and returns the new traversal path. This new traversal path that is returned will have a prev equal to the one append was called on and a depth that is +1 greater than its prev.

Let's consider our gender example again to help explain. For each gender we build up a new path that goes from the movie to the gender group

   		// get the traversal path labeled m (which will be a movie in the center)
    	var traversalPath = paths[0].labeled('m');
    	var movie = traversalPath.entity;
    	...
    	...
   		// create the gender group and edge between the movie and the group
		var gender = graph.createNode(data, 'gendergroup');
    	var edge = graph.createEdge(movie, gender);
    	// build up the path that we will be appending to, in this case the gender
    	// group will be the end and we will append the actors and actresses
    	// to it via an edge
    	var nextPath = traversalPath.append(edge).append(gender); 
   		

In this case, the movie is already at depth 0 because it is the root of the original query. Therefore the next path's entity is going to have an entity that is the gender group and its depth will be 2. We than keep this next path around to serve as the root for visiting all the actors and actresses which will individually build off of this path. That code is as follows:

   		for (var i = 0; i < paths.length; i++) {
    		// get the person which is labeled 'p'
    		var person = paths[i].labeled('p').entity;
    		// create an edge between the gender group and person
    		var nextEdge = graph.createEdge(gender,person);
    		// append the new edge and actor the the nextPath and append
    		// that as a result
    		this.result(nextPath.append(nextEdge).append(person));
    	}
    	

Notice that we are never changing the nextPath variable but rather appending all the person relationships to it. Each time we do this append, the person node will have a depth of 4. Interestingly, in the original traversal path, the person's path had a depth of 2, but we changed it by inserting a node in front of it, thus giving it a completely new state. Finally, this result is called with the traversal path of the person, thus making the entire path a part of the result set.

Grouping Genres By Year - a more complicated option

Grouping genres by year takes a different approach than the gender groups. In this case, we are actually electing to add the genre year groups to the graph directly, allowing them to be queried, searched, and exist as any other oridinary node. Developers requiring this type of interaction with groups should follow this pattern.

To add a little more to this example, genres will only be grouped if there are more than 2 groups and 15 movies across all groups. If both conditions are not met, then the original paths will just be passed as the results and no modification will take place.

The query and grouping functions follow a very similar pattern as the gender groups.

      		graph.query({$choice:[	
      				...
		      		// group genres into movie groups by year when centering on genre
					[ 'genre:g', {$replace:[ [ 'edge','movie:m'], 
									groupByMovieYear, replaceByMovieYear ]}],	
						...
					]})
					.execute(entity)
      	

The grouping function uses labels to retrieve the movie in the traversal path and return the year.

		    // group all movies by year
			function groupByMovieYear(data, path) {
				// return the year of the movie
				return path.labeled('m').entity.data.year;
			}
		

Now the replace function actually examines the paths and checks to see if any groups exist for that particular genre and year. If it does, then almost no work needs to be done. If it doesn't exist, then the replace function creates the necessary group and edges, making sure to add them to the graph so they can be retrieved later.

		// Replacement function for genres. All of the groups that are created here
		// are actually added to the graph which allows centering and searching.
		function replaceByMovieYear(paths, keys) {
			// get the traversal labeled 'g' (will be a genre)
			var traversalPath = paths[0].labeled('g');
			// get the from entity - will be a genre
			var from = traversalPath.entity;
		
			// if there are less than 3 groups or 15 results, then just
			// mark all the traversal paths as results and return without 
			// creating a group node
			if ( this.totalGroups < 3 || this.totalResults < 15 ) {
				paths.forEach(this.result);
				return;
			}
			// At this point we look to see if there is already a group year 
			// with this particular year attached to the genre. 
			// Because we are adding entities
			// to the actual graph in this example, we don't want to duplicate 
			// nodes and edges so it is important that we check that we 
			// haven't already done this particular grouping.
			var groupEdge = graph.edges(from)
								 .filter(function(edge){
									var other = edge.otherNode(from);
									return other.isType('genreyeargroup') &&
										   other.data.year == keys[0];
								}).first();
			// We already did the grouping for this particular genre group so 
			// just append the full traversal path, call result, and return.
			if (groupEdge) {
				this.result(traversalPath.append(groupEdge)
										 .append(groupEdge.otherNode(from)));
				return;
			}
			// the group doesn't exist so create the data for our group node
			var data = { 
				genrename: from.data.genrename, 
				year: keys[0],
				count: paths.length
			};
			// create the group node
			var group = graph.createNode(data,"genreyeargroup");
			// create an edge from the genre to the genre year group
			var fromEdge = graph.createEdge(from, group);
		
			// add the edge to graph, ensuring that the group will also be added
			// because we are adding this edge to the graph we can click and search
			// on the groups we generate
			graph.add(fromEdge);
		
			// now create and add edges between the movies and genre year group
			for (var i = 0; i < paths.length; i++) {
				 // each result should be a unique movie and will labeled 'm'
				 graph.add( graph.createEdge(group, paths[i].labeled('m').entity));
			}
			// only append the from node (the genre), the year group, and the edge
			// to the result
			this.result(traversalPath.append(fromEdge).append(group));
		}
		

Grouping Shared Relationships - another option

To demonstrate how to group shared replationships, we create a movie_movie relationship for any two movies that contain the same actor. Our query looks like this:

      	graph.query({$choice:[	
			      	....	
			        // movie to movie relationship  
			        ['movie:a', {$replace:[ [ 'edge','person:p','edge','movie:b'], 
			                         groupByCommonPerson, replaceByCommonPerson ]}],
			        ....
			  ]})
 			  .execute(entity).
      	

In this query, we have labeled the two movies 'a' - which will always be the root - and 'b' which comes at the very end of the query. The shared person between them is labeled with 'p'.

For grouping, we use the id of the movie labeled 'b' as the key for our group.

      	// Groups movie by the title. In this case the title being grouped is
		// for the movie -> edge -> person -> edge -> movie:b 
		// condition and by grouping on the last movie, 
		// we can associate movies via common actor.
		function groupByCommonPerson(data, path) {
			return path.labeled('b').entity.id;
		}	
      	

The replace function is actually pretty straight forward. We just create an edge between the two movies and only add the two movies and edge to the result set, thus completely discarding the person connected to the two movies.

      	// Replaces the movie -> edge -> person -> edge -> movie with a 
		// movie -> edge -> movie relationship
		function replaceByCommonPerson(paths, key){
			// get the first movie in the traversal which will be the center
			var traversalPath = paths[0].labeled('a');
			// get the movies at the beginning and end of the traversal -
			// they will be the same for all paths
			var from = traversalPath.entity;	
			var to = paths[0].labeled('b').entity;
			// create an edge between these two movies but don't add the
			// edge to the graph
			var edge = graph.createEdge(from,to,false,{});
			// get all the common people between the two movies - they are labeled
			// with 'p'
			var people = paths.map(function(tp){
				return tp.labeled('p').entity;
			});
			// store them on the edges data
			edge.data.people = people;
			// append the edge and two movies to the result
			this.result(traversalPath.append(edge).append(to));
		} 
      	

One last step - templates

It is important to remember that because our groups are actually nodes, we have to treat them as such. This means, at the very least, we need to create templates for them so that they will actually render.

	
        // a template for the genreyeargroup
		display.template('genreyeargroup').as(function(selection,node) {	
			// if the genreyeargroup is in the center - show the genre
			// name with the year 
			if (centerEntity === node) {
				selection.append('text')
					.style('text-anchor','middle')
					.style('text-align','center')
					.attr('dy', '-10px')
					.text(node.data.genrename);
			}
			// show the year and the count of the genreyeargroup
			selection.append('text')
				.style('text-anchor','middle')
				.style('text-align','center')
				.attr("dy", ".5ex").text(node.data.year+' ('+node.data.count+')');
		});
		
		// a template for the gendergroup
		display.template('gendergroup').as(function(selection,node) {
			selection.append('circle').attr('r',10);
			// a male and female class to help in css styling
			if(node.data.gender == 'male') {
				selection.addClass('male');
			} else {
				selection.addClass('female');
			}
		});

Summary

In this tutorial we covered a few of the ways one can use the $replace operator to do various types of grouping, reducing, and modification of query results. However, the $replace operator is not limited to just these areas and can be used in facilitating very powerful features that extend beyond this tutorial.