class

NgLib::BinaryLifting(T)

Inherits Reference < Object

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

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

graph.query
graph.where
graph.weight_sum

Constructors

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

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

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

n = 10
graph = BinaryLifting.new(n)
Source
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} }
Source

Instance methods

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)
Source
build

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

Source
impl_log2(x : Int) : Int32
Source
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}
Source
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}
Source
size
Source
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
Source
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
Source
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
Source
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
Source