C++

Forum

 
Graph Adjacency List - Edge getEdge (int, int)Help!

arbhie2581 (7)
Good evening. I'm programming a graph hat handles directed, undirected, weighted and not weighted graphs that implements adjacency list. Everything works fine except for this function that I'm stuck and unable to finish. Please give me some input or advices how to finish this code. Basically what I'm trying to do is to return the edge if it exist and return null if not. Thanks!

1
2
3
4
5
6
7
8
 
Edge getEdge(int v1, int v2) const {
		list<int>::const_iterator i;
		for (i = ADJACENCY_LIST[v1].begin(); i != ADJACENCY_LIST[v1].end(); ++i) {
			if(ADJACENCY_LIST[v1].front() == v2) 
			????????????
		}
                return NULL;
	}
TheDestroyer (441)
if(ADJACENCY_LIST[v1].front() == v2)

You're looping with i, and not using it... what's the point of looping anyway??
Last edited on
arbhie2581 (7)
I didn't notice that...

1
2
3
4
5
6
7
8
9
 
Edge Graph::getEdge(int v1, int v2) const {
		list<int>::const_iterator i;
                Edge edge(v1, v2);
		for (i = ADJACENCY_LIST[v1].begin(); i != ADJACENCY_LIST[v1].end(); ++i) {
			if(ADJACENCY_LIST[i].front() == v2) 
			  return edge;
		}
                return NULL;
	}


now how would I return that properly? return edge & return NULL is error. Thanks!
Gaminic (1621)
How are you edges stored? What your function does now is make a new edge(v1, v2), then check if it exists, and if so returns it. That could work, depending on what you want to do with it. If you want to make changes to the edge, you'll need to find the actual edge, which depends on how you're storing them.

arbhie2581 (7)
this is my edge class...

1
2
3
4
5
6
7
8
9
10
11
12
 
class Edge {
public:
	int v1;		// from edge
	int v2;		// to edge
	bool directed;
	double weight;
	int distance;
	Edge();
	Edge(int v1, int v2, double weight = -1)
	: v1(v1), v2(v2), weight(weight) {
	}
};


and this is my addEdge function...

1
2
3
4
5
6
7
8
9
10
11
12
13
 
void Graph::addEdge(Edge e) {
		if (!directed) {
			ADJACENCY_LIST[e.v1].push_back(e.v2);
			ADJACENCY_LIST[e.v2].push_back(e.v1);
			adjacent = true;
			numEdges+=2;
		}
		else if (directed) {
			ADJACENCY_LIST[e.v1].push_back(e.v2);
			adjacent = true;
			numEdges++;
		}
	}


my goal is to return an edge object if the vertices exist otherwise it returns a NULL, but I can't output them properly. the logic makes sense to me (i think) but my problem is proper output.

thanks!
Gaminic (1621)
But where are your actual edges? If just addEdge for all Edges, you lose the Weight info, don't you?

You could define an edge this way:
1
2
3
4
5
6
 
class Edge {
    int v2;
    double weight;
    int distance; // Why do you need both weight & distance anyway?
    Edge* next;
}

Then, every ADJACENCY_LIST just keeps the first Edge, because every item in ADJACENCY_LIST[v1] starts at v1, so there's no reason to save that data.

This way, all edge data is saved into items that are directly inside the list; you don't need to refer to outside data.

[edit]
Instead of using push_back to add an element, you'll have to make a manual function to add edges to a list. It's still very easy:
1
2
3
4
 
void addEdge(Edge* e, int v1) { // Pass by pointer (or by ref)
    e->next = ADJACENCY_LIST[v1]; // Old "first" becomes second
    ADJACENCY_LIST[v1] = e; // e is now the first of the list
}

It all depends on how you get and process your data. It might still be easier to add "v1" as a member of every edge, but I don't really see a good reason.
Last edited on
arbhie2581 (7)
The parameters are all pre-set by my professor... (so I can't pass by reference on the addEdge function). I'm saving the v1 & v2 vertices because I need to handle direct and undirected graphs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
class Graph {
public:
	int numVertices;
	int numEdges;
	bool directed;
	bool weighted;
	bool adjacent;
	list<int> *ADJACENCY_LIST;
	static char noOfGraphs;
	Graph(int n, bool directed, bool weighted)
	: directed(directed), weighted(weighted) {
		numVertices = n;
		numEdges = 0;
		ADJACENCY_LIST = new list<int>[n];
		adjacent = false;
		noOfGraphs++;
	}
	void addEdge(Edge e) {		
		if (!directed) {
			ADJACENCY_LIST[e.v1].push_back(e.v2);
			ADJACENCY_LIST[e.v2].push_back(e.v1);
			adjacent = true;
			numEdges+=2;
		}
		else if (directed) {
			ADJACENCY_LIST[e.v1].push_back(e.v2);
			adjacent = true;
			numEdges++;
		}
	}
	int getAdjacentList(int v, Graph & g) {
		int count = 0;
		list<int>::iterator i;
		for(i = g.ADJACENCY_LIST[v].begin(); i != g.ADJACENCY_LIST[v].end(); ++i)
			if (g.adjacent) count++;
		return count;
	}
	int getNumVertices() {return numVertices;}
	int getNumEdges() {return numEdges;}
	bool isDirected() {return directed;}
	bool isWeighted() {return weighted;}
	Edge getEdge(int v1, int v2) const { // ERROR HERE...
		list<int>::const_iterator i;
		Edge edge(v1, v2);
		for (i = ADJACENCY_LIST[v1].begin(); i != ADJACENCY_LIST[v1].end(); ++i) {
			if(ADJACENCY_LIST[v1].front() == v2) 
				return edge;
		}
	}
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
class Edge {
public:
	int v1;		// from edge
	int v2;		// to edge
	bool directed;
	double weight;
	Edge *next;     // dunno how to use this yet...
	Edge();
	Edge(int v1, int v2, double weight = -1)
	: v1(v1), v2(v2), weight(weight) {
	}
};

void BFS(Graph & g, int s) {
	int v = g.getNumVertices();
	bool *visited = new bool[v];
	for (int i = 0; i < v; i++)
		visited[i] = false;
	list<int> queue;
	visited[s] = true;
	queue.push_back(s);
	list<int>::iterator i;
	cout << "Breadth-First Traversal: \t";
	while (!queue.empty()) {
		s = queue.front();
		cout << s << " ";
        queue.pop_front();

		for(i = g.ADJACENCY_LIST[s].begin(); i != g.ADJACENCY_LIST[s].end(); ++i) {
			if(!visited[*i]) {
				visited[*i] = true;
				queue.push_back(*i);
			}
		}
	}
	cout << '\n';
}

void DFS(Graph & g, int s) {
	int v = g.getNumVertices();
	bool *visited = new bool[v];
	for (int i = 0; i < v; i++)
		visited[i] = false;
	cout << "Depth-First Traversal: \t\t";
	RDFS(g, s, visited);
	cout << "\n\n";
}

void RDFS(Graph & g, int v, bool visited[]) { // DFS Helper
	visited[v] = true;
    cout << v << " ";
	list<int>::iterator i;
    for(i = g.ADJACENCY_LIST[v].begin(); i != g.ADJACENCY_LIST[v].end(); ++i)
        if(!visited[*i])
            RDFS(g, *i, visited);
}


Thanks for the feedbacks!
Gaminic (1621)
Don't really have time to go over all of it right now, but it might help us if you show the piece of code where Edge input is found (from a file, I suppose?) and added to the graph.

(P.S.: For a undirected graph, you could simply add an edge "to V2" to V1's and an edge "to V1" to V2's adj.list.)

[edit]
I'm sorry, just realized I've been getting seriously sidetracked. To your original question: (your code)
1
2
3
4
5
6
7
8
9
 
Edge Graph::getEdge(int v1, int v2) const {
		list<int>::const_iterator i;
                Edge edge(v1, v2);
		for (i = ADJACENCY_LIST[v1].begin(); i != ADJACENCY_LIST[v1].end(); ++i) {
			if(ADJACENCY_LIST[i].front() == v2) 
			  return edge;
		}
                return NULL;
	}

This isn't right. You're looking for (v1, v2), thus you shouldn't be going through ADJ_LIST[i], but always ADJ_LIST[j]. Secondly, you should be checking the entire list, not .front().

You have an iterator 'i' which begins as ADJ[v1].begin() and goes to end(). All you need to do is check the edge pointed to by the iterator and see if it goes to v2.

You can get the element pointed to by dereferncing the iterator, e.g.:
1
2
 
list<int>::iterator i = myList.begin();
cout << *i; // Will print the first int in the list.

Thus, all you need to do is to check if "*i == v2".
Last edited on
arbhie2581 (7)
I think I'm on the right track here, BTW I input my edges on main not from a file. Thank you so much for having time and patience to help me.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
Graph a(8, U, N); 
	Edge a0(0, 1);
	Edge a1(1, 3);
	Edge a2(6, 3);
	Edge a3(4, 5);
	Edge a4(1, 2);
	Edge a5(3, 7);
	Edge a6(3, 4);
	a.addEdge(a0);
	a.addEdge(a1);
	a.addEdge(a2);
	a.addEdge(a3);
	a.addEdge(a4);
	a.addEdge(a5);
	a.addEdge(a6);
	cout << a;
	BFS(a, 0);
	DFS(a, 0);


your example cout << *i is very helpful, makes me understand more abut this.

Since the logic is getting clearer now, my question now is how to return an object when vertices are found or return NULL if nothing there?

this seems not to work... 
1
2
3
 
PSEUDO
if (found) return edge; // is this correct way to return the edge?
else return NULL; // error: no suitable constructor exists to convert from "int" to "Edge"

Gaminic (1621)
Since you're returning by value, you can't simply return NULL. You can, however, make a specific object chosen to represent a "null object", for example Edge(0,0). Since 0->0 is a useless/meaningless edge, you can easily add check code to compare the returned edge to "Edge(0,0)".

By the way, "return edge" would here simply be "return *i", since i points to the "found" edge!
arbhie2581 (7)
Thank you very much for the help!
Topic archived. No new replies allowed.