pathcalculation.java

国外的数据结构与算法分析用书

import java.io.*;
import java.util.*;
import dslib.graph.*;

public class PathCalculation
{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String tempString = new String();
  
	int a[][] = {{0, 0, 0, 1, 0},
			{0, 0, 1, 0, 0},
			{0, 1, 0, 0, 0},
			{0, 0, 1, 0, 1},
			{1, 1, 0, 0, 0}};   
    
	int c[][] = {{0, 100000, 100000, 1},
			{3, 0, 1, 100000},
			{5, 1, 0, 100000},
			{8, 1, 4, 0}};
    
	public PathCalculation() throws IOException
	{
		int p[][] = countPaths(a);
		tempString = br.readLine();
		System.out.println("\nThe adjacency matrix to the power n is\n");
		printMatrix(p);
		int w[][] = warshallsAlg(a);
		System.out.println("\nThe Path matrix for a is\n");
		printMatrix(w);
		tempString = br.readLine();
		int d[][] = floydsAlg(c); 
		System.out.println("\nThe shortest paths matrix for c is\n");
		printMatrix(d);
		tempString = br.readLine();
		testComputeAdjacenyMatrix();
		tempString = br.readLine();
		testCycleDetector();
		tempString = br.readLine();
	}  
    
	public int[][] countPaths (int arr[][]) throws IOException
	{
		Vector b =  new Vector(5);
		int r, i, j, k, sum = 0;

		b.insertElementAt((int [][])arr.clone(), 0);
		System.out.println("\n\n A to the power 1");
		printMatrix((int [][])b.get(0));
		tempString = br.readLine();
		int tp[][] = new int[5][5];
		int t1[][] = new int[5][5];

		for (r = 1; r < 5; r++)
		{
			int temp[][] = new int [5][5];
			b.insertElementAt(temp, r);
			for (i = 0; i < 5; i++)
			{
				for (j = 0; j < 5; j++)
				{
					sum = 0;
					for (k = 0; k < 5; k++)
					{
						tp = (int [][])b.get(r-1);
						t1 = (int [][])b.get(0);
						sum += tp[i][k] * t1[k][j];
					}
					tp = (int [][])b.get(r);
					tp[i][j] = sum;
					b.insertElementAt(tp, r);
				}
			}
			System.out.println("\nA to the power " + (r+1) );
			printMatrix((int [][])b.get(r));
			tempString = br.readLine();
		}
		return (int [][])b.get(4);
	}   
    
	/**	The reachability (path) matrix computed by means of Warshall's algorithm
		Analysis: Time = O(n^3), where n is the number of nodes in the graph */
	public int[ ][ ] warshallsAlg (int[ ][ ] a)
	{
		int[ ][ ] w = (int [][])a.clone();
		for (int k = 1; k <= a.length; k++)
			for (int i = 1; i <= a.length; i++)
				for (int j = 1; j <= a.length; j++)
					if (matrixItem(w,i,j) == 0)
						matrixSetItem(w, matrixItem(w,i,k) * matrixItem(w,k,j), i, j);
		return w;
	}
	
	/**	The shortest paths matrix computed by means for Floyd's algorithm
		Analysis: Time = O(n^3), where n is the number of nodes in the graph */
	public int[ ][ ] floydsAlg (int[ ][ ] w)
	{
		int[ ][ ] d = (int [][])w.clone();
		int[ ][ ] p = new int[w.length][w.length];
		for (int k = 1; k <= w.length; k++)
			for (int i = 1; i <= w.length; i++)
				for (int j = 1; j <= w.length; j++)
					if (matrixItem(d,i,k) + matrixItem(d,k,j) < matrixItem(d,i,j))
					{
						matrixSetItem(d, matrixItem(d,i,k) + matrixItem(d,k,j), i, j);
						matrixSetItem(p,k,i,j); 
					}
		return p;
	}
    
	public void printMatrix(int arr[][])
	{
		int i, j;
		for (i = 0; i < arr.length; i++)
		{
			for (j = 0; j < arr.length; j++)
				System.out.print(arr[i][j] + " ");
			System.out.println();
		}
	}

	public void testComputeAdjacenyMatrix()
	{
		GraphLinkedRepUos g = new GraphLinkedRepUos(4, "d");
		g.vNew("first");
		g.vNew("second");
		g.search("first");
		VertexUos v = (VertexUos) g.item();
		g.search("second");
		g.eNew(v, (VertexUos)g.item());
		g.vNewIth(null, 3);
		g.goIth(3);
		g.eNew(v, (VertexUos)g.item());
		g.eNew((VertexUos)g.item(), v);
		g.vNewIth("fourth", 4);
		g.goIth(4);
		g.eNew(v, (VertexUos)g.item());
		System.out.println(g);
	
		int[ ][ ] a = computeAdjacenyMatrix(g);
		System.out.println("\nThe adjacency matrix is \n");
		printMatrix(a);
	}

	public int[ ][ ] computeAdjacenyMatrix(GraphUos g)
	{
		int [ ][ ] a = new int[g.capacity()][g.capacity()];
		g.goFirst();
		while (!g.after())
		{
			g.eGoFirst((VertexUos)g.item());
			while (!g.eAfter())
			{
				matrixSetItem(a, 1, g.iterationIndex(), g.adjIndex());
				g.eGoForth();
			}
			g.goForth();
		}
		return a;
	}
	
	/**	Set the item with indices i and j. <br>
		Analysis: Time = O(1) */
	protected void matrixSetItem(int[ ][ ] a, int x, int i, int j)
	{
		/* indices 1 through n are mapped to 0 through n-1. */
		a[i-1][j-1] = x;
	}
 
	/**	The item with indices i and j. <br>
		Analysis: Time = O(1) */
	protected int matrixItem(int[ ][ ] a, int i, int j)
	{
		/* indices 1 through n are mapped to 0 through n-1. */
		return a[i-1][j-1];
	}

	public void testCycleDetector()
	{
		CycleGraphLinkedRepUos g = new CycleGraphLinkedRepUos(8);
		for (int i=1; i<=8; i++)
			g.vNewIth(null, i);
		g.eNew(1, 2);
		g.eNew(1, 5);
		g.eNew(2, 3);
		g.eNew(3, 4);
		g.eNew(5, 7);
		g.eNew(7, 6);
		g.eNew(7, 4);
		g.eNew(6, 5);
		g.eNew(6, 1);
		System.out.println(g);

		for (int i=1; i<=g.n(); i++)
		{
			g.goIth(i);
			System.out.println("\nResult of cycle test on " + g.item() 
				+ " is " + g.isInCycle((SearchVertexUos)g.item()));
		}
	}

	public static void main(String args[]) throws IOException
	{
		PathCalculation c = new PathCalculation();
	}   

}