Class: Relyze::Graph::Graph

Inherits:
Object
  • Object
show all
Defined in:
C:/Program Files/Relyze/lib/relyze/core/graph.rb

Overview

A base class representing a graph.

Direct Known Subclasses

DirectedGraph

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(name = '', display = {}) ⇒ Graph

Returns a new instance of Graph

Parameters:

  • name (String) (defaults to: '') —

    This graphs name.

  • display (Hash) (defaults to: {}) —

    A hash of display options.

[View source]

31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 31

def initialize( name='', display={} )
    @name     = name
    @root     = nil
    @nodes    = []
    @data_map = {}
    @next_id  = 0
    @display  = {
        :graph_color  => display.fetch( :graph_color,  '#FFFFFF' ),
        :font_name    => display.fetch( :font_name,    'Courier New' ),
        :font_size    => display.fetch( :font_size,    10 ),
        :font_color   => display.fetch( :font_color,   '#000000' ),
        :font_justify => display.fetch( :font_justify, :left ),
        :node_padding => display.fetch( :node_padding, 20 ),
        :node_spacing => nil,
        :graph_x      => 0.0,
        :graph_y      => 0.0,
        :graph_width  => 0.0,
        :graph_height => 0.0
    }.merge!( display )
end

Instance Attribute Details

#data_map ⇒ Object (readonly)

Hash

A hash map of data objects to their associated Node.


18
19
20
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 18

def data_map
  @data_map
end

#display ⇒ Object (readonly)

Hash

A hash of display properties for this graph.


21
22
23
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 21

def display
  @display
end

#name ⇒ Object

String

Gets this graph's name.


24
25
26
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 24

def name
  @name
end

#nodes ⇒ Object (readonly)

Array<Relyze::Graph::Node>

An array of node objects.


15
16
17
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 15

def nodes
  @nodes
end

#root ⇒ Object

Relyze::Graph::Node, nil

This graphs root node (if any).


27
28
29
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 27

def root
  @root
end

Instance Method Details

#_new_edge(lhs, rhs, data) ⇒ Object (protected)

[View source]

353
354
355
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 353

def _new_edge( lhs, rhs, data )
    return Edge.new( self, lhs, rhs, data )
end

#_new_node(id, data) ⇒ Object (protected)

[View source]

349
350
351
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 349

def _new_node( id, data )
    return Node.new( self, id, data )
end

#analyze ⇒ true, false

Analyze this graph in order to calculate the dominator's, post dominator's, dominance frontiers and control dependencies of this graphs nodes.

Returns:

  • (true, false)
[View source]

180
181
182
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 180

def analyze
    return false
end

#color2html(color) ⇒ String

Helper method to convert a Integer color to a HTML color string

Parameters:

Returns:

  • (String) —

    The HTML color.

[View source]

327
328
329
330
331
332
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 327

def color2html( color )
    red   = (color >>  0) & 0xFF
    green = (color >>  8) & 0xFF
    blue  = (color >> 16) & 0xFF
    return "#%02X%02X%02X" % [ red, green, blue ]
end

#complexity ⇒ Integer

Calculate this graphs cyclomatic complexity.

Returns:

[View source]

62
63
64
65
66
67
68
69
70
71
72
73
74
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 62

def complexity
    p = 1
    edges = 0
    @nodes.each do | node |
        if( node.indegree == 0 )
            if( node != @root )
                p += 1
            end
        end
        edges += node.outdegree
    end
    return edges - @nodes.size + (2 * p)
end

#create_edge(lhs, rhs, data = nil) ⇒ Relyze::Graph::Edge

Create a new Edge in this graph between two nodes.

Parameters:

  • lhs (Relyze::Graph::Node) —

    This edges left hand side node.

  • rhs (Relyze::Graph::Node) —

    This edges right hand side node.

  • data (Object) (defaults to: nil) —

    An arbitrary object to associate with this edge.

Returns:

[View source]

140
141
142
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 140

def create_edge( lhs, rhs, data=nil )
    return self._new_edge( lhs, rhs, data )
end

#create_node(data = nil) ⇒ Relyze::Graph::Node

Create a new Node in this graph.

Parameters:

  • data (Object) (defaults to: nil) —

    An unique object to associate with this node.

Returns:

[View source]

103
104
105
106
107
108
109
110
111
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 103

def create_node( data=nil )
    node = self._new_node( @next_id, data )
    @nodes << node
    if( not data.nil? )
        @data_map[data] = node
    end
    @next_id += 1
    return node
end

#directed? ⇒ true, false

Is this a directed graph?

Returns:

  • (true, false)
[View source]

55
56
57
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 55

def directed?
    return false
end

#dominator_tree ⇒ nil, Relyze::Graph::Graph

Create a new dominator tree for this graph. You must call #analyze prior to calling this method, to ensure the required dominator information is available. The data property for each node in the dominator tree holds its corresponding node from the original graph.

Examples:

Create and display a dominator tree

# Analyze an existing graph to generate its dominator information
graph.analyze
# Generate the dominator tree
dom_tree = graph.dominator_tree
# Layout the new dominator tree with a default hierarchical layout
dom_tree.layout
# Display the tree in the Relyze UI
@relyze.graph_dialog( dom_tree )

Returns:

[View source]

208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 208

def dominator_tree
    dom_tree = ::Relyze::Graph::Graph.new( "%s - Dominator Tree" % [self.name] )
    
    @nodes.each do | node |
        
        if( node.immediate_dominator.nil? )
            next
        end
        
        dg_curr_node = dom_tree.find_or_create_node( node )
        
        dg_idom_node = dom_tree.find_or_create_node( node.immediate_dominator )
        
        if( dg_curr_node == dg_idom_node )
            next
        end
        
        dom_tree.create_edge( dg_idom_node, dg_curr_node )
    end
    
    return dom_tree
end

#find_node(data) ⇒ Relyze::Graph::Node?

Find an existing node with an associated data object.

Parameters:

  • data (Object) —

    Find a node with this data object.

Returns:

[View source]

117
118
119
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 117

def find_node( data )
    return @data_map.fetch( data, nil )
end

#find_or_create_node(data) ⇒ Relyze::Graph::Node

Either find an existing node with an associated data object and if not found, create a new node and associate it with a data object.

Parameters:

  • data (Object) —

    Find or create a node with this data object.

Returns:

[View source]

126
127
128
129
130
131
132
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 126

def find_or_create_node( data )
    node = self.find_node( data )
    if( node.nil? )
        node = self.create_node( data )
    end
    return node
end

#generate_random(node_count = 128, edge_count = 8) ⇒ Relyze::Graph::Graph

Generate a random collection of nodes and edges for this graph.

Parameters:

  • node_count (Integer) (defaults to: 128) —

    The maximum number of nodes to create.

  • edge_count (Integer) (defaults to: 8) —

    The maximum number of edges to create in any node.

Returns:

[View source]

81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 81

def generate_random( node_count=128, edge_count=8 )
    prng = ::Random.new

    0.upto( prng.rand( node_count ) ) do | i |
        node = self.create_node( i )
    end

    @nodes.each do | node |
        if( prng.rand( 2 ) == 0 )
            0.upto( prng.rand( edge_count ) ) do
                self.create_edge( node, @nodes[ prng.rand( @nodes.length ) ] )
            end
        end
    end

    return self
end

#layout(opts = { :layout => :hierarchical, :direction => :topdown }) ⇒ true, false

Run a layout algorithm over this graph to set the node and edge display positions.

Examples:


graph = Relyze::Graph::DirectedGraph.new( 'Test', { :font_justify => :center } )

graph.generate_random

graph.layout( { :layout => :hierarchical, :direction => :topdown } )

@relyze.graph_dialog( graph )

graph.layout( { :layout => :circular, :order => :outdegree } )

@relyze.graph_dialog( graph )

graph.layout( { :layout => :force, :min_iterations => 100, :max_iterations => 1000, :parallel => true } )

@relyze.graph_dialog( graph )

Parameters:

  • opts (Hash) (defaults to: { :layout => :hierarchical, :direction => :topdown }) —

    The layout options.

Options Hash (opts):

  • :layout (Symbol) —

    The layout algorithm to use, either :hierarchical, :circular or :force.

  • :direction (Symbol) —

    For a hierarchical layout, either :topdown or :bottomup.

  • :order (Symbol) —

    For a circular layout, either :degree, :indegree or :outdegree.

  • :min_iterations (Integer, nil) —

    For a force layout, the minimum number of layout iteration to perform.

  • :max_iterations (Integer, nil) —

    For a force layout, the maximum number of layout iteration to perform.

  • :parallel (true, false) —

    For a force layout, perform the layout with parallel operations.

Returns:

  • (true, false)
[View source]

172
173
174
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 172

def layout( opts={ :layout => :hierarchical, :direction => :topdown } )
    return false
end

#post_dominator_tree ⇒ nil, Relyze::Graph::Graph

Create a new post dominator tree for this graph. You must call #analyze prior to calling this method, to ensure the required dominator information is available. The data property for each node in the dominator tree holds its corresponding node from the original graph.

Returns:

[View source]

237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 237

def post_dominator_tree
    dom_tree = ::Relyze::Graph::Graph.new( "%s - Post Dominator Tree" % [self.name] )
    
    @nodes.each do | node |
        
        if( node.immediate_post_dominator.nil? )
            next
        end
        
        dg_curr_node = dom_tree.find_or_create_node( node )
        
        dg_idom_node = dom_tree.find_or_create_node( node.immediate_post_dominator )
        
        if( dg_curr_node == dg_idom_node )
            next
        end
        
        dom_tree.create_edge( dg_idom_node, dg_curr_node )
    end
    
    return dom_tree
end

#svg_escape(text) ⇒ String

SVG escape a string.

Returns:

  • (String) —

    The escaped string

[View source]

337
338
339
340
341
342
343
344
345
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 337

def svg_escape( text )
    text.gsub!( "&",  "&amp;" )
    text.gsub!( "<",  "&lt;" )
    text.gsub!( ">",  "&gt;" )
    text.gsub!( "\"", "&quot;" )
    text.gsub!( "'",  "&apos;" )
    text.gsub!( " ",  "&#160;" )
    return text
end

#to_dot ⇒ String

Export this graph object as a DOT graph.

Returns:

[View source]

298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 298

def to_dot

    dot = ""

    dot << "%s {\r\n" % [ ( self.directed? ? 'digraph' : 'graph' ) ]

    dot << "\tbgcolor=\"%s\"\r\n" % @display[:graph_color]

    @nodes.each do | node |

        dot << node.to_dot

        node.edges.each do | edge |

            next if edge.lhs != node

            dot << edge.to_dot
        end
    end

    dot << "}\r\n"

    return dot
end

#to_svg ⇒ String

Export this graph object as a SVG element, suitable for embedding in HTML.

Returns:

  • (String) —

    An SVG element.

[View source]

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
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 263

def to_svg

    svg  = "<svg "
    svg << "width=\"%f\" " % @display[:graph_width]
    svg << "height=\"%f\" " % @display[:graph_height]
    svg << "viewBox=\"%f %f %f %f\" " % [ @display[:graph_x] - (@display[:graph_width] / 2.0), @display[:graph_y] - (@display[:graph_height] / 2.0), @display[:graph_width], @display[:graph_height] ]
    svg << "preserveAspectRatio=\"xMinYMin meet\" "
    svg << "xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" "
    svg << "style=\"background-color:%s;\" " % @display[:graph_color]
    svg << ">"

    svg << "<g class=\"relyze_graph\" transform=\"scale(1 1) rotate(0)\">"

    @nodes.each do | node |

        svg << node.to_svg

        node.edges.each do | edge |

            next if edge.lhs != node

            svg << edge.to_svg
        end
    end

    svg << "</g>"

    svg << "</svg>"

    return svg
end

#topological_sort ⇒ nil, Array<Relyze::Graph::Node>

Perform a topological sort on this graphs nodes from its root node. This is equivalent to depth first search in reverse post order.

Returns:

[View source]

188
189
190
 
# File 'C:/Program Files/Relyze/lib/relyze/core/graph.rb', line 188

def topological_sort
    return nil
end
9 11:51:56 2022 by yard 0.9.20 (ruby-2.6.5).