Shortest_Path.Rmd

---
title: "Untitled"
author: "Fugo Takefusa 300543407"
date: "27/06/2022"
output: html_document
---

```{r}
library(network)
library(dplyr)
library(statnet.common)
library(sna)
library(igraph)
```


```{r}
error_check = function(sociomatrix, start, end){
  if (!is.matrix(sociomatrix)){
    return(stop("The object should be a matrix"))
  }
  if (!is.numeric(start)){
    return(stop("'start' must be a positive integer"))
  }
  if (round(start) != start | start < 1){
    return(stop("'start' must be a positive integer"))
  }
  if (!is.numeric(end)){
    return(stop("'end' must be a positive integer"))
  }
  if (round(end) != end | end < 1){
    return(stop("'end' must be a positive integer"))
  }
  if (end > nrow(sociomatrix)){
    return(stop(paste0("There is no such an ending point: ", end)))
  }
  if (start == end){
    return(stop("The starting point and the ending point are the same"))
  }
  
}

sekko = function(candidate, path.to.end, edge, e){

  path.counter = 1
  continue = "yes"
  while (continue == "yes"){
    counter = 1
    candidate2 = data.frame("From"=integer(), "To"=integer(), "Cum.Dist"=integer())
    
    for (i in 1:nrow(candidate)){
      for (j in 1:nrow(edge)){
        if (edge[j, 1] == candidate[, 2][i] #find the candidate row from edgelist
            & !edge[j, 2] %in% unique(unlist(candidate[, c(-2,-3)])) # excluding the path with destination same as used nodes
            & edge[j, 3] + candidate[i,3]  < path.to.end[1,3]){# edge j indicate new dist, candidate i indicate previous dist
          candidate2[counter, ] = edge[j, ]
          candidate2[counter, 3] = candidate2[counter, 3] + candidate[i,3]#cumulative dist
          for (k in 1:path.counter){
            if (k == path.counter){
              candidate2[counter, paste0("node", k)] = candidate[i, 1]#record the previous path
            } else {
              candidate2[counter, paste0("node", k)] = candidate[i, k + 3]#record the previous path
            }
          }
          counter = counter + 1 
        }
      }
    }
    
    if (nrow(candidate2) == 0){
      continue = "no"
    } else {
      for (i in 1:nrow(candidate2)){
        if(candidate2[i, 2] == e){
          path.to.end = dplyr::bind_rows(path.to.end, candidate2[i, ])
        }
      }
    }
    path.to.end = path.to.end[order(path.to.end[,3]),]
    candidate = candidate2[!duplicated(candidate2[, 2]), ]
    path.counter = path.counter + 1
    
  }
  print(path.to.end[1,])
  return(path.to.end[1,])
}

hongun = function(candidate, path.to.end, edge, e){
  path.counter = 1
    continue = "yes"
    
    while (continue == "yes"){
      counter = 1
      candidate2 = data.frame("From"=integer(), "To"=integer(), "Cum.Dist"=integer())
      
      for (i in 1:nrow(candidate)){
        for (j in 1:nrow(edge)){
          if (edge[j, 1] == candidate[, 2][i] #find the candidate row from edgelist
              & !edge[j, 2] %in% candidate[i, c(-2,-3)] # excluding the path with destination same as used nodes
              & edge[j, 3] + candidate[i,3]  < path.to.end[1,3]){# edge j indicate new dist, candidate i indicate previous dist
            candidate2[counter, ] = edge[j, ]
            candidate2[counter, 3] = candidate2[counter, 3] + candidate[i,3]#cumulative dist
            for (k in 1:path.counter){
              if (k == path.counter){
                candidate2[counter, paste0("node", k)] = candidate[i, 1]#record the previous path
              } else {
                candidate2[counter, paste0("node", k)] = candidate[i, k + 3]#record the previous path
              }
            }
            counter = counter + 1 
          }
        }
      }
      
      if (nrow(candidate2) == 0){
        continue = "no"
      } else {
        for (i in 1:nrow(candidate2)){
          if(candidate2[i, 2] == e){
            path.to.end = dplyr::bind_rows(path.to.end, candidate2[i, ])
          }
        }
      }
      #print(path.counter)
      #print(path.to.end)
      #print(candidate2)
      candidate = candidate2
      path.counter = path.counter + 1
      #if (nrow(candidate2) > 100 & path.counter %in% c(6, 12)){
        #path.to.end = dplyr::bind_rows(path.to.end, sekko(candidate, path.to.end, edge, e))
      #}
      path.to.end = path.to.end[order(path.to.end[,3]),]
    }
    return(path.to.end)
}

    

shortest.path = function(sociomatrix, start, end){
  require(network)
  require(dplyr)
  
  error_check(sociomatrix, start, end)
  s = start
  e = end
  net = network(sociomatrix, directed = TRUE, ignore.eval=F, names.eval = "cost")
  edge = data.frame(as.edgelist(net, attrname = "cost"))
  reacha.net = reachability(net)

  if (reacha.net[s,e] == 0){
    warning(paste0("There is no path from ", s, " to ", e))
    return(data.frame("Cum.Dist"=Inf, "From"=s, "To"=e))
  }
  
  #First setup
  path.to.end = data.frame("From"=s, "To"=e, "Cum.Dist"=Inf)
  for (i in 1:nrow(edge)){
    if(edge[i, 1] == s & edge[i, 2] == e){
      path.to.end[1, ] = edge[i, ]
    }
  }
  candidate = data.frame("From"=integer(), "To"=integer(), "Cum.Dist"=integer())
  counter = 1
  for (i in 1:nrow(edge)){
    if(edge[i, 1] == s & (edge[i, 3] <  path.to.end[3])){
      candidate[counter,] = edge[i,]
      counter = counter + 1
    }
  }
  
  if (nrow(candidate) == 0){
    if (path.to.end[1, 3] == Inf){
      warning(paste0("There is no path from ", s, " to ", e))
    }
    return(path.to.end[, c(3, 1, 2)])
  } else {
    
    #Main part
    path.to.end = sekko(candidate, path.to.end, edge, e)
    path.to.end = hongun(candidate, path.to.end, edge, e)
    
    #Tidy up
    ind = ncol(path.to.end)
    path.to.end = path.to.end[, c(3:ind,1, 2)]
    names(path.to.end)[c((ind-1), ind)] = c(paste0("node", ind-2),paste0("node", ind-1)) 
    return(unique(path.to.end))
  }
}


#Functions which can generate random social matrix
matrix.dir = function(n, p0){
  data=sample(c(0, 1, 2, 5, 8, 10), n*n, replace = TRUE,
              prob = c(p0,  (1-p0)/5, (1-p0)/5, (1-p0)/5, (1-p0)/5, (1-p0)/5))
  mat=matrix(data, ncol=n)
  diag(mat) = 0
  return(mat)
}

matrix.undir = function(n, p0){
  mat = matrix(rep(0, n*n), ncol=n)
  for (i in 1:n){
    for (j in 1:n){
      if (i != j & i < j){
        mat[j, i]  = mat[i, j] = sample(c(0, 1, 5, 8, 9), 1, replace = TRUE,
              prob = c(p0,  (1-p0)/4, (1-p0)/4, (1-p0)/4, (1-p0)/4))
      }
    }
  }
  return(mat)
}

```



```{r}
n = 100
mat = matrix.undir(n, 0.9)
net= network(mat, directed = TRUE, ignore.eval=F,
             names.eval = "cost")
plot(net, #displaylabels = TRUE, #edge.label = "cost", edge.label.col = 4,
     arrowhead.cex = 0, edge.lwd = 0.4, vertex.cex = 1)


shortest.path(mat, 1,65)
#efficient.path(mat, 1, n)
```