0
\$\begingroup\$

The following code is applying the depth-first search and breadth-first search algorithm to find the shortest path from bottom left to top right in a 10 x 10 grid. I need reviews to improve my implementation and code quality.

Graph.h:

#include <iostream>
#pragma once
using namespace std;
struct point{
    int x, y;
    bool operator>(point pnt){
        return (this->x > pnt.x) && (this->y > pnt.y);
    }
};
struct node{
    char val; 
    bool visited; 
    point prev;
    node(char v = 0){
        val = v;
        visited = false;
        prev = {-1, -1};
    }
};
class GRAPH{
    size_t rows, cols;
    char route;
    node** nodes = nullptr;
public:
    GRAPH(size_t n, size_t m, char **vals = nullptr, char rout = '*'){
        rows = n;
        cols = m;
        route = rout;
        if(vals){
            nodes = new node*[rows];
            for(size_t i = 0; i < rows; i++){
                nodes[i] = new node[cols];
                for(size_t j = 0; j < cols; j++){
                    nodes[i][j] = (vals[i][j]);
                }
            }
            for(size_t i = 0; i < rows; i++)
                delete vals[i];
            delete[]vals;
        }
    }
    void display(){
        for(size_t i = 0; i < rows; i++){
            for(size_t j = 0; j < cols; j++)
                cout << nodes[i][j].val << ' ';
            cout << '\n';
        }
        cout << '\n';
    }
    bool inside_graph(point pnt){
        return pnt.x < rows && pnt.y < cols; 
    }
    bool is_on_route(point pnt){
        return this->inside_graph(pnt) && this->at(pnt).val == route;
    }
    node& at(point pnt){
        return nodes[pnt.x][pnt.y];
    }
    point size(){
        return {rows, cols};
    }
    ~GRAPH(){
        for(size_t i = 0; i < rows; i++)
            delete nodes[i];
        delete[]nodes;
    }
};

Solve.cpp

#include <iostream>
#include <queue>
#include <fstream>
#include "graph.h"
using namespace std;
int dfs_cnt = 0, bfs_cnt = 0;
GRAPH init_graph();
void DFS(GRAPH&, point, point);
void BFS(GRAPH&, point, point);
void solve(GRAPH&, bool);
void mark(GRAPH&, char);
int main()
{
    GRAPH graph_for_DFS = init_graph();
    DFS(graph_for_DFS, {graph_for_DFS.size().x - 1, 0}, {0, graph_for_DFS.size().y - 1});
    mark(graph_for_DFS, '+');
    graph_for_DFS.display();
    solve(graph_for_DFS, 0);

    GRAPH graph_for_BFS = init_graph();
    BFS(graph_for_BFS, {graph_for_BFS.size().x - 1, 0}, {0, graph_for_BFS.size().y - 1});
    mark(graph_for_BFS, '+');
    graph_for_BFS.display();
    solve(graph_for_BFS, 1);
    return 0;
}
GRAPH init_graph(){
    dfs_cnt = bfs_cnt = 0;
    ifstream maze("Maze.txt");
    size_t n, m;
    maze >> n >> m;
    char **grid = new char* [n];
    for(size_t i = 0; i < n; i++){
        grid[i] = new char[m];
        maze >> grid[i];
    }
    maze.close();
    return GRAPH(n, m, grid);
}
void DFS(GRAPH& graph, point src, point dest){
    dfs_cnt++;
    if(src > dest)
        return;
    point tmp = {src.x - 1, src.y};
    if(graph.is_on_route(tmp) && !graph.at(tmp).visited){
        graph.at(tmp).visited = true;
        graph.at(tmp).prev = src;
        DFS(graph, tmp, dest);
    }
    tmp = {src.x, src.y + 1};
    if(graph.is_on_route(tmp) && !graph.at(tmp).visited){
        graph.at(tmp).visited = true;
        graph.at(tmp).prev = src;
        DFS(graph, tmp, dest);
    }
}
void BFS(GRAPH& graph, point src, point dest){
    queue<point> q;
    q.push(src);
    point curr = src;
    while(!q.empty() && !(curr > dest)){
        curr = q.front();
        graph.at(curr).visited = true;
        q.pop();
        point tmp = {curr.x - 1, curr.y};
        bfs_cnt++;
        if(graph.is_on_route(tmp) && !graph.at(tmp).visited){
            q.push(tmp);
            graph.at(tmp).visited = true;
            graph.at(tmp).prev = curr;
            bfs_cnt++; 
        }
        tmp = {curr.x, curr.y + 1};
        if(graph.is_on_route(tmp) && !graph.at(tmp).visited){
            q.push(tmp);
            graph.at(tmp).visited = true;
            graph.at(tmp).prev = curr;
            bfs_cnt++;
        }
    }
}
void mark(GRAPH& graph, char mrk){
    for(node *tmp = &graph.at({0, graph.size().y - 1}); tmp != &graph.at({graph.size().x - 1, 0}); tmp = &graph.at(tmp->prev))
        tmp->val = mrk;
    graph.at({graph.size().x - 1, 0}) = mrk;
}
void solve(GRAPH& graph, bool is_BFS){
    ofstream sol(is_BFS ? "BFS_Solved_Maze.txt" : "DFS_Solved_Maze.txt");
    size_t n = graph.size().x, m = graph.size().y;
    sol << (is_BFS? bfs_cnt : dfs_cnt) << '\n';
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++)
            sol << graph.at({i, j}).val << ' ';
        sol <<'\n';
    }
}

Maze.txt

10 10
########**
########**
#######**#
##******##
##*****###
##*****###
#***######
#*########
**########
**########
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

The comparison operator in point is broken, as you have many points that are not equal (equivalent) but neither is greater that the other. The usual way for comparing two values in a struct like this is to only look at the second element if the first values are equal. You could make a std::pair from the two points and compare those. Using std::tie is an easy way to do this. The member function should be const, and the parameter should be passed by a const reference (although some would disagree when passing a small struct such as point).

bool operator>(const point &pnt) const {
    return std::tie(x, pnt.x) > std::tie(y, pnt.y);
}

You use a lot of manual memory management in GRAPH. You're missing copy and move constructors and assignment operators, which will lead to memory problems. This violates the Rule of Three (or five). Replace it all with std::vector, and the memory management will all be taken care of for you (also, the destructor could then be omitted or defaulted).

The constructor for GRAPH assumes that the values have been allocated. As it does not own the memory passed in by vals, it should not attempt to free it. It might also be helpful (for the longer term use of the class) to have a default constructor and a way to resize an existing GRAPH object.

display, inside_graph, and is_on_route should also be const member functions. Consider adding in an overload of at that is a const member function that returns by value (or const reference). In the standard library, member functions named at will perform bounds checking, and throw an exception if a subscript is out of bounds. You could add that to at, and add two overloads for operator[] that would not perform the bounds checking.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.