I'm one piece of the algorithm away from finishing an assignment, but for the life of me I cannot figure out how to implement this pseudo code line.
A weighted graph is being defined by a text file. In the text file, the top line is the number of vertices, and the rest of the lines are 3 numbers defining edges: vertex 1, vertex 2, and cost (parameters for each edge).
class Graph
{
struct Edge
{
int dest; // destination vertex number
int cost; // edge weight
Edge *next;
};
struct Vertex
{
Edge *adj;
bool known;
int dist;
int path;
};
vector<Vertex *> vertices;
vector<int> PQ;
int PQsize;
void PQinsert (int v);
int PQdeleteMin ();
public:
Graph () { PQsize=0; }
int numVertices () { return vertices.size(); }
int dist (int dest) { return vertices[dest]->dist; }
void readFile (char *name);
void dijkstra (int start);
void printPath (int dest);
I need to be able to determine and cycle through all vertices adjacent to a starting vertex.
I imagine that would involve determining how many edges are associated with the starting vertex and going through each vertex on the other end of the edge, but I cannot for the life of me figure out how to determine and cycle through all edges connected to a vertex when each Vertex only has a single Edge parameter. This would be easy if he had implemented an adjacency list for each vertex, cycling through such a list would be easy, but he chose not to.
> the top line is the number of edges, and the rest of the lines are (...) (parameters for each edge).
¿so why your example input has 13 lines instead of 8?
> This would be easy if he had implemented an adjacency list for each vertex
maybe that's exactly what's doing.
I don't realize another meaning for `next' edge, and `vertex::adj' edge.
I'm afraid I don't follow. Maybe I'm interpreting wrong, but
Edge *adj; seems to define a pointer to one adjacent edge. I don't see a list being created here. If I'm wrong, maybe you could explain why/how it would create a list w/ that declaration?
as for std::{forward_,}list, I probably would if we were allowed to change anything but the dijkstra method, which he has specifically forbidden
class node_list{
public:
node_list *next;
};
class list{
public:
node_list *head;
};
int main(){
list l;
l.head = NULL; //empty list
l.head = new node_list; //inserting one element
l.head->next = new node_list; //another element
l.head->next->next = new node_list; //yet another element
l.head->next->next->next = NULL;
}
replace list with Vertex, and node_list with Edge.
It may be using another representation, ¿so why don't you go and ask instead of playing a guessing game?