- Grasping Graph Theory
- Old and Famous Problems
- Graphs, Computers, and Popular Culture
- Constructing a Simple Graph with Boost
- Adding Values to Vertices and Edges
- Manipulating Property Values
- Adding Vertices and Edges
- Iterating Through the Edges and Vertices
- Solving Problems with Graphs and Boost
Graphs, Computers, and Popular Culture
Graphs show up all over the place in the world of computers. The Web itself is one massive graph, with each page being a vertex, and each link to another page an edge. Another place you see a graph concept is in social sites such as MySpace. In that sense, each profile is a vertex, and each friendship connection is an edge. That is, profiles are linked to other profiles via friend connections, just as vertices are linked to other vertices via edges.
In fact, the friendship link concept is used in a game people play, often called "Six Degrees of Kevin Bacon." The idea is that every Hollywood movie star is linked to Kevin Bacon by at most six links, and your job is to find the links. For example, take Jamie Foxx, who is two degrees from Kevin Bacon. One link goes like this: Jamie Foxx was in Booty Call with David Hemblen, who was in Where the Truth Lies with Kevin Bacon. (How did I know? I checked it out at The Oracle of Bacon.)
One popular social networking site, Facebook, uses graph theory to tell how members are connected to other members. If you’re signed in, you visit a member’s page, and that member is only a couple of links away, Facebook shows the connection. It says that person A is on your friend list, who has person B on his or her friend list, who in turn is friends with the person whose profile you’re looking at. The FAQ even mentions using graph theory algorithms to make those connections visible.