Class: Yargi::Digraph

Inherits:
Object
  • Object
show all
Includes:
Markable
Defined in:
lib/yargi/random.rb,
lib/yargi/digraph.rb,
lib/yargi/digraph_edge.rb,
lib/yargi/digraph_vertex.rb

Overview

Directed graph implementation.

  • All selection methods (vertices, each_vertex, edges, each_edge) implement the predicate-selection mechanism (they accept a predicate filter as well as a predicate block, with a AND semantics when used conjointly).

  • Removal methods (remove_vertex, remove_vertices, remove_edge, remove_edges) accept varying arguments that are automatically converted to set of vertices or edges. Recognized arguments are Vertex and Edge instances, VertexSet and EdgeSet instances, Array instances, and predicates. When multiple arguments are used conjointly, a OR-semantics is applied.

    Example:

    graph.remove_vertices(Circle, Diamond)               # removes all vertices tagged as Circle OR Diamond
graph.remove_vertices(Yargi::ALL & Circle & Diamond) # remove vertices that are both Circle and Diamond

Defined Under Namespace

Classes: Edge, Vertex

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Markable

#add_marks, #get_mark, #has_mark?, #set_mark, #tag, #to_h

Constructor Details

#initialize {|_self| ... } ⇒ Digraph

Creates an empty graph instance

Yields:

  • (_self)

Yield Parameters:



26
27
28
29
30
31
 
# File 'lib/yargi/digraph.rb', line 26

def initialize
  @vertices = VertexSet[]
  @edges = EdgeSet[]
  @marks = {}
  yield(self) if block_given?
end

Class Method Details

.random(vertex_count = nil, edge_count = nil, strip = nil) {|r| ... } ⇒ Digraph

Generates a random graph.

Example:

# Generate a random graph with 20 vertices
# and 60 edges exactly (no stripping)
Digraph.random(20,60,false)

# Even more powerful, r is a Digraph::Random
Digraph.random do |r|
  r.vertex_count = 20
  r.edge_count = 60
  r.strip = false
  r.vertex_builder = lambda{|v,i| ... } # as digraph.add_n_vertices
  r.edge_builder   = lambda{|e,i| ... } # similarl
end

Parameters:

  • vertex_count (Integer) (defaults to: nil) —

    number of vertices to generate

  • edge_count (Integer) (defaults to: nil) —

    number of edges to generate

  • strip (Integer) (defaults to: nil) —

    strip the graph (reachability for first vertex)

Yields:

  • (r)

Returns:

  • (Digraph) —

    a directed graph randomly generated



86
87
88
89
90
91
92
93
94
 
# File 'lib/yargi/random.rb', line 86

def self.random(vertex_count = nil, edge_count = nil, strip = nil)
  r = Random.new{|rand|
    rand.vertex_count = vertex_count if vertex_count
    rand.edge_count = edge_count if edge_count
    rand.strip = strip if strip
  }
  yield(r) if block_given?
  r.execute
end

Instance Method Details

#add_edge(source, target, *args) ⇒ Object Also known as: connect

Connects source to target state(s). source and target may be any selection expression that can lead to vertex sets. args can be module instances or hashes, which are all installed on edges e using e.tag and e.add_marks, respectively.



133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
 
# File 'lib/yargi/digraph.rb', line 133

def add_edge(source, target, *args)
  if Vertex===source and Vertex===target
    edge = Digraph::Edge.new(self, @edges.length, source, target)
    apply_arg_conventions(edge, args)
    source.add_out_edge(edge)
    target.add_in_edge(edge)
    @edges << edge
    edge
  else
    sources, targets = to_vertices(source), to_vertices(target)
    created = EdgeSet[]
    sources.each do |src|
      targets.each do |trg|
        created << add_edge(src, trg, *args)
      end
    end
    created
  end
end

#add_edges(*extremities) ⇒ Object Also known as: connect_all

Adds many edges at once



155
156
157
158
159
 
# File 'lib/yargi/digraph.rb', line 155

def add_edges(*extremities)
  extremities.collect do |extr|
    add_edge(extr[0], extr[1], *extr[2..-1])
  end
end

#add_n_vertices(n, *args) ⇒ Object

Creates n vertices. args can be module instances or hashes, which are all installed on vertices v using v.tag and v.add_marks, respectively. If a block is given, it is called after each vertex creation. The vertex is passed as first argument and the iteration index (from 0 to n-1) as second one.



77
78
79
80
81
82
83
84
85
 
# File 'lib/yargi/digraph.rb', line 77

def add_n_vertices(n, *args)
  vertices = []
  n.times do |i|
    vertex = add_vertex(*args)
    vertices << vertex
    yield vertex, i if block_given?
  end
  VertexSet.new(vertices)
end

#add_vertex(*args) ⇒ Object

Adds a vertex. args can be module instances or hashes, which are all installed on the vertex v using v.tag and v.add_marks, respectively.



64
65
66
67
68
69
 
# File 'lib/yargi/digraph.rb', line 64

def add_vertex(*args)
  vertex = Digraph::Vertex.new(self, @vertices.length)
  apply_arg_conventions(vertex, args)
  @vertices << vertex
  vertex
end

#each_edge(filter = nil, &block) ⇒ Object

Calls block on each graph edge for with the ‘filter and block’ predicate evaluates to true.



121
122
123
124
125
126
127
 
# File 'lib/yargi/digraph.rb', line 121

def each_edge(filter=nil, &block)
  if filter.nil?
    @edges.each &block
  else
    edges(filter).each &block
  end
end

#each_vertex(filter = nil, &block) ⇒ Object

Calls block on each graph vertex for with the ‘filter and block’ predicate evaluates to true.



53
54
55
56
57
58
59
 
# File 'lib/yargi/digraph.rb', line 53

def each_vertex(filter=nil, &block)
  if filter.nil?
    @vertices.each &block
  else
    vertices(filter).each &block
  end
end

#edge_count ⇒ Object

Returns number of graph edges



104
105
106
 
# File 'lib/yargi/digraph.rb', line 104

def edge_count
  @edges.size
end

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

Returns all graph edges for which the ‘filter and block’ predicate evaluates to true (see Yargi::Predicate).



115
116
117
 
# File 'lib/yargi/digraph.rb', line 115

def edges(filter=nil, &block)
  @edges.filter(filter, &block)
end

#ith_edge(i) ⇒ Object

Returns the i-th edge



109
110
111
 
# File 'lib/yargi/digraph.rb', line 109

def ith_edge(i)
  @edges[i]
end

#ith_vertex(i) ⇒ Object

Returns the i-th vertex



41
42
43
 
# File 'lib/yargi/digraph.rb', line 41

def ith_vertex(i)
  @vertices[i]
end

#reconnect(edges, source, target) ⇒ Object

Reconnects some edge(s). source and target are expected to be Vertex instances, or nil. edges may be any selection expression that can be converted to an edge set. This method reconnects all edges to the specified source and target vertices (at least one is expected not to be nil).

Raises:

  • (ArgumentError) 


182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
 
# File 'lib/yargi/digraph.rb', line 182

def reconnect(edges, source, target)
  raise ArgumentError, "Vertices expected as source and target"\
    unless (source.nil? or Vertex===source) and (target.nil? or Vertex===target)
  to_edges(edges).each do |edge|
    if source
      edge.source.remove_out_edge(edge)
      source.add_out_edge(edge)
    end
    if target
      edge.target.remove_in_edge(edge)
      target.add_in_edge(edge)
    end
    edge.reconnect(source, target)
    edge
  end
end

#remove_edges(*edges) ⇒ Object Also known as: remove_edge

Removes all edges returned by evaluating the edges selection expression.



164
165
166
167
168
169
170
171
172
173
174
 
# File 'lib/yargi/digraph.rb', line 164

def remove_edges(*edges)
  edges = to_edges(edges).sort{|e1,e2| e2<=>e1}
  edges.each do |edge|
    edge.source.remove_out_edge(edge)
    edge.target.remove_in_edge(edge)
    @edges.delete_at(edge.index)
    edge.index = -1
  end
  @edges.each_with_index {|edge,i| edge.index=i}
  self
end

#remove_vertices(*vertices) ⇒ Object Also known as: remove_vertex

Removes all vertices returned by evaluating the vertices selection expression.



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

def remove_vertices(*vertices)
  vertices = to_vertices(*vertices).sort{|v1,v2| v2<=>v1}
  vertices.each do |vertex|
    remove_edges(vertex.in_edges+vertex.out_edges)
    @vertices.delete_at(vertex.index)
    vertex.index=-1
  end
  @vertices.each_with_index {|v,i| v.index=i}
  self
end

#to_dot(buffer = '') ⇒ Object

Encodes this graph for dot graphviz



202
203
204
205
206
207
208
209
210
211
212
 
# File 'lib/yargi/digraph.rb', line 202

def to_dot(buffer='')
  buffer << "digraph G {\n"
  buffer << "  graph[#{to_dot_attributes(self.to_h(true))}]\n"
  each_vertex do |v|
    buffer << "  V#{v.index} [#{to_dot_attributes(v.to_h(true))}]\n"
  end
  each_edge do |e|
    buffer << "  V#{e.source.index} -> V#{e.target.index} [#{to_dot_attributes(e.to_h(true))}]\n"
  end
  buffer << "}\n"
end

#vertex_count ⇒ Object

Returns number of graph vertices



36
37
38
 
# File 'lib/yargi/digraph.rb', line 36

def vertex_count
  @vertices.size
end

#vertices(filter = nil, &block) ⇒ Object

Returns all graph vertices for which the ‘filter and block’ predicate evaluates to true (see Yargi::Predicate).



47
48
49
 
# File 'lib/yargi/digraph.rb', line 47

def vertices(filter=nil, &block)
  @vertices.filter(filter, &block)
end