*** Calculating the components of a graph *** 

Dear Sean Dear Phil, and fellow pundits

Maybe I will just becloud your understanding by jumping
in at this point, but here goes anyhow.

I think we should study a simplest inductive algorithm
for graphs that solves both your problems. That is more or
less present in what has been said --- but mixed up with
other stuff. My prejudice for modularity says this graph
algorithm should be programmed separately and kept in mind
(and on disk).

A few months back I started to program such a thing without
planning ahead and frankly admit to getting lost in the
details.

Here is the situation: A finite graph grows by addition of
vertices one by one. And along with a new vertex come all
the edges that join it directly to earlier vertices.

Abstractly, one knows that at any moment the graph has
finitely many (connected) components. They are like teams;
two vertices are in the same team (component) if you can
get from one t'other by following edges of the graph.

The aim of the algorithm is to inductively and effectively keep
track of the components of the growing graph. The algorithm will
in fact provide a list of all the components; for each component
a list of its members; and finally a means of telling instantly
if two vertices lie in the same component.


Mow my particular linked list model:  

 --- the vertices just after time t  are labelled by the
integers 1,...,t.  You start with no vertices at time 0. We
anticipate <= N vertices labelled 1,...,N, though Mac handles
could make the sky the limit.

 --- Each component will become a linked list.  And the set
of components will be itself a linked list.

     The inductive calculation uses four integer "bookkeeping"
functions  s, p, c, C  on  1,...,N  --- as follows:

  (i) To each integer x  in  1,...,N, a successor s(x) is
specified, and the value 0 means we are at the end of the list
of elements of a component.

  (ii) Similarly one has a predecessor function p(x).  

Warning: There need not be any relation between the *order* in
the list of the vertices in a component and the edges that join
them.

 (iii) The catalog of components is given by a third function c
on  1,...,N.  the vertex t and its edges have been added, we will
have  u  components whose initial vertices are:

       c(1), c(c(1)), ... , c^u(1)

where c(c^u(1)=0 is the first value 0 reached by iterating
c on 1.

 (iv) C  a function that sends the vertices to the positive
integers 1,...,N and that is constant on components of the
graph, but  has different values on distinct components.

     Life begins at time 1 with one vertex  1 , and one has
s(1)=0, p(1)=0, c(1)=1, c^2(1)=0, C(1)=1.

    Now, here is the big inductive step.  Just before time t,
*before* introducing the new vertex t at time t, we have
functions s, p, c describing a collection of  u <= t-1
components:

c^1 :   c^1(1), s(c^1(1)), s(s(c^1(1))),...
c^2 :   c^2(1), s(c^2(1)), s(s(c^2(1))),...
  .
  .
  .
c^u :   c^u(1), s(c^u(1)), s(s(c^u(1))),...

Here c^k(x) means c(c(...c(x)...)) --- with k iterations of
c.  We assume inductively that the function C assigns
integers <= t-1.

We are then presented with a new vertex  t  and a finite set
of new edges that connect the new vertex  t  to some of
the established vertices  1,...,t-1.

First add  t  as an isolated vertex, a new component with

c^(u+1) :  t=c(c^u(1)), s(t)=0, p(t)=0, C(t)=t

Recall that C has value < t on earlier vertices 
so  t  is a new value.

Next, inductively add the new edges one by one;  for each edge
e, the function C applied to the end of the edge remote from  t
tells us whether it is in the component of  t.  If yes, then we
do nothing and just move on to the next edge. If no, then let the
remote end of  e  be in the component

c^k : c^k(1), s(c^k(1)), s(s(c^k(1))),...

we use p and  s to string that preexisting component onto that of
t to form one component, with t  as initial vertex. That revises
p and s.
       
Then, we make c  leap over the vanishing k-th component, say
by setting 

    c(c^{k-1}) = c^{k+1}(1)


We define  t  to be the value of C on the enlarged component of
vertex t.

This completes the induction.

The number of components of a nonempty finite graph is the first
positive integer  n  such that c^{n+1}(1)=0.

There is a lot of overkill in this algorithm, but I think it has
virtues: If we exploit the vertex ordering in the most natural way,
the algorithm is deterministic. And I think all the information
maintained is potentially useful, and that the algorithm is still
fast enough and compact enough (4N integers of storage) to handle
hundreds of thousands of points intercctively. So it is probably
useful for many jobs.

                  Cheers

                        Larry Siebenmann

PS. I have not converted to FB and tested; until someone does,
there will probably be some inadequacies and inaccuracies in the
description above.

PS. The algorithm is so basic that it is probably in some
textbook, but I do not know a reference.