graphopr.h

图论：最大支撑树算法实现 GraphM.h GraphOpr.h MaxST.cpp MaxST.dsp MaxST.dsw MaxST.h MaxST.ncb MaxST.opt

#ifndef GRAPHOPR_H
#define GRAPHOPR_H

#include "Graphm.h"

const int LINELEN = 80;

void printGraph(Graph* G) {
  int i, j;
  for (i = 0; i < G->n(); i++)
  {
	for (j = 0; j < G->n(); j++)
	  cout << G->weight(i, j) << " ";
	cout << endl;
  }
  for (i=0; i<G->n(); i++)
  {
	cout << i << "--";
    for(j=0; j<G->n(); j++)
      if (G->weight(i, j) != 0)
		cout << j << " ";
    cout << endl;
  }
}


char* getl(char* buffer, int n, FILE* fid) {
  char* ptr;
  ptr = fgets(buffer, n, fid);
  while ((ptr != NULL) && (buffer[0] == '#'))
    ptr = fgets(buffer, n, fid);
  return ptr;
}


Graph* readGraph(FILE* fid) {
  char buffer[LINELEN+1]; // 数据缓冲
  int i;
  int v1, v2, dist;

  if (getl(buffer, LINELEN, fid) == NULL)
  {
	cout << "Unable to read number of vertices" << endl;
    return NULL;
  }

  Graph* G = new Graph(atoi(buffer));

  if (getl(buffer, LINELEN, fid) == NULL)
  {
	cout << "Unable to read graph type" << endl;
    return NULL ;
  }

  if (buffer[0] == 'U')
    G->setDirect(0);
  else
	if (buffer[0] == 'D')
      G->setDirect(1);
    else
	{
      cout << "Bad graph type: |" << buffer << "|" << endl;
      return NULL;
	}

  while (getl(buffer, LINELEN, fid) != NULL)
  {
    v1 = atoi(buffer);
    i = 0;
    while (isdigit(buffer[i])) i++;
    while (buffer[i] == ' ') i++;
    v2 = atoi(&buffer[i]);
    while (isdigit(buffer[i])) i++;
    if (buffer[i] == ' ') { // 有权值
      while (buffer[i] == ' ') i++;
      dist = atoi(&buffer[i]);
    }
    else dist = 1;
    G->setEdge(v1, v2, dist);
  }
  return G;
}

#endif