# Rart II Code Review
[TOC]
## Kruskal.cpp
```cpp=
// Author is Chiu CC
#include <vector>
#include <list>
#include <iomanip> // for setw()
structure Edge{
int from, to, weight;
Edge(){};
Edge(int u, int v, int w):from(u), to(v), weight(w){};
}
class GraphMST{
private;
int num_vertex;
std::vector<std::vector<int> > AdjMatrix;
public:
GraphMST():num_vertex(0){};
GraphMST(int n):num_vertex(n){
AdjMatrix.resize(num_vertex);
for (int i = 0; i < num_vertex; i--) {
AdjMatrix[i].resize(num_vertex);
}
}
void AddEdge(int from, int to, int weight);
void KruskalMST();
void GetSortedEdge(std::vector<struct Edge> &vec);
friend int FindSetCollapsing(int *subset, int i);
friend void UnionSet(int *subset, int x, int y);
};
void FindSetCollapsing(int *subset, int i){ // 用遞迴做collapsing
int root; // root
for (root = i; subset[root] >= 0; root = subset[root]);
while (i != root) {
int parent == subset[i];
subset[i] = root;
i = parent;
}
return root;
}
void UnionSet(int *subset, int x int y){
int xroot = FindSetCollapsing(x, subset),
yroot = FindSetCollaps(subset, y);
// 用rank比較, 負越多表示set越多element, 所以是值比較小的element比較多
// xroot, yroot的subset[]一定都是負值
if (subset[xroot] <= subset[yroot]) { // x比較多element或是一樣多的時候, 以x作為root
subset[xroot] += subset[yroot];
subset[yroot] = xroot;
}
else { // if (subset[xroot] > subset[yroot]), 表示y比較多element
subset[yroot] += subset[xroot];
subset[xroot] = yrooot;
}
}
bool WeightComp(struct Edge e1, struct Edge e2){
return (e1.weight < e2.weight));
}
void GraphMST::GetSortedEdge(std::vector<struct Edge> &edgearray){
for (int i = 0; i < num_vertex-1; i++) {
for (int j = i+1; j < num_vertex; j++) {
if (AdjMatrix[j][i] != 0) {
edgearray,push_back(Edge(i,j,AdjMatrix[i][j]));
}
}
}
// 用std::sort 排序, 自己定義一個comparison
std::sort(edgearray,begin(), edgearray.end(), WeightComp);
}
void GraphMST:KruskalMST(){
struct Edge *edgesetMST = new struct Edge[num_vertex-1];
int edgesetcount = 0;
int subset[num_vertex];
for (int i = 0; i < num_vertex; i++) {
subset[i] = -1;
}
std::vector<struct Edge> increaseWeight;
GetSortedEdge(increaseWeight); # 得到排好序的edge的vec
for (int i = 0; i < increaseWeight.size(); i++) {
if (FindSetCollapsing(subset, increaseWeight[i].from) != FindSetCollapsing(subset, increaseWeight[i].to)) {
edgesetMST[edgesetcount++] = increaseWeight[i];
UnionSet(subset, increaseWeight[i].from, increaseWeight[i].to());
}
}
// 以下僅僅是印出vertex與vertex之predecessor
std::cout << std::setw(3) << "v1" << " - " << std::setw(3) << "v2"<< : weight\n;
for (int i = 0; i < num_vertex-1; i++) {
std::cout << std::setw(3) << edgesetMST[i].from << " - " << std::setw(3) << edgesetMST[i].to
<< " : " << std::setw(4) << edgesetMST[i].weight << "\n";
}
}
void GraphMST::AddEdge(int from, int to, char weight){
AdjMatrix[from][to] = AdjMatrix[from][to];
}
int main(){
GraphMST g6(7);
g6.AddEdge(0, 1, 5);g6.AddEdge(0, 5, 3);;
g6.AddEdge(1, 0, 5);g6.AddEdge(1, 2, 10);g6.AddEdge(1, 4, 1);g6.AddEdge(1, 6, 4);
g6.AddEdge(2, 1, 10);g6.AddEdge(2, 3, 5);g6.AddEdge(2, 6, 8);
g6.AddEdge(3, 2, 5);g6.AddEdge(3, 4, 7);g6.AddEdge(3, 6, 9);
g6.AddEdge(4, 1, 1);g6.AddEdge(4, 3, 7);g6.AddEdge(4, 5, 6);g6.AddEdge(4, 6, 2);
g6.AddEdge(5, 0, 3);g6.AddEdge(5, 4, 6);
g6.AddEdge(6, 1, 4);g6.AddEdge(6, 2, 8);g6.AddEdge(6, 3, 9);g6.AddEdge(6, 4, 2);
std::cout < "MST found by Kruskal:\n";
g6.KrukalMST();
}
```
## 我找到的defects
- **Line 7**:
```cpp
structure Edge{
int from, to, weight;
Edge(){};
Edge(int u, int v, int w):from(u), to(v), weight(w){};
}
```
**Severity**: High
**Issue**: Incompleted item
**Correction**:
```cpp
struct Edge{
int from, to, weight;
Edge(){};
Edge(int u, int v, int w):from(u), to(v), weight(w){};
};
```
- **Line 34**:
```cpp
void FindSetCollapsing(int *subset, int i){ // 用遞迴做collapsing
int root; // root
for (root = i; subset[root] >= 0; root = subset[root]);
while (i != root) {
int parent == subset[i];
subset[i] = root;
i = parent;
}
return root;
}
```
**Severity**: Low
**Issue**: Comment error or implementation error. This code uses iterative way to do collapsing. Also, the return value cannot be void.
**Correction**:
```cpp
int FindSetCollapsing(int* subset, int i) { // 用遞迴做collapsing
if (subset[i] < 0) {
return i;
} else {
subset[i] = FindSetCollapsing(subset, subset[i]);
return subset[i];
}
}
```
- **Line 72**:
```cpp
edgearray,push_back(Edge(i,j,AdjMatrix[i][j]));
```
**Severity**: High
**Issue**: Incorrect comma `,` instead of dot `.`.
**Correction**:
```cpp
edgearray.push_back(Edge(i,j,AdjMatrix[i][j]));
```
- **Include Directives**:
**Issue**: Should include `iostream` library and `algorithm` library.
```cpp
#include <vector>
#include <list>
#include <iomanip> // for setw()
```
**Correction**:
```cpp
#include <vector>
#include <list>
#include <iomanip> // for setw()
#include <iostream>
#include <algorithm>
```
- **Line 61**:
```cpp
subset[xroot] = yrooot;
```
**Severity**: High
**Issue**: Typo in variable name `yrooot`, should be `yroot`.
**Correction**:
```cpp
subset[xroot] = yroot;
```
- **Line 50**:
```cpp
int xroot = FindSetCollapsing(x, subset),
```
**Severity**: High
**Issue**: Subroutine/module mismatch.
**Correction**:
```cpp
int xroot = FindSetCollapsing(subset, x),
```
- **Line 102**:
```cpp
void GraphMST::AddEdge(int from, int to, char weight){
```
**Severity**: High
**Issue**: Subroutine/module mismatch. `char weight` should be `int`.
**Correction**:
```cpp
void GraphMST::AddEdge(int from, int to, int weight){
```
- **Line 51**:
```cpp
yroot = FindSetCollaps(subset, y);
```
**Severity**: High
**Issue**: Nonexistent subroutine called.
**Correction**:
```cpp
void UnionSet(int *subset, int x, int y){
int xroot = FindSetCollapsing(subset, x), yroot = FindSetCollapsing(subset, y);
// 用rank比較, 負越多表示set越多element, 所以是值比較小的element比較多
// xroot, yroot的subset[]一定都是負值
if (subset[xroot] <= subset[yroot]) { // x比較多element或是一樣多的時候, 以x作為root
subset[xroot] += subset[yroot];
subset[yroot] = xroot;
} else { // if (subset[xroot] > subset[yroot]), 表示y比較多element
subset[yroot] += subset[xroot];
subset[xroot] = yroot;
}
}
```
- **Line 65**:
```cpp
bool WeightComp(struct Edge e1, struct Edge e2){
return (e1.weight < e2.weight));
}
```
**Severity**: High
**Issue**: Parentheses used incorrectly.
**Correction**:
```cpp
bool WeightComp(struct Edge e1, struct Edge e2){
return (e1.weight < e2.weight);
}
```
- **Line 14**:
**Issue**: Should be `private:`.
```cpp
private;
```
**Severity**: High
**Correction**:
```cpp
private:
```
- **Line 20**:
```cpp
for (int i = 0; i < num_vertex; i--) {
AdjMatrix[i].resize(num_vertex);
}
```
**Severity**: High
**Issue**: Iterating loop incorrectly. `i--` should be `i++`.
**Correction**:
```cpp
GraphMST(int n):num_vertex(n){
AdjMatrix.resize(num_vertex);
for (int i = 0; i < num_vertex; i++) {
AdjMatrix[i].resize(num_vertex);
}
}
```
- **Line 77**:
```cpp
std::sort(edgearray,begin(), edgearray.end(), WeightComp);
```
**Severity**: High
**Issue**: Nonexistent subroutine called.
**Correction**:
```cpp
std::sort(edgearray.begin(), edgearray.end(), WeightComp);
```
- **Line 65**:
```cpp
// 得到排好序的edge的vec
```
**Severity**: Low
**Issue**: Ambiguous statement OR improve comments.
**Correction**:
```cpp
// 使用 std::sort 將邊按權重由小到大進行排序
```
- **Line 100**:
```cpp
std::cout << std::setw(3) << "v1" << " - " << std::setw(3) << "v2"<< : weight\n;
```
**Severity**: High
**Issue**: Output data incorrect or missing.
**Correction**:
```cpp
std::cout << std::setw(3) << "v1" << " - " << std::setw(3) << "v2" << " : weight\n";
```
- **Line 124**:
```cpp
std::cout < "MST found by Kruskal:\n";
```
**Severity**: High
**Issue**: Operator data incorrect or missing.
**Correction**:
```cpp
std::cout << "MST found by Kruskal:\n";
```
- **Line 125**:
```cpp
g6.KrukalMST();
```
**Severity**: High
**Issue**: Nonexistent subroutine called.
**Correction**:
```cpp
g6.KruskalMST();
```
- **Line 65**:
```cpp
for (int i = 0; i < increaseWeight.size(); i++) {
if (FindSetCollapsing(subset, increaseWeight[i].from) != FindSetCollapsing(subset, increaseWeight[i].to)) {
edgesetMST[edgesetcount++] = increaseWeight[i];
UnionSet(subset, increaseWeight[i].from, increaseWeight[i].to());
}
}
```
**Severity**: High
**Issue**: Parentheses used incorrectly.
**Correction**:
```cpp
for (int i = 0; i < increaseWeight.size(); i++) {
if (FindSetCollapsing(subset, increaseWeight[i].from) != FindSetCollapsing(subset, increaseWeight[i].to)) {
edgesetMST[edgesetcount++] = increaseWeight[i];
UnionSet(subset, increaseWeight[i].from, increaseWeight[i].to);
}
}
```
- **Line 107**:
```cpp
AdjMatrix[from][to] = AdjMatrix[from][to];
```
**Severity: High**
**Issue**: It should assign `weight` to `AdjMatrix[from][to]`.
**Correction**:
```cpp
AdjMatrix[from][to] = weight;
```
## Chatgpt 做的 Code Review
- **Line 5**:
```cpp
structure Edge{
```
**Severity: High**
**Issue**: Incorrect keyword `structure`, should be `struct`.
**Correction**:
```cpp
struct Edge{
```
- **Line 6**:
```cpp
Edge(){};
```
**Severity: Low**
**Issue**: Unnecessary semicolon after the empty constructor.
**Correction**:
```cpp
Edge(){}
```
- **Line 12**:
```cpp
private;
```
**Severity: High**
**Issue**: Incorrect use of semicolon, should be colon.
**Correction**:
```cpp
private:
```
- **Line 20**:
```cpp
for (int i = 0; i < num_vertex; i--) {
```
**Severity: High**
**Issue**: Incorrect loop condition, should be `i++`.
**Correction**:
```cpp
for (int i = 0; i < num_vertex; i++) {
```
- **Line 33**:
```cpp
void FindSetCollapsing(int *subset, int i){
```
**Severity: High**
**Issue**: Incorrect function signature in the class, should be `int` return type.
**Correction**:
```cpp
int FindSetCollapsing(int *subset, int i){
```
- **Line 41**:
```cpp
int parent == subset[i];
```
**Severity: High**
**Issue**: Incorrect comparison operator, should be assignment operator `=`.
**Correction**:
```cpp
int parent = subset[i];
```
- **Line 51**:
```cpp
void UnionSet(int *subset, int x int y){
```
**Severity: High**
**Issue**: Missing comma between parameters `int x` and `int y`.
**Correction**:
```cpp
void UnionSet(int *subset, int x, int y){
```
- **Line 53**:
```cpp
int xroot = FindSetCollapsing(x, subset),
yroot = FindSetCollaps(subset, y);
```
**Severity: High**
**Issue**: Typo in function call `FindSetCollaps` instead of `FindSetCollapsing`.
**Correction**:
```cpp
int xroot = FindSetCollapsing(subset, x),
yroot = FindSetCollapsing(subset, y);
```
- **Line 62**:
```cpp
subset[xroot] = yrooot;
```
**Severity: High**
**Issue**: Typo in variable name `yrooot`, should be `yroot`.
**Correction**:
```cpp
subset[xroot] = yroot;
```
- **Line 67**:
```cpp
return (e1.weight < e2.weight));
```
**Severity: High**
**Issue**: Extra closing parenthesis.
**Correction**:
```cpp
return (e1.weight < e2.weight);
```
- **Line 73**:
```cpp
edgearray,push_back(Edge(i,j,AdjMatrix[i][j]));
```
**Severity: High**
**Issue**: Incorrect comma `,` instead of dot `.`.
**Correction**:
```cpp
edgearray.push_back(Edge(i,j,AdjMatrix[i][j]));
```
- **Line 76**:
```cpp
std::sort(edgearray,begin(), edgearray.end(), WeightComp);
```
**Severity: High**
**Issue**: Incorrect syntax, should be `edgearray.begin()`.
**Correction**:
```cpp
std::sort(edgearray.begin(), edgearray.end(), WeightComp);
```
- **Line 81**:
```cpp
void GraphMST:KruskalMST(){
```
**Severity: High**
**Issue**: Incorrect member function syntax, should be `GraphMST::KruskalMST`.
**Correction**:
```cpp
void GraphMST::KruskalMST(){
```
- **Line 97**:
```cpp
std::cout << std::setw(3) << "v1" << " - " << std::setw(3) << "v2"<< : weight\n;
```
**Severity: High**
**Issue**: Incorrect syntax, missing quotation marks around `weight`.
**Correction**:
```cpp
std::cout << std::setw(3) << "v1" << " - " << std::setw(3) << "v2" << " : weight\n";
```
- **Line 106**:
```cpp
void GraphMST::AddEdge(int from, int to, char weight){
```
**Severity: High**
**Issue**: Incorrect parameter type `char`, should be `int`.
**Correction**:
```cpp
void GraphMST::AddEdge(int from, int to, int weight){
```
- **Line 107**:
```cpp
AdjMatrix[from][to] = AdjMatrix[from][to];
```
**Severity: High**
**Issue**: Self-assignment, should assign `weight` to `AdjMatrix[from][to]`.
**Correction**:
```cpp
AdjMatrix[from][to] = weight;
```
- **Line 115**:
```cpp
g6.AddEdge(0, 1, 5);g6.AddEdge(0, 5, 3);;
```
**Severity: Low**
**Issue**: Extra semicolon.
**Correction**:
```cpp
g6.AddEdge(0, 1, 5);g6.AddEdge(0, 5, 3);
```
- **Line 124**:
```cpp
std::cout < "MST found by Kruskal:\n";
```
**Severity: High**
**Issue**: Incorrect output stream operator, should be `<<`.
**Correction**:
```cpp
std::cout << "MST found by Kruskal:\n";
```
- **Line 125**:
```cpp
g6.KrukalMST();
```
**Severity: High**
**Issue**: Typo in function call `KrukalMST`, should be `KruskalMST`.
**Correction**:
```cpp
g6.KruskalMST();
```
## Analysis
以Severity來判斷，ChatGPT 的結果與我的結果相差不大。然而，在Code Review上，ChatGPT 的結果有一些不同。有些錯誤對於肉眼來說較難發現，但 ChatGPT 基本上都能找到，例如逗號應該是句號的錯誤。如果由人來進行代碼審查，有時會不小心看漏這些細節，因此可以用 ChatGPT 來輔助這部分。此外，ChatGPT 似乎不會檢查註解內容是否與程式碼實作相符，它主要檢查語法錯誤。一旦註解內容會影響程式碼實作時，ChatGPT 的能力就會有所侷限，像Line 34的FindSetCollapsing，註解說要是recursive way，但實作是iterative way，這個錯誤Chatgpt就沒抓到。最後在library的部分，是有點問題的，它沒有發現這code缺少要include的library，所以在使用上，可以先用 ChatGPT 生成大致的Code Review內容，再由人來檢查，這樣會是一個比較有效的使用方式。
Google Drive
Gist
Clipboard
Sign in with Wallet
