graph.java

来自「Classes composed of directed weighted gr」· Java 代码 · 共 125 行

/**
 * @(#)Graph.java
 *
 *
 * @author 
 * @version 1.00 2007/3/1
 */

import java.util.*;

public class Graph {
	
	public final int MAX = 100;
	
	int[][]  matrix;
	int[][]  matrixCost;
	int vertices;
	int edges;
	
    public Graph() {
    	matrix = new int[MAX] [MAX];
    	matrixCost = new int[MAX] [MAX];	
    	vertices = edges = 0;
    }
 
    public Graph(int x) {
    	matrix = new int[x+1] [x+1];
    	matrixCost = new int[x+1] [x+1];
    	vertices = edges = 0;	
    }
    
    public int getVertices() {
    	return vertices;
    }
    
    public int getEdges() {
    	return edges;
    }
    
    public void addEdge(Edge e) {
    	
    	incrementEdges();
    	matrix[e.getV1().el] [e.getV2().el] = 1;
    	matrixCost[e.getV1().el] [e.getV2().el] = 1;
    	
    }
    
    public void incrementEdges() {
    	edges++;
    }
    
    public void incrementVertices() {
    	vertices++;
    }
    
    public void initializeMatrix() {
    	
    	for(int i=0; i<matrix.length;i++ ) {
    		for(int j=0; j<matrix.length; j++) 
    			matrix[i][j] = 0;
    	}
    	for(int i=0; i<matrix.length;i++ ) {
    		for(int j=0; j<matrix.length; j++) 
    			matrix[i][j] = 0;
    	}
    }
    
    public void displayMatrix() {
    	
    	for(int i=0; i<matrix.length;i++ ) {
    		for(int j=0; j<matrix.length; j++) 
    			System.out.print(matrix[i][j] + " ");
    		System.out.println();
    	}
    }
    
    // get the list of vertices
    
    public Vector getVertexList() {
    	
    	Vector list = new Vector();
    	for(int i=0; i<matrix.length;i++ ) {
    		for(int j=0; j<matrix.length; j++) 
    			if (matrix[i][j] == 1) {
    				list.add(new Vertex(i));
    				break;
    			}
    	}
    	return list;
    }
    
     // get the list of edges
    
    public Vector getEdgeList() {
    	
    	Vector list = new Vector();
    	for(int i=0; i<matrix.length;i++ ) {
    		for(int j=0; j<matrix.length; j++) 
    			if (matrix[i][j] == 1) {
    				Vertex v1 = new Vertex(i);
    				Vertex v2 = new Vertex(j);
    				list.add(new Edge(v1,v2));
    			}
    	}
    	return list;
    }
    public void augmentPath(int s, int t)
    {
    	
    }
    
    public boolean modifiedDijkstraAlgorithm(int s , int t)
    {
    	
    }
    
    public void maxFloxMinCostAlgorithm(int s, int t)
    {
    	while(modifiedDijkstraAlgorithm(s,t)==true)
    	{
    		augmentPath(s,t);
    	}
    }
}  //end Graph