class Dag::Graph(V)
- Dag::Graph(V)
- Reference
- Object
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
- Enumerable(V)
- Iterable(V)
Defined in:
dag.crInstance Method Summary
-
#==(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.
-
#==(other)
Compares with other vertex.
-
#add(vertex : V)
Adds a new vertex to the graph.
-
#add(*vertices : V)
Adds a new vertex to the graph.
-
#add_edge(from : V, to : V)
Adds a new edge to graph.
-
#add_edge(edge : Tuple(V, V))
Adds a new edge to graph.
-
#add_edge(*edges : Tuple(V, V))
Adds a new edge to graph.
-
#delete(vertex : V)
Deletes a vertex from graph.
-
#delete_edge(from : V, to : V)
Deletes an edge from graph.
-
#descendant?(v : V, other : V) : Bool
Check if
other
is a descentant ofv
-
#each(&)
Calls a given block on every key and vertex pairs stored in the graph topological order.
-
#each : Iterator(V)
Retreives an iterator of the graph.
-
#has?(vertex : V)
Checks whether a vertex exists in graph
-
#has_edge?(from : V, to : V)
Checks whether an edge exists.
-
#predecessors(vertex : V)
Gets the predecessors of a vertex identified by key.
-
#roots
Retreives all the root vertices of the graph
-
#successors(vertex : V)
Gets the successors of a vertex identified by key.
-
#valid?
Validate a graph, whether it is acyclic.
Instance Method Detail
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
Compares with other vertex. It is allways false.
Example:
dag = Dag::Graph(Int32).new
dag.add(1)
dag == 1 # => false
dag == 2 # => false
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]
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]
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
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
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
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
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
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
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 ]
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]
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
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
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]
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]
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]
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