Speed up Matching with Lookup Maps

Table of Contents

Basics

Let’s assume you have two node classes, a high number of instances (n) and a mapping attribute called ID. If two nodes of the two classes share the same ID a certain action shall be executed. If you look for this pattern in a classic LHS rule pattern the number of matches that need to be checked is n², which can lead to long running times. One way to increase the performance of your analysis is to create a lookup map for one node class containing the ID-attribute as domain and the related node as the range. The following image graphically explains the idea.

Map Match
Use of maps for LHS matches

You create a map for all nodes of one class. Next, you loop over the instances of the other node class and check whether the id can be found in the map. If so, a certain action can be executed between the respective nodes. This way the program doesn’t have to go through all possible combinations of the two node classes and also doesn’t have to access different graph elements but just loop through a container, which is a much faster operation (log(n)).

How to set it up

  1.  Create a procedure, initialize the map and fill it with the instances of the first node class and the parentid value:
    procedure findLHSmatches(){
    def ref container:map<string,Part> = map<string,Part>{};
    for(n:Part in nodes(Part)){
    container.add(node.parentid,node);
    }
    return();
    }
  2. Loop over the other node class and check if the instances’ id attribute is found in the container, if yes pick the node out of the map:procedure findLHSmatches(){
    def ref container:map<string,Part> = map<string,Part>{};
    for(n:Part in nodes(Part)){
    container.add(node.parentid,node);
    }
    for(parent:Product in nodes(Product)){
    if(parent.id in container){
    def child:Part = container[parent.id];
    }
    return();
    }
  3. And then run a calculation and create and edge between the nodes:procedure findLHSmatches(){
    def ref container:map<string,Part> = map<string,Part>{};
    for(n:Part in nodes(Part)){
    container.add(n.parentid,n);
    }
    for(parent:Product in nodes(Product)){
    if(parent.id in container){
    def child:Part = container[parent.id];
    parent.cost = parent.cost + child.cost;
    parent-:Contains->child;
    }
    }
    return();
    }

One limitation of GrGen is the use of containers in containers, meaning that you cannot create a map that contains another container, like a set. As this can be very helpful, for example, to group all products of the same id, we created a set of library elements for Soley Studio that do this, as described in this article.

Was this article helpful?

Related Articles