#include <graphs.hpp>

Public Member Functions
	Graph (int v)
	Constructor for the Graph class. More...

void	add_edge (int v, int w, int weight)
	Adds an edge between two vertices with a specified weight. More...

void	dfs (int start)
	Performs Depth-First Search (DFS) traversal starting from a given vertex. More...

void	dfs_rec (int v, std::vector< bool > &visited)
	Helper function for recursive Depth-First Search (DFS) traversal. More...

void	bfs (int start)
	Performs Breadth-First Search (BFS) traversal starting from a given vertex. More...

void	dijkstra (int start)
	Applies Dijkstra's algorithm to find the single-source shortest paths in the graph. More...

void	bellman_ford (int start)
	Applies Bellman-Ford algorithm to find the single-source shortest paths in the graph, handling negative weights. More...

std::vector< std::pair< int, std::pair< int, int > > >	kruskal ()
	Applies Kruskal's algorithm to find the minimum spanning tree of the graph. More...

void	floyd_warshall ()
	Applies Floyd-Warshall algorithm to find all-pairs shortest paths in the graph. More...

void	topo_sort ()
	Performs topological sorting on a Directed Acyclic Graph (DAG) More...

std::vector< std::vector< int > >	connected_components ()
	Finds connected components in an undirected graph using Depth-First Search (DFS) More...

bool	is_bipartite ()
	Determines if a given graph is bipartite using BFS (Breadth First Search) More...

std::vector< double >	betweenness_centrality ()
	Calculates betweenness centrality for each vertex in the graph. More...

bool	has_hamiltonian_circuit ()
	Checks if the graph contains a Hamiltonian circuit. More...

bool	has_eulerian_path ()
	Checks if the graph contains an Eulerian path. More...

int	eccentricity (int vertex)
	Calculates the eccentricity of a specified vertex in the graph. More...

int	radius ()
	Calculates the radius of the graph. More...

std::vector< int >	greedy_coloring ()
	Performs graph coloring using the greedy algorithm. More...

int	chromatic_number ()
	Calculates the chromatic number of the graph. More...

std::vector< std::pair< int, int > >	match_cardinality ()
	Finds a maximum cardinality matching in the graph using a greedy algorithm. More...

std::vector< std::pair< int, int > >	match_wt ()
	Finds a maximum weight matching in the graph using a greedy algorithm. More...

bool	is_planar ()
	Checks if the graph is planar using Kuratowski's theorem. More...

void	planar_gen (int num_vertices, double radius)
	Generates a random planar graph using the random geometric graph model. More...

bool	has_k5 ()
	Checks if the graph contains a subgraph that is a subdivision of K5. More...

bool	has_k33 ()
	Checks if the graph contains a subgraph that is a subdivision of K3,3. More...

bool	is_k33 (const std::set< int > &k_vertices)
	Checks if a set of vertices forms a subgraph that is a subdivision of K3,3. More...

double	euclid_dist (const std::pair< double, double > &point1, const std::pair< double, double > &point2)
	Calculates the Euclidean distance between two 2D points. More...

std::vector< uint64_t >	compress ()
	Compresses the graph using Elias Gamma encoding. More...

void	decompress (const std::vector< uint64_t > &compressed)
	Decompresses a compressed graph using Elias Gamma encoding. More...

Public Attributes
int	vertices

std::vector< std::vector< std::pair< int, int > > >	adj_list

Private Member Functions
void	topo_sort_util (int v, std::vector< bool > &visited, std::stack< int > &topo_stack)
	Helper function for topological sorting. More...

int	find (std::vector< int > &parent, int i)
	Finds the representative element of the set that contains the given element. More...

void	union_sets (std::vector< int > &parent, int x, int y)
	Unions two sets by rank in the disjoint set data structure. More...

void	dfs_connected_components (int v, std::vector< bool > &visited, std::vector< int > &component)
	Performs Depth-First Search (DFS) traversal to find connected components in an undirected graph. More...

int	choose_random_neighbor (int vertex)
	Chooses a random neighbor of a given vertex. More...

bool	hamiltonian_circuit_util (int v, std::vector< bool > &visited, std::vector< int > &path, int count)
	Utility function for finding a Hamiltonian circuit. More...

Private Attributes
std::vector< bool >	is_matched

Detailed Description

Definition at line 49 of file graphs.hpp.

Constructor & Destructor Documentation

◆ Graph()

gpmp::Graph::Graph ( int v )

inline

Constructor for the Graph class.

Parameters

v	Number of vertices in the graph

Definition at line 58 of file graphs.hpp.

58 : vertices(v), adj_list(v) {

59 }

gpmp::Graph::adj_list

std::vector< std::vector< std::pair< int, int > > > adj_list

Definition: graphs.hpp:52

gpmp::Graph::vertices

int vertices

Definition: graphs.hpp:51

Member Function Documentation

◆ add_edge()

void gpmp::Graph::add_edge	(	int	v,
		int	w,
		int	weight
	)

Adds an edge between two vertices with a specified weight.

Parameters

v	The first vertex
w	The second vertex
weight	The weight of the edge

Definition at line 44 of file graphs.cpp.

                                                  {
     adj_list[v].emplace_back(w, weight);
     adj_list[w].emplace_back(v, weight); // uncomment for undirected graph
 }

References adj_list.

Referenced by main().

◆ bellman_ford()

void gpmp::Graph::bellman_ford ( int start )

Applies Bellman-Ford algorithm to find the single-source shortest paths in the graph, handling negative weights.

Parameters

start The starting vertex for Bellman-Ford algorithm

Definition at line 116 of file graphs.cpp.

                                       {
     std::vector<int> dist(vertices, std::numeric_limits<int>::max());
     dist[start] = 0;
  
     for (int i = 0; i < vertices - 1; ++i) {
         for (int u = 0; u < vertices; ++u) {
             for (const auto &neighbor : adj_list[u]) {
                 int v = neighbor.first;
                 int weight = neighbor.second;
  
                 if (dist[u] != std::numeric_limits<int>::max() &&
                     dist[u] + weight < dist[v]) {
                     dist[v] = dist[u] + weight;
                 }
             }
         }
     }
  
     std::cout << "Bellman-Ford Shortest Paths from vertex " << start << ":\n";
     for (int i = 0; i < vertices; ++i)
         std::cout << "Vertex " << i << ": " << dist[i] << "\n";
 }

References u.

Referenced by main().

◆ betweenness_centrality()

std::vector< double > gpmp::Graph::betweenness_centrality ( )

Calculates betweenness centrality for each vertex in the graph.

Returns: Vector of doubles representing the betweenness centrality of each vertex

Definition at line 298 of file graphs.cpp.

                                                     {
     std::vector<double> centrality(vertices, 0.0);
  
     for (int s = 0; s < vertices; ++s) {
         std::vector<int> predecessors(vertices, -1);
         std::vector<int> distance(vertices, -1);
         std::vector<int> num_shortest_paths(vertices, 0);
         std::stack<int> stack;
         std::queue<int> bfs_queue;
  
         distance[s] = 0;
         num_shortest_paths[s] = 1;
         bfs_queue.push(s);
  
         while (!bfs_queue.empty()) {
             int v = bfs_queue.front();
             bfs_queue.pop();
             stack.push(v);
  
             for (const auto &neighbor : adj_list[v]) {
                 int w = neighbor.first;
                 if (distance[w] == -1) {
                     distance[w] = distance[v] + 1;
                     bfs_queue.push(w);
                 }
  
                 if (distance[w] == distance[v] + 1) {
                     num_shortest_paths[w] += num_shortest_paths[v];
                     predecessors[w] = v;
                 }
             }
         }
  
         std::vector<double> dependency(vertices, 0.0);
  
         while (!stack.empty()) {
             int w = stack.top();
             stack.pop();
  
             for (const auto &predecessor : adj_list[w]) {
                 int v = predecessor.first;
                 dependency[v] += (static_cast<double>(num_shortest_paths[v]) /
                                   num_shortest_paths[w]) *
                                  (1 + dependency[w]);
             }
  
             if (w != s) {
                 centrality[w] += dependency[w];
             }
         }
     }
  
     return centrality;
 }

◆ bfs()

void gpmp::Graph::bfs ( int start )

Performs Breadth-First Search (BFS) traversal starting from a given vertex.

Parameters

start The starting vertex for BFS traversal

Definition at line 65 of file graphs.cpp.

                              {
     std::vector<bool> visited(vertices, false);
     std::queue<int> bfs_queue;
  
     visited[start] = true;
     bfs_queue.push(start);
  
     while (!bfs_queue.empty()) {
         int v = bfs_queue.front();
         bfs_queue.pop();
         std::cout << v << " ";
  
         for (const auto &neighbor : adj_list[v]) {
             if (!visited[neighbor.first]) {
                 visited[neighbor.first] = true;
                 bfs_queue.push(neighbor.first);
             }
         }
     }
 }

Referenced by main().

◆ choose_random_neighbor()

int gpmp::Graph::choose_random_neighbor ( int vertex )

private

Chooses a random neighbor of a given vertex.

Parameters

vertex The vertex for which a random neighbor is chosen

Returns: The index of the randomly chosen neighbor in the adjacency list

◆ chromatic_number()

int gpmp::Graph::chromatic_number ( )

Calculates the chromatic number of the graph.

Returns: The chromatic number of the graph

Definition at line 467 of file graphs.cpp.

                                 {
     std::vector<int> result(vertices, -1);
  
     // assign the first color to the first vertex
     result[0] = 0;
  
     // initialize available colors. For each vertex, remove colors used by its
     // neighbors.
     std::vector<bool> available(vertices, false);
     for (const auto &neighbor : adj_list[0]) {
         int v = neighbor.first;
         if (result[v] != -1) {
             available[result[v]] = true;
         }
     }
  
     // assign colors to the remaining vertices
     for (int v = 1; v < vertices; ++v) {
         for (int c = 0; c < vertices; ++c) {
             if (!available[c]) {
                 result[v] = c;
                 break;
             }
         }
  
         // reset available colors for the next vertex
         std::fill(available.begin(), available.end(), false);
  
         // update available colors for neighbors
         for (const auto &neighbor : adj_list[v]) {
             int u = neighbor.first;
             if (result[u] != -1) {
                 available[result[u]] = true;
             }
         }
     }
  
     // find the maximum color assigned, which represents the chromatic number
     int chrom_num = *std::max_element(result.begin(), result.end()) + 1;
  
     return chrom_num;
 }

References u.

◆ compress()

std::vector< uint64_t > gpmp::Graph::compress ( )

Compresses the graph using Elias Gamma encoding.

Returns: Vector of uint64_t representing the compressed graph

Definition at line 693 of file graphs.cpp.

                                         {
     std::vector<uint64_t> compressed;
     compressed.push_back(vertices);
  
     for (int v = 0; v < vertices; ++v) {
         // encode the number of neighbors using Elias Gamma encoding
         std::bitset<64> binary_representation(adj_list[v].size() + 1);
         int length = log2(adj_list[v].size() + 1) + 1;
  
         // store the length of the encoded number
         compressed.push_back(length);
  
         // store the encoded number
         compressed.push_back(
             std::stoull(binary_representation.to_string(), 0, 2));
  
         // store the neighbors
         for (const auto &neighbor : adj_list[v]) {
             compressed.push_back(neighbor.first);
         }
     }
  
     return compressed;
 }

◆ connected_components()

std::vector< std::vector< int > > gpmp::Graph::connected_components ( )

Finds connected components in an undirected graph using Depth-First Search (DFS)

Returns: Vector of vectors representing the connected components

Definition at line 254 of file graphs.cpp.

                                                           {
     std::vector<std::vector<int>> components;
     std::vector<bool> visited(vertices, false);
  
     for (int v = 0; v < vertices; ++v) {
         if (!visited[v]) {
             std::vector<int> component;
             dfs_connected_components(v, visited, component);
             components.push_back(component);
         }
     }
  
     return components;
 }

◆ decompress()

void gpmp::Graph::decompress ( const std::vector< uint64_t > & compressed )

Decompresses a compressed graph using Elias Gamma encoding.

Parameters

compressed Vector of uint64_t representing the compressed graph

Definition at line 719 of file graphs.cpp.

                                                                 {
     int index = 0;
     vertices = compressed[index++];
  
     adj_list.resize(vertices);
  
     for (int v = 0; v < vertices; ++v) {
         int length = compressed[index++];
         uint64_t encoded_neighbors = compressed[index++];
         std::bitset<64> binary_representation(encoded_neighbors);
  
         // decode the number of neighbors
         int num_neighbors =
             std::stoi(binary_representation.to_string().substr(64 - length),
                       nullptr,
                       2) -
             1;
  
         // decode and add neighbors
         for (int i = 0; i < num_neighbors; ++i) {
             adj_list[v].emplace_back(compressed[index++],
                                      0); // TODO assuming unweighted graph
         }
     }
 }

◆ dfs()

void gpmp::Graph::dfs ( int start )

Performs Depth-First Search (DFS) traversal starting from a given vertex.

Parameters

start The starting vertex for DFS traversal

Definition at line 49 of file graphs.cpp.

                              {
     std::vector<bool> visited(vertices, false);
     dfs_rec(start, visited);
 }

Referenced by main().

◆ dfs_connected_components()

void gpmp::Graph::dfs_connected_components	(	int	v,
		std::vector< bool > &	visited,
		std::vector< int > &	component
	)

private

Performs Depth-First Search (DFS) traversal to find connected components in an undirected graph.

This method is a helper function used by the connected_components method

Parameters

v	The current vertex during DFS traversal
visited	A vector indicating whether each vertex has been visited
component	The connected component being formed during the traversal

Definition at line 353 of file graphs.cpp.

                                                                       {
     visited[v] = true;
     component.push_back(v);
  
     for (const auto &neighbor : adj_list[v]) {
         int u = neighbor.first;
         if (!visited[u]) {
             dfs_connected_components(u, visited, component);
         }
     }
 }

References u.

◆ dfs_rec()

void gpmp::Graph::dfs_rec	(	int	v,
		std::vector< bool > &	visited
	)

Helper function for recursive Depth-First Search (DFS) traversal.

Parameters

v	The current vertex
visited	A vector indicating whether each vertex has been visited

Definition at line 54 of file graphs.cpp.

                                                        {
     visited[v] = true;
     std::cout << v << " ";
  
     for (const auto &neighbor : adj_list[v]) {
         if (!visited[neighbor.first]) {
             dfs_rec(neighbor.first, visited);
         }
     }
 }

◆ dijkstra()

void gpmp::Graph::dijkstra ( int start )

Applies Dijkstra's algorithm to find the single-source shortest paths in the graph.

Parameters

start The starting vertex for Dijkstra's algorithm

Definition at line 86 of file graphs.cpp.

                                   {
     std::priority_queue<std::pair<int, int>,
                         std::vector<std::pair<int, int>>,
                         std::greater<std::pair<int, int>>>
         pq;
     std::vector<int> dist(vertices, std::numeric_limits<int>::max());
  
     dist[start] = 0;
     pq.push({0, start});
  
     while (!pq.empty()) {
         int u = pq.top().second;
         pq.pop();
  
         for (const auto &neighbor : adj_list[u]) {
             int v = neighbor.first;
             int weight = neighbor.second;
  
             if (dist[u] + weight < dist[v]) {
                 dist[v] = dist[u] + weight;
                 pq.push({dist[v], v});
             }
         }
     }
  
     std::cout << "Dijkstra's Shortest Paths from vertex " << start << ":\n";
     for (int i = 0; i < vertices; ++i)
         std::cout << "Vertex " << i << ": " << dist[i] << "\n";
 }

References u.

Referenced by main().

◆ eccentricity()

int gpmp::Graph::eccentricity ( int vertex )

Calculates the eccentricity of a specified vertex in the graph.

Parameters

vertex The vertex for which eccentricity is calculated

Returns: The eccentricity of the specified vertex

Definition at line 431 of file graphs.cpp.

                                       {
     std::vector<int> distance(vertices, std::numeric_limits<int>::max());
     distance[vertex] = 0;
  
     std::queue<int> bfs_queue;
     bfs_queue.push(vertex);
  
     while (!bfs_queue.empty()) {
         int v = bfs_queue.front();
         bfs_queue.pop();
  
         for (const auto &neighbor : adj_list[v]) {
             int u = neighbor.first;
             if (distance[u] == std::numeric_limits<int>::max()) {
                 distance[u] = distance[v] + 1;
                 bfs_queue.push(u);
             }
         }
     }
  
     // the eccentricity is the maximum distance from the given vertex
     return *std::max_element(distance.begin(), distance.end());
 }

References u.

◆ euclid_dist()

double gpmp::Graph::euclid_dist	(	const std::pair< double, double > &	point1,
		const std::pair< double, double > &	point2
	)

Calculates the Euclidean distance between two 2D points.

Parameters

point1	The first 2D point
point2	The second 2D point

Returns: The Euclidean distance between the two points

Definition at line 686 of file graphs.cpp.

                                                                        {
     double dx = point1.first - point2.first;
     double dy = point1.second - point2.second;
     return std::sqrt(dx * dx + dy * dy);
 }

◆ find()

int gpmp::Graph::find	(	std::vector< int > &	parent,
		int	i
	)

private

Finds the representative element of the set that contains the given element.

Parameters

parent	The parent vector representing disjoint sets
i	The element to find

Returns: The representative element of the set containing 'i'

Definition at line 242 of file graphs.cpp.

                                                  {
     if (parent[i] == -1)
         return i;
     return find(parent, parent[i]);
 }

◆ floyd_warshall()

void gpmp::Graph::floyd_warshall ( )

Applies Floyd-Warshall algorithm to find all-pairs shortest paths in the graph.

Definition at line 170 of file graphs.cpp.

                                {
     std::vector<std::vector<int>> dist(
         vertices,
         std::vector<int>(vertices, std::numeric_limits<int>::max()));
  
     for (int i = 0; i < vertices; ++i) {
         dist[i][i] = 0;
         for (const auto &neighbor : adj_list[i]) {
             int v = neighbor.first;
             int weight = neighbor.second;
             dist[i][v] = weight;
         }
     }
  
     for (int k = 0; k < vertices; ++k) {
         for (int i = 0; i < vertices; ++i) {
             for (int j = 0; j < vertices; ++j) {
                 if (dist[i][k] != std::numeric_limits<int>::max() &&
                     dist[k][j] != std::numeric_limits<int>::max() &&
                     dist[i][k] + dist[k][j] < dist[i][j]) {
                     dist[i][j] = dist[i][k] + dist[k][j];
                 }
             }
         }
     }
  
     std::cout << "Floyd-Warshall Shortest Paths:\n";
     for (int i = 0; i < vertices; ++i) {
         for (int j = 0; j < vertices; ++j) {
             std::cout << "From " << i << " to " << j << ": ";
             if (dist[i][j] == std::numeric_limits<int>::max())
                 std::cout << "INF";
             else
                 std::cout << dist[i][j];
             std::cout << "\n";
         }
     }
 }

Referenced by main().

◆ greedy_coloring()

std::vector< int > gpmp::Graph::greedy_coloring ( )

Performs graph coloring using the greedy algorithm.

Returns: Vector of integers representing the color assigned to each vertex

Definition at line 511 of file graphs.cpp.

                                           {
     std::vector<int> result(vertices, -1);
  
     // assign colors to vertices
     for (int v = 0; v < vertices; ++v) {
         std::vector<bool> available(vertices, false);
         for (const auto &neighbor : adj_list[v]) {
             int u = neighbor.first;
             if (result[u] != -1) {
                 available[result[u]] = true;
             }
         }
  
         for (int c = 0; c < vertices; ++c) {
             if (!available[c]) {
                 result[v] = c;
                 break;
             }
         }
     }
  
     return result;
 }

References u.

◆ hamiltonian_circuit_util()

bool gpmp::Graph::hamiltonian_circuit_util	(	int	v,
		std::vector< bool > &	visited,
		std::vector< int > &	path,
		int	count
	)

private

Utility function for finding a Hamiltonian circuit.

Parameters

v	The current vertex in the exploration
visited	Vector indicating whether each vertex has been visited
path	Vector representing the current path in the exploration
count	The count of vertices visited so far

Returns: True if a Hamiltonian circuit is found, false otherwise

Definition at line 395 of file graphs.cpp.

                                                       {
     visited[v] = true;
     path.push_back(v);
  
     if (count == vertices) {
         // all vertices are visited; check if there is an edge from the last
         // added vertex to the starting vertex
         for (const auto &neighbor : adj_list[v]) {
             if (neighbor.first == path[0]) {
                 return true; // Hamiltonian circuit found
             }
         }
     } else {
         // recursive step to try all vertices as the next one in the Hamiltonian
         // circuit
         for (const auto &neighbor : adj_list[v]) {
             if (!visited[neighbor.first]) {
                 if (hamiltonian_circuit_util(neighbor.first,
                                              visited,
                                              path,
                                              count + 1)) {
                     return true;
                 }
             }
         }
     }
  
     // backtrack
     visited[v] = false;
     path.pop_back();
     return false;
 }

◆ has_eulerian_path()

bool gpmp::Graph::has_eulerian_path ( )

Checks if the graph contains an Eulerian path.

Returns: True if the graph contains an Eulerian path, false otherwise

Definition at line 381 of file graphs.cpp.

                                   {
     // A connected graph has an Eulerian path if and only if it has exactly 0 or
     // 2 vertices with an odd degree.
     int odd_degrees = 0;
  
     for (int v = 0; v < vertices; ++v) {
         if (adj_list[v].size() % 2 != 0) {
             ++odd_degrees;
         }
     }
  
     return odd_degrees == 0 || odd_degrees == 2;
 }

◆ has_hamiltonian_circuit()

bool gpmp::Graph::has_hamiltonian_circuit ( )

Checks if the graph contains a Hamiltonian circuit.

Returns: True if the graph contains a Hamiltonian circuit, false otherwise

Definition at line 367 of file graphs.cpp.

                                         {
     std::vector<int> path;
     std::vector<bool> visited(vertices, false);
  
     for (int v = 0; v < vertices; ++v) {
         path.clear();
         if (hamiltonian_circuit_util(v, visited, path, 1)) {
             return true;
         }
     }
  
     return false;
 }

◆ has_k33()

bool gpmp::Graph::has_k33 ( )

Checks if the graph contains a subgraph that is a subdivision of K3,3.

Returns: True if the graph contains a subgraph that is a subdivision of K3,3, false otherwise

Definition at line 654 of file graphs.cpp.

                         {
     for (int v = 0; v < vertices; ++v) {
         if (adj_list[v].size() >= 3) {
             std::set<int> neighbors;
             for (const auto &neighbor : adj_list[v]) {
                 neighbors.insert(neighbor.first);
             }
  
             if (is_k33(neighbors)) {
                 return true;
             }
         }
     }
  
     return false;
 }

◆ has_k5()

bool gpmp::Graph::has_k5 ( )

Checks if the graph contains a subgraph that is a subdivision of K5.

Returns: True if the graph contains a subgraph that is a subdivision of K5, false otherwise

Definition at line 624 of file graphs.cpp.

                        {
     for (int v = 0; v < vertices; ++v) {
         if (adj_list[v].size() >= 5) {
             std::set<int> neighbors;
             for (const auto &neighbor : adj_list[v]) {
                 neighbors.insert(neighbor.first);
             }
  
             for (const auto &u : neighbors) {
                 std::set<int> common_neighbors;
                 for (const auto &neighbor : adj_list[u]) {
                     if (neighbors.find(neighbor.first) != neighbors.end()) {
                         common_neighbors.insert(neighbor.first);
                     }
                 }
  
                 for (const auto &w : common_neighbors) {
                     if (neighbors.find(w) != neighbors.end()) {
                         return true;
                     }
                 }
             }
         }
     }
  
     return false;
 }

References u.

◆ is_bipartite()

bool gpmp::Graph::is_bipartite ( )

Determines if a given graph is bipartite using BFS (Breadth First Search)

Note: A bipartite graph is a graph where the vertices can be divided into two disjoint sets such that all edges connect a vertex in one set to a vertex in another set

Definition at line 269 of file graphs.cpp.

                              {
     std::vector<int> color(vertices, -1);
     std::queue<int> bfs_queue;
  
     for (int start = 0; start < vertices; ++start) {
         if (color[start] == -1) {
             color[start] = 0;
             bfs_queue.push(start);
  
             while (!bfs_queue.empty()) {
                 int v = bfs_queue.front();
                 bfs_queue.pop();
  
                 for (const auto &neighbor : adj_list[v]) {
                     int u = neighbor.first;
                     if (color[u] == -1) {
                         color[u] = 1 - color[v];
                         bfs_queue.push(u);
                     } else if (color[u] == color[v]) {
                         return false; // Not bipartite
                     }
                 }
             }
         }
     }
  
     return true; // Bipartite
 }

References u.

◆ is_k33()

bool gpmp::Graph::is_k33 ( const std::set< int > & k_vertices )

Checks if a set of vertices forms a subgraph that is a subdivision of K3,3.

Parameters

vertices The set of vertices to be checked

Returns: True if the set of vertices forms a subgraph that is a subdivision of K3,3, false otherwise

Definition at line 672 of file graphs.cpp.

                                                     {
     if (k_vertices.size() == 6) {
         int degree_sum = 0;
         for (int v : k_vertices) {
             degree_sum += adj_list[v].size();
         }
  
         // Cast vertices.size() to int to avoid the comparison warning
         return degree_sum == 2 * static_cast<int>(k_vertices.size());
     }
     return false;
 }

◆ is_planar()

bool gpmp::Graph::is_planar ( )

Checks if the graph is planar using Kuratowski's theorem.

Returns: True if the graph is planar, false otherwise

Definition at line 589 of file graphs.cpp.

                           {
     // planar graphs satisfy Kuratowski's theorem: they do not contain a
     // subgraph that is a subdivision of K5 or K3,3.
     return !has_k5() && !has_k33();
 }

◆ kruskal()

std::vector< std::pair< int, std::pair< int, int > > > gpmp::Graph::kruskal ( )

Applies Kruskal's algorithm to find the minimum spanning tree of the graph.

Returns: Vector of edges forming the minimum spanning tree

Definition at line 139 of file graphs.cpp.

                                                               {
     std::vector<std::pair<int, std::pair<int, int>>> edges;
     for (int u = 0; u < vertices; ++u) {
         for (const auto &neighbor : adj_list[u]) {
             int v = neighbor.first;
             int weight = neighbor.second;
             edges.emplace_back(weight, std::make_pair(u, v));
         }
     }
  
     std::sort(edges.begin(), edges.end());
  
     std::vector<std::pair<int, std::pair<int, int>>> min_span_tree;
     std::vector<int> parent(vertices, -1);
  
     for (const auto &edge : edges) {
         int u = edge.second.first;
         int v = edge.second.second;
  
         int setU = find(parent, u);
         int setV = find(parent, v);
  
         if (setU != setV) {
             min_span_tree.push_back(edge);
             union_sets(parent, setU, setV);
         }
     }
  
     return min_span_tree;
 }

References u.

Referenced by main().

◆ match_cardinality()

std::vector< std::pair< int, int > > gpmp::Graph::match_cardinality ( )

Finds a maximum cardinality matching in the graph using a greedy algorithm.

Returns: Vector of pairs representing the edges in the maximum cardinality matching

Definition at line 535 of file graphs.cpp.

                                                           {
     std::vector<std::pair<int, int>> matching;
  
     // iterate through each vertex and find unmatched neighbors
     for (int v = 0; v < vertices; ++v) {
         if (!is_matched[v]) {
             for (const auto &neighbor : adj_list[v]) {
                 int u = neighbor.first;
                 if (!is_matched[u]) {
                     matching.push_back({v, u});
                     is_matched[v] = true;
                     is_matched[u] = true;
                     break;
                 }
             }
         }
     }
  
     return matching;
 }

References u.

◆ match_wt()

std::vector< std::pair< int, int > > gpmp::Graph::match_wt ( )

Finds a maximum weight matching in the graph using a greedy algorithm.

Returns: Vector of pairs representing the edges in the maximum weight matching

Definition at line 557 of file graphs.cpp.

                                                  {
     std::vector<std::pair<int, int>> matching;
  
     // sort edges in descending order based on weights
     std::vector<std::pair<std::pair<int, int>, int>> wt_edges;
     for (int v = 0; v < vertices; ++v) {
         for (const auto &neighbor : adj_list[v]) {
             int u = neighbor.first;
             int weight = neighbor.second;
             wt_edges.push_back({{v, u}, weight});
         }
     }
  
     std::sort(wt_edges.rbegin(),
               wt_edges.rend(),
               [](const auto &a, const auto &b) { return a.second < b.second; });
  
     // iterate through sorted edges and add to matching if both vertices are
     // unmatched
     for (const auto &edge : wt_edges) {
         int v = edge.first.first;
         int u = edge.first.second;
         if (!is_matched[v] && !is_matched[u]) {
             matching.push_back({v, u});
             is_matched[v] = true;
             is_matched[u] = true;
         }
     }
  
     return matching;
 }

References u.

◆ planar_gen()

void gpmp::Graph::planar_gen	(	int	num_vertices,
		double	radius
	)

Generates a random planar graph using the random geometric graph model.

Parameters

num_vertices	The number of vertices in the generated graph
radius	The radius parameter for the random geometric graph model

Definition at line 597 of file graphs.cpp.

                                                           {
     vertices = num_vertices;
     adj_list.resize(vertices);
  
     // generate random points in a 2D plane
     std::vector<std::pair<double, double>> points;
     for (int v = 0; v < vertices; ++v) {
         double x = static_cast<double>(rand()) / RAND_MAX;
         double y = static_cast<double>(rand()) / RAND_MAX;
         points.push_back({x, y});
     }
  
     // connect vertices if their Euclidean distance is less than the specified
     // radius
     for (int v = 0; v < vertices; ++v) {
         for (int u = v + 1; u < vertices; ++u) {
             double distance = euclid_dist(points[v], points[u]);
             if (distance < radius) {
                 // TODO the weight of the generated edges should probably be
                 // determined algorithmically
                 add_edge(v, u, 0);
             }
         }
     }
 }

References u.

◆ radius()

int gpmp::Graph::radius ( )

Calculates the radius of the graph.

Returns: The radius of the graph

Definition at line 456 of file graphs.cpp.

                       {
     int min_ecntrc = std::numeric_limits<int>::max();
  
     for (int v = 0; v < vertices; ++v) {
         int vEccentricity = eccentricity(v);
         min_ecntrc = std::min(min_ecntrc, vEccentricity);
     }
  
     return min_ecntrc;
 }

◆ topo_sort()

void gpmp::Graph::topo_sort ( )

Performs topological sorting on a Directed Acyclic Graph (DAG)

Definition at line 209 of file graphs.cpp.

                           {
     std::stack<int> topo_stack;
     std::vector<bool> visited(vertices, false);
  
     for (int i = 0; i < vertices; ++i) {
         if (!visited[i]) {
             topo_sort_util(i, visited, topo_stack);
         }
     }
  
     std::cout << "Topological Sorting: ";
     while (!topo_stack.empty()) {
         std::cout << topo_stack.top() << " ";
         topo_stack.pop();
     }
     std::cout << std::endl;
 }

Referenced by main().

◆ topo_sort_util()

void gpmp::Graph::topo_sort_util	(	int	v,
		std::vector< bool > &	visited,
		std::stack< int > &	topo_stack
	)

private

Helper function for topological sorting.

Parameters

v	The current vertex
visited	A vector indicating whether each vertex has been visited
topo_stack	The stack used for topological sorting

Definition at line 227 of file graphs.cpp.

                                                             {
     visited[v] = true;
  
     for (const auto &neighbor : adj_list[v]) {
         int u = neighbor.first;
         if (!visited[u]) {
             topo_sort_util(u, visited, topo_stack);
         }
     }
  
     topo_stack.push(v);
 }

References u.

◆ union_sets()

void gpmp::Graph::union_sets	(	std::vector< int > &	parent,
		int	x,
		int	y
	)

private

Unions two sets by rank in the disjoint set data structure.

Parameters

parent	The parent vector representing disjoint sets
x	The representative element of the first set
y	The representative element of the second set

Definition at line 248 of file graphs.cpp.

                                                                {
     int setX = find(parent, x);
     int setY = find(parent, y);
     parent[setX] = setY;
 }

Member Data Documentation

◆ adj_list

std::vector<std::vector<std::pair<int, int> > > gpmp::Graph::adj_list

Definition at line 52 of file graphs.hpp.

Referenced by add_edge().

◆ is_matched

std::vector<bool> gpmp::Graph::is_matched

private

Definition at line 259 of file graphs.hpp.

◆ vertices

int gpmp::Graph::vertices

Definition at line 51 of file graphs.hpp.

The documentation for this class was generated from the following files:

include/openGPMP/disct/graphs.hpp
modules/disct/graphs.cpp

Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Graph()

Member Function Documentation

◆ add_edge()

◆ bellman_ford()

◆ betweenness_centrality()

◆ bfs()

◆ choose_random_neighbor()

◆ chromatic_number()

◆ compress()

◆ connected_components()

◆ decompress()

◆ dfs()

◆ dfs_connected_components()

◆ dfs_rec()

◆ dijkstra()

◆ eccentricity()

◆ euclid_dist()

◆ find()

◆ floyd_warshall()

◆ greedy_coloring()

◆ hamiltonian_circuit_util()

◆ has_eulerian_path()

◆ has_hamiltonian_circuit()

◆ has_k33()

◆ has_k5()

◆ is_bipartite()

◆ is_k33()

◆ is_planar()

◆ kruskal()

◆ match_cardinality()

◆ match_wt()

◆ planar_gen()

◆ radius()

◆ topo_sort()

◆ topo_sort_util()

◆ union_sets()

Member Data Documentation

◆ adj_list

◆ is_matched

◆ vertices