C++

Forum

 
Represent a graph using adjacent list

Lacy9265 (119)
Write a C++ class derived from GraphInterface file. Use an adjacent list to represent the graph I have already done this with an adjacent matrix but now I need to do it with adjacent list. How can I take my code used from the adjacent matrix and change it so it is for an adjacent list. This post includes GraphInterface.h and Graph.h file.

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
 
// GraphInterface.h
 #ifndef _GRAPH_INTERFACE
#define _GRAPH_INTERFACE

 template < class LabelType>
class GraphInterface
 {
 public:

/** Gets the number of vertices in this graph.
@pre   None.
 @return  The number of vertices in the graph. */
virtual int getNumVertices() const = 0;
		
 /** Gets the number of edges in this graph.
  @pre   None.
  @return  The number of edges in the graph. */
 virtual int getNumEdges() const = 0;


   /** Creates an undirected edge in this graph between two vertices
   that have the given labels. If such vertices do not exist, creates
   them and adds them to the graph before creating the edge.
   @param start  A label for the first vertex.
   @param end  A label for the second vertex.
   @param edgeWeight  The integer weight of the edge.
  @return  True if the edge is created, or false otherwise. */
  virtual bool add(LabelType start, LabelType end, int edgeWeight) = 0;


  /** Removes an edge from this graph. If a vertex has no other edges,
  it is removed from the graph since this is a connected graph.
  @pre  None.
 @param start  A label for the first vertex.
  @param end  A label for the second vertex.
 @return  True if the edge is removed, or false otherwise. */
 virtual bool remove(LabelType start, LabelType end) = 0;


  /** Gets the weight of an edge in this graph.
   @return  The weight of the specified edge.
 If no such edge exists, returns a negative integer. */
 virtual int getEdgeWeight(LabelType start, LabelType end) const = 0;
	

  /** Performs a depth-first search of this graph beginning at the given
vertex and calls a given function once for each vertex visited.
 @param start  A label for the first vertex.
 @param visit  A client-defined function that performs an operation on
  or with each visited vertex. */
	virtual void depthFirstTraversal(LabelType start, void visit(LabelType&)) = 0;


 /** Performs a breadth-first search of this graph beginning at the given
  vertex and calls a given function once for each vertex visited.
  @param start  A label for the first vertex.
 @param visit  A client-defined function that performs an operation on
   or with each visited vertex. */
 virtual void breadthFirstTraversal(LabelType start, void visit(LabelType&)) = 0;


 /** Destroy this graph and frees assigned memory*/
 virtual ~GraphInterface(){ }
 }; // end GraphInterface
#endif



// Graph.h file
#include "GraphInterface.h"
#include <string>
#include <fstream>
#include <iostream>
#include <vector>


#ifndef _GRAPH
#define _GRAPH

#include "GraphInterface.h"

template<class LabelType>
class Graph : public GraphInterface<LabelType>
{
private:
    // Define maximum number of nodes
    static const int size = 10;
    int adj[size][size] = { 0 };
    bool visited[size] = { 0 };

public:
    Graph();

    int getNumVertices() const;

    
    int getNumEdges() const;

    bool add(LabelType start, LabelType end, int edgeWeight);

    
    bool remove(LabelType start, LabelType end);

   
    int getEdgeWeight(LabelType start, LabelType end) const;

    
    void depthFirstTraversal(LabelType start, void visit(LabelType&));

    
    void breadthFirstTraversal(LabelType start, void visit(LabelType&));
};

template<class LabelType>
Graph<LabelType>::Graph()
{}

template<class LabelType>
int Graph<LabelType>::getNumVertices() const
{
    return size;
}

template<class LabelType>
int Graph<LabelType>::getNumEdges() const
{
    int edgeCount = 0;
    for (int i = 0; i < size; ++i)
        for (int j = 0; j < size; ++j)
            if (adj[i][j] != 0)
                ++edgeCount;

    return edgeCount / 2;
}

template<class LabelType>
bool Graph<LabelType>::add(LabelType start, LabelType end, int edgeWeight)
{
    adj[start][end] = edgeWeight;
    adj[end][start] = edgeWeight;
    return true;
}

template<class LabelType>
bool Graph<LabelType>::remove(LabelType start, LabelType end)
{
    adj[start][end] = 0;
    adj[end][start] = 0;
    return true;
}

template<class LabelType>
int Graph<LabelType>::getEdgeWeight(LabelType start, LabelType end) const
{
    return adj[start][end];
}

template<class LabelType>
void Graph<LabelType>::depthFirstTraversal(LabelType start, void visit(LabelType&))
{
    // Visit the current node
    visit(start);

    // Mark the current node as visited
    visited[start] = true;

    // For all other nodes
    for (int i = 0; i < size; ++i) {
        if (adj[start][i] != 0 && (!visited[i]))
            depthFirstTraversal(i, visit);
    }
}

template<class LabelType>
void Graph<LabelType>::breadthFirstTraversal(LabelType start, void visit(LabelType&))
{
    // Vector that contains the adjacent nodes
    std::vector<LabelType> alist;
    alist.push_back(start);

    // Mark current node as visited
    visited[start] = true;

    int check;
    while (!alist.empty()) {
        check = alist[0];

        // Print node
        visit(check);
        alist.erase(alist.begin());

        // Every vertex adjacent
        for (int i = 0; i < size; ++i) {
            if (adj[check][i] != 0 && (!visited[i])) {
                // Add node to the queue
                alist.push_back(i);

                // Mark next node as visited
                visited[i] = true;
            }
        }
    }
    // Reset visited as all false
    for (int i = 0; i < size; ++i)
        visited[i] = false;
}


#endif
salem c (3687)
Lacy9265 (119)
I just need help taking my code for adjacent matrix and changing it for an adjacent list. I'm just confused on which way I can do this.
Lacy9265 (119)
I have tried creating variables for my adjacent list class that uses list. However I get multiple errors now that I don't understand how to fix. Here is my code for the adjacent list.

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
 
#include "GraphInterface.h"
#include <string>
#include <fstream>
#include <iostream>
#include <vector>
#include<list>

#ifndef GRAPH_TWO
#define GRAPH_TWO

template<class LabelType>
class GraphTwo : public GraphInterface<LabelType>
{
private:
    // Define maximum number of nodes
    static const int size = 10;
    std::list <int> adj[size][size]= { 0 };
    std::list <bool> visited[size] = { 0 };

public:
    GraphTwo();

    // Get the number of vertices
    int getNumVertices() const;

    // Get the number of the edges
    int getNumEdges() const;


    // Creates an undirected edge in this graph between two vertices
    // that have the given labels.If such vertices do not exist, creates
    // themand adds them to the graph before creating the edge
    bool add(LabelType start, LabelType end, int edgeWeight);


    // Removes an edge from this graph. If a vertex has no other edges,
    // it is removed from the graph since this is a connected graph.
    bool remove(LabelType start, LabelType end);


    // Gets the weight of an edge in this graph.
    int getEdgeWeight(LabelType start, LabelType end) const;


    // Performs a depth - first search of this graph beginning at the given
    // vertex and calls a given function once for each vertex visited.
    void depthFirstTraversal(LabelType start, void visit(LabelType&));


    // Performs a breadth - first search of this graph beginning at the given
    // vertex and calls a given function once for each vertex visited.
    void breadthFirstTraversal(LabelType start, void visit(LabelType&));
};
template<class LabelType>
GraphTwo<LabelType>::GraphTwo()
{}

template<class LabelType>
int GraphTwo<LabelType>::getNumVertices() const
{
    return size;
}

template<class LabelType>
int GraphTwo<LabelType>::getNumEdges() const
{
    int edgeCount = 0;
    for (int i = 0; i < size; ++i)
        for (int j = 0; j < size; ++j)
            if (adj[i][j] != 0)
                ++edgeCount;

    return edgeCount / 2;
}

template<class LabelType>
bool GraphTwo<LabelType>::add(LabelType start, LabelType end, int edgeWeight)
{
    adj[start][end] = edgeWeight;
    adj[end][start] = edgeWeight;
    return true;
}

template<class LabelType>
bool GraphTwo<LabelType>::remove(LabelType start, LabelType end)
{
    adj[start][end] = 0;
    adj[end][start] = 0;
    return true;
}

template<class LabelType>
int GraphTwo<LabelType>::getEdgeWeight(LabelType start, LabelType end) const
{
    return adj[start][end];
}

template<class LabelType>
void GraphTwo<LabelType>::depthFirstTraversal(LabelType start, void visit(LabelType&))
{
    // Visit the current node
    visit(start);

    // Mark the current node as visited
    visited[start] = true;

    // For all other nodes
    for (int i = 0; i < size; ++i) {
        if (adj[start][i] != 0 && (!visited[i]))
            depthFirstTraversal(i, visit);
    }
}

template<class LabelType>
void GraphTwo<LabelType>::breadthFirstTraversal(LabelType start, void visit(LabelType&))
{
    // Vector that contains the adjacent nodes
    std::vector<LabelType> alist;
    alist.push_back(start);

    // Mark current node as visited
    visited[start] = true;

    int check;
    while (!alist.empty()) {
        check = alist[0];

        // Print node
        visit(check);
        alist.erase(alist.begin());

        // Every vertex adjacent
        for (int i = 0; i < size; ++i) {
            if (adj[check][i] != 0 && (!visited[i])) {
                // Add node to the queue
                alist.push_back(i);

                // Mark next node as visited
                visited[i] = true;
            }
        }
    }
    // Reset visited as all false
    for (int i = 0; i < size; ++i)
        visited[i] = false;
}

#endif
Lacy9265 (119)
Errors I get.

L79, L80, L87, L88, L105, L109, L122, and L135: Severity
Error C2679 binary '=': no operator found which takes a right-hand operand of type 'int' (or there is no acceptable conversion)
Last edited on
seeplus (6476)
1
2
 
std::list <int> adj[size][size] = {0};
std::list <bool> visited[size] = {0};


This defines adj as a 2-d array of type std::list. visited as a 1-d array of type std::list. This means that the type of each element in these arrays is std::list.

Is this what you want/mean?

If yes, then you can't initialise elements to 0 as this isn't valid for std::list.

Also L70. As the element type of adj is std::list, you can't test against 0.
L87/88 You set an element to 0 but the type of element is std:list.

If the element type of adj/visited is as you want, then you need to change how you process each element - using std::list functions/defined operators.
Last edited on
Lacy9265 (119)
I'm confused on how I define the variables as a list that would work for my code above. This is my first time with using list. Could someone please help me figure out how I should be doing my list variables and how to implement in the code I have above.
Last edited on
Lacy9265 (119)
Can someone please help me figure out how I would configure the variables on L17 and 18 to use list for an adjacency list for a graph.
Lacy9265 (119)
Can someone please help. This is the last part for the assignment I need to do.
seeplus (6476)
Well this compiles OK. But whether it is what is required for the graph.... It's untested.

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
 
#include <iostream>
#include <string>
#include <vector>

template < class LabelType>
class GraphInterface
{
public:

	/** Gets the number of vertices in this graph.
	@pre   None.
	 @return  The number of vertices in the graph. */
	virtual int getNumVertices() const = 0;

	/** Gets the number of edges in this graph.
	 @pre   None.
	 @return  The number of edges in the graph. */
	virtual int getNumEdges() const = 0;


	/** Creates an undirected edge in this graph between two vertices
	that have the given labels. If such vertices do not exist, creates
	them and adds them to the graph before creating the edge.
	@param start  A label for the first vertex.
	@param end  A label for the second vertex.
	@param edgeWeight  The integer weight of the edge.
   @return  True if the edge is created, or false otherwise. */
	virtual bool add(LabelType start, LabelType end, int edgeWeight) = 0;


	/** Removes an edge from this graph. If a vertex has no other edges,
	it is removed from the graph since this is a connected graph.
	@pre  None.
   @param start  A label for the first vertex.
	@param end  A label for the second vertex.
   @return  True if the edge is removed, or false otherwise. */
	virtual bool remove(LabelType start, LabelType end) = 0;


	/** Gets the weight of an edge in this graph.
	 @return  The weight of the specified edge.
   If no such edge exists, returns a negative integer. */
	virtual int getEdgeWeight(LabelType start, LabelType end) const = 0;


	/** Performs a depth-first search of this graph beginning at the given
  vertex and calls a given function once for each vertex visited.
   @param start  A label for the first vertex.
   @param visit  A client-defined function that performs an operation on
	or with each visited vertex. */
	virtual void depthFirstTraversal(LabelType start, void visit(LabelType&)) = 0;


	/** Performs a breadth-first search of this graph beginning at the given
	 vertex and calls a given function once for each vertex visited.
	 @param start  A label for the first vertex.
	@param visit  A client-defined function that performs an operation on
	  or with each visited vertex. */
	virtual void breadthFirstTraversal(LabelType start, void visit(LabelType&)) = 0;


	/** Destroy this graph and frees assigned memory*/
	virtual ~GraphInterface() { }
}; // end GraphInterface


template<class LabelType>
class GraphTwo : public GraphInterface<LabelType>
{
private:
	// Define maximum number of nodes
	static const int size = 10;
	/*std::list <int>*/ int adj[size][size] = {0};
	/*std::list <bool>*/ int visited[size] = {0};

public:
	GraphTwo();

	// Get the number of vertices
	int getNumVertices() const;

	// Get the number of the edges
	int getNumEdges() const;


	// Creates an undirected edge in this graph between two vertices
	// that have the given labels.If such vertices do not exist, creates
	// themand adds them to the graph before creating the edge
	bool add(LabelType start, LabelType end, int edgeWeight);


	// Removes an edge from this graph. If a vertex has no other edges,
	// it is removed from the graph since this is a connected graph.
	bool remove(LabelType start, LabelType end);


	// Gets the weight of an edge in this graph.
	int getEdgeWeight(LabelType start, LabelType end) const;


	// Performs a depth - first search of this graph beginning at the given
	// vertex and calls a given function once for each vertex visited.
	void depthFirstTraversal(LabelType start, void visit(LabelType&));


	// Performs a breadth - first search of this graph beginning at the given
	// vertex and calls a given function once for each vertex visited.
	void breadthFirstTraversal(LabelType start, void visit(LabelType&));
};
template<class LabelType>
GraphTwo<LabelType>::GraphTwo()
{}

template<class LabelType>
int GraphTwo<LabelType>::getNumVertices() const
{
	return size;
}

template<class LabelType>
int GraphTwo<LabelType>::getNumEdges() const
{
	int edgeCount = 0;
	for (int i = 0; i < size; ++i)
		for (int j = 0; j < size; ++j)
			if (adj[i][j] != 0)
				++edgeCount;

	return edgeCount / 2;
}

template<class LabelType>
bool GraphTwo<LabelType>::add(LabelType start, LabelType end, int edgeWeight)
{
	adj[start][end] = edgeWeight;
	adj[end][start] = edgeWeight;
	return true;
}

template<class LabelType>
bool GraphTwo<LabelType>::remove(LabelType start, LabelType end)
{
	adj[start][end] = 0;
	adj[end][start] = 0;
	return true;
}

template<class LabelType>
int GraphTwo<LabelType>::getEdgeWeight(LabelType start, LabelType end) const
{
	return adj[start][end];
}

template<class LabelType>
void GraphTwo<LabelType>::depthFirstTraversal(LabelType start, void visit(LabelType&))
{
	// Visit the current node
	visit(start);

	// Mark the current node as visited
	visited[start] = true;

	// For all other nodes
	for (int i = 0; i < size; ++i) {
		if (adj[start][i] != 0 && (!visited[i]))
			depthFirstTraversal(i, visit);
	}
}

template<class LabelType>
void GraphTwo<LabelType>::breadthFirstTraversal(LabelType start, void visit(LabelType&))
{
	// Vector that contains the adjacent nodes
	std::vector<LabelType> alist;
	alist.push_back(start);

	// Mark current node as visited
	visited[start] = true;

	int check;
	while (!alist.empty()) {
		check = alist[0];

		// Print node
		visit(check);
		alist.erase(alist.begin());

		// Every vertex adjacent
		for (int i = 0; i < size; ++i) {
			if (adj[check][i] != 0 && (!visited[i])) {
				// Add node to the queue
				alist.push_back(i);

				// Mark next node as visited
				visited[i] = true;
			}
		}
	}
	// Reset visited as all false
	for (int i = 0; i < size; ++i)
		visited[i] = false;
}

int main()
{
	GraphTwo<int> g2;

}

Lacy9265 (119)
@seeplus how is this an adjacency list for a graph. It uses the same type of variables I used for my adjacency matrix.
Last edited on
seeplus (6476)
All i did was to change the code so that it compiled. As I said, I don't know whether this was what was required or not. Your code treats adj and visited as arrays, so I made their type arrays. I know very little now about graphs (haven't touched graphs for over 40 years!) so I can't help with the algorithm. Sorry.
Lacy9265 (119)
So you don't know if the code you written is considered an adjacency list instead of an adjacency matrix.
Topic archived. No new replies allowed.