Jarrad's

package graphs.freshcode;

//exported project

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;






import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;

import org.jgrapht.Graph;
import org.jgrapht.Graphs;
import org.jgrapht.graph.*;

public class PageRankGraph extends BaseGraph<Integer, DefaultWeightedEdge> {

        private static final long serialVersionUID = 1L;

        public PageRankGraph() {
                super(DefaultWeightedEdge.class);
        } // ensure non-instantiability.

        // // START OF PAGERANK CODE
        //

        public Integer getRandomLink(Integer v) {
                // ADDED
                // PRE: vertex v has non-empty adjacency list
                // POST: returns a vertex ID randomly selected from adjacent vertices,
                // according to distribution of edge weights
                // adapted from Sedgewick:
                // http://introcs.cs.princeton.edu/java/16pagerank/RandomSurfer.java.html

                // TODO
                double totalWeight = 0;
                DefaultWeightedEdge e = null;

                Set<DefaultWeightedEdge> s = outgoingEdgesOf(v);

                Iterator<DefaultWeightedEdge> iter = s.iterator();

                // First iteration finds the total weight
                while (iter.hasNext()) {
                        e = (DefaultWeightedEdge)iter.next();
                        totalWeight += getEdgeWeight(e);
                }

                Random r = new Random();

                // Generates the (somewhat) random vertex that we want
                int result = r.nextInt((int) totalWeight) + 1;

                totalWeight = 0;
                e = null;
                Integer nextVertex = null;

                Iterator<DefaultWeightedEdge> iter2 = s.iterator();
                ;

                // Finds the correct vertex
                while (iter2.hasNext()) {
                        e = (DefaultWeightedEdge) iter2.next();
                        nextVertex = getEdgeTarget(e);
                        totalWeight += getEdgeWeight(e);

                        if (result <= totalWeight)
                                break;
                }
                return nextVertex;
        }

        public Integer surfWithJump(Integer v, Integer n, Double jumpThreshold) {
                // PRE: v is vertex to start surf; n >= 0; 0 <= jumpThreshold <= 1.0
                // POST: surfs the graph randomly for n moves,
                //       choosing adjacent vertex according to distribution of edge weights if random number is below jumpThreshold,
                //       choosing any vertex uniformly randomly otherwise;
                //       modifies # visits in vertices
                //       returns last visited vertex at end of surfing

                // TODO


                Random r = new Random();
                Integer vertex = v;

                Set<Integer> s = vertexSet();

                //Continue to surf n times
                for(; n > 0; n--){

                        //If the vertex is a sink, choose a random vertex
                        if(outgoingEdgesOf(v).size() == 0) {
                            vertex = r.nextInt(s.size());
                        }

                        double willJump = Math.random();

                        //Path taken to jump to a (somewhat) random adjacent vertex if the random number is below the jumpThreshold
                        if(willJump < jumpThreshold) {
                                vertex = getRandomLink(vertex);
                        }

                        //Path take to a select a random vertex otherwise
                        else {
                                vertex = r.nextInt(s.size());
                        }

                        setVisits(vertex, (getVisits(vertex)+1));

                }
                return vertex;
        }

        public ArrayList<Integer> topN(Integer N) {
                // PRE: none
                // POST: returns N vertices with highest number of visits, in order;
                // returns all vertices if <N in the graph;
                // returns vertices ranked 1,..,N,N+1,..,N+k if these k have the
                // same number of visits as vertex N

                // TODO

            Set<Integer> s = vertexSet();

            Iterator<Integer> iter = s.iterator();

            ArrayList<Integer> a = new ArrayList<Integer>();

            if(N <= 0) {
                return new ArrayList<Integer>();
            }

            //Adding an initial element to the list so that we have something to compare to
            a.add((Integer)iter.next());

            Integer temp = 0;

            //Generates a sorted list
            while(iter.hasNext()) {

                temp = (Integer)iter.next();

                for(int i = 0; i < a.size(); i++) {

                    //Insert temp if its number of visits is greater than element at i
                    if(getVisits(temp) > getVisits(a.get(i))) {
                        a.add(i, temp);
                        break;

                    }
                    //temp.visits is not greater than any others and we have reached the end of the list
                    else if(i == a.size()-1) {
                        a.add(temp);
                        break;

                    }
                }
            }

            //Return entire list
            if(a.size() <= N) {
                return a;
            }

            //Else return truncated list
            else {
                ArrayList<Integer> smallA = new ArrayList<Integer>();

                for(int i = 0; i < N; i++) {
                    smallA.add(a.get(i));
                }

                return smallA;

            }
        }

        public void setVertexWeights() {
                // PRE: -
                // POST: set weights of each vertex v to be v.visits divided by
                // the total of visits for all vertices

                // TODO

            Set<Integer> s = vertexSet();

            Iterator<Integer> iter = s.iterator();

            int totalVisits = 0;
            Integer vertex = 0;

            //Calculate total number of visits
            while(iter.hasNext()) {
                vertex = (Integer)iter.next();
                totalVisits += getVisits(vertex);
            }

            iter = s.iterator();

            //Setting weight for all vertices
            while(iter.hasNext()) {
                vertex = (Integer)iter.next();
                setWeight(vertex, getVisits(vertex)/(double)totalVisits);
            }
            return;
        }

        public void convergenceWeights(Integer dp, Double jumpThreshold) {
                // PRE: dp >= 0 representing number of decimal places
                // POST: web is surfed until all weights are constant to dp decimal
                // places,
                // for at least one iteration

                // TODO

            Set<Integer> s = vertexSet();

            Integer surfVertex = getFirstVertex();
            Integer vertex = null;

            BigDecimal a1[] = new BigDecimal[s.size()];
            BigDecimal a2[] = new BigDecimal[s.size()];

            for(int i = 0; i < a2.length; i++) {
                a2[i] = new BigDecimal(-1);
            }

            int counter;

            boolean switched = true;

            Iterator<Integer> iter = null;

            while(true) {

                surfVertex = surfWithJump(surfVertex, 1, jumpThreshold);

                setVertexWeights();

                iter = s.iterator();

                counter = 0;

                while(iter.hasNext()) {
                    vertex = (Integer)iter.next();
                    if(switched) {
                        a1[counter] = new BigDecimal(getWeight(vertex)).setScale(dp, RoundingMode.DOWN);
                        switched = false;
                    }
                    else {
                        a2[counter] = new BigDecimal(getWeight(vertex)).setScale(dp, RoundingMode.DOWN);
                        switched = true;

                    }
                    counter++;
                }

                for(int i = 0; i < a1.length; i++) {
                    if(a1[i].compareTo(a2[i]) != 0) {
                        break;
                    }
                    else if(i == a1.length-1) {
                        return;
                    }
                }
            }
        }

        public Integer surfWithJumpUntilHit(Integer v, Integer n,
                        Double jumpThreshold) {
                // PRE: v is vertex to start surf; n >= 0; 0 <= jumpThreshold <= 1.0
                // POST: surfs the graph randomly until visit v for second time (maximum
                // n moves),
                // choosing adjacent vertex according to distribution of edge weights if
                // random number is below jumpThreshold,
                // choosing any vertex uniformly randomly otherwise;
                // modifies # visits in vertices
                // returns number of vertices visited

                // TODO

            Random r = new Random();
            Integer initialVertex = v;
            Integer vertex = v;
            Set<Integer> s = vertexSet();

            Iterator<Integer> iter = s.iterator();

            //Continue to surf n times
            for(; n > 0; n--){

                    //If the vertex is a sink, choose a random vertex
                    if(outgoingEdgesOf(v).size() == 0) {
                        vertex = r.nextInt(s.size());
                    }

                    double willJump = Math.random();

                    //Path taken to jump to a (somewhat) random adjacent vertex if the random number is below the jumpThreshold
                    if(willJump < jumpThreshold) {
                            vertex = getRandomLink(vertex);
                    }

                    //Path take to a select a random vertex otherwise
                    else {
                        vertex = r.nextInt(s.size());
                    }

                    setVisits(vertex, (getVisits(vertex)+1));

                    if(vertex == initialVertex) {

                        iter = s.iterator();

                        int totalVisits = 0;


                        while(iter.hasNext()) {
                            vertex = (Integer)iter.next();
                            totalVisits += getVisits(vertex);
                        }

                        return totalVisits;
                    }
            }

            return 0;
        }

        public Integer surfWithJumpUntilCover(Integer v, Integer n,
                        Double jumpThreshold) {
                // PRE: v is vertex to start surf; n >= 0; 0 <= jumpThreshold <= 1.0
                // POST: surfs the graph randomly until all vertices visited (with
                // maximum n vertices visited),
                // choosing adjacent vertex according to distribution of edge weights if
                // random number is below jumpThreshold,
                // choosing any vertex uniformly randomly otherwise;
                // modifies # visits in vertices
                // returns number of vertices visited

                // TODO

            Random r = new Random();
            Integer vertex = v;
            setMarked(v);

            Set<Integer> s = vertexSet();
            Iterator<Integer> iter = s.iterator();

            boolean allVisited = false;

            //Continue to surf n times
            for(; n > 0; n--){

                    //If the vertex is a sink, choose a random vertex
                    if(outgoingEdgesOf(v).size() == 0) {
                        vertex = r.nextInt(s.size());
                    }

                    double willJump = Math.random();

                    //Path taken to jump to a (somewhat) random adjacent vertex if the random number is below the jumpThreshold
                    if(willJump < jumpThreshold) {
                            vertex = getRandomLink(vertex);
                    }

                    //Path take to a select a random vertex otherwise
                    else {
                        vertex = r.nextInt(s.size());
                    }

                    setVisits(vertex, (getVisits(vertex)+1));

                    iter = s.iterator();

                    allVisited = true;

                    while(iter.hasNext()) {
                        vertex = (Integer)iter.next();
                        if(isMarked(vertex) == false)
                            allVisited = false;
                    }

                    if(allVisited) {
                        iter = s.iterator();

                        int totalVisits = 0;

                        while(iter.hasNext()) {
                            vertex = (Integer)iter.next();
                            totalVisits += getVisits(vertex);

                        }

                        return totalVisits;
                    }

            }

            return 0;

        }

        public Double averageHittingTime(Integer v, Integer n, Integer maxHits,
                        Double jumpThreshold) {
                // PRE: n >= 1 is number of iterations for averaging; maxHits >= 0; 0 <=
                // jumpThreshold <= 1.0
                // POST: returns average number of vertices visited until hitting,
                // across n iterations,
                // (not including those which stopped because they reached maxHits)
                // returns 0 if all iterations reached maxVisits

                // TODO

                Double averageVisits = 0.0;

                Set<Integer> s = vertexSet();
                Iterator<Integer> iter = null;
                Integer vertex = null;

                Integer[] a = new Integer[s.size()];
                int counter = 0;

                for(int i = 0; i < n; i++) {

                    iter = s.iterator();

                    counter = 0 ;
                    while(iter.hasNext()) {
                        vertex = (Integer)iter.next();
                        a[counter] = getVisits(vertex);
                        setVisits(vertex, 0);
                        counter++;

                    }

                    averageVisits += surfWithJumpUntilHit(v, maxHits, jumpThreshold);

                    counter = 0;
                    iter = s.iterator();
                    while(iter.hasNext()) {
                        vertex = (Integer)iter.next();
                        setVisits(vertex, getVisits(vertex) + a[counter]);
                        counter++;

                    }
                }

                averageVisits = averageVisits/n;

                return averageVisits; // TODO: REPLACE THIS WITH AN APPROPRIATE RETURN VALUE

        }

        public Double averageCoverTime(Integer n, Integer maxVisits,
                        Double jumpThreshold) {
                // PRE: n >= 1 is number of iterations for averaging; maxVisits >= 0; 0
                // <= jumpThreshold <= 1.0
                // POST: returns average number of vertices visited until cover, across
                // n iterations,
                // (not including those which stopped because they reached maxVisits)
                // randomly selecting start vertex each iteration
                // returns 0 if all iterations reached maxVisits

                // TODO

            Double averageVisits = 0.0;

            Set<Integer> s = vertexSet();
            Iterator<Integer> iter = null;

            Random r = new Random();
            Integer vertex = null;

            Integer[] a = new Integer[s.size()];
            int counter = 0;

            for(int i = 0; i < n; i++) {

                vertex = r.nextInt(s.size());

                iter = s.iterator();

                counter = 0 ;
                while(iter.hasNext()) {
                    vertex = (Integer)iter.next();
                    a[counter] = getVisits(vertex);
                    setVisits(vertex, 0);
                    counter++;

                }

                averageVisits += surfWithJumpUntilCover(n, maxVisits, jumpThreshold);

                counter = 0;
                iter = s.iterator();
                while(iter.hasNext()) {
                    vertex = (Integer)iter.next();
                    setVisits(vertex, getVisits(vertex) + a[counter]);
                    counter++;

                }
            }

            averageVisits = averageVisits/n;

            return averageVisits; // TODO: REPLACE THIS WITH AN APPROPRIATE RETURN VALUE

        }

        public Integer boostVertex(Integer v, Integer dp) {
                // PRE: v is a vertex in the graph
                // POST: returns a vertex v2 (!= v) such that when edge (v,v2,1.0) is
                // added to the graph,
                // the weight of v is larger than when edge (v,v3,1.0) is added to the
                // graph
                // (for any v3), when the graph is surfed to convergence
                // if there is no such vertex v2 (i.e. v is already connected to all
                // other vertices),
                // return v
                // edges are only added if they do not already exist in the graph

                // TODO

                return -1; // TODO: REPLACE THIS WITH AN APPROPRIATE RETURN VALUE

        }

        public void setWeightedIntFromFile(String fInName) throws IOException {
                // Reads list of edges from a file, one pair of integers plus weight per
                // line
                BufferedReader fIn = new BufferedReader(new FileReader(fInName));
                String s;
                Integer x, y;
                Double w;

                while ((s = fIn.readLine()) != null) {
                        java.util.StringTokenizer line = new java.util.StringTokenizer(s);
                        while (line.hasMoreTokens()) {
                                x = Integer.parseInt(line.nextToken());
                                y = Integer.parseInt(line.nextToken());
                                w = Double.parseDouble(line.nextToken());
                                this.addVertex(x);
                                this.addVertex(y);
                                DefaultWeightedEdge e = this.addEdge(x, y);
                                this.setEdgeWeight(e, w);
                        }
                }
                fIn.close();

                unsetAllMarked();
        }

        public static void main(String[] args) {
                PageRankGraph g = new PageRankGraph();

                try {
                        String PATH = "/home/madras/teaching/15comp225/assignments/a2/assignment-sample-graphs/";
                        g.setWeightedIntFromFile(PATH + "medium-weight.txt");
                } catch (IOException e) {
                        System.out.println("in exception: " + e);
                }
                System.out.println(g.toString());
                g.print();

        }
}