Module: GraphUtils

Defined in:
lib/GraphUtils.rb

Defined Under Namespace

Classes: BipartiteGraph, DirectedEdge

Class Method Summary collapse

Class Method Details

.find_paths(startVertex, edges) ⇒ Object

Performs a breadth-first traversal of the graph given by the list of edges starting at startVertex. Returned is the list of edges that were traversed.



228
229
230
231
232
233
234
235
236
237
238
239
240
 
# File 'lib/GraphUtils.rb', line 228

def find_paths(startVertex, edges)
    arcs = Set.new
    edgeQueue = edges.find_all { |edge| edge.startVertex == startVertex }.to_set
    while not edgeQueue.empty?
	currentEdge = edgeQueue.find { |i| true }
	edgeQueue.delete(currentEdge)
	arcs.add(currentEdge)
	nextEdges = edges.find_all { |edge| edge.startVertex == currentEdge.endVertex }
	edgeQueue.merge(nextEdges.delete_if { |edge| arcs.include?(edge) })
    end

    return arcs.to_a
end

.strongly_connected_components(nodes, edges) ⇒ Object

Computes the strongly connected components in a graph given by its edges. The first argument is a set of nodes in the graph, the second argument is a list of directed edges. Returned is an array of strongly connected components, each one an array of nodes in the component. Algorithm due Robert Tarjan (1972).



248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
 
# File 'lib/GraphUtils.rb', line 248

def strongly_connected_components(nodes, edges)
    edge_cache = Hash.new
    nodes.each { |node|
	edge_cache[node] = Array.new
    }
    edges.each { |edge|
	edge_cache[edge.startVertex] << edge
    }
    retval = Array.new
    nodeQueue = nodes.dup
    while not nodeQueue.empty?
	retval += tarjan(nodeQueue.find { |i| true }, nodeQueue, edge_cache, [], 0, {}, {})
    end

    return retval
end