program ErdosRenyi;
{ Large Erdos-Renyi random graphs generator
  by Vladimir Batagelj
  Ljubljana, 21. February / 7. March 2002 }
{$APPTYPE CONSOLE}
uses
  SysUtils;
const
  gtype: array [1..7] of string = (
    'undirected', 'directed', 'acyclic', 'undirected bipartite',
    'directed bipartite', 'acyclic bipartite', '2-mode' );
  lines: array [1..7] of string = (
    'edges', 'arcs', 'arcs', 'edges', 'arcs', 'arcs', 'edges' );
var
  StartTime, FinishTime : Comp;
  rep, net : TextFile;
  m, leng, f, half : LongInt;
  n, k, s, u, v, n1, t, w : integer;
  p, q, lq, dega : extended;
  tg : string;
begin
  AssignFile(rep,'report.txt'); Rewrite(rep);
  AssignFile(net,'random.net'); Rewrite(net);
  Randomize;
  writeln('Erdos-Renyi random graph generator 2');
  writeln('©2002 V. Batagelj');
  write('number of vertices = '); readln(n);
  writeln('type:');
  writeln(' 1-u , 2-d , 3-a , 4-ub, 5-db, 6-ab, 7-2m');
  write('type               = '); readln(t);
  if t > 3 then begin
    write('number of vertices in V1 = '); readln(n1);
  end else n1 := 0;
  write('average degree = '); readln(dega);
  writeln(rep,'n = ',n:5,' n1 = ',n1:5,' d = ',dega:9:5);
  writeln(rep,gtype[t]);
 { determine parameters }
  case t of
   1, 3 : begin f := 1; u := 2; leng := n*(n-1) div 2; w := n-1; end;
   2: begin f := 0; u := 0; leng := n*(n-1); w := n-1; end;
   4, 6, 7 : begin f := 0; u := 0; leng := n1*(n-n1); w := n-n1; end;
   5 : begin f := 0; u := 0; half := n1*(n-n1); leng := 2*half; w := n-n1; end;
  end;
  p := dega/w;
  StartTime := TimeStampToMSecs(DateTimeToTimeStamp(Time));
  q := 1 - p;
 { generate a random graph }
  write(net,'*vertices ',n);
  if t=7 then writeln(net,' ',n1) else writeln(net);
  writeln(net,'% Pajek: random ',gtype[t],' graph / p = ', p:9:7);
  k := 0; lq := ln(q); m := 0;
  writeln(net,'*',lines[t]);
  writeln(rep,'leng = ', leng:7);
  writeln(rep,'E(m) = ', leng*p:11:3);
  writeln(rep);
  while k < leng do begin
    s := 1 + trunc( ln(1 - random) / lq );
    k := k + s; m := m + 1;
    write(rep, m:5, s:5, k:8);
    if k > leng then writeln(rep)
    else begin
      case t of
      1, 3 : begin
           while f < k do begin f := f+u; u := u+1 end;
           v := k+u-f-1;
         end;
      2: begin
           while f < k do begin f := f+w; u := u+1 end;
           v := k+w-f; if v >= u then v := v+1
         end;
      4, 6, 7 : begin
           while f < k do begin f := f+w; u := u+1 end;
           v := n1+k+w-f;
         end;
      5 : begin
           if k <= half then begin
             while f < k do begin f := f+w; u := u+1 end;
             v := n1+k+w-f;
           end else begin
             while f < k do begin f := f+n1; u := u+1 end;
             v := k+n1-f;
           end;
         end;
      end;
      writeln(rep,u:8,v:7);
      writeln(net,' ',u,' ',v);
    end;
  end;
  FinishTime := TimeStampToMSecs(DateTimeToTimeStamp(Time));
  writeln(rep,'m = ',m-1:5);
  writeln(FinishTime-StartTime:10:2,'ms spent');
  writeln(rep,FinishTime-StartTime:10:2,'ms spent');
  CloseFile(rep); CloseFile(net);
  writeln('done, press ENTER'); readln;
end.