Class: EmailGraph::DirectedGraph

Inherits:
Object
  • Object
show all
Defined in:
lib/email_graph/directed_graph.rb

Overview

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

Has these additional specifications:

  • Vertices and edges are hashable objects; the latter should inherit from Edge

  • Efficient fetching of in-edges in addition to out

Direct Known Subclasses

InteractionGraph

Instance Method Summary collapse

Constructor Details

#initialize ⇒ DirectedGraph 



11
12
13
14
 
# File 'lib/email_graph/directed_graph.rb', line 11

def initialize
  @from_store = {}
  @to_store   = {}
end

Instance Method Details

#add_edge(e) ⇒ Object

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



49
50
51
52
 
# 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) ⇒ Object

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



42
43
44
45
 
# 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) ⇒ Object

A specific edge from v to w



27
28
29
 
# File 'lib/email_graph/directed_graph.rb', line 27

def edge(v, w)
  (@from_store[v] || []).find{ |e| e.to == w }
end

#edges ⇒ Object

All edges



22
23
24
 
# File 'lib/email_graph/directed_graph.rb', line 22

def edges
  @from_store.values.to_set.flatten
end

#edges_from(v) ⇒ Object

Out-edges from vertex v



32
33
34
 
# File 'lib/email_graph/directed_graph.rb', line 32

def edges_from(v)
  @from_store[v]
end

#edges_to(v) ⇒ Object

In-edges to vertex v



37
38
39
 
# File 'lib/email_graph/directed_graph.rb', line 37

def edges_to(v)
  @to_store[v]
end

#to_undirected(&edge_factory) ⇒ Object

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.



82
83
84
85
86
87
88
89
90
91
92
93
94
 
# 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 ⇒ Object

All vertices



17
18
19
 
# File 'lib/email_graph/directed_graph.rb', line 17

def vertices
  @from_store.keys
end

#with_each_edge_and_inverse(edges = nil, &block) ⇒ Object

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).



59
60
61
62
63
64
65
66
67
68
69
70
71
 
# 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