This article is the second in a series of short pieces introducing the Katana Graph Python Library for Graph Analytics. We will focus on single-source shortest path and connected components graph analytics algorithms in the library.
Single-source shortest path
Single-source shortest path (SSSP) is similar to breadth-first search, which we covered in part one of this series, but when calculating distances from a given node to all the others in a graph, SSSP takes values assigned to each edge, known as edge weights, into account. Edge weights are positive values that can represent distance, cost, or any other quantity that you wish to minimize as it accumulates along the path. This algorithm returns, for each node, its distance from the source node in which the paths are the least expensive routes between the corresponding nodes in the original graph. This is useful for route mapping, network routing, and logistics research.
There are a number of single-source shortest path algorithms, including Bellman-Ford and Dijkstra’s, that are useful in different applications or with different types of graphs. The Bellman-Ford algorithm has a greater time complexity than Dijkstra’s and is useful for small- and medium-sized graphs and is able to detect negative cycles. Dijkstra’s algorithm, on the other hand, has a logarithmic time complexity which is efficient for large/medium graphs, but it cannot detect negative cycles.
Connected components
“Connected components” describes groups of nodes within the graph that are connected internally. Bridges (or cut edges, cut points) and articulation points are edges and nodes that serve as a single point of connection between components. The removal of a bridge (edge) or articulation point (node) would increase the number of connected components. For example, if you have two groups of nodes connected by a single edge, that edge is the bridge, and removing it would result in two independent groups of nodes.
Identifying the number of components in a graph is critical for understanding its structure. For example, looking at a map of states, roads, and prominent cities would show that while there may be several roads between cities, it is primarily major roadways connecting states to one another. Viewing data in this way also displays unlikely cut points, such as a small country road on the outskirts that allows travel between two small towns while incidentally connecting two states. This algorithm has been useful for very large-scale integration (VLSI) and other electronic circuit work.
To learn more about how the Katana Graph Intelligence Platform is used to solve problems, speak to a Katana Graph Intelligence Platform expert.
Get to Know Katana Graph
We thrive on testing new and diverse ideas.
Katana Graph was born of cutting-edge research and scientific rigor, and these beginnings have a powerful effect on who we are to this day. We’re devoted to problem solving, and are relentless in our pursuit of more effective and more efficient solutions to real-world challenges. Continuous improvement is the very foundation of our success.
