# Matrix
generateMatrix <- function(n){

  mat <- matrix(sample(c(0,1), n*n, T), n, n)

  for(i in 1:n){
    for(j in i:n){
      mat[i, j] <- mat[j,i]
    }
  }

  diag(mat) <- 0
  return(mat)
}


# Reset colors
resetColors <- function(n){
  colors <- c()
  for(i in 1:n){
    colors[i] <- "gray"
  }

  return(colors)
}

# Find edge number
findEdgeNumber <- function(a, from, to){

  minNum <- min(c(from, to))
  maxNum <- max(c(from, to))

  count <- 0

  for(i in 1:sqrt(length(a))){
    for(j in 1:sqrt(length(a))){
      if(a[i,j] == 1 && i <= j){
        count <- count+1
      }

      if(i == minNum && j == maxNum){
        return(count)
        break
      }
    }
  }
}

# Delete from arr
deleteFromArr <- function(arr, value){
  if(length(arr) > 0){
    for(i in 1:length(arr)){
      if(arr[i] == value){
        arr <- arr[-i]
        return(arr)
      }
    }
  }
}

# Draw graph
drawGraph <- function(a, g, vertexColors, edgesColors){

  igraph_options(
    vertex.color = vertexColors,
    vertex.size = 30,
    vertex.shape = "sphere",
    vertex.label.cex = 3,
    vertex.label.color = "white",
    vertex.label.family = "sans-serif",

    edge.color = edgesColors,
    width = 3
  )

  roots <- c(1)
  rootsLevel <- c(1)

  for(i in (1:sqrt(length(a)))){
      roots[length(roots)+1] <- i
      rootsLevel[length(rootsLevel)+1] <- i
  }

  plot(g, layout=layout_as_tree(g, root=roots, rootlevel = rootsLevel))
}

deepStart <- function(n, searchFrom){

  # Settings
  a <- generateMatrix(n)
  g <- graph.adjacency(a, mode="undirected")
  available <- 1:n
  available <- available[-searchFrom]

  # Colors
  vertexColors <- resetColors(n)
  edgesColors <- resetColors(n*n)

  print(a)


  saveHTML({

    # Draw canvas
    drawGraph(a, g, vertexColors, edgesColors)
    vertexColors[searchFrom] = "green"
    drawGraph(a, g, vertexColors, edgesColors)

    deepSearch(a, g, searchFrom, available, vertexColors, edgesColors)
  },

  img.name = "eaGraph", imgdir = "eaGraph7", htmlfile = "eaGraph3.html",
  autobrowse = TRUE, autoplay =  FALSE, title = "Ershov Andrew's Graph",
  description = "Deep search graph")
}


# Search
deepSearch <- function(a, g, searchFrom, available, vertexColors, edgesColors){

  if(length(available > 0)){
    for(i in 1:n){
      # There edge
      if( (a[searchFrom, i]) == 1){
        # Is free?
        check <- 0
        for(b in 1:length(available)){
          if(length(available) > 0){
            if(available[b] == i){
              check <- 1
              available <- available[-b]


              edgeNumber <- findEdgeNumber(a, searchFrom, i)

              edgesColors[edgeNumber] = "green"
              vertexColors[i] = "green"
              vertexColors[searchFrom] = "red"

              # Save animation
              drawGraph(a, g, vertexColors, edgesColors)
              vertexColors[i] = "red"
              edgesColors[edgeNumber] = "gray"

              # Remove from list
              available <- deepSearch(a, g, i, available, vertexColors, edgesColors)

              break
            }
          }
        }
      }
    }
  }

  return(available)

}

# Code
n <- 5
searchFrom <- 1

deepStart(n, searchFrom)