//----------------------------------------------------------------
//	File:		graph.java
//	Purpose:	Implement a directed, weighted graph class via an 
//              Adjacency Matrix
//  Author : 
//  Last Modified : 
//  Comments : 
//----------------------------------------------------------------

import java.io.*;

public class Graph { 

private int numEdges;
private int numVertices;
private double [][] M; 
private final double NO_EDGE = 1.0e100;	//define NO_EDGE's value for class

public Graph(){
  numEdges = 0; numVertices = 0;
}

public Graph(int n) {
   numEdges = 0; numVertices = 0;
   M = new double[n][n];
   for (int i=0; i<n; i++)
     for (int j=0; j<n ; j++)
       M[i][j] = NO_EDGE;
}

public void initialize(String fileName){
    FileInput myFile = new FileInput(fileName); 
    int first = 0, second=0, third=0; 
    String next="";
	while (!myFile.eof()){
	  if (numEdges==0)
	    { numVertices = myFile.getInt();
	      M = new double[numVertices][numVertices];
	      for (int i=0; i<numVertices; i++)
            for (int j=0; j<numVertices ; j++)
              M[i][j] = NO_EDGE;
	    }
	  else
	    { first = myFile.getInt();
	      second = myFile.getInt();
	      third = myFile.getInt();
	      M[first][second]=third;
	    }
	  numEdges++;
	}   
	     
	
      
}


public void setSize(int n) 
{
	M = new double[n][n];
	numVertices = n;
}

public void addEdge(int origin, int destination, double value) 
{
	 if (!hasEdge(origin, destination))
	   M[origin][destination] = value;
}

public void removeEdge(int origin, int destination) 
{
	if (hasEdge(origin, destination))
	   M[origin][destination] = NO_EDGE;
}

public boolean hasEdge(int origin, int destination)
{
    if (M[origin][destination] != NO_EDGE)
        return true;
    else
        return false;
}

public double edgeValue(int origin, int destination)
{
   if (hasEdge(origin, destination))
     return M[origin][destination];
   else
     return NO_EDGE;
}

public int inDegree(int n){
   int count=0;
   for (int i=0; i<numVertices; i++)
     if (M[i][n]!= NO_EDGE)
        count++;
   return count;
}

public int outDegree(int n){
   int count=0;
   for (int j=0; j<numVertices; j++)
     if (M[n][j]!= NO_EDGE)
        count++;
   return count;
}

public int degree(int n){
  return (inDegree(n)+outDegree(n));
}

public int getVertices(){
    return numVertices;
}

public void print() {
   for (int i=0; i<numVertices ;i++)
    { System.out.print(i + "==>");
      for (int j=0; j<numVertices; j++)
        if (hasEdge(i,j))
           System.out.print(j + " ");
      System.out.println();
     }      
}



public boolean hasPath(int origin, int destination){
    int start = origin;
    while (start != destination)
      { for (int i=0; i<numVertices; i++)
          if (hasEdge(start,i))
             start = i;
          else  return false; 
       }
    if (start==destination) return true;   

}
// retunr the path length from origin to destination
// same assumption as above
public int pathLength(int origin, int destination){
    int count=0;
    int start = origin;
    while (start != destination)
      { for (int i=0; i<numVertices; i++)
          if (hasEdge(start,i))
             {start = i; count++;}
          else  return -1; 
       }
    if (start==destination) return count;  
}
//  return true if for each edge from i to j, there is an edge from j to i
public boolean isSymmetric(){
    for (int i=0; i<numVertices; i++)
      for (int j=0; j<numVertices; j++)
         if (hasEdge(i,j) && !hasEdge(j,i))
            return false;
    return true;
}

//  retunr the total number of one way edges (if (i,j) is there then (j,i) is not there
// and vice versa
public int oneWay(){
   int count = 0;
   for (int i=0; i<numVertices; i++)
      for (int j=i; j<numVertices; j++)
         if (hasEdge(i,j) && !hasEdge(j,i))  count++;
   return count;
}


}