Module: Networkr

Defined in:
lib/networkr.rb,
lib/networkr/version.rb,
lib/networkr/graphs/graph.rb,
lib/networkr/graphs/digraph.rb,
lib/networkr/algorithms/prim.rb,
lib/networkr/algorithms/karger.rb,
lib/networkr/graphs/multigraph.rb,
lib/networkr/algorithms/dijkstra.rb,
lib/networkr/algorithms/kosaraju.rb

Defined Under Namespace

Classes: DiGraph, Graph, MultiGraph, Tracker

Constant Summary collapse

VERSION = 
"0.0.2"

Class Method Summary collapse

Class Method Details

.dijkstra(g, source_node) ⇒ Object 



11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
# File 'lib/networkr/algorithms/dijkstra.rb', line 11

def dijkstra(g, source_node)
  nodes_processed = [source_node]
  shortest_path_distances = {}
  shortest_path_distances[source_node] = 0

  while nodes_processed.length != g.length
    shortest = nil
    start_node = nil
    end_node = nil
    nodes_processed.each do |node|
      g.children_of(node).each do |v, options|
        if !nodes_processed.include?(v)
          if shortest.nil? || shortest_path_distances[node] + options[:weight] < shortest
            shortest = shortest_path_distances[node] + options[:weight]
            start_node = node
            end_node = v
          end
        end
      end
    end
    nodes_processed << end_node
    shortest_path_distances[end_node] = shortest
  end
  shortest_path_distances
end

.karger(g) ⇒ Object 



11
12
13
14
15
16
17
18
19
20
21
 
# File 'lib/networkr/algorithms/karger.rb', line 11

def karger(g)
  while g.length > 2
    node1 = g.adj.keys.sample
    node2 = g.children_of(node1).keys.sample
    e = [node1, node2]
    contract(g, node1, node2)
  end
  node1 = g.adj.keys[0]
  node2 = g.adj.keys[1]
  g.adj[node1][node2].length
end

.karger_repeated(g) ⇒ Object 



23
24
25
26
27
28
29
30
31
32
 
# File 'lib/networkr/algorithms/karger.rb', line 23

def karger_repeated(g)
  g_copy = g.deep_copy

  n = g.length
  mincut = n
  (n ** 2 * Math.log(n)).to_i.times do
    mincut = karger(g_copy) if karger(g_copy) < mincut
  end
  mincut
end

.kosaraju_num_scc(original_g, g_rev) ⇒ Numeric

Returns number of strongly connected components.

Parameters:

Returns:

  • (Numeric) —

    number of strongly connected components



23
24
25
26
27
28
 
# File 'lib/networkr/algorithms/kosaraju.rb', line 23

def kosaraju_num_scc(original_g, g_rev)
  tracker1 = Tracker.new
  tracker2 = Tracker.new
  tracker2 = kosaraju(original_g, g_rev, tracker1, tracker2)
  num_scc(tracker2)
end

.kosaraju_scc_sizes(original_g, g_rev) ⇒ Array<Numeric>

Returns sizes (numbers of nodes) of strongly connected components in descending order.

Parameters:

Returns:

  • (Array<Numeric>) —

    sizes (numbers of nodes) of strongly connected components in descending order



13
14
15
16
17
18
 
# File 'lib/networkr/algorithms/kosaraju.rb', line 13

def kosaraju_scc_sizes(original_g, g_rev)
  tracker1 = Tracker.new
  tracker2 = Tracker.new
  tracker2 = kosaraju(original_g, g_rev, tracker1, tracker2)
  sizes(tracker2)
end

.prim(g, source_node) ⇒ Object 



11
12
13
14
15
16
17
18
19
20
 
# File 'lib/networkr/algorithms/prim.rb', line 11

def prim(g, source_node)
  nodes_spanned = [source_node]
  tree_so_far = Graph.new
  while nodes_spanned.length != g.length
    e = min_edge(g, nodes_spanned)
    tree_so_far.add_edge(e[0][0], e[0][1], weight: e[1])
    nodes_spanned << e[0][1]
  end
  tree_so_far
end