topic
digraph (digraphs)
A digraph, short for directed graph, is a data structure composed of a finite set of vertices connected by directed edges, commonly referred to as arcs. Unlike standard undirected graphs where connections are symmetric, each edge in a digraph has a designated orientation pointing from a source vertex to a target vertex, representing a one-way relationship. Every vertex is characterized by an indegree, which counts incoming edges, and an outdegree, which counts outgoing edges. Typically implemented using adjacency lists or adjacency matrices, digraphs are widely applied in computer science to model asymmetric systems, task scheduling dependencies, program control flow, web link navigation, and state transitions in finite automata.
3 items
Transformers Meet Directed Graphs
Simon Geisler, Yujia Li, Daniel J. Mankowitz, Ali Taylan Cemgil, Stephan Günnemann, Cosmin Paduraru
Why you should read this
Develops direction-aware positional encodings using Magnetic Laplacian eigenvectors and directional random walks to extend Transformers to directed graphs, significantly improving performance on source code understanding and sorting network verification.
Transformers were originally proposed as a sequence-to-sequence model for text but have become vital for a wide range of modalities, including images, audio, video, and undirected graphs. However, transformers for directed graphs are a surprisingly underexplored topic, despite their applicability to ubiquitous domains, including source code and logic circuits. In this work, we propose two direction- and structure-aware positional encodings for directed graphs: (1) the eigenvectors of the Magnetic Laplacian – a direction-aware generalization of the combinatorial Laplacian; (2) directional random walk encodings. Empirically, we show that the extra directionality information is useful in various downstream tasks, including correctness testing of sorting networks and source code understanding. Together with a data-flow-centric graph construction, our model outperforms the prior state of the art on the Open Graph Benchmark Code2 relatively by 14.7%.
Added
2026-10-03
An introduction to graph theory
Darij Grinberg
Why you should read this
Provides a rigorous graduate-level introduction to graph theory by combining algebraic perspectives, structural theorems, and numerous practice exercises.
This is a graduate-level introduction to graph theory, corresponding to a quarter-long course. It covers simple graphs, multigraphs as well as their directed analogues, and more restrictive classes such as tournaments, trees and arborescences. Among the features discussed are Eulerian circuits, Hamiltonian cycles, spanning trees, the matrix-tree and BEST theorems, proper colorings, Turan's theorem, bipartite matching and the Menger and Gallai--Milgram theorems. The basics of network flows are introduced in order to prove Hall's marriage theorem. Around a hundred exercises are included (without solutions).
Added
2026-08-20
Mathematics for Computer Science
Eric Lehman, F Thomson Leighton, Albert R Meyer
Why you should read this
Provides foundational mathematical tools and logical reasoning skills necessary for solving complex problems in computer science.
This book provides a comprehensive introduction to mathematics for computer science, covering fundamental topics such as proofs, the well-ordering principle, logical formulas, and mathematical data types including sets, sequences, functions, and binary relations.
Added
2026-08-18
