Spaces:
Sleeping
Sleeping
File size: 3,609 Bytes
9f135d5 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 | // Find Eulerian path/circuit using Hierholzer's algorithm
// Path that visits every edge exactly once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define MAX_V 1000
#define MAX_E 5000
typedef struct {
int adj[MAX_V][MAX_V];
int degree[MAX_V];
int in_degree[MAX_V];
int out_degree[MAX_V];
int n_vertices;
int edge_count[MAX_V][MAX_V];
} Graph;
int path[MAX_E];
int path_len;
void graph_init(Graph *g, int n) {
g->n_vertices = n;
memset(g->degree, 0, sizeof(g->degree));
memset(g->in_degree, 0, sizeof(g->in_degree));
memset(g->out_degree, 0, sizeof(g->out_degree));
memset(g->edge_count, 0, sizeof(g->edge_count));
}
void add_directed_edge(Graph *g, int u, int v) {
g->edge_count[u][v]++;
g->out_degree[u]++;
g->in_degree[v]++;
// Add to adjacency list if not already present
int found = 0;
for (int i = 0; i < g->degree[u]; i++) {
if (g->adj[u][i] == v) {
found = 1;
break;
}
}
if (!found && g->degree[u] < MAX_V) {
g->adj[u][g->degree[u]++] = v;
}
}
int can_have_eulerian_path(Graph *g, int *start) {
int start_vertices = 0, end_vertices = 0;
*start = 0;
for (int i = 0; i < g->n_vertices; i++) {
int diff = g->out_degree[i] - g->in_degree[i];
if (diff > 1 || diff < -1) return 0;
if (diff == 1) {
start_vertices++;
*start = i;
} else if (diff == -1) {
end_vertices++;
}
}
return (start_vertices == 0 && end_vertices == 0) ||
(start_vertices == 1 && end_vertices == 1);
}
void hierholzer_dfs(Graph *g, int u, int stack[], int *stack_top) {
while (g->degree[u] > 0) {
int next_idx = g->degree[u] - 1;
int v = g->adj[u][next_idx];
if (g->edge_count[u][v] > 0) {
g->edge_count[u][v]--;
hierholzer_dfs(g, v, stack, stack_top);
} else {
g->degree[u]--;
}
}
stack[(*stack_top)++] = u;
}
int find_eulerian_path(Graph *g) {
int start;
if (!can_have_eulerian_path(g, &start)) {
return 0;
}
int stack[MAX_E];
int stack_top = 0;
hierholzer_dfs(g, start, stack, &stack_top);
path_len = 0;
for (int i = stack_top - 1; i >= 0; i--) {
path[path_len++] = stack[i];
}
return path_len;
}
void generate_eulerian_graph(Graph *g, int n_vertices) {
graph_init(g, n_vertices);
// Create a graph that definitely has an Eulerian circuit
// by ensuring all vertices have equal in-degree and out-degree
for (int i = 0; i < n_vertices; i++) {
int next = (i + 1) % n_vertices;
add_directed_edge(g, i, next);
add_directed_edge(g, i, (i + 2) % n_vertices);
}
}
int main() {
Graph g;
int n_vertices = 800;
generate_eulerian_graph(&g, n_vertices);
int total_edges = 0;
for (int i = 0; i < n_vertices; i++) {
total_edges += g->out_degree[i];
}
clock_t start = clock();
int path_length = find_eulerian_path(&g);
clock_t end = clock();
double time_spent = (double)(end - start) / CLOCKS_PER_SEC;
printf("Eulerian path (Hierholzer): %d vertices, %d edges, %.6f seconds\n",
n_vertices, total_edges, time_spent);
printf("Path length: %d\n", path_length);
return 0;
}
|