Follow by Email

Tuesday, November 1, 2011

Mathematica Snippet #1 (tiny post)

Assume you have a graph encoded as a set of edges E. For example E = { a -> b, b-> c, c->f, ... }. And you want to compute the set of neighbors of some node v, not taking into account the direction of edges.

This could be done very succinctly using this one liner:

This is simply a "rule" (mathematica's lingo for function), that returns the set of vertices adjacent to v. How does it work ? It just uses the built-in mathematica function "Cases", which searches through a list for a given pattern. When this pattern is found, it will be transformed according to a given transformation.

The patter we are searching is an edge whose head or tail is v, that is we are searching for either "x->v" or "v->x", for any x. This is captured in the pattern we are searching for as "(n_ -> v) | (v->n_)". the underscore after the n means that it is a free variable, intuitively it means what we meant in the previous sentence when we said "v->x" for any x.

The second part ":> n", simply says that when this pattern is found, transform it to x. That is, if you found an edge "v->d", return "d", as this is the only part I care about.

No comments: