module Graph(Edge, Edge2)

Included Modules

Direct including types

Defined in:

graph.cr
graph/bfs.cr
graph/bfs01.cr
graph/bipartite_graph.cr
graph/components.cr
graph/compress.cr
graph/decompose.cr
graph/degree.cr
graph/detect_cycle.cr
graph/dijkstra.cr
graph/kruskal.cr
graph/namori_decompose.cr
graph/topological_sort.cr
graph/tree.cr
graph/tree_walk.cr

Constructors

Class Method Summary

Instance Method Summary

Instance methods inherited from module Enumerable(Edge2)

accumulate(init : U) : Array(U) forall U
accumulate : Array(T)
accumulate(init : U, &block : U, T -> U) : Array(U) forall U
accumulate(&block : T, T -> T) : Array(T) accumulate, mex : T mex, mex_sorted : T mex_sorted, tally(*, default : Int32) : Hash(T, Int32) tally, unique : self
unique(&) : self unique

Constructor Detail

def self.new(size : Int, edges : Enumerable) #

[View source]
def self.new(size : Int) #

[View source]

Class Method Detail

def self.restore_path(prev : Array(Int32?), v : Int) : Array(Int32) #

[View source]

Instance Method Detail

def <<(edge : Tuple) : self #

Add edge.


[View source]
abstract def <<(edge : Edge2) #

Add edge.


[View source]
def [](*args, **options) #

[View source]
def [](*args, **options, &) #

[View source]
def add_edges(edges : Enumerable) : self #

[View source]
def bfs(start : Int) : Array(Int32?) #

Returns the array of distance of each node from start or nil.


[View source]
def bfs!(start : Int) : Array(Int32) #

Returns the array of distance of each node from start.


[View source]
def bfs01(start : Int) : Array(Int32?) #

Returns the array of distance of each node from start or nil. All of cost of edge must be 0 or 1.


[View source]
def bfs01(start : Int, &) : Array(Int32?) #

Returns the array of distance of each node from start or nil. block must return 0 or 1.


[View source]
def bfs01!(start : Int) : Array(Int32) #

Returns the array of distance of each node from start. All of cost of edge must be 0 or 1.


[View source]
def bfs01!(start : Int32, &) : Array(Int32) #

Returns the array of distance of each node from start. block must return 0 or 1.


[View source]
def bfs01_st(start : Int, goal : Int) : Int32? #

Returns the distance from start to goal if path is present, otherwise returns nil. All of cost of edge must be 0 or 1.


[View source]
def bfs01_st(start : Int, goal : Int, &) : Int32? #

Returns the distance from start to goal if path is present, otherwise returns nil. block must return 0 or 1.


[View source]
def bfs01_st!(start : Int, goal : Int, &) : Int32 #

Returns the distance from start to goal if path is present, otherwise raises ArgumentError. block must return 0 or 1.


[View source]
def bfs01_st!(start : Int, goal : Int) : Int32 #

Returns the distance from start to goal if path is present, otherwise raises ArgumentError. All of cost of edge must be 0 or 1.


[View source]
def bfs_st(start : Int, goal : Int) : Int32? #

Returns the distance from start to goal if path is present, otherwise returns nil.


[View source]
def bipartite_graph : Array(Bool)? #

Returns table of color if the graph is bipartite graph, otherwise returns nil


[View source]
def components : Tuple(Int32, Array(Int32), Array(Set(Int32))) #

Returns {number of connected components, index, groups}.


[View source]
def compress : self #

Returns the graph that deleted isolated vertices.


[View source]
def decompose : Tuple(Array(self), Array(Tuple(Int32, Int32)), Array(Array(Int32))) #

Decomposes the graph into each conected components.


[View source]
def detect_cycle : Array(Edge)? #

[View source]
def diameter #

Calculates diameter of the tree and returns {distance, vertex1, vertex2}.


[View source]
def dijkstra(start : Int) #

Returns the array of distance of each node from start or nil.


[View source]
def dijkstra(start : Int, goal : Int) #

Returns the distance of start to goal or nil.


[View source]
def dijkstra!(start : Int, goal : Int) #

Returns the distance of start to goal.


[View source]
def dijkstra!(start : Int) #

Returns the array of distance of each node from start.


[View source]
def dijkstra_with_path(start : Int, goal : Int) #

[View source]
def dijkstra_with_prev(start : Int) #

[View source]
def each(&) : Nil #

Yields each edge of the graph, ans returns nil.


[View source]
def each_child(vertex : Int, parent) #

[View source]
def each_child(vertex : Int, parent, &) : Nil #

[View source]
def graph : Array(Array(Edge)) #

[View source]
def indegree : Array(Int32) #

Returns table of indegree.


[View source]
def inspect(io : IO) : Nil #

[View source]
def kruskal #

Calculates cost of minimum spanning tree if the graph is connected, otherwise returns nil.


[View source]
def namori_decompose : Tuple(self, Array(Int32)) #

Returns forest and cycle of the undirected graph with equal number of vertices and edges.


[View source]
def outdegree : Array(Int32) #

Returns table of outdegree.


[View source]
def parent_table(root : Int32) : Array(Int32?) #

[View source]
def post_order(root : Int) : Array(Int32) #

[View source]
def pre_order(root : Int) : Array(Int32) #

[View source]
def reverse : self #

[View source]
def size(*args, **options, &) #

[View source]
def size(*args, **options) #

[View source]
def subtree_size(root : Int32) : Array(Int32) #

[View source]
def to_s(io : IO) : Nil #

[View source]
def to_undirected : self #

[View source]
def topological_sort : Array(Int32)? #

[View source]
def tree_distance(root : Int32) #

Returns the distance of each node from root.


[View source]
def tree_path(start : Int32, goal : Int32, &) : Nil #

[View source]
def tree_path(start : Int32, goal : Int32) : Array(Int32) #

[View source]