# 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.