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 ]