Autocad LT and the Coxeter Graph

Author

Ed Pegg Jr.
Wolfram Research, Inc.
April 8, 2003

Implementation

Turning an Autocad object into a Mathematica object requires a small amount of effort.  The easiest way is to save Autocad line art as DXF, Import as DXF into Mathematica, and then to strip the zeroes.  For this demonstration, I made a nice embedding of the Coxeter Graph.  More information on this object can be seen at http://mathworld.wolfram.com/CoxeterGraph.html.

coxeter  =  Import["C:\\coxeter.dxf", "DXF"];

There are two equivalent ways of converting the 3D DXF file into a 2D object, both involving stripping the zeroes.  The first method involves pattern matching.

Show[
        Graphics[Map[Last, First[coxeter]] /. {a_, b_, c_} ->  {a, b}], 
        AspectRatio -> Automatic];

A faster method is to use the Drop function, mapped at the appropriate level.

Show[
        Graphics[
          Map[Drop[#, -1] &, Map[Last, First[coxeter]], {-2}]], 
        AspectRatio ->  Automatic];

Next, we'll employ some useful packages.  The Graphs package is by Eric Weisstein, and can be found at http://library.wolfram.com/infocenter/MathSource/4775/ or http://mathworld.wolfram.com/packages/.

<< DiscreteMath`Combinatorica`;
<< Graphs`;

After loading the packages, the line object can be converted into a Combinatorica object.  The .1 at the end cleans up some vertices that are incorrectly separated.  If removed, the graph will have too many vertices.

temp  = 
      LinesToGraph[
        Graphics[
          Map[Drop[#, -1] &, 
            Map[Last, First[coxeter]], {-2}]],  .1]

The way Combinatorica programming is set up, in an undirected graph, the lines must always be set up as {{lesser, greater}}.  The following code cleans that up.

CoxeterG  =  
        Graph[Map[
            Sort, InputForm[temp][[1, 1]], {2}], InputForm[
              temp][[1, 2]]];

It is now a proper Mathematica object.

ShowGraph[CoxeterG];

Various Mathematica tests can now be applied.

HamiltonianQ[CoxeterG] // Timing

IsomorphicQ[CoxeterG, CoxeterGraph2] // Timing

ShowGraphArray[{CoxeterGraph2,  
          CoxeterG}, 
VertexStyle -> Disk[ .05], 
        VertexColor -> Red];

InputForm[CoxeterG]