changed direction of follower map, basic hub rank up and running

5 files changed, 237 insertions, 25 deletions

diff --git a/src/main/java/edu/brown/cs/student/term/DatabaseQuerier.java b/src/main/java/edu/brown/cs/student/term/DatabaseQuerier.java
index 1bb49c7..7e9a184 100644
--- a/src/main/java/edu/brown/cs/student/term/DatabaseQuerier.java
+++ b/src/main/java/edu/brown/cs/student/term/DatabaseQuerier.java
@@ -85,8 +85,4 @@ public class DatabaseQuerier{
 
     return trades;
   }
-
-
-
-
 }
diff --git a/src/main/java/edu/brown/cs/student/term/hub/HubSearch.java b/src/main/java/edu/brown/cs/student/term/hub/HubSearch.java
index 4c382ec..4d5755c 100644
--- a/src/main/java/edu/brown/cs/student/term/hub/HubSearch.java
+++ b/src/main/java/edu/brown/cs/student/term/hub/HubSearch.java
@@ -1,7 +1,101 @@
 package edu.brown.cs.student.term.hub;
 
+import edu.brown.cs.student.term.DatabaseQuerier;
+import edu.brown.cs.student.term.repl.commands.SetupCommand;
+
+import java.time.Instant;
+import java.util.*;
+
 public class HubSearch {
 
+  LinkMapper mapper;
+  Map<Holder, Set<Holder>> followerToLeaderMap = new HashMap<>();
+
+  //TODO: Make this just take in a map from holder -> set of holder
+  public HubSearch(LinkMapper mapper){
+    this.mapper = mapper;
+  }
+
+  //TODO: reevaluate this basic version and tweak to customize
+  public Map<Holder, Double> runHubSearch(Instant start, Instant end){
+    followerToLeaderMap = mapper.makeFollowerLinks(start, end);
+    int numHolders = followerToLeaderMap.size();
+    List<Holder> holders = new ArrayList<>(followerToLeaderMap.keySet());
+    double[] weights = new double[numHolders];
+    double[] rank = new double[numHolders];
+    double[] rankPrime = new double[numHolders];
+    Arrays.fill(rankPrime, 1.0 / numHolders);
+
+    while(!withinDistance(rank, rankPrime)){
+      rank = Arrays.copyOf(rankPrime, rankPrime.length);
+      //calculating hub rank for ith holder
+      for(int i = 0; i < numHolders; i++){
+        rankPrime[i] = 0;
+        //iterating through all holders to calculate hub rank
+        for(int j = 0; j < numHolders; j++){
+          double weightIJ = getWeight(holders.get(i), holders.get(j), numHolders);
+          rankPrime[i] += (weightIJ * rank[j]);
+        }
+      }
+    }
+
+    //potentially should change this to be a map from holder id => double?
+    Map<Holder, Double> hubRankMap = new HashMap<>();
+
+    for(int i = 0; i < rankPrime.length; i++){
+      hubRankMap.put(holders.get(i), rankPrime[i]);
+    }
+
+    return hubRankMap;
+  }
+
+  private double getWeight(Holder leader, Holder follower, int numHolders){
+
+    //dampening factor
+    double damp = 0.15;
+    /*
+      In normal page rank:
+     links is the pages that k links to, if k links to j, then
+     we want to add some weight to j from k, but that
+     weight is diluted by the number of links that k has
+     in general because we don't want to count a bunch of links
+     from a page as highly as one targeted link from one page to another
+
+     In Hub Search
+     leader = j, follower = k, if follower links to (follows) leader,
+     then we want to add some weight from follower to leader,
+     but should that weight be diluted by the number of people
+     who followed leader or the number of people who follower followed
+     --- probably the second option ;( */
+    Set<Holder> peopleFollowed = followerToLeaderMap.get(follower);
+    int numberFollowed = peopleFollowed.size();
+
+    if(peopleFollowed.contains(leader)){
+      return ((damp / numHolders) + (1 - damp) * (1.0 / numberFollowed));
+    } else if(numberFollowed == 0){
+      return ((damp / numHolders) + (1 - damp) * (1.0 / numHolders));
+    } else {
+      return (damp / numHolders);
+    }
+  }
+
+  private boolean withinDistance(double[] r, double[] rPrime){
+    double sum = 0.0;
+    for(int i = 0; i < r.length; i++){
+      sum += Math.pow((r[i] - rPrime[i]), 2);
+    }
+
+    return sum <= 0.001;
+  }
+
+
+
+
+
+
+
+
+
   /*
    def pageRank(pList: List[Page]): mutable.HashMap[Int, Double] = {
     val n = pList.length
@@ -41,5 +135,14 @@ public class HubSearch {
       (0.15 / n)
     }
   }
+
+  def distance(r1: Array[Double], r2: Array[Double]): Boolean = {
+    var sum = 0.0
+    for (i <- 0 to r1.length - 1) {
+      sum = sum + Math.pow((r1(i) - r2(i)), 2)
+    }
+    sum <= .001
+
+  }
    */
 }
diff --git a/src/main/java/edu/brown/cs/student/term/hub/LinkMapper.java b/src/main/java/edu/brown/cs/student/term/hub/LinkMapper.java
index f4ec0a7..8bc8cf9 100644
--- a/src/main/java/edu/brown/cs/student/term/hub/LinkMapper.java
+++ b/src/main/java/edu/brown/cs/student/term/hub/LinkMapper.java
@@ -1,7 +1,6 @@
 package edu.brown.cs.student.term.hub;
 
 import edu.brown.cs.student.term.DatabaseQuerier;
-import edu.brown.cs.student.term.repl.commands.SetupCommand;
 import edu.brown.cs.student.term.trade.Trade;
 
 import java.sql.SQLException;
@@ -10,30 +9,23 @@ import java.util.*;
 
 public class LinkMapper {
 
+  //TODO: Review what we actually need in here
   //not strictly necessary but may be nice to maintain
   private List<List<Trade>> allTrades = new ArrayList<>();
-  private Map<Holder, List<Trade>> personToTradesMap = new HashMap<>();
-  private Map<Holder, List<Holder>> personToFollowers = new HashMap<>();
+  private Map<Holder, Set<Holder>> followerToLeaders = new HashMap<>();
   private DatabaseQuerier databaseQuerier;
 
   public LinkMapper(DatabaseQuerier db){
     this.databaseQuerier = db;
   }
 
-  /**
-   * Returns the person => trades map as is, does not update it
-   * @return person to trades map
-   */
-  public Map<Holder, List<Trade>> getPersonToTradesMap() {
-    return personToTradesMap;
-  }
 
   /**
-   * Returns the person => follower map  as is, does not update it
+   * Returns the follower => leaders map  as is, does not update it
    * @return person to follower map
    */
-  public Map<Holder, List<Holder>> getPersonToFollowers() {
-    return personToFollowers;
+  public Map<Holder, Set<Holder>> getFollowerToLeaders() {
+    return followerToLeaders;
   }
 
   /**
@@ -41,20 +33,17 @@ public class LinkMapper {
    * in the same time period
    * @return the newly updated link map
    */
-  public Map<Holder, List<Holder>> makeFollowerLinks(Instant start, Instant end){
+  public Map<Holder, Set<Holder>> makeFollowerLinks(Instant start, Instant end){
     if(databaseQuerier != null){
       try{
         List<List<Trade>> allTrades = databaseQuerier.getAllTradesByStock(start, end);
         //reset the map to be blank
-        personToFollowers = new HashMap<>();
+        followerToLeaders = new HashMap<>();
 
         for(List<Trade> tradeList : allTrades){
           convertTradeListToFollowerMap(tradeList);
         }
 
-        //System.out.println(personToFollowers.toString());
-        System.out.println("num people in map: " + personToFollowers.size());
-
       } catch(SQLException e) {
         System.out.println("ERROR: SQL Error while retrieving trade list");
       }
@@ -62,9 +51,12 @@ public class LinkMapper {
       System.out.println("ERROR: No database loaded in yet");
     }
 
-    return personToFollowers;
+    return followerToLeaders;
   }
 
+
+  //TODO: Try to create both leader => follower and follower => leader map at once
+  //only if necessary tho!
   private void convertTradeListToFollowerMap(List<Trade> tradeList){
     List<Holder> holderList = new ArrayList<>();
 
@@ -73,6 +65,66 @@ public class LinkMapper {
       holderList.add(trade.getHolder());
     }
 
+    //Set<Holder> followers = new HashSet<>(holderList);
+    Set<Holder> encountered = new HashSet<>();
+
+    //[bob, george, jane, bob, mary]
+    for(Holder current: holderList){
+      //only want to use first instance of a holder to dictate who they followed
+      //for instance, if the person whose at the front buys again, they probably
+      //didn't follow the people in between, just wanted to buy again
+      if(!encountered.contains(current)){
+        if(followerToLeaders.containsKey(current)){
+          //TODO: this probably makes it O(n^2), might want to optimize later
+          followerToLeaders.get(current).addAll(encountered);
+        } else {
+          Set<Holder> currentLeaders = new HashSet<>(encountered);
+          followerToLeaders.put(current, currentLeaders);
+        }
+        encountered.add(current);
+      }
+    }
+
+  }
+
+  //This code creates a leader => follower map!
+  /*private void convertTradeListToFollowerMap(List<Trade> tradeList){
+    List<Holder> holderList = new ArrayList<>();
+
+    //gets in order list of people
+    for (Trade trade : tradeList) {
+      holderList.add(trade.getHolder());
+    }
+
+    Set<Holder> followers = new HashSet<>(holderList);
+    Set<Holder> encountered = new HashSet<>();
+
+    for(Holder current: holderList){
+      //want to check if we've already gotten followers for this trade for this holder
+      if(!encountered.contains(current)){
+        encountered.add(current);
+        followers.remove(current);
+        if(personToFollowers.containsKey(current)){
+          //TODO: this probably makes it O(n^2), might want to optimize later
+          personToFollowers.get(current).addAll(followers);
+        } else {
+          Set<Holder> currentFollowers = new HashSet<>(followers);
+          personToFollowers.put(current, currentFollowers);
+        }
+      }
+    }
+  }*/
+
+
+  //Old version using lists of followers, allowing for duplicates
+  /*private void convertTradeListToFollowerMap(List<Trade> tradeList){
+    List<Holder> holderList = new ArrayList<>();
+
+    //gets in order list of people
+    for (Trade trade : tradeList) {
+      holderList.add(trade.getHolder());
+    }
+
     Set<Holder> followers = new HashSet<>(holderList);
     Set<Holder> encountered = new HashSet<>();
 
@@ -90,5 +142,5 @@ public class LinkMapper {
         }
       }
     }
-  }
+  }*/
 }
diff --git a/src/test/java/edu/brown/cs/student/HubRankTest.java b/src/test/java/edu/brown/cs/student/HubRankTest.java
new file mode 100644
index 0000000..9ba0987
--- /dev/null
+++ b/src/test/java/edu/brown/cs/student/HubRankTest.java
@@ -0,0 +1,54 @@
+package edu.brown.cs.student;
+
+import edu.brown.cs.student.term.DatabaseQuerier;
+import edu.brown.cs.student.term.hub.Holder;
+import edu.brown.cs.student.term.hub.HubSearch;
+import edu.brown.cs.student.term.hub.LinkMapper;
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+
+import java.time.Instant;
+import java.util.Map;
+
+public class HubRankTest {
+
+  /** these should span the entire mock dataset */
+  //12 am on 3/11 in UTC
+  private Instant start = Instant.parse("2021-03-11T05:00:00.00Z");
+  //12 am on 3/28 in UTC
+  private Instant end = Instant.parse("2021-03-28T05:00:00.00Z");
+
+  private DatabaseQuerier db;
+
+  @Before
+  public void setUp() {
+    try{
+      db = new DatabaseQuerier("data/lil_mock.sqlite3");
+    } catch(Exception e){
+      System.out.println("DBQuerier Test, couldn't connect to db???");
+    }
+  }
+
+  /*
+  * try{
+
+    } catch(Exception e) {
+      System.out.println("Error in test");
+    }*/
+
+  @After
+  public void tearDown() {
+    db = null;
+  }
+
+  @Test
+  public void testMapper(){
+    setUp();
+    LinkMapper lm = new LinkMapper(db);
+    lm.makeFollowerLinks(start, end);
+    HubSearch hub = new HubSearch(lm);
+    Map<Holder, Double> him = hub.runHubSearch(start, end);
+    System.out.println(him);
+  }
+}
diff --git a/src/test/java/edu/brown/cs/student/LinkMapperTest.java b/src/test/java/edu/brown/cs/student/LinkMapperTest.java
index 9b46d5e..2683b90 100644
--- a/src/test/java/edu/brown/cs/student/LinkMapperTest.java
+++ b/src/test/java/edu/brown/cs/student/LinkMapperTest.java
@@ -1,12 +1,15 @@
 package edu.brown.cs.student;
 
 import edu.brown.cs.student.term.DatabaseQuerier;
+import edu.brown.cs.student.term.hub.Holder;
+import edu.brown.cs.student.term.hub.HubSearch;
 import edu.brown.cs.student.term.hub.LinkMapper;
 import org.junit.After;
 import org.junit.Before;
 import org.junit.Test;
 
 import java.time.Instant;
+import java.util.Map;
 
 public class LinkMapperTest {
 
@@ -21,7 +24,7 @@ public class LinkMapperTest {
   @Before
   public void setUp() {
     try{
-      db = new DatabaseQuerier("data/mock_trades.sqlite3");
+      db = new DatabaseQuerier("data/lil_mock.sqlite3");
     } catch(Exception e){
       System.out.println("DBQuerier Test, couldn't connect to db???");
     }
@@ -44,5 +47,9 @@ public class LinkMapperTest {
     setUp();
     LinkMapper lm = new LinkMapper(db);
     lm.makeFollowerLinks(start, end);
+    HubSearch hub = new HubSearch(lm);
+    Map<Holder, Double> him = hub.runHubSearch(start, end);
+    System.out.println(him);
   }
+
 }