Class: NetworkX::DiGraph

Inherits:
Graph
  • Object
show all
Defined in:
lib/networkx/digraph.rb

Overview

Describes the class for making Directed Graphs

Direct Known Subclasses

MultiDiGraph

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods inherited from Graph

#add_edges, #add_edges_from, #add_nodes, #add_nodes_from, #add_path, #add_weighted_edge, #add_weighted_edges, #add_weighted_edges_from, balanced_tree, barbell_graph, #bfs_edges, #bfs_nodes, bull_graph, circular_ladder_graph, complete_edges, complete_graph, cubical_graph, cycle_graph, #degree, #dfs_edges, #dfs_postorder_nodes, #dfs_preorder_nodes, diamond_graph, dodecahedral_graph, #each_bfs_edge, #each_bfs_node, #each_dfs_edge, #each_dfs_postorder_node, #each_dfs_preorder_node, #each_edge, #each_node, #edge?, #edges, empty_graph, #get_edge_data, #get_node_data, heawood_graph, house_graph, house_x_graph, #info, ladder_graph, lollipop_graph, moebius_kantor_graph, #multigraph?, #neighbours, #node?, null_graph, #number_of_nodes, octahedral_graph, path_graph, #put_graph_x2, read_edgelist, read_weighted_edgelist, #remove_edges, #remove_nodes, star_graph, tetrahedral_graph, trivial_graph, wheel_graph

Constructor Details

#initialize(**graph_attrs) ⇒ DiGraph

Constructor for initializing graph

Examples:

Initialize a graph with attributes ‘type’ and ‘name’

graph = NetworkX::Graph.new(name: "Social Network", type: "undirected")

Parameters:

  • graph_attrs (Hash{ Object => Object }) —

    the graph attributes in a hash format



19
20
21
22
23
 
# File 'lib/networkx/digraph.rb', line 19

def initialize(**graph_attrs)
  super(**graph_attrs)

  @pred = {}
end

Instance Attribute Details

#adj ⇒ Hash{ Object => Hash{ Object => Hash{ Object => Object } } } (readonly)

Stores the edges and their attributes in an adjencency list form

Returns:

  • (Hash{ Object => Hash{ Object => Hash{ Object => Object } } }) —

    the current value of adj



10
11
12
 
# File 'lib/networkx/digraph.rb', line 10

def adj
  @adj
end

#graph ⇒ Hash{ Object => Object } (readonly)

Stores the attributes of the graph

Returns:

  • (Hash{ Object => Object }) —

    the current value of graph



10
11
12
 
# File 'lib/networkx/digraph.rb', line 10

def graph
  @graph
end

#nodes(data: true) ⇒ Hash{ Object => Hash{ Object => Object } } (readonly)

Stores the nodes and their attributes

Returns:

  • (Hash{ Object => Hash{ Object => Object } }) —

    the current value of nodes



10
11
12
 
# File 'lib/networkx/digraph.rb', line 10

def nodes
  @nodes
end

#pred ⇒ Hash{ Object => Hash{ Object => Hash{ Object => Object } } } (readonly)

Stores the reverse edges and their attributes in an adjencency list form

Returns:

  • (Hash{ Object => Hash{ Object => Hash{ Object => Object } } }) —

    the current value of pred



10
11
12
 
# File 'lib/networkx/digraph.rb', line 10

def pred
  @pred
end

Instance Method Details

#add_edge(node1, node2, **edge_attrs) ⇒ Object

Adds the respective edge

Examples:

Add an edge with attribute name

graph.add_edge(node1, node2, name: "Edge1")

Add an edge with no attribute

graph.add_edge("Bangalore", "Chennai")

Parameters:

  • node1 (Object) —

    the first node of the edge

  • node2 (Object) —

    the second node of the edge

  • edge_attrs (Hash{ Object => Object }) —

    the hash of the edge attributes



36
37
38
39
40
41
42
43
 
# File 'lib/networkx/digraph.rb', line 36

def add_edge(node1, node2, **edge_attrs)
  add_node(node1)
  add_node(node2)

  edge_attrs = (@adj[node1][node2] || {}).merge(edge_attrs)
  @adj[node1][node2] = edge_attrs
  @pred[node2][node1] = edge_attrs
end

#add_node(node, **node_attrs) ⇒ Object

Adds a node and its attributes to the graph

Examples:

Add a node with attribute ‘type’

graph.add_node("Noida", type: "city")

Parameters:

  • node (Object) —

    the node object

  • node_attrs (Hash{ Object => Object }) —

    the hash of the attributes of the node



52
53
54
55
56
 
# File 'lib/networkx/digraph.rb', line 52

def add_node(node, **node_attrs)
  super(node, **node_attrs)

  @pred[node] = {} unless @pred.has_key?(node)
end

#clear ⇒ Object

Clears the graph

Examples:

graph.clear


102
103
104
105
106
 
# File 'lib/networkx/digraph.rb', line 102

def clear
  super

  @pred.clear
end

#directed? ⇒ Boolean

Returns:

  • (Boolean) 


230
231
232
 
# File 'lib/networkx/digraph.rb', line 230

def directed?
  true
end

#edge_subgraph(edges) ⇒ Object

Returns subgraph consisting of given edges

Examples:

graph.edge_subgraph([%w[Nagpur Wardha], %w[Nagpur Mumbai]])

Parameters:

  • edges (Array<Object, Object>) —

    the edges to be included in the subraph



211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
 
# File 'lib/networkx/digraph.rb', line 211

def edge_subgraph(edges)
  case edges
  when Array, Set
    sub_graph = NetworkX::DiGraph.new(**@graph)
    edges.each do |u, v|
      raise KeyError, "Edge between #{u} and #{v} does not exist in the graph!" unless @nodes.has_key?(u) \
                                                                                && @adj[u].has_key?(v)

      sub_graph.add_node(u, **@nodes[u])
      sub_graph.add_node(v, **@nodes[v])
      sub_graph.add_edge(u, v, **@adj[u][v])
    end
    sub_graph
  else
    raise ArgumentError, 'Expected Argument to be Array or Set of edges, ' \
                         "received #{edges.class.name} instead."
  end
end

#in_degree(node) ⇒ Object

Returns in-degree of a given node

Examples:

graph.in_degree(node)

Parameters:

  • node (Object) —

    the node whose in degree is to be calculated



140
141
142
 
# File 'lib/networkx/digraph.rb', line 140

def in_degree(node)
  @pred[node].length
end

#number_of_edges ⇒ Object

Returns number of edges

Examples:

graph.number_of_edges


112
113
114
 
# File 'lib/networkx/digraph.rb', line 112

def number_of_edges
  @adj.values.map(&:length).sum
end

#out_degree(node) ⇒ Object

Returns out-degree of a given node

Examples:

graph.out_degree(node)

Parameters:

  • node (Object) —

    the node whose out degree is to be calculated



150
151
152
 
# File 'lib/networkx/digraph.rb', line 150

def out_degree(node)
  @adj[node].length
end

#remove_edge(node1, node2) ⇒ Object

Removes edge from the graph

Examples:

graph.remove_edge('Noida', 'Bangalore')

Parameters:

  • node1 (Object) —

    the first node of the edge

  • node2 (Object) —

    the second node of the edge

Raises:

  • (KeyError) 


89
90
91
92
93
94
95
96
 
# File 'lib/networkx/digraph.rb', line 89

def remove_edge(node1, node2)
  raise KeyError, "#{node1} is not a valid node." unless @nodes.has_key?(node1)
  raise KeyError, "#{node2} is not a valid node" unless @nodes.has_key?(node2)
  raise KeyError, 'The given edge is not a valid one.' unless @adj[node1].has_key?(node2)

  @adj[node1].delete(node2)
  @pred[node2].delete(node1)
end

#remove_node(node) ⇒ Object

Removes node from the graph

Examples:

graph.remove_node("Noida")

Parameters:

  • node (Object) —

    the node to be removed

Raises:

  • (KeyError) 


68
69
70
71
72
73
74
75
76
77
78
79
80
 
# File 'lib/networkx/digraph.rb', line 68

def remove_node(node)
  raise KeyError, "Error in deleting node #{node} from Graph." unless @nodes.has_key?(node)

  neighbours = @adj[node]
  neighbours.each_key { |k| @pred[k].delete(node) }
  @pred[node].each_key do |k|
    @adj[k].delete(node)
  end

  @pred.delete(node)
  @adj.delete(node)
  @nodes.delete(node)
end

#reverse ⇒ Object

Returns the reversed version of the graph

Examples:

graph.reverse


158
159
160
161
162
163
164
165
 
# File 'lib/networkx/digraph.rb', line 158

def reverse
  new_graph = NetworkX::DiGraph.new(**@graph)
  @nodes.each { |u, attrs| new_graph.add_node(u, **attrs) }
  @adj.each do |u, edges|
    edges.each { |v, attrs| new_graph.add_edge(v, u, **attrs) }
  end
  new_graph
end

#size(is_weighted = false) ⇒ Object

Returns the size of graph

Examples:

graph.size(true)

Parameters:

  • is_weighted (Bool) (defaults to: false) —

    if true, method returns sum of weights of all edges else returns number of edges



123
124
125
126
127
128
129
130
131
132
 
# File 'lib/networkx/digraph.rb', line 123

def size(is_weighted = false)
  if is_weighted
    graph_size = 0
    @adj.each do |_, hash_val|
      hash_val.each { |_, v| graph_size += v[:weight] if v.has_key?(:weight) }
    end
    return graph_size
  end
  number_of_edges
end

#subgraph(nodes) ⇒ Object

Returns subgraph consisting of given array of nodes

Examples:

graph.subgraph(%w[Mumbai Nagpur])

Parameters:

  • nodes (Array<Object>) —

    the nodes to be included in the subgraph



186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
 
# File 'lib/networkx/digraph.rb', line 186

def subgraph(nodes)
  case nodes
  when Array, Set
    sub_graph = NetworkX::DiGraph.new(**@graph)
    nodes.each do |u|
      raise KeyError, "#{u} does not exist in the current graph!" unless node?(u)

      sub_graph.add_node(u, **@nodes[u])
      @adj[u].each do |v, uv_attrs|
        sub_graph.add_edge(u, v, **uv_attrs) if @adj[u].has_key?(v) && nodes.include?(v)
      end
    end
    sub_graph
  else
    raise ArgumentError, 'Expected Argument to be Array or Set of nodes, ' \
                         "received #{nodes.class.name} instead."
  end
end

#to_undirected ⇒ Object

Returns the undirected version of the graph

Examples:

graph.to_undirected


171
172
173
174
175
176
177
178
 
# File 'lib/networkx/digraph.rb', line 171

def to_undirected
  new_graph = NetworkX::Graph.new(**@graph)
  @nodes.each { |u, attrs| new_graph.add_node(u, **attrs) }
  @adj.each do |u, edges|
    edges.each { |v, attrs| new_graph.add_edge(u, v, **attrs) }
  end
  new_graph
end