How to Represent Single-Variable Functions Using Functional Graphs
Algorithmically Speaking - #16: Theory and applications of functional graphs.
Hello there!
Welcome to Algorithmically Speaking, where we discuss topics on the intersection of Computer Science, Software Engineering, and life.
This post is taken directly from my upcoming book, The Competitive Programmer Graphs Handbook, a graph theory book focusing on three main topics: bipartite graphs, functional graphs, and Euler paths. You can read all the details here:
You can play a crucial role in bringing this book to life by preordering your digital, DRM-free copy. By doing so, you'll receive early and frequent updates, including all future editions.
This chapter will be dedicated to working with a particular type of graph, known as functional graphs or successor graphs.
After providing all the necessary definitions and showing some specific characteristics that hold in this type of graph, the chapter continues by presenting examples of problems where it will be necessary to recognize and apply some recurring ideas when dealing with these specific graphs. Tasks involving cycle detection or finding the k-th successor in a functional graph will be covered in the proposed problems.
This is the agenda for today:
Basic Definitions 🎯 — basic definitions of functional graphs.
Main Algorithms 🌸 — how to find cycles and the kth successor of a vertex in functional graphs.
Context 📝 — examples of these graphs in common life and competitive programming scenarios.
Before we begin, if you think you need a refresher on the basics of graph theory to take the most out of today’s discussion, please look at the previous articles of this series:
01 - Mathematical Induction Applied to Graphs
02 - Paths, Connectivity, and Trees
Let’s get started!
Basic Definitions 🎯
Within directed graphs, a particular type has the following characteristic: the outdegree of each node is equal to 1. That is, each vertex has a unique successor. These graphs are usually called functional graphs or successor graphs.
A functional graph is a directed graph where each vertex has only one outgoing edge.
These graphs have several notable characteristics. The first is that if G is a functional graph, then let C be a connected component of the underlying graph of G. It holds that |VC| = |EC|. That is, the number of edges in this connected component equals the number of vertices in it.
This fact is not very surprising since, by definition, each vertex has only one outgoing edge. However, it will be handy when proving the following:
Proposition 1. Let G =< V, E > be a connected, undirected graph such that |VG| = |EG|. Then G has exactly one cycle.
Proof. According to what was seen here, the following definitions are equivalent:
G is a tree. (1)
G is an acyclic and connected graph. (2)
G is a connected graph, and |EG| = |VG| − 1. (3)
G has no cycles, but if an edge is added between two non-adjacent vertices, exactly one cycle is created. (4)
The graph G has at least one cycle. If it had no cycles, it would be a tree according to the second definition (acyclic and connected), and by the third definition, it would hold that |VG| = |EG| − 1, which contradicts the fact that |VG| = |EG|.
If T is the spanning subgraph of G created when an edge belonging to a cycle of G is removed. By the third definition, T is a tree. Therefore, G has exactly one cycle according to the fourth definition. ∎
Let H be the subgraph of G induced by the vertices of C. Then, H has only one cycle. This cycle is the same as C, with the edges directed according to the constraints of G.
The vertices that belong to the cycle in H are reachable from all the vertices in H since they are in the same connected component, each with exactly one outgoing edge. This means that for every vertex v, after |VH| steps, it is guaranteed to enter a cycle. Since there is only one cycle, v reaches all the vertices of the cycle.
The above indicates that functional graphs are, essentially, a set of subgraphs consisting of a directed cycle and several paths that converge into the cycle.
Main Algorithms 🌸
The problem of the K-th successor ⏩
Among the most valuable operations that can be performed on these graphs is finding, for a vertex u, what its k-th successor is. In other words, which node is reached if starting from u and traversing k edges.
The simplest solution to this problem has a time complexity of O(k). Start at u and traverse one edge at a time. The vertex reached after traversing k edges will be the k-th successor of u. However, the fact that each node has only one outgoing edge allows for using an idea that will improve the computational cost of this algorithm.
The technique that will be shown next is known as binary lifting and is widely used when the problem has a structure similar to functional graphs. For example, it can also be applied in trees, where each vertex has a unique parent.
Let there be a function F(x, k), which returns the k-th successor of node x. The idea is to precompute the values of F(x, k) for k that are powers of two. This can be computed efficiently for each node using the following recurrence:
The idea behind this precomputation is that every path of length k, a power of two, can be divided into two paths of length k/2. These values can be calculated in O(n log K), where K is the length of the largest successor we want to find because we are calculating O(log K) values for each vertex.
After this precomputation, any query of the form F(x, k) can be performed in O(log k) by representing k as a sum of powers of two. For example, to calculate F(x, 11), we use the formula:
In this way, finding any successor of a given vertex in logarithmic time is possible after a relatively inexpensive precomputation. This represents a considerable improvement over the naive O(k) algorithm.
Detection of Cycles 🔄
Keep reading with a 7-day free trial
Subscribe to Algorithmically Speaking to keep reading this post and get 7 days of free access to the full post archives.