program trnsfm c this program transforms a graph given by its adjacency list c i j c into a form suitable for the bisection program c it is setup so that the edges can be given in an arbitrary c order, also i>j is allowed c the max degree of any node is set (arbitrarily) to 30 c if you have a graph with max-degree larger than that, just change c the dimension, or write your own program to transform c the input for this program is as follows c first line: nodes nedges (= number nodes, number of edges) c then comes a list of size: nedges c node1( i) node2( i) , i=1,...,nedges parameter( nmax = 5000, ndeg = 30) c note that i set the max degree ndeg to 30, change it if necessary integer*2 icol( nmax), nb( nmax, ndeg) character*20, infile, outfil print *,'filename :' read '(a20)', infile print *,'outputfile:' read '(a20)', outfil open( 4, file = infile, status = 'old') read(4,*) nodes,nedges write(6, *) ' nodes, edges =' ,nodes, nedges if (nodes .gt. nmax) then print *,'n too large' stop endif n1 = nodes if ((nodes/2)*2 .ne. nodes) then print *, 'node number odd, .. increase..by one' n1 = nodes + 1 endif do 200 i = 1,nodes icol( i) = 0 200 continue open( 5, file = outfil, status = 'unknown') write(5,302) n1, nodes-1,nedges 302 format(1x,i6,i6,i7) istop = 0 maxdeg = 0 c now run through all edges do 300 i =1, nedges read(4,*) i1,j if ( i1 .gt. j) then itmp = i1 i1 = j j = itmp endif icol( i1) = icol( i1) + 1 if (icol( i1) .gt. ndeg) then istop = 1 if (maxdeg .lt. icol(i1)) maxdeg = icol(i1) endif if (istop .eq. 0) nb( i1, icol( i1)) = j 300 continue close( 4) if (istop .eq. 1) then print *, ' largest degree is ', maxdeg print *, ' nothing done! ' stop endif 301 format(1x,2i6) write( 5, 305) (icol(i), i=1,nodes-1) 305 format(20i4) do 340 i=1,nodes-1 if (icol( i) .gt. 0) then do 342 j = 1, icol( i) c here the 1 represents the weight 1, if you have weights c you have to read them and place them here correctly write(5,306) nb(i,j),1 342 continue endif 306 format(1x,i5,i2) 340 continue close( 5) end