Class: Topiary::DirectedGraph

Inherits:
Graph
  • Object
show all
Defined in:
lib/topiary/directed_graph.rb

Overview

A graph whose edges are directed instead of directionless

Instance Attribute Summary

Attributes inherited from Graph

#nodes

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from Graph

#to_s

Constructor Details

#initialize(nodes = []) ⇒ DirectedGraph

Returns a new instance of DirectedGraph.



107
108
109
110
 
# File 'lib/topiary/directed_graph.rb', line 107

def initialize(nodes=[])
  super
  @forbid_cycles = false
end

Class Method Details

.acyclic_from_node_count(node_count) ⇒ Object 



79
80
81
 
# File 'lib/topiary/directed_graph.rb', line 79

def self.acyclic_from_node_count(node_count)
  acyclic_from_node_list(1.upto(node_count).map{|i| Node.new i.to_s})
end

.acyclic_from_node_list(nodes = []) ⇒ Object 



83
84
85
 
# File 'lib/topiary/directed_graph.rb', line 83

def self.acyclic_from_node_list(nodes=[])
  all_from_node_list(nodes).reject(&:has_cycles?).each(&:forbid_cycles!)
end

.all_from_node_count(node_count) ⇒ Object 



12
13
14
 
# File 'lib/topiary/directed_graph.rb', line 12

def self.all_from_node_count(node_count)
  all_from_node_list(1.upto(node_count).map{|i| Node.new i.to_s})
end

.all_from_node_list(nodes = []) ⇒ Object

Assumes that all input nodes are edgeless.



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
 
# File 'lib/topiary/directed_graph.rb', line 17

def self.all_from_node_list(nodes=[])
  Enumerator.new do |y|
    if nodes.empty?
      # There is one graph with zero nodes:
      y.yield DirectedGraph.new
    else
      # Find the number of combinations with replacement,
      # denoted
      #    n
      # ((   ))
      #    k
      #
      # which is
      #
      #   n + k - 1
      # (           )
      #      k
      #
      # and where
      #
      #   n          n!
      # (   ) = ------------
      #   k      k!(n - k)!
      node_count = nodes.size
      n = node_count + 2 - 1
      pair_count = factorial(n) /
                   (factorial(2) * factorial(n - 2))
      # Between every two nodes u & v there are 3 choices:
      #
      #   - no edge
      #   - edge from u to v
      #   - edge from v to u
      #
      # Except if u & v are the same node,
      # choice 2 & choice 3 are the same, so skip one of them.
      %w[. < >].repeated_permutation(pair_count).each do |edges|
        our_nodes = nodes.map(&:clone)
        pairs = our_nodes.repeated_combination(2).to_a
        g = DirectedGraph.new our_nodes
        skip = false
        edges.each_with_index do |dir, i|
          case dir
          when '.'
            # no edge
          when '<'
            pairs[i][0].need! pairs[i][1]
          when '>'
            # If the two nodes are the same,
            # we already did this:
            if pairs[i][0] == pairs[i][1]
              skip = true
              break
            end
            pairs[i][0].feed! pairs[i][1]
          end
        end
        y.yield g unless skip
      end
    end
  end
end

.topologically_distinct(graphs) ⇒ Object

Returns only those graphs that are topologically distinct



88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
 
# File 'lib/topiary/directed_graph.rb', line 88

def self.topologically_distinct(graphs)
  already_seen = Set.new
  Enumerator.new do |y|
    graphs.each do |g|
      is_new = true
      already_seen.each do |g2|
        if g2.topologically_equivalent? g
          is_new = false
          break
        end
      end
      if is_new
        y.yield g
        already_seen << g
      end
    end
  end
end

Instance Method Details

#add_edge!(from_node, to_node) ⇒ Object 



112
113
114
115
 
# File 'lib/topiary/directed_graph.rb', line 112

def add_edge!(from_node, to_node)
  from_node.feed! to_node
  maybe_forbid_cycles!
end

#edges ⇒ Object 



117
118
119
120
121
122
123
124
125
 
# File 'lib/topiary/directed_graph.rb', line 117

def edges
  Enumerator.new do |y|
    nodes.each do |n|
      n.feeds.each do |n2|
        y.yield Edge.new(n, n2)
      end
    end
  end
end

#forbid_cycles!(v = true) ⇒ Object

rubocop:enable Naming/PredicateName



180
181
182
183
 
# File 'lib/topiary/directed_graph.rb', line 180

def forbid_cycles!(v=true)
  @forbid_cycles = v
  maybe_forbid_cycles! if v
end

#has_cycles? ⇒ Boolean

rubocop:disable Naming/PredicateName

Returns:

  • (Boolean) 


172
173
174
175
176
177
 
# File 'lib/topiary/directed_graph.rb', line 172

def has_cycles?
  Topiary.sort nodes
  false
rescue InvalidGraph
  true
end

#topologically_equivalent?(other) ⇒ Boolean

Two graphs A and B are topologically equivalent if there is a bijection phi on the vertices such that edge phi(u)phi(v) is in B iff uv is in A.

Returns:

  • (Boolean) 


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
 
# File 'lib/topiary/directed_graph.rb', line 130

def topologically_equivalent?(other)
  our_nodes = nodes.to_a
  other_nodes = other.nodes.to_a
  return false if our_nodes.size != other_nodes.size
  our_edges = edges.to_a
  other_edges = other.edges.to_a
  return false if our_edges.size != other_edges.size

  our_node_numbers = Hash[
    our_nodes.each_with_index.map{|n, i| [n, i]}
  ]

  # Since there are no permutations,
  # we have to special case graphs with 0 or 1 node:
  case our_nodes.size
  when 0
    true
  when 1
    true  # since we already know they have the same number of edges
  else
    # Now we have to try all permutations of the nodes:
    0.upto(nodes.size - 1).to_a.permutation.each do |phi|
      equivalent = true
      catch :answered do
        our_nodes.each_with_index do |u, i|
          phi_u = other_nodes[phi[i]]
          u.feeds.each do |v|
            phi_v = other_nodes[phi[our_node_numbers[v]]]
            if not phi_u.feeds.include?(phi_v)
              equivalent = false
              throw :answered
            end
          end
        end
      end
      return true if equivalent
    end
    false
  end
end