Using Semirings

From KDTWiki
Jump to: navigation, search

KDT users can define their own semirings, but for the ease of understanding we will recreate the built-in semirings here. The first built-in semiring is sr_plustimes which is the standard (+,*) semiring that performs matrix arithmetic we are used to.

>> addFn = lambda x,y: x+y
>> mulFn = lambda x,y: x*y
>> sR = kdt.sr(addFn, mulFn)

The second built-in semiring is sr_select2nd which always uses the second argument of a pair.

>> Fn = lambda x,y: y
>> sR = kdt.sr(Fn, Fn)

Now let's look at an example where we might want to use a a different semiring. Graph contraction takes a DiGraph \[G= \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 2.0 & 0 & 0 & 0\\ 0 & 0 & 1.0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 2.0 & 8.0 & 0 & 0 & 0 & 4.0\\ 2.0 & 6.0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 3.0 & 0 & 3.0 & 0 & 0 & 0 & 1.0 & 0 & 0\\ 0 & 0 & 0 & 0 & 7.0 & 0 & 0 & 0 & 1.0 & 0\\ 0 & 0 & 0 & 0 & 5.0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1.0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 6.0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 3.0 & 0 & 0 & 1.0 & 0 \end{pmatrix} \] and a label vector \[ \begin{pmatrix} 3\\ 1\\ 1\\ 2\\ 1\\ 0\\ 2\\ 2\\ 0\\ 0 \end{pmatrix} \]

and uses them to create an n by m contraction matrix where n is the number of old vertices and m is the number of new vertices. A non-zero i,j entry means that the old vertex j will be included in the new vertex i. \[M= \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 1.0 & 0 & 0 & 1.0 & 1.0\\ 0 & 1.0 & 1.0 & 0 & 1.0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1.0 & 0 & 0 & 1.0 & 1.0 & 0 & 0\\ 1.0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} \]

Then the contraction is performed by operating on the original matrix using the plustimes semiring. $$G' = M G M^{T}$$ and after removing the main diagonal (we don't want self loops) the result is \[G'= \begin{pmatrix} 0 & 13.0 & 0 & 0\\ 12.0 & 0 & 4.0 & 0\\ 0 & 11.0 & 0 & 2.0\\ 0 & 0 & 2.0 & 0 \end{pmatrix} \]

Using the plustimes semiring means that edges between different two different sets in the labeling will have their weights added to form a single edge in the new graph. Perhaps this is not the functionality we want, maybe we only want to keep around the edge with the highest weight. Then we would define a new semiring and use it in the contraction procedure.

>> maxFn = lambda x,y: max(x,y)
>> mulFn = lambda x,y: x*y
>> sR = kdt.sr(maxFn, mulFn)

The result would instead be \[G'= \begin{pmatrix} 0 & 7.0 & 0 & 0\\ 8.0 & 0 & 3.0 & 0\\ 0 & 6.0 & 0 & 2.0\\ 0 & 0 & 2.0 & 0 \end{pmatrix} \]

Personal tools
Namespaces
Variants
Actions
KDT
Toolbox