Directed Graphs, Bridges, and the Mayor’s Office: Part 2 of Ann's Visit to G'Raph

The edges in a graph can either be directed or undirected. Directed edges indicate one way relationships, such as: There is a link from Node A to Node B. Undirected edges indicate bidirectional relationships, such as: Node A and Node B are linked. The distinction between undirected and directed edges is important to both the structure of the graph and how algorithms operate on the graph.

As Ann waited in the mayor's office, she studied the map of G'Raph that hung on the wall. The map itself was huge, taking up the entire south wall of the room. There was at least a thousand dirt islands, represented as tiny circles, and several thousand bridges, represented as lines. Each bridge was clearly labeled with some number, which Ann assumed was the distance between islands. At seeing the full extent of the city mapped out, Ann again wondered why anyone would build a city in such an inhospitable swamp.

"Ann!" greeted the mayor in a loud voice. "You have grown so much since I last saw you. It must have been at least ten years. How have you been?"

"I have been splendid. Thank you for asking. And yourself?" responded Ann. She had absolutely no recollection of ever meeting the mayor. Then again, given how young she was ten years ago, this was not a surprise.

Still, Ann was convinced that she should remember this particular man. His bushy gray muttonchops alone would be impossible to forget. They easily covered half of his face.

"I am wonderful," answered the mayor. "Life in G'Raph is most wonderful. How are you finding our humble town so far?"

"I have met the most charming and helpful people. However, I do have to admit that your islands pose a bit of a navigational challenge," answered Ann honestly.

The mayor laughed. He turned to look at the map on the wall. "Yes. That is a common feeling. Luckily, our best scholars have developed some wonderful algorithms. Once a person masters those, life becomes a lot easier."

"I suppose," replied Ann. She was thoroughly unconvinced.

"You know... It was not always this simple either," continued the mayor in a hushed tone. "My predecessor made such a wonderful mess of our bridge system. He actually made each bridge one way."

"Really?" Ann gasped. She could see that it would take a long time to navigate around the city using the bidirectional bridges. The thought of making all the paths one way was absurd.

"Yes," answered the mayor. "He thought it would streamline movement. Admittedly, it did make the traffic flow better over each bridge. But it also meant that you had to account for the direction of every bridge when planning your path. Worse though, since each bridge only went one direction, some paths became much too long. He even started building second bridges between some high traffic islands -- one bridge from here to there and another from there to here. Perhaps you wondered why there are two parallel bridges between the south market and the top hat shoppe?"

"I did not come that way, so I did not have an opportunity to wonder," Ann explained.

"Well, that is why. Before the second bridge, people had to take nine bridges to get to from south market to the top hat shoppe. It was horrendous!"

"The second bridge helped?" asked Ann.

"It did. However, building extra bridges is just too cumbersome. Unlike adding edges on this map, building a bridge takes real effort. Adding new edges in the physical world is not as simple as drawing a new line. Eventually, we returned to using two way bridges again."

Ann nodded in agreement. From what she had seen, each bridge probably took days to build. She could not imagine it being worth doubling that effort.

Finally, Ann decided to get to the real purpose of her visit. "Sir. My father has always spoken highly of the theorists of G'Raph. I am sure that you are aware of my question and the vaguely defined danger that the kingdom faces. Would it be possible for me to stay here and learn from your scholars?"

The mayor's face lit up in a wide smile. "Of course!" he proclaimed. "You are welcome to stay as long as you want. I assure you that you shall find our scholar's work most enlightening. I shall take you to the G'Raph library first thing tomorrow."

After thanking the mayor, Ann began her trek back to the inn. As she crossed the bridge from the dry cleaner to the inn, she was grateful that the bridge was undirected. She was too tired to find her way around G'Raph through an entirely different set of bridges.

To be continued in Bridge Weights: Part 3 of Ann's Visit to G'Raph...

--------------

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