Skip to main content

Construct adjacency list by using adjacency matrix in ruby

Ruby program for Construct adjacency list by using adjacency matrix. Here more information.

#    Ruby program for
#    Construct adjacency list using adjacency matrix
class Graph 
	# Define the accessor and reader of class Graph
	attr_reader :vertices, :adgeList
	attr_accessor :vertices, :adgeList
	def initialize(matrix) 
		#  Set number of nodes
		self.vertices = matrix.length
		self.adgeList = []
		i = 0
		#  Create memory of adgeList of each vertice
		while (i < self.vertices) 
			self.adgeList.push([])
			i += 1
		end

		self.makeAdjacencyList(matrix)
	end

	#  Convert into adjacency list
	def makeAdjacencyList(matrix) 
		i = 0
		while (i < self.vertices) 
			j = 0
			while (j < self.vertices) 
				if (matrix[i][j] == 1) 
					self.addEdge(i, j)
				end

				j += 1
			end

			i += 1
		end

	end

	def addEdge(u, v) 
		if (u < 0 || u >= self.vertices || 
            v < 0 || v >= self.vertices) 
			return
		end

		#  Add node edge
		self.adgeList[u].push(v)
	end

	#  Display graph nodes and edges
	def printGraph() 
		print("\n Graph Adjacency List ")
		i = 0
		while (i < self.vertices) 
			print(" \n [", i ,"] :")
			j = 0
			#  iterate edges of i node
			while (j < self.adgeList[i].length) 
				if (j != 0) 
					print(" → ")
				end

				print(" ", self.adgeList[i][j])
				j += 1
			end

			i += 1
		end

	end

end

def main() 
	matrix = [
		[0, 1, 1, 0, 1],
		[1, 0, 1, 0, 1],
		[1, 1, 0, 1, 0],
		[0, 1, 0, 0, 1],
		[1, 1, 0, 1, 0]
	]
	g = Graph.new(matrix)
	#  Display graph element
	g.printGraph()
end

main()

Output

 Graph Adjacency List  
 [0] : 1 →  2 →  4 
 [1] : 0 →  2 →  4 
 [2] : 0 →  1 →  3 
 [3] : 1 →  4 
 [4] : 0 →  1 →  3




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment