This documentation is automatically generated by online-judge-tools/verification-helper

:heavy_check_mark: src/graph/bfs01.cr

Depends on

Verified with

Code

require "../graph"

module Graph(Edge, Edge2)
  # Returns the array of distance of each node from *start* or `nil`.
  # *block* must return `0` or `1`.
  def bfs01(start : Int, &block) : Array(Int32?)
    raise ArgumentError.new unless 0 <= start < size
    queue = Deque{start}
    dist = Array(Int32?).new(size, nil).tap(&.[start] = 0)
    while v = queue.shift?
      current_dist = dist[v].not_nil!
      graph[v].each do |edge|
        cost = yield edge
        raise ArgumentError.new("Unexpected cost: #{cost}") unless cost == 0 || cost == 1
        next_dist = current_dist + cost
        d = dist[edge.to]
        if d.nil? || next_dist < d
          dist[edge.to] = next_dist
          if cost == 0
            queue.unshift edge.to
          else
            queue.push edge.to
          end
        end
      end
    end
    dist
  end

  # Returns the array of distance of each node from *start* or `nil`.
  # All of cost of edge must be `0` or `1`.
  def bfs01(start : Int) : Array(Int32?)
    bfs01(start, &.cost)
  end

  # Returns the array of distance of each node from *start*.
  # *block* must return `0` or `1`.
  def bfs01!(start : Int32, &block) : Array(Int32)
    bfs01(start) { |edge| yield edge }.map(&.not_nil!)
  end

  # Returns the array of distance of each node from *start*.
  # All of cost of edge must be `0` or `1`.
  def bfs01!(start : Int) : Array(Int32)
    bfs01!(start, &.cost)
  end

  # Returns the distance from *start* to *goal* if path is present, otherwise returns `nil`.
  # *block* must return `0` or `1`.
  def bfs01_st(start : Int, goal : Int, &block) : Int32?
    raise ArgumentError.new unless 0 <= start < size
    queue = Deque{start}
    dist = Array(Int32?).new(size, nil).tap(&.[start] = 0)
    while v = queue.shift?
      current_dist = dist[v].not_nil!
      return current_dist if v == goal
      graph[v].each do |edge|
        cost = yield edge
        raise ArgumentError.new("Unexpected cost: #{cost}") unless cost == 0 || cost == 1
        next_dist = current_dist + cost
        d = dist[edge.to]
        if d.nil? || next_dist < d
          dist[edge.to] = next_dist
          if cost == 0
            queue.unshift edge.to
          else
            queue.push edge.to
          end
        end
      end
    end
    nil
  end

  # Returns the distance from *start* to *goal* if path is present, otherwise returns `nil`.
  # All of cost of edge must be `0` or `1`.
  def bfs01_st(start : Int, goal : Int) : Int32?
    bfs01_st(start, goal, &.cost)
  end

  # Returns the distance from *start* to *goal* if path is present, otherwise raises `ArgumentError`.
  # *block* must return `0` or `1`.
  def bfs01_st!(start : Int, goal : Int, &block) : Int32
    bfs01_st(start, goal) { |edge| yield edge } || raise ArgumentError.new
  end

  # Returns the distance from *start* to *goal* if path is present, otherwise raises `ArgumentError`.
  # All of cost of edge must be `0` or `1`.
  def bfs01_st!(start : Int, goal : Int) : Int32
    bfs01_st(start, goal, &.cost) || raise ArgumentError.new
  end
end
# require "../graph"
# require "./graph/edge"
struct WeightedEdge(T)
  include Comparable(WeightedEdge(T))

  property to : Int32, cost : T

  def initialize(@to, @cost : T)
  end

  def <=>(other : WeightedEdge(T))
    {cost, to} <=> {other.cost, other.to}
  end

  def to_s(io) : Nil
    io << '(' << to << ", " << cost << ')'
  end

  def inspect(io) : Nil
    io << "->" << to << '(' << cost << ')'
  end
end

struct WeightedEdge2(T)
  include Comparable(WeightedEdge2(T))

  property from : Int32, to : Int32, cost : T

  def initialize(@from, @to, @cost : T)
  end

  def initialize(@from, edge : WeightedEdge(T))
    @to, @cost = edge.to, edge.cost
  end

  def <=>(other : WeightedEdge2(T))
    {cost, from, to} <=> {other.cost, other.from, other.to}
  end

  def reverse : self
    WeightedEdge2(T).new(to, from, cost)
  end

  def sort : self
    WeightedEdge2(T).new(*{to, from}.minmax, cost)
  end

  def to_s(io) : Nil
    io << '(' << from << ", " << to << ", " << cost << ')'
  end

  def inspect(io) : Nil
    io << from << "->" << to << '(' << cost << ')'
  end
end

struct UnweightedEdge
  property to : Int32

  def initialize(@to)
  end

  def initialize(@to, cost)
  end

  def cost : Int32
    1
  end

  def to_s(io) : Nil
    io << to
  end

  def inspect(io) : Nil
    io << "->" << to
  end
end

struct UnweightedEdge2
  property from : Int32, to : Int32

  def initialize(@from, @to)
  end

  def initialize(@from, @to, cost)
  end

  def initialize(@from, edge : UnweightedEdge)
    @to = edge.to
  end

  def cost : Int32
    1
  end

  def reverse : self
    UnweightedEdge2.new(to, from)
  end

  def sort : self
    UnweightedEdge2.new(*{to, from}.minmax)
  end

  def to_s(io) : Nil
    io << '(' << from << ", " << to << ')'
  end

  def inspect(io) : Nil
    io << from << "->" << to
  end
end

module Graph(Edge, Edge2)
  include Enumerable(Edge2)

  getter graph : Array(Array(Edge))

  def initialize(size : Int)
    @graph = Array(Array(Edge)).new(size) { [] of Edge }
  end

  def initialize(size : Int, edges : Enumerable)
    initialize(size)
    add_edges(edges)
  end

  # Add *edge*.
  abstract def <<(edge : Edge2)

  # :ditto:
  def <<(edge : Tuple) : self
    self << Edge2.new(*edge)
  end

  def add_edges(edges : Enumerable) : self
    edges.each { |edge| self << edge }
    self
  end

  delegate size, :[], to: @graph

  # Yields each edge of the graph, ans returns `nil`.
  def each(&) : Nil
    (0...size).each do |v|
      graph[v].each do |edge|
        yield Edge2.new(v, edge)
      end
    end
  end

  def each_child(vertex : Int, parent, &block) : Nil
    graph[vertex].each do |edge|
      yield edge if edge.to != parent
    end
  end

  def each_child(vertex : Int, parent)
    graph[vertex].each.reject(&.to.== parent)
  end

  def reverse : self
    if self.class.directed?
      each_with_object(self.class.new(size)) do |edge, reversed|
        reversed << edge.reverse
      end
    else
      dup
    end
  end

  def to_undirected : self
    if self.class.directed?
      each_with_object(self.class.new(size)) do |edge, graph|
        graph << edge << edge.reverse
      end
    else
      dup
    end
  end

  def to_s(io : IO) : Nil
    io << '['
    join(", ", io) do |edge, io|
      edge.inspect io
    end
    io << ']'
  end

  def inspect(io : IO) : Nil
    io << "[\n"
    graph.each do |edges|
      io << "  " << edges << ",\n"
    end
    io << ']'
  end
end

class DiGraph(T)
  include Graph(WeightedEdge(T), WeightedEdge2(T))

  def self.weighted?
    true
  end

  def self.directed?
    true
  end

  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges : Enumerable(WeightedEdge2(T)))
    super
  end

  def initialize(size : Int, edges : Enumerable({Int32, Int32, T}))
    super
  end

  def <<(edge : WeightedEdge2(T)) : self
    raise IndexError.new unless 0 <= edge.from < size && 0 <= edge.to < size
    @graph[edge.from] << WeightedEdge.new(edge.to, edge.cost)
    self
  end
end

class UnGraph(T)
  include Graph(WeightedEdge(T), WeightedEdge2(T))

  def self.weighted?
    true
  end

  def self.directed?
    false
  end

  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges : Enumerable(WeightedEdge2(T)))
    super
  end

  def initialize(size : Int, edges : Enumerable({Int32, Int32, T}))
    super
  end

  def <<(edge : WeightedEdge2(T)) : self
    raise IndexError.new unless 0 <= edge.from < size && 0 <= edge.to < size
    @graph[edge.from] << WeightedEdge.new(edge.to, edge.cost)
    @graph[edge.to] << WeightedEdge.new(edge.from, edge.cost)
    self
  end
end

class UnweightedDiGraph
  include Graph(UnweightedEdge, UnweightedEdge2)

  def self.weighted?
    false
  end

  def self.directed?
    true
  end

  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges : Enumerable)
    super
  end

  def <<(edge : UnweightedEdge2) : self
    raise IndexError.new unless 0 <= edge.from < size && 0 <= edge.to < size
    @graph[edge.from] << UnweightedEdge.new(edge.to)
    self
  end
end

class UnweightedUnGraph
  include Graph(UnweightedEdge, UnweightedEdge2)

  def self.weighted?
    false
  end

  def self.directed?
    false
  end

  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges : Enumerable)
    super
  end

  def <<(edge : UnweightedEdge2) : self
    raise IndexError.new unless 0 <= edge.from < size && 0 <= edge.to < size
    @graph[edge.from] << UnweightedEdge.new(edge.to)
    @graph[edge.to] << UnweightedEdge.new(edge.from)
    self
  end
end

module Graph(Edge, Edge2)
  # Returns the array of distance of each node from *start* or `nil`.
  # *block* must return `0` or `1`.
  def bfs01(start : Int, &block) : Array(Int32?)
    raise ArgumentError.new unless 0 <= start < size
    queue = Deque{start}
    dist = Array(Int32?).new(size, nil).tap(&.[start] = 0)
    while v = queue.shift?
      current_dist = dist[v].not_nil!
      graph[v].each do |edge|
        cost = yield edge
        raise ArgumentError.new("Unexpected cost: #{cost}") unless cost == 0 || cost == 1
        next_dist = current_dist + cost
        d = dist[edge.to]
        if d.nil? || next_dist < d
          dist[edge.to] = next_dist
          if cost == 0
            queue.unshift edge.to
          else
            queue.push edge.to
          end
        end
      end
    end
    dist
  end

  # Returns the array of distance of each node from *start* or `nil`.
  # All of cost of edge must be `0` or `1`.
  def bfs01(start : Int) : Array(Int32?)
    bfs01(start, &.cost)
  end

  # Returns the array of distance of each node from *start*.
  # *block* must return `0` or `1`.
  def bfs01!(start : Int32, &block) : Array(Int32)
    bfs01(start) { |edge| yield edge }.map(&.not_nil!)
  end

  # Returns the array of distance of each node from *start*.
  # All of cost of edge must be `0` or `1`.
  def bfs01!(start : Int) : Array(Int32)
    bfs01!(start, &.cost)
  end

  # Returns the distance from *start* to *goal* if path is present, otherwise returns `nil`.
  # *block* must return `0` or `1`.
  def bfs01_st(start : Int, goal : Int, &block) : Int32?
    raise ArgumentError.new unless 0 <= start < size
    queue = Deque{start}
    dist = Array(Int32?).new(size, nil).tap(&.[start] = 0)
    while v = queue.shift?
      current_dist = dist[v].not_nil!
      return current_dist if v == goal
      graph[v].each do |edge|
        cost = yield edge
        raise ArgumentError.new("Unexpected cost: #{cost}") unless cost == 0 || cost == 1
        next_dist = current_dist + cost
        d = dist[edge.to]
        if d.nil? || next_dist < d
          dist[edge.to] = next_dist
          if cost == 0
            queue.unshift edge.to
          else
            queue.push edge.to
          end
        end
      end
    end
    nil
  end

  # Returns the distance from *start* to *goal* if path is present, otherwise returns `nil`.
  # All of cost of edge must be `0` or `1`.
  def bfs01_st(start : Int, goal : Int) : Int32?
    bfs01_st(start, goal, &.cost)
  end

  # Returns the distance from *start* to *goal* if path is present, otherwise raises `ArgumentError`.
  # *block* must return `0` or `1`.
  def bfs01_st!(start : Int, goal : Int, &block) : Int32
    bfs01_st(start, goal) { |edge| yield edge } || raise ArgumentError.new
  end

  # Returns the distance from *start* to *goal* if path is present, otherwise raises `ArgumentError`.
  # All of cost of edge must be `0` or `1`.
  def bfs01_st!(start : Int, goal : Int) : Int32
    bfs01_st(start, goal, &.cost) || raise ArgumentError.new
  end
end
Back to top page