0

I am trying to implement depth-first traversal for an undirected graph using C++. I am using the map with struct as key and value. I am using Stack to implement depth-first traversal and Use one extra variable to handle the undirected graph. Below is the program

#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <iterator>

struct graphNode
{
    std::string node;
    int visited;

    graphNode() : node(""), visited(0)
    {
        //std::cout << "Default constructor called\n";
    }

    graphNode(std::string _node, int _val) : node(_node), visited(_val)
    {
        //std::cout << "Copy constructor called node:" << node << "\n";
    }
};

bool operator<(const graphNode& a, const graphNode& b)
{
    //std::cout << "operator < called for " << this->node << " and " << a.node << "\n";
    return a.node < b.node;
}

bool operator==(const graphNode& a, const graphNode& b)
{
    //std::cout << "operator == called for " << this->node << " and " << a.node << "\n";
    return a.node == b.node;
}

using graphType = std::map<graphNode, std::vector<graphNode>>;
using edgeListType = std::multimap<std::string, std::string>;

graphType graph;

void printGraph()
{
    std::cout << "{\n";
    for(auto eachNode : graph)
    {
        std::cout << "\t{ " << eachNode.first.node << " ,{ ";

        for(auto eachNeighbor : eachNode.second)
        {
            std::cout << eachNeighbor.node << " ";
        }
        std::cout << "}}\n";
    }
    std::cout << "};\n";
}

void buildGraph(edgeListType& edgeList)
{
    for(auto each : edgeList)
    {
        //std::cout << "Taking " << each.first << " " << each.second << "\n";
        //graph.insert({{each.first, 0}, {{each.second, 0}}});
        //graph.insert({{each.second, 0}, {{each.first, 0}}});
        graph[{each.first, 0}].push_back({each.second, 0});
        graph[{each.second, 0}].push_back({each.first, 0});
        //printGraph();
    }
}

void updateVisited(graphNode source)
{
    graphType::iterator itr = graph.find(source);
    if(itr != graph.end())
    {
        itr->first.visited = 1;
    }
}

void depthFirstTraversal(graphNode source)
{
    std::stack<graphNode> _stack;
    _stack.push(source);

    while(!_stack.empty())
    {
        graphNode _top = _stack.top();
        if(_top.visited)
        {
            continue;
        }
        _stack.pop();
        std::cout << _top.node << "\n";
        for(auto each : graph.at(_top))
        {
            _stack.push(each);
        }
    }
}

int main()
{
    edgeListType edgeList =
    {
        {"i", "j"},
        {"k", "i"},
        {"m", "k"},
        {"k", "l"},
        {"o", "n"}
    };
    std::cout << "Edge List size:" << edgeList.size() << "\n";

    buildGraph(edgeList);
    //printGraph();

    depthFirstTraversal(graph.begin()->first);
    return 0;
}

When I try to compile this code, I get this error

UndirectedGraph.cpp: In function ‘void updateVisited(graphNode)’:
UndirectedGraph.cpp:75:28: error: assignment of member ‘graphNode::visited’ in read-only object
   75 |         itr->first.visited = 1;
      |         ~~~~~~~~~~~~~~~~~~~^~~

My question is, how and why is my map read only?

user17732522
  • 53,019
  • 2
  • 56
  • 105
  • 9
    The key (`->first`) in a `std::map` is `const`. The map is ordered according to its value, so if you could change it that would mess up the ordering. – user17732522 Apr 08 '22 at 14:45
  • If `visited` takes no part in the ordering of `graphNode`s, you may be able to safely declare it [`mutable`](https://en.cppreference.com/w/cpp/language/cv). – user4581301 Apr 08 '22 at 14:55
  • Or `visited` should be part of the value rather than the key. e.g. `std::map>>` – Kevin Apr 08 '22 at 14:58

0 Answers0