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?