R Source Code

Algebraic Geometry: Minimal Free Resolutions of the Edge Ideal of a Graph

Given a graph G on n vertices, labeled {x_1,...,x_n}. Let k be a field, and S=k[x_1,...,x_n] the polynomial ring. The edge ideal of G is the ideal of S generated by those monomials x_ix_j corresponding to edges in G. We can study the graph by studying this ideal and in particular, by considering the free resolution of this ideal. See Splitting Cycles in Graphs and Chordal Graphs and Minimal Free Resolutions.

Code implementing some algorithms described in the above papers is available at CRAN. The code contains C routines, and makes calls to Singular. This is not necessary, particularly if the graph in question is chordal, but unless the graph is chordal or one of a very small number of special cases, the code will only return an "approximation" if Singular is not available.

Class Cover Catch Digraph

Class cover catch digraphs are a method of reducing the complexity of a classification task by covering the training points of one class by balls that do not intersect the other class. One then constructs the catch digraph defined by these (pointed) balls, and uses a greedy algorithm to approximate a minimal dominating set of the directed graph, producing a (near) optimal covering of the one class with balls (optimal in the sense of lowest number of balls required in the cover). Variations on this theme are implemented, as well as several types of classifiers based on this idea. See:

Class Cover Catch Digraphs, Classification Using Class Cover Catch Digraphs, A Hierarchical Methodology for Class Detection Problems with Skewed Priors and On the distribution of the domination number for random class cover catch digraphs.

R code (which calls some C functions for some of the computations) is available here: cccd.tgz and at (CRAN).

Some Misc Utilities

pdist computes interpoint distance matrices. pdist(X,Y) computes the distances between the rows of X and those of Y, with a few variations on which distance is computed. This is a part of cccd, but sometimes it's nice to just have the pdist part without all the rest.

stem some stemmer code I found on the web (in C) called from R.