//
// Programm zur Erzeugung eines dichten, zusammenhängenden
// Zufallsgraphen mit positiven, ganzzahligen Kantengewichten
//
// Aufrufparameter: Knotenzahl, Dateiname
//
#include <LEDA/graph.h>
#include <LEDA/random_source.h>
#include <LEDA/map2.h>
#include <LEDA/graph_misc.h>

main(int ac, char **av) {
    int n = (ac>1? atoi(av[1]) : 0);
    if (ac!=3 || n<1) {
	cerr <<"usage: " <<av[0] <<" n s\n";
	cerr <<"       n = number of nodes\n";
	cerr <<"       s = name of file to which graph is saved\n";
	exit(1);
	}
    node *V = new node[n];
    GRAPH<int,int> g;
    for (int i=0; i<n; i++) {
	V[i] = g.new_node();
	g[V[i]] = i%2;
    }
    map2<int,int,int> adj;
    random_source S(0,n-1);
    for (int j=0; j<n*(n-1)/8 || !Is_Connected(g); j++) {
	int gewicht;
	S >> gewicht;
	gewicht += 42;
	int a,b;
	do {
	    S >> a;
	    S >> b;
	} while (a==b || adj.defined(a,b));
	g[g.new_edge(V[a],V[b])]=gewicht;
	adj(a,b) = 1;
    }
    edge e;
    forall_edges(e,g) if (g[g.source(e)]!=g[g.target(e)]) g[e] += n;
    node v;
    forall_nodes(v,g) g[v]=0;
    g.write(av[2]);
    cout <<"graph with " <<n <<" nodes created and written to file '" <<av[2] <<"'\n";
}