Home

Topological sort

In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

— Topological sorting, Wikipedia

Math terminology aside, a topological sort allows you take a series of "a comes before b" commands a produce a list of elements which satisfies these constraints. Perhaps these constraints represent files that must be loaded before they can be used, or tasks which must be completed to ship a product.

We'll be using them to generate some CSS to place certain elements above others, a technique that has been used before by the authors of the successful Aphrodite CSS-in-JS framework.

🔗 Example

The following graph comes from Wikipedia:

A collection of 8 nodes with the following associations from top to bottom: (5) points to (11). (7) points to (11) and (8). (3) points to (8) and (10). (11) points to (2), (9), and (10). (8) points to (9).

The orderings below satisfy these constraints:

5, 7, 3, 11, 8, 2, 9, 10 (visual top-to-bottom, left-to-right)
3, 5, 7, 8, 11, 2, 9, 10 (smallest-numbered available vertex first)
5, 7, 3, 8, 11, 10, 9, 2 (fewest edges first)
7, 5, 11, 3, 10, 8, 9, 2 (largest-numbered available vertex first)
5, 7, 11, 2, 3, 8, 9, 10 (attempting top-to-bottom, left-to-right)
3, 7, 8, 5, 11, 10, 2, 9 (arbitrary)

In each list, if node a points to node b, then a appears before b in the list. The fact that multiple orderings exist shows that there are ambiguities: Which of 3, 5, and 7 comes first? We can choose!

How can we generate one of these lists ourselves? Meet toposort.

🔗 Representing the graph

There are a number of ways to take the image above and represent it in code. We'll use an Adjacency list for clarity, by keeping track of a set of nodes (the circles), and for each node, a set of nodes it points to.

// A directed acyclic graph with a list of nodes
// and a mapping of connections between nodes
const dag = {
  nodes: new Set([5, 7, 3, 11, 8, 2, 9, 10]),
  adjacency: {
    5: new Set([11]),
    7: new Set([11, 8]),
    3: new Set([8, 10]),
    11: new Set([2, 9, 10]),
    8: new Set([9]),
  },
};

🔗 The algorithm

One of the algorithms for computing topological sortings is Kahn's Algorithm, which has the following pseudocode.

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge

while S is not empty do
  remove a node n from S
  add n to L
  for each node m with an edge e from n to m do
    remove edge e from the graph
    if m has no other incoming edges then
      insert m into S

if graph has edges then
  return error  (graph has a cycle)
else 
  return L  (topologically sorted)

Converting this to JavaScript to run on dag isn't particularly interesting, but you're welcome to try it out to work your fingers.

function toposort({ nodes, adjacency }) {
  const res = [];

  // Build a set of nodes with no incoming edge
  const noIncomingEdge = [];
  nodes.forEach((node) => {
    if (
      !Object.values(adjacency).some((incoming) =>
        incoming.has(node)
      )
    ) {
      noIncomingEdge.push(node);
    }
  });

  while (noIncomingEdge.length > 0) {
    const node = noIncomingEdge.pop();
    res.push(node);

    // Loop through all the nodes from `node`
    (adjacency[node] || []).forEach((target) => {
      // What other nodes point to this?
      const otherIncomingNodes = Object.keys(
        adjacency
      ).filter(
        (parent) =>
          // Stringly-typed :(
          parent != node &&
          adjacency[parent].has(target)
      );

      // If none: queue target up for processing
      if (otherIncomingNodes.length === 0) {
        noIncomingEdge.push(target);
      }
    });

    // Remove all of the edges coming out
    // of `node`
    delete adjacency[node];
  }

  if (Object.keys(adjacency).length > 0) {
    throw new Error("Loop detected");
  }

  return res;
}

console.log(toposort(dag))

Running this, we get the output:

[ 3, 7, 8, 5, 11, 10, 9, 2 ]

Which closely matches the "3, 7, 8, 5, 11, 10, 2, 9 (arbitrary)." The difference being that the (2) and (9) are swapped: which is fine! There is nothing in the graph suggesting that (2) must come before (9).

If we really wanted to, of course, we could add such a constraint to our directed acyclic graph (DAG).

const dag = {
  nodes: new Set([5, 7, 3, 11, 8, 2, 9, 10]),
  adjacency: {
    5: new Set([11]),
    7: new Set([11, 8]),
    3: new Set([8, 10]),
    11: new Set([2, 9, 10]),
    8: new Set([9]),
    // (2) must come before (9)
    2: new Set([9]),
  },
};

console.log(toposort(dag))
// [ 3, 7, 8, 5, 11, 10, 2, 9 ]

🔗 Making use of a topological sort

We'll build a toy to generate z-index values for us from a series of "element a is above element b" constraints.

To start, we'll define a ZIndexResolver class. It will keep track of a graph of its own and run toposort on it later.

class ZIndexResolver {
  constructor() {
    this.dag = {
      nodes: new Set([]),
      adjacency: {},
    };
  }
}

Defining "element a is above element b" constraints will make use of an above(a, b) method. Massaging this a bit to fit our graph we'll (1) make sure both a and b are in our nodes field and (2) create an adjacency from a to b (defining an empty adjacency set first if necessary)

class ZIndexResolver {
  // ...
  above(a, b) {
    this.dag.nodes.add(a);
    this.dag.nodes.add(b);
    this.dag.adjacency[a] ||= new Set([]);
    this.dag.adjacency[a].add(b);
  }
}

Once above is built, we can run toposort on our graph (we already did the hard work):

class ZIndexResolver {
  // ...
  resolve() {
    return toposort(this.dag);
  }
}

Let's try this out on a plausible layout we might have with content, menus, tooltips, and modals. The "nodes" in our graph will simply be CSS selectors.

const resolver = new ZIndexResolver();

// A nav with dropdowns
resolver.above(".nav", "main");
resolver.above(".dropdown", ".nav");
resolver.above(".submenu", ".dropdown");

// Tooltips in the document
resolver.above(".tooltip", "main");

// Modals should go above everything
resolver.above(".modal", ".nav");
resolver.above(".modal", ".submenu");
resolver.above(".modal", ".tooltip");

console.log(resolver.resolve());

Running this produces the following output

[ '.modal', '.tooltip', '.submenu', '.dropdown', '.nav', 'main' ]

Submenus are above dropdowns, which are above the nav bar, which sit on top of our main content. So far as good.
Modals appear above everything. That seems reasonable to me, they should be front and center.
Curiously, it looks like tooltips appear above dropdowns. , we didn't specify otherwise.

🔗 Generating CSS

To generate CSS, we'll do some looping.

class ZIndexResolver {
  // ...
  generateCSS() {
    return this.resolve()
      .map(
        (sel, idx) =>
          `${sel} { z-index: ${idx}; }`
      )
      .join("\n");
  }
}

// ...
console.log(resolver.generateCSS())

And get the following output:

.modal { z-index: 0; }
.tooltip { z-index: 1; }
.submenu { z-index: 2; }
.dropdown { z-index: 3; }
.nav { z-index: 4; }
main { z-index: 5; }

But — oops — everything's backwards. above(a, b) means a should come before b in our list, but a should have a higher z-index than b if we want it to be above it.

No worries, we'll throw a reverse in there:

class ZIndexResolver {
  // ...
  generateCSS() {
    return this.resolve()
      .reverse()
      .map(
        (sel, idx) =>
          `${sel} { z-index: ${idx}; }`
      )
      .join("\n");
  }
}

// ...
console.log(resolver.generateCSS())

And see the following (correct) output:

main { z-index: 0; }
.nav { z-index: 1; }
.dropdown { z-index: 2; }
.submenu { z-index: 3; }
.tooltip { z-index: 4; }
.modal { z-index: 5; }

🔗 Changes to the ordering

Sure enough, bug reports start pouring in that tooltips keep covering up our dropdowns. The CEO thinks it looks gross and we need to fix it right away.

A tooltip appearing above a dropdown menu: oh the humanity!

Editor's note

This is the actual behavior of GitHub's Primer design system. I pasted the following code in one of the examples:

<Dropdown>
  <Dropdown.Button>Dropdown</Dropdown.Button>
  <Dropdown.Menu direction="sw">
    <Dropdown.Item>Item 1</Dropdown.Item>
    <Dropdown.Item>Item 2</Dropdown.Item>
    <Dropdown.Item>Item 3</Dropdown.Item>
  </Dropdown.Menu>
</Dropdown>
<Box borderWidth="1px" borderStyle="solid" borderColor="border.default" borderRadius={2} p={3}>
  <Tooltip aria-label="Hello, Tooltip!">Text with a tooltip</Tooltip>
</Box>

In the past we may have gone digging for z-indexs and resolved the ordering manually (maybe bump 200 to 300 or even 99999, or just cry). We're in the future now, so such a change is trivial.

const resolver = new ZIndexResolver();

// A nav with dropdowns
resolver.above(".nav", "main");
resolver.above(".dropdown", ".nav");
resolver.above(".submenu", ".dropdown");

// Tooltips in the document
resolver.above(".tooltip", "main");

// Modals should go above everything
resolver.above(".modal", ".nav");
resolver.above(".modal", ".submenu");
resolver.above(".modal", ".tooltip");

// Dropdowns must appear above tooltips
resolver.above(".dropdown", ".tooltip");

console.log(resolver.generateCSS());

And the bug is fixed

main { z-index: 0; }
.nav { z-index: 1; }
.tooltip { z-index: 2; }
.dropdown { z-index: 3; }
.submenu { z-index: 4; }
.modal { z-index: 5; }

A tooltip covered by a dropdown menu. Is this actually better? Who knows.

—

Thanks for reading! I hope this was a gentle introduction to a lesser-known but still very powerful algorithm. I hope you find a fun use-case for it. The code in its entirety can be found below and on GitHub.

And an extra shout-out to my former colleague Emily on having used this technique nearly five years before the publishing of this post.

Full source

// A directed acyclic graph with a list of nodes
// and a mapping of connections between nodes
const dag = {
  nodes: new Set([5, 7, 3, 11, 8, 2, 9, 10]),
  adjacency: {
    5: new Set([11]),
    7: new Set([11, 8]),
    3: new Set([8, 10]),
    11: new Set([2, 9, 10]),
    8: new Set([9]),
    2: new Set([9]),
  },
};

// https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm
function toposort({ nodes, adjacency }) {
  const res = [];

  // Build a set of nodes with no incoming edge
  const noIncomingEdge = [];
  nodes.forEach((node) => {
    if (
      !Object.values(adjacency).some((incoming) =>
        incoming.has(node)
      )
    ) {
      noIncomingEdge.push(node);
    }
  });

  while (noIncomingEdge.length > 0) {
    const node = noIncomingEdge.pop();
    res.push(node);

    // Loop through all the nodes from `node`
    (adjacency[node] || []).forEach((target) => {
      // What other nodes point to this?
      const otherIncomingNodes = Object.keys(
        adjacency
      ).filter(
        (parent) =>
          // Stringly-typed :(
          parent != node &&
          adjacency[parent].has(target)
      );

      // If none: queue target up for processing
      if (otherIncomingNodes.length === 0) {
        noIncomingEdge.push(target);
      }
    });

    // Remove all of the edges coming out
    // of `node`
    delete adjacency[node];
  }

  if (Object.keys(adjacency).length > 0) {
    throw new Error("Loop detected");
  }

  return res;
}

// console.log(toposort(dag));

class ZIndexResolver {
  constructor() {
    this.dag = {
      nodes: new Set([]),
      adjacency: {},
    };
  }

  above(a, b) {
    this.dag.nodes.add(a);
    this.dag.nodes.add(b);
    this.dag.adjacency[a] ||= new Set([]);
    this.dag.adjacency[a].add(b);
  }

  resolve() {
    return toposort(this.dag);
  }

  generateCSS() {
    return this.resolve()
      .reverse()
      .map(
        (sel, idx) =>
          `${sel} { z-index: ${idx}; }`
      )
      .join("\n");
  }
}

const resolver = new ZIndexResolver();

// A nav with dropdowns
resolver.above(".nav", "main");
resolver.above(".dropdown", ".nav");
resolver.above(".submenu", ".dropdown");

// Tooltips in the document
resolver.above(".tooltip", "main");

// Modals should go above everything
resolver.above(".modal", ".nav");
resolver.above(".modal", ".submenu");
resolver.above(".modal", ".tooltip");

// Dropdowns must appear above tooltips
resolver.above(".dropdown", ".tooltip");

console.log(resolver.generateCSS());