Graphs

[yem]

Hi,
Visual Studio seems to be telling me that the iterator it is const (and therefor not letting me return it) although I can't seem to figure out why?
Anyone know why and what I can do to change that?
Thanks

Vertex* Graph::findVertex(string s)
{
	map<Vertex, list<Vertex>>::iterator it;

	for (it = graphMap.begin(); it != graphMap.end(); it++)
	{
		if (it->first.Key == s)
			return it;
	}

	return nullptr;
}

[yem]

Here's all of my code so far.
NOTE: There are parts missing as I am still in the process of writing it. I am just posting everything in case something that I wrote elsewhere directly corelates with this issue (the iterator being const).

#include "GraphElements.h"

Edge::Edge(Vertex* t)
{
	target = t;
}

bool Edge:: operator==(Edge& e)
{
	if (this->target != e.target)
		return false;

	return true;
}

Vertex::Vertex(string key)
{
	Key = key;
	color = Color::White;
}

void Vertex::addEdge(Edge e)
{
	EdgeList.push_back(e);
}

int Vertex::numOfNeighbors()
{
	return EdgeList.size();
}

bool Vertex::targetExist(Vertex* v)
{
	list<Edge>::iterator it;

	for (it = EdgeList.begin(); it != EdgeList.end(); it++)
	{
		if (*v == *(it->target))
			return true;
	}

	return false;
}

bool Vertex:: operator==(Vertex& v)
{
	if (this->Key == v.Key)
		return true;

	return false;
}

void Vertex::print()const
{
	cout << Key << ": ";

	//list<Edge>::iterator it;

	for (list<Edge>::const_iterator it = EdgeList.cbegin(); it != EdgeList.cend(); it++)
	{
		cout << it->target->Key << " ";
	}
}

#include<string>
#include <list>
#include<iostream>

#pragma once

using namespace std;

class Vertex;

class Edge
{
public:
	Edge(Vertex* t);
	bool operator==(Edge& e);

	//fields
	Vertex* target;
};

enum class Color {White,Gray,Black};

class Vertex
{
public:
	Vertex(string key);
	void addEdge(Edge);
	int numOfNeighbors();
	bool targetExist(Vertex* v);
	bool operator==(Vertex& v);
	void print()const;
	friend class Graph;
private:
	string Key;
	Color color;
	list<Edge> EdgeList;
};

#include "Graph.h"

Vertex* Graph::findVertex(string s)
{
	map<Vertex, list<Vertex>>::iterator it;

	for (it = graphMap.begin(); it != graphMap.end(); it++)
	{
		if (it->first.Key == s)
			return it;
	}

	return NULL;
}

bool Graph::addVertexShell(string v)
{
	Vertex tempV = Vertex(v);
	list<Vertex> tempN;
	graphMap.insert(pair<Vertex, list<Vertex>>(tempV, tempN));
}

bool Graph::delVertexShell(string v)
{


	// delete edges that are incident (to or from ) it

	list<Vertex>::iterator it;

	for(it=)

}

bool Graph::printAll()
{
	map<Vertex, list<Vertex>>::iterator it;

	for (it = graphMap.begin(); it != graphMap.end(); it++)
	{
		it->first.print();
	}

	return true;
}

#include"GraphElements.h"
#include<map>
#include<list>

#pragma once

using namespace std;

class Graph
{
public:
	Graph();
	~Graph();
	Vertex* findVertex(string s);
	bool addVertexShell(string v);
	bool delVertexShell(string v);
	bool addEdgeShell(string s, string t);
	bool delEdgeShell(string s, string t);
	bool printNeighborsShell(string k);
	bool printFollowersShell(string k);
	bool printAllReachedShell(string k);
	bool printAll();
private:
	map<Vertex, list<Vertex>> graphMap;
};

#include<iostream>
#include<string>
#include"Graph.h"

using namespace std;

int main()
{
	try {
		string v1, v2, name;
		Graph g;
		int choice;
		cout << "choose one of the following:\n";
		cout << "1 - add a writer\n";
		cout << "2 - delete a writer\n";
		cout << "3 - add a follow up (edge)\n";
		cout << "4 - delete a follow up (edge)\n";
		cout << "5 - print all neighbors (followed)\n";
		cout << "6 - print all followers\n";
		cout << "7 - print all vertices that can be reached from V\n";
		cout << "8 - print all the graph\n";
		cout << "10 - exit";
		cout << endl;

		do
		{
			cin >> choice;
			switch (choice)
			{
			case 1:cout << "enter the writer name\n";
				cin >> v1;
				g.addVertexShell(v1);
				break;
			case 2:cout << "enter the writer name\n";
				cin >> v1;
				if (g.delVertexShell(v1))
					cout << "success";
				else
					cout << "ERROR";
				break;
			case 3:cout << "enter the follower and the writer\n";
				cin >> v1 >> v2;
				if (g.addEdgeShell(v1, v2))
					cout << "success";
				else
					cout << "ERROR";
				break;
			case 4:cout << "enter the follower and the writer\n";
				cin >> v1 >> v2;
				if (g.delEdgeShell(v1, v2))
					cout << "success";
				else
					cout << "ERROR";
				break;
			case 5:cout << "enter the v you want to print its neighbours\n";
				cin >> v1;
				g.printNeighborsShell(v1);
				break;
			case 6:cout << "enter the v you want to its followers\n";
				cin >> v1;
				g.printFollowersShell(v1);
				break;
			case 7:
				cout << "enter writer\n";
				cin >> v1;
				g.printAllReachedShell(v1);
				break;

			case 8:
				cout << "The graph:\n";
				g.printAll();
				break;

			case 10:cout << "byebye";  break;
			default:cout << "ERROR";

			}
			cout << endl;
		} while (choice != 10);
	}
	catch (string s)
	{
		cout << s << endl;
	}
	return 0;
}

[seeplus]

The map key is const (can't be changed) - so you can't return an iterator that would allow the key to be changed.

Also, the return type is a pointer to vertex, yet you are returning an iterator of type map<Vertex, list<Vertex>>::iterator ??

[yem]

what would be the correct way then to go through the map and try and find a vertex that has the same key?

Also isn't an iterator a pointer to that type of object (in this case an element of list)?

[seeplus]

Perhaps something like this (not tried):

Vertex* Graph::findVertex(string s)
{
	map<Vertex, list<Vertex>>::iterator it;

	for (it = graphMap.begin(); it != graphMap.end(); it++)
	{
		if (it->first.Key == s)
			return &(it->first);
	}

	return nullptr;
}

[yem]

Tried that. got the following error:

Error (active) E0120 return value type does not match the function type

[seeplus]

Try returning const Vertex* instead of Vertex*

[seeplus]

This compiles OK - but not tried!

#include <map>
#include <string>
#include <list>

using namespace std;

struct Vertex {
	string Key;
};

map<Vertex, list<Vertex>> graphMap;

const Vertex* findVertex(string s)
{
	map<Vertex, list<Vertex>>::iterator it;

	for (it = graphMap.begin(); it != graphMap.end(); it++)
	{
		if (it->first.Key == s)
			return &(it->first);
	}

	return nullptr;
}

or if allowed by compiler:

const Vertex* findVertex(const string& s)
{
	for (auto it = graphMap.begin(); it != graphMap.end(); ++it)
		if (it->first.Key == s)
			return &(it->first);

	return nullptr;
}

or even:

const Vertex* findVertex(const string& s)
{
	for (const auto& [ver, lst] : graphMap)
		if (ver.Key == s)
			return &ver;

	return nullptr;
}

Why return a pointer to a key in a map? Why not just return the iterator - with .end() if not found?

auto findVertex(const string& s)
{
	for (auto it = graphMap.begin(); it != graphMap.end(); ++it)
		if (it->first.Key == s)
			return it;

	return graphMap.end();
}

[yem]

"Why return a pointer to a key in a map? Why not just return the iterator - with .end() if not found?"

I was actually just thing that before I saw your response. Especially because if I return it as a const i wont be able to edit it after, right?

if I wanted to avoid the "auto" keyword, this would be the right syntax, right?

map<Vertex, list<Vertex>>::iterator Graph:: findVertex(const string& s)
{
	for (map<Vertex, list<Vertex>>::iterator it = graphMap.begin(); it != graphMap.end(); ++it)
		if (it->first.Key == s)
			return it;

	return graphMap.end();
}

[dhayden]

The real problem is the way you're representing the Vertices. What is graphMap supposed to represent? Since it maps a vertex to a list of vertices, does it represent the edges from the key vertex? But then shouldn't it map to a list of pointers to vertices? Otherwise you can't have more than one edge into a vertex.

You'll never get the code right unless you're crystal clear on what the data represents. This is why it's a good idea to comment the data. It lets you put a stake in the group to declare what the data represents.

Your graph needs a collection of vertices with two key properties:
- They can't move, since each Edge contains a pointer to the vertex
- You want quick access by vertex string.

So maybe something like this:
map<string, unique_ptr<vertex> > vertices;

Then findVertex is just

auto iter = vertices.find(s);
return (iter == vertices.end() ? nullptr : iter->second.get());

[yem]

dhayden

it's a homework assignment so it's not entirely up to me.

-the class vertex has to have 2 fields
1) a string for a key
2) a list of edges (it's a directed graph)

-the class that represents the graph itself has to have a map where the key is a Vertex which is mapped to a list of neighbors (I understood that to mean a list of Vertices which either has an edge to our Vertex or our Vertex has an edge to it)

[yem]

shouldn't the following code return an iterator that would point to a level on the map?
based on the error from the second piece of included code it seems to be returning a Vertex and not a pointer to that level?

map<Vertex, list<Vertex>>::iterator Graph::findVertex(const string& s)
{
	for (map<Vertex, list<Vertex>>::iterator it = graphMap.begin(); it != graphMap.end(); ++it)
		if (it->first.Key == s)
			return it;

	return graphMap.end();
}

bool Graph::delVertexShell(string v)
{
	map<Vertex, list<Vertex>>::iterator temp = (findVertex(v))->first;  //find the Vertex that needs to be deleted (this line causes the error)

	// delete edges that are incident (to or from ) it
	
}

[seeplus]

->first returns a type Vertex (type of map key), not an iterator so:

bool delVertexShell(const string& v)
{
	const map<Vertex, list<Vertex>>::iterator temp = findVertex(v);

	if (temp != graphMap.end()) {
		const Vertex &vert = temp->first;  //find the Vertex that needs to be deleted (this line causes the error)

		// delete edges that are incident (to or from ) it
	}
}

This is where auto comes into it's own!

bool delVertexShell(const string& v)
{
	const auto temp = findVertex(v);

	if (temp != graphMap.end()) {
		const auto& vert = temp->first;  //find the Vertex that needs to be deleted (this line causes the error)

		// delete edges that are incident (to or from ) it
	}
}

Why not use auto??

[yem]

the submission box for my college uses a very old compiler and i'm pretty certain from previous times that the compiler doesn't take auto

[yem]

with this method will i be able to access

temp->second

afterwards?

Once I find the correct Vertex I'll need to access second

[seeplus]

Complain long and loud about being forced to use an extremely out-of-date C++ compiler! It sounds like you're using a C++98 compiler - which is 22 years out of date! The current C++ standard is C++20!

[yem]

lol. I'm in second year and we've been complaining about that for more than a year and a half. All of the professors are on our side but the IT department keeps on saying that they can't update it on the online checker for technical reasons. I'm not sure why.
I'm pretty sure that you're right that it's a C++98 compiler. I've had to rewrite a lot of homework assignments after I tried submitting them and they don't even get compiled despite working perfectly on Visual Studio.

[seeplus]

IT department keeps on saying that they can't update it on the online checker for technical reasons.

Bo***cks! There are various on-line c++ compilers that support the latest C++!

The IT people just don't want to get off their a***s and do some work.

[yem]

probably.

either way I can't seem to figure out how to delete a Vertex from the graph.

my thought process is as follows:

1) for each Vertex in the neighbor list (the second field in the map) check if it's a directed edge from our Vertex using the targetExist function (our vertex is the source).

2) if it's not, then access that neighbor Vertex through the neighbor list in the map and remove that edge from his edgeList .

3) remove the intended Vertex from the graphMap

I've been having a lot of issues with the implementation though (as you can see above)

[yem]

actually, since I already have the key shouldn't I just be able to access the mapped value through the [] operator?

https://www.cplusplus.com/reference/map/map/operator[]/