***************************************************************************
COMBINATORICA UPDATE
Volume 1 - 7/17/90
Steven Skiena
Department of Computer Science
State University of New York
Stony Brook, NY 11794
(516)-632-9026
skiena@sbcs.sunysb.edu
***************************************************************************
Contents
========
1. Introduction to this newsletter
2. Version 0.6 released
3. "Implementing Discrete Mathematics" released
4. Future developments
5. T-shirts, anyone?
6. diffs between version 0.5 and 0.6
***************************************************************************
Introduction
This is the first installment of "Combinatorica Update", a very
occasional newsletter informing you of new releases of Combinatorica,
a combinatorics and graph theory package running under Mathematica.
To be placed on the mailing list for "Combinatorica Update", send email
to skiena@sbcs.sunysb.edu. There are currently about 85 subscribers.
In addition to announcing software updates, I would like to
keep users of the package informed about what other people are doing.
It seems that people are using Combinatorica for both teaching and research.
We would like to know what you are doing with the package, as well as what
you would like in such a system. With such feedback, we can provide better
service as well as satisfy our curiousity.
***************************************************************************
Version 0.6 Released
The latest version of Combinatorica.m, with improvements to
Isomorphism, DeBruijnSequence, VertexColoring, PlanarQ, and FindCycle,
is available by anonymous ftp from cs.sunysb.edu. The differences between
version 0.5 and version 0.6 are included at the end of this newsletter,
so the Unix utility patch can be used to update the source without ftp.
Included with the ftp distribution of version 0.6 is a collection of
twenty special graphs, exactly the special graphs which appear as examples in
the book. These are written in SPREMB format and are readable with ReadGraph.
These include the Peterson, Grotztsch, Coxeter, and Heawood graphs, as well as
the icosahedron and dodecahedron. We intend that the next release
will include a much larger collection of graphs.
***************************************************************************
"Implementing Discrete Mathematics" Released
I am proud to announce that my book, "Implementing Discrete
Mathematics: Combinatorics and Graph Theory with Mathematica", was
released June 4, 1990 by the Advanced Book Division, Addison-Wesley,
Redwood City, CA (ISBN 0-201-50943-1). Despite what you may have heard,
Tom Cruise is not slated to play Paul Erdos in the movie version.
The book is the best guide to Combinatorica, and is recommended
for all serious users, their libraries, students, friends, and relatives.
Of course, the package is available by anonymous ftp from cs.sunysb.edu
and comes with sufficient documentation to get started without the book.
The book can be ordered by calling 1-800-447-2226.
The text of Addison-Wesley's press release follows:
=======================================================================
"Implementing Discrete Mathematics: Combinatorics and Graph Theory with
Mathematica" is both a reference on combinatorial algorithms and a laboratory
for experimentation in discrete mathematics. Full implementations, in the
Mathematica programming language, of over 230 combinatorial algorithms are
included. These programs facilitates experimentation in discrete mathematics
by computer, enabling the reader to answer questions not mentioned in the book.
The functions themselves provide excellent examples of Mathematica programming,
and a brief guide to Mathematica is included.
The book concentrates on two distinct areas in discrete mathematics:
combinatorics and graph theory. The first section provides algorithms
for generating combinatorial structures such as permutations, partitions,
and Young tableaux, and studies various aspects of these structures. The
rest of the book concentrates on graph theory, including techniques for
constructing and displaying a wide variety of different graphs and computing
graph invariants. "Implementing Discrete Mathematics: Combinatorics and
Graph Theory with Mathematica" is a comprehensive exploration of discrete
mathematics well-suited for independent study or as a supplement for courses
in combinatorics, graph theory, algorithms, or programming.
Highlights of this book:
* The book and associated software extends Mathematica into a unique tool for
experimenting with discrete structures.
* It is a complete reference on over 230 combinatorial algorithms.
* Hundreds of interesting examples of this software in action are included
in the book, along with problems suggesting new areas to investigate.
* The full implementation of and documentation for this package is included in
the book, which is available electronically for all versions of Mathematica.
***************************************************************************
Future developments
Our long range goal is to create a portable, high-performance
library of combinatorial algorithms in a language such as C++, so that
the routines can be called from both Mathematica and other programs.
Version 2 of Mathematica will incorporate MathLink, a new communication
standard, and we expect that implementing certain algorithms in C++
will lead to vast improvements in the performance of Combinatorica.
Further, we anticipate that this portable library will also be useful in
non-Mathematica applications. Combinatorica can be viewed as a prototype
of this library.
This library is currently in the planning stage, and needs your
feedback to proceed. What functions/algorithms would you want in such
a library? What potential applications of such a library might you
envision?
***************************************************************************
T-shirts, anyone?
Combinatorica got its start at Apple Computer which, it is
said, is a t-shirt company fronting as a computer company. Coming from
this tradition, it seems natural to market a line of Combinatorica t-shirts,
and I am prepared to start a subsidiary (Graph Products, Inc.) to do so.
Actually, I thought that was a great name for a company, and the idea of
t-shirts came later.
As I envision this, each t-shirt will contain a drawing of one
or more graphs, probably in color. What better way to tell the world
that you are a graph theorist? Since this project is still in the early
planning stage, it is premature to give a price, but all proceeds (if any)
will go to some worthy cause.
Anyone who submits a graph which I eventually turn into a t-shirt
will receive a free shirt. The only rule is that the graph must be
constructed and drawn with Combinatorica, like the pictures at the front
of each chapter in the book. Also, any ideas for pretty graphics will be
distributed with acknowledgments in this forum.
As a start, try the following graphics, although the ones in the
book are better:
ShowGraph[ GraphProduct[Star[7], Path[4]] ];
ShowGraph[ LineGraph[ GridGraph[4,4] ] ];
ShowGraph[ GraphProduct[Star[6], Cycle[5]] ];
***************************************************************************
Patches - version 0.5 to version 0.6
*************************** cut here **************************************
7c7
< Version 0.5 5/9/90 Beta Release
---
> Version 0.6 6/11/90 Beta Release
1801c1801
< {x,y} = v [[i]];
---
> {x,y} = Chop[ v [[i]] ];
2298,2305c2298,2308
< Block[{eg=Edges[g],eh=Edges[h]},
< Backtrack[
< Equivalences[g,h],
< (IdenticalQ[InduceSubgraph[g,Range[Length[#]]],
< InduceSubgraph[h,#] ] &&
< !MemberQ[Drop[#,-1],Last[#]])&,
< (IsomorphismQ[g,h,#])&,
< flag
---
> Block[{eg=Edges[g],eh=Edges[h],equiv=Equivalences[g,h]},
> If [!MemberQ[equiv,{}],
> Backtrack[
> equiv,
> (IdenticalQ[InduceSubgraph[g,Range[Length[#]]],
> InduceSubgraph[h,#] ] &&
> !MemberQ[Drop[#,-1],Last[#]])&,
> (IsomorphismQ[g,h,#])&,
> flag
> ],
> {}
2337,2340c2340,2341
< FindCycle[g_Graph,flag_:Undirected] := FindCycle[g,flag,1] /; V[g] >= 2
<
< FindCycle[g_Graph,flag_,start_Integer] :=
< Block[{edge,n=V[g],x,queue={start},ex,cycle={},parent,next},
---
> FindCycle[g_Graph,flag_:Undirected] :=
> Block[{edge,n=V[g],x,queue,ex,cycle,parent,next={{1}}},
2342,2347c2343,2349
< parent=Table[n+1,{n}];
< parent[[start]] = 0;
< While[ queue != {},
< {x, queue} = {First[queue], Rest[queue]};
< If [x === {},
< cycle = Drop[cycle,-1],
---
> parent=Table[n+1,{n}];
> While[next != {},
> queue = First[next];
> parent[[ First[queue] ]] = 0;
> cycle = {};
> While[queue != {},
> {x, queue} = {First[queue], Rest[queue]};
2353c2355
< queue = Join[ex,{{}},queue];
---
> queue = Join[ex,queue];
2356c2358,2359
< ]
---
> ];
> next = Position[parent,n+1]
2358,2361c2361
< If [(next = Position[Drop[parent,start],n+1]) == {},
< {},
< FindCycle[g,flag,start+next[[1,1]]]
< ]
---
> {}
2366,2367c2366,2368
< While[(i=parent[[i]]) != s, PrependTo[lst,i] ];
< PrependTo[lst,i]
---
> While[!MemberQ[lst,(i=parent[[i]])], PrependTo[lst,i] ];
> PrependTo[lst,i];
> Take[lst, Flatten[Position[lst,i]]]
2446c2447
< DeBruijnSequence[alph_List,n_Integer?Positive] :=
---
> DeBruijnSequence[alph_List,n_Integer] :=
2466c2467,2469
< ]
---
> ] /; n>=2
>
> DeBruijnSequence[alph_List,n_Integer] := alph /; n==1
2716c2719
< If [color[[i]]!=0, l[[i]] = 0],
---
> If [color[[i]]!=0, l[[i]] = -1],
2998c3001
< PlanarQ[g_Graph] := False /; (M[g] > 3 V[g]-6)
---
> PlanarQ[g_Graph] := False /; (M[g] > 3 V[g]-6) && (V[g] > 2)
3033c3036
< Select[ToUnorderedPairs[g],
---
> Select[ToOrderedPairs[g],
3035c3038
< Map[Sort, Partition[Append[cycle,First[cycle]],2,1]]
---
oaK Partition[Append[cycle,First[cycle]],2,1]