-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.go
143 lines (119 loc) · 3.55 KB
/
main.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
package main
import (
"fmt"
"github.com/abhishek-bhangalia-busy/detect-cycle/db"
"github.com/abhishek-bhangalia-busy/detect-cycle/initializers"
"github.com/abhishek-bhangalia-busy/detect-cycle/models"
"github.com/go-pg/pg/v10"
)
var DB *pg.DB
func init() {
initializers.LoadEnvVariables()
}
func main() {
//connect to DB
DB = db.ConnectToDB()
defer DB.Close()
//creating schema
err := db.CreateSchema(DB)
if err != nil {
fmt.Println("error : ",err.Error())
}
var empID, managerID uint64
fmt.Println("Enter the empID :")
fmt.Scanln(&empID)
fmt.Println("Enter the managerID :")
fmt.Scanln(&managerID)
var ans bool
ans, err = canAddEdge(empID, managerID)
if err != nil {
fmt.Println("error : ", err.Error())
}
if ans {
fmt.Println("Cycle does not exist. Employee can be managed by manager.")
} else {
fmt.Println("Cycle will exist. So Employee can't be managed by manager.")
}
}
// this func detects cycle in whole graph
// so if cycle can exist in the existed table also then we will use this method
// func detectCycle() (bool, error) {
// // Fetch all rows from the table
// var rows []models.EmployeeManager
// if err := DB.Model(&rows).Select(); err != nil {
// fmt.Println("Error querying database: %v\n", err)
// return false, err
// }
// // Execute query to retrieve max values
// var result struct {
// MaxID uint64
// }
// _, err := DB.QueryOne(&result, `SELECT GREATEST(MAX(employee_id) , MAX(manager_id) ) AS max_id FROM employee_managers`)
// if err != nil {
// fmt.Println("can't get max eid and max mid")
// return false, err
// }
// //Creating graph (adjacency list) from data
// graph := make(map[uint64][]uint64)
// for _, row := range rows {
// graph[row.EmployeeID] = append(graph[row.EmployeeID], row.ManagerID)
// }
// var empID, managerID uint64
// fmt.Println("Enter the empID :")
// fmt.Scanln(&empID)
// fmt.Println("Enter the managerID :")
// fmt.Scanln(&managerID)
// graph[empID] = append(graph[empID], managerID)
// if empID > result.MaxID {
// result.MaxID = empID;
// }
// if(managerID > result.MaxID){
// result.MaxID = managerID;
// }
// //checking if graph has cycle
// var vis = make([]bool, result.MaxID+1)
// var dfs_visit = make([]bool, result.MaxID+1)
// for k := range graph {
// if !vis[k] && hasCycle(k, vis, dfs_visit, graph) {
// return true, nil
// }
// }
// return false, nil
// }
//this func will not check whole graph for cycle.
//so, if we are given that cycle will not exist in the table then we can use this method and save time as it will not traverse whole graph for cycle
//it will only check the part of graph which is connected to newly added edge
func canAddEdge(empID uint64, managerID uint64) (bool, error) {
// Fetch all rows from the table
var rows []models.EmployeeManager
if err := DB.Model(&rows).Select(); err != nil {
fmt.Println("Error querying database: %v\n", err)
return true, err
}
graph := make(map[uint64][]uint64)
for _, row := range rows {
graph[row.EmployeeID] = append(graph[row.EmployeeID], row.ManagerID)
}
graph[empID] = append(graph[empID], managerID)
var vis = make(map[uint64]bool)
var dfs_visit = make(map[uint64]bool)
if hasCycle(empID, vis, dfs_visit, graph) {
return false, nil
}
return true, nil
}
func hasCycle(v uint64, vis map[uint64]bool, dfs_vis map[uint64]bool, g map[uint64][]uint64) bool {
vis[v] = true
dfs_vis[v] = true
for _, nb := range g[v] {
if !vis[nb] {
if hasCycle(nb, vis, dfs_vis, g) {
return true
}
} else if dfs_vis[nb] {
return true
}
}
dfs_vis[v] = false
return false
}