class EmailGraph::DirectedGraph

Graph with single, directed edges between vertices; loops allowed.

Has these additional specifications:

Public Class Methods

new() click to toggle source
# File lib/email_graph/directed_graph.rb, line 11
def initialize
  @from_store = {}
  @to_store   = {}
end

Public Instance Methods

add_edge(e) click to toggle source

Adds an edge and associated vertices if they don’t already exist and returns the edge

# File lib/email_graph/directed_graph.rb, line 49
def add_edge(e)
  add_vertex(e.from); add_vertex(e.to)
  (@from_store[e.from].add?(e) && @to_store[e.to].add(e) && e) || edge(e.from, e.to)
end
add_vertex(v) click to toggle source

Adds a vertex if it doesn’t already exist and returns it

# File lib/email_graph/directed_graph.rb, line 42
def add_vertex(v)
  @from_store[v] ||= Set.new
  @to_store[v]   ||= Set.new
end
edge(v, w) click to toggle source

A specific edge from v to w

# File lib/email_graph/directed_graph.rb, line 27
def edge(v, w)
  (@from_store[v] || []).find{ |e| e.to == w }
end
edges() click to toggle source

All edges

# File lib/email_graph/directed_graph.rb, line 22
def edges
  @from_store.values.to_set.flatten
end
edges_from(v) click to toggle source

Out-edges from vertex v

# File lib/email_graph/directed_graph.rb, line 32
def edges_from(v)
  @from_store[v]
end
edges_to(v) click to toggle source

In-edges to vertex v

# File lib/email_graph/directed_graph.rb, line 37
def edges_to(v)
  @to_store[v]
end
to_undirected(&edge_factory) click to toggle source

Converts to an instance of EmailGraph::Undirected graph.

The optional edge_factory block should take a pair of an edge and its inverse (if it exists), and return either an undirected edge-ish or if there should be no edge between the two vertices, then return nil. If no block is passed, an UndirectedEdge will be created if both the edge and its inverse exist.

Only adds vertices that have edges, i.e., no isolated vertices in result.

# File lib/email_graph/directed_graph.rb, line 82
def to_undirected(&edge_factory)
  edge_factory ||= Proc.new{ |e1, e2| UndirectedEdge.new(e1.from, e1.to) if e1 && e2 }      

  edges = Set.new
  with_each_edge_and_inverse do |e, e_inverse|
    new_edge = edge_factory.call(e, e_inverse)
    edges.add(new_edge) if new_edge
  end

  UndirectedGraph.new.tap do |g|
    edges.each{ |e| g.add_edge(e) } 
  end
end
vertices() click to toggle source

All vertices

# File lib/email_graph/directed_graph.rb, line 17
def vertices
  @from_store.keys
end
with_each_edge_and_inverse(edges=nil, &block) click to toggle source

Yields each edge and its inverse to the provided block.

Option to provide edges; default is all edges.

A pair set is yielded only once (not again in reverse).

# File lib/email_graph/directed_graph.rb, line 59
def with_each_edge_and_inverse(edges=nil, &block)
  edges ||= self.edges

  yielded_pairs = Set.new
  edges.each do |e|
    pair = Set.new([e.from, e.to])
    if !yielded_pairs.include?(pair)
      e_inverse = edge(e.to, e.from)
      block.call(e, e_inverse)
      yielded_pairs << pair
    end
  end
end