summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/BoyerMyrvold2004.lua
blob: f587861d79d981455846acd4eddf6a29eb850bed (plain)
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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678

--[[
---Data structures---

Vertices from the original ugraph are referred to as input vertices.
The tables that contain vertex data relevant to the algorithm
are referred to as vertices.
A vertex table may have the following keys:

-sign
1 or -1, indicates whether this and all in the depth-first search
following vertices must be considered flipped
(i. e. adjacency lists reversed) in respect to the dfs parent

-childlist
A linked list containing all dfs children of the vertex whose virtual roots
have not yet been merged into the vertex, sorted by lowpoint

-adjlistlinks
A table with two fields with keys 0 and 1, containing the two half edges
of the vertex which lie on the external face of the graph
(if the vertex lies on the external face).
The half edge with key 0 lies in the 0-direction of the other half edge
and vice-versa
The two fields may hold the same half edge, if the vertex has degree one

-pertinentroots
A linked list containing all virtual roots of this vertex that are
pertinent during the current step

-inputvertex
The input vertex that corresponds to the vertex

-dfi
The depth-first search index (number of the step in the dfs at which
the vertex was discovered)

-dfsparent
The depth-first search parent (vertex from which the vertex was discovered
first in the dfs)

-leastancestor
Dfi of the vertex with lowest dfi that can be reached using one back edge
(non-tree edge)

-lowpoint
Dfi of the vertex with lowest dfi that can be reached using any number of
tree edges plus one back edge


A root vertex is a virtual vertex not contained in the original ugraph.
The root vertex represents another vertex in a biconnected component (block)
which is a child of the biconnected component the represented vertex is in.
The only field that it has in common with other vertices is the
adjacency list links array:

-isroot
always true, indicates that this vertex is a virtual root

-rootparent
The vertex which this root represents

-rootchild
The only dfs child of the original vertex which is contained in the
root verticis biconnected component

-adjlistlinks
See adjlistlinks of a normal vertex


A half edge is a table with the following fields:

-links
A table with two fields with keys 0 and 1, containing the neighboring
half edges in the adjacency list of the vertex these edges originate from.

-target
The vertex the half edge leads to

-twin
The twin half edge which connects the two vertices in the opposite direction

-shortcircuit
True if the half edge was inserted in order to make a short circuit for the
algorithm. The edge will be removed at the end.

The BoyerMyrvold2004 class has the following fields:

-inputgraph
The original ugraph given to the algorithm

-numvertices
The number of vertices of the graph

-vertices
The vertex table with depth-first search indices as keys

-verticesbyinputvertex
The vertex table with input vertices as keys

-verticesbylowpoint
The vertex table with low points as keys

-shortcircuitedges
An array of all short circuit half edges
(which may not be in the original graph and will be removed at the end)

--]]

local BM = {}
require("pgf.gd.planar").BoyerMyrvold2004 = BM

-- imports
local Storage = require "pgf.gd.lib.Storage"
local LinkedList = require "pgf.gd.planar.LinkedList"
local Embedding = require "pgf.gd.planar.Embedding"

-- create class properties
BM.__index = BM

function BM.new()
  local t = {}
  setmetatable(t, BM)
  return t
end

-- initializes some data structures at the beginning
-- takes the ugraph of the layout algorithm as input
function BM:init(g)
  self.inputgraph = g
  self.numvertices = #g.vertices
  self.vertices = {}
  self.verticesbyinputvertex = Storage.new()
  self.verticesbylowpoint = Storage.newTableStorage()
  self.shortcircuitedges = {}
  for _, inputvertex in ipairs(self.inputgraph.vertices) do
    local vertex = {
      sign = 1,
      childlist = LinkedList.new(),
      adjlistlinks = {},
      pertinentroots = LinkedList.new(),
      inputvertex = inputvertex,
    }
    setmetatable(vertex, Embedding.vertexmetatable)
    self.verticesbyinputvertex[inputvertex] = vertex
  end
end

--[[
local function nilmax(a, b)
  if a == nil then return b end
  if b == nil then return a end
  return math.max(a, b)
end

local function nilmin(a, b)
  if a == nil then return b end
  if b == nil then return a end
  return math.min(a, b)
end
--]]

-- the depth-first search of the preprocessing
function BM:predfs(inputvertex, parent)
  local dfi = #self.vertices + 1
  local vertex = self.verticesbyinputvertex[inputvertex]
  self.vertices[dfi] = vertex
  -- set the dfs infos in the vertex
  vertex.dfi = dfi
  vertex.dfsparent = parent
  vertex.leastancestor = dfi
  vertex.lowpoint = dfi
  -- find neighbors
  for _, arc in ipairs(self.inputgraph:outgoing(inputvertex)) do
    local ninputvertex = arc.head
    assert(ninputvertex ~= inputvertex, "Self-loop detected!")
    local nvertex = self.verticesbyinputvertex[ninputvertex]
    if nvertex.dfi == nil then
      -- new vertex discovered
      self:predfs(ninputvertex, vertex) -- recursive call
      vertex.lowpoint = math.min(vertex.lowpoint, nvertex.lowpoint)
    elseif parent and ninputvertex ~= parent.inputvertex then
      -- back edge found
      vertex.leastancestor = math.min(vertex.leastancestor, nvertex.dfi)
      vertex.lowpoint = math.min(vertex.lowpoint, nvertex.dfi)
    end
  end
  -- put vertex into lowpoint sort bucket
  table.insert(self.verticesbylowpoint[vertex.lowpoint], vertex)
end

-- the preprocessing at the beginning of the algorithm
-- does the depth-first search and the bucket sort for the child lists
function BM:preprocess()
  -- make dfs starting at an arbitrary vertex
  self:predfs(self.inputgraph.vertices[1])
  -- create separated child lists with bucket sort
  for i = 1, self.numvertices do
    for _, vertex in ipairs(self.verticesbylowpoint[i]) do
      if vertex.dfsparent then
        vertex.childlistelement
            = vertex.dfsparent.childlist:addback(vertex)
      end
    end
  end
end

-- adds tree edges and the corresponding virtual root vertices
-- of the currentvertex
function BM:add_trivial_edges(vertex)
  -- find all dfs children
  for _, arc in ipairs(self.inputgraph:outgoing(vertex.inputvertex)) do
    local nvertex = self.verticesbyinputvertex[arc.head]
    if nvertex.dfsparent == vertex then
      -- create root vertex
      local rootvertex = {
        isroot = true,
        rootparent = vertex,
        rootchild = nvertex,
        adjlistlinks = {},
        name = tostring(vertex) .. "^" .. tostring(nvertex)
      }
      setmetatable(rootvertex, Embedding.vertexmetatable)
      nvertex.parentroot = rootvertex
      -- create half edges
      local halfedge1 = {target = nvertex, links = {}}
      local halfedge2 = {target = rootvertex, links = {}}
      halfedge1.twin = halfedge2
      halfedge2.twin = halfedge1
      -- create circular adjacency lists
      halfedge1.links[0] = halfedge1
      halfedge1.links[1] = halfedge1
      halfedge2.links[0] = halfedge2
      halfedge2.links[1] = halfedge2
      -- create links to adjacency lists
      rootvertex.adjlistlinks[0] = halfedge1
      rootvertex.adjlistlinks[1] = halfedge1
      nvertex.adjlistlinks[0] = halfedge2
      nvertex.adjlistlinks[1] = halfedge2
    end
  end
end

-- for the external face vertex which was entered through link vin
-- returns the successor on the external face and the link through
-- which it was entered
local function get_successor_on_external_face(vertex, vin)
  local halfedge = vertex.adjlistlinks[1 - vin]
  local svertex = halfedge.target
  local sin
  if vertex.adjlistlinks[0] == vertex.adjlistlinks[1] then
    sin = vin
  elseif svertex.adjlistlinks[0].twin == halfedge then
    sin = 0
  else
    sin = 1
  end
  return svertex, sin
end

-- the "walkup", used to identify the pertinent subgraph,
-- i. e. the subgraph that contains end points of backedges
-- for one backedge this function will mark all virtual roots
-- as pertinent that lie on the path between the backedge and the current vertex
-- backvertex: a vertex that is an endpoint of a backedge to the current vertex
-- currentvertex: the vertex of the current step
-- returns a root vertex of the current step, if one was found
local function walkup(backvertex, currentvertex)
  local currentindex = currentvertex.dfi
  -- set the backedgeflag
  backvertex.backedgeindex = currentindex
  -- initialize traversal variables for both directions
  local x, xin, y, yin = backvertex, 1, backvertex, 0
  while x ~= currentvertex do
    if x.visited == currentindex or y.visited == currentindex then
      -- we found a path that already has the pertinent roots marked
      return nil
    end
    -- mark vertices as visited for later calls
    x.visited = currentindex
    y.visited = currentindex

    -- check for rootvertex
    local rootvertex
    if x.isroot then
      rootvertex = x
    elseif y.isroot then
      rootvertex = y
    end
    if rootvertex then
      local rootchild = rootvertex.rootchild
      local rootparent = rootvertex.rootparent
      if rootvertex.rootparent == currentvertex then
        -- we found the other end of the back edge
        return rootvertex
      elseif rootchild.lowpoint < currentindex then
        -- the block we just traversed is externally active
        rootvertex.pertinentrootselement
            = rootparent.pertinentroots:addback(rootvertex)
      else
        -- the block we just traversed is internally active
        rootvertex.pertinentrootselement
            = rootparent.pertinentroots:addfront(rootvertex)
      end
      -- jump to parent block
      x, xin, y, yin = rootvertex.rootparent, 1, rootvertex.rootparent, 0
    else
      -- just continue on the external face
      x, xin = get_successor_on_external_face(x, xin)
      y, yin = get_successor_on_external_face(y, yin)
    end
  end
end

-- inverts the adjacency of a vertex
-- i. e. reverses the order of the adjacency list and flips the links
local function invert_adjacency(vertex)
  -- reverse the list
  for halfedge in Embedding.adjacency_iterator(vertex.adjlistlinks[0]) do
    halfedge.links[0], halfedge.links[1]
        = halfedge.links[1], halfedge.links[0]
  end
  -- flip links
  vertex.adjlistlinks[0], vertex.adjlistlinks[1]
      = vertex.adjlistlinks[1], vertex.adjlistlinks[0]
end

-- merges two blocks by merging the virtual root of the child block
-- into it's parent, while making sure the external face stays consistent
-- by flipping the root block if needed
-- mergeinfo contains four fields:
-- root - the virtual root vertex
-- parent - it's parent
-- rout - the link of the root through which we have exited it
--        during the walkdown
-- pin - the link of the parent through which we have entered it
--       during the walkdown
local function mergeblocks(mergeinfo)
  local root = mergeinfo.root
  local parent = mergeinfo.parent
  local rout = mergeinfo.rootout
  local pin = mergeinfo.parentin
  if pin == rout then
    -- flip required
    invert_adjacency(root)
    root.rootchild.sign = -1
    --rout = 1 - rout -- not needed
  end

  -- redirect edges of the root vertex
  for halfedge in Embedding.adjacency_iterator(root.adjlistlinks[0]) do
    halfedge.twin.target = parent
  end

  -- remove block from data structures
  root.rootchild.parentroot = nil
  parent.pertinentroots:remove(root.pertinentrootselement)
  parent.childlist:remove(root.rootchild.childlistelement)

  -- merge adjacency lists
  parent.adjlistlinks[0].links[1] = root.adjlistlinks[1]
  parent.adjlistlinks[1].links[0] = root.adjlistlinks[0]
  root.adjlistlinks[0].links[1] = parent.adjlistlinks[1]
  root.adjlistlinks[1].links[0] = parent.adjlistlinks[0]
  parent.adjlistlinks[pin] = root.adjlistlinks[pin]
end

-- inserts a half edge pointing to "to" into the adjacency list of "from",
-- replacing the link "linkindex"
local function insert_half_edge(from, linkindex, to)
  local halfedge = {target = to, links = {}}
  halfedge.links[    linkindex] = from.adjlistlinks[    linkindex]
  halfedge.links[1 - linkindex] = from.adjlistlinks[1 - linkindex]
  from.adjlistlinks[    linkindex].links[1 - linkindex] = halfedge
  from.adjlistlinks[1 - linkindex].links[    linkindex] = halfedge
  from.adjlistlinks[linkindex] = halfedge
  return halfedge
end

-- connect the vertices x and y through the links xout and yin
-- if shortcircuit is true, the edge will be marked as a short circuit edge
-- and removed at the end of the algorithm
function BM:embed_edge(x, xout, y, yin, shortcircuit)
  -- create half edges
  local halfedgex = insert_half_edge(x, xout, y)
  local halfedgey = insert_half_edge(y, yin, x)
  halfedgex.twin = halfedgey
  halfedgey.twin = halfedgex
  -- short circuit handling
  if shortcircuit then
    halfedgex.shortcircuit = true
    halfedgey.shortcircuit = true
    table.insert(self.shortcircuitedges, halfedgex)
    table.insert(self.shortcircuitedges, halfedgey)
  end
end

-- returns true if the given vertex is pertinent at the current step
local function pertinent(vertex, currentindex)
  return vertex.backedgeindex == currentindex
      or not vertex.pertinentroots:empty()
end

-- returns true if the given vertex is externally active at the current step
local function externally_active(vertex, currentindex)
  return vertex.leastancestor < currentindex
      or (not vertex.childlist:empty()
      and vertex.childlist:first().lowpoint < currentindex)
end

-- the "walkdown", which merges the pertinent subgraph and embeds
-- back and short circuit edges
-- childrootvertex - a root vertex of the current vertex
--                   which the walkdown will start at
-- currentvertex - the vertex of the current step
function BM:walkdown(childrootvertex, currentvertex)
  local currentindex = currentvertex.dfi
  local mergestack = {}
  local numinsertededges = 0 -- to return the number for count check
  -- two walkdowns into both directions
  for vout = 0,1 do
    -- initialize the traversal variables
    local w, win = get_successor_on_external_face(childrootvertex, 1 - vout)
    while w ~= childrootvertex do
      if w.backedgeindex == currentindex then
        -- we found a backedge endpoint
        -- merge all pertinent roots we found
        while #mergestack > 0 do
          mergeblocks(table.remove(mergestack))
        end
        -- embed the back edge
        self:embed_edge(childrootvertex, vout, w, win)
        numinsertededges = numinsertededges + 1
        w.backedgeindex = 0 -- this shouldn't be necessary
      end
      if not w.pertinentroots:empty() then
        -- we found a pertinent vertex with child blocks
        -- create merge info for the later merge
        local mergeinfo = {}
        mergeinfo.parent = w
        mergeinfo.parentin = win
        local rootvertex = w.pertinentroots:first()
        mergeinfo.root = rootvertex
        -- check both directions for active vertices
        local x, xin = get_successor_on_external_face(rootvertex, 1)
        local y, yin = get_successor_on_external_face(rootvertex, 0)
        local xpertinent = pertinent(x, currentindex)
        local xexternallyactive = externally_active(x, currentindex)
        local ypertinent = pertinent(y, currentindex)
        local yexternallyactive = externally_active(y, currentindex)
        -- chose the direction with the best vertex
        if xpertinent and not xexternallyactive then
          w, win = x, xin
          mergeinfo.rootout = 0
        elseif ypertinent and not yexternallyactive then
          w, win = y, yin
          mergeinfo.rootout = 1
        elseif xpertinent then
          w, win = x, xin
          mergeinfo.rootout = 0
        else
          w, win = y, yin
          mergeinfo.rootout = 1
        end
        -- this is what the paper says, but it might cause problems
        -- not sure though...
        --[[if w == x then
            mergeinfo.rootout = 0
        else
            mergeinfo.rootout = 1
        end--]]
        table.insert(mergestack, mergeinfo)
      elseif not pertinent(w, currentindex)
          and not externally_active(w, currentindex) then
        -- nothing to see here, just continue on the external face
        w, win = get_successor_on_external_face(w, win)
      else
        -- this is a stopping vertex, walkdown will end here
        -- paper puts this into the if,
        -- but this should always be the case, i think
        assert(childrootvertex.rootchild.lowpoint < currentindex)
        if #mergestack == 0 then
          -- we're in the block we started at, so we embed a back edge
          self:embed_edge(childrootvertex, vout, w, win, true)
        end
        break
      end
    end
    if #mergestack > 0 then
      -- this means, there is a pertinent vertex blocked by stop vertices,
      -- so the graph is not planar and we can skip the second walkdown
      break
    end
  end
  return numinsertededges
end

-- embeds the back edges for the current vertex
-- walkup and walkdown are called from here
-- returns true, if all back edges could be embedded
function BM:add_back_edges(vertex)
  local pertinentroots = {} -- not in the paper
  local numbackedges = 0
  -- find all back edges to vertices with lower dfi
  for _, arc in ipairs(self.inputgraph:outgoing(vertex.inputvertex)) do
    local nvertex = self.verticesbyinputvertex[arc.head]
    if nvertex.dfi > vertex.dfi
        and nvertex.dfsparent ~= vertex
        and nvertex ~= vertex.dfsparent then
      numbackedges = numbackedges + 1
      -- do the walkup
      local rootvertex = walkup(nvertex, vertex)
      if rootvertex then
        -- remember the root vertex the walkup found, so we don't
        -- have to call the walkdown for all root vertices
        -- (or even know what the root vertices are)
        table.insert(pertinentroots, rootvertex)
      end
    end
  end
  -- for all root vertices the walkup found
  local insertededges = 0
  while #pertinentroots > 0 do
    -- do the walkdown
    insertededges = insertededges
        + self:walkdown(table.remove(pertinentroots), vertex)
  end
  if insertededges ~= numbackedges then
    -- not all back edges could be embedded -> graph is not planar
    return false
  end
  return true
end

-- the depth-first search of the postprocessing
-- flips the blocks according to the sign field
function BM:postdfs(vertex, sign)
  sign = sign or 1
  local root = vertex.parentroot
  if root then
    sign = 1
  else
    sign = sign * vertex.sign
  end

  if sign == -1 then
    -- number of flips is odd, so we need to flip here
    invert_adjacency(vertex)
  end

  -- for all dfs children
  for _, arc in ipairs(self.inputgraph:outgoing(vertex.inputvertex)) do
    local nvertex = self.verticesbyinputvertex[arc.head]
    if nvertex.dfsparent == vertex then
      -- recursive call
      self:postdfs(nvertex, sign)
    end
  end
end

-- the postprocessing at the end of the algorithm
-- calls the post depth-first search,
-- removes the short circuit edges from the adjacency lists,
-- adjusts the links of the vertices,
-- merges root vertices
-- and cleans up the vertices
function BM:postprocess()
  -- flip components
  self:postdfs(self.vertices[1])

  -- unlink the short circuit edges
  for _, halfedge in ipairs(self.shortcircuitedges) do
    halfedge.links[0].links[1] = halfedge.links[1]
    halfedge.links[1].links[0] = halfedge.links[0]
  end

  -- vertex loop
  local rootvertices = {}
  local edgetoface = {}
  for _, vertex in ipairs(self.vertices) do
    -- check for root vertex and save it
    local root = vertex.parentroot
    if root then
      table.insert(rootvertices, root)
    end

    -- clean up links and create adjacency matrix
    local link = vertex.adjlistlinks[0]
    local adjmat = {}
    vertex.adjmat = adjmat
    if link then
      -- make sure the link points to a half edge
      -- that is no short circuit edge
      while link.shortcircuit do
        link = link.links[0]
      end
      -- create link
      vertex.link = link

      -- create adjacency matrix
      for halfedge in Embedding.adjacency_iterator(link) do
        setmetatable(halfedge, Embedding.halfedgemetatable)
        local target = halfedge.target
        if target.isroot then
          target = target.rootparent
        end
        adjmat[target] = halfedge
      end
    end

    -- clean up vertex
    vertex.sign = nil
    vertex.childlist = nil
    vertex.adjlistlinks = nil
    vertex.pertinentroots = nil
    vertex.dfi = nil
    vertex.dfsparent = nil
    vertex.leastancestor = nil
    vertex.lowpoint = nil
    vertex.parentroot = nil
  end

  -- root vertex loop
  for _, root in ipairs(rootvertices) do
    -- make sure the links point to a half edges
    -- that are no short circuit edge
    local link = root.adjlistlinks[0]
    while link.shortcircuit do
        link = link.links[0]
    end

    -- merge into parent
    local rootparent = root.rootparent
    local parentlink = rootparent.link
    local adjmat = rootparent.adjmat
    for halfedge in Embedding.adjacency_iterator(link) do
      setmetatable(halfedge, Embedding.halfedgemetatable)
      halfedge.twin.target = rootparent
      adjmat[halfedge.target] = halfedge
    end
    if parentlink == nil then
      assert(rootparent.link == nil)
      rootparent.link = link
    else
      -- merge adjacency lists
      parentlink.links[0].links[1] = link
      link.links[0].links[1] = parentlink
      local tmp = link.links[0]
      link.links[0] = parentlink.links[0]
      parentlink.links[0] = tmp
    end
  end
end

-- the entry point of the algorithm
-- returns the array of vertices
-- the vertices now only contain the inputvertex field
-- and a field named "link" which contains an arbitrary half edge
-- from the respective adjacency list
-- the adjacency lists are in a circular order in respect to the plane graph
function BM:run()
  self:preprocess()
  -- main loop over all vertices from lowest dfi to highest
  for i = self.numvertices, 1, -1 do
    local vertex = self.vertices[i]
    self:add_trivial_edges(vertex)
    if not self:add_back_edges(vertex) then
      -- graph not planar
      return nil
    end
  end
  self:postprocess()
  local embedding = Embedding.new()
  embedding.vertices = self.vertices
  return embedding
end

return BM