CNL Generation Algorithm

The below algorithm (Algorithm 1), describes how the CNL tree is constructed. The starting node represents the input concept or the starting position. This initial node is then expanded (linked) with additional nodes, based on the traversal. After the construction is completed, traversing the constructed node (Algorithm 2) results in the verbalized output.

Algorithm 1: Construct CNL Tree

1: procedure build_cnl_tree(start_node, vocabulary, collected_triples, instance_stats)
2:     sparql_query ← build SPARQL query for start_node's path
3:     query_results ← execute query on graph
4:     is_normalized ← False
5:     for each pattern in patterns do
6:         if pattern.check(query_results) then
7:             query_results ← pattern.normalize(start_node, collected_triples)
8:             is_normalized ← True
9:             instance_stats.patterns_evaluated ← instance_stats.patterns_evaluated + 1
10:         break
11:     end if
12:     end for
13:     start_node.display_label ← vocabulary.get_class_label(start_node.concept)
14:     for each (predicate, object_node) in query_results do
15:         predicate_label ← vocabulary.get_relationship_label(predicate)
16:         if predicate_label = Vocabulary.IGNORE_VALUE then
17:             collected_triples.append((start_node.concept, predicate, object_node))
18:             continue
19:         next_node ← create VerbalizationNode for object_node
20:         new_edge ← create VerbalizationEdge (predicate, next_node)
21:         new_edge.display_label ← predicate_label
22:         start_node.add_edge(new_edge)
23:         collected_triples.append((start_node.concept, predicate, next_node.concept))
24:         instance_stats.relationship_counter[predicate] ← instance_stats.relationship_counter[predicate] + 1
25:         if object_node is URIRef then
26:             object_display_label ← vocabulary.get_class_label(object_node)
27:         else if object_node is Literal then
28:             object_display_label ← object_node.toPython()
29:         else if object_node is BNode then
30:             build_cnl_tree(next_node, vocabulary, collected_triples, instance_stats)
31:             continue
32:         else
33:             object_display_label ← None
34:         end if
35:     next_node.display_label ← object_display_label
36:     end for
37: end procedure

Algorithm 2: Verbalize Node

1: procedure verbalize 2:     sentences ← create empty list
3:     for each edge in self.references do
4:         sentence ← call edge.verbalize().strip()
5:         append sentence to sentences
6:     display_label ← self.display
7:     if is_blank_node(self.concept) then
8:         display_label ← empty string
9:     if length(sentences) ≥ 2 then
10:         next_text ← combine sentences with , and and wrap in parentheses
11:     else if length(sentences) = 1 then
12:         next_text ← first item in sentences
13:     else
14:         next_text ← empty string
15:     if is_vowel(display_label[0]) then
16:   indefinite_article ← 'an '
17:     else
18:         indefinite_article ← 'a '
19:     return indefinite_article + display_label + next_text
20: end procedure