Who Knows Whom? When Anything Can Connect: Graphs

Find a person's friends in one step, in a network where anyone can know anyone and friendships loop back around: why a list of pairs and a tree both fall short, and the structure that fits, the graph, with one-way and two-way connections and weights.

Journeyman · Data Structures · Updated

By

After this lesson you can

  • Describe a graph as vertices joined by edges, using an everyday network such as friends or roads
  • Tell one-way edges from two-way edges, and say when an edge needs a weight
  • Choose a list, a tree or a graph for data, from how its items connect

Key takeaways

  • Friendships kept as a list of pairs make every "who are Dev's friends?" read every pair, O(E); a tree can't hold them, because a person has many friends and friendships loop back around.
  • A graph is a set of things, called vertices, joined by connections, called edges.
  • A two-way edge works in both directions, like a friendship; a one-way edge goes one way only, like following someone.
  • A weight is a number on an edge, such as the miles of a road, for when connections aren't all equal.
  • A dictionary that maps each vertex to the list of its neighbors finds anyone's neighbors in O(k), where k is how many they have.

Before this: Who Works Under Whom? Trees gave every person one manager and no loops. Friends don't work that way.

You're building the "people you may know" box for a small social app. Its first question, for every box it draws, is "who are Dev's friends?" Here is what the app has: every time someone taps Add friend, it writes the pair down. Eight people have made seven friendships so far:

Friendship Friendship
Ava and Ben Dev and Eli
Ava and Cara Eli and Fay
Ben and Dev Gus and Hana
Cara and Dev

Map apps ask the same kind of question ("which roads leave this town?"), and so do course catalogs ("what does this course unlock?") and the web ("which pages does this one link to?"). By the end of this lesson you'll have the structure all of them use, the graph. First, Dev's friends.

What would you try?

Read the list of pairs. To find Dev's friends, read every pair and keep the ones with Dev in them: Ben, Cara, Eli. With 7 pairs, that's nothing. But a real app with 1,000,000 people and about 200 friends each has 100 million pairs, and every "who are Dev's friends?" reads all 100 million to find his 200. That's O(E), where E is the number of friendships, for every box on every screen.

Use a tree, like the org chart. A tree gives each person a place under one parent, and walking down from the top finds everyone. So put Ava at the top, Ben and Cara under her, and Dev under... which one? Dev is friends with both Ben and Cara. A tree gives Dev one parent, so one of those friendships has nowhere to go. And Ava, Ben, Dev and Cara make a loop: follow the friendships from Ava and you come back to Ava. A tree promises there are no loops.

Give each person a page with their friends on it. Like an address book: Dev's page lists Ben, Cara and Eli. "Who are Dev's friends?" turns straight to Dev's page and reads 3 names, or Dev's 200 in the real app, never the other 100 million pairs. A new friendship is one note on each person's page.

What we tried Who are Dev's friends? Where it breaks
A list of pairs O(E): read all 100 million every lookup, at real size
A tree can't be stored Dev has two "parents", and Ava–Ben–Dev–Cara loops
A page per person O(k): read Dev's own page nowhere so far

The questions that lead to it

What does a tree assume about every node? One parent, and no way to walk in a circle back to where you started. Is that true of friends? No: anyone can know anyone, and friends of friends are often friends.

So what's left, once "one parent" and "no loops" are gone? Only things, and the connections between them. A connection can join any two things, and nothing says how many a thing can have.

Does following a singer mean the singer follows you? No, so some connections go one way. Is every road the same? No: one is 2 miles and another is 40, so some connections carry a number.

How it got its name

This shape turned out to be everywhere, so it got a name: a graph. (Not the kind with bars and axes: the word comes from the diagrams mathematicians drew of dots and lines.)

  • The things are vertices (one is a vertex, read "VER-tex"); some books call them nodes.
  • The connections are edges: a friendship, a road, a link.
  • Two vertices joined by an edge are neighbors.

A graph doesn't care where things sit on the page, only what's connected to what. It doesn't need to be all one piece either: Gus and Hana know each other and nobody else, so they're a graph of their own, sitting beside the rest.

Eight people in a small social network drawn as circles with their names, Ava, Ben, Cara, Dev, Eli, Fay, Gus and Hana, joined by seven lines, one for each friendship: Ava with Ben and with Cara, Ben and Cara each with Dev, Dev with Eli, Eli with Fay, and Gus with Hana off to one side, not connected to the others

One way or two ways. A friendship goes both ways: if Ava is Ben's friend, Ben is Ava's. That's a two-way edge, and a graph made of them is an undirected graph. Following goes one way: Ava can follow a singer who has never heard of her. That's a one-way edge, drawn as an arrow, and a graph made of them is a directed graph. One-way streets, "this course must come before that one" and "this page links to that page" are one-way edges too.

Edges with a weight. On a social app every friendship counts the same. On a road map they don't. A number on an edge is its weight, and a graph with them is a weighted graph. The weight is whatever you add up along a route: miles, minutes, dollars of airfare. Ask "does this connection cost something, and does that cost differ from edge to edge?" If yes, the edges need weights. Without weights, every edge counts as one step.

Three small everyday graphs side by side: towns joined by roads with the miles written on each road, as a weighted graph; friends joined by plain lines that work both ways, as an undirected graph; and a follower pointing one-way arrows at the people they follow, as a directed graph

A social network in code

The page per person is a dictionary: each person is a key, and their value is the list of their friends. The code reads the app's list of pairs once, and writes each friendship in both people's lists, because it goes both ways.

(string, string)[] friendships = { ("Ava", "Ben"), ("Ava", "Cara"), ("Ben", "Dev"), ("Cara", "Dev"), ("Dev", "Eli"), ("Eli", "Fay"), ("Gus", "Hana") };
Dictionary<string, List<string>> network = new Dictionary<string, List<string>>();

void AddFriend(string person, string friend)
{
    if (!network.ContainsKey(person))
    {
        network[person] = new List<string>();
    }
    network[person].Add(friend);
}

foreach ((string first, string second) in friendships)
{
    AddFriend(first, second);
    AddFriend(second, first);
}

Console.WriteLine("People: " + network.Count + ", friendships: " + friendships.Length);
foreach (KeyValuePair<string, List<string>> entry in network)
{
    Console.WriteLine(entry.Key + ": " + string.Join(", ", entry.Value));
}
People: 8, friendships: 7
Ava: Ben, Cara
Ben: Ava, Dev
Cara: Ava, Dev
Dev: Ben, Cara, Eli
Eli: Dev, Fay
Fay: Eli
Gus: Hana
Hana: Gus
String[][] friendships = {{"Ava", "Ben"}, {"Ava", "Cara"}, {"Ben", "Dev"}, {"Cara", "Dev"}, {"Dev", "Eli"}, {"Eli", "Fay"}, {"Gus", "Hana"}};
Map<String, List<String>> network = new LinkedHashMap<>();

void addFriend(String person, String friend) {
    if (!network.containsKey(person)) {
        network.put(person, new ArrayList<>());
    }
    network.get(person).add(friend);
}

void main() {
    for (String[] pair : friendships) {
        addFriend(pair[0], pair[1]);
        addFriend(pair[1], pair[0]);
    }
    IO.println("People: " + network.size() + ", friendships: " + friendships.length);
    for (Map.Entry<String, List<String>> entry : network.entrySet()) {
        IO.println(entry.getKey() + ": " + String.join(", ", entry.getValue()));
    }
}
People: 8, friendships: 7
Ava: Ben, Cara
Ben: Ava, Dev
Cara: Ava, Dev
Dev: Ben, Cara, Eli
Eli: Dev, Fay
Fay: Eli
Gus: Hana
Hana: Gus
friendships = [("Ava", "Ben"), ("Ava", "Cara"), ("Ben", "Dev"), ("Cara", "Dev"), ("Dev", "Eli"), ("Eli", "Fay"), ("Gus", "Hana")]
network = {}


def add_friend(person, friend):
    if person not in network:
        network[person] = []
    network[person].append(friend)


for first, second in friendships:
    add_friend(first, second)
    add_friend(second, first)

print(f"People: {len(network)}, friendships: {len(friendships)}")
for person, friends in network.items():
    print(f"{person}: {', '.join(friends)}")
People: 8, friendships: 7
Ava: Ben, Cara
Ben: Ava, Dev
Cara: Ava, Dev
Dev: Ben, Cara, Eli
Eli: Dev, Fay
Fay: Eli
Gus: Hana
Hana: Gus
const friendships = [["Ava", "Ben"], ["Ava", "Cara"], ["Ben", "Dev"], ["Cara", "Dev"], ["Dev", "Eli"], ["Eli", "Fay"], ["Gus", "Hana"]];
const network = new Map();

function addFriend(person, friend) {
  const friends = network.get(person) ?? [];
  friends.push(friend);
  network.set(person, friends);
}

for (const [first, second] of friendships) {
  addFriend(first, second);
  addFriend(second, first);
}

console.log(`People: ${network.size}, friendships: ${friendships.length}`);
for (const [person, friends] of network) {
  console.log(`${person}: ${friends.join(", ")}`);
}
People: 8, friendships: 7
Ava: Ben, Cara
Ben: Ava, Dev
Cara: Ava, Dev
Dev: Ben, Cara, Eli
Eli: Dev, Fay
Fay: Eli
Gus: Hana
Hana: Gus
const friendships: [string, string][] = [["Ava", "Ben"], ["Ava", "Cara"], ["Ben", "Dev"], ["Cara", "Dev"], ["Dev", "Eli"], ["Eli", "Fay"], ["Gus", "Hana"]];
const network = new Map<string, string[]>();

function addFriend(person: string, friend: string): void {
  const friends = network.get(person) ?? [];
  friends.push(friend);
  network.set(person, friends);
}

for (const [first, second] of friendships) {
  addFriend(first, second);
  addFriend(second, first);
}

console.log(`People: ${network.size}, friendships: ${friendships.length}`);
for (const [person, friends] of network) {
  console.log(`${person}: ${friends.join(", ")}`);
}
People: 8, friendships: 7
Ava: Ben, Cara
Ben: Ava, Dev
Cara: Ava, Dev
Dev: Ben, Cara, Eli
Eli: Dev, Fay
Fay: Eli
Gus: Hana
Hana: Gus

Java's HashMap doesn't promise to keep keys in the order they were added, so the Java tab uses a LinkedHashMap, which does. Python's dict, JavaScript's Map and C#'s Dictionary (as long as nothing is removed) list them in the order they were added.

Seven friendships, but fourteen names in the lists: every two-way edge is written twice, once from each end. Dev's line is the answer the app wanted, read from his own page. Dev has three friends, the most of anyone; in textbooks, the number of edges touching a vertex is its degree, so Dev's degree is 3.

Try it. Make the network one-way, a "who follows whom" graph: delete the line that adds second, first, and run it again. Now Ben's list holds only Dev, and Fay and Hana have no list at all, because no edge starts at them.

When a tree or a list is enough

A graph can hold anything a tree can, but a tree is simpler when its promise is true. An org chart (one manager each) and folders on a disk (one parent folder each) never loop, so a tree's walks need no "have I been here?" notes. And a plain list of pairs is fine for a job that reads every pair once, such as exporting all the friendships to a file. What tips it to a graph is the question asked most: "who is connected to this one?", over and over, when anything can connect to anything.

Cost card

The dictionary of lists is called an adjacency list, and the next lesson, Are These Two Friends? Adjacency Lists and Grids, compares it with a second way. Here's what it costs, where k is how many friends the person has:

What you do Big-O The everyday reason
Add a person O(1) A new, empty page in the address book
Add a friendship O(1) One quick note on each person's page
List someone's friends O(k) Turn straight to their page, then read it
Check whether two people are friends O(k) Read down one person's page, looking for the other name

Check yourself

2 questions to try on the lesson page.

So what

Roads, friendships, follows, prerequisites and links are all vertices and edges, so one set of tools works on every one of them. When your data has things that can connect to any number of other things, and the connections can loop, it's a graph, and the rest of this module is the tools that work on it.

Key terms

Cheat sheets