Part 1 in this series can be found here.

So, by the end of the previous post on Mathematica and Graph Theory, we had managed to take our single string of text and turn it into a graph of ingredients which go well together. Now we actually want to do something useful with this data – ie. come up with some tasty recipes!

We will refer in the following to foodgraph as the graph of all of the food pairings we started with

We will define a recipe very loosely as a set of ingredients all of which go well together. This is clearly far from a real recipe, but it’s a pretty good starting point for one.

Within the graph, a set of ingredients which all go well together form what is known as a connected subgraph – each node is linked to every other node. It’s no good having a recipe where A goes well with B and B goes well with C, but A doesn’t go well with C.

A connected subgraph is known in graph theory language as a clique, and luckily Mathematica has a very simple syntax for us, however, we need to be a little careful. In fact when we run the command:

FindClique[foodgraph, {n}, All]

Will find all the maximal cliques of size n in the graph foodgraph. Note however that this will find only maximal cliques. This means that it will not find any cliques which themselves are subgraphs of larger cliques, but in fact these would be rather useful too.

It turns out that the largest clique in our graphs are of size 8, and there are a total of four of these:

• basil, fennel, marjoram, onion, oregano, parsley, rosemary, thyme
• basil, fennel, garlic, marjoram, oregano, parsley, rosemary, thyme
• allspice, cardamom, cinnamon, clove, coriander, cumin, ginger, nutmeg
• allspice, cinnamon, clove, coriander, cumin,  ginger, mace, nutmeg

We can see immediately from this that there are some pretty clear missing food pairings in our original string. For instance we can see that onion and garlic have not been paired, else there would have been the combined clique containing the union of the first two sets. Similarly mace and ginger have not been paired as the same would have been true for the second two cliques.

For any cooks of European-based cookery out there none of these ingredient lists would be very surprising. We need to dig a bit further to find some more unusual combinations.

To find all the cliques of size 7, running the command

FindClique[foodgraph, {7}, All]

Isn’t quite right as this will not include subgraphs of the cliques of size 8.

The size seven cliques are thus given by:

size7cliques=Join[FindClique[gg, {7}, All], Flatten[Table[Delete[#, n] // Sort,{n, 8}]&/@FindClique[gg, {8}, All], 1] // Union] // Union

Where we have added to the maximal cliques of size 7, all size 7 subgraphs of the cliques of size 8. Getting down to smaller cliques requires simply an iteration of the above line. Plotting the (log of the) numbers of cliques of each size gives an intriguing plot:

This perhaps raises the question as to what we can learn about a graph structure by studying the form of this curve.

OK, but for now we want to be able to code something more useful than simply finding cliques. What if you look in your cupboard and find that you have coconut and cilantro and you want to be able to create recipes using these ingredients. Well, let’s write a module to do this:

findcliquewith[ingredients_]:=Module[{nit, allcliques, recipe, cliqueswithfood1},
     allcliques = FindClique[gg, 8, All]; (*find all of the cliques in the whole graph*)
     DeleteCases[If[Intersection[#, Sort[{ingredients} // Flatten]] == Sort[{ingredients} // Flatten], #] & /@ allcliques, Null]
]