#*****************************************************************************80
#
## alphabet_binary_tree plots a binary tree for alphabetizing.
#
#  Licensing:
#
#    This code is distributed under the MIT license. 
#
#  Modified:
#
#    01 September 2020
#
#  Author:
#
#    John Burkardt
#
cat ( date ( ), "\n" )
cat ( "\n" )
cat ( "alphabet_binary_tree\n" )
cat ( " ", version$version.string, "\n" )
cat ( "  Plot an alphabetizing binary tree." )

library ( igraph )

filename = "alphabet_binary_tree.png"
png ( filename )

G <- graph.tree ( n = 1, children = 2 )
V(G)$name <- "A-Z"

G <- G + vertices ( "A-M" )
G <- G + edge ( "A-Z", "A-M" )
G <- G + vertices ( "N-Z" )
G <- G + edge ( "A-Z", "N-Z" )

G <- G + vertices ( "A-F" )
G <- G + edge ( "A-M", "A-F" )
G <- G + vertices ( "G-M" )
G <- G + edge ( "A-M", "G-M" )
G <- G + vertices ( "N-S" )
G <- G + edge ( "N-Z", "N-S" )
G <- G + vertices ( "T-Z" )
G <- G + edge ( "N-Z", "T-Z" )

G <- G + vertices ( "A-C" )
G <- G + edge ( "A-F", "A-C" )
G <- G + vertices ( "D-F" )
G <- G + edge ( "A-F", "D-F" )
G <- G + vertices ( "G-I" )
G <- G + edge ( "G-M", "G-I" )
G <- G + vertices ( "J-M" )
G <- G + edge ( "G-M", "J-M" )
G <- G + vertices ( "N-P" )
G <- G + edge ( "N-S", "N-P" )
G <- G + vertices ( "Q-S" )
G <- G + edge ( "N-S", "Q-S" )
G <- G + vertices ( "T-V" )
G <- G + edge ( "T-Z", "T-V" )
G <- G + vertices ( "W-Z" )
G <- G + edge ( "T-Z", "W-Z" )

G <- G + vertices ( "A" )
G <- G + edge ( "A-C", "A" )
G <- G + vertices ( "B-C" )
G <- G + edge ( "A-C", "B-C" )
G <- G + vertices ( "D" )
G <- G + edge ( "D-F", "D" )
G <- G + vertices ( "E-F" )
G <- G + edge ( "D-F", "E-F" )
G <- G + vertices ( "G" )
G <- G + edge ( "G-I", "G" )
G <- G + vertices ( "H-I" )
G <- G + edge ( "G-I", "H-I" )
G <- G + vertices ( "J-K" )
G <- G + edge ( "J-M", "J-K" )
G <- G + vertices ( "L-M" )
G <- G + edge ( "J-M", "L-M" )
G <- G + vertices ( "N" )
G <- G + edge ( "N-P", "N" )
G <- G + vertices ( "O-P" )
G <- G + edge ( "N-P", "O-P" )
G <- G + vertices ( "Q" )
G <- G + edge ( "Q-S", "Q" )
G <- G + vertices ( "R-S" )
G <- G + edge ( "Q-S", "R-S" )
G <- G + vertices ( "T" )
G <- G + edge ( "T-V", "T" )
G <- G + vertices ( "U-V" )
G <- G + edge ( "T-V", "U-V" )
G <- G + vertices ( "W-X" )
G <- G + edge ( "W-Z", "W-X" )
G <- G + vertices ( "Y-Z" )
G <- G + edge ( "W-Z", "Y-Z" )

G <- G + vertices ( "B" )
G <- G + edge ( "B-C", "B" )
G <- G + vertices ( "C" )
G <- G + edge ( "B-C", "C" )
G <- G + vertices ( "E" )
G <- G + edge ( "E-F", "E" )
G <- G + vertices ( "F" )
G <- G + edge ( "E-F", "F" )
G <- G + vertices ( "H" )
G <- G + edge ( "H-I", "H" )
G <- G + vertices ( "I" )
G <- G + edge ( "H-I", "I" )
G <- G + vertices ( "J" )
G <- G + edge ( "J-K", "J" )
G <- G + vertices ( "K" )
G <- G + edge ( "J-K", "K" )
G <- G + vertices ( "L" )
G <- G + edge ( "L-M", "L" )
G <- G + vertices ( "M" )
G <- G + edge ( "L-M", "M" )
G <- G + vertices ( "O" )
G <- G + edge ( "O-P", "O" )
G <- G + vertices ( "P" )
G <- G + edge ( "O-P", "P" )
G <- G + vertices ( "R" )
G <- G + edge ( "R-S", "R" )
G <- G + vertices ( "S" )
G <- G + edge ( "R-S", "S" )
G <- G + vertices ( "U" )
G <- G + edge ( "U-V", "U" )
G <- G + vertices ( "V" )
G <- G + edge ( "U-V", "V" )
G <- G + vertices ( "W" )
G <- G + edge ( "W-X", "W" )
G <- G + vertices ( "X" )
G <- G + edge ( "W-X", "X" )
G <- G + vertices ( "Y" )
G <- G + edge ( "Y-Z", "Y" )
G <- G + vertices ( "Z" )
G <- G + edge ( "Y-Z", "Z" )

my_layout <- layout.reingold.tilford ( G, params = list ( root = "A-Z" ) )
plot ( G, layout = my_layout, vertex.size = 12, 
  main = "Alphabetizing binary tree" )

cat ( '  Graphics saved as "', filename, '"\n' )
#
#  Terminate.
#
cat ( "\n" )
cat ( "alphabet_binary_tree:\n" )
cat ( "  Normal end of execution.\n" )

quit ( )