DEV Community: Christian Herlein

Graphs are not data structures

Christian Herlein — Mon, 17 Mar 2025 18:46:18 +0000

In a programmer's lifetime, you have to deal with thousands of structures. In other words, you are always deciding how to organize your data. There are many options out there, from single variables to complex matrices of custom-defined structs. One of those common approaches is graphs.

But graphs are not data structures: they are mathematical structures.

Of course, you can apply them as data structures; so many pieces of software depend on them. Even if you don't realize it, you are dealing with graphs all the time. For example, a linked list is just a special case of a directed graph.

But when considering graphs as mathematical constructs rather than mere data structures, they become a much more powerful tool. Here I present two more applications of graphs in software development: as a processing design and as codebase representation.

Note: Although this is a general programming post, I'm using Go for the code examples.

Process by graphs

Let's deal with this problem:

We have to process each day's minimum temperature of a city (X), doing x³ and then the result square root or its opposite natural logarithm. Then, store the result into a map, using the result as the key and its certificate as the value.

But we have to take care of:

Numbers are 8-bit signed integers -128; 127
Handling real-number groups
If x < 0, doing sqrt(x³) will result in a math error. In such cases, the program will use logn(-x)
If x³ overflows int8 max value, will look for logn(-x³)
When looking for logn, we will ask a remote service for an error signature

Is it a realistic problem? Of course not. But the abstract idea is present here.

Lets think in a traditional approach:

  func process(input []int8, certs map[float64]string) {
    for i := 0; i < len(input); i++ {
      var result float64
      var needCert bool
      var cert = "no_need"

      x := input[i]
      switch {
        case x > 0 && x*x*x < 0: // testing for overflow scenarios
          x = x * x * x
          // we want the same behavior as x < 0
          // Note: In Go, fallthrough transfers control to the
          // next case rather than breaking out of the switch
          fallthrough 
        case x < 0:
          needCert = true
          result = math.Log(float64(-x))
        default:
          x = x * x * x
          result = math.Sqrt(float64(x))
      }

      if needCert {
        cert = askCert(x)
      }

      certs[result] = cert
    }
  }

Now, we have problems: we are processing inputs one by one, we are trying to do all in the same place, processing in batch, and waiting for askCert(x) response before processing another input. In summary, we are not being efficient and not applying clean code good practices.

So, for cleaning this mess, we can take a different approach: graphs.

Let's assume we treat processes as vertices and communications as edges. Each process will perform one of our atomic operations: x³, x < 0, sqrt(x) and log(x), and communication will be done via channels.

To implement this, let's create each function assuming that it will run indefinitely (as nodes). Then, we pass them the input and output channels (edges). The clearest approach to declaring edges is to first define an adjacency matrix, then specify the corresponding channel types, and finally, assign edge weights (e.g., using buffer sizes in Go). Of course, doing this way is not strictly necessary; in the example of the full implementation below I'm declaring each channel manually, expecting to be clearer in the intentions:

Playground code implementation

But, why would we want to create this mess? Two main factors: control and performance. That is because our example is just a base to start thinking. Processes are as flexible as we can imagine. One of the most important scenarios to apply is when you have a lot of I/O operations; you can use a vertex process to start background calls to your I/O operation and send its response to some other vertex where you know it will be used. That would reduce the awaiting time without compromising the remote resource, by avoiding an overload of calls (an abstraction of "just in time" inventory system).

In Cloud(x) we applied this approach to enhance our customer's data processing—achieving a 16x improvement in combined time efficiency and resource utilization.

Code as Graph

Another benefit is that it aids in the study and maintenance of software. You can apply graph theory to understand your codebase and even predict its behavior before writing any code.

Studying code by itself is something that, as programmers, we usually don't do. But we should. That topic has been studied by German Cárdenas in his publication "Evaluating the Graph-based Visualization Technique: A Controlled Experiment".

The application of graphs to study codebases is not a new idea. Back in 2002, Eva Van Emden and Leon Moonen published "Java Quality Assurance by Detecting Code Smells". In that research, they represented "entities" of the software using graphs: packages, classes, methods, etc.

To have graphs at a design stage is relatively common, but how much time do we actually invest in studying and maintaining these graphs? In my experience, almost no one will ever update a graph that was created in the early stages of the project. Plus, the graph will serve merely as a visual reference rather than as an active development tool.

Imagine a fully updated graph representing your RESTful API encompassing functions, calls, and models. We will be able to quickly realize the effort of a change. You can apply Depth First Search or Breadth First Search to find out how many parts of your code will be affected. Then, take your Dominators Tree to evaluate the risks of your plan. And of course, if the graph becomes disconnected (your connectivity is greater than 1), you will quickly notice you have dead code to deal with.

Let's also assign weights to edges to represent the expected execution time of functions. This allows us to estimate an endpoint's response time using Dijkstra's algorithm. We would be able to calculate how many resources we need to serve the expected number of concurrent users, and what parts of our software require more optimizations.

This topic is as extensive as graph theory itself. There is a wealth of studies and documentation available. It is up to you, as a developer, to adopt this knowledge and apply it to your daily work.

Conclusion

As software developers, we know that there are too many tools available. Almost every year, a new technology or update with amazing features is released in the market, and many expect us to remain up-to-date and adopt them as quickly as possible to stay at the forefront of the tech industry. Consequently, we are drifting further away from fundamental principles.

Periodically discussing computer science fundamentals helps us rediscover valuable tools, tricks, and best practices. It reminds us that we should continuously reflect on our implementations, and study their behavior instead of merely reapplying the same formula repeatedly.

This time, graphs have been put into discussion. Their advantages are huge. We should harness their full potential rather than using them merely to structure data. Remember:

Graphs are not data structures.

About Ethics

Christian Herlein — Tue, 18 May 2021 04:57:43 +0000

Without any doubts, I am very under level on this topic. Honesty goes first.

That said... how many times do we stop writting code to reflex on how much impact it will have on the comunity we live into? Let me guess: not many.

The World has moved faster than ever in 2020, and it still does in '21. That global ticket called COVID-19 put all of us hands on work for adapting, even for thoose who were the most anti virtual activists. And those tasks revealed a lot of who we are, how IT people think, work, imagine or even, move.

We are one of the first industries that adopt remote work as usual, many years ago. And we created our tools, our methods, our culture. And we were pointed as the freaks. But now, almost every single industry is working completly or in part as we are used to.

It is then in this cahotic context when we can really have a meassure about how much impact we made into people's life. And it is a bit scary to remember ourselves writting code without cocerns on if it could harm someone, or if we were dealing with some personal data. Or even beyond: how many times did we notice something smelt rare on the definitions we were given?

Tons of times we had to deal with customer's or bosse's intentions we can disagree, but we still have to code. Did we do the enoug to protect everybody's integrity? Or have we protect our own integrity, keeping us as good citizens?

There are two accepted and adopted ethics codes around:
ACM: https://www.acm.org/code-of-ethics
IEEE: https://www.ieee.org/about/corporate/governance/p7-8.html

But still, it looks a really underated topic in our community. I have never had the chance to discuss it in a work environment, for example.

In other to improve our proffesion, my intention and commitment is to put this topic on the table every single time I can. This is my promisse to Touring and Ritchie.

Furthermore, I want to motivate you to be conscious on the impact you are causing with your code... and to raise an alert every time you see something strange behind the scenes.

Thans for the reading, and ethic hacking!

Publics API authenticate

Christian Herlein — Mon, 10 May 2021 12:58:10 +0000

Scenario:

Some time ago, a new project was presented to me. I had to design the solution.

Among other stuff, that I will talk later, one of the challenges was about communicate a set of services that were expose to the public internet. Despite I was not comfortable about that, it was one of the requirements; a custom app had to be able to talk to the API directly, while most of the apps will talk to a specific API (entry point, EP). This EP then will have to talk to other services as well.

Then, the problem was: How do I control that every request between two APIs were actually allowed to ask and read information?

Every auth I had used at that time were in the form of: 1. I were provided a pair of key values to send in headers every time. 2. I had to ask for a new token every time I want to send a message.

But this time I wanted to make something different, and put in practise an advice given to me by an older college: triangles tends to be safe.

The third guy:

To make my triangle, I created a new API that was going to be the source of true for permissions. Lets name it SoT.

Then, the general algorithm was:

Every API will have its own secret key.
SoT will have everybody’s secrets key.
When a request comes from EP, a transaction will be created on SoT.
Every request will be signed by emitter with secret and transaction.
SoT will be the only capable of tell if a signature is right or not.
Every time an API receives a requests, will ask to SoT if request’s signature is valid.

Implementation:

Actually, coding that solution was quite straight forward; I needed two clients components and the SoT controllers:

From EP ask for create and sign a transaction

  transactionId = new uuid()
  sign = new Hash(EP_SECRET_KEY, transactionId)

  // EntryPoint as requester API name for signer field
  ok = sot.create(‘EntryPoint’, transactionId, sign)

Into SoT

 remoteKey = keys.get(input.signer)
 if input.sign == new Has(remoteKey, input.transactionId)
   createTransaction()
 else
   Error(403, ‘Can not create transaction’)

From a requested API (as endpoint middleware)

  if !sot.validate(input.sign, input.transactionId, input.signer)
    Error(403, ‘Invalid signature’)

  continue()

Once a request was authenticated, other internal calls can be authed in the same way.

About the secrets, they should be generated randomly in deploy time. Every time we deploy an API, we renew its secret and let SoT know about the change. They are stored in env vars.
Risks:

Not really found a lot to concern about. As we keep secrets real secrets, we should have no concern. Who want to make unauthorized requests should know the secrets and the hash function implemented.

Sum up:

It’s quite easy to implement triangle authentications by our own with certain security level. What we need to care about is keep keys secrets and don’t expose our hash functions.

Gretings:

Thanks for the read. Any suggestions or comments are appreciated.