class NgLib::BinaryLifting(T)

Overview

ダブリングを実現します。

graph = NgLib::BinaryLifting(Int64).new(n) {
  {to[i], weight[i]}
}

graph.query
graph.where
graph.weight_sum

Defined in:

nglib/graph/binary_lifting.cr

Constructors

Instance Method Summary

Constructor Detail

def self.new(n : Int, limit : Int = UInt64::MAX // 2, initial : T = T.zero) #

n 頂点 0 辺のグラフを作ります。

移動回数の上限を limit で指定します。 initial でノードの初期値を指定します。

n = 10
graph = BinaryLifting.new(n)

[View source]
def self.new(n : Int, limit : Int = UInt64::MAX // 2, initial : T = T.zero, &) #

n 頂点 n 辺のグラフを作ります。

ブロックで各 i に対する移動先と重みをタプルで返す必要があります。

移動回数の上限を limit で指定します。 initial でノードの初期値を指定します。

n = 10
graph = BinaryLifting.new(n) { |i| {a[i].to_i32, 0} }

[View source]

Instance Method Detail

def add_edge(s : Int, t : Int, weight : T = T.zero) #

頂点 s から頂点 t に重み weight の辺を追加します。

n = 10
graph = BinaryLifting.new(n) { |i| {a[i].to_i32, 0} }
graph.add_edge(0, 1, 10)
graph.add_edge(1, 5, 3)
graph.add_edge(5, 1, 2)

[View source]
def build #

query　が高速にできるよう、データを構築します。


[View source]
def impl_log2(x : Int) : Int32 #

[View source]
def query(start : Int, times : Int) #

頂点 start から times 回移動する経路中の重みの総和と場所を返します。

n = 3
graph = BinaryLifting.new(n)
graph.add_edge(0, 1, 1)
graph.add_edge(1, 2, 10)
graph.add_edge(2, 0, 100)

graph.query(start: 0, times: 5) # => {2, 122}
graph.query(start: 1, times: 5) # => {0, 221}

[View source]
def query!(start : Int, times : Int) #

頂点 start から times 回移動する経路中の重みの総和と場所を返します。

build 済みかの確認を行いません。

n = 3
graph = BinaryLifting.new(n)
graph.add_edge(0, 1, 1)
graph.add_edge(1, 2, 10)
graph.add_edge(2, 0, 100)

graph.query!(start: 0, times: 5) # => {2, 122}
graph.query!(start: 1, times: 5) # => {0, 221}

[View source]
def size : Int32 #

[View source]
def weight_sum(start : Int, times : Int) #

頂点 start から times 回移動する経路中の重みの総和を返します。

n = 3
graph = BinaryLifting.new(n)
graph.add_edge(0, 1, 1)
graph.add_edge(1, 2, 10)
graph.add_edge(2, 0, 100)

graph.weight_sum(start: 0, times: 5) # => 122
graph.weight_sum(start: 1, times: 5) # => 221

[View source]
def weight_sum!(start : Int, times : Int) #

頂点 start から times 回移動する経路中の重みの総和を返します。

build 済みかの確認を行いません。

n = 3
graph = BinaryLifting.new(n)
graph.add_edge(0, 1, 1)
graph.add_edge(1, 2, 10)
graph.add_edge(2, 0, 100)

graph.weight_sum!(start: 0, times: 5) # => 122
graph.weight_sum!(start: 1, times: 5) # => 221

[View source]
def where(start : Int, times : Int) #

頂点 start から times 回移動したときいる場所を返します。

n = 3
graph = BinaryLifting.new(n)
graph.add_edge(0, 1, 1)
graph.add_edge(1, 2, 10)
graph.add_edge(2, 1, 100)

graph.where(start: 0, times: 5) # => 2
graph.where(start: 1, times: 5) # => 0

[View source]
def where!(start : Int, times : Int) #

頂点 start から times 回移動したときいる場所を返します。

build 済みかの確認を行いません。

n = 3
graph = BinaryLifting.new(n)
graph.add_edge(0, 1, 1)
graph.add_edge(1, 2, 10)
graph.add_edge(2, 0, 100)

graph.where!(start: 0, times: 5) # => 2
graph.where!(start: 1, times: 5) # => 0

[View source]