class Dag::Graph(V)

Overview

Graph class represents a directed acyclic graph with unweighted edges. Graph is represented as adjecency list of its vertices. Graph uses a Hash(V) storing its elements. V must be a uniqe value identifying a vertex of graph.

Example:

dag = Dag::Graph(Int32).new
dag.add 1, 2, 3, 4, 5
dag.add_edge({1, 3}, {1, 2}, {3, 4})

Included Modules

Defined in:

dag.cr

Instance Method Summary

Instance Method Detail

def ==(other : Graph(V)) #

Two graph equals if they have vertices with same ids and the other has an edge between vertices with same ids if the first graph has an edge.

Example:

dag1 = Dag::Graph(Int32).new
dag1.add 1
dag1.add 3
dag1.add 5
dag1.add_edge 1, 3
dag1.add_edge 5, 3

dag2 = Dag::Graph(Int32).new
dag2.add 1
dag2.add 3
dag2.add 5
dag2.add_edge 1, 3
dag2.add_edge 5, 3
dag1.should eq(dag2)

dag1 == dag2 # => true

[View source]
def ==(other) #

Compares with other vertex. It is allways false.

Example:

dag = Dag::Graph(Int32).new
dag.add(1)
dag == 1 # => false
dag == 2 # => false

[View source]
def add(vertex : V) #

Adds a new vertex to the graph. If vertex is already exists function will raise VertexExistsError Example:

dag = Dag::Graph(Int32).new
dag.add 1
dag.add 2
dag.to_a # => [1,2]

[View source]
def add(*vertices : V) #

Adds a new vertex to the graph. If vertex is already exists function will raise VertexExistsError Example:

dag = Dag::Graph(Int32).new
dag.add 1
dag.add 2
dag.to_a # => [1,2]

[View source]
def add_edge(from : V, to : V) #

Adds a new edge to graph. Function will insert vertex too if one of the vertices doesn't exists. If edge is already exists it will not add it again.

Example:

dag = Dag::Graph(Int32).new
dag.add_edge 1, 2
dag.to_a           # => [1, 2]
dag.has_edge? 1, 2 # => true

[View source]
def add_edge(edge : Tuple(V, V)) #

Adds a new edge to graph. Function will insert vertex too if one of the vertices doesn't exists. If edge is already exists it will not add it again.

Example:

dag = Dag::Graph(Int32).new
dag.add_edge 1, 2
dag.to_a           # => [1, 2]
dag.has_edge? 1, 2 # => true

[View source]
def add_edge(*edges : Tuple(V, V)) #

Adds a new edge to graph. Function will insert vertex too if one of the vertices doesn't exists. If edge is already exists it will not add it again.

Example:

dag = Dag::Graph(Int32).new
dag.add_edge 1, 2
dag.to_a           # => [1, 2]
dag.has_edge? 1, 2 # => true

[View source]
def delete(vertex : V) #

Deletes a vertex from graph. Raises VertexNotExistsError when vertex doesn't exists in graph.

Example:

dag = Dag::Graph(Int32).new
dag.add 1
dag.add 2
dag.add_edge 1, 2
dag.delete 2
dag.has? 2 # => false

[View source]
def delete_edge(from : V, to : V) #

Deletes an edge from graph. If one of the vertices doesn't exists, function will raise VertexNotExistsError. If edge doesn't exists, function will do nothing.

Example:

dag = Dag::Graph(Int32).new
dag.add 1
dag.add 2
dag.add_edge 1, 2
dag.delete_edge 1, 2

[View source]
def descendant?(v : V, other : V) : Bool #

Check if other is a descentant of v

If two vertices, [a, b] are topologically sorted, then a is not a descendant of b.

Example:

dag = Dag::Graph(Int32).new
dag.add 1, 2, 3, 4, 5
dag.add_edge({1, 2}, {2, 3}, {3, 4}, {5, 4})
dag.descendant? 1, 4 # => true
dag.descendant? 1, 5 # => false
dag.descendant? 2, 1 # => false
dag.valid?           # => false

[View source]
def each(&) #

Calls a given block on every key and vertex pairs stored in the graph topological order. Topological order is computed with Kahn's algorytm.

Example:

dag = Dag::Graph(Int32).new
dag.add(1, 2, 3, 4)
dag.add_edge({1, 2}, {3, 4})
dag.each { |v| p! v }
dag.to_a # => [1, 2, 3, 4 ]

[View source]
def each : Iterator(V) #

Retreives an iterator of the graph. The iterator will retreive vertices in topological order.

Example:

dag = Dag::Graph(Int32).new
(1...10).each { |i| dag.add i }
dag.add_edge({1, 3}, {5, 9}, {8, 7}, {8, 6}, {6, 4}, {4, 3}, {4, 7})
dag.each.size.should eq 9
dag.each.to_a.should eq [1, 2, 5, 8, 9, 6, 4, 3, 7]

[View source]
def has?(vertex : V) #

Checks whether a vertex exists in graph

Example:

dag = Dag::Graph(Int32).new
dag.add 1
dag.add 2
dag.has? 1 # => true
dag.has? 2 # => true
dag.has? 3 # => false

[View source]
def has_edge?(from : V, to : V) #

Checks whether an edge exists. Raises VertexNotExistsError when one of the vertices doesn't exists.

Example:

dag = Dag::Graph(Int32).new
dag.add_edge 1, 2
dag.has_edge? 1, 2 # => true

[View source]
def predecessors(vertex : V) #

Gets the predecessors of a vertex identified by key. Example:

dag = Dag::Graph(Int32).new
dag.add 1, 2, 3, 4
dag.add_edge({1, 2}, {2, 3}, {2, 4})
dag.predecessors 2 # => [1]

[View source]
def roots #

Retreives all the root vertices of the graph

Example:

dag = Dag::Graph(Int32).new
dag.add 1, 2, 3
dag.add_edge 1, 2
dag.roots # => [1, 3]

[View source]
def successors(vertex : V) #

Gets the successors of a vertex identified by key.

Example:

dag = Dag::Graph(Int32).new
dag.add 1, 2, 3, 4
dag.add_edge({1, 2}, {2, 3}, {2, 4})
dag.successors(2) # => [3,4]

[View source]
def valid? #

Validate a graph, whether it is acyclic.

Example:

dag = Dag::Graph(Int32).new
dag.add 1, 2, 3, 4
dag.add_edge({1, 2}, {2, 3}, {3, 4})
dag.valid? # => true
dag.add_edge(4, 2)
dag.valid? # => false

[View source]