graph_matrix.cpp

这个代码包括求图的最大生成树和Ｍ着色问题．

 
#include <stdlib.h>
#include <string.h>
#include <error.h>
#include <stdio.h>
#include <assert.h>
#include <list>
#include <algorithm> // we can use the find algorithm
#include "graph_matrix.h"

using namespace std;

mgraph::mgraph(size_t sz):size(sz)
{
  edgematrix = (size_t *)malloc( sizeof(size_t) * size *size); // memory allocate for edge matrix
  memset(edgematrix,MAX_INT,sizeof(size_t) * size*size);	// set the distance to the biggest int, thus each vertex is disconnect with an other
}

 
mgraph::~mgraph()
{
  size = 0;
  if(edgematrix != NULL){	// free the space for edge matrix
    free(edgematrix);
    edgematrix = NULL;		// remember to set each free point to NULL
  }
}

// method : connect
// arguments: i(int) : vertex index
// j(int) : vertex index
// distance(int) : distance between vertex i and j
// return: OK
// ERROR if some error occour
int 
mgraph::connect(int i, int j, int distance)
{
  if((size_t) i >= size || (size_t) j >= size){
    return ERROR;
  }
  edgematrix[i*size + j] = distance;
  return OK;
}
// method :       read_file
// arguments:   file(char *) : graph file name
// return:        OK
//                   ERROR if some error occour
// note:          file content many lines, each line describe an edge use three int numbers (i j k)
//                   that i and j is the index of vertex, k is distance between i and j,
//                   numbers separted with spaces
int 
mgraph::read_file( char * file)
{
  FILE *fd = NULL;
  fd = fopen(file,"r");		// open the file
  if(fd == NULL){		// error open file
    perror("error while read file");
    return ERROR;
  }
  int i,j,k;
  while(fscanf(fd,"%d%d%d",&i,&j,&k) != EOF){ // read file untill the End Of the File
    if( connect(i,j,k) == ERROR){ // add the path to graph
      return ERROR;
    }
  }
  fclose(fd);
  return OK;
}
// method : print
// arguments: 
//return: OK
//           ERROR if some error occour
// note :  print only the matrix,
int 
mgraph::print()
{
  size_t i,j;
  printf("------------------------------------\n");
  printf("\t");
  for(i = 0; i < size; i++){	// table head
    printf("[%d]\t",i);
  }
  printf("\n");
  for(i = 0; i < size; i++){	// print row by row
    printf("[%d]\t", i);
    for(j=0; j< size; j++){	// one row
      if(edgematrix[i * size + j] == MAX_INT){ // not connected
	printf("NO\t");
      } else {			// if connected
	printf("%d\t",edgematrix[i * size + j]);
      }//endif
    }//end for j
    printf("\n");
  }//end for i
  printf("------------------------------------\n");
  return OK;
}

// method : max_span_tree
// arguments: mgraph &g: the maximum spanning tree
// return:	OK
//          ERROR if some error occour
// note :  
int
mgraph::max_span_tree(mgraph &g)
{
	int		i,j;
	edge	temp_edge;
	std::list<edge> edge_list;
	std::list<int>  used_list;//nodes in max tree

	assert(edgematrix != NULL);
	//find all the edges
	for(i=0; i<size; i++){
		for(j=0; j<size; j++){
			if(j!=i && edgematrix[i * size + j] != MAX_INT){
				temp_edge.src = i;
				temp_edge.dst = j;
				temp_edge.length = edgematrix[i * size + j];
				edge_list.push_back(temp_edge);
			}
		}
	}
	//sort the edges in the edge_list
	edge_list.sort();//sort it from small to big
	//create the max spanning tree
	while(!edge_list.empty()){
		temp_edge = edge_list.back();
		if(find(used_list.begin(),used_list.end(),temp_edge.src) == used_list.end()
			|| find(used_list.begin(),used_list.end(),temp_edge.dst) == used_list.end()){// if it is not used
			if( g.connect(temp_edge.src,temp_edge.dst,temp_edge.length) == ERROR)
				return ERROR;
			if( g.connect(temp_edge.dst,temp_edge.src,temp_edge.length) == ERROR)
				return ERROR;
			used_list.push_back(temp_edge.src);
			used_list.push_back(temp_edge.dst);
		}
		edge_list.pop_back();
	}
	return OK;
}