Conference rusure::math

    Re .0:
    
    > Does someone have a quick and easy way to find the diameter of a graph?
    
    Pick it up by any node.  Then grab the lowest-hanging node and let the
    graph hang from that node.  The distance from that node to the new
    lowest-hanging node is the diameter of the graph.
    
    Sorry, couldn't resist.           
    
    
    				-- edp

>    Pick it up by any node...

This works iff the graph is acyclic. More formally, pick a node and compute
the distances to all other nodes. Take the node at maximum distance and
repeat the computation. The maximum from that result is the diameter. The 
proof is a little tricky, since the diameter may not pass through the first 
node picked.

    Consider this technique (basically the same as in .1 and .2):
    
    	a.  Hold the graph up by a node,
    	b.  Pick the/a bottommost node, and then hold the graph up by that node,
    	c.  Repeat step b (as necessary).
    
    Out of curiosity, does this work on a cyclic graph, if it's applied
    enough times?  If so, how many times is enough?  If not, what is a
    counter-example?

A cyclic graph has an infinite diameter - you can go around the cycle 
indefinitely. I can't remember all the details of the proof, but for
acyclic graphs "as often as needed" is once. 

    I *think* this is right:
    
    Make boolean matrix A where A(i, j) is true if nodes i and j are
    directly connected.  Then start taking "powers" of the matrix:
    A * A will have a value of true for each i, j when there is a path
    of length 2 from i to j.  Keep going, i.e. make A^3, A^4, etc. until
    A^n is completely false.  Then (n-1) will be the diameter of the graph.
    
    Note that in multiplying the matrices, "or" is substituted for
    addition, and "and" for multiplication.j
    
    
    							Mark

	Lynn's right.   This amazingly simple algorithm is only guaranteed
to work for connected, acyclic graphs (aka: trees).   You *can* define the
concept of distance on a connected graph with cycles (just the length of 
*shortest* route between two points).   So you *can* define the concept of
diameter for such a graph.   The problems come in applying the algorithm
suggested.

	Peter asked for a counter-example.   Here's the smallest:

	A--D
	|\ |
	| \|
	C--B

	Suppose you start from point A.   Then since all other points are
distance 1 from A, you might pick B for the second point.   Similarly,
you might select A again for your third point.   You could iterate back
and forth between A&B all day at this game.   And yet the diameter is 2, as
exhibited by CD.

	Why does the algorithm work for trees?

-------------------------------------------------------------------------------

Proof:

	Let A,B,C be the first, second and third points visited.   (ie: it
is hypothesized that C is one end of a diameter.)   Since the graph is a
tree, BA & BC are unique paths.   Let K be the "fork in the road" between
BA & BC.

	What we will prove is that for every path in the graph, there is
a path with C as an end-vertex which is at least as long.   In particular,
therefore, C must be one end of some diameter, and any other point of maximal
distance from C will be the other end of a diameter.   

	So define various arbitrary points.   Let D hang off AK, let E 
hang off BK, let F hang off CK.   So we get a structure looking sort of like 
this:

		A
		|
		*--D
		|
		K--*--C
		|  |
	     E--*  F
		|
		B

where the links aren't meant to represent single edges here but paths.
Various of the points may coincide here (eg: A with K with C) but that doesn't
matter:  it just means that the associated path will have length 0.

	Any path through K is of one of the following typical forms:
DE or DF or EF.

|DE| = |DK| + |KE| =< |CK| + |KE| (since C is at least as far from B as D is)
= |EC|

|DF| =  |DK| + |KF| =< |DK| + |KC| (for the same general reason as above)
= |DC|

|EF| = |EK| + |KF| =< |EK| + |KC| (as above) = |EC|.

	Any path *not* through K is of one of the following typical forms:
DD', EE', FF' (where D',E',F' are defined in the obvious way, as random
additional points hanging off AK,BK,CK respectively.)

|DD'| =< |DK|+|KD'| =< |DK|+|KC| (as above) = |DC|

|FF'| =< |FK|+|KF'| =< |FK|+|KC| (as above) = |FC|

|EE'| (is the slightly complicated one).   Let M be the fork in the road
between EB and EK.

		A
		|
		*--D
		|
		K--*--C
		|  |
	     E--M  F
		|
		B

	Then E' will be hanging off one of EM or BM or KM.   Wlog (swap E with
E' if necessary) E' does not hang off KM.   In the other two cases:
|EE'| =< |EM|+|ME'| =< |CM|+|ME'| (since C is at least as far from B as E is)
= |CE'| (since the path from C to E' must pass through M in each of the two
cases.)

	Thus every path is shorter than some path involving C, and we have our
result.

Cheers,
Andrew.

   If you are after a "practical" approximation of the diameter of
   the graph, you can adapt techniques that are used in finite element
   analysis to reduce the bandwidth and profile of the matrices
   involved.

    Finite element analysis is a numerical way of approximating the
    solution to boundary problems for the complicated kinds of geometries
    that occur in the real world where no closed form solutions exist.
    The geometry is descretized into elements and "simple" functions
    are postulated to exist on each element.  By piecing together
    the patchwork of elements, one can constrain the weighted combination
    of all the functions on each element to satisfy the boundary
    value problem in some appropriate sense, such as weighted residuals.

    This leads to large systems of simulataneous equations for linear
    problems, as there can be thousands of elements involved.  But
    not every element touches every other, only their neighbors.
    This means the system of equations has a very sparse matrix.

    Here is where graph theory comes in.  What one wants to do is
    permute the rows and columns of the matrix to obtain a "banded"
    matrix since such matrices can pretty clearly be solved in much
    less time than an arbitrary dense one.  That is, a dense N by N
    matrix is an O(N^3) problem to solve, while a banded matrix is
    an O(N*B^2) problem, where B is the bandwidth.

    If you look at only the topology of the elements, you have a
    graph.

    One way to reduce the profile is to introduce a so-called "level
    structure" on the graph:  choose a root node (heuristically
    one with minimal "degree", the number of neighbors.)  That node
    is in level 0.  Next assign neighbors of that node to level 1.
    Assign neighbors of those that are not in level 0 or 1 to level 2.
    And so on.

    The idea should be clear and is easy to visualize for a planar
    graph that might arise in a 2 dimensional mesh.

    The "length" of the resulting set of levels is an approximation
    of the diameter.  Note that this works for cyclic or acyclic
    graphs.  To iteratively improve this first approximation,
    for each of the nodes in the last level, recompute the level
    structure rooted at that node and if you get a longer one, take
    that as a new approximation and iteratively try again.

    This never loops, and for finite element problems rarely ever
    requires more than 2 iterations.

    The resulting length of level structure is called the pseudo-diameter.
    The longer the level structure is, the narrower the bandwidth
    of matrix there will be, so this is a good strategy.

    To use this (easily computed) level structure, one renumbers the
    nodes in the graph using variations on the following idea.
    Number the root node zero.  Then sort the nodes in the next level
    by degree, assigning them numbers in ascending order by degree.
    (ties are broken arbitrarily.)  Next, for each node in that level,
    by degree, number its neighbors (not already numbered) by degree.
    When all nodes in a given level are processed this way, go
    to the next level and repeat.  This tends to reduce the
    bandwidth of the resulting matrix.  Depending on how the 
    matrix is stored, there are ways to further reduce the profile
    (average bandwidth) as well as the maximum bandwidth.

    The origional algorithm was due to Cuthill and McGee.

    While I know this is not provably optimal, it is very fast to
    compute and the level structure idea is probably useful to
    know about.

    This is from memory, though I've coded such stuff while playing
    around with the techniques (for simple 2D problems.)

    Such algorithms are called "minimum degree" algorithms in the
    literature.

    - Jim

>   If you are after a "practical" approximation of the diameter of
>   the graph, you can adapt techniques that are used in finite element
>   analysis to reduce the bandwidth and profile of the matrices
>   involved.

	It surprises me that the algorithm you propose doesn't take
advantage of the 2D or 3D nature of the object your trying to model.   I
would have thought that would be a very powerful constraint that finite
element analysts in reality would use to minimize the bandwidth, in
preference to this generic algorithm.

>    This never loops, and for finite element problems rarely ever
>    requires more than 2 iterations.

	I wondered, are you *guaranteed* to get the proper diameter after
doing a full search of all last-level nodes, with any number of iterations?

	The following little graph never yields the true diameter, if you
start at the vertex labeled 0.   And yet the diameter of the graph is 4,
from the leftmost to the rightmost vertex.

	     +--0--+
	     |     |
	  +--1     1--+
	  2  |     |  2
	  +--2     2--+
	     |     |
	     +--3--+

	In fact, using this sort of model, it's easy to build finite element
graphs of a plane surface, such that d ~= [_/3*p], where d is the diameter,
and p is is the pseudo-diameter.   I guess if you use this algorithm, to
get the diameter of something like an ellipse, you should apply the additional
heuristic of starting at one end of the major axis, rather than at one end of 
the minor one!

	The limit for abstract graphs is d = 2p-2.   This is attainable by
just changing the lengths of the edges in the little graph above, and is
clearly the best bound possible. 

Cheers,
Andrew.

>	It surprises me that the algorithm you propose doesn't take
>advantage of the 2D or 3D nature of the object your trying to model.   I
>would have thought that would be a very powerful constraint that finite
>element analysts in reality would use to minimize the bandwidth, in
>preference to this generic algorithm.

It really simplifies life to have a generic algorithm because the
finite element meshes are not made only of regular arrays of quads
or triangles, but arbitrary mixtures.  So it's just as easy to
have a general graph - for my 2D meshes I've often used a "quad edge"
data structure like the one in the Delaunay triangulation program
I once posted.

>    This never loops, and for finite element problems rarely ever
>    requires more than 2 iterations.

>	I wondered, are you *guaranteed* to get the proper diameter after
>doing a full search of all last-level nodes, with any number of iterations?

It's only a heuristic since the exact solution is uneconomical to
calculate.

>	In fact, using this sort of model, it's easy to build finite element
>graphs of a plane surface, such that d ~= [_/3*p], where d is the diameter,
>and p is is the pseudo-diameter.   I guess if you use this algorithm, to
>get the diameter of something like an ellipse, you should apply the additional
>heuristic of starting at one end of the major axis, rather than at one end of 
>the minor one!>>

This is probably true, but in practice it turns out that the
technique works well. Also, the actual diameter is not the goal -
the goal is to eventually number nodes for a narrow profile banded
matrix, but a level structure as deep as the true diameter is a good
starting place.

It looks neat to plot pictures of the N by N matrix before and
after various kinds of renumbering - you see it get stuff close to
the diagonal when things are working.

It also looks neat to see the level structure sweep thru the mesh
on a graphics display.  In fact, this level structure is used in
so-called "fontal solution methods" which page in parts of the
matrices for really *huge* problems.  ANSYS uses that kind of solver.

(I like seeing stuff happen more than proving theorems...)

- Jim

> (I like seeing stuff happen more than proving theorems...)

	To your credit.   I am yet to arrive at this useful viewpoint of the
world.   :-)

Cheers,
Andrew.

Re .7:

  Interestingly, Alan George discovered that the ordering obtained by 
  reversing the Cuthill-McKee (not McGee) ordering is much better in 
  reducing the profile of a matrix than the Cuthill-McKee ordering. The
  Reverse Cuthill-McKee (RCM) ordering leaves the bandwidth of the matrix 
  unchanged. RCM is currently the most popular reordering scheme for 
  reducing the profile of a matrix.

  chandrika