Network.java

Base model

/*
 * Network.java
 *
 * Created on January 18, 2005, 4:09 PM
 * Modified June 14, 2006
 * 
 * This class generates a network, runs some
 * net statistics, and writes it to a pajek-formatted file
 */

package CoopNetBlue;
//import java.util.Random;
import uchicago.src.sim.network.NetworkFactory;
import uchicago.src.sim.network.EdgeFactory;
import java.util.Formatter;
import uchicago.src.sim.util.Random;
import java.util.ArrayList;
import uchicago.src.sim.gui.OvalNetworkItem;
import rlriolo.ioutils.*;
import java.io.PrintWriter;
import java.util.HashSet;
import uchicago.src.sim.util.*;
import java.util.Vector;


/**
 *
 * @author Jack Waddell
 */
public class Network {
    
    //*******************************************************
    // static parameters

    // the main model
    public static CoopNetBlue model;
    

    //*******************************************************
    // Instance parameters
    public int[][]     adjacencyMatrix;  // Yes, it is Aij = 1 if j -> i.
    public int         networkSize;      // The number of agents
    public int         connectRadius;    // The radius for grid or SWN inits
    public double      reconnectProb;    // The prob or (re)wiring in (SWN) or random net
    // a pointer to the agent list,
    public ArrayList<CustomNode> agentList = new ArrayList<CustomNode>();
    
    // These are for writing a pajek-formatted file
    protected String		pajekFileName = "pajek";
    protected String 		outputDirName = "./";
    protected PrintWriter	pajekFile, plaintextPajekFile;
    
    
   
    ////////////////////////////////////////////////////////////////////////
    // Constructor
    public Network(int networkSize, int connectRadius, double reconnectProb){
	this.networkSize = networkSize;
	this.connectRadius = connectRadius;
	this.reconnectProb = reconnectProb;
    }


    ///////////////////////////////////////////////////////////////////////
    // buildAdjacencyMatrix
    // Inputs: int netType, selects which specific type of matrix to form
    // Outputs: int[][], the adjacency matrix
    public int[][] buildAdjacencyMatrix(int netType){
	switch(netType){
	case 0 : return buildAdjacencyMatrix2DWS();
	case 1 : return buildAdjacencyMatrixWS();
	case 2 : return buildAdjacencyMatrixRand();
	default: return buildAdjacencyMatrix2DWS();
	}
    }
    

    ///////////////////////////////////////////////////////////////////////////
    //
    // buildAdjacencyMatrixWS
    // Develops an adjacency matrix for a Watts-Strogatz Small World 
    // network based on the given parameters.  Note that this 
    // implementation uses a disconnecting rewire, so that it is
    // possible to disconnect groups in the network.  It is also 
    // possible to have less than an average degree of 2x connectRadius, 
    // since a connection can be "overwritten" during the rewire.
    //
    //  Inputs:  double reconnectProb:  each neighbor connection 
    // has a probability p of being disconnected from the outgoing side (i) 
    // and reattached to a random node (including the one from which it 
    // was just disconnected, and any other nodes that j goes to.)]
    // connectRadius: the number of neighbors to either side of each node.  
    // Note that this often leads to cycles.
    
    public int[][] buildAdjacencyMatrixWS(){
        
        adjacencyMatrix = new int[networkSize][networkSize];
	
	// Make the regular gride
        for(int i = 0; i < networkSize; i++){
            for(int j = i; j< networkSize; j++){
                if( (j <= (i + connectRadius) ) && (i!=j) ){
                    adjacencyMatrix[i][j] = 1;
                    adjacencyMatrix[j][i] = 1;
                }
                else if( (j >= (networkSize - connectRadius + i) ) && (i!=j)){
                    adjacencyMatrix[i][j] = 1;
                    adjacencyMatrix[j][i] = 1;
                }
                else{
                    adjacencyMatrix[i][j] = 0;
                    adjacencyMatrix[j][i] = 0;
                }
            }
        }
        
	// Do random rewiring
	double randomDouble;        
        for(int i = 0; i < networkSize; i++){
            for(int j = 1; j < networkSize; j++){
                randomDouble = model.getUniformDoubleFromTo(0,1);
                if((randomDouble < reconnectProb)&&
		                 (adjacencyMatrix[i][j]==1)){
		    adjacencyMatrix[i][j] = 0;
		    int randomi = j;
		    do{
			randomi = model.getUniformIntFromTo(0, networkSize - 1);
			if(model.rDebug > 2)
			    System.out.printf("j = %d, randomi = %d, A[i][j] = %d\n",
					      j,randomi, adjacencyMatrix[randomi][j]);
		    } while (randomi == j || adjacencyMatrix[randomi][j] ==1);
		    
		    adjacencyMatrix[randomi][j] = 1;
		    adjacencyMatrix[j][randomi] = 1;
                }
            }
        }
	

        return adjacencyMatrix;
    }
	
    ///////////////////////////////////////////////////////////////////////////
    //
    // buildAdjacencyMatrix2DWS
    // Develops an adjacency matrix for a Toroidal - Watts-Strogatz Small 
    // World network based on the given parameters.  Note that this 
    // implementation uses a disconnecting rewire, so that it is
    // possible to disconnect groups in the network. 
    public int[][] buildAdjacencyMatrix2DWS(){
        // Make regular grid
        adjacencyMatrix = new int[networkSize][networkSize];
        int ix, iy, jx, jy;
        int size = (int) Math.floor(Math.sqrt(networkSize));
        System.out.printf("Size = %d \n", size);
        for(int i = 0; i < networkSize; i++){
            for(int j = i; j< networkSize; j++){
                
                ix = i % size;
                iy = i / size;
                
                jx = j % size;
                jy = j / size;
                
                double dx = Math.min( Math.min( Math.pow(jx - ix,2), 
						Math.pow(jx + size - ix, 2)), 
				      Math.pow(jx - size - ix, 2) );
                double dy = Math.min( Math.min( Math.pow(jy - iy,2), 
						Math.pow(jy + size - iy, 2)), 
				      Math.pow(jy - size - iy, 2) );

                if( (Math.sqrt(dx + dy) <= (connectRadius) ) && (i!=j) ){
                    adjacencyMatrix[i][j] = 1;
                    adjacencyMatrix[j][i] = 1;
                }
                
                else{
                    adjacencyMatrix[i][j] = 0;
                    adjacencyMatrix[j][i] = 0;
                }
            }
        }
        
        double randomDouble;
        // Do random rewiring
        for(int i = 0; i < networkSize; i++){
            for(int j = 1; j < networkSize; j++){
                randomDouble = model.getUniformDoubleFromTo(0,1);
                if((randomDouble < reconnectProb)&&
		                    (adjacencyMatrix[i][j]==1)){
		    adjacencyMatrix[i][j] = 0;
		    int randomi = j;
		    do{
			randomi = model.getUniformIntFromTo(0, networkSize - 1);
			System.out.printf("j = %d, randomi = %d, A[i][j] = %d\n",
					  j,randomi, adjacencyMatrix[randomi][j]);
		    } while (randomi == j || adjacencyMatrix[randomi][j] ==1);
		    
		    adjacencyMatrix[randomi][j] = 1;
		    adjacencyMatrix[j][randomi] = 1;
                }
            }
        }
	System.out.printf("----> Finished 2DWS Adjacency Mat\n");
        return adjacencyMatrix;
    }
    
    
    ///////////////////////////////////////////////////////////////////////////
    //
    // buildAdjacencyMatrixStar
    // Develops an adjacency matrix for a Star Network, centered on i.
    public int[][] buildAdjacencyMatrixStar(int i){
        
        adjacencyMatrix = new int[networkSize][networkSize];
        int ix, iy, jx, jy;
        for(int k = 0; k < networkSize; k++){
	    for(int j = 0; j< networkSize; j++){
		adjacencyMatrix[k][j] = 0;
		adjacencyMatrix[j][k] = 0;
	    }
	}
        
	for(int j = 0; j< networkSize; j++){
	    if(i!=j){
		adjacencyMatrix[i][j] = 1;
		adjacencyMatrix[j][i] = 1;
	    }
	}

	System.out.printf("----> Finished Star Adjacency Mat\n");
        return adjacencyMatrix;
    }
    
    //////////////////////////////////////////////////////////////////
    // buildAdjacencyMatrixRand
    // Develops a symmetric, random adjacency matrix, so that the
    //  probability of an edge existing between any pair of nodes is
    //  reconnectProb.
    public int[][] buildAdjacencyMatrixRand(){
        
        adjacencyMatrix = new int[networkSize][networkSize];
        int i, j;
	double randn;
        for(i = 0; i < networkSize; i++){
	    for(j = 0; j < networkSize; j++){
		randn = model.getUniformDoubleFromTo(0, 1);
		
		if (randn < reconnectProb){
		    adjacencyMatrix[i][j] = 1;
		    adjacencyMatrix[j][i] = 1;
		}
		//else
		//    System.out.printf("Randn = %f vs %f\n", randn, reconnectProb);
	    }
	}
        
	System.out.printf("----> Finished Random Adjacency Mat\n");
        return adjacencyMatrix;
    }


    ///////////////////////////////////////////////////////////////////////
    // buildAgentList
    // Develops an arrayList of CustomNodes interconnected based on the
    // adjacency matrix developed.
    public void buildAgentList(){
	
	// Create all the agents
        for(int i = 0; i < networkSize; i++){
            OvalNetworkItem drawable = new OvalNetworkItem(0,0);
	    
	    double strategy = model.getUniformDoubleFromTo(0, 1);
	    
            CustomNode agent = new CustomNode(drawable, strategy);
            agentList.add(agent);
        }

	// Create the edges between them, governed by the adjacency
	//  matrix
        CustomEdge edge;
        double cc;
        CustomNode jnode, inode;
        for(int i = 0; i < networkSize; i++){
            for(int j = 0; j < networkSize; j++){
                if(adjacencyMatrix[i][j] == 1){
                    jnode = (CustomNode) agentList.get(j);
                    inode = (CustomNode) agentList.get(i);
                    edge = new CustomEdge(jnode, inode);
                    jnode.addOutEdge(edge);
                    inode.addInEdge(edge);

		    // This symmetritizes the network
		    // i.e. makes undirected
		    edge = new CustomEdge(inode, jnode);
		    inode.addOutEdge(edge);
		    jnode.addInEdge(edge);


                }
            }
        }
    }
    
    
    /////////////////////////////////////////////////////////////
    // printAdjacencyMatrix
    // a debugging tool.  Prints the adjacency matrix to the terminal
    public void printAdjacencyMatrix(){
        System.out.printf("--- Printing Adjacency Matrix, size %d ---\n", 
			  networkSize);
        for(int i = 0; i < networkSize; i++){
            for(int j = 0; j < networkSize; j++){
		System.out.printf(" %d ", adjacencyMatrix[i][j]);
            }
            System.out.printf("\n");
        }
    }
    
    
    //////////////////////////////////////////////////////////////
    // writePajekNetwork
    // Writes the network to a file in pajek
    //  format.  Note: this version writes DOS type line feeds.
    public void writePajekNetwork(ArrayList<CustomNode> agentList){
	String verts, arcs;
	// These are carriage return and line feed in DOS format.
	char cr = (char) 13;
	char lf = (char) 10;
	
	// pajek requires the vertices and arcs separately.
	verts = String.format("*Vertices %d%c%c", networkSize, cr, lf);	
	arcs = String.format("*Arcs %c%c", cr, lf);
	
	// step through all nodes
	for(int i = 0; i < networkSize; i++){
	    CustomNode inode = (CustomNode) agentList.get(i);
	    verts += String.format("%d \"N%d: %d\"",
		   inode.getID() + 1, inode.getID(), inode.getUtility());
	   
	    verts += String.format(" ic %s%c%c", inode.getMyPajekColor(),cr, lf);
	    
	    ArrayList edgesInList = inode.getInEdges();
	    int numEdges = edgesInList.size();
	    CustomNode testNode = (CustomNode) (model.agentList).get(i);
	    if (testNode != inode)
		System.out.printf("Nodes(%d) not equal\n", i);
	    if ( (testNode.getOutDegree() != inode.getOutDegree()) || (testNode.getInDegree() != inode.getInDegree()))
		System.out.printf("Nodes(%d) have different degree\n", i);
	    if (numEdges > 0)
		// if node has at least one neighbor, write the edges
		for(int j = 0;  j < numEdges; j++){
		    CustomEdge edge = (CustomEdge)edgesInList.get(j);
		    arcs += String.format("%d %d %c%c",
			    ((CustomNode)edge.getFrom()).getID() + 1,
			    ((CustomNode)edge.getTo()).getID() + 1, cr, lf);
		}
	}
	String s = verts + arcs;
	writeToPajekFile(s);
    }
    
    /////////////////////////////////////////////////////////////
    // writeLineToPajekFile
    // writes a single line to the pajek file
    public void writeLineToPajekFile ( String line ) {
	if ( pajekFile == null ) {
	    return;
	}
	else {
	    pajekFile.println( line );
	}
    }
    
    //////////////////////////////////////////////////////////
    // writeToPajekFile
    // Does the same.
    public void writeToPajekFile ( String line ) {
	if ( pajekFile == null ) {
	    return;
	}
	else {
	    pajekFile.print( line );
	}
    }
    
    //////////////////////////////////////////////////////////////
    // startPajekFile
    // opens a file to write the pajek network to.
    public PrintWriter startPajekFile () {
	if ( model.rDebug > 0 )
	    System.out.println( "startPajekFile called!" );
	pajekFile = null;
	String fullFileName = pajekFileName + String.format( "%02d.net",
			      model.runNumber );
	
	pajekFile = IOUtils.openFileToWrite( outputDirName, fullFileName, "r" );
	if ( model.rDebug > 0 )
	    System.out.println( "startPajekFile completed!" );
	
	return pajekFile;
    }
    
    //////////////////////////////////////////////////////////////
    // startPajekFile - overload
    // opens a file to write the pajek network to.  Calls it
    // by integer i
    public PrintWriter startPajekFile (int i) {
	if ( model.rDebug > 0 )
	    System.out.println( "startPajekFile called!" );
	pajekFile = null;
	String fullFileName = pajekFileName + String.format(
			     "%03d.%02d.net", i, model.runNumber );
	
	pajekFile = IOUtils.openFileToWrite( outputDirName, 
					     fullFileName, "r" );
	
	if ( model.rDebug > 0 )
	    System.out.println( "startPajekFile completed!" );
	return pajekFile;
    }
    
    //////////////////////////////////////////////////////////
    // endPajekFile
    // closes the open pajekFile
    public void endPajekFile ( ) {
	IOUtils.closePWFile( pajekFile );
    }


    ///////////////////////////////////////////////////////////
    // getAverageCC1
    // Calculates the average 1-neighborhood clustering coefficient
    public double getAverageCC1(){
	CustomNode node = null;
	double sum = 0;
	for(int i = 0; i < agentList.size(); i ++){
	    node = (CustomNode) agentList.get(i);
	    sum += getNodeCC1(node);
	}
	return sum / (double) agentList.size();
    }

    
    //////////////////////////////////////////////////////////
    // getAverageCC2
    // Calculates the average 2-neighborhood clustering coefficient
    public double getAverageCC2(){
	CustomNode node = null;
	double sum = 0;
	for(int i = 0; i < agentList.size(); i ++){
	    node = (CustomNode) agentList.get(i);
	    sum += getNodeCC2(node);
	}
	return sum / (double) agentList.size();
    }


    
    /////////////////////////////////////////////////////////
    // union
    // Support function.
    // Returns the union of two array lists of nodes
    public ArrayList<CustomNode> union(ArrayList<CustomNode> l1, 
				       ArrayList<CustomNode> l2){
	ArrayList<CustomNode> unionList = new ArrayList<CustomNode>();
	unionList.addAll(l1);
	for(int i = 0; i < l2.size(); i ++){
	    CustomNode node = (CustomNode) l2.get(i);
	    if (!unionList.contains(node))
		unionList.add(node);
	}
	return unionList;
    }

    /////////////////////////////////////////////////////////////
    // intersection
    // Support function
    // Return the intersection of two array lists of nodes
    public ArrayList<CustomNode> intersection(ArrayList<CustomNode> l1, 
				       ArrayList<CustomNode> l2){
	ArrayList<CustomNode> interList = new ArrayList<CustomNode>();
	for(int i = 0; i < l1.size(); i ++){
	    CustomNode node = (CustomNode) l1.get(i);
	    if (l2.indexOf(node) >-1)
		interList.add(node);
	}
	return interList;
    }

    /////////////////////////////////////////////////////////////
    // getNodeCC1
    // Computes the clustering coefficient CC1, as per Pajek documentation
    // This is the 1-neighborhood clustering coefficient
    public double getNodeCC1 (CustomNode node){
	ArrayList<CustomNode> neighborsList = new ArrayList<CustomNode>();
	// Get all neighbors
	neighborsList = union(node.getOutNodes(), node.getInNodes());
	int sum = 0;
	int k = neighborsList.size();
	for(int j = 0; j < k; j ++){
	    CustomNode jnode = (CustomNode) neighborsList.get(j);
	    ArrayList<CustomNode> nOut = jnode.getOutNodes();
	    ArrayList<CustomNode> nIn = jnode.getInNodes();
	    
	    sum += (intersection(nOut, neighborsList)).size();
	    sum += (intersection(nIn, neighborsList)).size();
	   
	}
	double cc1 = 0;
	if (k > 1)
	    cc1 = (double)sum/( 2* (double)k * (double)(k-1));
	return cc1;
    }


    /////////////////////////////////////////////////////////////
    // getNodeCC2
    // computes the clustering coefficient CC2, as per Pajek documentation
    // E(G1(v))/E(G2(v))
    // This is the 2-neighboorhood clustering coefficient
    public double getNodeCC2 (CustomNode node){
	
	// calc E(G1(v)) = sum1
	ArrayList<CustomNode> neighbors1List = new ArrayList<CustomNode>();
	ArrayList<CustomNode> neighbors2List = new ArrayList<CustomNode>();
	neighbors1List = union(node.getOutNodes(), node.getInNodes());
	neighbors2List.addAll(neighbors1List);

	int sum1 = 0;
	int k = neighbors1List.size();
	for(int j = 0; j < k; j ++){
	    CustomNode jnode = (CustomNode) neighbors1List.get(j);
	    ArrayList<CustomNode> nOut = jnode.getOutNodes();
	    ArrayList<CustomNode> nIn = jnode.getInNodes();
	    
	    sum1 += (intersection(nOut, neighbors1List)).size();
	    //sum1 += (intersection(nIn, neighbors1List)).size();

	    neighbors2List = union(neighbors2List, union(nOut, nIn));
	}
	
	//System.out.printf("For node %d sum1 = %d\n", node.getID(), sum1);

	
	int index = neighbors2List.indexOf(node);
	while (index > 0){
	    //System.out.printf("node index = %d\n", index);
	    neighbors2List.remove(index);
	    index = neighbors2List.indexOf(node);
	}

	// calc E(G2(v)) = sum2
	int sum2 = 0;
	int ind1, ind2;
	for(int j = 0; j < neighbors2List.size(); j++){
	    
	    CustomNode jnode = (CustomNode) neighbors2List.get(j);
	    ArrayList<CustomNode> nOut = jnode.getOutNodes();
	    ArrayList<CustomNode> nIn = jnode.getInNodes();

	    sum2 += (intersection(nOut, neighbors2List)).size();
	    //sum2 += (intersection(nIn, neighbors2List)).size();

	    ind1 = neighbors2List.indexOf(jnode);
	    ind2 = neighbors2List.lastIndexOf(jnode);
	    if (ind1 != ind2)
		System.out.printf ("Node %d in list multiple times\n", jnode.getID());

	}
	
	//System.out.printf("For node %d sum1 = %d\n", node.getID(), sum2);
	

	double cc2 = 0;
	if (sum2 > 0)
	    cc2 = (double)sum1/(double)sum2;
	return cc2;
    }

   



    /////////////////////////////////////////////////////////
    // printList
    // Debug tool
    // Prints the contents of an ArrayList
    public void printList(ArrayList<CustomNode> list){
	for(int i = 0; i < list.size(); i++){
	    CustomNode node = (CustomNode) list.get(i);
	    System.out.printf("%d, ", node.getID());

	}
	System.out.printf("\n");
    }

    ///////////////////////////////////////////////////////////
    // PickRandomEdge
    // Picks a random edge with uniform probability in O(m/(n*n))
    //   (I think)
    public CustomEdge pickRandomEdge(){
	CustomEdge edge = null;
	CustomNode inode;
	CustomNode jnode;
	do{
	    inode = agentList.get(model.getUniformIntFromTo(0, agentList.size() -1));
	    do{
		jnode = agentList.get(model.getUniformIntFromTo(0, agentList.size() -1));
	    } while (inode == jnode);
	    
	    if ( (jnode.getOutNodes()).contains(inode))
		edge = getEdgeFromTo(jnode, inode);
	} while (edge == null);
	return edge;
    }

   

    ///////////////////////////////////////////////////////////
    // selectRandomUncoupledPair
    // Selectrs a random pair of nodes with uniform probability.
    public CustomNode[] selectRandomUncoupledPair(){
	boolean pass = false;
	CustomNode inode, jnode;
	int i, j;
	CustomEdge edge;
	do{
	    i = model.getUniformIntFromTo(0, agentList.size() -1);
	    do{
		j = model.getUniformIntFromTo(0, agentList.size() -1);	
	    } while (i == j);
		
	    inode = (CustomNode) agentList.get(i);
	    jnode = (CustomNode) agentList.get(j);
	    if ( !(jnode.getOutNodes()).contains(inode)){
		pass = true;
	    }
	} while (!pass);
	CustomNode[] nodes = {inode, jnode};
	return nodes;
    }

    ////////////////////////////////////////////////////////////
    // selectRandomUncoupledNode
    // 
    public CustomNode selectRandomUncoupledNode(CustomNode jnode){
	boolean pass = false;
	CustomNode inode = null;
	int i, j = jnode.getID();
	CustomEdge edge;
	// get a list of the nodes, but make sure it isn't the main list
	// 'cause we're gonna shuffle it
	ArrayList <CustomNode> nodesList = new ArrayList<CustomNode>();
	nodesList.addAll(agentList);
	SimUtilities.shuffle(nodesList, Random.uniform);
	
	i = 0;
	int k = 0;
	do{
	    
	    inode = (CustomNode) nodesList.get(i);
	    if (inode != jnode){
		if ( !(jnode.getOutNodes()).contains(inode)){
		    pass = true;
		}
	    }
	    i++;
	    if (i == nodesList.size()){
		i = 0;
		k ++;
	    }
	} while ( !pass && k < 2 );

	if (k == 2){
	    do{
		i = model.getUniformIntFromTo(0, agentList.size() - 1);
		inode = (CustomNode) agentList.get(i);
	    } while ( i == j || (jnode.getOutNodes()).contains(inode));
	}
	return inode;
    }


    // getters and setters
    public String getPajekFileName () { return pajekFileName; }
    public void setPajekFileName ( String s ) {
	pajekFileName = s;
    }
    
    
    public String getOutputDirName () { return outputDirName; }
    public void setOutputDirName ( String s ) {
	outputDirName = s;
    }

    public int getNetworkSize() {return networkSize;}
    public ArrayList<CustomNode> getAgentList() {return agentList;}
    
    public PrintWriter getPajekFile () { return pajekFile; }
    
    public CustomEdge getEdgeFromTo(CustomNode jnode, CustomNode inode){
	CustomEdge edge;
	HashSet edgeList = inode.getEdgesFrom(jnode);
	Object[] edges = edgeList.toArray();
	// get the edge object connected to jnode
	edge = ((CustomEdge)edges[0]);
	return edge;
    }

    //**************************************************
    // Static Methods
    public static void setModel(CoopNetBlue m){model = m;}
}