summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PlanarLayout.lua
blob: 9e5b8d72ec021dd61ac07906635aef529c427439 (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


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

-- imports
local Coordinate = require "pgf.gd.model.Coordinate"
local Storage = require "pgf.gd.lib.Storage"
local BoyerMyrvold = require "pgf.gd.planar.BoyerMyrvold2004"
local ShiftMethod = require "pgf.gd.planar.ShiftMethod"
local Embedding = require "pgf.gd.planar.Embedding"
local PDP = require "pgf.gd.planar.PDP"
local InterfaceToAlgorithms = require("pgf.gd.interface.InterfaceToAlgorithms")
local createEdge = InterfaceToAlgorithms.createEdge
local createVertex = InterfaceToAlgorithms.createVertex

InterfaceToAlgorithms.declare {
  key = "planar layout",
  algorithm = PlanarLayout,
  preconditions = {
    connected = true,
    loop_free = true,
    simple    = true,
  },
  postconditions = {
    fixed = true,
  },
  summary = [["
    The planar layout draws planar graphs without edge crossings.
  "]],
  documentation = [["
    The planar layout is a pipeline of algorithms to produce
    a crossings-free drawing of a planar graph.
    First a combinatorical embedding of the graph is created using
    the Algorithm from Boyer and Myrvold.
    The combinatorical Embedding is then being improved by
    by the Sort and Flip algorithm and triangulated afterwards.
    To determine the actual node positions the shift method
    by de Fraysseix, Pach and Pollack is used.
    Finally the force based Planar Drawing Postprocessing improves the drawing.
  "]],
  examples = {
    [["
      \tikz \graph [nodes={draw, circle}] {
          a -- {
              b -- {
                  d -- i,
                  e,
                  f
              },
              c -- {
                  g,
                  h
              }
          },
          f --[no span edge] a,
          h --[no span edge] a,
          i --[no span edge] g,
          f --[no span edge] g,
          c --[no span edge] d,
          e --[no span edge] c
      }
    "]]
  }
}

function PlanarLayout:run()
  --local file = io.open("timing.txt", "a")

  local options = self.digraph.options

  -- get embedding
  local bm = BoyerMyrvold.new()
  bm:init(self.ugraph)
  local embedding = bm:run()

  assert(embedding, "Graph is not planar")

  --local start = os.clock()
  if options["use sf"] then
    embedding:improve()
  end

  -- choose external face
  local exedge, exsize = embedding:get_biggest_face()

  -- surround graph with triangle
  local v1, v2, vn = embedding:surround_by_triangle(exedge, exsize)

  -- make maximal planar
  embedding:triangulate()

  if options["show virtual"] then
    -- add virtual vertices to input graph
    for _, vertex in ipairs(embedding.vertices) do
      if vertex.virtual then
        vertex.inputvertex = createVertex(self, {
          name = nil,--vertex.name,
          generated_options = {},
          text = vertex.name
        })
        vertex.virtual = false
      end
    end

    -- add virtual edges to input graph
    for _, vertex in ipairs(embedding.vertices) do
      for halfedge in Embedding.adjacency_iterator(vertex.link) do
        if halfedge.virtual then
          createEdge(
            self,
            vertex.inputvertex,
            halfedge.target.inputvertex
          )
        end
        halfedge.virtual = false
      end
    end
  end

  -- create canonical ordering
  local order = embedding:canonical_order(v1, v2, vn)

  local sm = ShiftMethod.new()
  sm:init(order)
  local gridpos = sm:run()

  local gridspacing = options["grid spacing"]
  for _, v in ipairs(order) do
    if not v.virtual then
      local iv = v.inputvertex
      iv.pos.x = gridpos[v].x * gridspacing
      iv.pos.y = gridpos[v].y * gridspacing
    end
  end

  embedding:remove_virtual()

  --start = os.clock()
  if options["use pdp"] then
    local pdp = PDP.new(
      self.ugraph, embedding,
      options["node distance"],
      options["node distance"],
      options["pdp cooling factor"],
      options["exponent change iterations"],
      options["start repulsive exponent"],
      options["end repulsive exponent"],
      options["start attractive exponent"],
      options["end attractive exponent"],
      options["edge approach threshold"],
      options["edge stretch threshold"],
      options["stress counter threshold"],
      options["edge divisions"]
    )
    pdp:run()
  end

end