(***********************************************************************
Mathematica-Compatible Notebook
This notebook can be used on any computer system with Mathematica 4.0,
MathReader 4.0, or any compatible application. The data for the notebook
starts with the line containing stars above.
To get the notebook into a Mathematica-compatible application, do one of
the following:
* Save the data starting with the line of stars above into a file
with a name ending in .nb, then open the file inside the application;
* Copy the data starting with the line of stars above to the
clipboard, then use the Paste menu command inside the application.
Data for notebooks contains only printable 7-bit ASCII and can be
sent directly in email or through ftp in text mode. Newlines can be
CR, LF or CRLF (Unix, Macintosh or MS-DOS style).
NOTE: If you modify the data for this notebook not in a Mathematica-
compatible application, you must delete the line below containing the
word CacheID, otherwise Mathematica-compatible applications may try to
use invalid cache data.
For more information on notebooks and Mathematica-compatible
applications, contact Wolfram Research:
web: http://www.wolfram.com
email: info@wolfram.com
phone: +1-217-398-0700 (U.S.)
Notebook reader applications are available free of charge from
Wolfram Research.
***********************************************************************)
(*CacheID: 232*)
(*NotebookFileLineBreakTest
NotebookFileLineBreakTest*)
(*NotebookOptionsPosition[ 32845, 919]*)
(*NotebookOutlinePosition[ 33564, 944]*)
(* CellTagsIndexPosition[ 33520, 940]*)
(*WindowFrame->Normal*)
Notebook[{
Cell[CellGroupData[{
Cell["CombinatoricaPlots Tutorial", "Title"],
Cell["\<\
David Park
djmp@earthlink.net
http://home.earthlink.net/~djmp/\
\>", "Subtitle"],
Cell["\<\
Install the CombinatoricaPlots package in AddOns/ExtraPackages/DiscreteMath \
directory. It is available at my web site above. CombinatoricalPlots \
automatically loads Combinatorica.\
\>", "Text"],
Cell[BoxData[{
\(\(<< DiscreteMath`CombinatoricaPlots`;\)\), "\n",
\(\(<< Graphics`Colors`;\)\)}], "Input",
CellLabel->"In[1]:="],
Cell[CellGroupData[{
Cell["History of Changes", "Section"],
Cell["\<\
Jan 2000: Individual position of labels, edge labels, midpoint arrows.
Feb 1, 2000: MidpointArrows out, ArrowheadPosition added.
Feb 6, 2000: Self-loops added.\
\>", "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell["Introduction", "Section"],
Cell[TextData[{
"The Combinatorica package by Steven Skiena is one of the popular additions \
to ",
StyleBox["Mathematica",
FontSlant->"Italic"],
". However it was done with one of the earlier versions of ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" and the graphical capability of the ShowGraph statement is much more \
limited that the rest of the package. The CombinatoricaPlots package and its \
PlotGraph statement greatly extends the graphical capability of \
Combinatorica."
}], "Text"],
Cell["\<\
ShowGraph had a limititation which cuts off some of the labels if a larger \
text size has been specified by the user. This has been fixed. \
CombinatoricaPlots allows, labeling of vertices, labeling of edges, and \
directed edges in any combination. There is also an option for putting the \
arrowheads at any point along directed edges. Self-loops can also be \
displayed. The graphical styles for all elements can be specified and the \
position of the labels can also be closely specified.\
\>", "Text"],
Cell[TextData[{
"In the initial version the CombinatoricaPlots package, graphs were \
converted by NormalizeVertices before plotting. Why did I do this? - Because \
Skiena did it in his ShowGraph statement. Why did he do it? My guess is that \
the version of ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" in use at that time did not have the option ",
Cell[BoxData[
\(PlotRange \[Rule] All\)]],
". So he had to fit all plots into a fixed space which made some allowance \
for vertex labels. NormalizeVertices scales all vertex locations so they fit \
into a unit square with one corner at the origin. But this is no longer \
necessary and it is confusing since vertices no longer appear at the \
locations initially specfied for the graph. In this new version, \
NormalizeVertices is no longer used, and the graphical coordinates of \
vertices are the same as their specification in the Graph structure."
}], "Text"],
Cell["\<\
This tutorial show how to plot many kinds of graphs using the combined \
features of Combinatorica and CombinatoricaPlots. In some of the examples, I \
have used colored text in the PlotGraph statement to highlight a feature \
being added to the plot. You do not have to use colored text in your own plot \
statements.\
\>", "Text"],
Cell[TextData[{
"I am not myself an expert on Combinatorica or combinatorics. I wish I was! \
I did the CombinatoricaPlots package because I desired better graph plotting \
facilities so I can learn more about it myself. It is a pity that Skiena's \
book ",
StyleBox["Implementing Discrete Mathematics: Combinatorics and Graph Theory \
with Mathematica",
FontSlant->"Italic"],
StyleBox[" is no longer in print. It is an important aid in using the \
Combinatorica package and contains the algorithms for all the routines.",
FontVariations->{"CompatibilityType"->0}]
}], "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell["Names and Information", "Section"],
Cell[CellGroupData[{
Cell[BoxData[
\(\(?DiscreteMath`CombinatoricaPlots\)\)], "Input",
CellLabel->"In[3]:="],
Cell[BoxData[
\(" CombinatoricaPlots adds more generalized plot routines to the \
Combinatorica package. PlotGraph replaces the old ShowGraph. It corrects an \
error that cuts off some of the labels. It allows plots to be both labeled \
and directed. It is possible to label edges as well as vertices. Graphics \
directives may be specified for the vertices, edges and labels. Directed \
edges may have the arrows at any point along the edge. Self-loops may be \
included in the plot."\)], "Print",
CellLabel->"From In[3]:="]
}, Open ]],
Cell[CellGroupData[{
Cell[BoxData[
\(\(?DiscreteMath`CombinatoricaPlots`*\)\)], "Input",
CellLabel->"In[4]:="],
Cell["\<\
ArrowheadPosition EdgeLabelTextOptions VertexDirectives
DrawGraph GraphPlottingOptions VertexLabelOffset
EdgeDirectives PlotGraph VertexLabels
EdgeLabelOffset SelfLoops VertexLabelTextOptions
EdgeLabels\
\>", "Print",
CellLabel->"From In[4]:="]
}, Open ]]
}, Closed]],
Cell[CellGroupData[{
Cell["Plotting Simple Graphs", "Section"],
Cell["\<\
To plot a graph, just use PlotGraph instead of ShowGraph. Here are some \
standard graphs from Combinatorica.\
\>", "Text"],
Cell[BoxData[
\(\(PlotGraph[CompleteGraph[5]];\)\)], "Input",
CellLabel->"In[5]:="],
Cell[BoxData[
\(\(PlotGraph[CompleteGraph[3, 3, 3]];\)\)], "Input",
CellLabel->"In[6]:="],
Cell[BoxData[
\(\(PlotGraph[GridGraph[3, 4]];\)\)], "Input",
CellLabel->"In[7]:="],
Cell[BoxData[
\(\(PlotGraph[Star[6]];\)\)], "Input",
CellLabel->"In[8]:="]
}, Closed]],
Cell[CellGroupData[{
Cell["GraphPlottingOptions", "Section"],
Cell["\<\
The option GraphPlottingOptions allows you to specify overall plotting \
options for the graph. This adds a background to the plot, adds a plot label, \
changes the font, and specifies the size of the image.\
\>", "Text"],
Cell[BoxData[
RowBox[{
RowBox[{"PlotGraph", "[",
RowBox[{\(CompleteGraph[5]\), ",", "\[IndentingNewLine]",
StyleBox[\(GraphPlottingOptions \[Rule] {Background \[Rule] Linen,
PlotLabel \[Rule] "\",
ImageSize \[Rule] 350, \
TextStyle \[Rule] {FontFamily \[Rule] "\"}}\),
FontColor->RGBColor[1, 0, 0]]}], "]"}], ";"}]], "Input",
CellLabel->"In[9]:="]
}, Closed]],
Cell[CellGroupData[{
Cell["Vertex Directives and Vertex Labels", "Section"],
Cell["This makes the vertices larger and colors them blue.", "Text"],
Cell[BoxData[
RowBox[{
RowBox[{"PlotGraph", "[",
RowBox[{\(CompleteGraph[5]\), ",", "\[IndentingNewLine]",
StyleBox[\(VertexDirectives \[Rule] {AbsolutePointSize[6], Blue}\),
FontColor->RGBColor[1, 0, 0]]}], "]"}], ";"}]], "Input",
CellLabel->"In[10]:="],
Cell["This puts labels on the vertices, using the vertex numbers.", "Text"],
Cell[BoxData[
RowBox[{
RowBox[{"PlotGraph", "[",
RowBox[{\(CompleteGraph[5]\), ",",
"\[IndentingNewLine]", \(VertexDirectives \[Rule] \
{AbsolutePointSize[6], Blue}\), ",", "\[IndentingNewLine]",
StyleBox[\(VertexLabels \[Rule] True\),
FontColor->RGBColor[1, 0, 0]]}], "]"}], ";"}]], "Input",
CellLabel->"In[11]:="],
Cell["\<\
The default vertex label offset has been used. But it didn't work too well \
for vertices 1 and 5. We can change the vertex label offsets using the \
VertexLabelOffset option, but that will probably mess up vertices 2 and 3. \
There are two solutions. The first is to put a background color on the labels \
to make them stand out better.\
\>", "Text"],
Cell[BoxData[
RowBox[{
RowBox[{"PlotGraph", "[",
RowBox[{\(CompleteGraph[5]\), ",",
"\[IndentingNewLine]", \(VertexDirectives \[Rule] \
{AbsolutePointSize[6], Blue}\), ",",
"\[IndentingNewLine]", \(VertexLabels \[Rule] True\), ",",
"\[IndentingNewLine]",
StyleBox[\(VertexLabelTextOptions \[Rule] {Background \[Rule]
Gold}\),
FontColor->RGBColor[1, 0, 0]]}], "]"}], ";"}]], "Input",
CellLabel->"In[12]:="],
Cell["\<\
You could also actually make the labels the vertices by placing them right on \
top the vertices.\
\>", "Text"],
Cell[BoxData[
RowBox[{
RowBox[{"PlotGraph", "[",
RowBox[{\(CompleteGraph[5]\), ",",
"\[IndentingNewLine]", \(VertexLabels \[Rule] True\), ",",
"\[IndentingNewLine]",
StyleBox[\(VertexLabelOffset \[Rule] {0, 0}\),
FontColor->RGBColor[1, 0, 0]], ",", "\[IndentingNewLine]",
StyleBox[\(VertexLabelTextOptions \[Rule] {Background \[Rule]
Gold}\),
FontColor->RGBColor[1, 0, 0]]}], "]"}], ";"}]], "Input",
CellLabel->"In[13]:="],
Cell["\<\
A second solution is to list the vertex labels explicitly, and whenever we \
want a different offset, we add it to the label specification. Here, the \
offsets for vertices 1 and 5 have been individually specified.\
\>", "Text"],
Cell[BoxData[
RowBox[{
RowBox[{"PlotGraph", "[",
RowBox[{\(CompleteGraph[5]\), ",",
"\[IndentingNewLine]", \(VertexDirectives \[Rule] \
{AbsolutePointSize[6], Blue}\), ",", "\[IndentingNewLine]",
StyleBox[\(VertexLabels \[Rule] {{1, {\(-2\), \(-1\)}}, 2, 3,
4, {5, {\(-2\), \(-1\)}}}\),
FontColor->RGBColor[1, 0, 0]]}], "]"}], ";"}]], "Input",
CellLabel->"In[14]:="]
}, Closed]],
Cell[CellGroupData[{
Cell["Directed Graphs", "Section"],
Cell["To plot the edges as arrows, use the Directed option.", "Text"],
Cell[BoxData[
RowBox[{
RowBox[{"PlotGraph", "[",
RowBox[{\(OrientGraph[Wheel[4]]\), ",", "\[IndentingNewLine]",
StyleBox[\(Directed \[Rule] True\),
FontColor->RGBColor[1, 0, 0]]}], "]"}], ";"}]], "Input",
CellLabel->"In[15]:="],
Cell["\<\
Often the directed edges will look better with the arrowheads at midpoint.\
\>", "Text"],
Cell[BoxData[
RowBox[{
RowBox[{"PlotGraph", "[",
RowBox[{\(OrientGraph[Wheel[4]]\), ",",
"\[IndentingNewLine]", \(Directed \[Rule] True\), ",",
"\[IndentingNewLine]",
StyleBox[\(ArrowheadPosition \[Rule] 1/2\),
FontColor->RGBColor[1, 0, 0]]}], "]"}], ";"}]], "Input",
CellLabel->"In[16]:="],
Cell["\<\
The tips of the arrowheads can be put at any fractional position of the edge \
from 0.13 to 1.\
\>", "Text"],
Cell[BoxData[
RowBox[{
RowBox[{"PlotGraph", "[",
RowBox[{\(OrientGraph[Wheel[4]]\), ",",
"\[IndentingNewLine]", \(Directed \[Rule] True\), ",",
"\[IndentingNewLine]",
StyleBox[\(ArrowheadPosition \[Rule] 0.8\),
FontColor->RGBColor[1, 0, 0]]}], "]"}], ";"}]], "Input",
CellLabel->"In[17]:="],
Cell["\<\
The edges above were actually plotted as an Arrow and a Line, joined at the \
arrow tip. Arrow plotting options can be passed to the Arrow routine by \
giving them as the right hand side of the Directed option.\
\>", "Text"],
Cell[BoxData[
RowBox[{
RowBox[{"PlotGraph", "[",
RowBox[{\(OrientGraph[Wheel[4]]\), ",", "\[IndentingNewLine]",
StyleBox[\(Directed \[Rule] {HeadCenter \[Rule] 1/3}\),
FontColor->RGBColor[1, 0, 0]], ",",
"\[IndentingNewLine]", \(ArrowheadPosition \[Rule] 1/2\)}], "]"}],
";"}]], "Input",
CellLabel->"In[18]:="],
Cell["This gives a more finished plot.", "Text"],
Cell[BoxData[
\(\(PlotGraph[
OrientGraph[
Wheel[4]], \[IndentingNewLine]Directed \[Rule] {HeadCenter \[Rule]
1/3}, \[IndentingNewLine]ArrowheadPosition \[Rule]
1/2, \[IndentingNewLine]VertexDirectives \[Rule] {AbsolutePointSize[
6], Blue}, \[IndentingNewLine]VertexLabelOffset \[Rule] {2.5,
0}, \[IndentingNewLine]VertexLabels \[Rule] {1, 2, {3, {0, 2}},
4}, \[IndentingNewLine]VertexLabelTextOptions \[Rule] {Background \
\[Rule] Gold}, \[IndentingNewLine]GraphPlottingOptions \[Rule] {Background \
\[Rule] MintCream, PlotLabel \[Rule] "\",
ImageSize \[Rule] 350}];\)\)], "Input",
CellLabel->"In[19]:="]
}, Closed]],
Cell[CellGroupData[{
Cell["Edge Directives", "Section"],
Cell["\<\
Continuing with the previous example, we can specify directives for the \
edges.\
\>", "Text"],
Cell[BoxData[
RowBox[{
RowBox[{"PlotGraph", "[",
RowBox[{\(OrientGraph[Wheel[4]]\), ",",
"\[IndentingNewLine]", \(Directed \[Rule] {HeadCenter \[Rule] 1}\),
",", "\[IndentingNewLine]", \(ArrowheadPosition \[Rule] 1/2\), ",",
"\[IndentingNewLine]", \(VertexDirectives \[Rule] \
{AbsolutePointSize[6], Blue}\), ",",
"\[IndentingNewLine]", \(VertexLabelOffset \[Rule] {2.5, 0}\), ",",
"\[IndentingNewLine]", \(VertexLabels \[Rule] {1, 2, {3, {0, 2}},
4}\), ",",
"\[IndentingNewLine]", \(VertexLabelTextOptions \[Rule] {Background \
\[Rule] Gold}\), ",", "\[IndentingNewLine]",
StyleBox[\(EdgeDirectives \[Rule] {OrangeRed, AbsoluteThickness[2],
AbsoluteDashing[{10, 4}]}\),
FontColor->RGBColor[1, 0, 0]], ",",
"\[IndentingNewLine]", \(GraphPlottingOptions \[Rule] {Background \
\[Rule] MintCream, PlotLabel \[Rule] "\",
ImageSize \[Rule] 350}\)}], "]"}], ";"}]], "Input",
CellLabel->"In[20]:="],
Cell["\<\
Well, I like the original graph better, but there may be occasions for \
different style edges, especially with composite graphs discussed below.\
\>", "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell["Edge Labels", "Section"],
Cell[TextData[{
"It is also possible to label edges. To do so you must supply a list of \
edges, as ordered pairs, and their labels. It is also possible to supply a \
sepecific offset for a specific edge. Continuing again with the same example \
we will create a set of labels for the edges in the form ",
Cell[BoxData[
\(e[from, \ to]\)]],
". The Combinatorica routine ToOrderedPairs extracts the edges from a graph \
as a list of order pairs of vertices. EdgeLabelOffset sets the offset for all \
the edge labels from the center of the edge. EdgeLabelTextOptions are passed \
to the Text statements that produce the labels."
}], "Text"],
Cell[CellGroupData[{
Cell[BoxData[{
\(e1 = ToOrderedPairs[OrientGraph[Wheel[4]]]\), "\n",
\(edgelabels = {e1, \(Apply[e, #] &\) /@ e1} // Transpose\)}], "Input",
CellLabel->"In[21]:="],
Cell[BoxData[
\({{1, 2}, {2, 3}, {2, 4}, {3, 1}, {3, 4}, {4, 1}}\)], "Output",
CellLabel->"Out[21]="],
Cell[BoxData[
\({{{1, 2}, e[1, 2]}, {{2, 3}, e[2, 3]}, {{2, 4}, e[2, 4]}, {{3, 1},
e[3, 1]}, {{3, 4}, e[3, 4]}, {{4, 1}, e[4, 1]}}\)], "Output",
CellLabel->"Out[22]="]
}, Open ]],
Cell[BoxData[
RowBox[{
RowBox[{"PlotGraph", "[",
RowBox[{\(OrientGraph[Wheel[4]]\), ",",
"\[IndentingNewLine]", \(Directed \[Rule] {HeadCenter \[Rule]
1/2}\), ",",
"\[IndentingNewLine]", \(ArrowheadPosition \[Rule] 0.8\), ",",
"\[IndentingNewLine]", \(VertexDirectives \[Rule] \
{AbsolutePointSize[6], Blue}\), ",",
"\[IndentingNewLine]", \(VertexLabelOffset \[Rule] {2.5, 0}\), ",",
"\[IndentingNewLine]", \(VertexLabels \[Rule] {1, 2, {3, {0, 2}},
4}\), ",",
"\[IndentingNewLine]", \(VertexLabelTextOptions \[Rule] {Background \
\[Rule] Gold}\), ",", "\[IndentingNewLine]",
StyleBox[\(EdgeLabels \[Rule] edgelabels\),
FontColor->RGBColor[1, 0, 0]], ",", "\[IndentingNewLine]",
StyleBox[\(EdgeLabelOffset \[Rule] {\(-1.2\), \(-2\)}\),
FontColor->RGBColor[1, 0, 0]], ",", "\[IndentingNewLine]",
StyleBox[\(EdgeLabelTextOptions \[Rule] {Background \[Rule]
PaleGreen,
TextStyle \[Rule] {FontFamily \[Rule] "\",
FontSize \[Rule] 10}}\),
FontColor->RGBColor[1, 0, 0]], ",",
"\[IndentingNewLine]", \(GraphPlottingOptions \[Rule] {Background \
\[Rule] MintCream, PlotLabel \[Rule] "\",
ImageSize \[Rule] 350}\)}], "]"}], ";"}]], "Input",
CellLabel->"In[23]:="]
}, Closed]],
Cell[CellGroupData[{
Cell["Designing Your Own Graphs", "Section"],
Cell["\<\
You may often find that Combinatorica does not have just the graph type that \
you want. But it is easy to make up your own graph. Here we construct a \
simple zig-zag path through four vertices. We start with an empty graph \
consisting of four vertices.\
\>", "Text"],
Cell[CellGroupData[{
Cell[BoxData[
\(g = EmptyGraph[4]\)], "Input",
CellLabel->"In[24]:="],
Cell[BoxData[
\(Graph[{{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0,
0}}, {{0, \(-\(3\/2\)\)}, {0, \(-\(1\/2\)\)}, {0, 1\/2}, {0,
3\/2}}]\)], "Output",
CellLabel->"Out[24]="]
}, Open ]],
Cell[BoxData[
\(\(PlotGraph[g];\)\)], "Input",
CellLabel->"In[25]:="],
Cell["\<\
But we want the vertices laid out in a pattern that will have a bend. We can \
change the vertex locations this way, giving a list of the vertex \
locations.\
\>", "Text"],
Cell[CellGroupData[{
Cell[BoxData[
\(g = ChangeVertices[g, {{\(-1\), 0}, {0, 0}, {0, 1}, {1, 1}}]\)], "Input",\
CellLabel->"In[26]:="],
Cell[BoxData[
\(Graph[{{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0,
0}}, {{\(-1\), 0}, {0, 0}, {0, 1}, {1, 1}}]\)], "Output",
CellLabel->"Out[26]="]
}, Open ]],
Cell[BoxData[
\(\(PlotGraph[g, VertexLabels \[Rule] True];\)\)], "Input",
CellLabel->"In[27]:="],
Cell["Now we can add the path edges to the graph.", "Text"],
Cell[CellGroupData[{
Cell[BoxData[{
\(\(g = AddEdge[g, {1, 2}, Directed];\)\), "\[IndentingNewLine]",
\(\(g = AddEdge[g, {2, 3}, Directed];\)\), "\[IndentingNewLine]",
\(g = AddEdge[g, {3, 4}, Directed]\)}], "Input",
CellLabel->"In[28]:="],
Cell[BoxData[
\(Graph[{{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {0, 0, 0,
0}}, {{\(-1\), 0}, {0, 0}, {0, 1}, {1, 1}}]\)], "Output",
CellLabel->"Out[30]="]
}, Open ]],
Cell[BoxData[
\(\(PlotGraph[g, VertexLabels \[Rule] True,
Directed \[Rule] True];\)\)], "Input",
CellLabel->"In[31]:="],
Cell["\<\
The Combinatorica routine FromOrderedPairs is also very convenient for \
setting up your own graphs.\
\>", "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell["DrawGraph", "Section"],
Cell["\<\
DrawGraph was designed to work in the DrawingPaper paradigm. The DrawingPaper \
packages can be obtained at my web site. But, in fact, you won't need \
DrawingPaper at all unless unless you want to combine Combinatorica graphs \
with other kinds of graphics. DrawGraph is used in the following manner. \
Let's take the oriented Wheel[4] example again. We put the DrawGraph inside a \
Show statement. GraphPlottingOptions are no longer used. If you use them, \
they will just be thrown away. Instead, these options are put as options to \
the Show statement itself. In addition, it is necessary to specify the \
AspectRatio and the PlotRange. Except for the GraphPlottingOptions, the \
DrawGraph statement is just like the PlotGraph statement.\
\>", "Text"],
Cell[BoxData[
RowBox[{
RowBox[{"Show", "[",
RowBox[{
RowBox[{"Graphics", "[",
RowBox[{"{", "\[IndentingNewLine]",
StyleBox[\(DrawGraph[
OrientGraph[
Wheel[4]], \[IndentingNewLine]Directed \[Rule] \
{HeadCenter \[Rule] 1/2}, \[IndentingNewLine]ArrowheadPosition \[Rule]
1/2, \[IndentingNewLine]VertexDirectives \[Rule] \
{AbsolutePointSize[6],
Blue}, \[IndentingNewLine]VertexLabelOffset \[Rule] \
{2.5, 0}, \[IndentingNewLine]VertexLabels \[Rule] {1, 2, {3, {0, 2}},
4}, \[IndentingNewLine]VertexLabelTextOptions \[Rule] \
{Background \[Rule] Gold}, \[IndentingNewLine]EdgeLabels \[Rule]
edgelabels, \[IndentingNewLine]EdgeLabelOffset \[Rule] \
{\(-1.2\), \(-2\)}, \[IndentingNewLine]EdgeLabelTextOptions \[Rule] \
{Background \[Rule] PaleGreen,
TextStyle \[Rule] {FontFamily \[Rule] "\",
FontSize \[Rule] 10}}]\),
FontColor->RGBColor[0.00390631, 0.660166, 0.382818],
Background->GrayLevel[1]],
StyleBox["}",
FontColor->RGBColor[0.00390631, 0.660166, 0.382818],
Background->GrayLevel[1]]}],
StyleBox["]",
FontColor->RGBColor[0.00390631, 0.660166, 0.382818],
Background->GrayLevel[1]]}], ",", "\[IndentingNewLine]",
RowBox[{"{",
RowBox[{
StyleBox[\(Background \[Rule] MintCream\),
FontColor->RGBColor[0, 0, 1]],
StyleBox[",",
FontColor->RGBColor[0, 0, 1]],
StyleBox[\(PlotLabel \[Rule] "\"\),
FontColor->RGBColor[0, 0, 1]],
StyleBox[",",
FontColor->RGBColor[0, 0, 1]],
StyleBox[\(ImageSize \[Rule] 350\),
FontColor->RGBColor[0, 0, 1]], ",",
StyleBox[\(AspectRatio \[Rule] Automatic\),
FontColor->RGBColor[1, 0, 0]],
StyleBox[",",
FontColor->RGBColor[1, 0, 0]],
StyleBox[\(PlotRange \[Rule] All\),
FontColor->RGBColor[1, 0, 0]]}], "}"}]}], "]"}],
";"}]], "Input",
CellLabel->"In[32]:="],
Cell["\<\
So, for a single graph, it is easier to use PlotGraph. The main use of \
DrawGraph will be when we want to plot composite graphs with different edge \
styles, or add extra elements to a plot. The last section illustrates a case.\
\
\>", "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell["SelfLoops", "Section"],
Cell[TextData[{
"If you wish to have self-loops, i.e., an edge from a vertex back to \
itself, you must add such directed edges to the graph. You can then display \
these self-loops in the plot by giving the option ",
Cell[BoxData[
\(SelfLoops \[Rule] True\)]],
". PlotGraph sets the radii of the self-loops as 15 % of the distance from \
the \"center\" of the graph to its furthest vertex. You can also set the \
radii directly by using ",
Cell[BoxData[
\(SelfLoops \[Rule] radius\)]],
" where radius is the absolute value of the radii to be used."
}], "Text"],
Cell["Here is a graph with one self-loop at the first vertex.", "Text"],
Cell[BoxData[{\(g = CompleteGraph[4];\), "\n",
RowBox[{
StyleBox[\(g = AddEdge[g, {1, 1}, Directed]\),
FontColor->RGBColor[1, 0, 0]], ";"}], "\n",
RowBox[{
RowBox[{"PlotGraph", "[",
RowBox[{"g", ",",
StyleBox[\(SelfLoops \[Rule] True\),
FontColor->RGBColor[1, 0, 0]],
",", \(EdgeDirectives \[Rule] {Blue}\)}], "]"}], ";"}]}], "Input",
CellLabel->"In[33]:="],
Cell["\<\
Here is a graph with self-loops at every vertex. The radii of the circles \
have been made smaller than the default value.\
\>", "Text"],
Cell[BoxData[{\(g = Wheel[4];\), "\n",
RowBox[{
StyleBox[\(Do[
g = AddEdge[g, {i, i}, Directed], {i, 1, Length[Vertices[g]]}]\),
FontColor->RGBColor[1, 0, 0]], ";"}], "\n",
RowBox[{
RowBox[{"PlotGraph", "[",
RowBox[{"g", ",", "\[IndentingNewLine]",
StyleBox[\(SelfLoops \[Rule] 0.07\),
FontColor->RGBColor[1, 0, 0]], ",",
"\[IndentingNewLine]", \(EdgeDirectives \[Rule] {Black}\), ",",
"\[IndentingNewLine]", \(VertexDirectives \[Rule] {PointSize[0.03],
Blue}\)}], "]"}], ";"}]}], "Input",
CellLabel->"In[36]:="]
}, Closed]],
Cell[CellGroupData[{
Cell["A Composite Graph - A Cayley Digraph", "Section"],
Cell[TextData[{
"The following example is taken from ",
StyleBox["A First Course in Abstract Algebra",
FontSlant->"Italic"],
" Sixth Edition, p88 by John Fraleigh. It shows a Cayley digraph for the \
cyclic group ",
Cell[BoxData[
\(\[DoubleStruckCapitalZ]\_6\)]],
" with the generating set ",
Cell[BoxData[
\({2, 3}\)]],
". It show how each element of the set ",
Cell[BoxData[
\({0, 1, 2, 3, 4, 5}\)]],
" can be obtained by adding either ",
Cell[BoxData[
\(2\)]],
" or ",
Cell[BoxData[
\(3\)]],
" modulo 6 to another element. The essential point for our purposes is that \
the edges which represent adding 2 are shown by a directed solid edge, and \
edges which represent adding 3 are show by an undirected dashed edge. We \
can't do this by plotting a single graph because all edges are in the same \
style. But we can combine two graphs, each with their own set of edges and \
edge styles."
}], "Text"],
Cell["\<\
This gives us the three vertices of a small equilaterial triangle.\
\>", "Text"],
Cell[CellGroupData[{
Cell[BoxData[
\(v1 = {Cos[\[Theta]],
Sin[\[Theta]]} /. {{\[Theta] \[Rule] \[Pi]/
2}, {\[Theta] \[Rule] \(-\[Pi]\)/
6}, {\[Theta] \[Rule] \(-5\) \[Pi]/6}}\)], "Input",
CellLabel->"In[39]:="],
Cell[BoxData[
\({{0,
1}, {\@3\/2, \(-\(1\/2\)\)}, {\(-\(\@3\/2\)\), \(-\(1\/2\)\)}}\)], \
"Output",
CellLabel->"Out[39]="]
}, Open ]],
Cell["\<\
This gives us the three vertices of a larger equilaterial triangle.\
\>", "Text"],
Cell[CellGroupData[{
Cell[BoxData[
\(v2 =
2 {Cos[\[Theta]],
Sin[\[Theta]]} /. {{\[Theta] \[Rule] \[Pi]/
2}, {\[Theta] \[Rule] \(-\[Pi]\)/
6}, {\[Theta] \[Rule] \(-5\) \[Pi]/6}}\)], "Input",
CellLabel->"In[40]:="],
Cell[BoxData[
\({{0, 2}, {\@3, \(-1\)}, {\(-\@3\), \(-1\)}}\)], "Output",
CellLabel->"Out[40]="]
}, Open ]],
Cell["We now make out first graph.", "Text"],
Cell[BoxData[
\(\(g1 =
FromOrderedPairs[{{1, 2}, {2, 3}, {3, 1}, {4, 5}, {5, 6}, {6, 4}},
Join[v1, v2]];\)\)], "Input",
CellLabel->"In[41]:="],
Cell[BoxData[
\(\(PlotGraph[g1, Directed \[Rule] True,
VertexLabels \[Rule] True];\)\)], "Input",
CellLabel->"In[42]:="],
Cell[TextData[{
"Now we make a ",
StyleBox["second",
FontSlant->"Italic"],
" graph with undirected edges between the inner and outer vertices."
}], "Text"],
Cell[BoxData[
\(\(g2 =
FromOrderedPairs[{{1, 4}, {2, 5}, {3, 6}},
Join[v1, v2]];\)\)], "Input",
CellLabel->"In[43]:="],
Cell[BoxData[
\(\(PlotGraph[g2, VertexLabels \[Rule] True];\)\)], "Input",
CellLabel->"In[44]:="],
Cell["\<\
Now, using DrawGraph, we can put these two different graphs together. The \
vertex labels give the elements of the group, and we put them right on top of \
the vertices in the second graph.\
\>", "Text"],
Cell[BoxData[
\(\(Show[
Graphics[{\[IndentingNewLine]DrawGraph[
g1, \[IndentingNewLine]Directed \[Rule] {HeadCenter \[Rule]
1/2}, \[IndentingNewLine]ArrowheadPosition \[Rule]
1/2, \[IndentingNewLine]EdgeDirectives \[Rule] {SeaGreen}], \
\[IndentingNewLine]DrawGraph[
g2, \[IndentingNewLine]EdgeDirectives \[Rule] {Blue,
AbsoluteDashing[{5,
10}]}, \[IndentingNewLine]VertexLabels \[Rule] {3, 5,
1, 0, 2,
4}, \[IndentingNewLine]VertexLabelTextOptions \[Rule] \
{Background \[Rule] Gold}, \[IndentingNewLine]VertexLabelOffset \[Rule] {0,
0}]}], \[IndentingNewLine]AspectRatio \[Rule] Automatic,
PlotRange \[Rule] All, Background \[Rule] Linen,
ImageSize \[Rule] 400,
PlotLabel \[Rule] \*"\"\<\!\(\[DoubleStruckCapitalZ]\_6\) \
Digraph\>\""];\)\)], "Input",
CellLabel->"In[45]:="],
Cell["\<\
We are making progress. Now, the last thing we want to do is add labels to \
the edges. We want to label all the green edges with 2, since they represent \
the addition of 2, and we want to label the blue edges with 3. Remember that \
the vertex numbers are different than the labels directly above.\
\>", "Text"],
Cell[CellGroupData[{
Cell[BoxData[
\(elabs1 = ToOrderedPairs[g1] /. a : {_, _} \[Rule] {a, 2}\)], "Input",
CellLabel->"In[46]:="],
Cell[BoxData[
\({{{1, 2}, 2}, {{2, 3}, 2}, {{3, 1}, 2}, {{4, 5}, 2}, {{5, 6},
2}, {{6, 4}, 2}}\)], "Output",
CellLabel->"Out[46]="]
}, Open ]],
Cell["\<\
I decided to edit the above to give a better offset for two of the labels.\
\>", "Text"],
Cell[BoxData[
\(\(elabs1 = {{{1, 2}, 2}, {{2, 3}, 2}, {{3, 1}, 2, {2, 0}}, {{4, 5},
2}, {{5, 6}, 2}, {{6, 4}, 2, {2, 0}}};\)\)], "Input",
CellLabel->"In[47]:="],
Cell[CellGroupData[{
Cell[BoxData[
\(elabs2 = ToOrderedPairs[g2] /. a : {_, _} \[Rule] {a, 3}\)], "Input",
CellLabel->"In[48]:="],
Cell[BoxData[
\({{{1, 4}, 3}, {{2, 5}, 3}, {{3, 6}, 3}}\)], "Output",
CellLabel->"Out[48]="]
}, Open ]],
Cell[BoxData[
\(\(elabs2 = {{{1, 4}, 3, {\(-2\), 0}}, {{2, 5}, 3}, {{3, 6},
3}};\)\)], "Input",
CellLabel->"In[49]:="],
Cell[BoxData[
\(\(Show[
Graphics[{\[IndentingNewLine]DrawGraph[
g1, \[IndentingNewLine]Directed \[Rule] {HeadCenter \[Rule]
1/2}, \[IndentingNewLine]ArrowheadPosition \[Rule]
1/2, \[IndentingNewLine]EdgeDirectives \[Rule] {SeaGreen}, \
\[IndentingNewLine]EdgeLabels \[Rule]
elabs1, \[IndentingNewLine]EdgeLabelOffset \[Rule] {\(-2\), \
\(-2\)}], \[IndentingNewLine]DrawGraph[
g2, \[IndentingNewLine]EdgeDirectives \[Rule] {Blue,
AbsoluteDashing[{5,
10}]}, \[IndentingNewLine]EdgeLabels \[Rule]
elabs2, \[IndentingNewLine]EdgeLabelOffset \[Rule] {0, \
\(-1\)}, \[IndentingNewLine]VertexLabels \[Rule] {3, 5, 1, 0, 2,
4}, \[IndentingNewLine]VertexLabelTextOptions \[Rule] \
{Background \[Rule] Gold}, \[IndentingNewLine]VertexLabelOffset \[Rule] {0,
0}]}], \[IndentingNewLine]AspectRatio \[Rule] Automatic,
PlotRange \[Rule] All, Background \[Rule] Linen,
ImageSize \[Rule] 400,
PlotLabel \[Rule] \*"\"\<\!\(\[DoubleStruckCapitalZ]\_6\) \
Digraph\>\""];\)\)], "Input",
CellLabel->"In[50]:="],
Cell["\<\
So, after some work, we do have a completely labeled digraph with different \
style edges. Notice that if we take the value of a starting vertex and add \
the value of the edge to it modulo 6, then we obtain the value of the other \
vertex. The blue edges can go in either direction, but the green lines go in \
only one direction.\
\>", "Text"],
Cell["\<\
It is always a certain amount of work to produce nice graphics. I hope that \
this example demonstrates that the CombinatoricaPlots package gives you the \
tools for making rather elaborate graph plots.\
\>", "Text"]
}, Closed]]
}, Open ]]
},
FrontEndVersion->"4.0 for Microsoft Windows",
ScreenRectangle->{{0, 1024}, {0, 683}},
WindowToolbars->"EditBar",
WindowSize->{706, 634},
WindowMargins->{{2, Automatic}, {Automatic, 0}},
StyleDefinitions -> "TutorialBook.nb"
]
(***********************************************************************
Cached data follows. If you edit this Notebook file directly, not using
Mathematica, you must remove the line containing CacheID at the top of
the file. The cache data will then be recreated when you save this file
from within Mathematica.
***********************************************************************)
(*CellTagsOutline
CellTagsIndex->{}
*)
(*CellTagsIndex
CellTagsIndex->{}
*)
(*NotebookFileOutline
Notebook[{
Cell[CellGroupData[{
Cell[1739, 51, 44, 0, 61, "Title"],
Cell[1786, 53, 90, 4, 91, "Subtitle"],
Cell[1879, 59, 207, 4, 48, "Text"],
Cell[2089, 65, 140, 3, 54, "Input"],
Cell[CellGroupData[{
Cell[2254, 72, 37, 0, 92, "Section"],
Cell[2294, 74, 183, 4, 92, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[2514, 83, 31, 0, 60, "Section"],
Cell[2548, 85, 517, 12, 88, "Text"],
Cell[3068, 99, 517, 8, 108, "Text"],
Cell[3588, 109, 941, 17, 168, "Text"],
Cell[4532, 128, 342, 6, 68, "Text"],
Cell[4877, 136, 590, 11, 88, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[5504, 152, 40, 0, 60, "Section"],
Cell[CellGroupData[{
Cell[5569, 156, 93, 2, 31, "Input"],
Cell[5665, 160, 531, 8, 123, "Print"]
}, Open ]],
Cell[CellGroupData[{
Cell[6233, 173, 95, 2, 31, "Input"],
Cell[6331, 177, 319, 7, 96, "Print"]
}, Open ]]
}, Closed]],
Cell[CellGroupData[{
Cell[6699, 190, 41, 0, 60, "Section"],
Cell[6743, 192, 133, 3, 28, "Text"],
Cell[6879, 197, 89, 2, 31, "Input"],
Cell[6971, 201, 95, 2, 31, "Input"],
Cell[7069, 205, 88, 2, 31, "Input"],
Cell[7160, 209, 80, 2, 31, "Input"]
}, Closed]],
Cell[CellGroupData[{
Cell[7277, 216, 39, 0, 60, "Section"],
Cell[7319, 218, 231, 4, 48, "Text"],
Cell[7553, 224, 482, 10, 100, "Input"]
}, Closed]],
Cell[CellGroupData[{
Cell[8072, 239, 54, 0, 60, "Section"],
Cell[8129, 241, 68, 0, 28, "Text"],
Cell[8200, 243, 298, 6, 54, "Input"],
Cell[8501, 251, 75, 0, 28, "Text"],
Cell[8579, 253, 370, 8, 77, "Input"],
Cell[8952, 263, 361, 6, 68, "Text"],
Cell[9316, 271, 512, 12, 100, "Input"],
Cell[9831, 285, 121, 3, 28, "Text"],
Cell[9955, 290, 541, 12, 100, "Input"],
Cell[10499, 304, 238, 4, 48, "Text"],
Cell[10740, 310, 449, 10, 77, "Input"]
}, Closed]],
Cell[CellGroupData[{
Cell[11226, 325, 34, 0, 60, "Section"],
Cell[11263, 327, 69, 0, 28, "Text"],
Cell[11335, 329, 271, 6, 54, "Input"],
Cell[11609, 337, 98, 2, 28, "Text"],
Cell[11710, 341, 356, 8, 77, "Input"],
Cell[12069, 351, 118, 3, 28, "Text"],
Cell[12190, 356, 356, 8, 77, "Input"],
Cell[12549, 366, 234, 4, 48, "Text"],
Cell[12786, 372, 372, 8, 77, "Input"],
Cell[13161, 382, 48, 0, 28, "Text"],
Cell[13212, 384, 737, 12, 261, "Input"]
}, Closed]],
Cell[CellGroupData[{
Cell[13986, 401, 34, 0, 60, "Section"],
Cell[14023, 403, 104, 3, 28, "Text"],
Cell[14130, 408, 1100, 20, 307, "Input"],
Cell[15233, 430, 169, 3, 48, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[15439, 438, 30, 0, 60, "Section"],
Cell[15472, 440, 650, 11, 128, "Text"],
Cell[CellGroupData[{
Cell[16147, 455, 174, 3, 54, "Input"],
Cell[16324, 460, 107, 2, 30, "Output"],
Cell[16434, 464, 182, 3, 51, "Output"]
}, Open ]],
Cell[16631, 470, 1478, 27, 376, "Input"]
}, Closed]],
Cell[CellGroupData[{
Cell[18146, 502, 44, 0, 60, "Section"],
Cell[18193, 504, 279, 5, 68, "Text"],
Cell[CellGroupData[{
Cell[18497, 513, 75, 2, 31, "Input"],
Cell[18575, 517, 208, 4, 72, "Output"]
}, Open ]],
Cell[18798, 524, 75, 2, 31, "Input"],
Cell[18876, 528, 181, 4, 48, "Text"],
Cell[CellGroupData[{
Cell[19082, 536, 120, 3, 31, "Input"],
Cell[19205, 541, 172, 3, 51, "Output"]
}, Open ]],
Cell[19392, 547, 102, 2, 31, "Input"],
Cell[19497, 551, 59, 0, 28, "Text"],
Cell[CellGroupData[{
Cell[19581, 555, 234, 4, 77, "Input"],
Cell[19818, 561, 172, 3, 51, "Output"]
}, Open ]],
Cell[20005, 567, 134, 3, 31, "Input"],
Cell[20142, 572, 124, 3, 28, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[20303, 580, 28, 0, 60, "Section"],
Cell[20334, 582, 766, 11, 148, "Text"],
Cell[21103, 595, 2391, 51, 422, "Input"],
Cell[23497, 648, 254, 5, 48, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[23788, 658, 28, 0, 60, "Section"],
Cell[23819, 660, 583, 12, 108, "Text"],
Cell[24405, 674, 71, 0, 28, "Text"],
Cell[24479, 676, 432, 10, 77, "Input"],
Cell[24914, 688, 146, 3, 48, "Text"],
Cell[25063, 693, 623, 13, 169, "Input"]
}, Closed]],
Cell[CellGroupData[{
Cell[25723, 711, 55, 0, 60, "Section"],
Cell[25781, 713, 964, 26, 148, "Text"],
Cell[26748, 741, 90, 2, 28, "Text"],
Cell[CellGroupData[{
Cell[26863, 747, 238, 5, 31, "Input"],
Cell[27104, 754, 137, 4, 48, "Output"]
}, Open ]],
Cell[27256, 761, 91, 2, 28, "Text"],
Cell[CellGroupData[{
Cell[27372, 767, 249, 6, 54, "Input"],
Cell[27624, 775, 102, 2, 32, "Output"]
}, Open ]],
Cell[27741, 780, 44, 0, 28, "Text"],
Cell[27788, 782, 168, 4, 77, "Input"],
Cell[27959, 788, 135, 3, 31, "Input"],
Cell[28097, 793, 165, 5, 28, "Text"],
Cell[28265, 800, 144, 4, 31, "Input"],
Cell[28412, 806, 103, 2, 31, "Input"],
Cell[28518, 810, 213, 4, 48, "Text"],
Cell[28734, 816, 982, 18, 307, "Input"],
Cell[29719, 836, 323, 5, 68, "Text"],
Cell[CellGroupData[{
Cell[30067, 845, 114, 2, 31, "Input"],
Cell[30184, 849, 146, 3, 30, "Output"]
}, Open ]],
Cell[30345, 855, 98, 2, 28, "Text"],
Cell[30446, 859, 179, 3, 54, "Input"],
Cell[CellGroupData[{
Cell[30650, 866, 114, 2, 31, "Input"],
Cell[30767, 870, 98, 2, 30, "Output"]
}, Open ]],
Cell[30880, 875, 137, 3, 31, "Input"],
Cell[31020, 880, 1210, 21, 399, "Input"],
Cell[32233, 903, 355, 6, 68, "Text"],
Cell[32591, 911, 226, 4, 48, "Text"]
}, Closed]]
}, Open ]]
}
]
*)
(***********************************************************************
End of Mathematica Notebook file.
***********************************************************************)