Module wl
k-dim Weisfeiler-Lehman algorithm
Functions
| replaceInt (n) | Replacement function for the case, where V={0,..,n-1} and k-tuples are encoded as n-ary numbers, and kWL will run for one graph. |
| replaceInt2 (n, k) | Similar to replaceInt, but for 2 graphs. |
| replacePlain (t, i, v) | If k-tuples are just tables of length k and __index etc. |
| replace1d (am) | Replacement function (like replaceInt) for k=1. |
| __lt (d1, d2) |
Tables
| indexByTuple | We plan to use color[t] for, e.g., t={3,8,7} in 3-WL Internally color[t] is stored at color.indexByTuple[3][8][7] Note that kWLMain never assigns a new table to color. |
Functions
- replaceInt (n)
-
Replacement function for the case, where V={0,..,n-1} and k-tuples
are encoded as n-ary numbers, and kWL will run for one graph.
A replacement function take an encoded tuple t=(u1,...,ui,...),
a position i and the element v to put in place i. Then it return the
encoding for the tuple t'=(u1,...,ui-1,v,ui+1,...).
Parameters:
- n
- replaceInt2 (n, k)
-
Similar to replaceInt, but for 2 graphs.
Here not all (2n)^k tuples are considered, but
only the 2(n^k) where all elements come from the same graph, thus
replacement depends on the graph the tuple is taken from.
Parameters:
- n
- k
- replacePlain (t, i, v)
-
If k-tuples are just tables of length k and __index etc. is used
see indexByTuple.
Parameters:
- t
- i
- v
- replace1d (am)
-
Replacement function (like replaceInt) for k=1.
for 1-dim-WL, we replace the ith vertex (i is always 1) u in the
"tuple" t=(u) by v iff v is a neighbor of u in G, otherwise we
return nil/. Thus kWLsift will return "()" for non-neighbors
and "("..c..")" for neighbors, where c is the old color of u.
As this depends on the adjacency of a graph G, this function
returns the actual replacement function.
Parameters:
- am
- __lt (d1, d2)
-
Parameters:
- d1
- d2
Returns:
- boolean d1 stands before d2 or is equiv. to d2
- number r: d1,d2 can be separated in round r