haskell-igraph-0.8.0: igraph/src/cliquer_graph.c
/*
* This file contains the graph handling routines.
*
* Copyright (C) 2002 Sampo Niskanen, Patric Östergård.
* Licensed under the GNU GPL, read the file LICENSE for details.
*/
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include "graph.h"
#ifdef USING_R
#include <R.h>
#endif
/*
static graph_t *graph_read_dimacs_binary(FILE *fp,char *firstline);
static graph_t *graph_read_dimacs_ascii(FILE *fp,char *firstline);
*/
/*
* graph_new()
*
* Returns a newly allocated graph with n vertices all with weight 1,
* and no edges.
*/
graph_t *graph_new(int n) {
graph_t *g;
int i;
ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
ASSERT(n>0);
g=malloc(sizeof(graph_t));
g->n=n;
g->edges=malloc(g->n * sizeof(set_t));
g->weights=malloc(g->n * sizeof(int));
for (i=0; i < g->n; i++) {
g->edges[i]=set_new(n);
g->weights[i]=1;
}
return g;
}
/*
* graph_free()
*
* Frees the memory associated with the graph g.
*/
void graph_free(graph_t *g) {
int i;
ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
ASSERT(g!=NULL);
ASSERT(g->n > 0);
for (i=0; i < g->n; i++) {
set_free(g->edges[i]);
}
free(g->weights);
free(g->edges);
free(g);
return;
}
/*
* graph_resize()
*
* Resizes graph g to given size. If size > g->n, the new vertices are
* not connected to any others and their weights are set to 1.
* If size < g->n, the last g->n - size vertices are removed.
*/
void graph_resize(graph_t *g, int size) {
int i;
ASSERT(g!=NULL);
ASSERT(g->n > 0);
ASSERT(size > 0);
if (g->n == size)
return;
/* Free/alloc extra edge-sets */
for (i=size; i < g->n; i++)
set_free(g->edges[i]);
g->edges=realloc(g->edges, size * sizeof(set_t));
for (i=g->n; i < size; i++)
g->edges[i]=set_new(size);
/* Resize original sets */
for (i=0; i < MIN(g->n,size); i++) {
g->edges[i]=set_resize(g->edges[i],size);
}
/* Weights */
g->weights=realloc(g->weights,size * sizeof(int));
for (i=g->n; i<size; i++)
g->weights[i]=1;
g->n=size;
return;
}
/*
* graph_crop()
*
* Resizes the graph so as to remove all highest-valued isolated vertices.
*/
void graph_crop(graph_t *g) {
int i;
for (i=g->n-1; i>=1; i--)
if (set_size(g->edges[i])>0)
break;
graph_resize(g,i+1);
return;
}
/*
* graph_weighted()
*
* Returns TRUE if all vertex weights of graph g are all the same.
*
* Note: Does NOT require weights to be 1.
*/
boolean graph_weighted(graph_t *g) {
int i,w;
w=g->weights[0];
for (i=1; i < g->n; i++)
if (g->weights[i] != w)
return TRUE;
return FALSE;
}
/*
* graph_edge_count()
*
* Returns the number of edges in graph g.
*/
int graph_edge_count(graph_t *g) {
int i;
int count=0;
for (i=0; i < g->n; i++) {
count += set_size(g->edges[i]);
}
return count/2;
}
#if 0
/*
* graph_write_dimacs_ascii_file()
*
* Writes an ASCII dimacs-format file of graph g, with comment, to
* given file.
*
* Returns TRUE if successful, FALSE if an error occurred.
*/
boolean graph_write_dimacs_ascii_file(graph_t *g, char *comment, char *file) {
FILE *fp;
ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
ASSERT(file!=NULL);
if ((fp=fopen(file,"wb"))==NULL)
return FALSE;
if (!graph_write_dimacs_ascii(g,comment,fp)) {
fclose(fp);
return FALSE;
}
fclose(fp);
return TRUE;
}
/*
* graph_write_dimacs_ascii()
*
* Writes an ASCII dimacs-format file of graph g, with comment, to the
* file stream fp.
*
* Returns TRUE if successful, FALSE if an error occurred.
*/
boolean graph_write_dimacs_ascii(graph_t *g, char *comment, FILE *fp) {
int i,j;
ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
ASSERT(graph_test(g,NULL));
ASSERT(fp!=NULL);
if (comment)
fprintf(fp,"c %s\n",comment);
fprintf(fp,"p edge %d %d\n",g->n,graph_edge_count(g));
for (i=0; i < g->n; i++)
if (g->weights[i]!=1)
fprintf(fp,"n %d %d\n",i+1,g->weights[i]);
for (i=0; i < g->n; i++)
for (j=0; j<i; j++)
if (GRAPH_IS_EDGE_FAST(g,i,j))
fprintf(fp,"e %d %d\n",i+1,j+1);
return TRUE;
}
/*
* graph_write_dimacs_binary_file()
*
* Writes a binary dimacs-format file of graph g, with comment, to
* given file.
*
* Returns TRUE if successful, FALSE if an error occurred.
*/
boolean graph_write_dimacs_binary_file(graph_t *g, char *comment, char *file) {
FILE *fp;
ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
ASSERT(file!=NULL);
if ((fp=fopen(file,"wb"))==NULL)
return FALSE;
if (!graph_write_dimacs_binary(g,comment,fp)) {
fclose(fp);
return FALSE;
}
fclose(fp);
return TRUE;
}
/*
* graph_write_dimacs_binary()
*
* Writes a binary dimacs-format file of graph g, with comment, to the
* file stream fp.
*
* Returns TRUE if successful, FALSE if an error occurred.
*/
#define STR_APPEND(s) \
if (headerlength+strlen(s) >= headersize) { \
headersize+=1024; \
header=realloc(header,headersize); \
} \
strncat(header,s,1000); \
headerlength+=strlen(s);
boolean graph_write_dimacs_binary(graph_t *g, char *comment,FILE *fp) {
char *buf;
char *header=NULL;
int headersize=0;
int headerlength=0;
int i,j;
ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
ASSERT(graph_test(g,NULL));
ASSERT(fp!=NULL);
buf=malloc(MAX(1024,g->n/8+1));
header=malloc(1024);
header[0]=0;
headersize=1024;
if (comment) {
strcpy(buf,"c ");
strncat(buf,comment,1000);
strcat(buf,"\n");
STR_APPEND(buf);
}
sprintf(buf,"p edge %d %d\n",g->n,graph_edge_count(g));
STR_APPEND(buf);
for (i=0; i < g->n; i++) {
if (g->weights[i]!=1) {
sprintf(buf,"n %d %d\n",i+1,g->weights[i]);
STR_APPEND(buf);
}
}
fprintf(fp,"%d\n",(int)strlen(header));
fprintf(fp,"%s",header);
free(header);
for (i=0; i < g->n; i++) {
memset(buf,0,i/8+1);
for (j=0; j<i; j++) {
if (GRAPH_IS_EDGE_FAST(g,i,j)) {
buf[j/8] |= SET_BIT_MASK(7-j%8);
}
}
fwrite(buf,1,i/8+1,fp);
}
free(buf);
return TRUE;
}
/*
* graph_read_dimacs_file()
*
* Reads a dimacs-format (ASCII or binary) file from the given file.
*
* Returns a newly allocated graph, or NULL if an error occurred, and an
* error message is printed to stderr.
*/
graph_t *graph_read_dimacs_file(char *file) {
FILE *fp;
graph_t *g;
ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
ASSERT(file!=NULL);
if ((fp=fopen(file,"rb"))==NULL) {
perror(file);
return NULL;
}
g=graph_read_dimacs(fp);
fclose(fp);
return g;
}
/*
* graph_read_dimacs()
*
* Reads a dimacs-format (ASCII or binary) file from the file stream fp.
*
* Returns a newly allocated graph, or NULL if an error occurred, and an
* error message is printed to stderr.
*/
graph_t *graph_read_dimacs(FILE *fp) {
char buffer[1024];
graph_t *g;
char tmp[10];
int n;
ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
ASSERT(fp!=NULL);
if (fgets(buffer,1023,fp)==NULL) {
fprintf(stderr,"Input does not contain any data.\n");
return NULL;
}
if (sscanf(buffer," %d %2s",&n,tmp)!=1) {
g=graph_read_dimacs_ascii(fp,buffer);
} else {
g=graph_read_dimacs_binary(fp,buffer);
}
return g;
}
/*
* parse_input()
*
* Parses the string str for ASCII-format dimacs commands, and modifies
* the graph g accordingly.
*
* Returns TRUE if successful, FALSE if a bad command was encountered.
*
* Note: Ignores all unknown commands. The 'd', 'v' and 'x' commands
* (mainly generator-specific information) are ignored silently,
* for all others a warning message is printed to stderr.
*/
static boolean parse_input(char *str,graph_t *g) {
int i,j,w;
char tmp[16];
for (i=0; i<strlen(str); i++) {
if (!isspace((int)str[i]))
break;
}
if (i>=strlen(str)) /* blank line */
return TRUE;
if (str[i+1]!=0 && !isspace(str[i+1])) /* not 1-char field */
return FALSE;
switch (str[i]) {
case 'c':
return TRUE;
case 'p':
if (g->n != 0)
return FALSE;
if (sscanf(str," p %15s %d %d %2s",tmp,&(g->n),&i,tmp)!=3)
return FALSE;
if (g->n <= 0)
return FALSE;
g->edges=calloc(g->n,sizeof(set_t));
for (i=0; i<g->n; i++)
g->edges[i]=set_new(g->n);
g->weights=calloc(g->n,sizeof(int));
for (i=0; i<g->n; i++)
g->weights[i]=1;
return TRUE;
case 'n':
if ((g->n <= 0) || (g->weights == NULL))
return FALSE;
if (sscanf(str," n %d %d %2s",&i,&w,tmp)!=2)
return FALSE;
if (i<1 || i>g->n)
return FALSE;
if (w<=0)
return FALSE;
g->weights[i-1]=w;
return TRUE;
case 'e':
if ((g->n <= 0) || (g->edges == NULL))
return FALSE;
if (sscanf(str," e %d %d %2s",&i,&j,tmp)!=2)
return FALSE;
if (i<1 || j<1 || i>g->n || j>g->n)
return FALSE;
if (i==j) /* We want antireflexive graphs. */
return TRUE;
GRAPH_ADD_EDGE(g,i-1,j-1);
return TRUE;
case 'd':
case 'v':
case 'x':
return TRUE;
default:
fprintf(stderr,"Warning: ignoring field '%c' in "
"input.\n",str[i]);
return TRUE;
}
}
/*
* graph_read_dimacs_binary()
*
* Reads a dimacs-format binary file from file stream fp with the first
* line being firstline.
*
* Returns the newly-allocated graph or NULL if an error occurred.
*
* TODO: This function leaks memory when reading erroneous files.
*/
static graph_t *graph_read_dimacs_binary(FILE *fp,char *firstline) {
int length=0;
graph_t *g;
int i,j;
char *buffer;
char *start;
char *end;
char **buf;
char tmp[10];
if (sscanf(firstline," %d %2s",&length,tmp)!=1)
return NULL;
if (length<=0) {
fprintf(stderr,"Malformed preamble: preamble size < 0.\n");
return NULL;
}
buffer=malloc(length+2);
if (fread(buffer,1,length,fp)<length) {
fprintf(stderr,"Malformed preamble: unexpected "
"end of file.\n");
free(buffer);
return NULL;
}
g=calloc(1,sizeof(graph_t));
start=buffer;
while (start < buffer+length) {
end=strchr(start,'\n');
if (end==NULL)
end=buffer+length;
end[0]=0;
if (!parse_input(start,g)) {
fprintf(stderr,"Malformed preamble: %s\n",start);
free (buffer);
return NULL;
}
start=end+1;
}
free(buffer);
if (g->n <= 0) {
fprintf(stderr,"Malformed preamble: number of "
"vertices <= 0\n");
free(g);
return NULL;
}
/* Binary part. */
buf=calloc(g->n,sizeof(char*));
for (i=0; i < g->n; i++) {
buf[i]=calloc(g->n,1);
if (fread(buf[i],1,i/8+1,fp) < (i/8+1)) {
fprintf(stderr,"Unexpected end of file when "
"reading graph.\n");
return NULL;
}
}
for (i=0; i < g->n; i++) {
for (j=0; j<i; j++) {
if (buf[i][j/8]&(1<<(7-(j%8)))) {
GRAPH_ADD_EDGE(g,i,j);
}
}
free(buf[i]);
}
free(buf);
return g;
}
/*
* graph_read_dimacs_ascii()
*
* Reads a dimacs-format ASCII file from file stream fp with the first
* line being firstline.
*
* Returns the newly-allocated graph or NULL if an error occurred.
*
* TODO: This function leaks memory when reading erroneous files.
*/
static graph_t *graph_read_dimacs_ascii(FILE *fp, char *firstline) {
graph_t *g;
char buffer[1024];
g=calloc(1,sizeof(graph_t));
if (!parse_input(firstline,g)) {
fprintf(stderr,"Malformed input: %s",firstline);
free(g);
return NULL;
}
while (fgets(buffer,1023,fp)) {
if (!parse_input(buffer,g)) {
fprintf(stderr,"Malformed input: %s",buffer);
return NULL;
}
}
if (g->n <= 0) {
free(g);
fprintf(stderr,"Unexpected end of file when reading graph.\n");
return NULL;
}
return g;
}
#endif
#ifndef USING_R
/*
* graph_print()
*
* Prints a representation of the graph g to stdout (along with any errors
* noticed). Mainly useful for debugging purposes and trivial output.
*
* The output consists of a first line describing the dimensions and then
* one line per vertex containing the vertex number (numbered 0,...,n-1),
* the vertex weight (if the graph is weighted), "->" and then a list
* of all vertices it is adjacent to.
*/
void graph_print(graph_t *g) {
int i,j;
int asymm=0;
int refl=0;
int nonpos=0;
int extra=0;
unsigned int weight=0;
boolean weighted;
ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
if (g==NULL) {
printf(" WARNING: Graph pointer is NULL!\n");
return;
}
if (g->n <= 0) {
printf(" WARNING: Graph has %d vertices "
"(should be positive)!\n",g->n);
return;
}
weighted=graph_weighted(g);
printf("%s graph has %d vertices, %d edges (density %.2f).\n",
weighted?"Weighted":((g->weights[0]==1)?
"Unweighted":"Semi-weighted"),
g->n,graph_edge_count(g),
(float)graph_edge_count(g)/((float)(g->n - 1)*(g->n)/2));
for (i=0; i < g->n; i++) {
printf("%2d",i);
if (weighted) {
printf(" w=%d",g->weights[i]);
if (g->weights[i] <= 0) {
printf("*NON-POSITIVE*");
nonpos++;
}
}
if (weight < INT_MAX)
weight+=g->weights[i];
printf(" ->");
for (j=0; j < g->n; j++) {
if (SET_CONTAINS_FAST(g->edges[i],j)) {
printf(" %d",j);
if (i==j) {
printf("*REFLEXIVE*");
refl++;
}
if (!SET_CONTAINS_FAST(g->edges[j],i)) {
printf("*ASYMMERTIC*");
asymm++;
}
}
}
for (j=g->n; j < SET_ARRAY_LENGTH(g->edges[i])*ELEMENTSIZE;
j++) {
if (SET_CONTAINS_FAST(g->edges[i],j)) {
printf(" %d*NON-EXISTENT*",j);
extra++;
}
}
printf("\n");
}
if (asymm)
printf(" WARNING: Graph contained %d asymmetric edges!\n",
asymm);
if (refl)
printf(" WARNING: Graph contained %d reflexive edges!\n",
refl);
if (nonpos)
printf(" WARNING: Graph contained %d non-positive vertex "
"weights!\n",nonpos);
if (extra)
printf(" WARNING: Graph contained %d edges to "
"non-existent vertices!\n",extra);
if (weight>=INT_MAX)
printf(" WARNING: Total graph weight >= INT_MAX!\n");
return;
}
#endif
/*
* graph_test()
*
* Tests graph g to be valid. Checks that g is non-NULL, the edges are
* symmetric and anti-reflexive, and that all vertex weights are positive.
* If output is non-NULL, prints a few lines telling the status of the graph
* to file descriptor output.
*
* Returns TRUE if the graph is valid, FALSE otherwise.
*/
boolean graph_test(graph_t *g,FILE *output) {
int i,j;
int edges=0;
int asymm=0;
int nonpos=0;
int refl=0;
int extra=0;
unsigned int weight=0;
boolean weighted;
ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
if (g==NULL) {
if (output)
fprintf(output," WARNING: Graph pointer is NULL!\n");
return FALSE;
}
weighted=graph_weighted(g);
for (i=0; i < g->n; i++) {
if (g->edges[i]==NULL) {
if (output)
fprintf(output," WARNING: Graph edge set "
"NULL!\n"
" (further warning suppressed)\n");
return FALSE;
}
if (SET_MAX_SIZE(g->edges[i]) < g->n) {
if (output)
fprintf(output," WARNING: Graph edge set "
"too small!\n"
" (further warnings suppressed)\n");
return FALSE;
}
for (j=0; j < g->n; j++) {
if (SET_CONTAINS_FAST(g->edges[i],j)) {
edges++;
if (i==j) {
refl++;
}
if (!SET_CONTAINS_FAST(g->edges[j],i)) {
asymm++;
}
}
}
for (j=g->n; j < SET_ARRAY_LENGTH(g->edges[i])*ELEMENTSIZE;
j++) {
if (SET_CONTAINS_FAST(g->edges[i],j))
extra++;
}
if (g->weights[i] <= 0)
nonpos++;
if (weight<INT_MAX)
weight += g->weights[i];
}
edges/=2; /* Each is counted twice. */
if (output) {
/* Semi-weighted means all weights are equal, but not 1. */
fprintf(output,"%s graph has %d vertices, %d edges "
"(density %.2f).\n",
weighted?"Weighted":
((g->weights[0]==1)?"Unweighted":"Semi-weighted"),
g->n,edges,(float)edges/((float)(g->n - 1)*(g->n)/2));
if (asymm)
fprintf(output," WARNING: Graph contained %d "
"asymmetric edges!\n",asymm);
if (refl)
fprintf(output," WARNING: Graph contained %d "
"reflexive edges!\n",refl);
if (nonpos)
fprintf(output," WARNING: Graph contained %d "
"non-positive vertex weights!\n",nonpos);
if (extra)
fprintf(output," WARNING: Graph contained %d edges "
"to non-existent vertices!\n",extra);
if (weight>=INT_MAX)
fprintf(output," WARNING: Total graph weight >= "
"INT_MAX!\n");
if (asymm==0 && refl==0 && nonpos==0 && extra==0 &&
weight<INT_MAX)
fprintf(output,"Graph OK.\n");
}
if (asymm || refl || nonpos || extra || weight>=INT_MAX)
return FALSE;
return TRUE;
}
/*
* graph_test_regular()
*
* Returns the vertex degree for regular graphs, or -1 if the graph is
* not regular.
*/
int graph_test_regular(graph_t *g) {
int i,n;
n=set_size(g->edges[0]);
for (i=1; i < g->n; i++) {
if (set_size(g->edges[i]) != n)
return -1;
}
return n;
}