4. Generating Graphs

t  =  GridGraph[7,  9];

ShowGraph[
      t =  SetGraphOptions[
          t,  {{1,  10,  20,  VertexStyle  ->  Disc[Large],  
              VertexColor  ->  HotPink}, {{8,  9}, {32,  39}, 
              EdgeStyle -> Fat}}]]

t  =  AddEdges[t, {{ {29,  30}}}];

ShowGraph[t,  VertexNumber -> On,  
      PlotRange -> Large[0.02]]

GraphUnion

?GraphUnion

NOTES
* GraphUnion preserves the graphics options of the two graphs.

ShowGraph[GraphUnion[t,  t],  PlotRange -> Large[0.02]]

ShowGraph[
      GraphUnion[CompleteGraph[3],  CompleteGraph[5,  5],  Star[4]],  
      PlotRange -> Large[0.1]]

ShowGraph[ GraphUnion [6,  CompleteGraph[3]]]

TIMING DISCUSSION 
GraphUnion should be extremely fast and asympototically linear in the number of edges + vertices in the resulting graph.

gt  =  Table[GridGraph[20,  10  i],  {i,  20}];

rt  =  
      Table[ Timing[ GraphUnion[ gt[[i]],  
              gt[[i]] ]; ],  {i,  20}]

ListPlot[ Map[ #[[1, 1]] &,  rt],  
      PlotJoined -> True]

Here is a comparison between the old  and the new implementations of GraphUnion. The improvement in time is significant.

a  =  DiscreteMath`OldCombinatorica`Wheel[200];  
    aa  =  Wheel[200];

b  =  DiscreteMath`OldCombinatorica`CompleteGraph[75];  
    bb  =  CompleteGraph[75];

{Timing[DiscreteMath`OldCombinatorica`GraphUnion[a,  b];],  
      Timing[GraphUnion[aa,  bb];]}

cc  =  Star[1000];  
    c  =  DiscreteMath`OldCombinatorica`Star[1000];

Timing[ GraphUnion[aa,  cc];]

Timing[ DiscreteMath`OldCombinatorica`GraphUnion[a, 
          c]; ]

ExpandGraph

?ExpandGraph

I don't see the need for ExpandGraph. AddVertices can replace ExpandGraph.

?AddVertices

ShowGraph[ExpandGraph[Wheel[10],  20]]

GraphIntersection

?GraphIntersection

p1 = 
        ShowGraph[s  =  Wheel[20],  VertexColor -> Red,  
          EdgeColor -> Red,  VertexNumber -> On, Graphics];

p2 = 
        ShowGraph[r  =  GridGraph[4, 5],  VertexColor -> Blue,  
          EdgeColor -> Blue,  VertexNumber -> On,  Graphics];

p3  =  
        ShowGraph[GraphIntersection[s,  r],  VertexColor -> Green,  
          EdgeColor -> Green,  VertexNumber -> On,  Graphics];

Show[ GraphicsArray[{p1,  p2,  p3} ],  
      ImageSize -> 600]

p4  =  
        ShowGraph[GraphIntersection[r, s],  VertexColor -> Green,  
          EdgeColor -> Green,  VertexNumber -> On,  Graphics];

Show[ GraphicsArray[{p1,  p2,  p4} ],  
      ImageSize -> 600]

NOTES
*There is an asymmetry in the function as far as inheritance of graphics information is concerned. The edge and vertex graphics information of the first graph are inherited by the result. Users should keep this in mind while choosing the order in which to specify the graphs.

ShowGraph[GraphIntersection[t,  CompleteGraph[63]],  
      VertexNumber -> On,  PlotRange -> Large[0.1]]

g  =  SetGraphOptions[Star[5],  VertexColor -> Red];  
    ShowGraph[g]

ShowGraph[GraphIntersection[g,  CompleteGraph[5]]]

TIMING DISCUSSION 
Let g1 be an m1-vertex graph and g2 be an m2-vertex graph. Let the number of edges in g1 ⋂ g2 be d. Then the asymptotic running time of the GraphIntersection function is θ(m1 log (m1) + m2 log(m2) + m1 d). Assuming that g1 and g2 are identical, this leads to a function that is asymptotic in m, the number of edges in the graph. Let us see if these claims bear out in experiments.

gt  =  Table[  GridGraph[20,  10  i],  {i,  20}];  
    rt  =  Table[
        Timing[GraphIntersection [ gt[[i]],  
              gt[[i]]];],  {i,  20}]

ListPlot[ Map[#[[1, 1]] &,  rt],  PlotJoined -> True]

The plot above is clearly quadratic and this brings up the question whether GraphIntersection could be rewritten so that it is sub-quadratic in the number of edges.
Here is a timing comparison between the new and the old implementations of GraphIntersection. For dense graphs the old implementation seems to be better, whereas for sparse graphs the new implementation of graph intersection does better.

a =  DiscreteMath`OldCombinatorica`CompleteGraph[80];  
    aa  =  CompleteGraph[80];

b  =  DiscreteMath`OldCombinatorica`GridGraph[8,  10];  
    bb  =  GridGraph[8, 10];

{Timing[DiscreteMath`OldCombinatorica`GraphIntersection[a,  
            b];],  Timing[GraphIntersection[aa,  bb];],  
      Timing[ GraphIntersection[bb,  aa];]}

a  =  DiscreteMath`OldCombinatorica`RandomTree[100];  
    aa  = RandomTree[100];

b  =  DiscreteMath`OldCombinatorica`GridGraph[10,  10];  
    bb  =  GridGraph[10,  10];

{Timing[DiscreteMath`OldCombinatorica`GraphIntersection[a,  
            b];],  Timing[GraphIntersection[aa,  bb];]}

GraphDifference

?GraphDifference

Edges[GraphDifference[t,  t]]

ShowGraph[s  =  EmptyGraph[V[t]],  
      VertexStyle -> Disc[Small]]

ShowGraph[GraphDifference[t,  s]]

NOTES
Again, graphics information from the first argument is inherited. 
TIMING DISCUSSION
The code for GraphDifference is very similar to the code for GraphIntersection. So I expect that experiments will show that the function has a similar worst case quadratic behaviour. However, the old implementation of GraphDifference is faster than the new implementation. It is impossible to beat GraphDifference since GraphDifference is simply matrix addition.

a  =  DiscreteMath`OldCombinatorica`CompleteGraph[100];  
    aa  =  CompleteGraph[100];

b  =  DiscreteMath`OldCombinatorica`RandomTree[100];  
    bb  =  RandomTree[100];

{Timing[DiscreteMath`OldCombinatorica`GraphDifference[a,  a];],  
      Timing[GraphDifference[aa,  aa];]}

{Timing[DiscreteMath`OldCombinatorica`GraphDifference[b,  b];],  
      Timing[GraphDifference[bb,  bb];]}

GraphSum

?GraphSum

ShowGraph[GraphSum[t,  Path[63]]]

g  =  
        SetGraphOptions[Wheel[10],  EdgeStyle -> Fat,  
          EdgeColor -> Purple];

h  =  
        SetGraphOptions[Star[10],  EdgeColor -> Green];

ShowGraph[GraphSum[g,  Star[10]]]

BUG
In the above example, the edges of Star[10] should keep their graphics properties and not inherit the graphics properties of the first graph. The following example also shows the same problem. I will fix this when I work on the graph data structure.

p1 = 
        ShowGraph[
          a  =  SetGraphOptions[ GridGraph[3, 3],  
              EdgeColor -> LightBlue,  VertexColor -> Red,  
              VertexStyle -> Disc[Large]],  Graphics];

p2 =  
        ShowGraph[
          b  =  SetGraphOptions[ Wheel[9],  EdgeColor  ->  Yellow,  
              VertexColor -> LightBlue,  VertexStyle -> Disc[Large]],  
          Graphics];

Show[GraphicsArray[{p1,  p2}],  ImageSize -> 500,  
      Background -> Black]

ShowGraph[ GraphSum[ a,  b ],  Background -> Black ,  
      PlotRange -> Large[0.01]]

What happens if the graphics information in the second graph is local? The following example shows that edge-graphics information is inherited correctly in this case.

b  =  Wheel[9];

ShowGraph[b]

p2 =  
      ShowGraph[
        b  =  SetGraphOptions[ b,  
            Append[Edges[b], EdgeColor  ->  Yellow],  
            VertexColor -> LightBlue,  VertexStyle -> Disc[Large]],  
        Background -> Black,  PlotRange -> Large[0.01]]

ShowGraph[ GraphSum[ a,  b ],  Background -> Black ,  
      PlotRange -> Large[0.01]]

TIMING DISCUSSION
GraphSum is simply a join of the edge lists and for all practical purposes should take O(1) time. Whether this is really true depends on the Join[...] operation. In any case, this function is extremely fast as revealed by the experiments below. Given how fast the function is, the plot below does not make a whole lot of sense.
The old implementation of this function is also quite fast since it involves adding the adjacency matrices.

gt  =  
        Table[  GridGraph[20,  10  i],  {i,  20}]; 
rt  =  
      Table[Timing[GraphSum [ gt[[i]],  gt[[i]]];],  {i,  
          20}]

ListPlot[ Map[#[[1, 1]] &,  rt],  PlotJoined -> True]

aa  =  
        Table[ DiscreteMath`OldCombinatorica`RandomTree[i^2],  {i,  10,  
            30,  10}];

bb  =  
        Table[ DiscreteMath`OldCombinatorica`GridGraph[i, i],  {i,  10,  
            30,  10}];

Table [
      Timing[ DiscreteMath`OldCombinatorica`GraphSum[aa[[i]],  
            bb[[i]] ];],  {i,  3}]

GraphJoin

?GraphJoin

l  =  r  = EmptyGraph[5];

ShowGraph[GraphUnion[l,  r]]

ShowGraph[GraphJoin[l,  r]]

BUG
The same graphics inheritance problem continues. Should the vertex in g2 loose its Green color? If the Green color were specified as a  local option, then this information is not lost (see example further below). Should making the right choice be the users burden?
The principle is that as much as possible graphics information is maintained from the original graphs. This means that no, g2's vertices should not loose their green color.

g1  =  
        SetGraphOptions[ Cycle[10],  VertexStyle -> Disc[Large],  
          VertexColor -> Blue];

g2  =  
        SetGraphOptions[CompleteGraph[1],   VertexColor -> Green,  
          VertexStyle -> Disc[Large]];

g3  =  
        SetGraphOptions[CompleteGraph[1],   {1, VertexColor -> Green},  
          VertexStyle -> Disc[Large]];

ShowGraph[GraphJoin[g1,  g2],  PlotRange -> Large[0.1]]

ShowGraph[ GraphJoin[g1,  g3],  PlotRange -> Large[0.1]]

TIMING DISCUSSION
The running time of the function is θ(n1n2+m1+m2) where n1 and m1 are the number of vertices and edges in graph 1 and n1 and m2 are the number of vertices and edges in graph 2. So the running time is quadratic in the size of the input. This is confirmed by the following experiment.
Further below there is a comparison of the running time of the new implementation and the running time of the old implementation. The new implementation is substantially faster by virtue of the sparse data structure it uses.

?GraphJoin

gt  =  
        Table[  GridGraph[5,  5  i],  {i,  5}];

rt  =  
        Table[Timing[GraphJoin[ gt[[i]],  gt[[i]]];],  {i,  
            5}];

ListPlot[ Map[#[[1, 1]] &, rt],  PlotJoined -> True]

a  =  
      Table[DiscreteMath`OldCombinatorica`RandomTree[i],  {i,  50,  70,  
          10}];  aa  =  
      Table[RandomTree[i],  {i,  50,  70,  10}];

b  =  
      Table[DiscreteMath`OldCombinatorica`GridGraph[i,  i],  {i,  10,  
          30,  10}];  
    bb  =  Table[GridGraph[i,  i],  {i,  10,  30,  10}];

Table[ 
      Timing[DiscreteMath`OldCombinatorica`GraphJoin[a[[i]],  
            b[[i]] ];],  {i,  3}]

Table[ 
      Timing[GraphJoin[aa[[i]],  bb[[i]] ];],  {i,  
        2}]

GraphProduct

?GraphProduct

l  = Wheel[5];

r  =  GridGraph[3,  3];

ShowGraph[GraphProduct[l,  r],  
      VertexStyle -> Disc[Small]]

ShowGraph[
      GraphProduct[CompleteGraph[3],  CompleteGraph[5]]]

ShowGraph[
      GraphProduct[CompleteGraph[5],  CompleteGraph[3]]]

ShowGraph[ 
      GraphProduct[CompleteGraph[3],  Star[3],  
        CompleteGraph[3]]]

BUG
As with GraphSum etc. Graphics information that is local is not inherited. This is shown in the following example. In fact, here graphics information from both graphs is missing. So in that sense this is a bug peculiar to GraphProduct.

ShowGraph[
      l  =  SetGraphOptions[l,  VertexColor -> Green,  
          EdgeColor -> Green],  Background -> Black]

ShowGraph[
      r  =  SetGraphOptions[r,  VertexColor -> Orange, 
          EdgeColor -> Orange],  Background -> Black]

ShowGraph[GraphProduct[l, r]]

BUG
There is a problem with inheriting local graphics information associated with vertices. The following example shows this. But, it not clear what convention to use for the vertices of the resulting graph. Something to think about.
The many copies of g1 should inherit graphics information of g1 and the edges that connect these copies should inherit information from g2.

ShowGraph[
      l1 =  SetGraphOptions[l, VertexColor -> Red, 
          EdgeColor -> Orange], Background -> Black]

ShowGraph[
      r1  =  SetGraphOptions[r, VertexColor -> Orange, 
          EdgeColor -> Orange],  Background -> Black]

ShowGraph[GraphProduct[l,  r]]

TIMING DISCUSSION
I need to look at the GraphProduct code somewhat carefully to figure out the asymptotic running time of the function. However, the output size if quadratic in the input size and I suspect the running time of the function is no worse than the size of the output produced. The following experiment bears this conjecture out. What is remarkable is that in under 22 seconds, the function could produce a graph with 62,500 vertices and 222,500 edges! This supports our view that now Combinatorica is not just a tool to play with small examples, but can be used for reasonable sized computations.

gt  =  Table[  GridGraph[5,  5  i],  {i,  10}]; 
rt  =  
      Table[Timing[GraphProduct[ gt[[i]],  gt[[i]]];],  {i,  
          10}]

g  =  GraphProduct[ gt[[10]],  gt[[10]]];

M[g]

V[g]

ListPlot[ Map[#[[1, 1]] &,  rt],  PlotJoined -> True]

aa  =  Cycle[100];

bb  =  RandomTree[100];

Timing[(ans  =  GraphProduct[aa,  bb]);]

V[ans]

M[ans]

a  =  DiscreteMath`OldCombinatorica`Cycle[30];

aa =  Cycle[30];

b  =  
        DiscreteMath`OldCombinatorica`RandomTree[30];

bb  =  RandomTree[30];

{Timing[DiscreteMath`OldCombinatorica`GraphProduct[a,  b];],  
      Timing[GraphProduct[aa,  bb];]}

NOTES
* Earlier I ran the above experiment with 50 instead of 30 as the argument for the various functions. But, that can occasionally crash  my machine because the old implementation of GraphProduct takes up too much memory.  When I run MMa 4.1 and run out of memory, the kernel shuts down and I get a polite message that there is no more memory. But, with MMa 3.0, the machine crashes.

IncidenceMatrix

?IncidenceMatrix

MatrixForm[IncidenceMatrix[Star[10]]]

g  =  SetGraphOptions[ Star[10],  EdgeDirection -> On];  
    ShowGraph[g,  VertexNumber -> On]

MatrixForm[IncidenceMatrix[g]]

LineGraph

?LineGraph

ShowGraph[LineGraph[CompleteGraph[5]]]

ShowGraph[LineGraph[Cycle[10]]]

ShowGraph[LineGraph[GridGraph[7,  7]]]

a  =  DiscreteMath`OldCombinatorica`GridGraph[25,  25];  
    aa  = GridGraph[25,  25];

{Timing[DiscreteMath`OldCombinatorica`LineGraph[a];],  
      Timing[LineGraph[aa];]}

NOTES
* The line graph inherits no graphics from the parent graph. It does inherit the embedding though.
* The speedup obtained with the new version is quite remarkable - 19.672 seconds vs 0.297 seconds - in the above example. 
TIMING DISCUSSION
I need to look at the code carefully to analyze the asymptotic running time of the function. Ideally, this would be linear in the size of output. The line graph of a grid graph is linear is size as a function of the grid graph. So the following experiment should give us running times that grow in a linear fashion.
The plot below does seem to support this claim!

gt  =  
        Table[  GridGraph[20,  10  i],  {i,  15}]; 
rt  =  
      Table[Timing[LineGraph[ gt[[i]]];],  {i,  15}]

ListPlot[ Map[#[[1, 1]] &,  rt],  PlotJoined -> True]

CirculantGraph

?CirculantGraph

ShowGraph[
      CirculantGraph[21,  RandomKSubset[Range[10],  3]]]

ShowGraph[
      CirculantGraph[21,  RandomKSubset[Range[10],  3]]]

ShowGraph[
      CirculantGraph[21,  RandomKSubset[Range[10],  3]]]

NOTES
* Note that circulant graphs contain multiple edges. Here is an illustration. For odd n, using the subset Range[Floor[n/2]] generates a complete graph with each edge doubled. For even n, using the same subset generates a complete graph with each edge double plus edges of the form{i, i+n/2} for each i.  This is a problem in the implementation of CompleteGraph - I could always use CirculantGraph and throw away the duplicates, but I am not sure I want to do that.

ne  =  Edges[CirculantGraph[5,  {1,  2}]]

Length[ne]

ne  =  Edges[CirculantGraph[4,  {1,  2}]]

Length[ne]

TIMING DISCUSSION
As expected, the running time of the CirculantGraph[...] function is linear in the size of the graph it produces. The function is quite fast and produces a circulant graph with 4000 vertices and 20,000 edges in about 3 seconds. However, the older implementation is faster because it simply uses a rotation operation on the adjacency matrix. But, using the older implementation we cannot come close to generating such large graphs.

{Timing[DiscreteMath`OldCombinatorica`CirculantGraph[
            2000,  {1,  2,  3,  4,  5}];],  
      Timing[CirculantGraph[
            2000,  {1,  2,  3,  4,  5}];]}

p  =  
        Table[ RandomKSubset[ Range[200  i] ,  5],  {i,  
            20}];

rt = 
      Table[Timing[ CirculantGraph[200  i,  p[[i]] ];],  {i, 
          20}]

ListPlot[ Map[#[[1, 1]] &,  rt],  PlotJoined -> True]

CompleteGraph

?CompleteGraph

ShowGraph[CompleteGraph[10]]

TIMING DISCUSSION
As expected, the running time of the CompleteGraph[...] is linear in the size of the graph. The function is pretty fast - a 400 vertex complete graph (with roughly, 80,000 edges) takes less than a second to be generated. The older implementation is faster since CirculantGraph[...] is faster, but that implementation cannot some close to generating graphs of the size that can be generated using the new implementation.

rt  =  
      Table[ Timing[ CompleteGraph[100 + 10  i];],  {i,  
          30}]

ListPlot[ 
      Table[ { (50  +  5  i) (99 + 10  i),  
          rt[[i,  1,  1]]},  {i,  30}],  
      PlotJoined -> True]

{Timing[DiscreteMath`OldCombinatorica`CompleteGraph[250];],  
      Timing[CompleteGraph[250];]}

{Timing[DiscreteMath`OldCombinatorica`CompleteGraph[500];],  
      Timing[CompleteGraph[500];]}

NOTES
* Complete directed graphs can also be generated.

ShowGraph[CompleteGraph[10,  Type -> Directed]]

TO DO
* Complete bipartite graphs can also be generated using CompleteGraph[....]. This seems to be too much of function name overloading. The graphs are different and the code is also quite different. I should just use something like CompleteKPartiteGraph[...] instead.

ShowGraph[CompleteGraph[3,  4,  3]]

?ShakeGraph

ShowGraph[ShakeGraph[CompleteGraph[3,  3,  3,  3],  0.3],  
      VertexStyle  ->  Disc[Small],  VertexNumber  ->  On]

Timing[ CompleteGraph[100,  100,  100,  100]; ]

Timing[ DiscreteMath`OldCombinatorica`CompleteGraph[100, 100, 100, 
          100];]

EmptyGraph

?EmptyGraph

ShowGraph[EmptyGraph[10]]

DiscreteMath`OldCombinatorica`ShowGraph[
      DiscreteMath`OldCombinatorica`EmptyGraph[10]]

NOTES
* Which embedding is better?

Turan

?Turan

ShowGraph[Turan[10,  4]]

ShowGraph[Turan[10,  2]]

TIMING DISCUSSION
The plot below confirms to some extent that Turan is linear in the size of the output it produces. I need to analyze the code further to make sure that this is true. The old implementation of Turan is much faster than the new implementation. Turan is definitely candidate for speedup. To speedup Turan I need to speed up the CompleteKpartiteGraph[...] implementation.
TO DO
Speedup the CompleteKpartiteGraph[...] implementation to make it more competitive with the older implementation.

rt  = 
      Table[Timing [gt[[i]] =  Turan[i*100,  50];],  {i,  5,  
          10}]

ListPlot[ 
      Table[{M[ gt[[i]] ],  rt[[ i - 4,  1,  1 ]] },  {i,  
          5,  10}],  PlotJoined -> True,  ImageSize -> 400]

Table[
      Timing [ DiscreteMath`OldCombinatorica`Turan[i*100,  
            50];],  {i,  5,  10}]

Clear[gt]

Cycle

?Cycle

ShowGraph[Cycle[20]]

TIMING DISCUSSION
The old implementation of Cycle is quite fast given that it is working on the adjacency matrix. It is also surprising that my machine did not crash while attempting to construct the 2000 x 2000 adjacency matrix. Anyway, this is probably the limit for the old implementation. The new implementation manages to build a 50,000 vertex cyle in about 3 seconds!
Since the code of Cycle is rather simple, it is easy to see that its running time is θ(n). The plot below conforms this.

{Timing[DiscreteMath`OldCombinatorica`Cycle[2000];],  
      Timing[Cycle[2000];]}

Timing[ Cycle[ 50000]; ]

rt  =  Table[ Timing[Cycle[500  i];] , {i,  20}]

ListPlot[ Map[ #[[1, 1]] &,  rt],  
      PlotJoined -> True]

Star

?Star

ShowGraph[Star[20]]

TIMING DISCUSSION
Note that the old implementation of Star is quite slow as compared to the new implementation Star. As expected, the running time of Star is linear.

{Timing[DiscreteMath`OldCombinatorica`Star[1000];],  
      Timing[Star[1000];]}

{Timing[DiscreteMath`OldCombinatorica`Star[2000];],  
      Timing[Star[2000];]}

rt  =  
        Table[ Timing[ Star[100  i];],  {i,  100}];

ListPlot[ Map[ #[[1, 1]] &,  rt],  
      PlotJoined -> True]

Wheel

?Wheel

ShowGraph[Wheel[20]]

TIMING DISCUSSION
The new implementation of Wheel is much faster than the old. As expected, the new implementation is linear.

{Timing[DiscreteMath`OldCombinatorica`Wheel[1000];],  
      Timing[Wheel[1000];]}

{Timing[DiscreteMath`OldCombinatorica`Wheel[2000];],  
      Timing[Wheel[2000];]}

rt  =  
        Table[ Timing[ Wheel[100  i];],  {i,  200}];

ListPlot[ Map[ #[[1, 1]] &,  rt],  
      PlotJoined -> True]

Path

?Path

ShowGraph[Path[20]]

TIMING DISCUSSION
The old implementation of Path is ridiculously slow! The new implementation is extremely fast. A path of length 5000 can be constructed in 0.13 seconds. Since the running time of the new implementation is so small the plot is somewhat bumpy; it is linear nevertheless.

Timing[DiscreteMath`OldCombinatorica`Path[2000];]

rt  =  
        Table[ Timing[ Path[100  i]; ],  {i,  500}];

ListPlot[ Map[ #[[1, 1]] &,  rt], PlotJoined -> True]

GridGraph

?GridGraph

ShowGraph[GridGraph[3,  4]]

ShowGraph[GridGraph[25,  25],  
      VertexStyle  ->  Disc[Small]]

TIMING DISCUSSION
The new implementation of GridGraph[...] is much faster than the old implementation. As expected, the running time of GridGraph is linear.

Timing[DiscreteMath`OldCombinatorica`GridGraph[40,  
          40];]

Timing[DiscreteMath`OldCombinatorica`GridGraph[30,  
          30];]

p  =  
      Table[Timing[GridGraph[20,  10  i];],  {i,  15}]

ListPlot[Map[#[[1,  1]] &,  p],  PlotJoined -> True]

HyperCube

?Hypercube

ShowGraph[Hypercube[6]]

ShowGraph[Hypercube[6],  
      PlotRange -> Zoom[{1,  2,  3,  4,  5,  6,  7,  8}],  
      VertexNumber -> On,  ImageSize -> 400]

TIMING DISCUSSION
The new implementation of Hypercube is much faster than the old implementation.  The implementations use dynamic programming to construct the hypercubes. Because of this the Table of timings below for the new implementation of Hypercube is misleading. Information stored while computing smaller hypercubes gets used in computing larger hypercubes. It is also somewhat peculiar that I was able to compute upto dimension 15 in the table, but ran out of memory when doing this separately.

Timing[DiscreteMath`OldCombinatorica`Hypercube[10];]

Timing[Hypercube[10];]

Table[Timing[Hypercube[n];],  {n,  15}]

Hypercube[15]

LabeledTreeToCode

?LabeledTreeToCode

LabeledTreeToCode[RandomTree[20]]

LabeledTreeToCode[CodeToLabeledTree[Table[10,  {20}]]]

LabeledTreeToCode[Path[100]]

TIMING DISCUSSION
The implementation of this function seems to be linear based on the plot below. However, I need to look at code some more to make sure that this is indeed true. However, this function is a candidate for speedup since it takes about 5 s to construct a Prufer code with 1000 vertices.
The speedup in going from the old implementation to the new implementation seems to be roughly a factor of 6.
TO DO
Speedup LabeledTreeToCode[...]

g  =  Table[RandomTree[i],  {i,  500,  1000, 100}];

rt = 
      Table[Timing[LabeledTreeToCode[ g[[i]] ]; ],  {i,  
          6}]

ListPlot[ Map[#[[1, 1]] &,  rt],  PlotJoined -> True]

gg  =  
        Table[DiscreteMath`OldCombinatorica`RandomTree[i],  {i,  500,  
            1000,  500}];

Table[
      Timing[ DiscreteMath`OldCombinatorica`LabeledTreeToCode[ 
            gg[[i]] ]; ],  {i,  2}]

CodeToLabeledTree

?CodeToLabeledTree

ShowGraph[CodeToLabeledTree[Table[10,  {20}]]]

ShowGraph[
      RadialEmbedding[CodeToLabeledTree[Table[10,  {20}]],  1]]

TIMING DISCUSSION
A quick look at the code of CodeToLabeledTree reveals that the asymptotic running time of this function is θ((n^2) log(n)). This is shown to some extent in the plot below - though it is obviously difficult to conclude the log(n) factor. This function is definitely a candidate for speedup. The new implementation is about 5 times faster than the old implementation.
TO DO
Speed up the CodeToLabeledTree function

s  =  
        Table[Table[Random[Integer,  {1,  i*100}] ,  {i*100 - 2}],  {i, 
            10}];

rt = 
      Table[ Timing[ CodeToLabeledTree[s[[i]] ]; ],  {i, 
          10}]

ListPlot[ Map[ #[[1, 1]] &,  rt],  
      PlotJoined -> True]

Table[ 
      Timing[ DiscreteMath`OldCombinatorica`CodeToLabeledTree [
            s[[i]] ]; ],  {i, 3}]

RandomTree

?RandomTree

ShowGraph[RadialEmbedding[RandomTree[20],  1],  
      VertexNumber -> On]

TIMING DISCUSSION
The new version of RandomTree seems about 4-5 times as fast as the old version. However, the new version might be speeded up if CodeToLabeledTree is speeded up. That might be possible by somehow getting rid of the Complement operations.
RandomTree generates a random code and then uses CodeToLabeledTree to get a tree. So its running time is completely dominated by the running time of CodeToLabeledTree. So it is not surprising that the running time plot looks quadratic.

Table[
      Timing[DiscreteMath`OldCombinatorica`RandomTree[i];],  {i, 100,  
        800,  100}]

p  =  
      Table[Timing[RandomTree[i];],  {i, 100,  800,  100}]

ListPlot[  Map[ #[[1, 1]] &,  p],  
      PlotJoined -> True]

RandomGraph

?RandomGraph

ShowGraph[s = RandomGraph[50,   .3],  
      VertexStyle -> Disc[0.01]]

ShowGraph[
      Highlight[s,  {Map[Sort, DepthFirstTraversal[s,  1,  Edge]]},  
        HighlightedEdgeColors -> {Blue}],  
      VertexStyle -> Disc[0]]

ShowGraph[
      Highlight[s,  {Map[Sort,  BreadthFirstTraversal[s,  1,  Edge]]},  
        HighlightedEdgeColors -> {Blue}],  
      VertexStyle -> Disc[0]]

TIMING DISCUSSION
RandomGraph[..] takes time θ((n^2)+ m), where n and m are the number of vertices and edges in the produced random graph. This is supported by the plots below. In the first plot n is fixed while p increases in linear fashion. In the second plot n increases and p is set at 1/n. This means that the expected number of edges is linear in n. However, the running time in this case increases in a quadratic fashion. It would wonderful if I could implement RandomGraph[...] so that its running time is θ(m+n).
TO DO
Implement RandomGraph[...] so that it takes time θ(m+n).
The new RandomGraph is much slower than the old RandomGraph because the new RandomGraph first constructs a random adjacency matrix (like RandomGraph) and then converts it into an edge list representation of a graph.

rt  =  
      Table[ Timing[ RandomGraph[100,  p];],  {p,  0.1,  0.9,  
          0.1}]

ListPlot[ Map[ #[[1, 1]] &,  rt],  
      PlotJoined -> True]

rt  =  
      Table[ Timing[ RandomGraph[20  i,  N[1/(20  i)]];],  {i,  
          20}]

ListPlot[ Map[ #[[1, 1]] &,  rt],  
      PlotJoined -> True]

{Timing[DiscreteMath`OldCombinatorica`RandomGraph[100,   .5];],  
      Timing[RandomGraph[100,   .5];]}

{Timing[DiscreteMath`OldCombinatorica`RandomGraph[300,   .5];], 
      Timing[RandomGraph[300,   .5];]}

{Timing[ DiscreteMath`OldCombinatorica`RandomGraph[300,  .8];], 
      Timing[RandomGraph[300,   .8];]}

BUG
Another problem with the new RandomGraph is that a version of the form RandomGraph[n, p, range] has been provided though, this does not work as of now. I have to decide whether to make this work or give separate options for generating random multigraphs and non-simple graphs.

ExactRandomGraph

?ExactRandomGraph

ShowGraph[ExactRandomGraph[10, 5],  
      Background -> LightBlue]

ShowGraph[ExactRandomGraph[20, 30],  Background -> Pink]

ShowGraph[s = ExactRandomGraph[100,  100],  
      VertexStyle -> Disc[0.02]]

ShowGraph[
      Highlight[s,  {Map[Sort,  DepthFirstTraversal[s,  1,  Edge]]},  
        HighlightedEdgeColors -> {Blue}],  
      VertexStyle -> Disc[0]]

TIMING DISCUSSON
This function has running time θ(mn+(n^2)) because it first generates a random permutation of size n(n-1)/2, picks the first m elements and then unranks these numbers into a set of edges. Each Unrank operation (using the function NthPair) takes θ(n) time. This is unfortunate and I wonder if this can be done in θ(m + n) time. The following plot shows the linear dependence on m and the plot below that shows the quadratic dependence on n.
The new ExactRandomGraph is not much faster than the old ExactRandomGraph. The small difference comes about because the new ExactRandomGraph does not need to convert from edges to adjacency matrix. 
TO DO
Speed up ExactRandomGraph[...] so that it takes θ(m + n) time.

rt  =  
      Table[ Timing[ExactRandomGraph[100,  m];],  {m,  100,  1000,  
          100}]

ListPlot[ Map[ #[[1, 1]] &,  rt],  
      PlotJoined -> True]

rt  =  
      Table[ Timing[ExactRandomGraph[n,  5  n];],  {n,  50,  250,  
          50}]

ListPlot[ Map[ #[[1, 1]] &,  rt],  
      PlotJoined -> True]

{Timing[DiscreteMath`OldCombinatorica`ExactRandomGraph[100,  
            100];],  Timing[ExactRandomGraph[100,  100];]}

{Timing[DiscreteMath`OldCombinatorica`ExactRandomGraph[500,  
            500];],  Timing[ExactRandomGraph[500,  500];]}

Timing[Map[{NthPair[#]} &,  
          Take[RandomPermutation[500 (500 - 1)/2],  500]];]

Timing[CircularVertices[1000];]

TO DO
Directed version of the new ExactRandomGraph should also be provided.

RandomVertices

?RandomVertices

ShowGraph[RandomVertices[Cycle[10]]]

TIMING DISCUSSION
This function takes linear time and is extremely fast.

g  =  GridGraph[50,  50];

Timing[ RandomVertices[ g ]; ]

DegreeSequence

?DegreeSequence

DegreeSequence[CompleteGraph[10]]

DegreeSequence[Path[100]]

TIMING DISCUSSION
The function is linear in the size of graph and this is confirmed by the plot below.
The running times of the old and the new implementation are comparable.

g  =  GridGraph[40, 40];  
    h  =  DiscreteMath`OldCombinatorica`GridGraph[40,  40];

Timing[ DegreeSequence[ g ]; ]

Timing[ DiscreteMath`OldCombinatorica`DegreeSequence[ 
          h ]; ]

gt  =  Table[GridGraph[20,  10  i],  {i,  20}];

rt  =  
        Table[ Timing[ DegreeSequence[ gt[[i]]]; ], {i, 
            20}];

ListPlot[ Map[ #[[1, 1]] &,  rt],  
      PlotJoined -> True]

gt  =  
        Table[ DiscreteMath`OldCombinatorica`GridGraph[20,  10  i],  {i,  
            5}];

rt  =  
        Table[ Timing[ DiscreteMath`OldCombinatorica`DegreeSequence[ 
                gt[[i]]]; ], {i, 5}];

ListPlot[ Map[ #[[1, 1]] &,  rt],  
      PlotJoined -> True]

GraphicQ

?GraphicQ

GraphicQ[DegreeSequence[RandomGraph[100,   .2]]]

GraphicQ[Range[100]]

TIMING DISCUSSION
GraphicQ and the new GraphicQ are almost identical and should take exactly the same amount of time.
 I need to look at the code of this function more carefully, but it does seem that this should take linear time in the size of the sequence. From the plot this is not conclusive; in fact, the plot seems to indicate that the function might be taking quadratic time.

a  =  DiscreteMath`OldCombinatorica`RandomTree[400];  
    aa  =  RandomTree[400];

$RecursionLimit = 10000;

{Timing[GraphicQ[DegreeSequence[aa]];], 
      Timing[DiscreteMath`OldCombinatorica`GraphicQ[
            DiscreteMath`OldCombinatorica`DegreeSequence[a]];]}

gt  =  
        Table [ 
          DegreeSequence[ RandomTree[20  i]],  {i,  20}];

rt  =  
      Table [ Timing[ GraphicQ[gt [[i]] ]; ],  {i,  
          20}]

ListPlot[ Map[#[[1, 1]] &,  rt],  PlotJoined -> True]

RealizeDegreeSequence

?RealizeDegreeSequence

NOTES
* I find this function a little strange. Why not just use GraphicQ's deterministic algorithm? Is the semi-random graph produced in this manner really useful? Does it produce a reasonably random Regular graph? Should we actually implement the algorithm in [Wor84] to generate a random regular graph?
* The new RealizeDegreeSequence is also a little ugly. Maybe its run-time could be improved by using more sophisticated Mathematica constructs.

ShowGraph[s = RandomTree[15],  VertexNumber -> On]

seq  =  DegreeSequence[s]

ShowGraph[g = RealizeDegreeSequence[seq],  
      VertexNumber -> On]

DegreeSequence[g]

NOTES
* Note that the graph that we started with and the graph that resulted from taking its degree sequence and then running the new DegreeSequence are not isomorphic.

IsomorphicQ[s, g]

TIMING DISCUSSION
The function is quite slow and needs significant speedup. Also from the plot it is clear that the function is not linear in the size of the output it produces. The running times of the new and the old version are virtually identical. This function is definitely in need of significant speedup.
TO DO
Speed up the RealizeDegreeSequence[...] function so that it is linear in the size of the output produced.

st  =  
        Table[ DegreeSequence[ GridGraph[10, 5  i]],  {i, 
            5}] ;

rt = 
      Table[Timing[ RealizeDegreeSequence[ 
              st[[i]]  ]; ],  {i,  5}]

ListPlot[ Map[ #[[1, 1]] &,  rt],  
      PlotJoined -> True]

st  =  
      Table[ DiscreteMath`OldCombinatorica`DegreeSequence[ 
          DiscreteMath`OldCombinatorica`GridGraph[10, 5  i]],  {i, 5}] ; 
    rt = Table[
        Timing[ DiscreteMath`OldCombinatorica`RealizeDegreeSequence[ 
              st[[i]]  ]; ],  {i,  5}]

RegularQ

?RegularQ

RegularQ[CompleteGraph[10]]

RegularQ[CompleteGraph[10,  10]]

RegularQ[RandomTree[10]]

RegularQ[Cycle[10]]

RegularGraph

?RegularGraph

ShowGraph[RegularGraph[1,  30],  
      VertexStyle -> Disc[Small]]

ShowGraph[
      RealizeDegreeSequence[{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
          1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}], 
      VertexStyle -> Disc[Small]]

ShowGraph[RegularGraph[2,  30],  
      VertexStyle -> Disc[Small]]

TIMING DISCUSSION
This function is essentially a call to RealizeDegreeSequence[...]. Hence, it has the same problems with running time as RealizeDegreeSequence does.

{Timing[DiscreteMath`OldCombinatorica`RegularGraph[10,  100];],  
      Timing[RegularGraph[10,  100];]}

MakeGraph

?MakeGraph

ShowGraph[
        g  =  MakeGraph[
            Permutations[{1,  2,  3,  
                4}],  (Count[#1  -  #2,  0]  ==  
                    2  &&  (Inversions[#1]  >  
                      Inversions[#2])) &]];

p  =  Permutations[ {1,  2,  3,  4}];

p1  = Map[ Text[#,  {0.05,  0.02}] &,  Cases[p,  {1, ___}]]; 
    p2  = Map[ Text[#,  {-0.05,  0.02}] &,  
        Cases[p,  {2, ___}]];
p3  = 
        Map[ Text[#,  {-0.05,  -0.02}] &,  
          Cases[p,  {3, ___}]];
p4 = 
        Map[ Text[#,  {0.05,  -0.02}] &,  
          Cases[p,  {4, ___}]];

g = SetVertexLabels[g,  Join[p1,  p2,  p3,  p4] ];

ShowGraph[ g ,  ImageSize -> 600,  VertexLabelColor -> Red, 
      PlotRange -> Large[0.2]]

IntervalGraph

?IntervalGraph

l  =  {{1,  10},  {2,  3},  {4,  5},  {6,  7},  {8,  
            9}};

s  = IntervalGraph[l];

s = 
        SetVertexLabels[s, 
          Map[ Text[#, {-0.09,  0.02}] &,  l]];

ShowGraph[  s ,  PlotRange -> Large[ .4],  
      ImageSize -> 400]

FunctionalGraph

?FunctionalGraph

ShowGraph[
      FunctionalGraph[Mod[(#^2 + 2*#),  20] &,  
        Table[i,  {i,  0,  19}]]]