Detecting Cycles in Graphs Using Data Structures in C
Introduction
Graphs are a fundamental data structure used to represent networks of items or entities, where the items or entities are represented as vertices (or nodes), and the connections between them are represented as edges. Detecting cycles in graphs is an important problem with numerous applications, such as deadlock detection, garbage collection, compiling language parsers, and analyzing network packets. In this article, we will explore how to detect cycles in graphs using various data structures and algorithms implemented in C.
Representation of Graph
Before diving into cycle detection, it's crucial to understand how graphs can be represented. There are two primary ways to represent graphs:
Adjacency Matrix: An N x N matrix where each element indicates whether there is an edge between the nodes.
int adjMatrix[N][N];Adjacency List: An array of linked lists where each index points to a list of corresponding connected vertices.
typedef struct listNode { int vertex; struct listNode* next; } ListNode; typedef struct adjacencyList { ListNode* head; } AdjList; typedef struct graph { int numVertices; AdjList* lists; int* visited; } Graph;
Cycle Detection Algorithms
The most common algorithms for detecting cycles in graphs are Depth-First Search (DFS) and Disjoint Set Union (DSU) with Union-Find.
Depth-First Search (DFS)
DFS is generally used to detect cycles in directed graphs. Here's the approach:
- Create a recursive DFS function that traverses the graph.
- Maintain a visited array to keep track of visited nodes.
- Use a recStack (recursion stack) to keep track of nodes currently in the recursion stack.
- Mark the current node as visited and push it to the recStack.
- If an adjacent vertex to the current node is already in the recStack, then there is a cycle.
- If no cycles are found in all nodes using DFS, then the graph is acyclic.
int isCyclicUtil(int v, int visited[], int recStack[], Graph* graph) {
if(visited[v] == 0) { // Mark the current node as visited and part of recursion stack
visited[v] = 1;
recStack[v] = 1;
// Recur for all the vertices adjacent to this vertex
ListNode* listNode = graph->lists[v].head;
while(listNode) {
int adjVertex = listNode->vertex;
if ( !visited[adjVertex] && isCyclicUtil(adjVertex, visited, recStack, graph) )
return 1;
else if (recStack[adjVertex])
return 1;
listNode = listNode->next;
}
}
recStack[v] = 0; // Remove the vertex from recursion stack
return 0;
}
int isCyclic(Graph* graph) {
int* visited = (int*)malloc(graph->numVertices * sizeof(int));
int* recStack = (int*)malloc(graph->numVertices * sizeof(int));
for(int i = 0; i < graph->numVertices; i++) {
visited[i] = recStack[i] = 0;
}
for(int i = 0; i < graph->numVertices; i++)
if ( !visited[i] && isCyclicUtil(i, visited, recStack, graph))
return 1;
free(visited);
free(recStack);
return 0;
}
Disjoint Set Union (DSU) with Union-Find for Undirected Graphs
For undirected graphs, Union-Find is a suitable method to detect cycles using DSU:
- Use the Union-Find algorithm to unite the vertices.
- If two vertices are part of the same set before uniting, then merging them will create a cycle.
Here's how you could implement it in C:
typedef struct subset {
int parent;
int rank;
} Subset;
int find(Subset subsets[], int i) { // Recursive path compression
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
void Union(Subset subsets[], int x, int y) {
int xset = find(subsets, x);
int yset = find(subsets, y);
if (xset == yset) {
printf("Cycle detected\n");
} else {
if (subsets[xset].rank < subsets[yset].rank)
subsets[xset].parent = yset;
else if (subsets[xset].rank > subsets[yset].rank)
subsets[yset].parent = xset;
else {
subsets[yset].parent = xset;
subsets[xset].rank++;
}
}
}
int isCyclicUndirected(Graph* graph) {
Subset* subsets = (Subset*)malloc(graph->numVertices * sizeof(Subset));
for (int v = 0; v < graph->numVertices; v++) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
// Iterate through all edges of graph, find sets of both vertices of every edge.
// If sets are the same, then there is cycle in graph.
for (int i = 0; i < graph->numVertices; i++) {
ListNode* pCrawl = graph->lists[i].head;
while (pCrawl) {
if (find(subsets, i) == find(subsets, pCrawl->vertex)) {
return 1;
}
Union(subsets, i, pCrawl->vertex);
pCrawl = pCrawl->next;
}
}
free(subsets);
return 0;
}
Conclusion
Determining whether a graph contains a cycle is a fundamental problem in computer science. The choice of algorithm depends on the type of graph (directed or undirected). For directed graphs, DFS is preferred due to its simplicity, while DSU/Union-Find technique is more efficient for undirected graphs. Both methods are vital tools in many practical applications dealing with graph structures, making the understanding of these concepts invaluable for any programmer.
By implementing these algorithms in C, one gets a deeper insight into the inner workings of these data structures and algorithms, which can further help in optimizing code and designing new solutions.
Examples with Frontend, Backend, Data Flow, and Application Running Step-by-Step for Beginners
Topic: C Programming and Data Structures - Detecting Cycles in Graphs
Detecting cycles in graphs is a common problem in computer science, and it can be efficiently solved using depth-first search (DFS). In this tutorial, we'll create a simple C application that detects cycles in an undirected graph using DFS. We'll also build a basic web interface as a frontend to interact with this application, and set up a backend server to handle requests from the frontend. This example is meant to give you a good sense of how these components can work together.
Prerequisites
- Basic Knowledge of C Programming.
- Understanding of Graph Data Structures.
- Familiarity with Web Development: HTML, CSS, JavaScript.
- Experience with a Server-Side Language: Node.js, Python, PHP, etc.
- Command Line Interface for Backend Commands.
Part 1: Backend (C Program)
Step 1: Define Graph Structure
A graph can be represented using an adjacency list. Let’s define a graph structure with the necessary fields:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Define a linked list node
typedef struct AdjListNode {
int dest;
struct AdjListNode* next;
} AdjListNode;
// Define a linked list
typedef struct AdjList {
AdjListNode *head;
} AdjList;
// Define a Graph
typedef struct Graph {
int V; // Number of vertices
AdjList* array;
} Graph;
// Create a new adjacency list node
AdjListNode* newAdjListNode(int dest) {
AdjListNode* newNode = (AdjListNode*) malloc(sizeof(AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// Creates a graph of V vertices
Graph* createGraph(int V) {
Graph* graph = (Graph*) malloc(sizeof(Graph));
graph->V = V;
// Create an array of adjacency lists. Size of array will be V
graph->array = (AdjList*) malloc(V * sizeof(AdjList));
// Initialize each adjacency list as empty by making head as NULL
for (int i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
// Adds an edge to an undirected graph
void addEdge(Graph* graph, int src, int dest) {
// Add an edge from src to dest. A new node is added to the adjacency list of src.
// The node is added at the beginning.
AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
// Since graph is undirected, add an edge from dest to src also
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
Step 2: Implement Cycle Detection Using DFS
Here, we implement a helper function for DFS and main cycle detection logic.
// A utility function to do DFS on a graph. It uses recursion based approach
bool isCyclicUtil(int v, bool visited[], bool recStack[], Graph* graph) {
if (!visited[v]) {
// Mark the current node as visited and part of recursion stack
visited[v] = true;
recStack[v] = true;
// Recur for all the vertices adjacent to this vertex
AdjListNode* temp = graph->array[v].head;
while (temp) {
int adj_vertex = temp->dest;
if (!visited[adj_vertex] && isCyclicUtil(adj_vertex, visited, recStack, graph))
return true;
else if (recStack[adj_vertex])
return true;
temp = temp->next;
}
}
recStack[v] = false;
return false;
}
// Returns true if the graph contains a cycle, else false.
bool isCyclic(Graph* graph) {
// Mark all the vertices as not visited and not part of recursion stack
bool* visited = (bool*) malloc(graph->V * sizeof(bool));
bool* recStack = (bool*) malloc(graph->V * sizeof(bool));
for (int i = 0; i < graph->V; i++) {
visited[i] = false;
recStack[i] = false;
}
// Call the recursive helper function to detect cycle in different DFS trees
for (int i = 0; i < graph->V; i++)
if (!visited[i])
if (isCyclicUtil(i, visited, recStack, graph))
return true;
free(visited);
free(recStack);
return false;
}
// Utility to print graph
void printGraph(Graph* graph) {
for (int v = 0; v < graph->V; ++v) {
AdjListNode* pCrawl = graph->array[v].head;
printf("\n Adjacency list of vertex %d\n head ", v);
while (pCrawl) {
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf("\n");
}
}
// Main function to demonstrate graph creation and cycle check
int main() {
int V = 4;
Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
printGraph(graph);
if(isCyclic(graph))
printf("Graph contains cycle\n");
else
printf("Graph doesn't contain cycle\n");
free(graph->array);
free(graph);
return 0;
}
To compile and run the program, use these commands:
gcc -o cycle_detection cycle_detection.c
./cycle_detection
This would print the adjacency list and whether the graph has a cycle or not.
Part 2: Backend (Server-Side Code)
Since we are interacting with the frontend via the web, let's set up a basic HTTP server using JavaScript's http module or any other server-side language of your choice. We'll use Node.js here:
Step A: Setting Up Node Server
First, install Node.js then create a project by executing the command below in terminal.
mkdir cycle_detection_web_project
cd cycle_detection_web_project
npm init -y
Next, install Express package, a minimal and flexible Node.js web application framework.
npm install express --save
Step B: Creating Server and Endpoint
Create a JavaScript file (app.js) for your Node server, and write this code:
const express = require('express');
const { execFile } = require('child_process');
const app = express();
const port = 3000;
app.use(express.json());
// Endpoint to run cycle detection
app.post('/detect_cycle', (req, res) => {
const { vertices, edges } = req.body;
const args = [vertices, edges];
execFile('./cycle_detection', args, (error, stdout, stderr) => {
if (error) {
console.error(`Cycle detection failed with error: ${stderr}`);
return res.status(500).send({ message: 'Internal Server Error' });
}
res.send({ message: stdout.trim() });
});
});
app.listen(port, () => {
console.log(`Cycle Detection Web Project running at http://localhost:${port}/`);
});
Now, we need to compile the C code again making sure to use arguments passed from the server. Modify main() in cycle_detection.c:
int main(int argc, char const *argv[]) {
if(argc != 3){
printf("Invalid number of parameters passed\n");
return 1;
}
int V = atoi(argv[1]);
int E = atoi(argv[2]);
Graph* graph = createGraph(V);
// Here, you would read edges from request body and addEdges
// But for simplicity, let’s consider some hard-coded values here,
// Replace this by dynamically reading edges sent by web server.
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
if(isCyclic(graph))
printf("Graph contains cycle\n");
else
printf("Graph doesn't contain cycle\n");
free(graph->array);
free(graph);
return 0;
}
Compile the C code using gcc:
gcc -o cycle_detection cycle_detection.c
Start the server:
node app.js
Part 3: Frontend (Web Interface)
We’ll use HTML and JavaScript to make an interactive interface that allows input of vertices and edges as well as sends them to the backend for cycle detection.
File A: index.html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Cycle Detection</title>
<style>
body { font-family: Arial, sans-serif; padding: 20px; }
.container { max-width: 500px; margin: auto; }
input { width: 100%; padding: 8px; margin-top: 8px; margin-bottom: 8px; }
button { padding: 10px 20px; background-color: #4CAF50; color: white; border: none; cursor: pointer; }
button:hover { background-color: #45a049; }
textarea { width: 100%; padding: 8px; height: 100px; }
p { font-weight: bold; }
</style>
</head>
<body>
<div class="container">
<h2>Detect Cycle in Graph</h2>
<input type="number" id="vertices" placeholder="Enter number of vertices...">
<textarea id="edges" placeholder="Enter edges in format 'source destination' with each line as one edge"></textarea>
<button onclick="detectCycle()">Detect Cycle</button>
<p id="result"></p>
</div>
<script>
async function detectCycle() {
const verticesInput = document.getElementById('vertices').value;
const edgesInput = document.getElementById('edges').value;
const edgesArray = [];
for(const edgeLine of edgesInput.split('\n')){
const [src, dest] = edgeLine.trim().split(' ').map(Number);
edgesArray.push(src, dest);
}
const dataToSend = JSON.stringify({
vertices: verticesInput,
edges: edgesArray.join(',')
});
try{
const response = await fetch('http://localhost:3000/detect_cycle', {
method: 'POST',
headers: {
'Content-Type': 'application/json'
},
body: dataToSend
});
const result = await response.json();
document.getElementById('result').innerText = result.message || 'No response';
}
catch(error){
document.getElementById('result').innerText = `Error: ${error}`;
}
}
</script>
</body>
</html>
Part 4: Connecting the Frontend and Backend
You've already made your C backend executable (cycle_detection). This server expects two pieces of information in the POST request: the number of vertices and edges. For our frontend, the user inputs these into corresponding textboxes and clicks the "Detect Cycle" button, which triggers the detectCycle() JavaScript function.
Part 5: Running the Application
Open three terminal sessions.
In the first session, navigate to your C source code directory. Run C application by using
gccand creating executable:gcc -o cycle_detection cycle_detection.c ./cycle_detectionMake sure it’s running as expected.
Start the Node.js Server in the second terminal:
node app.jsEnsure the server is listening on
http://localhost:3000.In the third session, start a simple HTTP server to serve the frontend files. You can use any available method (Python's Simple HTTP Server, Node's http static file service etc.). With Python3, you can do it like this:
python3 -m http.server 8080Open your browser and navigate to
http://localhost:8080/index.html. You'll find the frontend where you can input vertices, edges, and check for cycles.Example Input:
- Vertices: 4
- Edges:
0 1,0 2,1 2,2 3
Click "Detect Cycle", and you should see the output showing if your graph contains a cycle.
Conclusion
In this example, you walked through an end-to-end flow starting from implementing a graph data structure and a cycle detection algorithm in C, setting up a basic HTTP server to interact with this C application, and finally creating a web frontend to input graph details and receive results. The key takeaway is not just to learn about cycle detection in graphs, but also understanding how various components in a web application might interact with each other.