#!/usr/bin/python
###########################################################################
#
#   Prevoz - graf za problem m misijonarjev in k ljudozercev
#
#   import sys; wdir = r'D:\2008\Python\DMFA'; sys.path.append(wdir)
#
#   import Prevoz;  Prevoz.run(wdir,2,2)
#   reload(Prevoz); Prevoz.run(wdir,2,2)
#
#   Vladimir Batagelj,  17. januar 2008
#
###########################################################################

import string, os, sys, datetime

def dopustna(m,k):
   global mm, km
   return (0<=m) and (m<=mm) and (0<=k) and (k<=km) and ((m==0) or (m>=k))

def run(wdir,m0=2,k0=2):
   global mm, km
   mm = m0; km=k0
   ime = 'prevoz'+str(mm)+'-'+str(km)
   print "\n*** Prevoz\nV. Batagelj, 17. januar 2008 / 17. januar 2008\n"
   print "Prevoz ",mm,":",km
   vtx  = open(wdir+'\\'+ime+'.vtx', 'w')
   edg  = open(wdir+'\\'+ime+'.edg', 'w')
   vtx.write('% '+ime+' - ' + datetime.datetime.now().ctime()+"\n")
   vtx.write('*vertices \n')
   znane = {}; s = ('L',mm,km); znane[s] = 1
   vtx.write(str(1)+' "(L,'+str(mm)+','+str(km)+')"\n')
   s = ('D',0,0); znane[s] = 2
   vtx.write(str(2)+' "(D,0,0)"\n')
   odprta = znane.keys()
   tock = 2; i = 0
   pomik = [(0,2),(1,1),(0,1),(1,0),(2,0)]
   for u,v in pomik:
      i = i+1
      edg.write('*edges :'+str(i)+' "('+str(u)+','+str(v)+')"\n')
   edg.write('*edges\n')
   while odprta != []:
      s = odprta[0]; odprta = odprta[1:]
      stran = s[0]; m = s[1]; k = s[2]
      if stran == 'L': nova = 'D'
      else: nova = 'L'
      t = znane[s]; i = 0
      for u,v in pomik:
         i = i+1
         if stran == 'L':
            p = m-u; q = k-v
         else:
            p = m+u; q = k+v
         if dopustna(p,q) and dopustna(mm-p,km-q):
            ns = (nova,p,q)
            if not znane.has_key(ns):
               tock = tock + 1; w = tock; znane[ns] = tock
               odprta.append(ns)
               vtx.write(str(w)+' "('+str(nova)+','+str(p)+','+str(q)+')"\n')
            else:
               w = znane[(nova,p,q)]
            edg.write(str(i)+': '+str(t)+' '+str(w)+'\n')
   vtx.close(); edg.close()
   print "konec"
# --------------------------