The City of G’Raph: Part 1 in Ann’s Visit to G’Raph

A graph is defined by a set of nodes and edges. The edges define a relationship between two nodes, linking those nodes. In unweighted graphs edges are binary -- there is either an edge between two nodes or there is not. In weighted graphs, the edges have real-valued weights indicating the relationship or proximity between two nodes. Graphs can be used to represent a large number of real world systems, including: social networks, computer networks, and transportation systems.

Ann arrived at the city of G'Raph shortly before nightfall. Any hope she had vanished as as she surveyed the city. It looked more like a massive swamp than a proper city. Tiny dirt islands dotted the landscape, poking out of the mud like warts. On each dirt island stood a small structure -- usually a house or business. The islands were connected by what appeared to be an inconceivably large number of rope bridges.

Despite the large sign stating "Welcome to G'Raph: Land of the Bridges", Ann was certain that she was in the wrong place. This could not be the same G'Raph of which her father had spoken so highly. To hear him tell it, some of the best minds in the world had built G'Raph into an intellectual powerhouse. Could she really find any answers here?

Ann took a deep breath, immediately regretting that decision as the swamp air filled her lungs. She coughed a few times, shook her head in dismay, and walked toward the city. Her first stop was G'Raph city hall. Hopefully, the mayor could introduce her to someone to help with her quest.

Unfortunately, Ann quickly discovered that she could not simply walk toward city hall. It almost seemed as though the town was designed to be confusing. Each little dirt island had a only few bridges connecting it to neighbors. This arrangement required her to stop and think about the path that she was taking instead of just the direction that she was going.

Finally, after crossing thirty bridges, Ann stopped at a small farm to ask directions. The farmer, who had been harvesting his radish crop from the swamp mud, seemed eager to help.

"Excuse me, sir. Can you point me in the direction of city hall?" asked Ann.

"The direction? I guess it is that way. But you need to take that bridge over there." The farmer’s arms extended in different directions.

"Are you sure?" asked Ann. In her experience, the fastest way to city hall was to walk toward it.

"You're not from around here, are you?" asked the farmer.

Ann shook her head.

"It's the bridges," explained the farmer. "In order to get anywhere in G'Raph, you have to understand how the different islands are connected. Each bridge forms a link between two island nodes. So in order to get from node A to node B, you need to take the correct sequence of bridges."

"I go that way?" Ann asked tentatively.

"You need to go: from here to McFane's farm, to the brewery, to the inn, to the 24 hour dry cleaners, and then to city hall. That is 5 bridges." The farmer counted the steps on his fingers.

Ann stared back at him.

"Let me write it down for you," the farmer offered. He pulled out a scrap of paper and sketched a small map:

North West corner of G'Raph (not to scale)

"There you go," he said, offering the paper to Ann. "Each line is a bridge. Just follow the bridges from island to island, and you will be fine."

"Thank you," Ann said. Her head spun wildly. How did anyone find their way around here?

Little did Ann know, the very structure of G'Raph had pushed it's population to become a city of algorithmic thinkers. It was here in the city of G’Raph that Ann would find the first real clue to her quest.

To be continued in Directed Graphs, Bridges, and the Mayor’s Office...