Graph

Note The Approximate Densest Subgraph problem involves finding a subgraph of a given graph that has the highest density, where density is typically defined as the number of edges divided by the number of vertices in the subgraph. Finding the exact densest subgraph is computationally expensive, so approximate solutions are often sought. Here’s a high-level outline of how an approximate algorithm for this problem might be implemented: Initialization: Start with all vertices of the graph and no edges....

Note An independent set in a graph is a set of vertices, no two of which are adjacent. A maximal independent set is an independent set that is not a subset of any other independent set in the graph. Here’s a basic approach to find a Maximal Independent Set: Start with an empty set S. Iterate over all vertices of the graph. For each vertex: If the vertex and its neighbors are not in S, add the vertex to S....

Note The Matching algorithm is a graph algorithm that finds a matching in a graph, where a matching is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. A Maximal matching is a matching that cannot have any more edges added to it without violating the matching property. A maximum matching is a matching that contains the largest possible number of edges....

Note Graph coloring is a way of assigning colors to the vertices of a graph so that no two adjacent vertices share the same color. This is a classical problem in the field of graph theory and has applications in various domains like scheduling, map coloring, and solving Sudoku puzzles. The simplest form of graph coloring is vertex coloring, where the aim is to minimize the number of colors used. This problem is NP-hard, meaning there is no known algorithm that can solve all instances of the problem efficiently (in polynomial time)....

Note Biconnectivity in graphs is an important concept used to identify biconnected components (BCCs). A graph is biconnected if it is connected and does not have any articulation points, meaning removing any single vertex will not disconnect the graph. The biconnected components of a graph are maximal biconnected subgraphs. Strict Definition: A BCC should contain at least three vertices in a cycle, ensuring that the removal of any single vertex does not disconnect the component....

Note The Low-Diameter Decomposition (LDD) algorithm is a graph partitioning algorithm that decomposes a graph into several connected subgraphs (or components) such that each subgraph has a low diameter. The diameter of a subgraph is defined as the maximum shortest path distance between any two nodes within the subgraph. The LDD algorithm works as follows: Start with an empty decomposition and an empty queue. Pick an unvisited node u and create a new set containing only u....

Description Strongly Connected Components operates the directed graph in which there is a directed path from each vertex to every other vertex. Weakly Connected Component (the one we discussed before) ignores the direction of the edges. WCC is commonly considered the “default” CC algorithm, if there isn’t a specification for Strongly or Weakly. Kosaraju’s Algorithm: Run 1st DFS to get finishing times of each vertex (i.e., postordering of DFS). [Backtracking] Run 2nd DFS on the transposed graph, starting with the visited vertices in Reverse Post-Order Each DFS tree in step 2 is an SCC....

Description A Minimum Spanning Tree (MST) of a weighted, connected, undirected graph is a tree that spans all the vertices in the graph and has the minimum possible total edge weight among all the trees that can be created from the graph. In simpler terms, it’s a subgraph that includes all the vertices, is a tree (meaning it has no cycles), and the sum of its edge weights is as small as possible....

count how many triangles can be formed inside the graph undirected graph, and each triangle would be counted for three times, once per node. $O(n^3)$ #include <iostream> #include <vector> // Reference: https://github.com/georgegito/vertexwise-triangle-counting/blob/master/src/v3/v3_seq.cpp // allow for parallelism auto bfs_tc(const std::vector<int>& rowPtr, const std::vector<int>& colIdx) { int numTriangles = 0; const auto numVertices = rowPtr.size() - 1; // check if two nodes have an edge between them with binary search (require sorted colIdx) auto intersect = [&](int first, int second) -> bool { // std::find is O(N), assuming the iterator is a forward iterator // auto first_begin = colIdx....

The betweenness centrality for each vertex is the number of these shortest paths that pass through the vertex. perform BFS (or SSSP if weighted graphs) for each vertex keep a stack of path for backtracking, i.e., traversing the graph in reverse BFS order #include <iostream> #include <queue> #include <stack> #include <vector> auto brandes(const std::vector<int>& rowPtr, const std::vector<int>& colIdx) { const auto numVertices = rowPtr.size() - 1; std::vector<float> betweenness(numVertices, 0.0f); //For each vertex s, perform a BFS to establish levels and predecessors //!...