1
\$\begingroup\$

there is my final code for implementing a Graph in C++ using adjacency list and Object-oriented. I got some help from StackOverflow and it was really helpful, but now I would ask about some advice for improving and a possible way of implementing two functions: isPath( v, w ) for finding if two nodes are connected and isConnected(graph) returning "yes" if the graph is strongly connected otherwise "no".

The code:

#include <iostream>
#include <vector>

using namespace std;

struct Edge {
    int source;
    int target;
};

class Graph
{
private:
    int numOfNodes;
    vector<vector<int>> baseVec;

public:
    Graph(int numOfNodes) : numOfNodes(numOfNodes), baseVec(numOfNodes) {}

    void newEdge(Edge edge) {
        if (edge.source >= numOfNodes || edge.target >= numOfNodes
            || edge.source < 0 || edge.target < 0) {
            cout << "Invalid edge!\n";
            return;
        }
        baseVec[edge.source].emplace_back(edge.target);
        baseVec[edge.target].emplace_back(edge.source);
    }

    void display() {
        for (vector<vector<int>>::size_type i = 0; i < baseVec.size(); i++) {
            cout << "\n Adjacency list of vertex " << i << "\n head: ";
            for (vector<int>::size_type j = 0; j < baseVec[i].size(); j++)
                cout << baseVec[i][j] << " ";
            std::cout << std::endl;
        }
    }
};

int main() {
    int vertex;
    cout << "Enter number of nodes: ";
    cin >> vertex;

    Graph graph(vertex);

    while (true) {
        int source, target;
        cout << "Enter edge ex.1 2 (-1 -1 to exit): \n";
        cin >> source >> target;
        if ((source == -1) && (target == -1))
            break;
        graph.newEdge({ source, target });
    }
    graph.display();
    return 0;
}

I really can't find many things to change, so I wrote the isConnected() function. Maybe it has some weaknesses or errors. Hope it's useful and I'm still waiting for advice. Thank you!

Code inside the class:

    bool isConected(std::vector<int> nodeVec)
        {

            for (st

d::vector<std::vector<int>>::size_type i = 0; i < baseVec.size(); i++)
        {
            if (baseVec[i].empty())
            {
                return false;
            }
        }
        for (std::vector<std::vector<int>>::size_type i = 0; i < baseVec.size(); i++)
        {
            for (std::vector<int>::size_type j = 0; j < baseVec[i].size() + 1; j++)
            {
                if (baseVec[i][j] == nodeVec[j + 1])
                {
                    return true;
                }
            }
        }
    }

The line in main:

std::vector<int> nodeVec;
    for (int i = 0; i < vertex; i++)
    {
        nodeVec.emplace_back(i);
    }

And:

if (graph.isConected(nodeVec) == true)
{
    std::cout << "Yes\n";
}
else
{
    std::cout << "No\n";
}
\$\endgroup\$
1
\$\begingroup\$

Some comments -

  • cout << "Invalid edge" is not a sane error-relaying mechanism. The C++ way to do things is to throw an exception. The calling code could catch the exception and print an error, or could let the app exit if this is a serious-enough error.
  • void display() needs to be void display() const. It doesn't modify anything.
  • Don't iterate through an STL container using an integer index. Iterate using an iterator. If you don't know what I mean, google around or read https://www.geeksforgeeks.org/iterators-c-stl/
\$\endgroup\$
  • \$\begingroup\$ What do you mean to "Don't iterate through an STL container using an integer index."? Which lines I have to change? \$\endgroup\$ – Top4o Nov 19 '18 at 14:35
  • 1
    \$\begingroup\$ for (vector<vector<int>>::size_type i = 0; i < baseVec.size(); i++) { \$\endgroup\$ – Reinderien Nov 19 '18 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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