State Alternative: Ranges

Frequently we have graphs where nodes and edges simply exist or not in different time periods. We are not interesting in varying any other dynamic property except for existence. For example, a node is active at time 0-5 and 8-12. We do not want to create a state for every time period. A new (.6+) feature of GUESS is a special range index. You may not specify a field for nodes and edges that functions to define these ranges.

The valid syntax for this textual field is a comma delimited set of ranges or individual times. For example: “1-2,5,10-12” indicates that the range of this object is between time periods 1 and 2, at time period 5, and between period 10 and 12. Using an interval tree, GUESS will create an index that can be used to select nodes and edges that are contained in, overlap, contain, or match a range exactly. The operators for this are roverlaps, rcontains, rcontained, and rexact and may be applied to the “Node” and “Edge” objects in the form of:

object operator range

where object is Node or Edge, operator is one of roverlaps, rcontains, rcontained, and rexeact, and the range is either a single number (e.g. 1 which implies a range of 1 to 1), a pair of numbers (e.g. (1,2) which implies a range of 1 to 2), or a string range (e.g. “5-8” which implies a range of 5 to 8).

An example may help. Let’s say we have a simple GDF file:

nodedef> name, range VARCHAR(32)
v0,"1-2,6-9"
v1,"1-3,8-15"
v2,"1-1"
v3,"5-12"
v4,"20-20"
edgedef> node1,node2,directed
v0,v1,true
v0,v2,true
v0,v3,true
v3,v4,true
v2,v4,true
v1,v4,true

We can do the following:

• Node roverlaps (2,5) which returns v0 and v1
  

• Node rcontains 5 which returns v3
  

• Node rcontained (19,21) which returns v4
  

• Node rexact (5,12) which returns v3

By default, GUESS will try and find a “range” field as soon as you invoke one of the range operations. You may also specify an alternative field using the following command (with a field as an argument):

• Node.setRangeField(…)
  

• Edge.setRangeField(…)

Note that if you change the field GUESS will not change the index automatically (e.g. if you say v0.range = ’20-25’ the range will not get updated). In order to force an update, use one of the following commands:

• Node.rebuildRangeIndex()
  

• Edge.rebuildRangeIndex()