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