Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement