maxitg / setreplace Goto Github PK

Right now, sets have to be specified as lists of lists. With rules being lists of rules of lists of lists, that's too many nested lists.

One partial remedy would be to use Rule or DirectedEdge to specify edges (expressions). This could be implemented just for 2-vertex edges, or maybe for arbitrary edges (although that would cause some issues because 1 -> 2 -> 3 is actually a two-level expression in WL).

Right now, WL implementation of SetReplace supports that, but C++ implementation does not, further HypergraphPlot does not support that as well. In those cases, these will have to be treated as special cases.

For example, this

HypergraphPlot[
 SetReplace[{0 -> 1}, 
  FromAnonymousRules[{0 -> 1} -> {0 -> 2, 2 -> 1}], 1, 
  Method -> "C++"]]

should produce the same result as

HypergraphPlot[
 SetReplace[{{0, 1}}, 
  FromAnonymousRules[{{0, 1}} -> {{0, 2}, {2, 1}}], 1, 
  Method -> "C++"]]

Currently, new vertex names produced by C++ and WL implementations are inconsistent.
I.e., consider the following:

SetReplace[{{0, 1}}, 
 ToPatternRules[{{0, 1}} -> {{0, 2}, {2, 1}}], 1, Method -> "LowLevel"]

SetReplace[{{0, 1}}, 
 ToPatternRules[{{0, 1}} -> {{0, 2}, {2, 1}}], 1, 
 Method -> "Symbolic"]

WL names are actually created by a Module on the right-hand side of the rules, thus it allows one to see which part of the rules a given vertex came from.

It would be nice to have these consistent by changing C++ implementation to also use the names from the Module.

This will require, however, to keep track of which part of the rules produced which vertices, which is currently not done in C++ implementation.

Background

Local rules are the ones where the left-hand side forms a connected hypergraph. For example, the rule

{{1, 2, 2}, {3, 2, 4}} -> {{3, 5, 5}, {5, 1, 1}, {4, 1, 3}}

is connected, whereas

{{1, 1}, {1, 2}, {3, 3}} -> {{4, 4}, {4, 1}, {1, 1}, {3, 1}, {3, 2}}

is not. More precisely, the left-hand side is connected if one cannot split it into two subsets such that they don't have any shared atoms. From that we can see the second rule is disconnected as it can be split into {{1, 1}, {1, 2}} and {{3, 3}}.

One can also see the same graphically using RulePlot. For the two rules above,

In[] := RulePlot /@ 
 WolframModel /@ {{{1, 2, 2}, {3, 2, 4}} -> {{3, 5, 5}, {5, 1, 1}, {4,
       1, 3}}, {{1, 1}, {1, 2}, {3, 3}} -> {{4, 4}, {4, 1}, {1, 
      1}, {3, 1}, {3, 2}}}

Current Situation

We currently have two implementations of the WolframModel evolution. They can be accessed with a Method option.

The Wolfram Language ("Symbolic") implementation does support disconnected rules, however the C++ implementation ("LowLevel") one does not.

The reason is due to how the matching is done in the C++ implementation. Currently, the C++ implementation keeps an index of all possible matches to the rules at all times. After each event is instantiated, it needs to update this index. It does it by starting with the just-created expressions and searching for all the expressions nearby that match any of the rules. (Nearby means they have shared atoms similar to the definition of connectedness.) This algorithm fails, however, if the rule is disconnected, as now some of the expressions in the match don't have to be nearby, and so they will never be found.

Possible Solution

One possibility is to note that the two connected components can essentially be matched independently of each other. So, instead of keeping the index of all matches, we can keep an index of all partial matches so that each part corresponds to a connected component. This way, in order to assemble an event, one will just combine multiple of such matches.

This would not provide many benefits for multiway systems (as they will have to enumerate all possible matches anyway), but it will make the singleway (including random) evolution more efficient.

One needs to be careful with two things though. One is the evolution order (affecting how the buckets here should be sorted). Perhaps a greedy algorithm of choosing the best partial matches for a given evolution order will work. But it is not obvious that it will, so it will need to be further investigated.

One also needs to worry about the weighting in the case of random evolution. One can naively assume that in that case every connected component of the event can be chosen independently at random. And for large states, it will approximately be the case. But it is not exactly the case, as matches to different connected components might have shared expressions in some cases, which would make the combination of such partial matches impossible, and might affect the weights. One will need to carefully think about these two problems in order to implement this issue.

Workarounds

Right now, in order to study disconnected rules, one has two possibilities.

Wolfram Language implementation

One can use Method -> "Symbolic" (in fact it will be used automatically if the rule is detected to be nonlocal). That, however, is a much slower implementation than the default C++ one. It also does not support all features (such as "EventOrderingFunction" and "EventSelectionFunction"):

In[] := WolframModel[{{1, 1}, {1, 2}, {3, 3}} -> {{4, 4}, {4, 1}, {1, 1}, {3, 
     1}, {3, 2}}, {{1, 1}, {1, 1}, {1, 1}}, 6, 
  Method -> "Symbolic"]["ExpressionsEventsGraph"]

Adding a connecting atom to each expression

Another approach is to make the left-hand side of the rule explicitly connected by adding an extra atom to every expression. This can be done with pattern rules:

In[] := WolframModel[<|
   "PatternRules" -> {{0, a_, a_}, {0, a_, b_}, {0, c_, c_}} :> 
     Module[{d}, {{0, d, d}, {0, d, a}, {0, a, a}, {0, c, a}, {0, c, 
        b}}]|>, {{0, 1, 1}, {0, 1, 1}, {0, 1, 1}}, 6, 
  Method -> "LowLevel"]["ExpressionsEventsGraph"]

Note, however, this will not be as efficient as the normal rule because the indexing step after the instantiation of each event will have to search through the entire graph for matches. Thus, the time complexity and memory use would be n^c where c is the number of connected components, and n is the size of the state.

UsageString is very small, and it creates additional steps for anyone who wants to install SetReplace. It will be better to just copy relevant code from UsageString directly toSetReplace.wl.

Right now SetReplace is very general, but also very slow. It runs in O(n * s * exp(r)), where n is the size of the set (number of edges in a graph), s is the number of steps, and r is the rule size. Now, exp(r) might have to stay, at least for the worst case, but n * s can certainly be reduced to something like max(n, s).

Also, it would help to implement the low-level code in a low-level language, like C++.

Currently, Wolfram Language implementation takes apart the Module on the right-hand side of the rules and makes certain assumptions about its contents. As a result, a lot of perfectly valid Wolfram Language syntax is unsupported there.

One example is compound expressions outside expressions on the right-hand side of the rule (i.e., inside of a Module) will make the WL implementation treat the entire subset as a single expression, producing unexpected results. For instance,

In[] := SetReplace[{{1, 2}}, {{a_, b_}} :> 
  Module[{c}, Print[c]; {{a, c}, {c, b}}], 3, 
 Method -> "Symbolic"]

yields

c$14386
c$14387
c$14388
Out[] = {{{{{1, c$14386}, c$14387}, 
   c$14388}, {c$14388, {c$14387, {c$14386, 2}}}}}

which is equivalent to this

In[] := SetReplace[{{1, 2}}, {{a_, b_}} :> Module[{c}, {{{a, c}, {c, b}}}], 3,
  Method -> "Symbolic"]

Out[] = {{{{{1, c$16217}, c$16218}, 
   c$16219}, {c$16219, {c$16218, {c$16217, 2}}}}}

instead of that

In[] := SetReplace[{{1, 2}}, {{a_, b_}} :> Module[{c}, {{a, c}, {c, b}}], 3, 
 Method -> "Symbolic"]

Out[] = {{1, c$16230}, {c$16230, c$16229}, {c$16229, c$16231}, {c$16231, 2}}

Another example is a condition which is evaluated after computing the output expressions:

lhs_ :> Module[{z}, 
  z = someFunc[lhs]; 
  z /; z =!= $Failed
]

To fix cases like these, we need to keep the right-hand sides of rules as-is until they are evaluated, at which point we need to disperse the resulting expressions to the resulting set. This will yield interesting consequences, for example, a single rule might have different numbers of outputs based on its inputs.

Implement checking that no multiway branching occurs in a WolframModel evolution.

There are two non-trivial checks that will need to be implemented: one for necessary and one for sufficient conditions.

Necessary condition

For the necessary condition, we need to make sure there is at most one match for every vertex. However, it is possible that the matches that appear different are actually the same, for instance, {{0, 0}, {0, 0}, {0, 0}} can match in multiple ways to {{a_, b_}, {c_, d_}, {e_, f_}}, however, all these matches would produce the same result if evaluated.

Further, it is possible that the rule would preserve symmetry, so, for instance, {{a_, b_}, {a_, c_}, {a_, d_}} -> {} would be confluent if matching degree-3 vertices, even though it can be matched multiple ways.

This must be fast enough to be always on during evaluation.

This (though no fast) was implemented during WSS19.

Sufficient condition

Sufficient condition is more tricky. It has to do with space-like pairs of events that do not simultaneously exist in a current evolution state of the system. For instance, consider the following toy example:

In[] := SetReplace[{1, 2}, {{1, 10} :> {X}, {x_} :> {x + 2}}, 40]

This system does branch, as it is possible to either evolve both numbers simultaneously and get

Out[] = {41, 42}

or it is also possible to evolve 2 4 times, and then use the first rule to get

Out[] = {X}

Hence, it is not sufficient to check duplicate matches between existing subsets of expressions, we need to consider past ones as well. Specifically, we need a fast way to identify if a pair of events is spacelike or timelike (i.e., if a pair of events is causally related).

This probably cannot be always fast, so they could be an option to turn this on and off.

This was not implemented during WSS19.

Implement computation of causal networks.

Vertices are substitution events, vertices are connected if they share events (i.e., the same event is an input for one, and an output for another event).

There are some messages in the package that are used for multiple symbols, such as messages about unsupported cases for C++ implementation can be produced for WolframModel, SetReplace, and other functions.

Currently, messages for an appropriate function are produced and registered, and then called on the fly. However, there is a language mechanism to deal with those, specifically, General:: messages, which should be used instead.

Describe the bug
When graphs are large (> 100 vertices), HypergraphPlot produces very large arrows. It would be nice to have these arrows scale automatically like it is done in Graph.

To Reproduce
Steps to reproduce the behavior:

HypergraphPlot[Table[Table[RandomInteger[{1, 2000}], 10], 50]]

Expected behavior
Arrows are small and do not take over the plot.

Screenshots

Version (please complete the following information):

• OS: macOS
• Wolfram Language Version: 11.3.0.0
• SetReplace git sha: d85b14c

Right now step specification in WolframModel just takes the number of events and the number of generations, and stops evaluating when the earliest is reached.

We can generalize that to make it similar to CellularAutomaton. Specifically, we can have the following choices:

Association input should be able to accept ranges as well.

It would be useful to have proper Wolfram Language documentation for the package. Ideally, the build script in Wolfram Language should build that documentation rather than Eclipse.

It is unclear how to manage it in git given that documentation is typically in a form of notebooks. Perhaps, it is possible to generate these notebooks automatically from a set of definition files containing usage, discussion, examples, etc.

These are significantly more details and a much better explanation in #485.

Implement SetCases that will return all subset matches to a left-hand side of a rule.

Alternatively, that can be implemented as "MatchesList" property of the evolution object.

The property "MatchesList" will give a set of lists of possible matches that could have been made for each of the updates that are done, with the first match being the one actually used. The matches a specified as {index, lhs} where index is the index of the rule used, and lhs is the instantiated left-hand side of the rule.

Currently, the newly created vertices are named automatically with unique symbols. We would like some customization for that, which could be "NodeNamingFunction" option of WolframModel.

By default, In the output from WolframModel, all nodes could be labeled sequentially starting from 1, across all generations in the evolution.

"NodeNamingFunction" -> All renames all nodes to be labeled sequentially starting from 1 , across all generations in the evolution.

"NodeNamingFunction" -> Automatic uses any existing labels, and labels new nodes with names such as vi.

"NodeNamingFunction" -> f names nodes with f[name, list], where name is the existing name of a node, or None if the node is new, and list is a list of the names of all nodes created so far, in the order they were created. Alternative: f[name, count], where count is the number of nodes that exist so far.

Currently, only WolframModel correctly checks for options. For other functions, if options do not exist, they are passed to internal functions without producing any warnings, i.e.,

SetReplace[{1, 2}, 1 -> 3, Metho -> "WolframLanguage"]

yields

We should instead see a single SetReplace::optx message saying Metho is not a valid option.

Right now unit tests test argument checking, however, they don't test if the functions stay unevaluated.

That should be fixed by updating all tests accordingly.

For sufficiently large number of tests, the test report notebook generated would not actually contain the TestReportObject completely, it will instead say "This object cannot be used as input."

There must be some way to force this object to be saved to the notebook as can be done while generating these objects interactively.

To reproduce, run ./build.wls && ./install.wls && ./test.wls, and open the generated notebook.

Alternatively, split correctness.wlt into multiple smaller test files.

HypergraphPlot fails for large graphs (~20k edges).

To Reproduce
Steps to reproduce the behavior:

1. Evaluate the following:

HypergraphPlot[
 SetReplace[{{1}}, FromAnonymousRules[{{1}} -> {{2}, {2}, {1, 2}}], 
  10000]]

2. There are two issues. First, Graph is being returned, not a GraphPlot. This is new behavior in Mathematica 12.
3. Second, there is a Thread::tdlen message.

Expected behavior
There should be no messages, and a picture should be produced (i.e., call GraphPlot) instead of a Graph object.

Screenshots

Version:

• OS: macOS
• Wolfram Language Version: 12.0
• SetReplace git sha: f013220

Right now, building C++ code for SetReplace requires Xcode, so it only works on a Mac.

But the code is quite simple, so it should be easy to build it on Linux and Windows as well.

The Xcode project can probably be deleted at that point and replaced with a cross platform build system such as make.

Right now, C++ implementation of SetReplace called through LibraryLink cannot be aborted during evaluation, except by killing the kernel.

Apparently, there is a way to add some code to the library so that standard way of aborting in Mathematica would abort the evaluation of C++ code as well.

This should be implemented.

It might be possible to statically prove confluence or, more weakly, absence of multiway branching for some systems.

It would be nice if that can be done as it can be much faster than actually running the system.

This is related to #349, which would be a dynamic test for confluence.

C++ code is only fast with certain assumptions, in particular, it assumes that the vertex degrees are small. There is a simple counterexample in which it is not the case:

SetReplace[#[[1]], FromAnonymousRules[#[[2]]], 30, 
   Method -> 
    "C++"] &@{{{1}}, {{{1}} -> {{1}, {1}, {1}}, {{1}, {1}, {1}} -> \
{{1}}}}

This runs 3 seconds, and that increases exponentially with the number of steps. It also consumes exponential memory.

Thus, we need to have a different approach if things like that happen, or, perhaps we should even switch to a different method.

Right now, there are correctness tests for single rules comparing WL and C++ implementations. It would be useful to add tests with multiple rules as well.

The following:

SetReplace[{{1, 5}, {2, 1}, {2, 3}, {2, 4}, {2, 5}, {3, 1}, {4, 
   2}, {4, 5}}, 
 FromAnonymousRules[{{1, 5}, {2, 1}, {2, 3}, {2, 4}, {2, 5}, {3, 
     1}, {4, 2}, {4, 5}} -> {}], 1, Method -> "C++"]

should produce an empty list {}, instead, it returns

{{1, 5}, {2, 1}, {2, 3}, {2, 4}, {2, 5}, {3, 1}, {4, 2}, {4, 5}}

Version (please complete the following information):

• OS: macOS
• Wolfram Language Version: 12.0
• SetReplace git sha: b8157e1

It would be useful for an SetSubstitutionEvolution object to have a property that could be called "Event" that would return the left and right-hand side of the rule used in that event, but with explicit expressions instead of patterns.

For example,

In[] := SetSubstitutionSystem[{{a_, b_}, {b_, c_}} :> {{a, c}}, {{1, 2}, {2, 
    3}, {3, 4}, {4, 5}}, \[Infinity]]["Event", 2]

would yield

{{3, 4}, {4, 5}} -> {{3, 5}}

This is useful for, i.e., highlighting specific events in a HypergraphPlot.

The following produces Rasterize::bigraster warning with ImageSize >= 389:

HypergraphPlot[{{1, 1}, {2, 2}}, ImageSize -> 389]

The output is still correct though.

Version (please complete the following information):

• OS: macOS
• Wolfram Language Version: 12.0
• SetReplace git sha: b8157e1

Documentation should be added to the C++ source code of SetReplace.

Given that WolframModel has a very general functionality, it does not make sense to keep many helper functions, such as SetReplaceFixedPoint, SetReplaceList, etc.

Probably, it might still be useful to rename SetReplaceAll to SetReplace, and keep it in a very simple version, but it's not certain if it's useful at all.

The problem

The Wolfram Language (Method -> "Symbolic") implementation of SetReplace already supports conditions on individual expressions. For example, the following works just fine:

In[] := WolframModel[<|
   "PatternRules" -> {x_, y_ /; y == -2} :> {x + y}|>, {1, -2, 
   3}, \[Infinity]]["ExpressionsEventsGraph", 
 VertexLabels -> Placed[Automatic, After]]

However, the conditions on the entire set are not supported. For example, the following does not get matched at all because the left-hand side of the rule is treated as a single expressions:

In[] := WolframModel[<|
   "PatternRules" -> {x_, y_} /; x + y == 0 :> {x + y}|>, {2, -2, 
   3}, \[Infinity]]["ExpressionsEventsGraph", 
 VertexLabels -> Placed[Automatic, After]]

Possible solution

Wolfram Language implementation currently deconstructs the rules and then puts them back together. However, it assumes the left-hand side of the rule is a list, it does not understand conditions.

One will need to manually pick the condition up, keep it through rule transformations (toNormalRules), and use it for matching.

Write now, WL code is only in two files, one is .wl package, the other one is .wlt tests.

However, it grows quite large.

Might be better to split it into multiple files.

Readme became outdated after the last commit to master.

In particular, it says the package can be installed by importing directly from GitHub, which is no longer the case.

Since the order of rule applications is sometimes important, it is useful to simulate multiway systems.

So, there should be an efficient way to produce a multiway-system graph, which would contain both the connections between multiway states, and corresponding states themselves.

Also, we don't want to store a lot of complete states of the system. We should store multiway system locally by assigning expressions to different branches.

Existing Replace-like functions in Wolfram Language, prioritize replacing earlier expressions to earlier rules, i.e.,

In[] := StringReplace["abc", {"bc" -> "x", "ab" -> "y"}]

Out[] = "yc"

or

In[] := SequenceReplace[{1, 2, 3}, {{2, 3} -> "x", {1, 2} -> "y"}]

Out[] = {"y", 3}

However, SetReplace prioritizes earlier rules, i.e.,

In[] := SetReplace[{{1, 2}, {2, 3}, {3, 
   4}}, {{{2, 3}, {3, 4}} -> {{x, y}}, {{1, 2}, {2, 3}} -> {{x, y}}}]

Out[] = {{1, 2}, {x, y}}

We should have consistency, therefore, the evaluation order should be changed both in "C++" and "WolframLanguage" methods.

There might need to be a subtle difference however, i.e.,

In[] := SetReplace[{{1}, {2}, {3}, {4}, {5}}, {
  {{2}, {3}, {4}} -> {{X}},
  {{3}} -> {{X}}
  }]

needs to evaluate to

Out[] = {{1}, {2}, {4}, {5}, {X}}

so that it is consistent with SetSubstitutionSystem replacing in the same order.

Right now, there just "AtomsCountFinal" and "AtomsCountTotal" functions, there is no way to loop up the number of atoms after a particular event or generation. So, it would be useful to change it, so that there is a property "AtomsCount", which takes a generation as an input, and "AtomsCountTotal", which computes the total count through the whole history.

The same can be done for expressions, and maybe events.

Describe the bug
If a vertex in a graph appears only in a single-vertex edge, this vertex is not displayed by HypergraphPlot at all.

To Reproduce

1. Evaluate

HypergraphPlot[{{0}}]

2. An empty image is produced.

Expected behavior
You should see a picture of a graph with a single vertex.

Screenshots

Version (please complete the following information):

• OS: macOS
• Wolfram Language Version: 12.0
• SetReplace git sha: dcab1c9

Additional context
The issue likely is that HypergraphPlot does not supply the list of vertices to the Graph which it uses.

Implement enumeration of SetReplace systems.

Specifically, come up with a numbering scheme (may be multiple numbers), i.e.,

size.initVsRuleSplit.ruleCount.rule1;rule2;....init

Then, there should be a function which would take this index, and return corresponding system (rules + initial condition).

There should be another function that would return the number of rules (and numbers of classes of rules) given a specific prefix, i.e., given size.initVsRuleSplit. it should be able to return max value for ruleCount, and so on.

There are multiple choices in evaluation of SetReplace, because the rules can sometimes match multiple sets of edges. Right now, a somewhat arbitrary choice is used.

It would be useful to have options in SetReplace for specifying different options. Specifically, there are multiple parameters one could sort by, such as: staleness of edges, permutation of inputs within a single rule, permutations of different rules.

Even after edges are sorted by staleness, the choice may still be non-obvious (i.e., a choice between edges {1, 4} and {2, 3}).

So, it looks like we need to specify sorting hierarchy, i.e., the current choice is {"RuleIndex", "RulePermutation", "MostStale"} ("MostStale" means {1, 4} will be chosen over {2, 3}).

Another possibility would be {"RuleIndex", "RulePermutation", "LeastRecent"}, in which case {2, 3} would be chosen.

The default though should probably be {"RuleIndex", "MostStale", "RulePermutation"}.

We wouldn't want to look at many rules by hand, because we might miss something.

So, it would be better to have a function that would automatically prove that a given system can only have nesting behavior.

An example of the syntax (which can probably be improved as I did not think much about it) could be

SetReplaceNestingQ[rule, init]

would return True, False, or Missing[] if a proof in either direction cannot be found.

We could also have a function that would actually return a proof object, such as

SetReplaceNestingProof[rule, init]

however, that might not be necessary.

The following

In[] := SetSubstitutionSystem[{} -> {}, {}]

should go into an infinite loop, because nothing to nothing can always be matched, and should thus produce an infinite number of events at generation 1.

However, now it returns a zero-events zero-generations object:

SetReplace only applies one of the rules once to the input set.

It would be useful to have a function that applies rules as many times as it takes until touching the same vertex twice is required to evaluate further.

For example, SetReplaceAll[{1, 2, 3}, {x_ :> -x}] would yield {-1, -2, -3}, which is equivalent to SetReplace[{1, 2, 3}, {x_ :> -x}, 3].

Currently, some functions take the number of events, i.e., SetReplace, and some functions take the number of generations, i.e., SetReplaceAll. It is also impossible to produce a SetSubstitutionEvolution object with a given number of events instead of generations, because SetSubstitutionSystem only takes the number of generations as an argument, and does not have any limit for the number of events.

Perhaps a better design would be to instead make all relevant functions take two step arguments, both optional. The first argument would be the number of generations, 1 by default. The second argument would be the number of events, Infinity by default.

For instance,

In[] := SetReplace[{{1, 2}, {2, 3}, {3, 4}, {4, 
   5}}, {{a_, b_}, {b_, c_}} :> {{a, c}}, 2, 2]

would evaluate the system for 2 generations and 2 events, whichever comes first.

Similarly,

In[] := SetSubstitutionSystem[{{a_, b_}, {b_, c_}} :> {{a, c}}, {{1, 2}, {2, 
   3}, {3, 4}, {4, 5}}, Infinity, 2]

would produce an evolution object with 2 events and whatever number of generations necessary to produce them.

Alternatively, instead of an argument, it could be an option, i.e., "MaxEvents", but the argument seems cleaner.

Implement anonymous rules (i.e., rules on vertex lists that name vertices with numbers and assume all vertices are anonymous).

This requires implementing two symbols:

1. AnonymizeRules symbol that takes rules in a form of {{1, 2}, {2, 3}} -> {{1, 3}}, and produces {{a_, b_}, {b_, c_}} :> {{a, c}}.
2. AnonymousRules is kind of the same, but it does not get evaluated, and is only expanded when supplied to SetReplace. Of course the real purpose of it is to use it with C++ code, which would use it directly without expanding it at all.

We should have a way to compare the states of the Wolfram model.

For that, we need a function that would take two hypergraphs as inputs and produce a mapping between atom names which would make them identical.

It would be useful to be able to "fix" some of the atoms so that they cannot be renamed in determining the isomorphism.

Right now, single-vertex edges are displayed by coloring corresponding vertices in a different color. However, they are sometimes hard to see.

It would be better to display them as, say, circles around the vertices.

Perhaps, it would also be better to display 3+-vertex edges without colors as well, say by having an edge split and go around the vertex if it's intermediate.

Since there is a lot of metadata generated during evolution, it might be useful to have a function SetSubstitutionSystem that would return a SetSubstitutionEvolution object, which can then be queried for various options, similar to how ProofObject works.

This object should contain the entire evolution history, in addition to which it could contain causal network, and some additional data about the evolution, such as confluence.

Rules involving empty expressions (hyperedges of zero vertices) and empty subsets are not currently supported by C++ code.

I.e., this:

SetReplace[{}, {} :> {{0}}, Method -> "C++"]

and this:

SetReplace[{{}}, {{}} :> {{0}}, Method -> "C++"]

falls back to Wolfram Language code.

It would be better to support these cases in C++, but they will require special treatment.

Right now, we have tests that construct a random set, and match it to a shuffled version of itself, however, that only tests the matching algorithm, not the replacement algorithm.

It would be useful to have tests that actually take random substitution rules (or lists of such rules), and evolve the system in both C++ and WolframLangugage methods to check for consistency.

That probably requires RandomSetSubstitutionRule function first.

It probably does not make sense to maintain two different implementations, especially given how much slower WL implementation is compare to C++ in most cases.

Perhaps, it would be best to remove it out of the main package, and just keep it for testing purposes.

However, the method used in the WL implementation is valuable, as it performs much better in some cases (i.e., when vertex degrees are very large), so it perhaps should be reimplemented in C++.

Passing large sets to C++ code is very slow. I.e., evaluate:

rules = {{{a_, b_}, {a_, c_}, {a_, d_}} :> 
    Module[{$0, $1, $2}, {{$0, $1}, {$1, $2}, {$2, $0}, {$0, $2}, \
{$2, $1}, {$1, $0}, {$0, b}, {$1, c}, {$2, d}, {b, $2}, {d, $0}}]};
AbsoluteTiming[
  set = SetReplace[{{0, 0}, {0, 0}, {0, 0}}, rules, 100]] // First
AbsoluteTiming[SetReplace[set, rules]][[1]]

The two timings produced should be similar, however, the second one is much slower than the other, which means the slow down occurs when the large graph is passed to C++ code.

Version:

• OS: macOS 10.14.5 (18F203)
• Wolfram Language Version: 12.0.0 for Mac OS X x86 (64-bit) (April 7, 2019)
• SetReplace git sha: 7feedca

Additional:
Unit test for SetCases will need to be updated with a smaller time after that's fixed.

Right now, the name of the repository, and the main function in it is SetReplace.

However, we are actually replacing subsets here, not sets. So, it would be better to call it SubsetReplace instead.