Source

grrdrr / gd.py

Full commit
  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


import cairo


class Graph(object):

    def __init__(self):
        self.nodes = []
        self.arcs = []
        self.layers = []
        self.style = None
        self.margins = None
        self.size = None

    def add_node(self):
        return Node(self)

    def add_arc(self, origin, target, weight=1.0):
        return Arc(self, origin, target, weight)

    def add_layer(self):
        return Layer(self)

    def set_style(self,
                background_color=(1.0, 1.0, 1.0),
                node_color=(0.0, 0.0, 0.0),
                arc_color=(0.0, 0.0, 0.0),
                text_color=(1.0, 1.0, 1.0),
                font_size=10):
        return GraphStyle(self, background_color=background_color,
                    node_color=node_color, arc_color=arc_color,
                    text_color=text_color, font_size=font_size)

    def set_margins(self, top, right, bottom, left):
        return GraphMargins(self, top, right, bottom, left)

    def set_size(self, width, height):
        return GraphSize(self, width, height)

    def measuring(self):
        if self.style is None:
            self.set_style()

        dummy_surface = cairo.ImageSurface(cairo.FORMAT_ARGB32, 1, 1)
        dummy_context = cairo.Context(dummy_surface)
        dummy_context.set_font_size(self.style.font_size)

        extents = dummy_context.text_extents('M')
        x_bearing, y_bearing, width, height, x_advance, y_advance = extents
        m_width = int(width)
        m_height = int(height)

        if self.margins is None:
            self.set_margins(m_height, m_width, m_height, m_width)

        for node in self.nodes:
            if node.dimensions is not None:
                continue
            if node.label is not None:
                extents = dummy_context.text_extents(node.label.text)
                x_bearing, y_bearing, width, height, x_advance, y_advance = extents
                node_width = int(width*2)
                node_height = int(height*2)
            else:
                node_width = m_width*2
                node_height = m_height*2
            node.set_dimensions(node_width, node_height)

    def sorting(self):
        existing_ranks = set(node.rank.value for node in self.nodes if node.rank is not None)
        value = 0
        for node in self.nodes:
            if node.rank is not None:
                continue
            while value in existing_ranks:
                value += 1
            node.set_rank(value)
            value += 1

    def layering(self):
        nodes_per_layer = int(len(self.nodes)**0.5)
        layer = None
        for node in sorted(self.nodes, key=(lambda node: node.rank.value)):
            if node.layer_item is not None:
                continue
            if layer is None or len(layer.items) > nodes_per_layer:
                layer = self.add_layer()
            layer.add_node_item(node)
        for arc in self.arcs:
            origin_layer_index = arc.origin.layer_item.layer.index
            target_layer_index = arc.target.layer_item.layer.index
            min_index = min(origin_layer_index, target_layer_index) + 1
            max_index = max(origin_layer_index, target_layer_index)
            for index in range(min_index, max_index):
                layer = self.layers[index]
                layer.add_arc_item(arc)

    def ordering(self):
        for layer in self.layers:
            node_items = [node.layer_item for node in self.nodes
                        if node.layer_item.layer is layer]
            arc_items = [layer_item for arc in self.arcs for layer_item in arc.layer_items
                        if layer_item.layer is layer]
            node_items_index = 0
            arc_items_index = 0
            value = 0

            while node_items_index < len(node_items) and arc_items_index < len(arc_items):
                if node_items_index <= arc_items_index:
                    item = node_items[node_items_index]
                    node_items_index += 1
                else:
                    item = arc_items[arc_items_index]
                    arc_items_index += 1
                item.set_order(value)
                value += 1

            while node_items_index < len(node_items):
                item = node_items[node_items_index]
                node_items_index += 1
                item.set_order(value)
                value += 1

            while arc_items_index < len(arc_items):
                item = arc_items[arc_items_index]
                arc_items_index +=  1
                item.set_order(value)
                value += 1

    def placing(self):

        layer_top = self.margins.top
        max_layer_bottom = layer_top
        layer_left = self.margins.left
        max_layer_right = layer_left
        is_leading_line = True
        for layer in self.layers:
            items = sorted(layer.items, key=(lambda item: item.order.value))
            if is_leading_line:
                is_leading_line = False
            else:
                layer_top += max(self.margins.top, self.margins.bottom)
            layer_bottom = layer_top
            layer_right = layer_left
            is_leading_column = True
            for item in items:
                if is_leading_column:
                    is_leading_column = False
                else:
                    layer_right += max(self.margins.left, self.margins.right)
                if item.is_node:
                    layer_bottom = max(layer_bottom, layer_top+item.node.dimensions.height)
                    layer_right += item.node.dimensions.width
            
            item_left = layer_left
            is_leading_column = True
            for item in items:
                if is_leading_column:
                    is_leading_column = False
                else:
                    item_left += max(self.margins.left, self.margins.right)
                if item.is_node:
                    node = item.node
                    x1 = item_left
                    y1 = (layer_top + layer_bottom - node.dimensions.height)/2
                    x2 = x1 + node.dimensions.width
                    y2 = y1 + node.dimensions.height
                    node.set_position(x1, y1, x2, y2)
                    cx = (x1 + x2)/2
                    cy = (y1 + y2)/2
                    for arc in node.incoming + node.outgoing:
                        arc.add_vertex(cx, cy)
                    item_left += node.dimensions.width
                else:
                    arc = item.arc
                    x = item_left
                    y = layer_top
                    arc.add_vertex(x, y)
                    x = item_left
                    y = layer_bottom
                    arc.add_vertex(x, y)

            layer_top = layer_bottom

            max_layer_bottom = layer_bottom
            max_layer_right = max(max_layer_right, layer_right)

        graph_width = max_layer_right + self.margins.right
        graph_height = max_layer_bottom + self.margins.bottom

        self.set_size(graph_width, graph_height)

    def layout(self):
        self.measuring()
        self.sorting()
        self.layering()
        self.ordering()
        self.placing()

    def draw(self, stream):
        self.layout()

        surface = cairo.ImageSurface(cairo.FORMAT_ARGB32, self.size.width, self.size.height)
        context = cairo.Context(surface)
        context.set_font_size(self.style.font_size)

        context.set_source_rgb(*self.style.arc_color)
        for arc in self.arcs:
            context.new_path()
            vertex = arc.vertices[0]
            context.move_to(vertex.x, vertex.y)
            for vertex in arc.vertices[1:]:
                context.line_to(vertex.x, vertex.y)
            context.stroke()

        context.set_source_rgb(*self.style.node_color)
        for node in self.nodes:
            position = node.position
            context.new_path()
            x = position.x1
            y = position.y1
            w = position.x2 - position.x1
            h = position.y2 - position.y1
            context.rectangle(x, y, w, h)
            context.fill()

        context.set_source_rgb(*self.style.text_color)
        for node in self.nodes:
            if node.label is not None:
                cx = (node.position.x1 + node.position.x2)/2
                cy = (node.position.y1 + node.position.y2)/2
                text = node.label.text
                extents = context.text_extents(text)
                x_bearing, y_bearing, width, height, x_advance, y_advance = extents
                x = cx - (width/2 + x_bearing)
                y = cy - (height/2 + y_bearing)
                context.move_to(x, y)
                context.show_text(text)

        surface.write_to_png(stream)


class GraphMargins(object):

    def __init__(self, graph, top, right, bottom, left):
        self.graph = graph
        self.top = top
        self.right = right
        self.bottom = bottom
        self.left = left
        graph.margins = self


class GraphStyle(object):

    def __init__(self, graph, background_color, node_color,
                arc_color, text_color, font_size):
        self.graph = graph
        self.background_color = background_color
        self.node_color = node_color
        self.arc_color = arc_color
        self.text_color = text_color
        self.font_size = font_size
        graph.style = self


class GraphSize(object):

    def __init__(self, graph, width, height):
        self.graph = graph
        self.width = width
        self.height = height
        graph.size = self


class Node(object):

    def __init__(self, graph):
        self.graph = graph
        self.incoming = []
        self.outgoing = []
        self.label = None
        self.dimensions = None
        self.position = None
        self.rank = None
        self.order = None
        self.layer_item = None
        self.index = len(graph.nodes)
        graph.nodes.append(self)

    def set_label(self, text):
        return NodeLabel(self, text)

    def set_dimensions(self, width, height):
        return NodeDimensions(self, width, height)

    def set_position(self, x1, y1, x2, y2):
        return NodePosition(self, x1, y1, x2, y2)

    def set_rank(self, value):
        return NodeRank(self, value)


class NodeLabel(object):

    def __init__(self, node, text):
        self.node = node
        self.text = text
        node.label = self


class NodeDimensions(object):

    def __init__(self, node, width, height):
        self.node = node
        self.width = width
        self.height = height
        node.dimensions = self


class NodePosition(object):

    def __init__(self, node, x1, y1, x2, y2):
        self.node = node
        self.x1 = x1
        self.y1 = y1
        self.x2 = x2
        self.y2 = y2
        node.position = self


class NodeRank(object):

    def __init__(self, node, value):
        self.node = node
        self.value = value
        node.rank = self


class NodeOrder(object):

    def __init__(self, node, value):
        self.node = node
        self.value = value
        node.order = self


class Arc(object):

    def __init__(self, graph, origin, target, weight):
        self.graph = graph
        self.origin = origin
        self.target = target
        self.weight = weight
        self.label = None
        self.layer_items = []
        self.vertices = []
        self.index = len(graph.arcs)
        graph.arcs.append(self)
        origin.outgoing.append(self)
        target.incoming.append(self)

    def set_label(self, text):
        return ArcLabel(self, text)

    def set_order(self, values):
        return ArcOrder(self, values)

    def add_vertex(self, x, y):
        return ArcVertex(self, x, y)


class ArcLabel(object):

    def __init__(self, arc, text):
        self.arc = arc
        self.text = text
        arc.label = self


class ArcOrder(object):

    def __init__(self, arc, values):
        self.arc = arc
        self.values = values
        arc.order = self


class ArcVertex(object):

    def __init__(self, arc, x, y):
        self.arc = arc
        self.x = x
        self.y = y
        arc.vertices.append(self)


class Layer(object):

    def __init__(self, graph):
        self.graph = graph
        self.items = []
        self.index = len(graph.layers)
        graph.layers.append(self)

    def add_node_item(self, node):
        return LayerNodeItem(self, node)

    def add_arc_item(self, arc):
        return LayerArcItem(self, arc)


class LayerNodeItem(object):

    def __init__(self, layer, node):
        self.layer = layer
        self.node = node
        self.is_node = True
        self.is_arc = False
        self.order = None
        self.index = len(layer.items)
        layer.items.append(self)
        node.layer_item = self

    def set_order(self, value):
        return LayerItemOrder(self, value)


class LayerArcItem(object):

    def __init__(self, layer, arc):
        self.layer = layer
        self.arc = arc
        self.is_node = False
        self.is_arc = True
        self.order = None
        self.index = len(layer.items)
        layer.items.append(self)
        arc.layer_items.append(self)

    def set_order(self, value):
        return LayerItemOrder(self, value)


class LayerItemOrder(object):

    def __init__(self, layer_item, value):
        self.layer_item = layer_item
        self.value = value
        layer_item.order = self