Graph visualization in the browser with D3.js

Intro

0:00 Hello and welcome back to episode four, where we're going to give smollerGraph a page in the browser, which draws its graph with D3, walks it a hop at a time, and shows how each node is kept on disk. Let's begin with a quick look at where we're going to be by the end of the episode.

0:17 By the end, sg is going to serve our animals to a page like this one, which lays them out as a graph, with the nodes in chartreuse and the relationships in coral. A walk from the red fox, along EATS, for two hops, lights up a hop at a time, down to the clover and the wheat. And clicking the red fox opens its record, as smollerGraph keeps it on disk: its page, its offset, its thirty-two bytes, and its chain of relationships, newest first.

0:43 On the website of the series, you can find more information about the project. The code is open source on GitHub, tagged at each step of each episode, so that you can follow along, and each episode has a page here, with its chapters and its code.

Last time

0:58 Now, before we get to today's work, let's quickly go over what we did last time. We wrote a generator for a social graph of a million relationships, identical on any machine. Sg learned to time its loads, and sg bench to time its walks. A script asked smollerGraph, Kùzu and Neo4j one question, for a thousand people. SmollerGraph was about twenty times slower than Kùzu to load, as it reads or writes six pages for each relationship it adds. It was about eleven times quicker than Neo4j to walk, as it's a function call, with no query language to pay for. The buffer pool, which keeps pages in memory, is the next big change to storage, and it's coming in the next episode. Before it, though, I'd like us to be able to see the graph, as the changes from here on are a lot easier to follow when we can look at what they do.

Today

1:47 Today, we're going to give smollerGraph a UI of its own, a bit like Neo4j Browser, which we saw in episode one. But first, the code gets two things that nanoMMO's code, from the other C++ series on this channel, has had from the start. Two linters, cpplint and clang-tidy, which check each push against Google's style guide and for common bugs. And Abseil, Google's C++ library, whose absl Status is how our errors are going to come back from now on. Then the graph learns to be written as JSON, the text format that web pages read, and a new command, sg serve, answers requests for it over HTTP. A page in the browser draws it with D3, a JavaScript library for drawing data, with a walk, lit up a hop at a time, and an inspector, which shows a node's record as it's kept on disk. All right, let's get started with the linters.

Two linters

2:41 The first linter is cpplint, Google's checker for its C++ style guide, and CPPLINT dot cfg holds its settings. Its first filter leaves out the copyright check, and the comment says why: the licence is in LICENSE, at the top of the repo, so the files don't each start with a copy of it. The second filter leaves out the check for includes without a folder in front, as our sources are all in src, and they include each other by name, which its comment says. The second linter is clang-tidy, which reads the code the way the compiler does, and dot clang-tidy says which of its checks to run. Minus star turns them all off, and then we turn on four families of them. Bugprone is for patterns that are often bugs, clang analyzer is the static analyzer, which follows the paths the code can take, and concurrency and performance are what they say. A few in each family are left out, with a minus in front, as they flag code that's fine here, such as easily swappable parameters, which would flag any function that takes two numbers in a row. Warnings as errors makes each finding fail the build, and the header filter checks our own headers, in src, and not the libraries'. In the Dockerfile, two new stages run them. The lint stage starts from a small Python image, and installs clang-format and cpplint with pip, at versions that won't change under us. The comment explains the folder they work in. Cpplint names each header guard after its path, so the sources are copied into a folder named after the project, which gives guards such as smollerGraph graph h, the ones we've been writing. Then find lists the C++ files, clang-format checks their format without changing them, and cpplint checks them against the style guide. The tidy stage starts from our toolchain, and installs Clang eighteen with its clang-tidy. It configures the build with CMake, which writes the compile commands file that clang-tidy reads, and run clang tidy checks each source file in src and tools, a few at a time. In CMake, the comment says why one line is new: with Clang, CMake looks for C++ twenty modules, which we don't use, and the flags it adds for them are ones clang-tidy can't read. So scanning for modules is off, for all of our targets. In the CI workflow, GitHub Actions builds the lint stage before the tests, and the tidy stage after them, so a push that breaks the style guide fails, the way a broken test does. Then come the fixes that the two linters asked for. The style guide doesn't allow the filesystem header, which it says lacks support for testing, and has security problems. So in graph dot c c, Open makes its folder with mkdir, from the system's headers, instead of create directories. The comment says why an error of E E X I S T is fine: the folder can be there already, from an earlier run. Mkdir makes one folder, and not the ones above it, which is all our graphs need. Make friends, the tool that writes the made-up social graph for the benchmarks, swaps the filesystem header for sys stat dot h and cerrno, as it makes its folder with mkdir too, in place of create directories. A folder that's there already, from an earlier run, is fine, as the comment over it says. When mkdir fails for any other reason, it prints the system's error, with str error, from cstring. The graph's test used remove all, from the filesystem header, to clear out a folder left from an earlier run. Now mkdtemp makes a new folder, replacing the six X's at the end of its name with a name of its own, so nothing is left in it from a run before, as the comment says. Last, cpplint asks each file to include the headers for what it uses, instead of getting them through another header. So facts dot c c includes string, and so does pager dot c c, and query dot c c includes vector.

6:35 Let's build the lint stage, which installs the two tools and runs clang-format and cpplint over the code. It finishes without a word from either of them, which is what we want from a linter. Then the tidy stage, which takes longer, as it configures the build and runs clang-tidy over each source file. It finishes without a finding too, and CI is going to run both of them on each push from here on.

Errors as statuses

7:01 Until now, a function of ours that could fail returned false, and wrote what went wrong into a string we passed it. Abseil, Google's open source C++ library, has a type for that, absl Status, which this guide describes. A status is a code and a message, and the code is ok when nothing went wrong. The codes are a fixed list, the canonical errors, such as not found, invalid argument and permission denied, so the code that gets an error can tell one kind from another without reading the message. And for a function that returns a value when it works, absl Status Or holds the value or the error, which the JSON and the queries we write later are going to use.

7:41 In CMake, Abseil is fetched like GoogleTest, before it, from its release of May twenty twenty-five, which is what nanoMMO uses too. The comment says what we use it for, absl Status and its string functions. ABSL propagate C X X standard tells Abseil to build with our C++ version, twenty. System marks its headers as a library's, so our warnings don't fire inside them, and exclude from all builds the parts of Abseil we link, and no more. The library links Abseil's status, status or and strings, publicly, so everything that links our library gets them too. In dot clang-tidy, one check gets told about absl Status. Performance no automatic move would flag returning a status that can't be moved, which is fine for a type as cheap to copy as a status. In pager dot h, we include string view and Abseil's status header. Open returns a status, and takes no error string, and its comment loses its second sentence, as the return type says it now. Open temporary returns a status too, and takes nothing at all. Adopt takes the name of what it opened, for its message. In pager dot c c, we include the status header and Abseil's str cat. Open returns a status, and passes its path to Adopt, as the name of what it opens. Open temporary returns a status too, and tells Adopt it's opening a temporary file. When the file can't be opened, Adopt makes its status with errno to status, which, as the comment says, picks the status code that goes with the system's error. A missing folder is not found, and a file we're not allowed to open is permission denied. Str cat puts the message together, can't open and the name, without plus signs or to string calls. The status is made before close, as close can change errno. At the end, Adopt returns ok status, for a file it opened. In record file dot h, we include the status header. Open returns a status now, in place of a bool, and takes no error string. When the pager can't open its file, it returns the pager's status, and otherwise it loads the count, and returns ok. The if has an initialiser, from C++ seventeen: the status lives in the if's own scope, and the condition after the semicolon checks it. Open temporary works like that too, with the pager's temporary file. In graph dot h, we include the status header, and Open returns a status too, with no error string to fill in. In graph dot c c, we include the status header and str cat. The constructor opens its two temporary files, the second when the first worked, and if either failed, it stops, with the status's text, from to string. Open returns errno to status when mkdir fails, in place of the text from str error, with the folder's name in the message. Then the two files open, the relationships when the nodes opened, and if either failed, Open returns its status. That replaces the old check, which joined two bools with an or. The comment over them says how they open: each one opens if the one before it did, and the first error is the one we return. The loop that reads each node's name back in is as it was, and at the end, Open returns ok, in place of true. In facts dot h, we include the status header too. Load facts returns a status, in place of a bool, and takes no error string, as the status carries the error now. Its comment says that a line it can't read is an error, with the line as its message. In facts dot c c, the two places that put the line in the error string and returned false now return an invalid argument error, Abseil's code for input that's wrong, with the line as its message. The end returns ok, in place of true. In main dot c c, charconv goes, and Abseil's numbers header gives us simple a to i, which reads a whole number from text, and says whether it could. Parse hops uses it, in place of from chars, so its check fits on a single line. Load keeps the status in an if with an initialiser, like the record file's, and prints its message when the facts don't load, and main prints it when the graph doesn't open, from an if like that too. In the graph's tests, the error strings go, and each status is compared with absl ok status, with assert e q, so when one fails, GoogleTest prints the status, with its code and its message. The test for a line that isn't a fact keeps the status Load facts returns, and checks that it is an invalid argument, and that its message is the line. The pager's tests include the status header, and lose their error string. Each of their three opens has to return ok status: the temporary file's, and the real file's, before and after it's opened again. The record file's tests change like that too: the header comes in, the error string goes, and its three opens are compared with ok status.

12:36 Let's build it, which takes a while the first time, as it builds the parts of Abseil we link. Then the tests, which pass, with the errors as statuses now.

The graph as JSON

12:46 The browser asks sg for a page, and the page asks for the graph, with a request for a path such as slash A P I slash graph. Sg serve takes the request, using a small HTTP library, and hands it to a function in a file of its own, api dot c c, which answers with JSON. Each answer is read from the node and relationship records we wrote in episode two. Keeping the JSON apart from HTTP means our tests can check each answer without starting a server.

13:16 The JSON goes in a header of its own, api dot h. It includes string and string view, and our graph's header. Its comment says what it's for: what sg serve answers with, as JSON. It's kept apart from HTTP, so the tests can check it without a server. Json string returns a piece of text as a JSON string, which its comment spells out: in quotes, with quotes, backslashes and control characters escaped. Error JSON returns an error's message as JSON, for the UI to show. Graph JSON returns each node and each relationship in the graph, for the UI to draw. In api dot c c, we include string, for the strings we build, and Abseil's str cat, for building them. Json string starts with an opening quote, and goes through the text a character at a time. A quote would end the string early, and a backslash would start an escape, so each of them goes in with a backslash in front of it. Characters below hex twenty are control characters, such as a new line or a tab, which JSON doesn't allow inside a string. The char is cast to unsigned first, as a char can be signed. Then a byte above a hundred and twenty-seven, such as part of the accented u in Kùzu, would come out negative and look like a control character. The comment says how each one goes in: as backslash u, and its code in four hex digits. Abseil's str append adds both to the end of the string, and absl Hex writes the code in hex, padded with zeros to four digits. Any other character goes in as it is, and a closing quote ends the string. Graph JSON builds one object, with two arrays in it. The nodes come first: for each id from zero up to the node count, an object with the id, and the name, which goes through Json string. Str append takes any number of pieces, strings and numbers alike, and adds them to the end of the string in one go. A comma goes between two objects, but not before the first one. Then come the relationships, after a bracket that closes the nodes and the start of a second array. For each relationship id, from zero up to the relationship count, we read the relationship's record from its file. A comma goes in front of all but the first one, as it did for the nodes. Then we write the relationship's id, the node it goes from, and the node it goes to. Last comes its type, which goes through Json string, like the names did. Str append writes the ids as plain JSON numbers, with no to string needed, and the closing brackets end the array and the object. That loop is all it takes to turn the relationship records into JSON. In graph dot h, the graph gets a way to read a relationship's record by its id, next to name, which reads a node's. In CMake, api dot c c joins the library, and api test dot c c joins the tests. Api test dot c c includes api dot h first, then the graph and GoogleTest. The first test, Escapes what JSON does not allow, checks that a plain name comes back in quotes, and that quotes, a backslash and a new line come out escaped. The strings it expects are raw string literals, between R, a quote and a bracket, so their quotes and backslashes need no escaping of their own. The second test, Lists nodes and relationships, makes a graph of its own in temporary files, as our other tests do. It adds the red fox first, and then a relationship where the fox eats the rabbit, which is added as a node on the way. Then it checks the whole of the JSON that graph turns into, written out the way we expect it. The fox is node zero, the rabbit is node one, and relationship zero goes from zero to one, with the type EATS. It's split over several raw strings, to keep the lines short, as C++ joins string literals that sit next to each other.

17:08 Let's build it, and run the tests, the two new ones along with the nine from before. They all pass, the new ones on the first try.

sg serve

17:18 For HTTP, we're going to use cpp-httplib, a library by Yuji Hirose that fits in a single header, under the MIT licence. An HTTP server is a project of its own, and not the one this series is about. In CMake, we fetch it like GoogleTest, after it. Its comment says how we use it: in one header, without HTTPS or compression. Cpp-httplib uses OpenSSL, zlib, Brotli and zstd when it finds them on the machine, so these four lines turn them off, and the build doesn't depend on what happens to be installed. Then we declare it, from the release zero point sixty point one, and make it available. Sg is now built from main dot c c and a new file, server dot c c, and it links with httplib's target, which brings in its header and threads. The library and the tests don't need HTTP, so they stay as they were. Server dot h includes string, Abseil's status header, and our graph's header, and declares one function, Serve. It takes the graph, an address and a port, and returns an absl Status. Its comment says what it does: it answers HTTP requests for the graph on that address and port, until the process is stopped. Like Open, it returns an error when it can't listen there, which the comment says too. In server dot c c, we include httplib dot h in angle brackets, as a library's header, then iostream and string, Abseil's status and str cat, and api dot h. Serve starts by making a server, from cpp-httplib's server class. Before anything else, we set its socket options, and the comment above them says why. Cpp-httplib lets several servers share a port by default, with an option called S O reuse port. So a second sg serve on a port that's in use would start without a word, and the two would take turns answering. S O reuse address, on its own, still lets a restarted server have its port straight back, and refuses a port that's busy. The option is set in a lambda, a function written in place, which cpp-httplib calls with each socket it opens, and set socket opt is its helper for setting one option on a socket. Those few lines turn a confusing mistake, two servers taking turns on one port, into an error we can see at once. It's a default worth knowing about, if you use cpp-httplib in a project of your own. Then we tell the server what to do with a GET request for slash A P I slash graph. Its handler is another lambda, which captures the graph by reference, and sets the response's content to Graph JSON, with the content type application slash JSON, so the browser knows how to read it. The comment above it says something worth knowing: the server answers requests on several threads at once. That's fine for now, as nothing writes to the graph while it's served. And our pager reads with pread, which doesn't move a shared position in the file, so two reads at once don't get in each other's way, as we said in episode two. Bind to port takes the address and the port, and when it fails, we return an unavailable error that says where, put together with str cat. Then we print where the graph is being served, with a link we can open in a browser. Std endl ends the line, and flushes it out, so it's written straight away. The comment says why that matters: in Docker, the output isn't a terminal, and the line would wait in a buffer otherwise. Listen after bind waits for requests and answers them, until the process is stopped, and if it stops listening for some other reason, we return an internal error. Otherwise, Serve returns ok, once the server stops. In main dot c c, we include server dot h, next to the graph and the query. The usage message gets a new line for sg serve, under bench. It takes a graph folder, a port, and an address, which is in square brackets, as it's optional. Main's own Serve reads the port with simple a to i, like the hops, and checks that it's a whole number from one to sixty-five thousand five hundred and thirty-five, the largest port there is. When it isn't one, we print an error that says what a port is, with the text we were given, and return one. Then it calls smollerGraph's Serve, and when the status isn't ok, prints its message after sg and a colon, like our other errors. Down in main, there's one more command to recognise, next to load, walk and bench. A new flag is true when the command is serve, and there are three arguments after sg or four, and the flag is called serve too. The usage is printed when none of the four commands match, so serve joins that list. After the graph opens, serve calls our Serve, with the address one two seven dot zero dot zero dot one when there's no fourth argument. That's the loopback address, which other machines can't reach, and the comment over Serve says so: it listens on this machine alone, unless it's given another address. The server has no passwords, so that's the safer default. And compose dot yaml runs it in a container, with the animals. Its comment says how: docker compose up, then open localhost on port eight four seven four. The project is called smollerGraph, and its one service, sg, is built from our Dockerfile's build stage, where the program gets built. Its command removes a graph left over from an earlier run, loads the animals, and serves them on port eight four seven four, on all of the container's addresses. Inside a container, the loopback address is the container's own, so nothing outside it could reach the server there. Exec replaces the shell with sg, and ports publishes port eight four seven four on our machine. Init true puts a small init process in front of sg, which passes on Docker's stop signal, so stopping the container doesn't wait ten seconds before it's killed.

23:17 Let's build it, which downloads cpp-httplib the first time. We load the animals into a graph folder, as before, and start sg serve on port eight four seven four, in the background, with an ampersand, so the terminal stays free for us. It says where it's serving the graph, on localhost. Curl asks for slash A P I slash graph, and jq, a command-line tool for JSON, prints the first four nodes, one a line. Node zero is the red fox, the first name in the facts file. And here are the first four relationships, starting with relationship zero, from the red fox to node one, mammal, of type IS_A.

Drawing the graph

23:57 Our graph has no positions of its own, so to place its nodes on the page, we're going to let D3 simulate forces between them, which is called a force-directed layout. D3 puts the nodes in a spiral to begin with, in the order they come. Each relationship pulls its two nodes towards a distance we choose, like a spring. Each node pushes the others away, like charges of one sign, which spreads the graph out. A collide force keeps the circles from overlapping, and a centring force keeps the graph in the middle of the page. The simulation moves the nodes a little on each tick, and the moves get smaller as it cools down, until the graph settles, after about three hundred ticks.

24:35 First, sg serve needs to send the files that make up the page, the HTML, the style sheet and the script. In server dot c c, after the socket options, set mount point serves the files in a folder at the root of the site. A request for slash style dot css gets the style sheet from it, and a request for slash on its own gets index dot html. The folder is SMOLLERGRAPH UI, which CMake is going to set. If the folder isn't there, it returns a not found error, with a message that names the folder. Its comment says why the files come from the source tree: changing one needs a reload in the browser, not a new build. In CMake, target compile definitions passes that name to the compiler, as a macro holding the path to the U I folder in our source tree. Now the page, in a new folder, U I. Index dot html starts with the doctype, then the html element, in English. In the head, meta charset says the page is UTF-8, and the title is smollerGraph, for the browser's tab. The first link loads JetBrains Mono from Google Fonts, the font of our videos, and the second loads our style sheet. Then comes D3, version seven point nine, from jsDelivr, which serves packages from npm. Graph dot js is a module, which the browser runs once the page is read, and which can use await outside a function. In the body, the header holds the brand, smollerGraph in brackets, as a Cypher node, like on the website. Main holds an S V G element with the id graph, where we're going to draw. S V G is the browser's format for drawings made of shapes and text. In its defs, the definitions it draws later, is a marker, an arrowhead for the ends of relationships. Its comment, above it, says how it's drawn: back from the line's end, so it stops at the edge of the node's circle, and doesn't hide under it. The view box gives it coordinates from zero to ten along the line, and minus five to five across it. Ref X is the point of the marker that sits on the line's end, so at thirty-eight, the tip, at ten, sits twenty-eight back: the circle's radius, twenty-six, and two for its outline. Marker units user space on use keeps it ten pixels wide, however thick the line is, and orient auto turns it along the line. The path draws the triangle, from zero, minus five, to the tip, at ten, zero, and back to zero, five. The style sheet goes in all at once, as it's about how the page looks, not how it works. Its comment says it uses the colours of the series, kept in custom properties at its top: the green-black field, chartreuse nodes and coral relationships. The body is a grid, with the header over the graph, and the graph fills the rest of the window. Nodes are circles in the field's colour, outlined in chartreuse, and relationships are coral lines, a little over half opaque, so the nodes stand out. Labels get an outline in the field's colour, drawn under the letters with paint order stroke, so they read over the lines that cross them. Then comes graph dot js, whose comment says what it does: it draws the graph sg serve sends, with a circle for each node and an arrow for each relationship, placed by a force simulation. D3 select finds the S V G element, by its id, and wraps it in a D3 selection, which is how D3 works with elements. We ask the browser for its size, its width and height, which the simulation is going to need. Then we append a group, G in S V G, which holds everything we draw, so moving or scaling that group moves the whole drawing. That's what d3 zoom does: the comment says dragging the background moves the view, and the mouse wheel zooms it. On each zoom event, the group gets the event's transform, a translation and a scale. Calling the zoom on the S V G attaches its event handlers to it. Then we fetch slash A P I slash graph, wait for the response, and wait again for its body to be read as JSON. Await at the top level works, as graph dot js is a module. Links are the relationships, mapped to copies of them with a source and a target, from their from and to. The spread, three dots, copies each relationship's fields into a new object, and the comment says why: D3 finds the two ends of a link by its source and target. Now, on to the simulation, where D3 force simulation takes the nodes, and gives each one a position, x and y, which it changes on each tick. The link force pulls each relationship's two nodes towards a hundred and seventy pixels apart. Its id function tells it to find nodes by their id field, as it would use their place in the array otherwise. The charge force, many body, pushes each node away from the others, with a strength of minus nine hundred, where a negative strength pushes. The centre force keeps the graph's middle at the middle of the S V G, and the collide force keeps nodes at least sixty pixels from each other's centres. The comment above it says it in words: relationships pull their nodes together, nodes push each other apart, and the whole graph is pulled towards the middle. Those four forces, and a few numbers, are the whole of the layout. Changing those numbers changes how spread out the graph is, and they're worth playing with. Next come the elements that draw the relationships on the page. Select all finds the elements with the class relationship, of which there are none yet. Data binds our links to them, a link to an element, and join creates an element for each link that has none, a group here, which gets the class relationship. Each group gets a line, which ends in our arrow marker, and a text, with the relationship's type. D, in those small functions, is D3's usual name for the datum, the piece of data bound to an element. That's D3's data join, which is its central idea: data on one side, elements on the other, joined up, so the elements follow the data. The nodes are joined in a similar way: a group for each node, with the class node, which calls drag on it, so it can be dragged. Each node's group gets a circle, twenty-six pixels in radius, and a text with its name, forty-eight pixels down, under the circle. Then comes the tick handler, for the simulation's ticks. Each tick of the simulation moves the nodes a little, so we move each line's ends to its source and target, which the comment above says: the relationships follow their ends. By now, the link force has swapped each link's source and target for the node objects, so they have an x and a y. Each type's label goes halfway along its line, and each node's group is translated to its node's position, which moves its circle and its name together. Last, drag, which the comment says pins a node under the pointer, and lets it go when it's dropped. D3 drag has three events, and we handle each of them. On start, when no other drag is going on, we reheat the simulation, with an alpha target of zero point three, so it keeps moving while we drag. Alpha is how hot the simulation is: it starts at one and cools towards zero, and the moves get smaller as it does. F x and f y fix a node's position, so the node starts out pinned where it is. On drag, the pinned position follows the pointer, and the rest of the graph reacts to it. On end, the alpha target goes back to zero, so the simulation cools down again, and the node is let go. That's the whole page, in about seventy lines of JavaScript.

31:54 Here's the page, served by sg in Docker, at this step's tag. The ten nodes started in a spiral, and the forces spread them out, with each relationship pulling its two ends together, until the graph settled. The red fox has four relationships going out of it, as arrows: it is a mammal, it lives in the forest, and it eats the rabbit and the field mouse. The meadow has the most coming in, with the rabbit and the field mouse living there, and the clover and the wheat growing there. And the arrowheads stop at the edges of the circles, as the marker was drawn back from the ends of the lines.

A walk, hop by hop

32:31 For the walk, the UI needs more than where it ends: it needs the nodes each hop reaches, to light them up in turn. In query dot h, Walk hops returns those, as a vector of vectors, one for each hop. Its comment says what's in it: the start on its own, then the nodes one hop away, and so on, so the last of them is what Walk returns. In query dot c c, Walk keeps its signature, so sg walk and sg bench, which call it, don't change. Inside, it now calls Walk hops, and returns the last hop's nodes, moved out of the vector, as we don't need the others. Below it, Walk hops takes the arguments Walk takes, and returns a vector of hops. Walk hops is the old loop, with reached in place of the frontier. Reached starts with one hop, the start on its own. Each hop goes through the nodes the last hop reached, which reached dot back gives us, and finds their neighbours, listing each of them once, as before. Then the next hop's nodes are pushed onto the end of reached, moved instead of copied. In api dot h, a walk can go wrong in ways the whole graph can't, so Error JSON comes first: it returns an error's message as JSON, for the UI to show, as its comment says. Then Walk JSON, which takes a walk's start, relationship type and hops, as text from a request. It returns an absl Status Or of a string: the JSON when the request makes a walk, and an error otherwise. Its comment says which errors: not found for a start the graph doesn't have, and an invalid argument for hops that aren't a number up to the limit. Both of them sit with Graph JSON, which stays as it was. In api dot c c, we include cstdint, optional and vector, Abseil's status, status or, numbers and str join, and query dot h, for Walk hops. In an unnamed namespace, k max hops is ten, and the comment says why there's a limit: the UI draws a few hops, not the whole graph. A walk of a hundred hops could keep the server busy for a while, too. Parse number takes the text and a maximum, and returns a std optional, which holds a number or nothing at all. Its comment says what it does: it reads text as a whole number, if it's one, and it's at most max. Simple a to i reads the text into number, and when it can't, or the number is over the maximum, we return null opt, the optional with nothing in it. Error JSON puts the message in an object, with a field called error, through Json string. Then comes Walk JSON, which uses both of them. It looks the start up by its name first, with Find, which returns an optional node id. When the graph has no node by that name, it returns a not found error, with a message that names it. Then it parses the hops, and anything that isn't a number up to ten is an invalid argument, the code for a request that's wrong. Returning a status where the function returns a status or works, as status or holds either one. The JSON is an object with one field, hops, an array of arrays. The comment explains them: each hop's nodes are an array of their ids, and the hops are an array of those. For each hop that Walk hops reaches, str join writes its ids with commas between them, and str cat puts square brackets round them. Then str join puts the hops together, with commas between them too, inside the object. Returning the string works too, as a status or holds the value when there's no error. In the tests, Lists the nodes each hop reaches adds the fox, the rabbit and the clover, with the fox eating the rabbit, and the rabbit eating the clover. A walk of two hops from the red fox along EATS has to work, and give three hops of nodes: zero, the fox, then one, the rabbit, then two, the clover. Assert true stops the test when the status or isn't ok, and prints its status, and the star reads the value out of it. Says what's wrong with a request asks for a badger, which the graph doesn't have, and expects a not found error, with absl is not found. Then hops written as the word two, and eleven hops, one more than the limit, both have to be invalid arguments. In server dot c c, an unnamed namespace gets a function of its own, Send. Not found is four oh four, and anything else is four hundred, a request that's wrong. An error goes in through Error JSON, and the JSON of an answer that worked goes in as it is, with the content type for JSON. Its comment says what it does: it sends JSON, or an error as JSON, with the HTTP status that goes with the error's code. Then a handler for slash A P I slash walk, which takes the request this time, as it needs what's in it. It reads three parameters from the request's query string, from, type and hops, which cpp-httplib has already split up and decoded for us. And it sends whatever Walk JSON returns, an error or the hops. In index dot html, the header gets a form for the walk, which reads as a sentence. Walk from, then an input for the start's name, the red fox to begin with, along, an input for the type, EATS, and for, a number input with two hops, from zero to ten. Each input has a name, which is the parameter it becomes. The button submits the form, and the output after it is where an error goes. The style sheet gives the form the field's colours, with the button in chartreuse. At the end come a walk's three classes: a node the walk reaches gets a thicker outline, a node it ends on is filled in, and a relationship it followed is drawn thicker, at full strength. At the end of graph dot js, the comment says what a walk does. It asks sg serve for the nodes each hop reaches, and lights them up a hop at a time, with the relationships it followed to reach them. Form is the walk's form, selected by its id, and timers holds the timers of a walk that's lighting up. On submit, prevent default stops the browser from loading a new page, which is what a form does otherwise. Form data reads the form's inputs, and URL search params turns them into a query string, such as from equals red fox, with its space encoded. We fetch slash A P I slash walk with that query, and read the answer as JSON. The output shows the answer's error, if it has one, and nothing otherwise, with the two question marks. And if the response is OK, light lights up the hops, along the type we asked for. Light clears the timers of a walk that's still lighting up, which the comment says, so a walk started before this one stops. Then it takes the classes off the nodes and relationships, so nothing is lit up. And it sets a timer for each hop, a second apart, which calls light hop. Light hop, its comment says, lights up the nodes one hop reaches, and the relationships it followed from the hop before. Before is a set of the ids the hop before reached, and reached is a set of this hop's. A relationship was followed when it has the walk's type, starts at a node in before, and ends at a node in reached. For the start, hops of minus one is undefined, which makes an empty set, so the start lights up with no relationships, as the comment says. The followed relationships get the class followed, and the nodes this hop reached get reached, and answer too, when it's the last hop. That one test is how the page knows which arrows the walk went along.

39:52 Let's build it, and run the tests, the four new ones among them. All thirteen pass, along with episode one's tests of Walk, which now goes through Walk hops.

40:03 With the page at step six, clicking walk asks for two hops of EATS from the red fox. The fox lights up first, then, a second later, the rabbit and the field mouse, with the two relationships it followed, and then the clover and the wheat, filled in, as that's where the walk ends. A walk from the tawny owl reaches the field mouse, and then the wheat, which the owl doesn't eat, but its prey does. And a badger, which our graph doesn't have, gets the four oh four's message, next to the button.

A node's record

40:32 The inspector shows where a record is kept, on which page and at which offset, and the record file is what knows that, from a record's id. So in record file dot h, the two functions that work it out come out of the private part, at the bottom of the class. They go into the public one, under count, with their comment about the header page. Page of and Offset of are static, so they need no record file to call them, just a record's id. In graph dot h, the graph can read a node's record by its id, as it can a relationship's. In api dot h, under Walk JSON, Node JSON takes the graph and an id, as text, and returns a status or too. It returns a node's record as it's kept on disk, and the comment lists what's in it: its page, its offset in the page and its bytes, then its chain of relationships, newest first, each with where it's kept. An id the graph doesn't have is an error, as the comment's last sentence says. In api dot c c, we include record file dot h, for the record file's two functions. In the unnamed namespace, after Parse number, Where is a template on the type of record, which it's given when it's called. It returns the page a record is kept on, and where it starts in that page, as two fields of a JSON object, which its comment says. It calls the record file's Page of and Offset of, for that type of record, so it works for nodes and relationships alike, and str cat writes the two numbers into the fields. Hex is a template too, on the record's type, and it takes a record, by reference. It returns the record's bytes in hex, sixteen a line, as x x d shows them. Reinterpret cast lets us look at the record as an array of bytes, which is fine for a struct like ours, made of plain numbers and characters. For each byte, a new line goes in front of the seventeenth, and a space in front of the others, apart from the first. Str append adds the byte as two hex digits, with absl Hex padding it with a zero when it needs one. Node JSON parses the id, and anything that isn't a number below the node count is a not found error. Then it reads the node's record, with the graph's new node function. Str cat starts the JSON with the node's id, then its name, through Json string. Where, for a node record, adds its page and its offset, as two more fields, and then come its bytes, from Hex, as a string. Last, the array for the chain opens, after its name. The comment says what comes next: the chain, from the node's first relationship to its last, which is the order they're kept in, newest first. It starts at the node's first out, and goes on until there's no next relationship. For each one, it reads the relationship's record, and a comma goes in front of all but the first. Then str append writes the relationship's id, which is where it sits in the relationship file. Its type goes through Json string, as it did for the graph's relationships. Next comes the node it goes to, by id, and by name, which the graph reads from that node's record. And last, where the relationship is kept, from Where, for a relationship record this time. Then it moves on to the record's next out, as Neighbours does, until the chain comes to an end, at no relationship. That's the chain we drew in episode two, read straight from the records. The first new test, Shows where a record and its chain are kept, makes a graph with the red fox in it. The fox eats the rabbit first, and then lives in the forest, so living in the forest is its newest relationship. The test asks for node zero, and the answer has to be ok. It's on page one, at offset zero, the first record after the header page. The comment explains its bytes: the name, padded with zeros, then the first relationship's id, one, with its lowest byte first, as x86 and ARM keep numbers. Five two, six five and six four are R, e and d in ASCII, and the zero one near the end is that id. The new line between the two rows of bytes is written as backslash u, zero zero zero a. Then the chain, newest first: relationship one, LIVES_IN the forest, at offset thirty-two, then relationship zero, EATS the rabbit. The second new test, Refuses a node the graph does not have, makes a graph with the red fox alone in it. It asks for node one, when there's one node, zero, and for the word fox, and both have to be not found errors. In server dot c c, the path for a node is a regular expression, in a raw string: slash A P I slash node slash, then one or more digits, in brackets, so they're captured. Request dot matches holds what was captured, and the first capture is the id, which goes to Node JSON, and Send turns its not found into a four oh four. In index dot html, next to the S V G, an aside holds the inspector: a heading for the node's name, a paragraph for where it is, and a pre element for its bytes, which keeps their line break. Then a heading that says relationships, newest first, and an ordered list for the chain. The style sheet hides the inspector until it's opened, and lays it out at the right of the graph. The node being inspected gets a light outline, and the relationships in its chain are dashed. In graph dot js, the zoom goes in a constant, as we're going to move the view with it. At the end, the comment says what clicking a node shows: its record as sg keeps it on disk, where it is, its bytes, and its chain of relationships, which light up in the graph too. Each node's group gets a click handler, which inspects the node by its id. Inspect fetches slash A P I slash node slash and the id, and reads the record. Panel is the inspector, the aside in the page. If it isn't open yet, we open it with the class open, and the comment says what comes next. The panel takes room from the graph, so the view moves over by half of the panel's width, and the graph stays in the middle of what's left. A transition animates that move, through the zoom's translate by, so the zoom knows where the view went. Then the panel's heading gets the node's name, and the paragraph says which node it is, and its page and offset. The bytes go in the pre element, as they come. The list is another data join: a list item for each relationship in the chain, with its type, the node it goes to, and on a second line, its id, page and offset. Chain is a set of the chain's relationship ids, and last come the classes: inspected on the node we clicked, and chained on the relationships in its chain. And the README says how to run the UI, with sg serve, or with docker compose up.

47:11 Let's build it, and run the tests, with the inspector's two: one checks where a record and its chain are kept, and one asks for a node that isn't there. All fifteen of them pass, on this machine and in Docker.

47:23 Back in the browser, here's the page at step seven, with the animals laid out as before, while the forces settle. Clicking the red fox opens its record, and the view moves over to make room for it. It's node zero, on page one, at offset zero, the first record after the header page. Its thirty-two bytes start with its name, R, e, d, a space, then f, o, x, in ASCII, padded with zeros. They end with zero b, which is eleven, the id of its first relationship. And here's relationship eleven, at the top of the chain, where the fox eats the field mouse. Then come ten, four and zero, newest first, as we drew the chain in episode two, and in the graph, the four of them are dashed. The tawny owl is node four, at offset a hundred and twenty-eight, which is four times thirty-two. Its chain starts with relationship twelve, where it eats the field mouse, and ends with three, where it is a bird.

Wrap-up

48:17 So, today the graph learned to be written as JSON, with tests that check each answer without a server. Sg serve answers HTTP with cpp-httplib, on this machine alone unless it's told otherwise, and in Docker with compose. A page draws the graph with D3's force simulation, lights up a walk a hop at a time, and shows a node's record and its chain as they're kept on disk. Next time, we're going to get back to storage, with a buffer pool, which keeps pages in memory instead of reading and writing six of them for each relationship. With sg serve answering on several threads, it's going to have to be safe to use from more than one of them at once. And we're going to measure what it does, before and after.

49:01 This is going to be an evolving project, so I'd love to hear from you. Let me know in the comments what you'd like to see in the UI next, and if you'd like to follow along, subscribe to the channel. I hope you find this useful, and thanks for watching.