⬆️ Top

# Compute the connected components of a graph

The strategy `main`

of the GRS below (cc.grs) outputs a set of graphs, each one being one of the connected components of the input graphs.

```
rule select_one { % This rule applies exactly once on each connected component of the graph.
pattern { N[!select] } % Select an unselected node N
% Nodes are totally ordrerd though an internal "__id__" value;
% we use this in the two without clauses below to ensure that only one node can be chosen in a given connected component:
% the "smallest" one, according to "__id__" order
without { N -> M; M.__id__ < N.__id__} % such that there is no "smaller" node M linked as a successor of N
without { M -> N; M.__id__ < N.__id__} % add such that there is no "smaller" node M linked as a predecessor of N
commands { N.select=yes }
}
package propagate {
rule down {
pattern { M[select]; N[!select]; M -> N }
commands { N.select = yes }
}
rule up {
pattern { M[!select]; N[select]; M -> N }
commands { M.select = yes }
}
}
rule remove_unselected {
pattern { N[!select]; }
commands { del_node N; }
}
rule clean {
pattern { N[select]; }
commands { del_feat N.select; }
}
strat main {
Seq (
select_one,
Onf (propagate),
Onf (remove_unselected),
Onf (clean),
)
}
```

## Explaining the GRS

Applied on a graph *G*, the GRS works as follow:

- Apply the
`select_one`

rule which output exactly one new graph for each connected component (see comments in rule for detail); in the graph one of the node of the selected connected component contained the features`select=yes`

- Apply iteratively the package
`propagate`

in order to mark all the node of the connected component with the feature`select=yes`

- Remove all unselected nodes that are not in the current connected component
- Remove the feature
`select=yes`

on all nodes

## Examples

### Basic two components graph

With the graph `two_cc.json`

, and the command:

```
grew transform -grs cc.grs -i two_cc.json -json
```

We obtained two output graphs, one for each connected component in the input graph.

Input | Output 1 | Output 2 |
---|---|---|

### Example with linguistic data

Starting with the sentence below:

We apply to it the following GRS which removes `appos`

relations:

```
rule r { pattern { e: M -[appos]-> N} commands {del_edge e }}
strat main { Onf (r) }
```

We obtained the following structure:

If we applied the GRS above, we obtained 3 small structures:

cc1 | cc2 | cc3 |
---|---|---|