Class: Graphsrb::Digraph

Inherits:
BaseGraph show all
Defined in:
lib/graphsrb/digraph.rb

Overview

Directed graph

Instance Method Summary collapse

Methods inherited from BaseGraph

#add_edge, #add_vertex, #clear, #copy, #edge_count, #edges, #has_vertex?, #initialize, #remove_vertex, #vertex_count, #vertices

Constructor Details

This class inherits a constructor from Graphsrb::BaseGraph

Instance Method Details

#adjacent_vertices(vertex) ⇒ Object Also known as: neighborhood

Retrieves adjacent vertices of a vertex (takes only outgoing edeges)



5
6
7
8
9
10
11
 
# File 'lib/graphsrb/digraph.rb', line 5

def adjacent_vertices(vertex)
  nodes = []
  id = vertex.id
  nodes = adj_table[id].nodes unless adj_table[id].nil?
  #Convert nodes into vertices
  nodes.map{|node| _create_vertex(node.vertex.id)}
end

#edge(v, u) ⇒ Object

Retrieves an edge



22
23
24
25
26
27
28
 
# File 'lib/graphsrb/digraph.rb', line 22

def edge(v, u)
  id1, id2 = v.id, u.id
  if has_vertex?(id1)
    node = adj_table[id1].find(_create_node(id2))
    return _create_edge(id1, id2, weight:node.weight) if node
  end
end

#has_edge?(id1, id2) ⇒ Boolean Also known as: edge?

Checks whether the digraph has an edge

Returns:

  • (Boolean) 


16
17
18
 
# File 'lib/graphsrb/digraph.rb', line 16

def has_edge?(id1, id2)
  has_vertex?(id1) && adj_table[id1].has_node?(_create_node(id2))
end

#incoming_edges(v) ⇒ Object

Retrieves incoming edges of a vertex



56
57
58
59
 
# File 'lib/graphsrb/digraph.rb', line 56

def incoming_edges(v)
  #Convert nodes into edges
  _incoming_nodes(v.id).map{|node| _create_edge(node.vertex.id, v.id, weight:node.weight)}
end

#increase_weight(v, u, dw) ⇒ Object

Increses edge weight by w



37
38
39
40
 
# File 'lib/graphsrb/digraph.rb', line 37

def increase_weight(v, u, dw)
  id1, id2 = v.id, u.id
  adj_table[id1].increase_weight(_create_node(id2), dw) if has_vertex?(id1)
end

#indegree(v) ⇒ Object

Returns in-degree of a vertex



67
68
69
 
# File 'lib/graphsrb/digraph.rb', line 67

def indegree(v)
  _incoming_nodes(v.id).size
end

#outdegree(v) ⇒ Object

Returns out-degree of a vertex



62
63
64
 
# File 'lib/graphsrb/digraph.rb', line 62

def outdegree(v)
  _outgoing_nodes(v.id).size
end

#outgoing_edges(v) ⇒ Object

Retrieves outgoing edges of a vertex



50
51
52
53
 
# File 'lib/graphsrb/digraph.rb', line 50

def outgoing_edges(v)
  #Convert nodes into edges
  _outgoing_nodes(v.id).map{|node| _create_edge(v.id, node.vertex.id, weight:node.weight)}
end

#remove_edge(id1, id2) ⇒ Object

Remove an edge from the graph



44
45
46
47
 
# File 'lib/graphsrb/digraph.rb', line 44

def remove_edge(id1, id2)
  adj_table[id1].delete(_create_node(id2)) if has_vertex?(id1)
  true
end

#update_weight(v, u, w) ⇒ Object

Updates edge weight



31
32
33
34
 
# File 'lib/graphsrb/digraph.rb', line 31

def update_weight(v, u, w)
  id1, id2 = v.id, u.id
  adj_table[id1].update_weight(_create_node(id2), w) if has_vertex?(id1)
end