Programmatically creating multivariate functions in Mathematica

1
votes

This is a split from discussion on earlier question.

Suppose I need to define a function f which checks if given labeling of a graph is a proper coloring. In other words, we have an integer assigned to every node and no two adjacent nodes get the same answer. For instance, for {"Path",3}, f[{1,2,3}] returns True and f[{1,1,2}] returns False. How would I go about creating such a function for arbitrary graph?

The following does essentially what I need, but generates Part warnings.

g[edges_] := Function @@ {{x}, And @@ (x[[First[#]]] != x[[Last[#]]] & /@ edges)}
f = g[GraphData[{"Path", 3}, "EdgeIndices"]];
f[{1, 2, 1}]==False

This is a toy instance problem I regularly come across -- I need to programmatically create a multivariate function f, and end up with either 1) part warning 2) deferring evaluation of g until evaluation of f

3
wolfram-mathematica
so you have 2 questions (1) how to create a function which takes a vector argument and manipulates it with Part[], and avoid errors arising when Part tries to deconstruct an undefined symbol, and (2) how to remember evaluations of the function so that they don't need to be recomputed. Or have I misunderstood ? - High Performance Mark
That code I suggested earlier builds a function f where f[a,b] gives True if a->b is an edge in the graph indices that were passed to g. I think I misunderstood your question in those earlier comments. - Michael Pilat
Actually, no it doesn't, it builds a function f[x] that gives True if x[[a]]==x[[b]] for any edge a->b in the graph. No coffee yet this morning! - Michael Pilat
Mark: I just need (1). Michael: actually it checks if x[a]==x[b] instead of x[[a]]==x[[b]], that's the problem - Yaroslav Bulatov

3 Answers

1
votes

Here's something. When nothing else is working, Hold and rules can usually get the job done. I'm not sure it produces the correct results w.r.t. your graph-coloring question but hopefully gives you a starting place. I ended up using Slot instead of named variable because there were some scoping issues (also present in my previous suggestion, x$ vs. x) when I used a named variable that I didn't spend the time trying to work around.

g[edges_] := 
 With[{ors = (Hold @@ edges) /. {a_, b_} :> #[[a]] == #[[b]]},
  Function[!ors] /. Hold -> Or
  ]

In[90]:= f = g[GraphData[{"Path", 3}, "EdgeIndices"]]
Out[90]= !(#1[[1]] == #1[[2]] || #1[[2]] == #1[[3]]) &

In[91]:= f[{1, 2, 3}]
Out[91]= True

In[92]:= f[{1, 1, 2}]
Out[92]= False

I feel like it lacks typical Mathematica elegance, but it works. I'll update if I'm inspired with something more beautiful.

1
votes

There are a couple other solutions to this kind of problem which don't require you to use Hold or ReleaseHold, but instead rely on the fact that Function already has the HoldAll attribute. You first locally "erase" the definitions of Part using Block, so the expression you're interested in can be safely constructed, and then uses With to interpolate that into a Function which can then be safely returned outside of the Block, and also uses the fact that Slot doesn't really mean anything outside of Function.

Using your example:

coloringChecker[edges_List] := 
 Block[{Part},
  With[{body = And @@ Table[#[[First@edge]] != #[[Last@edge]], {edge, edges}]},
   body &]]

I don't know if this is all that much less cumbersome than using Hold, but it is different.

0
votes

I'm still puzzled by the difficulties that you seem to be having. Here's a function which checks that no 2 consecutive elements in a list are identical:

f[l_List] := Length[Split[l]] == Length[l]

No trouble with Part, no error messages for the simple examples I've tried so far including OP's 'test' cases. I also contend that this is more concise and more readable than either of the other approaches seen so far.