\section{wGraph.cpp} <>= /* File: wGraph.cpp * Last Revision: 2-Apr-2001 * Description: this file contains the definition of the class wGraph * as declared in the file wGraph.H (see file wGraph.H to get more insight). * * programmer: Romeo Rizzi. * rrizzi@rtm.science.unitn.it * * Classes defined: wGraph */ #include "wGraph.H" #include Graph::Graph(graph_enum gen, int num_nodi, double expected_deg, int np, int seed) { n_nodes = num_nodi; n_edges = 0; half_n_nodes = num_nodi/2; // Initialize the random generator and other parameters to generate the graph. iseed = (long)(n_nodes *131 + expected_deg *101 + np *191 + seed ) % 32767; smyrand(iseed); density = (double) expected_deg / (n_nodes - 1) ; distance = sqrt(expected_deg / (n_nodes * 3.141592653589793238)); // Allocate the adjacency matrix "adj_M [u][v]". allocate_adj_M(); // Allocate the matrix of weights "W [u][v]". allocate_W(); // Generate a type (gen) graph. Generate the adjacency matrix adj_M[u][v]. switch (gen) { case DSJ_G : generate_G_graph(density); break; case DSJ_U : generate_U_graph(distance); break; } Make_Star_DataStructure(); cout << "\n\nN= " << n_nodes << " Nu= " << expected_deg << " Tipo grafo= " << gen << " N.lati= " << n_edges << " Seed= " << iseed << " N.problema= " << np << endl; } void Graph::allocate_adj_M() { adj_M = new int*[n_nodes] -1; for (int i = n_nodes; i; i--) { adj_M[i] = new int[n_nodes] -1; for(int j = n_nodes; j; j--) adj_M[i][j] = 0; } } void Graph::allocate_W() { W = new int*[n_nodes] -1; for (int i = n_nodes; i; i--) { W[i] = new int[n_nodes] -1; for(int j = n_nodes; j; j--) W[i][j] = 0; } } Graph::~Graph() { for(int i = n_nodes; i; i--) { delete [] (adj_M[i] +1); delete [] (W +1); } delete [] (adj_M +1); delete [] (W +1); delete [] (first_nei +1); delete [] (list_of_neighbors +1); delete [] (deg +1); } void Graph::Make_Star_DataStructure() { deg = new int[n_nodes] -1; max_deg = 0; first_nei = new int[n_nodes] -1; list_of_neighbors = new int[2*n_edges + n_nodes] -1; int pos = 1; for(int i = n_nodes; i; i--) { first_nei[i] = pos; for(int j = n_nodes; j; j--) if (adj_M[i][j]) list_of_neighbors[ pos++ ] = j; deg[i] = pos - first_nei[i]; list_of_neighbors[ pos++ ] = 0; if( deg[i] > max_deg ) max_deg = deg[i]; } } // generate random weights and store them into matrix W void Graph::random_W() { for(int i = 1; i < n_nodes; i++) for(int j = n_nodes; j > i; j--) if ( adj_M[i][j] ) W[i][j] = W[j][i] = 1+dado(MAX_W); } // generate G graphs void Graph::generate_G_graph(double density) { for(int i = 1; i < n_nodes; i++) for(int j = n_nodes; j > i; j--) if ( myrand() < density ) { adj_M[i][j] = adj_M[j][i] = 1; n_edges ++; } random_W(); } // generate U graphs void Graph::generate_U_graph(double distance) { int i, j; double *x, *y; x = new double[n_nodes +1]; y = new double[n_nodes +1]; for(i = n_nodes; i; i--) { x[i] = myrand(); y[i] = myrand(); } for(i = n_nodes; i; i--) for(j = n_nodes; j > i; j--) if(SQR( x[i] -x[j] ) + SQR( y[i] -y[j] ) < SQR(distance)) { adj_M[i][j] = adj_M[j][i] = 1; n_edges ++; } delete [] x; delete [] y; random_W(); } void Graph::dimacs_input(const char *file) { ifstream in(file); if (!in.good()) { cerr << "err: input_graph: Input graph does not exist." << endl; exit(1); } char first_char_of_line, pippo[1000]; in.get(first_char_of_line); while(first_char_of_line != 'p') { in.getline(pippo,1000); in.get(first_char_of_line); } in >> pippo >> n_nodes >> n_edges; in.getline(pippo,1000); // Allocate the adjacency matrix "adj_M [u][v]". allocate_adj_M(); // Allocate the matrix of weights "W [u][v]". allocate_W(); int i, j, w, num_arcs = n_edges; while(num_arcs--) { in.get(first_char_of_line); while(first_char_of_line != 'e') { in.getline(pippo,1000); in.get(first_char_of_line); } in >> i >> j >> w; in.getline(pippo,1000); adj_M[i][j] = 1; adj_M[j][i] = 1; W[i][j] = w; W[j][i] = w; } half_n_nodes = n_nodes /2; } void Graph::johnson_input(const char *file) { ifstream in(file); if (!in.good()) { cerr << "err: input_graph: Input graph does not exist." << endl; exit(1); } int max_node = 0, num_arc = 0, node_of_line, degree, neighbor, w; char pippo[50]; do { in >> node_of_line >> pippo >> degree; if (node_of_line > max_node) max_node = node_of_line; num_arc += degree; for (; degree > 0; degree--) { in >> neighbor; if (neighbor > max_node) max_node = neighbor; } } while(in); n_nodes = max_node; n_edges = num_arc /2; half_n_nodes = n_nodes /2; // Allocate the adjacency matrix "adj_M [u][v]". allocate_adj_M(); // Allocate the matrix of weights "W [u][v]". allocate_W(); in.close(); in.open(file); do { in >> node_of_line >> pippo >> degree; for (; degree > 0; degree--) { in >> neighbor >> w; adj_M[node_of_line][neighbor] = 1; adj_M[neighbor][node_of_line] = 1; W[node_of_line][neighbor] = w; W[neighbor][node_of_line] = w; } } while(in); in.close(); } Graph::Graph(const int format, const char *file) { switch (format) { case DIMACS : dimacs_input(file); break; case JOHNSON : johnson_input(file); break; default: cerr << "err: input_graph: " << "We input only graphs in DIMACS or JOHNSON format." << endl; exit(1); } Make_Star_DataStructure(); } void Graph::write(const int format, const char *file) { if (format != DIMACS) { cerr << "err: output_graph: " << "We output only graphs in DIMACS format." << endl; exit(1); } ofstream output(file); output << "p gp " << n_nodes << " " << n_edges << endl; for(int i = 1; i < n_nodes; i++) for(int j = i+1; j <= n_nodes; j++) if (adj_M[i][j]) output << "e " << i << " " << j << " " << W[i][j] << endl; output.close(); } int Graph::size_of_cut(const int *x) // returns the number of edges whose // endpoints have different x[] values. { int size = 0; for(int node = n_nodes; node; node--) { int x_node = x[node]; neighbor_pos = list_of_neighbors + first_nei[node]; while(*neighbor_pos > node) if(x[*(neighbor_pos ++)] != x_node) ++size; } return size; } @