       Re: graphs

• To: mathgroup at smc.vnet.net
• Subject: [mg60983] Re: [mg60946] graphs
• From: "David Park" <djmp at earthlink.net>
• Date: Thu, 6 Oct 2005 04:08:25 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

```Leigh,

1) Do add all the set of diagonal edges to an n x n graph you could use...

g2 = g;
Do[If[Mod[i, n] != 0, g2 = AddEdges[g2, {i, i + n + 1}]],
{i, 1, n^2 - (n + 1)}]

3) To better show all the vertex labels use PlotRange -> All.

ShowGraph[g2,
VertexNumber -> True,
PlotRange -> All]

2) To retain the numbering of the vertices don't remove the vertices. Just
remove the edges that lead to the vertices.

You might want to look at the Combinatorica Graphics package at my web site
below. It gives more control on the rendering of the graph. You could, for
example, use circles containing the vertex numbers at the vertices. I think
you could suppress the display of some vertices. You could also use directed
edges with the arrowheads in the center instead of at the end of the edges.

The Combinatorica package is poorly documented.

David Park

From: leigh pascoe [mailto:leigh at cephb.fr]
To: mathgroup at smc.vnet.net

Dear Mathgroup,

I am using Combinatorica to study a board game represented by a graph.
The nxn graph can be created using

<<DiscreteMath`Combinatorica`
n=4;
g=GridGraph[n,n];
ShowGraph[g,VertexNumber\[Rule]True]

The vertices of the graph are numbered from the bottom left in rows,
hence to refer to the matrix (row,column) location of a vertex we define

cellindex[i_,j_]:=n*(n-i)+j;

Now to complete the graph we draw edges from cell(i,j) to cell(i-1,j+1),
where these vertices exist. Here is an example for the 4x4 case

ShowGraph[
g,{{cellindex[2,1],cellindex[1,2]},{cellindex[2,2],
cellindex[1,3]},{cellindex[2,3],cellindex[1,4]},{cellindex[3,1],
cellindex[2,2]},{cellindex[3,2],cellindex[2,3]},{cellindex[3,3],
cellindex[2,4]},{cellindex[4,1],cellindex[3,2]},{cellindex[4,2],
cellindex[3,3]},{cellindex[4,3],cellindex[3,4]}}],
VertexNumber\[Rule]True]

This works ok, but I now have several problems: I would like to write
the above statement as an implied loop for a general nxn gridgraph. I
can't seem to get the correct syntax for this. Can anyone help me?

Then I would like to define some functions on the graph, referring to
the vertices by there grid position. However when I add or delete a
vertex, the numbering on the graph changes. I would like to be able
mutate the graph, but still be able to address vertices by the original
labels, as defined by the cellindex[i,j] function (or any other for that
matter. Any suggestions?

A third problem (bug?) is that in the ShowGraph command the vertex label
on the left loses the left most digit(s) when displayed, as shown above.
I just note that here in case someone at Wolfram wants to fix it.

The documentation for this package is also rather (very) limited. I
bought the book on the package, which gives some more details, but many
functions still remain undocumented. Does anyone know a better source?