#! /bin/sh # This is a shell archive, meaning: # 1. Remove everything above the #! /bin/sh line. # 2. Save the resulting text in a file. # 3. Execute the file with /bin/sh (not csh) to create: # README # glib.c # graphtypes.h # input.form # main.c # makefile # match.c # output.form # test.in # This archive created: Thu Feb 21 19:34:59 EST 1991 export PATH; PATH=/bin:/usr/bin:/usr/ucb:/usr/bin:/etc:/usr/etc:/usr/local/X11R4/bin:/usr/local/bin:/dimacs/u2/badics/bin:/dimacs/u2/badics/out:/usr/lib/news:. if test -f 'README' then echo shar: "will not over-write existing file 'README'" else cat << \SHAR_EOF > 'README' ------------------------------------------------------------------------- The Match_C.shell file contains a program, written in C, for finding MAXIMUM-CARDINALITY MATCHING in UNDIRECTED graphs. ------------------------------------------------------------------------- This program was written by Ed Rothberg to implement H. Gabow's N-cubed non-weighted matching algorithm. For an explanation of the algorithm see JACM 23, pp221-34 . MAIN PROGRAMS: - match REQUIRED FILES: README input.form output.form makefile graphtypes.h glib.c main.c match.c TO GET THESE FILES: Run the "Match_C.shell" file in the /bin/sh shell. (It will unwrap itself.) FILE DESCRIPTIONS: input.form: Describes the input formats for match. output.form: Describes output formats for match. ***Format converters will be available soon to translate input and output files from and to the DIMACS Challenge format. Contributions are welcome. test.in: A sample input for match The others are source code files written in C language. HOW TO MAKE THE PROBLEM-SOLVERS: match: Solves maximum matching for undirected graphs presented in an adjacency-list format. Requires: graphtypes.h glib.c main.c match.c makefile To compile: $make To invoke: $match input_file If no filename is given, a small help message appears. It always writes to standard out. / This README file was written by DIMACS, and based on experiments with the codes. / SHAR_EOF fi if test -f 'glib.c' then echo shar: "will not over-write existing file 'glib.c'" else cat << \SHAR_EOF > 'glib.c' #include "graphtypes.h" #include #include AddEdge (g,n,m,label) Graph g; int n,m,label; { Edge edge1,edge2; edge1 = (Edge) malloc(2*sizeof(struct edge_ent)); edge2 = edge1 + 1; edge1->label = label; edge1->endpoint = m; edge1->otheredge = edge2; edge1->prevedge = NULL; edge1->nextedge = g[n].adj_list; if (edge1->nextedge != NULL) edge1->nextedge->prevedge = edge1; g[n].adj_list = edge1; g[n].degree++; edge2->label = label; edge2->endpoint = n; edge2->otheredge = edge1; edge2->prevedge = NULL; edge2->nextedge = g[m].adj_list; if (edge2->nextedge != NULL) edge2->nextedge->prevedge = edge2; g[m].adj_list = edge2; g[m].degree++; } Edge FindEdge(graph,i,j) Graph graph; int i,j; { Edge edge; edge = graph[i].adj_list; while (edge!=NULL && edge->endpoint!=j) edge = edge->nextedge; if (edge==NULL) return(NULL); else return(edge); } int RemoveEdge(graph,edge) Graph graph; Edge edge; { Edge other; int i,j; if (edge==NULL) return(0); other = edge->otheredge; i = other->endpoint; j = edge->endpoint; graph[i].degree--; graph[j].degree--; if (edge->prevedge == NULL) { graph[i].adj_list = edge->nextedge; if (edge->nextedge != NULL) edge->nextedge->prevedge = NULL; } else if (edge->nextedge == NULL) (edge->prevedge)->nextedge = NULL; else { (edge->nextedge)->prevedge = edge->prevedge; (edge->prevedge)->nextedge = edge->nextedge; } if (other->prevedge == NULL) { graph[j].adj_list = other->nextedge; if (other->nextedge != NULL) other->nextedge->prevedge = NULL; } else if (other->nextedge == NULL) (other->prevedge)->nextedge = NULL; else { (other->nextedge)->prevedge = other->prevedge; (other->prevedge)->nextedge = other->nextedge; } free((edge < other) ? edge : other); return(1); } int NumEdges(g) Graph g; { int i,size,edges; edges = 0; size = Degree(g,0); for (i=1; i<=size; i++) edges += Degree(g,i); edges /= 2; return(edges); } Graph NewGraph(size) int size; { Graph tmp; int i; tmp = (Graph) malloc((size+1)*sizeof(struct node_entry)); for (i=1; i<=size; i++) { Degree(tmp,i) = 0; FirstEdge(tmp,i) = NULL; NLabel(tmp,i) = i; } Degree(tmp,0) = size; return(tmp); } EuclidGraph NewEuclid(size) int size; { EuclidGraph xy; xy = (EuclidGraph) malloc((size+1)*2*sizeof(int)); xy[0][0] = size; return(xy); } MatrixGraph NewMatrix(size) int size; { MatrixGraph graph; int i; graph = (MatrixGraph) malloc((size*(size+1)+1)*sizeof(int)); graph[0] = size; for (i=1; i<=size; i++) /* zero the diagonal */ graph[i*(size+1)] = 0; return(graph); } Graph CopyGraph(g) Graph g; { int i,j,size; Edge edge; Graph cp; size = Degree(g,0); cp = NewGraph(size); for (i=1; i<=size; i++) { Xcoord(cp,i) = Xcoord(g,i); Ycoord(cp,i) = Ycoord(g,i); edge = FirstEdge(g,i); for (j=1; j<=Degree(g,i); j++) { if (i < EndPoint(edge)) AddEdge(cp,i,EndPoint(edge),ELabel(edge)); edge = NextEdge(edge); } } return (cp); } /* Graph I/O routines */ Graph ReadGraph (size,file) int *size; char file[]; { Graph graph; FILE *fp; char c; int edges, degree, vlabel, elabel, adj_node, i, j; int xcoord, ycoord; if (file[0] == '\0') fp = stdin; else fp = fopen(file,"r"); if (fp==NULL) { printf("ReadGraph: file %s can't be opened\n",file); exit(0); } fscanf(fp,"%d%d %c",size,&edges,&c); if (c !='U' && c!='u') { printf("ReadGraph: file %s does not contain an undirected graph\n",file); exit(0); } while (getc(fp)!='\n') ; graph = NewGraph(*size); for (i = 1; i <= *size; ++i) { fscanf(fp,"%d%d%d%d",°ree,&vlabel,&xcoord,&ycoord); NLabel(graph,i) = vlabel; Xcoord(graph,i) = xcoord; Ycoord(graph,i) = ycoord; while (getc(fp)!='\n') ; for (j = 1; j <= degree; ++j) { fscanf(fp,"%d%d", &adj_node, &elabel); while (getc(fp)!='\n') ; if (i>1; l = (l + k/l)>>1; l = (l + k/l)>>1; l = (l + k/l)>>1; return ((l*l .000000001) ? l+1 : l); } int eucdistsq(graph,i,j) /* Find the square of the dist between two points */ EuclidGraph graph; int i,j; { register int dv,dh; dv = graph[i][0]-graph[j][0]; dh = graph[i][1]-graph[j][1]; return(dv*dv+dh*dh); } SHAR_EOF fi if test -f 'graphtypes.h' then echo shar: "will not over-write existing file 'graphtypes.h'" else cat << \SHAR_EOF > 'graphtypes.h' #define INF 100000000 #define NULL 0 struct node_entry { int degree; int label; int x; int y; struct edge_ent *adj_list; }; typedef struct node_entry *Graph; struct edge_ent { int endpoint; int label; int label2; struct edge_ent *nextedge; struct edge_ent *prevedge; struct edge_ent *otheredge; }; typedef struct edge_ent *Edge; extern Graph ReadGraph(),NewGraph(),CopyGraph(); extern int RemoveEdge(),NumEdges(); extern Edge FindEdge(); #define Degree(graph,n) (graph[n].degree) #define NLabel(graph,n) (graph[n].label) #define Xcoord(graph,n) (graph[n].x) #define Ycoord(graph,n) (graph[n].y) #define FirstEdge(graph,n) (graph[n].adj_list) #define EndPoint(e) (e->endpoint) #define ELabel(e) (e->label) #define ELabel2(e) (e->label2) #define Other(e) (e->otheredge) #define NextEdge(e) (e->nextedge) extern Graph Prim(); extern int *EulerTraverse(),*Match(),*Weighted_Match(),*Dijkstra(),*Concomp(); /* Euclidean graph type */ typedef int (*EuclidGraph)[2]; extern Graph EuclidPrim(); extern EuclidGraph ReadEuclid(),NewEuclid(); extern int eucdist(),eucdistsq(); extern int *CvxHull(); /* Distance matrix graph type */ typedef int *MatrixGraph; extern int *MatrixDijkstra(); extern Graph MatrixPrim(); extern Graph MatrixMaxFlow(); extern MatrixGraph ReadMatrix(), NewMatrix(); SHAR_EOF fi if test -f 'input.form' then echo shar: "will not over-write existing file 'input.form'" else cat << \SHAR_EOF > 'input.form' Disclaimer: the following description was obtained by inspection of the code and some simple tests. It was not written by the implementor. CCM There will soon be available a program for translating from the DIMACS standard format to this format. Contributions are welcome. CCM ------------------------------------------------------------------------- INPUT FORMAT FOR MATCH: ------------------------------------------------------------------------- Graph I/O is performed by a generic graph library package, so some of the fields are ignored by the "match" code (but you must include dummy fields in the input). There are three types of lines: the first line, vertex lines, and edge lines. The fields in each line type are as follows. First line-> size edges U size: integer giving number of vertices edges: integer giving number of edges U: character ``U'' or ``u'' specifying an undirected graph Vertex lines-> degree vlabel xcoord ycoord degree: edge degree of the vertex vlabel: vertex label (ignored--vertices are referred to by index) xcoord: integer x-coordinate location (ignored) ycoord: integer y-coordinate location (ignored) *****Each vertex line is followed immediately by the lines for all its adjacent edges (thus each edge appears twice, once for each vertex).****** Edge lines-> adjacent label adjacent: index (not vlabel) of the adjacent vertex label: integer edge label (ignored) SHAR_EOF fi if test -f 'main.c' then echo shar: "will not over-write existing file 'main.c'" else cat << \SHAR_EOF > 'main.c' #include "graphtypes.h" main(argc,argv) int argc; char *argv[]; { int *Mate; Graph graph; int i,size; graph = ReadGraph(&size,argv[1]); Mate = Match(graph); for (i=1; i<=size; i++) printf("%d %d\n",i,Mate[i]); } SHAR_EOF fi if test -f 'makefile' then echo shar: "will not over-write existing file 'makefile'" else cat << \SHAR_EOF > 'makefile' match: main.o match.o glib.o cc -o match main.o match.o glib.o -lm SHAR_EOF fi if test -f 'match.c' then echo shar: "will not over-write existing file 'match.c'" else cat << \SHAR_EOF > 'match.c' /* N-cubed Non-weighted matching */ /* Implementation of H. Gabow's labelling scheme */ /* For an explanation of the algorithm see JACM 23, pp221-34 */ /* Written by Edward Rothberg 6/85 */ #include "graphtypes.h" struct adj { int edge; struct adj *next; }; static struct adj **adj_list; static struct adj *space; static int U, V; /* U = no. of nodes, V = no. of edges */ static int *MATE; /* stores the mate of each vertex. 0 if vertex is exposed */ static int *FIRST; /* first non-outer vertex in the path back to the start of */ /* the search */ static int *LABEL; /* multi-purpose label */ static int *OUTER; /* queue of outer vertices to be searched */ static int *END; /* stores endpoints of edges */ static int qcount = 0; int *Match (graph) Graph graph; { int x,y,i,u,v,qptr=0; struct adj *p; U = Degree(graph,0); V = NumEdges(graph); /* set up matching data structure */ Initialize (graph); /* start off with a greedy matching */ Greedy(); /* search for an augmenting path from each exposed node */ for (u=1; u<=U; ++u) { if (MATE[u] != 0) continue; OUTER[++qcount] = u; LABEL[u] = 0; while (qcount != qptr) { /* while queue is not empty */ x = OUTER[++qptr]; p = adj_list[x]; while (p != NULL) { /* y is adjacent to an outer vertex */ y = (END[p->edge]==x) ? END[p->edge-1] : END[p->edge]; if (MATE[y] == 0 && y != u) { /* found an augmenting path */ MATE[y] = x; REMATCH(x,y); qptr = qcount; break; } else if (LABEL[y] >= 0) { /* created a blossom */ DOLABEL(x,y); } else { /* extended the search path */ v = MATE[y]; if (LABEL[v] < 0) { LABEL[v] = x; FIRST[v] = y; OUTER[++qcount] = v; } } p = p->next; } } for (i=0; i<=U; ++i) LABEL[i] = -1; qcount = 0; qptr = 0; } FreeUp(); return(MATE); } /* take input graph and set up matching data structure. Matching uses a */ /* structure where each edge has a number, and the adjacency list entry */ /* for an edge contains that number */ Initialize (graph) Graph graph; { int i, j; int allocsize; int currentedge,adj_node; Edge edge; struct adj *p; currentedge = U+2; END = (int *) malloc((U+2*V+1)*(sizeof(int))); adj_list = (struct adj **) malloc((U+1)*(sizeof(struct adj *))); for (i=1; i<=U; i++) adj_list[i] = NULL; space = (struct adj *) malloc(2*V*sizeof(struct adj)); p = space; for (i = 1; i <= U; ++i) { edge = FirstEdge(graph,i); for (j = 1; j <= Degree(graph,i); ++j) { adj_node = EndPoint(edge); if (i < adj_node) { END[currentedge-1] = i; END[currentedge] = adj_node; p->edge = currentedge; p->next = adj_list[i]; adj_list[i]=p++; p->edge = currentedge; p->next = adj_list[adj_node]; adj_list[adj_node] = p++; currentedge += 2; } edge = NextEdge(edge); } } allocsize = (U+1)*(sizeof(int)); FIRST = (int *) malloc(allocsize); MATE = (int *) malloc(allocsize); LABEL = (int *) malloc(allocsize); OUTER = (int *) malloc(allocsize); for (i = 0; i <= U; ++i) { LABEL[i] = -1; FIRST[i] = 0; MATE[i] = 0; } } FreeUp () { free(adj_list); free(space); free(END); free(FIRST); free(LABEL); free(OUTER); } /* greedy matching. If a vertex is unmatched, check all adjacent vertices */ /* to see if any of them are also unmatched. If so, match them. */ Greedy() { struct adj *p; int i,adj_node; for (i=1; i<=U; i++) { if (MATE[i]!=0) continue; p = adj_list[i]; while (p!=NULL) { adj_node = (END[p->edge]!=i) ? END[p->edge] : END[p->edge-1]; if (MATE[adj_node]==0) { MATE[i] = adj_node; MATE[adj_node] = i; break; } p = p->next; } } } /* Augment the matching along the augmenting path defined by LABEL */ REMATCH(v,w) int v,w; { int t,x,y; t = MATE[v]; MATE[v] = w; if (MATE[t] != v) return; else if (LABEL[v] <= U) { MATE[t] = LABEL[v]; REMATCH (LABEL[v], t); return; } else { x = END[LABEL[v]]; y = END[LABEL[v]-1]; REMATCH (x, y); REMATCH (y, x); return; } } /* Make all non-outer vertices in the blossom outer */ LabelSub (v,edge,join) int v,edge,join; { while (v != join) { LABEL[v] = edge; FIRST[v] = join; OUTER[++qcount] = v; v = FIRST[LABEL[MATE[v]]]; } } /* return the number of the edge between x and y */ Findedge (x,y) int x,y; { int edge; struct adj *p; p = adj_list[x]; while (p != NULL) { edge = p->edge; if (END[edge] == y || END[edge-1] == y) return(edge); p = p->next; } return(0); } /* x and y are adjacent and both are outer. Create a blossom. */ DOLABEL (x,y) int x,y; { int r,s; int edge, flag, join; register temp; edge = Findedge (x,y); flag = -edge; r = FIRST[x]; s = FIRST[y]; if (r == s) return; LABEL[r] = flag; LABEL[s] = flag; if (s != 0) { temp = r; r = s; s = temp; } r = FIRST[LABEL[MATE[r]]]; while (LABEL[r] != flag) { LABEL[r] = flag; if (s != 0) { temp = r; r = s; s = temp; } r = FIRST[LABEL[MATE[r]]]; } join = r; LabelSub(FIRST[x], edge, join); LabelSub(FIRST[y], edge, join); for (s = 1; s <= qcount; s++) if (LABEL[FIRST[OUTER[s]]] > 0) FIRST[OUTER[s]] = join; } SHAR_EOF fi if test -f 'output.form' then echo shar: "will not over-write existing file 'output.form'" else cat << \SHAR_EOF > 'output.form' Disclaimer: the following description was obtained by inspection of the code and some simple tests. It was not written by the implementor. CCM There will soon be available a program for translating from this output format to the DIMACS standard format. Contributions are welcome. CCM ---------------------------------------------------------------------- OUTPUT FORMAT FOR WMATCH ---------------------------------------------------------------------- The i-th line: Contains the i-th vertex and its mate. If the first entry is 0, the i-th vertex is unmatched. For example: 1 3 2 4 3 1 4 2 5 6 6 5 SHAR_EOF fi if test -f 'test.in' then echo shar: "will not over-write existing file 'test.in'" else cat << \SHAR_EOF > 'test.in' 6 8 U 2 3 0 0 2 6 3 8 3 3 0 0 1 6 5 3 4 6 3 3 0 0 1 8 4 3 5 3 3 3 0 0 2 6 3 3 6 8 3 3 0 0 3 3 2 3 6 6 2 3 0 0 4 8 5 6 SHAR_EOF fi exit 0 # End of shell archive