Class: CRDT::ORGraph

Inherits:
Object
  • Object
show all
Defined in:
lib/crdt/or_graph.rb

Overview

Observe Remove Graph (variant of 2P2P Graph)

This is a general purpose graph data type. It works by keeping a 2P set for vertices and an OR set for edges

Vertices are created uniquely on a node, and are represented with a token. It is left to the user to tie this token to their internal data. When merging changes, removes take precedence over adds, which can cause some surprising behavior when removing vertices

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(node_identity = Thread.current.object_id, token_counter = 0) ⇒ ORGraph

Create a new graph



10
11
12
13
14
15
 
# File 'lib/crdt/or_graph.rb', line 10

def initialize(node_identity = Thread.current.object_id, token_counter = 0)
  @node_identity = node_identity
  @token_counter = token_counter
  @vertices = {}
  @edges = {}
end

Instance Attribute Details

#edges ⇒ Object

Returns the value of attribute edges.



17
18
19
 
# File 'lib/crdt/or_graph.rb', line 17

def edges
  @edges
end

#vertices ⇒ Object

Returns the value of attribute vertices.



17
18
19
 
# File 'lib/crdt/or_graph.rb', line 17

def vertices
  @vertices
end

Class Method Details

.from_h(hash) ⇒ Object

Create a new Graph from a hash, such as that deserialized from JSON



94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
# File 'lib/crdt/or_graph.rb', line 94

def self.from_h(hash)
  graph = ORGraph.new(hash["node_identity"], hash["token_counter"])

  hash["vertices"].each do |token, vertex|
    graph.vertices[token] ||= {
      incoming_edges: vertex[:incoming_edges].dup,
      outgoing_edges: vertex[:outgoing_edges].dup,
      removed: vertex[:removed],
    }
  end
  hash["edges"].each do |token, edge|
    graph.edges[token] = {
      observed: edge[:observed].dup,
      removed: edge[:removed].dup,
    }
  end

  return graph
end

Instance Method Details

#add_edge(from, to) ⇒ Object

add an edge leading from the given vertex to the given vertex

Returns:

  • token representing the created edge



56
57
58
59
60
61
62
63
64
 
# File 'lib/crdt/or_graph.rb', line 56

def add_edge(from, to)
  @vertices[from][:outgoing_edges] << to
  @vertices[to][:incoming_edges] << from
  token = edge_token(from, to)
  @edges[token] ||= { observed: [], removed: [] }
  @edges[token][:observed] << issue_token

  return token
end

#create_vertex ⇒ Object

Add a new vertex to the graph

Returns:

  • token representing the newly created vertex



46
47
48
49
50
51
 
# File 'lib/crdt/or_graph.rb', line 46

def create_vertex
  token = issue_token
  # the edge arrays are a performance optimization to provide O(1) lookup for edges by vertex
  @vertices[token] = { incoming_edges: [], outgoing_edges: [], removed: false }
  return token
end

#has_edge?(from, to) ⇒ Boolean

Test if an edge exists between the given vertices

Returns:

  • (Boolean) 


27
28
29
30
31
 
# File 'lib/crdt/or_graph.rb', line 27

def has_edge?(from, to)
  edge = @edges[edge_token(from, to)]
  return false unless edge
  return ! edge[:observed].empty?
end

#has_vertex?(token) ⇒ Boolean

Test if a given vertex token is in this graph

Returns:

  • (Boolean) 


20
21
22
23
24
 
# File 'lib/crdt/or_graph.rb', line 20

def has_vertex?(token)
  vertex = @vertices[token]
  return false unless vertex
  return ! vertex[:removed]
end

#incoming_edges(to) ⇒ Object

Get a list of all the edges that terminate at the given vertex



39
40
41
 
# File 'lib/crdt/or_graph.rb', line 39

def incoming_edges(to)
  @vertices[to][:incoming_edges].map { |from| [from, to] }
end

#merge(other) ⇒ Object

Perform a one-way merge, bringing in changes from another graph



115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
# File 'lib/crdt/or_graph.rb', line 115

def merge(other)
  other.vertices.each do |token, vertex|
    @vertices[token] ||= {
      incoming_edges: [],
      outgoing_edges: [],
      removed: false,
    }

    # cleaning out removed edges is taken care of while merging edges
    @vertices[token][:incoming_edges] |= vertex[:incoming_edges]
    @vertices[token][:outgoing_edges] |= vertex[:outgoing_edges]
    @vertices[token][:removed] |= vertex[:removed]
  end
  other.edges.each do |edge_token, edge|
    from, to = from_edge_token(edge_token)
    @edges[edge_token] ||= {
      observed: [],
      removed: [],
    }

    @edges[edge_token][:observed] |= edge[:observed]
    @edges[edge_token][:removed] |= edge[:removed]
    @edges[edge_token][:observed] -= @edges[edge_token][:removed]

    # vertex removal takes precedence over edge creation
    if @vertices[from][:removed] || @vertices[to][:removed]
      @edges[edge_token][:removed] += @edges[edge_token][:observed]
      @edges[edge_token][:observed] = []
    end

    if @edges[edge_token][:observed].empty?
      @vertices[to][:incoming_edges].delete(from)
      @vertices[from][:outgoing_edges].delete(to)
    end
  end
end

#outgoing_edges(from) ⇒ Object

Get a list of all the edges that originate at the given vertex



34
35
36
 
# File 'lib/crdt/or_graph.rb', line 34

def outgoing_edges(from)
  @vertices[from][:outgoing_edges].map { |to| [from, to] }
end

#remove_edge(from, to) ⇒ Object

remove an edge from this graph



75
76
77
78
79
80
81
 
# File 'lib/crdt/or_graph.rb', line 75

def remove_edge(from, to)
  edge = @edges[edge_token(from, to)]
  edge[:removed] += edge[:observed]
  edge[:observed] = []
  @vertices[from][:outgoing_edges] -= [to]
  @vertices[to][:outgoing_edges] -= [from]
end

#remove_vertex(vertex) ⇒ Object

remove a vertex from this graph, and any edges that involve it



67
68
69
70
71
72
 
# File 'lib/crdt/or_graph.rb', line 67

def remove_vertex(vertex)
  @vertices[vertex][:removed] = true
  (incoming_edges(vertex) + outgoing_edges(vertex)).each do |from, to|
    remove_edge(from, to)
  end
end

#to_h ⇒ Object

Get a hash representation of this graph, suitable for serialization to JSON



84
85
86
87
88
89
90
91
 
# File 'lib/crdt/or_graph.rb', line 84

def to_h
  return {
    node_identity: @node_identity,
    token_counter: @token_counter,
    vertices: @vertices,
    edges: @edges,
  }
end