This course will introduce you to Ruby, as well as teach you about classes, methods, variables, data structures, loops, enumerable methods, and finishing touches.
Experts Exchange Solution brought to you by
"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.
Experts Exchange Solution brought to you by
Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.
Start your 7-day free trialFrom novice to tech pro — start learning today.
Experts Exchange Solution brought to you by
(1) What text book? (Just curious)
(2) I can give you the typical descriptions of what an adjacency matrix and an adjacency list are. I tend to represent graphs using two classes, node and edge, where each edge has pointers at two nodes and each node has two lists of edges (in arc and out arcs); your choice among the various representations depends on what you want to do.
Adjacency matrix: Square matrix with one row (and one column) for each node in the graph. The entry at [i][j] in the matrix is 0 if there is no edge between node[i] and node[j], 1 if there is such an edge.
Adjacency list: Since the size of an adjaceny matrix is quadratic in the number of nodes (O(n^2) where n is the number of edges), if the graph is not densely connected, keeping an array of nodes, each with a list of the nodes they are adjacent to, can be more space efficient. Each edge is represented in two lists (so if there is an edge from node[i] to node[j], the edge is represented by a "j" appearing in list[i] and a "i" appearing in list[j]).
(3) Printing out:
Adjacency matrix is easy to print, fairly compact, and you can do it with a pair of for loops that move the indices over the whole square.
Adjaceny lists can be harder to print (one count-controlled loop, one loop to traverse a list) because you typically need separators between successive entries in any one list (so you can tell the difference between node 1 and node 2 appearing in the list and node 12 appearing in the list).
(4) Code structure
Regardless of structure you should think about the interface of a graph object. You need constructor/destructor. you need to be able to add a node (with whatever information a node requires) and you need to be able to add an edge (this requires being able to specify two nodes already in the graph). Then printing the graph rounds out the basic set of functions you need in the interface.
To handle insertion of edges you probably need to be able to find a node by "name" (some sort of node identifier) but that is a private function.
The actual data members of the graph class depend on the graph representation you select.
Hope this helps, -bcl