Neighbors in directed graph

[clarkkent]

Do predecessors of a vertex count as one of its neighbors? I want to display each vertex's neighbors but I keep getting its predecessor as one of its neighbors, This is the function for adding directed edges, what should I change so I only get its neighbors and not its predecessor.

void addDirectedEdge(vertex * x, vertex * y, float z)
{
x->neighbors.push_back(y);
y->dist = z;
}

[ne555]

> I want to display each vertex's neighbors but I keep getting its predecessor as one of its neighbors
perhaps you should show your "display neighbours" function.


> y->dist = z;
`distance' is a property of an edge, not of a vertex
when adding another edge pointing to `y' you'll lose that value.

Also, `z' is a terrible name.

[clarkkent]

thanks for your response, removing that part dis not help, when I try to display each vertex and its neighbors I still get the each vertex's predecessors as one of the neighbors.


This is my code

#include <string>
#include <list>
#include <queue>
#include <vector> 

using namespace std;

class directedGraph
{
private:
	class vertex
	{
	public:
		string data;
		list<vertex*> neighbors;
		bool visited; 
		vertex* predecesor; 
		float dist; 
		vertex*path; 

		vertex(string x)
		{
			data = x;
		}
		
	};

	list<vertex*> vertexList;

	//locate vertex containg value x
	vertex * findVertex(string x)
	{
		for each(vertex * v in vertexList)
		{
			if (v->data == x)
				return v;
		}
		return NULL;
	}

public:

	directedGraph()
	{
	}

	void addVertex(string x)
	{
		vertexList.push_back(new vertex(x));
	}

	//add directed edge going from x to y
	void addDirectedEdge(string x, string y)
	{
		vertex * xVert = findVertex(x);
		vertex * yVert = findVertex(y);

		xVert->neighbors.push_back(yVert); //I would think that this should only add y to x's neighbors, but when I try to display I  get x as one of y's neighbors
	}

	void addEdge(string x, string y)
	{
		addDirectedEdge(x, y);
		addDirectedEdge(y, x);
	}

	//display all vertices and who they connect to
	void testDisplay()                                     //Could the problem be in the display function? 
	{
		for each(vertex * v in vertexList)
		{
			cout << v->data << ": ";
			for each(vertex * u in v->neighbors)
			{
				cout << u->data << ", ";
			}
			cout << endl;
		}
	}

	}

};

[ne555]

¿for each?


I don't see anyting obviously wrong on how you are adding the edge, please provide a testcase. http://www.eelis.net/iso-c++/testcase.xhtml


> I still get the each vertex's predecessors as one of the neighbors.
I don't see where you set the ``predecesor' (¿what's that?)

[clarkkent]

I set the predecessor in the Breadth first search function which I did not include since I thought it had nothing to do with the problem I am having.

I tried the testcase but got an error, which I don't understand since it works on visual studio.
http://codepad.org/Ihdr5woD

when I run on Visual Studio i get something like this

a b c
b a d
c a d e e
d b c e
e c c d f
f e

the first letter on each row is the vertex and then its neighbors are listed, but for example if you look at vertex d, according to my inputs it should not point to any other vertex yet I get as its neighbors all the vertex that point to it, should that happen? In a directed graph do the predecessors count as neighbors?

[ne555]

//for each(vertex * u in v->neighbors)
for(vertex *u : v->neighbors) //c++11 

I guess that `for each' is an extension of your compiler.


In `main()' you use `addEdge()', that's for non-directed graph.

	void addEdge(string x, string y) //for non-directed edges
	{
		addDirectedEdge(x, y); //adds the two direction
		addDirectedEdge(y, x);
	}

you should use `addDirectedEdge()' instead.

[clarkkent]

Wow I didn't see that, thank you.