3
\$\begingroup\$

Following is the graph I used to create adj list.

enter image description here

The code should follow all the best practices of C++ 14 and stl.

map is used instead of vector to keep label.

Any suggestions for better implementation are welcome. .h

#pragma once

#include <iostream>
#include <vector>
#include <list>
#include <unordered_map>
#include <algorithm>

using std::unordered_map;
using std::list;
using std::pair;
using std::cout;
using std::endl;
using std::make_pair;
using std::for_each;

class AdjList
{
private:

    typedef pair<int, char> edge;
    unordered_map<char , list <edge> > adjList;

public:
    void createGraph();
    void printGraph();
    void test();
};

.cpp

#include "AdjList.h"

void AdjList::createGraph()
{
    list<edge> A;
    A.push_back(make_pair(3, 'B'));
    A.push_back(make_pair(2, 'E'));

    list<edge> B; //B points nowhere

    list<edge> C;
    C.push_back(make_pair(1, 'A'));

    list<edge> D;
    D.push_back(make_pair(4, 'C'));

    list<edge> E;
    E.push_back(make_pair(4, 'D'));

    adjList['A'] = A;
    adjList['B'] = B;
    adjList['C'] = C;
    adjList['D'] = D;
    adjList['E'] = E;

}

void AdjList::printGraph()
{
    for each (auto elem in adjList)
    {
        cout << elem.first << " -> ";

        for_each(elem.second.begin(), elem.second.end(), [](auto val) {

            cout << val.second << "(" << val.first << "), ";

        });

        cout << endl;
    }
}

void AdjList::test()
{
    createGraph();
    printGraph();
}

test() is called from main to test.

Output:

A -> B(3), E(2),

B ->

C -> A(1),

D -> C(4),

E -> D(4),

\$\endgroup\$
3
\$\begingroup\$

Good work!

Do not polute the global namespace in headers

using std::unordered_map;
...

Anyone who #includes your file will have these imported in their global namespace. You should should migrate these to your .cpp file, and just use std:: for the two instances in the header.

list<> vs vector<>

There is nothing in your code that suggests list<> is preferable to vector<>. Unless you need fast insertion/removal in the middle of the structure, vector<> is preferable here.

For each ( in ) is not a thing

for each (auto elem in adjList) is not standard C++, but a MSVC extension, use range-based for instead. Furthermore, by using auto instead of auto &, you are working on copies of the adjacency list, not references.

You want this:

for(auto const& elem : adjList) {

Don't use for_each when a range-based for works.

for_each is not best practice unless you are already manipulating a predicate. range-based-for is preferable:

Like so:

for(auto const& val : elem.second) {
    cout << val.second << "(" << val.first << "), ";
}

Emplace into containers

You want to use emplace_back() instead of push_back() in containers where possible:

Like So:

list<edge> C;
C.push_back(make_pair(1, 'A')); // bad
C.emplace_back(1, 'A'); // much better

Move containers if you know you are done with them.

When you do this:

adjList['A'] = A;

You create a copy of A, when you know you are done with it. You should promote A to a RValue:

adjList['A'] = std::move(A);

You are mixing your functionality with your test harness

createGraph(); and test(); have no business being members of this class, and should be free-floating functions.

Once you do this, you will realize that there is a lot of stuff missing from your class as it does not expose the interface required to implement these simple cases.

\$\endgroup\$
2
\$\begingroup\$

Same procedure as always:

  • Don't use using in headers, at least not to modify the global namespace.
  • In a header, only include those headers that are necessary for the definitions.

Specific to your code:

  • The public API of the AdjList is useless, since you can only create a single graph with it.
  • Instead of AdjList, it should be called AdjListGraph, since it is a graph, not a list.
  • The method add_edge(char, int, char) would make the class useful. It would also free the calling code from using std::pair, which should be considered an implementation detail.
  • If you can foresee that after creation, graphs will be heavily modified by removing edges, your choice of using std::list is good. Otherwise, prefer std::vector.

In the end, your code should look like this:

AdjListGraph g;
g.add_edge('A', 3, 'B');
g.add_edge('A', 2, 'E');
g.add_edge('C', 7, 'A');
...

std::cout << "The graph is:\n";
std::cout << g;
\$\endgroup\$

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.