/* make a test graph for hierholzer.w */

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

extern int
main(int argc, char *argv[])
{
	unsigned long *nodes, i, edge_count, node_count, from, to;
	int has_from;

	if (argc != 3 && argc != 4) {
		fprintf(stderr, "Usage: %s <node count> <edge count> [seed]\n", argv[0]);
		fprintf(stderr, "Some extra edges may be added to the graph.\n");
		return (EXIT_FAILURE);
	}

	node_count = atol(argv[1]);
	edge_count = atol(argv[2]);
	if (argc == 4)
		srand(atol(argv[3]));
	else
		srand(time(NULL));

	nodes = calloc(node_count, sizeof *nodes);
	if (nodes == NULL) {
		perror("Cannot allocate memory");
		return (EXIT_FAILURE);
	}

	printf("%lu\n", node_count);

	for (i = 0; i < edge_count; i++) {
		from = rand() % node_count;
		to = rand() % node_count;
		nodes[from]++;
		nodes[to]++;

		printf("%lu %lu\n", from, to);
	}

	/* now complete the graph so it is Eulerian */
	has_from = 0;
	for (i = 0; i < node_count; i++) {
		if (nodes[i] % 2 == 0)
			continue;

		if (!has_from) {
			from = i;
			has_from = 1;
		} else {
			printf("%lu %lu\n", from, i);
			has_from = 0;
		}
	}

	/* with a 50% chance, generate a graph with two odd nodes */
	if (rand() % 2 != 0)
		printf("%lu %lu\n", rand() % node_count, rand() % node_count);

	return (EXIT_SUCCESS);
}