mcolor.java

四色问题以及推广为M色问题的算法实现

//
//程序名称：图形染色问题
//程序用途：算法分析与设计上机实验
//程序作者：张焕人
//作者邮箱: [e-mail]  
//          [e-mail]
//作者QQ：27949278
//


import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.RandomAccessFile;

public class Mcolor
{   
	private static boolean[][] adjMat;
	private static int VertsNum;
	private static int ColorsNum;
	private static int minCNum;
	private static int color[];
	private static int MethodNum=0;
	private static boolean found=false;
	public static void initGraph(int num)
	{
		
		adjMat = new boolean[num][num];
		color=new int[num];
		for(int y=0; y<num; y++)      // set adjacency
		{	color[y]=0;
			for(int x=0; x<num; x++)   //    matrix to 0
				adjMat[x][y] = false;
		}
	}
	
	public static String getUserCommand()
	{
		String s = "";
		try
		{
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			s = br.readLine();
			
		}
		catch(IOException e)
		{
			
		}
		return s;
	}
	
	public static void readGraph(){
		File currentDir = new File(".\\");
		String filename;
		String file;
		
		try {
		   System.out.print("请输入要打开的数据文件(直接回车选定默认文件map.txt)：");
		   file=getUserCommand();
		   if (file.length()==0)
			   filename=currentDir.getCanonicalPath()+"\\"+"map.txt";
		   else filename=currentDir.getCanonicalPath()+"\\" + file;	         
		   RandomAccessFile raf= new RandomAccessFile( filename,"r" );
							
			while(raf.length()==0) 
			{ 
				System.out.println("输入有误或相应的记录不存在！");
			    System.out.println("按任意键重新输入...");
			    file=getUserCommand();
				   if (file.length()==0)
					   filename=currentDir.getCanonicalPath()+"\\"+"map.txt";
				   else filename=currentDir.getCanonicalPath()+"\\" + file;	         
				raf= new RandomAccessFile( filename,"r" );
			}
			
			int start,end;
			
			VertsNum=Integer.parseInt(raf.readLine());
			System.out.println("图中共有顶点数目："+VertsNum);
			initGraph(VertsNum);
			
			String tmp;  
			
			while(raf.getFilePointer()!=raf.length())
			{   
				tmp=raf.readLine();
				start=Integer.parseInt(tmp.split(" ")[0])-1;  //the array starts with '0'
			    end=Integer.parseInt(tmp.split(" ")[1])-1;   //一定要类型匹配
			    adjMat[start][end]=true;
			    adjMat[end][start]=true;
			    
			}
			System.out.println("成功打开文件"+filename);
			
			} catch (FileNotFoundException e) {
				System.out.println("相应的文件不存在! 请重新输入...");
				readGraph();
			}
			catch (IOException e) {
				e.printStackTrace();
			}
	}
	
	public static void showAdjMat()
	{   System.out.println("图的邻接矩阵表示形式如下：");
		for(int i=0;i<VertsNum;i++)
		{ 
			for(int j=0;j<VertsNum;j++)
			{   if(adjMat[i][j])  System.out.print(" "+1); 
			       else  System.out.print(" "+0);
			}
		    System.out.println();
		}
	}
	
	public static void print(int[] x)
	{ MethodNum++;
	  System.out.print("染色方法"+MethodNum+": ");
	  for(int i=0;i<x.length;i++)
	  {
		System.out.print(x[i]+" ");  
	  }	
	  System.out.println();
	}
	
	public static void initColor()
	{   
		found=false;
		MethodNum=0;
		for(int i=0;i<VertsNum;i++)
			color[i]=0;
	}
	
	public static void coloring(int k)
	{
	  
	  while(true)
	  {
	   nextValue(k);
	   if (color[k]==0) break;    //第k点无法着色,说明这个图无法着色.  
	   if (k==VertsNum-1) 
	      		   print(color);
	     else coloring(k+1);   //第k点能着色,考虑下一个点,递归调用
	  }
	}
	
	public static void coloring(int k,int det)
	{   
		while(true)
		  {
		   nextValue(k);
		   if (color[k]==0) break;    //第k点无法着色,说明这个图无法着色.  
		   if (k==VertsNum-1) 
		   { 
			   found=true;
			   for(int i=0;i<VertsNum;i++)  //统计需要的颜色数目
			   	   if(minCNum<color[i]) minCNum=color[i];
			       return;
		  }
		      
		     else 
		    	 {   coloring(k+1,1);   //第k点能着色,考虑下一个点,递归调用
		    	     if(found) return;
		    	 }
		  }
	}
	
		
	public static void nextValue(int k)
	{
	 int j;
     while(true)
     {
    	 color[k]=(color[k]+1)%(ColorsNum+1);
         if (color[k]==0) return;   //表示m种都已试过!
         for(j=0;j<VertsNum;j++)  
         if (adjMat[k][j]&& color[k]==color[j]) break ;
              //退出FOR循环
         if(j==VertsNum) return; //表示第k点可着色返回color(k)
     }
      
	}
	
	 public static void showMainMenu()
	  {
	    System.out.println("\n\n\n*****************************************************************************");
	    System.out.println("**********                  1      查看邻接矩阵                         **********");
	    System.out.println("**********                  2    重新读取图形数据                       **********");
	    System.out.println("**********                  3    重新设置颜色数目                       **********");
	    System.out.println("**********                  4      查看染色结果                       **********");
	    System.out.println("**********                  0         退出                             **********");
	    System.out.println("*****************************************************************************");
	  }	

	public static void main(String[] args)
	{
		System.out.println("\n\n\n\n\n\n\n\n\n");
	    System.out.println(" \t\t\t\t             欢迎运行染色算法展示程序\n");
	    System.out.println(" \t\t\t\tcopyright@2005-2008  author 张焕人  company 中南大学");
	    getUserCommand();
	    System.out.println("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");	   
	    System.out.println("按任意键继续...");
	      getUserCommand();
	      readGraph();
//	      System.out.print("请输入您想要给地图染色的颜色数目：");
//			String tmp=getUserCommand();
//			ColorsNum=Integer.parseInt(tmp);
		ColorsNum=VertsNum;
		initColor();
		coloring(0,1);
		System.out.println("成功对此图染色共需要颜色数目："+minCNum);
		ColorsNum=minCNum;
	    while( true )
	    { 
	      System.out.println("按任意键继续...");
	      getUserCommand();
	      showMainMenu();
	      System.out.print("请输入要选择的功能项：");
	      String cmd = getUserCommand();
	      if( cmd.equalsIgnoreCase("0") == true )
	        { System.out.print("确认要退出吗(Y)？");
	          getUserCommand();
	          System.out.println("谢谢您的使用，再见！");
	      	  break;}
	      else if ( cmd.equalsIgnoreCase("1") == true )
	      {
	      	showAdjMat();
	      }
	      else if( cmd.equalsIgnoreCase("2") == true )
	      {
	      	readGraph();
	      	ColorsNum=VertsNum;
			initColor();
			coloring(0,1);
			System.out.println("成功对此图染色共需要颜色数目："+minCNum);
			ColorsNum=minCNum;
	      }
	      else if( cmd.equalsIgnoreCase("3") == true )
	      {
	    	  System.out.print("请输入您想要给地图染色的颜色数目：");
			  ColorsNum=Integer.parseInt(getUserCommand());
			  initColor();
	    	  coloring(0);
			  if(MethodNum==0)	System.out.println("用"+ColorsNum+"种颜色无法按条件染此图");
				else System.out.println("用"+ColorsNum+"种颜色染此图时共有以上"+MethodNum+"种方法");
	      
	      
	      }
	      else if( cmd.equalsIgnoreCase("4") == true )
	      {
	    	  initColor();
	    	  coloring(0);
			  if(MethodNum==0)	System.out.println("用"+ColorsNum+"种颜色无法按条件染此图");
				else System.out.println("用"+ColorsNum+"种颜色染此图时共有以上"+MethodNum+"种方法");
	      
	      }
	      else { System.out.println("此功能选项不存在，请重新输入..."); 
	           getUserCommand();}  
	        }
	      }
}