*************************************************************************** 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]