getdir := proc(G) option inline; op(1,G); end proc:
getwt := proc(G) option inline; op(2,G); end proc:
vlist := proc(G) option inline; op(3,G); end proc:
listn := proc(G) option inline; op(4,G); end proc:
ginfo := proc(G) option inline; op(5,G); end proc:
eweight := proc(G) option inline; op(6,G); end proc:
getops := proc(G) option inline; op(1..6,G); end proc:
makeweights := proc(G,W) option inline; subsop(6=W,2=weighted,G) end:
makevertices := proc(G,V) option inline; subsop(3=V,G) end:

macro( VERTEXTYPE = {integer, symbol, string, indexed} ):

# This module contains all the random graph generators.
# The main command in the GraphTheory module that it
# needs to use is Graph( ... ) command to create graphs.
# It also uses GraphComplement.
# But it also needs to get it's hands on components of graphs
# and avoid making redundant copies of components of graphs
# hence the use of getops, makeweights, listn, etc.


#################################################################################
##PACKAGE(help) RandomGraphs
##DATE          August 2006
##
##DESCRIPTION
##  
##- The `RandomGraphs` package contains routines for randomly
##  generating graphs with particular properties or structure.
##  Details are provided on the help pages for individual commands.
##
##SECTION List of RandomGraphs Commands
##  
##- The following is a list of the commands in the RandomGraphs package.
##
##-(lead=indent)  "AssignEdgeWeights"
##-(lead=indent)  "RandomBipartiteGraph"
##-(lead=indent)  "RandomDigraph"
##-(lead=indent)  "RandomGraph"
##-(lead=indent)  "RandomNetwork"
##-(lead=indent)  "RandomTournament"
##-(lead=indent)  "RandomTree"
##
##SEEALSO
##
##- "GraphTheory"
##
##XREFMAP
##-    "AssignEdgeWeights"	: Help:RandomGraphs[AssignEdgeWeights]
##-    "RandomBipartiteGraph"	: Help:RandomGraphs[RandomBipartiteGraph]
##-    "RandomDigraph"		: Help:RandomGraphs[RandomDigraph]
##-    "RandomGraph"		: Help:RandomGraphs[RandomGraph]
##-    "RandomNetwork"		: Help:RandomGraphs[RandomNetwork]
##-    "RandomTournament"	: Help:RandomGraphs[RandomTournament]
##-    "RandomTree"		: Help:RandomGraphs[RandomTree]



RandomGraphs := module()
export AssignEdgeWeights,
       RandomBipartiteGraph,
       RandomDigraph,
       RandomGraph,
       RandomNetwork,
       RandomTournament,
       RandomTree;
option package;
local  RandomLevels;

##############################################
##PROCEDURE(doti)       RandomGraphs[AssignEdgeWeights]
##AUTHOR                Michael Monagan
##DATE                  June 25, 2006
##
##CALLINGSEQ
##- AssignEdgeWeights('G','m..n')
##- AssignEdgeWeights('G','a..b')
##- AssignEdgeWeights('G','R')
##
##PARAMETERS
##- 'G' : graph
##- 'm', 'n' : integers satisfying 'n' >= 'm'
##- 'a', 'b' : floats satisfying 'b' >= 'a'
##- 'R' : user defined function for generating random edge weights
##
##DESCRIPTION
##- If 'G' is a weighted graph, ~AssignEdgeWeights(G,...)~ assigns new random
##  edge weights to 'G', i.e., for each edge ~(i,j)~ in 'G' the ~(i,j)~\'th
##  entry in the weight matrix of 'G' is updated inplace.
##
##- If 'G' is an unweighted graph, a weighted graph is first created before
##  assigning the edge weights.  The structure of 'G' is not copied.
##
##- ~AssignEdgeWeights(G,m..n)~ assigns the edges of the weighted graph
##  random integer weights uniformly distributed on ~[m,n]~.
##  
##- ~AssignEdgeWeights(G,a..b)~ assigns the edges of the weighted graph
##  random decimal weights uniformly distributed on ~[a,b)~.
##
##- ~AssignEdgeWeights(G,R)~ assigns the edges of the weighted graph
##  'G' values defined by ~R()~.  The Maple procedure ~R~ must return numerical
##  values, i.e., integers, rationals, or floating point constants.
##
##EXAMPLES
##> with(GraphTheory):
##> with(RandomGraphs):
##> T := Graph( weighted, {[1,2],[2,3],[3,4],[4,1]} );
##> WeightMatrix(T);
##> AssignEdgeWeights(T,1..9);
##> WeightMatrix(T);
##> T := RandomTree(4);
##> T := AssignEdgeWeights(T, 0.0 .. 1.0);
##> W := WeightMatrix(T);
##> op(3,W);
##< datatype = float[8], storage = rectangular, order = Fortran_order, shape = [symmetric]
##> T := RandomTree(100);
##> T := AssignEdgeWeights(T,1..99);
##> op(3,WeightMatrix(T));
##< datatype = integer, storage = sparse, order = Fortran_order, shape = [symmetric]
##-(nolead) This example creates a network
##> N := Graph({[1,2],[1,3],[1,4],[2,3],[4,3],[2,5],[3,5],[4,5]});
##> U := rand(1..4):
##> B := proc() if U()=1 then 1 else 2 fi end: 
##-(nolead) So Prob(B=1)=1/4, Prob(B=2)=3/4
##> N := AssignEdgeWeights(N,B);
##> W := WeightMatrix(N);
##> op(3,W);
##< datatype = anything, storage = rectangular, order = Fortran_order, shape = []
##
##SEEALSO
##- "GraphTheory[Graph]"
##- "GraphTheory[MakeWeighted]"
##- "GraphTheory[WeightMatrix]"
##- "RandomTree"
##
##XREFMAP
##- "RandomTree" : Help:RandomGraphs[RandomTree]
#---- version 24. AE & MBM
# MBM: needs the option "triangle_innequality_must_hold"

AssignEdgeWeights := proc(G::GRAPHLN,R)
# NB: this does NOT make a copy of the list of neighbours or the info table
local m,n,D,U,V,A,T,W,N,i,j,gen,out,sto,sha;
  gen:=0.0..1.0;
  out:=float[8];
  if nargs>1 then
    if type(R,float..float) then out:=float[8]; gen := R;
    elif type(R,integer..integer) then out:=integer; gen := R;
    elif type(R,numeric..numeric) then out:=anything; gen := R;
    else out:=anything;
         gen:=proc() local x;
                x := R();
                if not type(x,numeric) then 
                  error "generator output edge weight %1 which is not of type numeric.",x;
                fi;
                x;
              end;
    fi;
  fi;
  D,U,V,A,T,W := getops(G);
  n := nops(V);
  m := add(nops(A[i]),i=1..n);
  if U = unweighted then
     # create the weight matrix and recursively assign the weights
     if m < n^2/4-10 then sto := sparse else sto := rectangular; fi;
     if D=directed then sha := [] else sha := symmetric; fi;
     W := Matrix(n,n,shape=sha,datatype=out,storage=sto);
     return AssignEdgeWeights(makeweights(G,W),args[2..nargs]);
  fi;
  if D = undirected then m := m/2; fi;
  U := LinearAlgebra:-RandomVector(m,generator=gen,outputoptions=[datatype=out]);
  if has([op(3,W)],shape=[symmetric]) then
     N := 0;
     for i to n do for j in A[i] do
         if i<j then N := N+1; W[i,j] := U[N]; fi;
     od; od;
  elif G = undirected then
     N := 0;
     for i to n do for j in A[i] do
         if i<j then N := N+1; W[i,j] := U[N]; W[j,i] := U[N]; fi;
     od; od;
  else # G is directed
     N := 0;
     for i to n do for j in A[i] do N := N+1; W[i,j] := U[N]; od; od;
  fi;
  G;
end:


#############################################
##PROCEDURE(doti)       RandomGraphs[RandomDigraph]
##AUTHOR                Michael Monagan
##DATE                  June 25, 2006
##
##CALLINGSEQ
##- RandomDigraph('n', 'p', options)
##- RandomDigraph('n', 'm', options)
##
##PARAMETERS
##- 'n'  :  positive integer or list of vertices
##- 'p'  :  real number between ~0.0~ and ~1.0~
##- 'm'  :  non-negative integer
##- options : sequence of options (see below)
##
##RETURNS
##- A randomly generated directed graph.
##
##DESCRIPTION
##- ~RandomDigraph(n,m)~ creates a directed unweighted graph on 'n' vertices
##  and 'm' edges, where the 'm' edges are chosen uniformly at random.
##
##- ~RandomDigraph(n,p)~ creates a directed unweighted graph on 'n' vertices
##  where each possible edge is present with probability 'p'.
##
##- If the first input is a positive integer 'n', then the vertices will
##  be labelled ~1,2,...,n~.  Alternatively the user may specify the vertex
##  labels in a list.
##
##- If the option ~weights=m..n~ is specified, where ~m <= n~ are integers,
##  the graph will be a weighted graph with edge weights chosen from ~[m,n]~
##  uniformly at random.  The weight matrix ~W~ in the graph will have
##  ~datatype=integer~, and if the edge from vertex ~i~ to ~j~ is not in the
##  graph then ~W[i,j] = 0~.
##
##- If the option ~weights=x..y~ where ~x <= y~ are decimals is specified, the
##  graph will be a weighted graph with numerical edge weights chosen from
##  ~[x,y]~ uniformly at random.  The weight matrix ~W~ in the graph will have
##  ~datatype=float[8]~, that is, double precision floats (16 decimal digits),
##  and if the edge from vertex ~i~ to ~j~ is not in the graph then
##  ~W[i,j] = 0.0~.
##
##- If the option ~weights=f~ where 'f' is a function (a Maple procedure) that
##  returns a number (integer, rational, or decimal number), then 'f' is used
##  to generate the edge weights.  The weight matrix ~W~ in the graph will have
##  ~datatype=anything~, and if the edge from vertex ~i~ to ~j~ is not in the
##  graph then ~W[i,j] = 0~.
##
##EXAMPLES
##> with(GraphTheory):
##> with(RandomGraphs):
##> G := RandomDigraph(10, .5);
# # G := Graph 1: a directed unweighted graph with 10 vertices and 42 arc(s)
##> IsDirected(G);
##< true
##> H := RandomDigraph(10, 20);
# # H := Graph 2: a directed unweighted graph with 10 vertices and 20 arc(s)
##> J := RandomDigraph(4, 6, weights=1..4);
# # J := Graph 3: a directed weighted graph with 4 vertices and 6 arc(s)
##> WeightMatrix(J);
##
##SEEALSO
##- "AssignEdgeWeights"
##- "GraphTheory[IsDirected]"
##- "GraphTheory[WeightMatrix]"
##- "RandomBipartiteGraph"
##- "RandomGraph"
##- "RandomNetwork"
##- "RandomTournament"
##- "RandomTree"
##
##XREFMAP
##- "AssignEdgeWeights" : Help:RandomGraphs[AssignEdgeWeights]
##- "RandomBipartiteGraph" : Help:RandomGraphs[RandomBipartiteGraph]
##- "RandomGraph" : Help:RandomGraphs[RandomGraph]
##- "RandomNetwork" : Help:RandomGraphs[RandomNetwork]
##- "RandomTournament" : Help:RandomGraphs[RandomTournament]
##- "RandomTree" : Help:RandomGraphs[RandomTree]
#---------ver. 23,  modified by MG
# MBM: Needs options 'acyclic' and 'stronglyconnected'

RandomDigraph := proc(V::{list(VERTEXTYPE),posint},p::nonnegative)
  local w, n, M, i, j, P, N, F, g, R, b, m, x, y, A, e, G, gen;
  if type(V,posint) then n := V; else n := nops(V); end if;
  w := false;
  gen := NULL;
  for i from 3 to nargs do
    if args[i] = directed then # allow this
    elif type(args[i],identical('weights')=anything) then
       gen:=rhs(args[i]); w:=true;
    else error "invalid optional argument: %1", args[i];
    fi;
  end do;
  if type(p, integer) then
     if p > n*(n-1) then error "a digraph on %1 vertices cannot have %2 edges",n,p; fi;
     b := evalb( p < (1/2)*n*(n-1));
     m := `if`(b, p, n*(n-1)-p);
     A := Array(1..n); for i to n do A[i] := {} end do;
     R := rand(1..n);
     for i to m do
       x := R(); y := R();
       while x=y or member(y,A[x]) do x := R(); y := R(); end do;
       A[x] := A[x] union {y};
     end do;
     #G := GRAPHLN(directed, unweighted, listint(n), A, GRAPH_TABLE_NAME(), 0 );
     #if not type(V,posint) then G := makevertices(G,V) end if;
     G := GraphTheory:-Graph(directed, unweighted, V, A);
     if not b then G := GraphTheory:-GraphComplement( G ) end if;
  elif p<=1 then
     M:=Matrix(n,n);
     R:=rand(10^10);
     P := p*10^10;
     for i to n do
       M[i,i]:=false;
       for j from 1 to n do
         if i<>j then M[i,j]:=evalb( R() < P ); end if;
       end do;
     end do;
     A := Array(1..n); for i to n do A[i] := {seq(`if`(M[i,j],j,NULL), j=1..n)}; end do;
     #G := GRAPHLN(directed, unweighted, listint(n), A, GRAPH_TABLE_NAME(), 0 );
     #if not type(V,posint) then G := makevertices(G,V) end if;
     G := GraphTheory:-Graph(directed, unweighted, V, A);
  else
     error "2nd argument must be a real number between 0,1 or a positive integer but received %1",p;
  end if;
  if w then G := AssignEdgeWeights(G,gen); end if;
  G;
end;

#############################################
##PROCEDURE(doti)       RandomGraphs[RandomGraph]
##AUTHOR                Michael Monagan
##DATE                  June 25, 2006
##
##CALLINGSEQ
##- RandomGraph('n','p',options)
##- RandomGraph('n','m',options)
##
##PARAMETERS
##- 'n'  :  positive integer or a list of vertex labels
##- 'p'  :  real number between ~0.0~ and ~1.0~
##- 'm'  :  non-negative integer
##- options : sequence of options (see below)
##
##RETURNS
##- A randomly generated graph.
##
##DESCRIPTION
##- ~RandomGraph(n,p)~ creates an undirected unweighted graph on 'n' vertices
##  where each possible edge is present with probability 'p' where
##  ~0.0 <= p <= 1.0~.
##
##- ~RandomGraph(n,m)~ creates an undirected unweighted graph on 'n' vertices
##  and 'm' edges where the 'm' edges are chosen uniformly at random.
##  The value of 'm' must satisfy ~0 <= m <= binomial(n,2) = n*(n-1)/2~.
##
##- If the first input is a positive integer 'n', then the vertices will
##  be labelled ~1,2,...,n~.  Alternatively the user may specify the vertex
##  labels in a list.
##
##- If the option 'directed' is specified, a random directed graph is chosen.
##  This is equivalent to using the "RandomDigraph" command.
##
##- If the option 'connected' is specified, the graph created will be connected,
##  and hence will have at least ~n-1~ edges.
##
##  For ~RandomGraph(n,m,connected)~, 'm' must be at least ~n-1~.
##  A random tree is first created, then the remaining ~m-n+1~ edges are
##  chosen uniformly at random.
##
##  For ~RandomGraph(n,p,connected)~, a random tree is first created then each
##  remaining edge is present with probability 'p'.
##
##- If the option ~weights=m..n~ is specified, where ~m <= n~ are integers,
##  the graph will be a weighted graph with integer edge weights chosen
##  from ~[m,n]~ uniformly at random.  The weight matrix ~W~ in the graph will
##  have ~datatype=integer~, and if the edge from vertex ~i~ to ~j~ is not in
##  the graph then ~W[i,j] = 0~.
##
##- If the option ~weights=x..y~ where ~x <= y~ are decimals is specified, the
##  graph will be a weighted graph with numerical edge weights chosen from
##  ~[x,y]~ uniformly at random.  The weight matrix ~W~ in the graph will have
##  ~datatype=float[8]~, that is, double precision floats (16 decimal digits),
##  and if the edge from vertex ~i~ to ~j~ is not in the graph then
##  ~W[i,j] = 0.0~.
##
##- If the option ~weights=f~ where 'f' is a function (a Maple procedure) that
##  returns a number (integer, rational, or decimal number), then 'f' is used
##  to generate the edge weights.  The weight matrix ~W~ in the graph will
##  have ~datatype=anything~, and if the edge from vertex ~i~ to ~j~ is not
##  in the graph then ~W[i,j] = 0~.
##
##EXAMPLES
##> with(GraphTheory):
##> with(RandomGraphs):
##> G := RandomGraph(8, .5);
# # G := Graph 1: an undirected unweighted graph with 8 vertices and 14 edge(s)
##> G := RandomGraph(8, 10);
# # G := Graph 2: an undirected unweighted graph with 8 vertices and 10 edge(s)
##> G := RandomGraph(8, 10, connected);
# # G := Graph 3: an undirected unweighted graph with 8 vertices and 10 edge(s)
##> IsConnected(G);
##< true
#
##> H := RandomGraph(4, 1.0, weights=0.0..1.0);
# # H := Graph 4: an undirected weighted graph with 8 vertices and 6 edge(s)
##> WeightMatrix(H);
##> H := RandomGraph(8, 10, connected, weights=1..4);
# # H := Graph 5: an undirected weighted graph with 8 vertices and 10 edge(s)
##> WeightMatrix(H);
##> U := rand(1..4):
##> f := proc() local x; x := U(); if x=1 then 1 else 2 fi end:
##> H := RandomGraph(6, 1.0, weights=f);
# # H := Graph 6: an undirected weighted graph with 6 vertices and 15 edge(s)
##> WeightMatrix(H);
##
##SEEALSO
##- "AssignEdgeWeights"
##- "GraphTheory[IsConnected]"
##- "GraphTheory[WeightMatrix]"
##- "RandomBipartiteGraph"
##- "RandomDigraph"
##- "RandomNetwork"
##- "RandomTournament"
##- "RandomTree"
##
##XREFMAP
##- "AssignEdgeWeights" : Help:RandomGraphs[AssignEdgeWeights]
##- "RandomBipartiteGraph" : Help:RandomGraphs[RandomBipartiteGraph]
##- "RandomDigraph" : Help:RandomGraphs[RandomDigraph]
##- "RandomNetwork" : Help:RandomGraphs[RandomNetwork]
##- "RandomTournament" : Help:RandomGraphs[RandomTournament]
##- "RandomTree" : Help:RandomGraphs[RandomTree]
#---------ver. 23,  modified by MG
# MBM: needs the option degree=d for generating regular graphs

RandomGraph := proc(V::{list(VERTEXTYPE),posint},p::{nonnegint,nonnegative})
local w, c, n, M, i, j, P, N, F, g, R, b, m, x, A, e, y, G, T, gen;
  if type(V,posint) then n := V; else n := nops(V); end if;
  w,c := false,false;
  gen:=NULL;
  for i from 3 to nargs do
      if args[i] = 'directed' then return RandomDigraph(args)
      elif args[i] = 'connected' then c := true
      elif type(args[i],identical('weights')=anything) then gen:=rhs(args[i]); w:=true;
      else error "invalid optional argument: %1", args[i];
      end if;
  end do;
  if n=1 then # degenerate case
     G := GraphTheory:-Graph(V,undirected);
  elif type(p, integer) then
     if p>n*(n-1)/2 then
        error "a graph on %1 vertices cannot have more then %2 edges", n, n*(n-1)/2;
     end if;
     if c and p<n-1 then
        error "a connected graph on %1 vertices needs at least %2 edges", n, n-1;
     end if;
     if p < n*(n-1)/4 then # add m edges to the empty graph
        m := p; # insert m edges
        if c then # start with a random tree so G is connected
           T := RandomTree(n); A := listn(T); m := m-(n-1);
        else
           A := Array(1..n,fill={});
        end if;
        R := rand(1..n);
        for i to m do
            x := R(); y := R();
            while x=y or member(y,A[x]) do x := R(); y := R(); end do;
            A[x] := A[x] union {y};
            A[y] := A[y] union {x};
        end do;
     else # remove edges from the complete graph
        P := {seq(i,i=1..n)};
        A := Array(1..n);
        for i to n do A[i] := P minus {i} od; # start with the complete graph
        m := (1/2)*n*(n-1)-p; # remove m edges
        if c then T := listn( RandomTree(n) ) end if;
        R := rand(1..n);
        for i to m do # remove m edges (which are not in the tree T)
            x := R(); y := R();
            while x=y or c and member(y,T[x]) or not member(y,A[x]) do x := R(); y := R(); end do;
            A[x] := A[x] minus {y};
            A[y] := A[y] minus {x};
        end do;
     fi;
     #G := GRAPHLN(undirected, unweighted, listint(n), A, GRAPH_TABLE_NAME(), 0 );
     #if not type(V,posint) then G := makevertices(G,V) end if;
     G := GraphTheory:-Graph(undirected, unweighted, V, A);
  elif p<=1 then
     M:=Matrix(n,n,shape=symmetric);
     R:=rand(10^10);
     P := p*10^10;
     for i to n do
         M[i,i]:=false;
         for j from i+1 to n do M[i,j] := evalb( R() < P ); end do;
     end do;
     if c then # make G connected
        T := RandomTree(n);
        A := listn(T);
        for i to n do
            for j in A[i] do M[i,j] := true; end do;
        end do;
     end if;
     A := Array(1..n); for i to n do A[i] := {seq(`if`(M[i,j],j,NULL), j=1..n)}; end do;
     #G := GRAPHLN(undirected, unweighted, listint(n), A, GRAPH_TABLE_NAME(), 0 );
     #if not type(V,posint) then G := makevertices(G,V) end if;
     G := GraphTheory:-Graph(undirected, unweighted, V, A);
  else
     error "2nd argument must be a real number between 0,1 or a positive integer but received %1",p;
  end if;
  if w then G := AssignEdgeWeights(G,gen); end if;
  G;
end;


#############################################
##PROCEDURE(doti)       RandomGraphs[RandomTournament]
##AUTHOR                Michael Monagan
##DATE                  June 25, 2006
##
##CALLINGSEQ
##- RandomTournament('n',options)
##
##PARAMETERS
##- 'n'  :  positive integer or list of vertex labels
##- options : sequence of options (see below)
##
##RETURNS
##- A randomly generated tournament.
##
##DESCRIPTION
##- ~RandomTournament(n)~ will create a random tournament on 'n' vertices.
##  This is a directed graph such that for every pair of vertices ~u~ and ~v~
##  either the arc ~u~ to ~v~ or the arc ~v~ to ~u~ is in the digraph.
##
##- If the first input is a positive integer 'n', then the vertices will
##  be labelled ~1,2,...,n~.  Alternatively the user may specify the vertex
##  labels in a list.
##
##- If the option ~weights=m..n~ is specified, where ~m <= n~ are integers,
##  the graph will be a weighted graph with edge weights chosen from ~[m,n]~
##  uniformly at random.  The weight matrix ~W~ in the graph will have
##  ~datatype=integer~, and if the edge from vertex ~i~ to ~j~ is not in the
##  graph then ~W[i,j] = 0~.
##
##- If the option ~weights=x..y~ where ~x <= y~ are decimals is specified,
##  the graph will be a weighted graph with numerical edge weights chosen from
##  ~[x,y]~ uniformly at random.  The weight matrix ~W~ in the graph will have
##  ~datatype=float[8]~, that is, double precision floats (16 decimal digits),
##  and if the edge from vertex ~i~ to ~j~ is not in the graph then
##  ~W[i,j] = 0.0~.
##
##- If the option ~weights=f~ where 'f' is a function (a Maple procedure) that
##  returns a number (integer, rational, or decimal number), then 'f' is used
##  to generate the edge weights.  The weight matrix ~W~ in the graph will have
##  ~datatype=anything~, and if the edge from vertex ~i~ to ~j~ is not in the
##  graph then ~W[i,j] = 0~.
##
##EXAMPLES
##> with(GraphTheory):
##> with(RandomGraphs):
##> T := RandomTournament(5);
# # T := Graph 1: a directed unweighted graph with 5 vertices and 10 arc(s)
##> T := RandomTournament(5,weights=1..5);
##> IsTournament(T);
##< true
##> WeightMatrix(T);
##
##SEEALSO
##- "AssignEdgeWeights"
##- "GraphTheory[IsTournament]"
##- "GraphTheory[WeightMatrix]"
##- "RandomBipartiteGraph"
##- "RandomDigraph"
##- "RandomGraph"
##- "RandomNetwork"
##- "RandomTree"
##
##XREFMAP
##- "AssignEdgeWeights" : Help:RandomGraphs[AssignEdgeWeights]
##- "RandomBipartiteGraph" : Help:RandomGraphs[RandomBipartiteGraph]
##- "RandomDigraph" : Help:RandomGraphs[RandomDigraph]
##- "RandomGraph" : Help:RandomGraphs[RandomGraph]
##- "RandomNetwork" : Help:RandomGraphs[RandomNetwork]
##- "RandomTree" : Help:RandomGraphs[RandomTree]
#---------ver. 23,  modified by MG

RandomTournament:=proc(V::{list(VERTEXTYPE),posint})
local n,M,i,j,A,P,R,G,gen,w;
 if type(V,integer) then n := V else n := nops(V) fi;
 gen:=NULL;
 w:=false;
 for i from 2 to nargs do
    if type(args[i],identical('weights')=anything) then gen:=rhs(args[i]); w:=true;
    else error "invalid optional argument: %1", args[i];
    end if;
 end do;
 M:=Matrix(n,n);
 R:=rand(10^10);
 P := (1/2)*10^10;
 for i to n do
   M[i,i]:=false;
   for j from i+1 to n do
   M[i,j]:=evalb( R() < P );
   M[j,i]:=not(M[i,j]);
   end do;
 end do;
 A := Array(1..n); for i to n do A[i] := {seq(`if`(M[i,j],j,NULL), j=1..n)}; end do;
 #G := GRAPHLN( directed, unweighted, listint(n), A, GRAPH_TABLE_NAME(), 0 );
 #if not type(V,posint) then G := makevertices(G,V) end if;
 G := GraphTheory:-Graph(directed, unweighted, V, A);
 if w then G := AssignEdgeWeights(G,gen); end if;
 G;
end;


#############################################
##PROCEDURE(doti)       RandomGraphs[RandomTree]
##AUTHOR                Michael Monagan
##DATE                  June 25, 2006
##
##CALLINGSEQ
##- RandomTree('n')
##- RandomTree('n',degree<'d')
##- RandomTree('n',options)
##
##PARAMETERS
##- 'n'  : positive integer or list of vertex labels
##- 'd'  : positive integer
##- options : sequence of options (see below)
##
##RETURNS
##- A randomly generated tree.
##
##DESCRIPTION
##- ~RandomTree(n)~ will create a random tree on 'n' vertices.
##  This is an undirected connected graph with ~n-1~ edges.
##  If the first input 'n' is a positive integer, the vertices will
##  be labelled ~1,2,...,n~.
##  Alternatively the user may specify the vertex labels in a list.
##
##- Starting with the empty undirected graph ~T~ on 'n' vertices, edges
##  are chosen uniformly at random and inserted into ~T~ if they do
##  do not create a cycle.  This is repeated until ~T~ has ~n-1~ edges.
##
##- The option ~degree<d~ or ~degree<=d~ limits the maximum degree of
##  every vertex in the tree.
##
##- If the option ~weights=m..n~ is specified, where ~m <= n~ are integers,
##  the tree will be a weighted graph with edge weights chosen from ~[m,n]~
##  uniformly at random.  The weight matrix ~W~ in the graph will have
##  ~datatype=integer~, and if the edge from vertex ~i~ to ~j~ is not in the
##  graph then ~W[i,j] = 0~.
##
##- If the option ~weights=x..y~ where ~x <= y~ are decimals is specified,
##  the tree will be a weighted graph with numerical edge weights chosen from
##  ~[x,y]~ uniformly at random.  The weight matrix ~W~ in the graph will have
##  ~datatype=float[8]~, that is, double precision floats (16 decimal digits),
##  and if the edge from vertex ~i~ to ~j~ is not in the graph then
##  ~W[i,j] = 0.0~.
##
##- If the option ~weights=f~ where 'f' is a function (a Maple procedure) that
##  returns a number (integer, rational, or decimal number), then 'f' is used
##  to generate the edge weights.  The weight matrix ~W~ in the tree will have
##  ~datatype=anything~, and if the edge from vertex ~i~ to ~j~ is not in the 
##  graph then ~W[i,j] = 0~.
##
##EXAMPLES
##> with(GraphTheory):
##> with(RandomGraphs):
##> T := RandomTree(10);
# # T := Graph 1: an undirected unweighted graph with 10 vertices and 9 edge(s)
##> T := RandomTree(10, weights=1..9);
# # T := Graph 2: an undirected weighted graph with 10 vertices and 9 edge(s)
##> IsTree(T);
##< true
##> WeightMatrix(T);
##> T := RandomTree(100);
##> MaximumDegree(T);
##> T := RandomTree(100,degree<4);
##> MaximumDegree(T);
##< 3
##
##SEEALSO
##- "AssignEdgeWeights"
##- "GraphTheory[IsTree]"
##- "GraphTheory[WeightMatrix]"
##- "RandomBipartiteGraph"
##- "RandomDigraph"
##- "RandomGraph"
##- "RandomNetwork"
##- "RandomTournament"
##
##XREFMAP
##- "AssignEdgeWeights" : Help:RandomGraphs[AssignEdgeWeights]
##- "RandomBipartiteGraph" : Help:RandomGraphs[RandomBipartiteGraph]
##- "RandomDigraph" : Help:RandomGraphs[RandomDigraph]
##- "RandomGraph" : Help:RandomGraphs[RandomGraph]
##- "RandomNetwork" : Help:RandomGraphs[RandomNetwork]
##- "RandomTournament" : Help:RandomGraphs[RandomTournament]
#---------ver. 23,  modified by MG
#---------ver. 24,  added degree<d option by MBM

RandomTree := proc(V::{list(VERTEXTYPE),posint})
local Walk,Link,n,A,E,T,t,R,i,j,u,v,gen,w,D,d;
  if type(V,integer) then n := V else n := nops(V) fi;
  gen:=NULL;
  w:=false;
  d:=n-1; # maximum degree
  for i from 2 to nargs do
    if type(args[i],identical('weights')=anything) then gen:=rhs(args[i]); w:=true;
    elif type(args[i],identical('degree')<posint) then d := rhs(args[i])-1;
    elif type(args[i],identical('degree')<=nonnegint) then d := rhs(args[i]);
    else error "invalid optional argument: %1", args[i];
    end if;
  end do;
  if n=1 then return GraphTheory:-Graph(V); fi;
  if d=0 then error "a Tree with %1 vertices cannot have degree 0", n; fi;
  if n=2 then return GraphTheory:-Graph(V,{{V[1],V[2]}}); fi;
  if d=1 then error "a Tree with %1 vertices cannot have degree 1", n; fi;
  Walk := proc(i) local j,k;
    j := i; k := A[i];
    while k<>0 do j := k; k := A[j]; od;
    j;
  end:
  Link := proc(i,u) local j,k;
    j := i;
    while j<>0 and j<>u do k := j; j := A[j]; A[k] := u; od;
    # MBM: (j,A[j]) := (A[j],u); is not evaluated correctly in Maple 10
    NULL;
  end;
  D := Array(1..n); # degree of vertices in the tree
  A := Array(1..n,fill=0); # contains components of the tree
  E := Array(1..n);    # contains edges of the tree
  R := rand(1..n);
  t := 1;
  while t<n do
    i := R(); while D[i]=d do i := R(); od;
    j := R(); while D[j]=d or j=i do j := R() od;
    u,v := Walk(i),Walk(j);
    if u=v then next fi; # both vertices are in same component
    D[i] := D[i]+1;
    D[j] := D[j]+1;
    if type(V,list) then E[t] := {V[i],V[j]}; else E[t] := {i,j} fi;
    if u=i then A[u] := j; Link(i,v); else A[v] := i; Link(j,u); fi;
    t := t + 1;
  end do;
  T := GraphTheory:-Graph( undirected, unweighted, V, {seq( E[i], i=1..n-1 )} );
  if w then T := AssignEdgeWeights(T,gen); end if;
  T;
end:


RandomLevels := proc(n :: posint, m :: posint)
  local randgen, ys, t, ysl, xs, i, k;
  if n > m then
    error "The first argument should not be greater than the second one."
  fi;
  if n = 1 then return [m]; fi;
  randgen := rand(1..m-1);
  ys := [];
  k := 0;
  while k < (n - 1) do
    t := rand(1..m-k-1)();
    for i from 1 to k do
      if t >= ys[i] then t := t + 1; fi;
    od;
    while member(t, {op(ys)}) do
      t := t + 1;
    od;
    ys := [op(ys),t];
    k := k + 1;
  od;
  ysl := sort([op(ys)]);
  xs := [ysl[1]];
  for i from 2 to n - 1 do
    xs := [op(xs), ysl[i]-ysl[i-1]];
  od;
  xs := [op(xs),m-ysl[n-1]];
  return xs;
end proc:

#############################################
##PROCEDURE(doti)       RandomGraphs[RandomNetwork]
##AUTHOR                Michael Monagan
##DATE                  June 25, 2006
##
##CALLINGSEQ
##- RandomNetwork('n','p',options)
##- RandomNetwork('n','p','q',options)
##- RandomNetwork('V','p',options)
##- RandomNetwork('V','p','q',options)
##
##PARAMETERS
##- 'n'  :  positive integer
##- 'p'  :  real number between ~0.0~ and ~1.0~
##- 'V'  :  list of vertices
##- 'q'  :  real number between ~0.0~ and ~1.0~
##- options : sequence of options (see below)
##
##RETURNS
##- A randomly generated network.
##
##DESCRIPTION
##- ~RandomNetwork(n,p)~ creates a directed unweighted network on 'n' vertices.
##  The larger 'p' is, the larger the number of levels in the network will be. 
##
##- ~RandomNetwork(V,p)~ does the same thing except that the vertex labels
##  are chosen from the list ~V~.
##
##- If the option 'acyclic' is specified, a random acyclic network is created.
##
##- The user can optionally specify 'q' which is a real number between ~0.0~
##  and ~1.0~.  The result would be a random network such that each possible
##  arc is present with probability 'q'. The default value for 'q' is ~0.5~.
##
##- If the option ~weights=m..n~ is specified, where ~m <= n~ are integers,
##  the network will be a weighted graph with edge weights chosen from ~[m,n]~
##  uniformly at random.  The weight matrix ~W~ in the graph will have
##  ~datatype=integer~, and if the edge from vertex ~i~ to ~j~ is not in the
##  graph then ~W[i,j] = 0~.
##
##- If the option ~weights=x..y~ where ~x <= y~ are decimals is specified, the
##  network will be a weighted graph with numerical edge weights chosen from
##  ~[x,y]~ uniformly at random.  The weight matrix ~W~ in the graph will have
##  ~datatype=float[8]~, that is, double precision floats (16 decimal digits),
##  and if the edge from vertex ~i~ to ~j~ is not in the graph then
##  ~W[i,j] = 0.0~.
##
##- If the option ~weights=f~ where 'f' is a function (a Maple procedure) that
##  returns a number (integer, rational, or decimal number), then 'f' is used
##  to generate the edge weights.  The weight matrix ~W~ in the network will
##  have ~datatype=anything~, and if the edge from vertex ~i~ to ~j~ is not in
##  the graph then ~W[i,j] = 0~.
##
##EXAMPLES
##> with(GraphTheory):
##> with(RandomGraphs):
##> N := RandomNetwork(10, .5);
# # N := Graph 1: a directed unweighted graph with 10 vertices and 28 arc(s)
##> IsNetwork(N);
##> DrawGraph(N);
##> N := RandomNetwork([a,b,c,d,e], 0.5, acyclic);
##> DrawNetwork(N);
##> N := RandomNetwork(10, 0.2, acyclic, weights=1..5);
##> WeightMatrix(N);
##> MaxFlow(N,1,10);
##
##SEEALSO
##- "AssignEdgeWeights"
##- "GraphTheory[DrawGraph]"
##- "GraphTheory[DrawNetwork]"
##- "GraphTheory[IsNetwork]"
##- "GraphTheory[MaxFlow]"
##- "RandomBipartiteGraph"
##- "RandomDigraph"
##- "RandomGraph"
##- "RandomTournament"
##- "RandomTree"
##
##XREFMAP
##- "AssignEdgeWeights" : Help:RandomGraphs[AssignEdgeWeights]
##- "RandomBipartiteGraph" : Help:RandomGraphs[RandomBipartiteGraph]
##- "RandomDigraph" : Help:RandomGraphs[RandomDigraph]
##- "RandomGraph" : Help:RandomGraphs[RandomGraph]
##- "RandomTournament" : Help:RandomGraphs[RandomTournament]
##- "RandomTree" : Help:RandomGraphs[RandomTree]
#---------ver. 23,  modified by Mahdi

RandomNetwork := proc(V::{list(VERTEXTYPE),posint},p::nonnegative)
  local n, w, a, i, G, q, l, levels, j, node, k, nc, A, s, t , R, Q, np , RG , b, cc, gen;
  if type(V,posint) then n := V; else n := nops(V); end if;
  w , a := false , false;
  gen := NULL;
  q := 0;
  for i from 3 to nargs do
    if args[i] = 'acyclic' then a := true
    elif type(args[i],nonnegative) and q = 0 then q := args[i];
    elif type(args[i],identical('weights')=anything) then gen:=rhs(args[i]); w:=true;
    else error "invalid optional argument: %1", args[i];
    end if;
  end do;
  if q = 0 then q := 0.5; fi;
  if (q > 1) then error "Invalid argument." fi;
  if (p > 1)  then error "The second argument must not be greater than 1."; fi;
  l := round(p*(n-2))+2;
  if l < 3 then l := 3; fi;
  levels := RandomLevels(l - 2, n - 2);
  levels := [1,op(levels),1];
  nc := 0;
  A := Array(1..n);
  R := rand(10^10);
  Q := q*10^10;
  for i from 1 to l - 1 do
    t := levels[i];
    for k from 1 to t do
      s := {};
      node := nc + k;
      for j from 1 to levels[i+1] do
        if (R() < Q)  then
          np := nc + t + j;
          s :=  s union {np};
        fi;
      od;
      cc := 1;
      if (a = true) then cc := k + 1; fi;
      for j from cc to t do
        if j <> k then
          if (R() < Q) then
            np := nc + j;
            s :=  s union {np};
          fi;
        fi;
      od;
      if s = {} then
        RG := rand(1..levels[i+1]);
        np := RG();
        s := s union {np+nc+t};
      fi;
      if (a = false) and (i > 2) then
        for j from 1 to levels[i-1] do
          if (R() < Q) then
            np := nc - levels[i-1] + j;
            s :=  s union {np};
          fi;
        od;
      fi;
      A[node] := s;
    od;
    nc := nc + t;
    for j from 1 to levels[i+1] do
      b := false;
      for k from 1 to t do
        if A[nc - t + k] = nc + j then b := true; fi;
      od;
      if not b then
        RG := rand(1..t);
        np := RG();
        A[nc - t + np] := A[nc - t + np] union {nc + j};
      fi;
    od;
  od;
  A[n] := {};
  #G := GRAPHLN(directed, unweighted, listint(n), A, GRAPH_TABLE_NAME(), 0 );
  #if not type(V,posint) then G := makevertices(G,V) end if;
  G := GraphTheory:-Graph(directed, unweighted, V, A);
  if w then G := AssignEdgeWeights(G,gen); end if;
  G;
end proc:


#############################################
##PROCEDURE(doti)       RandomGraphs[RandomBipartiteGraph]
##AUTHOR                Michael Monagan
##DATE                  June 25, 2006
##
##CALLINGSEQ
##- RandomBipartiteGraph('n','p',options)
##- RandomBipartiteGraph('n','m',options)
##- RandomBipartiteGraph(['a','b'],'p',options)
##- RandomBipartiteGraph(['a','b'],'m',options)
##
##PARAMETERS
##- 'n', 'a', 'b'  :  positive integers
##- 'p'        :  real number between ~0.0~ and ~1.0~
##- 'm'        :  non-negative integer
##- options : sequence of options (see below)
##
##RETURNS
##- A randomly generated bipartite graph.
##
##DESCRIPTION
##- ~RandomBipartiteGraph(n, p)~ creates an undirected unweighted bipartite
##  graph on 'n' vertices where each possible edge is present with probability
##  'p'.
##
##- ~RandomBipartiteGraph(n, m)~ creates an undirected unweighted bipartite
##  graph on 'n' vertices and 'm' edges where the 'm' edges are chosen
##  uniformly at random.
##
##- ~RandomBipartiteGraph([a,b], p)~ creates an undirected unweighted bipartite
##  graph on ~a+b~ vertices with partite sets of sizes 'a' and 'b', where each
##  possible edge is present with probability 'p'.
##
##- ~RandomBipartiteGraph([a,b], m)~ creates an undirected unweighted bipartite
##  graph on ~a+b~ vertices with partite sets of sizes 'a' and 'b', and with
##  'm' edges chosen uniformly at random.
##
##- If the option ~weights=m..n~ is specified, where ~m <= n~ are integers,
##  the graph will be a weighted graph with edge weights chosen from ~[m,n]~
##  uniformly at random.  The weight matrix ~W~ in the graph will have
##  ~datatype=integer~, and if the edge from vertex ~i~ to ~j~ is not in the
##  graph then ~W[i,j] = 0~.
##
##- If the option ~weights=x..y~ where ~x <= y~ are decimals is specified, the
##  graph will be a weighted graph with numerical edge weights chosen from
##  ~[x,y]~ uniformly at random.  The weight matrix ~W~ in the graph will have
##  ~datatype=float[8]~, that is, double precision floats (16 decimal digits),
##  and if the edge from vertex ~i~ to ~j~ is not in the graph then
##  ~W[i,j] = 0.0~.
##
##- If the option ~weights=f~ where 'f' is a function (a Maple procedure) that
##  returns a number (integer, rational, or decimal number), then 'f' is used
##  to generate the edge weights.  The weight matrix ~W~ in the graph will have
##  ~datatype=anything~, and if the edge from vertex ~i~ to ~j~ is not in the
##  graph then ~W[i,j] = 0~.
##
##EXAMPLES
##> with(GraphTheory):
##> with(RandomGraphs):
##> G := RandomBipartiteGraph(10,0.5);
##> IsBipartite(G,'p');
##< true
##> p;
##> G := RandomBipartiteGraph([2,3], 1.0);
##> Neighbors(G);
##< [[3, 4, 5], [3, 4, 5], [1, 2], [1, 2], [1, 2]]
##> G := RandomBipartiteGraph([2,2],4,weights=1..10);
##> WeightMatrix(G);
##> H := RandomBipartiteGraph([7,11], 45);
##> ChromaticIndex(H);
##
##SEEALSO
##- "AssignEdgeWeights"
##- "GraphTheory[ChromaticIndex]"
##- "GraphTheory[IsBipartite]"
##- "GraphTheory[Neighbors]"
##- "GraphTheory[WeightMatrix]"
##- "RandomGraph"
##- "RandomDigraph"
##- "RandomNetwork"
##- "RandomTournament"
##- "RandomTree"
##
##XREFMAP
##- "AssignEdgeWeights" : Help:RandomGraphs[AssignEdgeWeights]
##- "RandomDigraph" : Help:RandomGraphs[RandomDigraph]
##- "RandomGraph" : Help:RandomGraphs[RandomGraph]
##- "RandomNetwork" : Help:RandomGraphs[RandomNetwork]
##- "RandomTournament" : Help:RandomGraphs[RandomTournament]
##- "RandomTree" : Help:RandomGraphs[RandomTree]
#---------ver. 23,  modified by MG
# MBM: needs the option "connected"

RandomBipartiteGraph := proc(N::{posint,[posint,posint]}, p::{nonnegint,nonnegative})
local m, n, M, a, b, R, pp, R1, R2, ecount, G, i, j, e, E, w, gen;

if type(N, posint) then
  if N=1 then error "number of vertices must be at least 2." fi;
  R:= rand(1..N-1);
  m := R();
  n := N-m;
  if type(p, integer) then
    while n*m < p do
      m := R();
      n := N-m;
    od;
  fi;
else
  m, n := op(N);
fi;

  w := false;
  gen:=NULL;
  for i from 3 to nargs do
    if type(args[i],identical('weights')=anything) then gen:=rhs(args[i]); w:=true;
    else error "invalid optional argument: %1", args[i];
    end if;
  end do;

M := Matrix(m, n, storage=sparse);
if type(p, integer) then
  if p>m*n then error "number of edges %1 must be less than %2 times %3", p, m, n; fi;
  ecount := 0;
  R1, R2 := rand(1..m), rand(1..n);
  if p<m*n/2 then # add p edges
     while ecount < p do
       a, b := R1(), R2();
       if M[a,b]=0 then M[a,b] := 1; ecount := ecount+1; fi;
     od;
  else # p>m*n/2 so remove m*n-p edges
     for i to m do for j to n do M[i,j] := 1 od; od;
     while ecount < m*n-p do
       a, b := R1(), R2();
       if M[a,b]=1 then M[a,b] := 0; ecount := ecount+1; fi;
     od;
  fi;
else
  if p>1 then error "invalid probability: %1", p; fi;
  R := rand(10^5);
  pp := p*10^5;
  for a to m do for b to n do
    if R() <= pp then
      M[a,b] := 1;
    fi;
  od od;
fi;

# E := {seq( [lhs(e)]+[0,m], e=op(2,M) )}; # MBM: generates an error in Maple 10
#E := [seq( [lhs(e),NULL]+[0,m], e=op(2,M) )]; # MBM: but this doesn't !!??
E := [seq( [op([1,1],e),op([1,2],e)+m], e=op(2,M) )]; # ADW: This should work always
E := {seq( {op(e)}, e=E )};
G := GraphTheory:-Graph( [$1..m+n], E ); # MBM: most of the time is here
if w then G := AssignEdgeWeights(G,gen); fi;

G;

end proc;
end module:
#savelib('RandomGraphs');