Differences

This shows you the differences between two versions of the page.

--- groimp-platform:extents [2024/12/16 18:13] – gaetan
+++ groimp-platform:extents [2025/01/14 15:29] (current) – gaetan
@@ Line 1: / Line 1: @@
 ====== Graph Extents ======
-A special feature of the graph management is the manipulation of [[https://javadoc.grogra.de/graph/de/grogra/graph/impl/Extent.html|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.
+A special feature of the graph management is the manipulation of [[https://javadoc.grogra.de/graph/de/grogra/graph/impl/Extent.html|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.
@@ Line 41: / Line 41: @@
 ===== Extent index =====
-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.
+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):
   - //meta objects//: Nodes of the meta graph. Added at index 7.
-  - //GUI inserted objects//: Nodes inserted from the GUI. Added at index 6.
+  - //GUI inserted objects//: Nodes inserted from the GUI. Added at index 6 (since GroIMP 2.1.5, they where added to index 7 before).
 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.
@@ Line 54: / Line 54: @@
 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;
+=== Example ===
+For instance, let's consider the following method in an empty project. Notice that we set the visible extent value to 1:
 <code java>
@@ Line 93: / Line 96: @@
 ===== Extent in XL queries =====
+=== Graph complexity ===
-For instance the following graph, where //RGGRoot// extends //Node//, and //Model.A// extends //Node//:
+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//, ...
-<uml>
+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.
-@startuml
-(Model.A) as a1
+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).
-(Model.A) as a2
-(Node) --> (RGGRoot)
-(RGGRoot) --> a1
+=== Indexes ===
-(RGGRoot) --> a2
-@enduml
+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.
-</uml>
+=== Examples ===
+The following code will create a chain of 8 cylinders, then stop growing.
+<code java>
+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); ]
+</code>
-GroIMP creates three extents, one for each type: Node, RGGRoot, and Model.A.
+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.
-Extents work as linked list.