** Next:** Experimental results
** Up:** Reduced Set of RSGs
** Previous:** Graph pruning

##

Graph union

Two compatible graphs and , (`COMPATIBLE`
), can be fused in a single graph, , which captures the data
structure information represented by the two original graphs. This
union of graphs is carried out by the `JOIN`
function which builds the new graph, , from the original ones,
and . This function does not modify the pvars set, ,
nor the selectors set, . On the contrary, the nodes set, , and
link sets, and , should be updated.

In particular, some of the nodes of and are going to
be summarized if they are compatible. Now, using the function ` MERGE_NODES` described in Sect. 3.2 we can
describe the sets , , and of the new RSG, resulting from
the union of and :

The set of nodes, , for the new graph, , comprises three
subsets: the non-compatible nodes from , the non-compatible
nodes from , and the nodes resulting from the union of
compatible nodes (`MERGE_NODES`):

=
`C_NODES`
`C_NODES`
`MERGE_NODES`
,

Therefore, we can define a `MAP`,
,
function which points out which node of the new graph is now
representing a certain node of the :

`MAP`

The map function for nodes is similarly defined. By using
this `MAP` function it is easy to describe the new
and sets.

The set of references from pvars to nodes are obtained
by translating the old references from and to the
new graph using the `MAP` function.

Similarly, we obtain the set of links between nodes:

This way, in the new graph, , we keep all the references and
links existing in the original graphs, and , just
changing the source and destination nodes for the
corresponding ones of the new graph using the `MAP` function.

Thus, the new resulting from the union of two compatible
graphs has been completely defined. We emphasize here that due to
this RSG union we can save a great amount of memory space, but at
the same time we enable the representation of several memory
configurations (which are not completely equal) with the same RSG.

** Next:** Experimental results
** Up:** Reduced Set of RSGs
** Previous:** Graph pruning
Rafael Asenjo Plaza
2002-02-19