\section{wGraph.H} <>= /* File: wGraph.H * Last Revision: 2-Apr-2001 * Description: a data type for weighted graphs. * a weighted graph is a graph G=(V,E) with integer weights on the edges. * * author: Romeo Rizzi. * romeo@science.unitn.it * * Classes declared: wGraph * * The class wGraph implements: * 1) The data structure storing a given weighted graph, * 2) The methods for quering this data structure, * 3) The methods to generate "DSJ_U" and "DSJ_G" graphs (see below), * 4) The methods for loading the input graph from a file. * (natural extension of DIMACS format, or of JOHNSON format). */ #ifndef _W_GRAPH_H #define _W_GRAPH_H #include #include #include "Rand.H" #define MAX_NODES 10000 #define MAX_W 100 #define DIMACS 1 #define BINARY_DIMACS 2 #define JOHNSON 3 #define SQR(x) ( (x)*(x) ) enum graph_enum { DSJ_U, DSJ_G}; /* We generate two kinds of graphs: * DSJ_U: Each node is put in the plane and receives two random coordinates. * Two nodes u and v are then connected by an edge uv, if and only * if their distance does not exceed a given constant. * In case the edge exists, then its weight is choosen uniformly * at random in the interval [1, ..., MAX_W]. * DSJ_G: Random weighted graphs where the probability that there exists * an edge between any two nodes is a constant. * In case the edge exists, then its weight is choosen uniformly * at random in the interval [1, ..., MAX_W]. * Thus the expected degree of any vertex is a constant. * Such graphs are indeed characterized by their expected degree. * * Note: G and U graphs are extensions of the unweighted graphs * produced in the class Graph or as by Dell'Amico - Maffioli. * Starting from a same seed we obtain the same support graph * as in the class Graph or as Dell'Amico - Maffioli. */ class Graph { /* A graph G has n nodes and m edges. * We number the nodes of G as: 1, ... ,n. * * Data Structures: * * 1) THE ADJACENCY MATRIX: adj_M * adj_M [u][v] == 1 if edge (u,v) exists; 0 otherwise. * * 2) THE MATRIX of WEIGHTS: W * W [u][v] gives the weight of edge (u,v) when such an edge exists. * * 3) THE SEQUENCE OF NEIGHBORS: list_of_neighbors and first_nei * list_of_neighbors has the following structure: * * | * first_nei[i] * * first_nei[i] = the position in list_of_neighbors[] of the first neighbor of vertex i * * The neighbors of vertex i are: * list_of_neighbors[first_nei[i]], list_of_neighbors[first_nei[i]+1],...,list_of_neighbors[first_nei[i+1]-1]). * * NOTE: (a detail in our implementation of list_of_neighbors) * Between the neighbors of node i and the neighbors * of node (i+1) we put a 0 as separetor. * This trick allows for a faster scan of the neighbors of any node. * (See procedures first_neighbor(node u) and next_neighbor() below. */ int n_nodes; // number of nodes. int n_edges; // number of edges. int half_n_nodes; // half_n_nodes = (n_nodes /2). int **adj_M; int **W; // SEQUENCE OF NEIGHBORS: int *first_nei; int *list_of_neighbors; int *deg; // the degree array of nodes. (degree= number of neighbors). int max_deg; // the maximum degree of a node. int *neighbor_pos; // used to scan the neighbor of a node. void Make_Star_DataStructure(); // derives "list_of_neighbors" and "first_nei" from "adj_M". // ALLOCATING THE ADJACENCY MATRIX "adj_M". void allocate_adj_M(); // ALLOCATING THE MATRIX OF WEIGHTS "W". void allocate_W(); // STORING RANDOM WEIGHTS INTO MATRIX "W". void random_W(); // GENERATING "DSJ_U" and "DSJ_G" GRAPHS: int iseed; // seed to random generate graphs DSJ_U or DSJ_G. double density, distance; void generate_G_graph(double density); /* Instantiates a graph of type "G". * assumes "adj_M" having been allocated before the call. * At termination "adj_M" is the adjacency matrix of the generated graph. * However the star data structures are not yet initialized at termination * and will be derived from "adj_M" in a second phase by the method "Make_Star_DataStructure()". */ void generate_U_graph(double distance); /* Instantiates a graph of type "U". * assumes "adj_M" having been allocated before the call. * At termination "adj_M" is the adjacency matrix of the generated graph. * However the star data structures are not yet initialized at termination * and will be derived from "adj_M" in a second phase by the method "Make_Star_DataStructure()". */ // LOADING UP A GRAPH FROM A FILE: void dimacs_input(const char *file); // inputs a graph in the binary (compressed) dimacs format. // see URL: void johnson_input(const char *file); // inputs a graph in the johnson format. // see URL: public: Graph (graph_enum gen, int n, double expected_deg, int np, int seed=1); /* Generates a graph of type with nodes. * is the seed to random generate the graph: different calls with * the same (and the same ) produce identical graphs. * (in fact, for a given pair (, ), we produce the same graph * as Dell'Amico-Maffioli generator). * is the expected degree of the random graph to be instantiated. * is the problem number and is output after the graph * has been generated together with other informations about the graph. */ Graph (const int format, const char *file); // Creates a graph by loading it from a in a given . ~Graph(); void write(const int format, const char *file); // saves the graph on a according to the specifyied // (useful for conversions, of no use for the search algorithms). int n() const // returns the number of nodes. { return n_nodes; } int m() const // returns the number of edges. { return n_edges; } int half_n() const // returns half the number of nodes. { return half_n_nodes; } int edge(int u, int v) const // returns 1 if nodes u and v are adjacent. {return adj_M [u][v]; } // returns 0 otherwise. // note: edge(x,x) == 0, no self-connection. int weight(int u, int v) const // returns the weight of edge uv. {return W [u][v]; } // the returned value is not defined // if u and v are not adjacent. int max_degree() // returns the maximum degree. { return max_deg; } int degree(int v) const // returns the degree of node v. { return deg[v]; } int first_neighbor(int v); // returns 0 if no neighbor. int next_neighbor(); // returns 0 if no next neighbor. int size_of_cut(const int *x); // returns the number of edges whose // endpoints have different x[] values. }; inline int Graph::next_neighbor() // returns 0 if no next neighbor. { return *(neighbor_pos ++); } inline int Graph::first_neighbor(int v) { // returns 0 if no neighbor. neighbor_pos = list_of_neighbors + first_nei[v]; return next_neighbor(); } #endif @