adjgraph.java

This code implements the shortest path algorithm via the simple scheme and fibonacci heap data struc

public class AdjGraph {
	// adjacent list graph
	private int source;
	private LinkListNode[] head; 
	//the linklist array which contain the first nodes of every lists
	private int vertexNb;
	
	public AdjGraph (){
		source = 0;
		vertexNb = 0;
		head = new LinkListNode[vertexNb];
		for(int i=0;i<vertexNb;i++)
			head[i] = new LinkListNode();
	}
	
	public AdjGraph(int vb){
		vertexNb = vb;
		head = new LinkListNode[vertexNb];
		for(int i=0;i<vb;i++)
			head[i] = new LinkListNode();
	}
	
	public void addNode(int idx1, int idx2, int w){
	//add node to the graph	
		LinkListNode tmp;
		tmp = head[idx1];
		
		if (tmp.getLink()==null )
		{
			LinkListNode newNode = new LinkListNode();
			newNode.setIndex(idx2);
			newNode.setLink(null); 
			newNode.setWeight(w);
			tmp.setLink(newNode);
		}
		else
		{	
			while(tmp.getLink()!=null && tmp.getIndex()!=idx2)
				tmp=tmp.getLink();
		}
		if (tmp.getIndex()!=idx2)
		{	//if the edge has alreay existed , do not insert it
			LinkListNode newNode = new LinkListNode();
			newNode.setIndex(idx2);
			newNode.setLink(null); 
			newNode.setWeight(w);
			tmp.setLink(newNode);
		}
		
	}
	
	public void setSource (int s){
		source = s;
	}
	
	public void setVertexNb (int v){
		vertexNb = v;
	}
	
	public int getWeight(int idx1, int idx2) {
		int Max=5000;
		LinkListNode tmp;
		tmp = head[idx1];
		if (idx1!=idx2){
			while ((tmp !=null)&&(tmp.getIndex()!=idx2) ){
				tmp=tmp.getLink();
			}
			if (tmp==null) return Max;
			//if no edge between two nodes, set the value to be MAX
			else return tmp.getWeights();
		}
		else return 0;
	}
	
	public int getVertexNb(){
		return vertexNb;
	}
	
	public int getSource (){
		return source;
	}
}