A Disagreement Over Data Structures: Part 5 of Ann's Visit to the City of G'Raph

Graphs can be represented by a variety of data structures. Two common representations are: adjacency matrices and adjacency lists. Both data structures can handle directed, undirected, weighted, or unweighted edges. An adjacency matrix represents a graph as a matrix -- with one row and one column for each node. The matrix value of row i, column j is the weight of the edge from node i to node j (or 0/1 for unweighted graphs). An adjacency list maintains a separate list of neighbors for each node.

Ann had obviously touched upon a controversial question. Florence and Edgar stood on opposite sides of the room glaring at each other. The question had seemed innocent enough. "Do you always represent graphs with these illustrations?" Ann had asked.

Florence had quickly answered. "No. Those are only for illustration. Adjacency matrices work better."

And Edgar had snapped. "No. The correct answer is that adjacency lists are the preferred tools."

Then the glaring had begun.

"What are adjacency matrices and adjacency lists?" asked Ann, starting with the most basic question. Both scholars immediately rushed to explain their data structures. The resulting sound reminded Ann of two chipmunks fighting.

"One at a time, please." Ann pleaded. "Florence, why don't you start with adjacency matrices?"

Florence smiled. "They are very simple. Every row represents a node and every column represents a node. If there is an edge between two nodes, you put their weight in the corresponding element. So M[i][j] would store the weight of the edge from node i to node j. Here is an example of some of the islands of G'Raph."

"Adjacency matrices are wonderful." continued Florence. "See how it puts all of the information into a single convenient form. They are very simple representations. And you can perform a bunch of computations by just multiplying the matrices."

Ann nodded. It seemed sensible enough.

"Why aren't there ones along the diagonal? Obviously you can get from the library to the library." asked Ann.

"Depending on what you are trying to represent, self edges (or loops) can certainly make sense. In this case, I am only representing the existence of bridges. And there is no bridge from the library to the library." explained Florence.

"Okay. Now Edgar, can you tell me about adjacency lists?" asked Ann, turning to the other scholar.

"Certainly." started Edgar. "You start with a list of each node in the graph. Imagine a giant array or linked list with the name of each node in it. Then for each of those nodes, you keep a list of all the nodes to which it connects. For graphs with a few edges, it can use a lot less memory. You only store the edges that are there Here is an example."

Ann studied the example. "Both forms can represent the same graph exactly, correct?" asked Ann. Both scholars nodded,

"And both forms can do directed graphs as well?" asked Ann. Both scholars nodded.

"And they can both represent weighted edges?" asked Ann. Both scholars nodded.

"Then why are you fighting? It seems like they both do the same thing, but have different advantages. A matrix is simpler to specify, and a list can take less space. Is that really worth fighting over?" asked Ann. Both scholars nodded.

"Space matters!" cried Edgar. "Have you ever tried using your precious matrices to represent the entire pigeon network, Florence? There are thousands and thousands of nodes!"

"Simplicity matters too!" answered Florence "I can traverse my matrices with two fixed size FOR loops. You need to iterate over lists of different size. I have seen your implementations… they have POINTERS!"

"Better to have pointers than a row with ten thousand useless zeros!" responded Edgar.

The argument was getting heated. Ann backed away from the two scholars. She was afraid that one of them would eventually throw a coffee mug.

Then Ann heard a low sigh from the corner of the room. Turning away from the argument, Ann peaked around a very large stack of books. There, at a tiny desk in the corner, was the most depressed looking person that she had ever seen. He hunched over his desk, staring at a single sheet of paper on his desk and shaking his head.

"Hello?" Ann asked.

The man looked up at her blankly. "Both data structures are completely reasonable in their own way." he explained without bothering to introduce himself.

"I can see that." Ann confirmed. "I think they both have advantages and disadvantages."

The man just nodded. "I wish they would see that. They make such a terrible racket when they argue. I have important work to do, you know."

"I see. Can I ask what you are working on?" asked Ann.

"It is not done." he answered. "I have not figured it out yet."

"Oh. What is the problem, then?" Ann probed.

The man did not answer for a while. Behind her, Ann could hear Florence shouting something about invertability. Ann tried to ignore the argument.

Finally, the man gave Ann a sad look. "It is a really simple problem. I do not know why I have not been able to come up with a good solution. It really is quite simple. I just want an algorithm that will give me the shortest path through a graph such that the path visits each node exactly once."

Ann thought about this for a second. "Sounds like a good problem." she offered.

The man nodded. "I have been working at it for a while without any success. It all started a long time ago, when a man in a dark cloak first told me about the problem. I think he might have been a traveling salesman. I never did see his face though. He just told me that he had a problem that he needed the best scholar in G'Raph to solve. I was young and naive. I told him that I would have an efficient algorithm by the end of the week… that was twenty-five years ago."

To be continued in Part 6: The Traveling Salesman's Problem...

Follow Ann's visit to G'Raph from the beginning with Part 1: The City of G'Raph.

-------

To learn more about matrices see Users, Peanut Vendors, and Matrix Indices.

To learn more about linked lists and arrays see Arrays, Linked Lists, and Zed's Coffee Shop or Linked Lists, Kindergarten and Ocean Voyages.