#!/usr/bin/python
# -*- coding: utf-8 -*-
"""
Graphgen generates a rectangular graph in the METIS graph format

  Usage:
    Graphgen.py n       --  generate a square n x n graph
    Graphgen.py n m     --  generate a n x m graph

'n' and 'm' must be integers
"""

__author__ = """Florian Wilhelm (Florian.Wilhelm@kit.edu)"""
__date__ = """26.03.2009"""

import sys

if len(sys.argv) <= 1:
	print __doc__
	sys.exit(1)
elif len(sys.argv) == 2:
	u = int(sys.argv[1])
	v = u
elif len(sys.argv) >= 3:
	u, v = int(sys.argv[1]), int(sys.argv[2])

filename = "graph-%sx%s"%(u,v)
vertices = u * v
edges = u * (v - 1) + v * (u - 1)

fh = open(filename, 'w')
fh.writelines("%s %s\n"%(vertices, edges))

for line in range(1, vertices + 1):
	neighbors = [line - 1, line - v, line + v, line + 1]
	if line % v == 1 or v == 1: # left border
		neighbors.remove(line - 1)
	if line % v == 0: # right border
		neighbors.remove(line + 1)
	if line <= v: # lower border
		neighbors.remove(line - v)
	if line > u*v - v: # upper border
		neighbors.remove(line + v)
	neighbors = map(str, neighbors)
	fh.writelines(" ".join(neighbors) + "\n")

fh.close()