⬆️ 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 { X[!select] }                  % Select an unselected node X
  % 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 { X -> Y; Y.__id__ < X.__id__}  % such that there is no "smaller" node Y linked as a successor of X
  without { Y -> X; Y.__id__ < X.__id__}  % add such that there is no "smaller" node Y linked as a predecessor of X
  commands { X.select=yes }
}

package propagate {
  rule down {
    pattern { Y[select]; X[!select]; Y -> X }
    commands { X.select = yes }
  }
  rule up {
    pattern { Y[!select]; X[select]; Y -> X }
    commands { Y.select = yes }
  }
}

rule remove_unselected {
  pattern { X[!select]; }
  commands { del_node X; }
}

rule clean {
  pattern { X[select]; }
  commands { del_feat X.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:

1. 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
2. Apply iteratively the package propagate in order to mark all the node of the connected component with the feature select=yes
3. Remove all unselected nodes that are not in the current connected component
4. 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: X -[appos]-> Y} 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