randomGraph/gengraph.ml at master · d-kmr/randomGraph · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
(* Options *)
let size = ref 0;; (* number of nodes *)
let undirected = ref false;;
let set_undirected () = undirected := true;;
let weightnum = ref 1;;
let set_weightnum n = weightnum := n;;
let dense = ref 5;;
let set_dense n = dense := n;;
let f_help () = print_endline "help";;

let speclist = [
    ("-u", Arg.Unit set_undirected, "generate an undirected graph");
    ("-d", Arg.Int set_dense, "set denseness of graphs [0:sparse .. 9:dense] (default = 5)");
    ("-w", Arg.Int set_weightnum, "set number of weights of edges (default = 1)");
  ];;

let msgUsage = "USAGE: gengraph <number> [options]"
;;

let usage_and_exit () =
  Arg.usage speclist msgUsage;
  exit 0
;;

let getsize nStr =
  try
    size := int_of_string nStr
  with
    _ ->
    print_endline "Illegal input";
    usage_and_exit ()
;;

let string_of_list sep to_string ls =
  List.fold_left (fun str x -> if str = "" then to_string x else str ^ sep ^ (to_string x)) "" ls
;;

type weights = int list;;  (* [1;2;3] is on an edge *)
type graph = weights array array;;

let existEdge () =
  let num = !dense - Random.int 10 in
  if num >= 0 then true else false
;;

let generate_directedgraph () =
  let empty:weights = [] in
  let graph = Array.make_matrix !size !size empty in
  for i = 0 to !size-1 do
    for j = 0 to !size-1 do
      match existEdge () with
      | true  ->
         for k = 0 to !weightnum-1 do
           graph.(i).(j) <- (1+Random.int 20) :: graph.(i).(j)
         done
      | false -> ()
    done;
  done;
  graph
;;

let generate_undirectedgraph () : graph =
  let empty:weights = [] in
  let g = Array.make_matrix !size !size empty in
  for i = 0 to !size-1 do
    for j = i to !size-1 do
      match existEdge () with
      | true  ->
         for k = 0 to !weightnum-1 do
           g.(i).(j) <- (1+Random.int 20) :: g.(i).(j);
           g.(j).(i) <- g.(i).(j)
         done
      | false -> ()
    done;
  done;
  g
;;

let print_matrix (g: graph) =
  for i = 0 to !size-1 do
    for j = 0 to !size-1 do
      let weight = g.(i).(j) in
      let weightStr = string_of_list "," string_of_int weight in
      Printf.printf "[%s] " weightStr
    done;
    print_endline "";
  done
;;

let to_string_undirected (g:graph): string =
  let str = ref "undirected\n" in
  for i = 0 to !size-1 do
    for j = i to !size-1 do
      if g.(i).(j) = [] then ()
      else
        str := !str ^ "(" ^ (string_of_int i) ^ "," ^ (string_of_int j) ^ "," ^ (string_of_list "," string_of_int g.(i).(j)) ^ ")\n";
    done;
  done;
  !str
;;

let to_string_directed (g:graph): string =
  let str = ref "directed\n" in
  for i = 0 to !size-1 do
    for j = 0 to !size-1 do
      if g.(i).(j) = [] then ()
      else
        str := !str ^ "(" ^ (string_of_int i) ^ "," ^ (string_of_int j) ^ "," ^ (string_of_list "," string_of_int g.(i).(j)) ^ ")\n";
    done;
  done;
  !str
;;


let () =
  Random.self_init ();
  Arg.parse speclist getsize msgUsage;
  if !size = 0 then usage_and_exit () else ();

  let (graph,output) =
    match !undirected with
    | true  ->
       let grp = generate_undirectedgraph () in
       let str = to_string_undirected grp in
       (grp,str)
    | false ->
       let grp = generate_directedgraph () in
       let str = to_string_directed grp in
       (grp,str)
  in
  (* print_matrix graph; *)
  print_endline output
;;