Graph Extents

A special feature of the graph management is the manipulation of extents. For each used node class in the graph, there exists an Extent which collects all nodes of this class and also has a link to the extent of its superclass and to the extents of its subclasses. This feature is currently used within the RGG plug-in for a fast processing of queries which specify node type patterns like in the rule F(x) == > F(2*x);. Instead of having to scan the whole graph for nodes of class F, the corresponding extent is used together with its sub-extents to directly iterate over all nodes of class F.

Extents are double linked lists. They could be used for any type of java classes. But, in GroIMP they are only created for Nodes in the graph. Thus, the elements of the extents will be referred as Node (and their subclasses). To be part of the project graph an object needs to extends Node. Thus, the highest level of Extent is the one wrapping the type Node. Then, for each new type of Node added in the graph, an extent is created and linked to its direct super class. The type of Node is described by its NType. The NType is an internal class defined by each Node. In java it is usually created with the code enhancer to ensure that all the required attributes for the persistence management are created. In RGG, the NType is automatically created for all modules. If a Node is added to the graph and it extends several level of Nodes, an extent for each intermediate NTypes is created.

Extent implements the following methods:

• getType(): return the type of the node of this extent.
• getSubExtents(): return the list of extents whose type is a sub type.
• getFirstNode(): return the first element added to this extent.
• getNextNode(): return the next element in the chain.
• getTotalSize(): return the size of the extent including the size of its sub extent.

E.g. in the following: (the init method is simplified, and we assume that there are not other nodes in the graph)

module A;
module B extends A;
module C extends B;
 
init()[ Axiom ==> C; ]

the graph only contains the root: Node, the RGGRoot, and one C node. GroIMP will create the following extents:

• one for Node of size 1
• one for RGGRoot of size 1
• one for A of size 0
• one for B of size 0
• one for C of size 1

An extent collects its nodes not by a single list, but by a number of (doubly linked) lists. Currently, eight lists are used, but this can easily be changed. This feature is used to partition the extents. The eight lists are called the extent indexes.

The extent indexes are defined from 0 to 7. By default most nodes added to the graph are added with the index 0. There are two exceptions (by default. You can manually set index of Node):

1. meta objects: Nodes of the meta graph. Added at index 7.
2. GUI inserted objects: Nodes inserted from the GUI. Added at index 6.

The most common example of extent index is the meta-graph. Each project in GroIMP includes a meta-graph with at least one node per compiled file in the project. Yet, these Nodes are not returned by default in XL queries. The reason is that, they were added to an invisible (by default) extent index.

Note: before GroIMP version 2.1.5, all objects added through the GUI>objects>insert> … where also added on the extent index 7. Thus, not queriable by default. E.g. If you inserted a Plane in the scene, it was not reachable by default queries. In GroIMP version 2.1.5 their extent index have been changed to 6.

An index is visible, if it is included in the queries. A Node can be added in the scene with a geometrical representation, and still be in an invisible index. By default only the 7th first indexes are visible (0 to 6). The last index (7) is not visible.

It is possible to change the index visibility in a project with the method: setVisibleExtents(int ) on the RGGGraph.

For instance, let's consider the following method in an empty project. Notice that we set the visible extent value to 1:

public void run(){
de.grogra.rgg.model.Runtime.INSTANCE.currentGraph().setVisibleExtents(1);
println((*Node*));
}

The method output:

de.grogra.rgg.RGGRoot[id=99]@2e86af42
de.grogra.rgg.Axiom[id=100]@59f1c976

Only the “normal” nodes are visible.

Let's change the visible extent value to 255. Now the method output:

de.grogra.graph.impl.Node[id=0]@5add4889
de.grogra.graph.impl.Node[id=1]@4f690d55
de.grogra.rgg.RGGRoot[id=103]@621de1a6
Model[id=101]@331e288e
parameters[id=102]@cd97a89
de.grogra.rgg.Axiom[id=104]@4cface1f

Some additional nodes are now visible:

• the roots (id 0 and 1). id 0 is the root of the main graph. id 1 is the root of the meta graph.
• the nodes from the meta graph: the compiled version of the files: Model, and parameters.

Notice that:

• Once the setVisibleExtents is called. The value remains until a new value is set.
• setVisibleExtents use as parameter the decimal value of a binary number of 8 values where each 1 mean that the index is visible, the 0 to 7 index visibility are defined from left to right. E.g. to have all indexes visible, we use 11111111 (eight 1), which is equal in decimal to 255. To have all indexes visible except for the 1rst one, we use 11111110 (=254). The default value is 01111111 (=127).

Extent are used in RGG for queries that involve Node types. E.g. the query F +> Node /> Model.A =⇒; will be resolved by: looping over the Extent of F, finding the edges that matches to the Extent of Node, …

Such a query will not visit the graph. It will loop over the extents data. Thus, the complexity of the graph might not affect the query.

Speed up queries by using more specific Node type: As the query loop over the extents content, ( (*Node*)) will loop over all nodes in the graph, while ( (*Model.A*)) only on the Extent Model.A and its sub extent. Each edge condition add a level of complexity. For instance: [Node Node Node == >;] has a complexity of n³ (n being the number of Node).

Additionally, the extent non visible indexes are not included in the query. Thus, nodes whose extent index is not visible will not add any complexity to the query.

The following code will create a chain of 8 cylinders, then stop growing.

module A(int i) extends F {
{setExtentIndex(i);}
}
 
static int i = 0;
{de.grogra.rgg.model.Runtime.INSTANCE.currentGraph().setVisibleExtents(127);}
 
public void init()[ Axiom ==> A(i); ]
 
public void run() [ a:A(x), (x==i) ==> a A(++i); ]

Indeed, the last F added as an extent index of 7, thus not visible (setVisibleExtents(127) means 0 to 6 visible). In this case, the query search for F that have a extent index of 7, but the index is not visible, thus, not used in the query.