Most connected

Scott Vokes
Twitter: @silentbicycle

Judges' comments:

To use:

make
./prog < example-1.txt

Try:

./prog < example-2.txt
./prog < example-tab.txt
./prog < ioccc.txt

Selected Judges Remarks:

What this program does is not witchcraft and there are no spectres, but you might have a meltdown trying to work it all out.

This entry is designed to mislead in many ways. However, if you find yourself wanting to know the possibilities for navigating a graph, you will get the answer you seek with no hocus pocus.

Author’s comments:

Introduction

This program reads a directed graph (as lines with integer node IDs), and prints the graph’s nodes in reverse-topologically sorted order, grouped into strongly connected components. Given a set of nodes representing targets and edges representing dependencies between them, it produces a build order with any dependency cycles gathered.

For example, the following input (provided as example-1.txt):

0 4 8
1 0
2 1 3
3 2
4 1
5 4 6
6 5 2
7 3 6 7

would be interpreted as:

0 -> 4, 8
1 -> 0
2 -> 1, 3
3 -> 2
4 -> 1
5 -> 4, 6
6 -> 5, 2
7 -> 3, 6, 7

So, node 0 has edges to / depends on nodes 4 and 8, node 1 depends on node 0, and so on. Then, it groups the graph’s nodes into strongly connected components and prints them in reverse-topologically sorted order:

0: 8
1: 0 1 4
2: 2 3
3: 5 6
4: 7

It uses Tarjan’s strongly connected components algorithm for the grouping and reverse-topological sorting, along with a bonus hidden implementation of counting sort, which sorts each group.

For other details about the input format, see “Issues and Limitations”.

Building

To build:

${CC} -o prog prog.c -std=c11 -O3 \
    -Wall -Wextra -pedantic -Wno-missing-prototypes

-Wno-missing-prototypes is necessary because there aren’t any prototypes. (They would put the program well over the size limit.)

Note: The program can also be built with -std=c99 or -std=c89.

If building with -Weverything, then -Wno-strict-prototypes may also be necessary – the function pointer declarations for _ and B may get warnings otherwise, for reasons described under “Obfuscations”.

Obfuscations

Issues and Limitations


Creative Commons License

© Copyright 1984-2018, Leo Broukhis, Simon Cooper, Landon Curt Noll - All rights reserved
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.