GPM_Core

GPM_Core package contains classes used to generate port graphs for rewriting. More...

GPM_Core package contains classes used to generate port graphs for rewriting.

This package is based on Boost Graph Library (BGL).

The purpose of the package is to rewrite graph:

The Graph with Ports Module is a module to use graph with vertices & edges whose vertices may be either a node and a port.

A node can only connected to ports by undirected edges whereas ports can only be connected to another port or to a node.

If a port is connected to many nodes, all the nodes are considered to be equals. If a port is connected to many ports, all the ports are considered to be equals. All nodes & ports may have tags.

Each graph element which can be either a port , an edge or a node have states defined by a variable. A particular variable called "mCoord" describes the coordinates of a vertex (either a node or a port). Each graph element mays also have trigger actions on modiffing variables. The GPM8GraphElement::executeTriggerActions() return false if the trigger actions can not be executed.

The purpose of this module is to rewriting a port graph to another.

The rewriting of graph consists in replacing all the occurences of a pattern graph by a transformer graph in a large graph. The algorithm needs datas:

• the large graph
• the pattern graph
• the transformer graph
• the transformation rules.

A first set of rules consists in managing the way to connect the transformer graph in the large graph thanks to the mapped pattern graph:

• mark "removed" the large graph nodes which are mapped to the pattern graph to remove it
• mark "removed" the large graph edges which are mapped to the pattern graph to remove it
• add new edge in large graph whose source node is mapped in pattern graph and whose target node is in added transformer graph

Another set of rules consists in modifiing the states of the large graph nodes or edges which are mapped to the pattern graph

• mark "set" to a new value its group name
• mark "set" to a new value its coordinates
• mark "set" or "add" new value in its variables

The last set of rules consists in setting the states of the vertex or edges for nodes or edges in the added transformer graph into large graph.

The re-writing algorithm is as follow:

• get all the mappings of the pattern graph into a large graph. Only vertex or ports with same group name can be mapped one to each other and another routine will validate the found mapping.
• for each mapping, replace the pattern graph by the transformer graph using the transformation rules, in parallel:
  • add a copy of the transformer graph into the large graph
  • add the edges between the mapped pattern graph and the added transformer graph
  • mark the edges or vertices to remove of the mapped pattern graph
  • mark the attributes to change of the mapped pattern graph
  • set the attributes of the added tranformed graph If one of the above action can not be set, the program fails
• execute the preceeding marked actions :
  • remove the marked edge and vertices
  • execute the trigger marked actions attached on kept vertices or edges
  • update the group id of each vertex
• reduce the port graph:
  • all the connected to a vertices to a vertex are merged one to each other
  • if a port is connected to more than one vertex, all the connected vertices are merged one to each other.
  • if a port is connected to more than one port, all the ports are merged one to each other

The rules is the way to connect the transformer graph in the large graph thanks to the pattern graph. The rules is given by the GPM_PatternFunction. The following methods consist in defining the rules to connect mapped transformed graph into large graph:

• GPM_PatternFunction::addPVertexToRemove consists in removing the mapped node from pattern graph to large graph.
• GPM_PatternFunction::addPEdgeToRemove consist in removing the mapped edge from the pattern graph to large graph
• GPM_PatternFunction::addPTEdgeToAdd consists in adding edge whose source node is the mapped node from pattern graph to large graph and target node is the mapped node from transformer graph to large graph.

To match pattern graph, the following methods consist in setting the id of nodes & ports in order to speed up the pattern graph research:

• GPM_PatternFunction::addVariableNameToNodeGroupId() adds the name of the variable to build the id of the node
• GPM_PatternFunction::addVariableNameToPortGroupId() adds the name of the variable to build the id of the port
• GPM_PatternFunction::initGroupNames() builds the id of each vertex.

When a pattern graph is found in the large graph the virtual method GPM_PatternFunction::isMappingValid() enables to reject the mapping if needed.

The GPM_PatternFunction::setIsUpToAutomorphism() method consists innot considering all the permutations of one mapping. The vertices of all mapping are ordered with respect to their internal id. The key is built from this ordered vertices list and this key is registered in a map. If the key already exists, the mapping is rejected, otherwise, the mapping is accepted.

The following virtual methods consist in modifiing the states of the mapped pattern graph to large graph

• GPM_PatternFunction::updateTransformerGraphStates consists in changing the states of variable of the transformer graph
• GPM_PatternFunction::updatePatternGraphStates consists in changing the states of variable of the the mapped node from pattern graph to large graph

The mappings of the pattern graph into a large graph are detected by the GPM_Graph::getPatterns() method. Only vertex with same group name can be mapped and only port with same group name can be also mapped. For each detected mapping, a specialized method GPM_Graph::isMappingValid is called to determine if the mapping is valid when using attributtes (coords,tag) unusued in the previous detecting.

The signal GPM_PortGraph::patternsMappingSignalEmit is emitted for special actions to do after mappings detection.

The method GPM_Graph::addSubGraph copies the transformer graph into a large graph.

The method GPM_Graph::executeTriggerActions execute all the marked actions.

The method GPM_PortGraph::reduce transform a general grap into a port graph.

It contains :

• GPM_Object describes the base class of the package
• GPM_Graph describes a graph which manages vertices & edges
• GPM_PortGraph describes a graph which manages vertices, ports & edges
• GPM_GraphElement describes an element of a graph (vertex,port or edge)
• GPM_Vertex describes a vertex
• GPM_Port describes a port
• GPM_Edge describes an edge between 2 vertices
• GPM_Variable describes the variable of a graph element
• GPM_Function describes a function
• GPM_PatternFunction describes rules for transforming pattern graph to transformer graph
• GPM_ClassFactory is a class which creates package classes
• GPM_CoreRun is the main class of the program.
• GPM_CoreTest is a package test
• GPM_BGLTest is a boost graph library examples.

The organization of this package is as follow: