This post has been republished via RSS; it originally appeared at: Azure Data Explorer Blog articles.
Introduction: The Seven Bridges of Königsberg
Graph theory is a branch of mathematics that studies the properties of graphs, which are mathematical structures composed of nodes (or vertices) and edges (or links) that connect them. Graphs can be used to model many real-world phenomena, such as social networks, the structure of the internet, the spread of diseases, or the flow of traffic.
Graph theory was started by Leonhard Euler in 1736 when he tried to solve a famous problem, called the Seven Bridges of Königsberg. The problem is based on the city of Königsberg (now Kaliningrad, Russia), which had four areas (two islands and two mainland parts) connected by seven bridges, as shown in the figure below.
The problem is to devise a walk through the city that would cross each of those bridges once and only once. Such a walk is now called an Eulerian path, in honor of Euler. Euler suggested to model the problem as a graph – with areas described as nodes, and bridges as edges between nodes. Euler proved that such a path is impossible for the Königsberg bridges by calculating degree - the total number of edges connected to a node.
Any node with an odd degree has to be a start or an end of the path. For example, for a node with a degree of three, a path can enter it, leave it and then enter it again. The same is correct for any odd number. In the Königsberg graph, all four nodes have odd degrees: three, three, three, and five. This means that there are no possible Eulerian paths, since we would have to start and end at all four nodes, which is impossible for a single path. This is a general criterion: an Eulerian path exists in a graph if and only if the number of nodes with an odd degree is zero or two.
In the following sections we are going to discuss how the bridges problem can be solved empirically using Kusto graph operators - starting with a quick recap of Kusto capabilities.
Exploring graph problems with Kusto graph operators
Kusto is a powerful Engine that enables us to analyze large-scale data. The Kusto Query Language (KQL) also supports graph operators, which allow us to perform complex graph operations on tabular data, such as finding paths, cycles or subgraphs. Graph operators can help us gain insights into the structure and behavior of various kinds of networks, such as web graphs, social networks, network security or connected industrial assets. They are available in every Microsoft offering that provides access to KQL.
- Fabric Real-Time Analytics (KQL Databases)
- Azure Data Explorer
- Free cluster
- Azure Monitor
- Microsoft Sentinel
One of the graph operators in Kusto is graph-match, which allows us to find patterns in a graph based on a specified pattern expression. For example, we can use graph-match to find all the paths of a certain length between two nodes, or all the cycles that include a certain edge. Graph-match also supports various parameters that control how the patterns are matched, such as the direction of the edges, the uniqueness of the nodes and edges, and the maximum number of hops.
We can use Kusto graph operators to validate Euler's solution to the Königsberg problem empirically using different parameters. To do so, we first need to create two tables: one for the nodes and one for the edges of the graph. The nodes table contains the name and the type of each node (mainland or island), while the edges table contains the source, the target, the name, and the type of each edge (bridge). Here is an example using a datatable operator in KQL:
Next, we can use the make-graph operator to create a graph object from the tables, using the nodeName column as the node identifier and the source and target columns as the edge endpoints. The execution creates a graph object:
Now we can use the graph-match operator to find different patterns in the graph, such as paths and cycles. The graph-match operator takes a graph object and a pattern expression as inputs and returns a tabular expression matches. The pattern expression consists of node and edge variables, connected by edge operators (--, ->, or <-). For example, the pattern expression (s)-[e]->(t) represents a directed edge from node s to node t, with edge e. The pattern expression (s)-[e]-(t) represents an undirected edge between node s and node t, with edge e. The pattern expression (s)-[e*1..8]-(t) represents a path of length 1 to 8 between node s and node t, with edge e as a wildcard. We chose the names s, e and t to represent source, edge and target respectively, but any variable names can be used.
The graph-match operator also supports a parameter to handle cycles. The possible values are:
- unique_edges (default): allows repeated visits to nodes, but not repeated visits to edges. This is equivalent to finding Eulerian paths or cycles in the graph.
- none: does not allow any repetitions of nodes or edges. This is equivalent to finding simple paths in the graph.
- all: allows any repetitions of nodes and edges. This is equivalent to finding all possible paths or cycles in the graph.
We can use different combinations of pattern expressions and parameters to explore the Königsberg graph and see how they affect the number and length of the matches. For example:
Here are some examples of using the graph-match operator with different parameter values, along with the number of paths, the maximum number of used edges, and a brief description of the results:
|
Graph-match pattern |
Number of paths |
Max number of edges |
Description |
|
| graph-match (s)-[e]->(t) |
7 |
1 |
This recreates the edges table, since each bridge is travelled in the direction provided in edges table, and we limit the paths to one hop. |
|
| graph-match (s)-[e]-(t) |
14 |
1 |
Each bridge can be travelled in any direction, so it appears twice (as a->b and b->a). |
|
| graph-match cycles = none (s)-[e*1..8]-(t) |
76 |
3 |
In this case, no repetitions are possible (neither edges nor nodes). The result is a list all the options to visit any area not more than once using any connecting bridge not more than once. |
|
| graph-match (s)-[e*1..8]-(t)
or
| graph-match cycles = unique_edges (s)-[e*1..8]-(t) |
820 |
6 |
The default parameter value is cycles = unique_edges, in which case repeated visits to nodes are allowed, but not repeated visits to edges. This recreates the conditions of the problem: we can use each bridge only once. Since maximum number of edges is 6, we can see that we can’t get to all the 7 bridges in this way. This validates the proposed solution. |
|
| graph-match cycles = all (s)-[e*1..8]-(t) |
163792 |
8 |
This allows to repeat usage of both nodes and edges, thus listing all possible combinations of paths, including cycles of different lengths. |
As you can see, even small data can generate complex patterns and huge number of paths. Using Kusto graph semantics you can easily model and explore such patterns to gain insights from your data.
The Kusto Detective Agency is a great way to experience the usefulness of Kusto Graph Semantics. Help rescuing Prof. Smoke using the power of graphs.