Mike Gerwitz

Activist for User Freedom

aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMike Gerwitz <gerwitm@lovullo.com>2016-07-05 15:18:38 -0400
committerMike Gerwitz <gerwitm@lovullo.com>2016-07-06 00:14:53 -0400
commit551e489c5fdbee5057b27d665ed0a3ab1751b901 (patch)
treeee3380a4713e67dc926cad0cbd347ca3f3cc64a4
parente34cf22d6b84bbcf9a144128fdf6fb7eebc6f357 (diff)
downloadtame-551e489c5fdbee5057b27d665ed0a3ab1751b901.tar.gz
tame-551e489c5fdbee5057b27d665ed0a3ab1751b901.tar.bz2
tame-551e489c5fdbee5057b27d665ed0a3ab1751b901.zip
Add graph:union
* src/graph.xsl (graph:union): Added * test/graph-test.xsl: Test data added * test/graph.xspec: Tests added
-rw-r--r--src/graph.xsl46
-rw-r--r--test/graph-test.xsl70
-rw-r--r--test/graph.xspec46
3 files changed, 162 insertions, 0 deletions
diff --git a/src/graph.xsl b/src/graph.xsl
index 692f577..387d183 100644
--- a/src/graph.xsl
+++ b/src/graph.xsl
@@ -144,4 +144,50 @@
</preproc:sym-deps>
</function>
+
+<!--
+ Merge sequence of graphs @var{$graphs} into a single graph by taking
+ the union of all vertices and edges.
+ Directionality will be preserved.
+
+ Edge attributes (@code{preproc:sym-ref/@@*)} will be set to the
+ union of all attributes on all edges of the same @code{@@name}.
+ @emph{If edge attributes do not share the same value,
+ the behavior is undefined.}
+
+ For example:
+
+ @float Figure, fig:union-graph
+ @verbatim
+ G₁: A->B->C
+ G₂: C->A
+ G₃: B->C->D
+
+ G∪: A->B->C->D
+ ^____/
+ @end verbatim
+ @caption{(G₁ ∪ G₂ ∪ G₃)}
+ @end float
+-->
+<function name="graph:union" as="element( preproc:sym-deps )*">
+ <param name="graphs" as="element( preproc:sym-deps )*" />
+
+ <preproc:sym-deps>
+ <for-each-group select="$graphs/preproc:sym-dep"
+ group-by="@name">
+ <preproc:sym-dep name="{@name}">
+ <for-each-group select="current-group()/preproc:sym-ref"
+ group-by="@name">
+ <preproc:sym-ref>
+ <sequence select="current-group()/@*" />
+
+ <!-- keep our name (overrides the above) -->
+ <attribute name="name" select="@name" />
+ </preproc:sym-ref>
+ </for-each-group>
+ </preproc:sym-dep>
+ </for-each-group>
+ </preproc:sym-deps>
+</function>
+
</stylesheet>
diff --git a/test/graph-test.xsl b/test/graph-test.xsl
index fea46fa..63cf618 100644
--- a/test/graph-test.xsl
+++ b/test/graph-test.xsl
@@ -99,6 +99,76 @@
</variable>
+<variable name="foo:graph-empty" as="element( preproc:sym-deps )">
+ <preproc:sym-deps />
+</variable>
+
+
+<variable name="foo:graph-vtwo" as="element( preproc:sym-deps )">
+ <preproc:sym-deps>
+ <preproc:sym-dep name="a">
+ <preproc:sym-ref name="a" attr1="foo" />
+ <preproc:sym-ref name="b" attr2="bar" />
+ </preproc:sym-dep>
+
+ <!-- test empty for merge -->
+ <preproc:sym-dep name="b" />
+ </preproc:sym-deps>
+</variable>
+
+
+<variable name="foo:graph-vthree" as="element( preproc:sym-deps )">
+ <preproc:sym-deps>
+ <preproc:sym-dep name="a">
+ <preproc:sym-ref name="b" attr1="foo" />
+ <preproc:sym-ref name="c" />
+ </preproc:sym-dep>
+
+ <preproc:sym-dep name="b">
+ <preproc:sym-ref name="c" attr3="baz" />
+ </preproc:sym-dep>
+
+ <preproc:sym-dep name="c">
+ <preproc:sym-ref name="a" />
+ </preproc:sym-dep>
+
+ <!-- disconnected -->
+ <preproc:sym-dep name="d">
+ <preproc:sym-ref name="e" />
+ </preproc:sym-dep>
+
+ <preproc:sym-dep name="e" />
+ </preproc:sym-deps>
+</variable>
+
+
+<!-- result of merging the above two -->
+<variable name="foo:graph-vtwo-vthree" as="element( preproc:sym-deps )">
+ <preproc:sym-deps>
+ <preproc:sym-dep name="a">
+ <preproc:sym-ref name="a" attr1="foo" />
+ <preproc:sym-ref name="b" attr1="foo" attr2="bar" />
+ <preproc:sym-ref name="c" />
+ </preproc:sym-dep>
+
+ <preproc:sym-dep name="b">
+ <preproc:sym-ref name="c" attr3="baz" />
+ </preproc:sym-dep>
+
+ <preproc:sym-dep name="c">
+ <preproc:sym-ref name="a" />
+ </preproc:sym-dep>
+
+ <!-- disconnected -->
+ <preproc:sym-dep name="d">
+ <preproc:sym-ref name="e" />
+ </preproc:sym-dep>
+
+ <preproc:sym-dep name="e" />
+ </preproc:sym-deps>
+</variable>
+
+
<function name="foo:lookup">
<param name="yield" as="element()" />
<param name="symbol" as="element( preproc:sym )" />
diff --git a/test/graph.xspec b/test/graph.xspec
index 14a04ef..c5e3216 100644
--- a/test/graph.xspec
+++ b/test/graph.xspec
@@ -171,4 +171,50 @@
$edge/@cattr = 'cvalue'
and $edge/@cattr2 = 'cvalue2'" />
</scenario>
+
+
+ <scenario label="graph:union">
+ <scenario label="given nothing">
+ <call function="graph:union">
+ <param name="graphs"
+ select="()" />
+ </call>
+
+ <expect label="produces an empty graph"
+ select="$foo:graph-empty" />
+ </scenario>
+
+
+ <scenario label="given two empty graphs">
+ <call function="graph:union">
+ <param name="graphs"
+ select="( $foo:graph-empty, $foo:graph-empty )" />
+ </call>
+
+ <expect label="produces an empty graph"
+ select="$foo:graph-empty" />
+ </scenario>
+
+
+ <scenario label="given graph with empty">
+ <call function="graph:union">
+ <param name="graphs"
+ select="( $foo:graph-empty, $foo:graph-vtwo )" />
+ </call>
+
+ <expect label="produces the non-empty graph"
+ select="$foo:graph-vtwo" />
+ </scenario>
+
+
+ <scenario label="given two different graphs">
+ <call function="graph:union">
+ <param name="graphs"
+ select="( $foo:graph-vtwo, $foo:graph-vthree )" />
+ </call>
+
+ <expect label="merges vertices and edges of unique vertices"
+ select="$foo:graph-vtwo-vthree" />
+ </scenario>
+ </scenario>
</description>