> I have read some information on Link on the web. It seems a very
> interesting system to me, but before I ask someone to install it (I
> can't do it myself) I would like to have answers to a few questions:
>
> - Which properties of simple undirected graphs can be easily computed?
> For example, are there (standard) menu options for the connectivity,
> the independence number (=stability number), hamiltonicity etc?
These property tests are not there yet. They probably will be
by the end of this summer. The base system is well set up to
add these easily, but I won't have time for quite awhile. In
the meantime, there are several algorithms and operations
(complement, isomorphism, product, dfs, bfs, strongly-connected
components, kruskal's algorithm).
> - If I want to program new functions on graphs (properties which cannot
> be computed by Link yet), in what language do I have to do that? Is that
> an easy-to-learn language?
Scheme, a small dialect of LISP, is the command language. It
is easy to learn a small enough subset of Scheme to put several
Link commands together, for example, to generate a set of
random graphs and thicken the edges of minimum spanning trees
in each.
More involved programming uses C++ libraries. There are many
examples of this in the programmer's manual.
> - Is it possible to (easily) generate (automatically) all graphs on at most
> (for example) 15 vertices and check if these graphs have certain
> properties (useful for investigating conjectures)?
This is another "no" but future "yes." I have linked in a
subset of Brendan McKay's "nauty" isomorphism testing system,
but he also has programs to generate all non-isomorphic graphs
of a given size. I am looking for student help in this (and
many other problems), so progress will depend on how much help
I can get.
If you are thinking of downloading Link anyway, you might want
to wait a month. I am adding some features now and will post a
new version in early March.
Jon Berry