class Topiary::DirectedGraph

A graph whose edges are directed instead of directionless

Public Class Methods

acyclic_from_node_count(node_count) click to toggle source
# 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=[]) click to toggle source
# 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) click to toggle source
# 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=[]) click to toggle source

Assumes that all input nodes are edgeless.

# 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
new(nodes=[]) click to toggle source
Calls superclass method
# File lib/topiary/directed_graph.rb, line 107
def initialize(nodes=[])
  super
  @forbid_cycles = false
end
topologically_distinct(graphs) click to toggle source

Returns only those graphs that are topologically distinct

# 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

Public Instance Methods

add_edge!(from_node, to_node) click to toggle source
# 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() click to toggle source
# 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) click to toggle source

rubocop:enable Naming/PredicateName

# File lib/topiary/directed_graph.rb, line 180
def forbid_cycles!(v=true)
  @forbid_cycles = v
  maybe_forbid_cycles! if v
end
has_cycles?() click to toggle source

rubocop:disable Naming/PredicateName

# File lib/topiary/directed_graph.rb, line 172
def has_cycles?
  Topiary.sort nodes
  false
rescue InvalidGraph
  true
end
topologically_equivalent?(other) click to toggle source

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.

# 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

Private Instance Methods

maybe_forbid_cycles!() click to toggle source
# File lib/topiary/directed_graph.rb, line 187
def maybe_forbid_cycles!
  raise InvalidGraph, "Cycles found!" if @forbid_cycles and has_cycles?
end