GraphProver-benchmarks/test-Graph.lua at master · TecMF/GraphProver-benchmarks · 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
134
135
136
137
138
139
140
141
142
143
144
145
146
#!/usr/bin/env lua
local arg = arg
local assert = assert
local io = io
local ipairs = ipairs
local math = math
local os = os
local pairs = pairs
local print = print
local table = table
local tonumber = tonumber
local tostring = tostring

require'Logic.Graph'
local Graph = assert (Graph)
local Node = assert (Node)
local Edge = assert (Edge)

_ENV = nil

local function usage ()
   io.stderr:write (('usage: %s [-d] NUM_V NUM_E X\n'):format (arg[0]))
   os.exit (1)
end

local NUM_V
local NUM_E
local X
local DEBUG = false
do
   if #arg < 3 or #arg > 4 then
      usage ()
   end
   if arg[1] == '-d' then
      DEBUG = true
      table.remove (arg, 1)
   end
   NUM_V = tonumber (arg[1])
   assert (NUM_V and NUM_V > 0, 'bad NUM_V')
   NUM_E = tonumber (arg[2])
   assert (NUM_E and NUM_E > 0, 'bad NUM_E')
   X = tonumber (arg[3])
   assert (X and X >= 0. and X <= 1., 'bad X')
   math.randomseed (os.time ())
   if NUM_V > 32000 or NUM_E > 32000 then -- taking too long
      os.exit (0)
   end
end

local function dump (G)
   local nodes = G:getNodes ()
   local edges = G:getEdges () or {}
   print (('graph %s: %d vertices, %d edges')
         :format (tostring (G), #nodes, #edges))
   for _,e in ipairs (edges) do
      print (('  %s:(%s,%s)'):format
         (tostring (e),
          e:getOrigem ():getLabel (),
          e:getDestino ():getLabel ()))
   end
end

local function add_random_nodes (G, n)
   local nodes = G:getNodes () or {}
   local vcount = #nodes
   for i=1,n do
      nodes[#nodes+1] = Node:new (tostring (vcount + i), 0, 0)
   end
   G:addNodes (nodes)
end

local function add_random_edges (G, n)
   local nodes = G:getNodes ()
   local edges = {}
   for i=1,n do
      local from = nodes[math.random (1,#nodes)]
      local to = nodes[math.random (1,#nodes)]
      edges[#edges+1]=Edge:new (tostring (i), from, to)
   end
   G:addEdges (edges)
end

local function del_random_edges (G, n)
   for i=1,n do
      local edges = G:getEdges () or {}
      local e = edges[math.random (1,#edges)]
      if DEBUG then
         print (('--> delete %s:(%s,%s)')
               :format (tostring (e),
                        e:getOrigem ():getLabel (),
                        e:getDestino ():getLabel ()))
      end
      G:removeEdge (e)
   end
end

local function search_random_edges (G, n)
   local nodes = G:getNodes ()
   local edges = G:getEdges ()
   for i=1,n do
      local from = nodes[math.random (1,#nodes)]
      local to = nodes[math.random (1,#nodes)]
      local found = nil
      for _,e in ipairs (edges) do
         if e:getOrigem () == from and e:getDestino () == to then
            found = e
            break
         end
      end
      if DEBUG then
         if found then
            print (('--> found %s:(%s,%s)')
                  :format (tostring (found),
                           from:getLabel (),
                           to:getLabel ()))
         else
            print (('--> not found (%s,%s)')
                  :format (from:getLabel (), to:getLabel ()))
         end
      end
   end
end

-- Main.
do
   local G = Graph:new ()
   assert (G)

   add_random_nodes (G, NUM_V)
   add_random_edges (G, NUM_E)
   add_random_nodes (G, NUM_V * X)
   add_random_edges (G, NUM_E * X)

   if DEBUG then
      print'\nInitial graph:'
      dump (G)
   end

   search_random_edges (G, NUM_E * X)
   del_random_edges (G, NUM_E * X)

   if DEBUG then
      print'\nFinal graph:'
      dump (G);
   end
end