#
#Linear programming
#
#A company makes two products A and B. The sales from product A must be at least 80% of all sales (A+B).
#The market is saturated with 100 products of type A. To produce one product A the
#company needs 2 kg of material and to product a product B it needs 4kg. 
#The company has 240kg available material. Profit form product A is 20€ and for
#product B it is 50€. How to maximize the company profit given these constraints. 

#Rewrite text into equations

#Maxsimize 20A + 50B 

#The text gives us the following constraints

#A >= 0.8(A+B)
#A <= 100
#2A + 4B <= 240
#A, B >= 0

#We will use a package lpSolve, due to this we have to change the form 
#of the first constraint

#0.8(A+B) - A <= 0
#0.8B - 0.2A <= 0

#optimization function
f.opt <- c(20, 50)

#constraints
f.con <- matrix(c(-0.2, 0.8, 1, 0, 2, 4, 1, 0, 0, 1), ncol = 2, byrow = TRUE)

#operators
f.dir <- c("<=", "<=", "<=", ">=", ">=")

#right hand side of constraints
f.rhs <- c(0, 100, 240, 0, 0)

#run the linear program with lpSolve

library(lpSolve)
#function lp returns the value of the best solution
rez <- lp("max", f.opt, f.con, f.dir, f.rhs)

#We can find the exact values of A and B
rez$solution

#rez Displays the max optimization value
rez

#-------------------------------------------------------------------------------
#Same exercise using lpSolveAPI

# Load lpSolveAPI
require(lpSolveAPI)

# Set an empty linear problem
linProgram <- make.lp(nrow = 0, ncol = 2)
# Set the linear program as a maximanization
lp.control(linProgram, sense="max")


# Set type of decision variables
set.type(linProgram, 1:2, type=c("real"))
# Set objective function coefficients vector C
set.objfn(linProgram, c(20, 50))

# Add constraints
add.constraint(linProgram, c(-0.2, 0.8), "<=", 0)
add.constraint(linProgram, c(1, 0), "<=", 100)
add.constraint(linProgram, c(2, 4), "<=", 240)
add.constraint(linProgram, c(1, 0), ">=", 0)
add.constraint(linProgram, c(0, 1), ">=", 0)



# Display the LPsolve matrix
linProgram

# Solve problem
solve(linProgram)

# Get the variables
get.variables(linProgram)
# Get the value of the objective function
get.objective(linProgram)

#---------------------------------------------------------------------------------

#Exercise 1
#Maximal flow

#You have a graf G(V,E), where each edge (u,v) of E has a positive flow c(u,v) >= 0.
#You also have a starting vertex s and terminal vertex t. Find the maximal flow from 
#s to t. 

#The graf consists of vertices V = {s,t,v1,v2,v3,v4,v5} and capacities:
#c(s, v1) = 20
#c(s, v4) = 7
#c(v1, v2) = 15
#c(v1, v3) = 5
#c(v2, t) = 12
#c(v2, v5) = 5
#c(v3, v4) = 2
#c(v3, v5) = 4
#c(v4, v1) = 3
#c(v4, v5) = 8
#c(v5, t) = 17
#find the maximal flow

#Exercise 2

#Write a function that will return the shortest path for graphs generated by make_my_graph()
library(tidyverse)
library(lpSolveAPI)
library(igraph)

make_my_graph2 <- function(v, e){
  #first create a path so that the problem will always be solvable
  #number of vertices on path excluding 1 and v
  path_size <- ceiling(runif(1, min = 2, max = v-1))
  path_ind <- c(1, sample(2:(v-1), path_size), v)
  path_from <- path_ind[1:(length(path_ind)-1)]
  path_to <- path_ind[2:(length(path_ind))]
  path_from_to <- bind_cols(from = path_from, to = path_to)
  
  #print(path_from_to)
  
  from <- sample(1:v, e - (path_size + 1), replace = T) #create start vertices
  to <- sample(1:v, e - (path_size + 1), replace = T) #create end vertices
  
  #create indexes for all other edges
  from_to_other <- bind_cols(from = from, to = to)
  #combine and delete duplicates and self-loops
  from_to <- bind_rows(path_from_to, from_to_other) %>% distinct() %>% filter(from != to)
  print(from_to)
  edges <- as.vector(t(from_to))
  #the above part gives approximate number of edges
  #add randomly using while
  print(paste0("Current edges: ", length(edges)/2, " Desired edges: ", e))
  while(length(edges)/2 < e){
    #add one more edge (and check for self-loops and duplication)
    from_to <- bind_rows(from_to, c(from = sample(1:v,1), to = sample(1:v,1))) %>% distinct() %>% filter(from != to)
    edges <- as.vector(t(from_to))
  }
  print(paste0("Current edges: ", length(edges)/2, " Desired edges: ", e))
  make_empty_graph() %>%
    add_vertices(1, color = "green") %>%
    add_vertices(v-2, color = "red") %>%
    add_vertices(1, color = "green") %>%
    add_edges(edges) %>%
    set_edge_attr("cost", value = c(1,runif(length(edges)/2-2, 0.1, 2), 1))
}
g <- make_my_graph2(30, 55)
is_connected(g)
as_data_frame(g)

plot(g)

#Finish the following function
return_shortest_path <- function(g){
  
}