I'm creating a graph from vertices and edges read in from a file. The vertices and edges are stored in a hash-table structure, where the vetices are stored in an array, and each vertex points to a linked list of edges. Currently, everything works great. However, i need to make the array of vertices dynamic (i don't know how many vertices will be in the file). So, every time a vertex is read in from the file, a new position in the array is made for that vertex. So, I've heard vectors are used to make dynamic arrays. However, i'm running into some trouble with them (first time i've used vectors), and i need some help. Here is what my working program looks like:
Code:
struct edge
{
int source;
int target;
string label;
edge *nextEdge;
};
struct vertex
{
int id;
string label;
string color;
int distance;
edge *next;
};
int EndChain(edge *¤tEdge);
int InsertEdge(edge *currentEdge, vertex *array1[], int tempSource, int tempTarget, string tempLabel2, string firstChar);
int InsertVertex(vertex *array1[], int tempId, string tempLabel);
//table size must me 1 more than the number of vertices.
#define tableSize 100
int main(int argc, char* argv[])
{
ifstream inFile ( argv[1] );
if ( !inFile.is_open() )
{
cout << "Could not open file." << endl;
}
else
{
string firstChar;
vertex *array1[tableSize] = {NULL};
edge *currentEdge;
currentEdge = NULL;
//Temp variables for vertex.
int tempId;
string tempLabel;
//Temp variables for edge.
int tempSource;
int tempTarget;
string tempLabel2;
while(!inFile.eof())
{
inFile >> firstChar;
//If the first character is %, ignore the rest of the line.
if(firstChar == "%")
{
inFile.ignore(10000, '\n');
}
//If the first character is a v, create a vertex.
else if(firstChar == "v")
{
inFile >> tempId >> tempLabel;
InsertVertex(array1, tempId, tempLabel);
}
//Create a directed edge.
else if(firstChar == "d")
{
inFile >> tempSource >> tempTarget >> tempLabel2;
InsertEdge(currentEdge, array1, tempSource, tempTarget, tempLabel2, firstChar);
}
//Create an undirected edge.
else if(firstChar == "u")
{
inFile >> tempSource >> tempTarget >> tempLabel2;
InsertEdge(currentEdge, array1, tempSource, tempTarget, tempLabel2, firstChar);
InsertEdge(currentEdge, array1, tempTarget, tempSource, tempLabel2, firstChar);
}
else
{
}
}
}
cout << endl;
cin.get();
return 0;
}
//Go to the end of edge chain to insert.
int EndChain(edge *¤tEdge)
{
while(currentEdge->nextEdge != NULL)
{
currentEdge = currentEdge->nextEdge;
}
return 0;
}
int InsertEdge(edge *currentEdge, vertex *array1[], int tempSource, int tempTarget, string tempLabel2, string firstChar)
{
//If no edge exists for current vertex.
if(array1[tempSource]->next == NULL)
{
array1[tempSource]->next = new edge;
currentEdge = array1[tempSource]->next;
currentEdge->source = tempSource;
currentEdge->target = tempTarget;
currentEdge->label = tempLabel2;
currentEdge->nextEdge = NULL;
}
//If an edge already exists for current vertex.
else
{
currentEdge = array1[tempSource]->next;
//Go to end of chain of edges to insert new edge.
EndChain(currentEdge);
currentEdge->nextEdge = new edge;
currentEdge = currentEdge->nextEdge;
currentEdge->source = tempSource;
currentEdge->target = tempTarget;
currentEdge->label = tempLabel2;
currentEdge->nextEdge = NULL;
}
return 0;
}
int InsertVertex(vertex *array1[], int tempId, string tempLabel)
{
array1[tempId] = new vertex;
array1[tempId]->id = tempId;
array1[tempId]->label = tempLabel;
array1[tempId]->next = NULL;
return 0;
So, i thought i just needed to declare a vector, and switch everything that is an array to the vector. I started out by declaring a vector like:
Code:
vector<vertex> *vertexArray;
Then i replaced all my function calls with array1 to vertexArray. Then i went to access the members of vertex, but i couldn't figure out how to do it.
Code:
array1[tempId]->id = 5;
vertexArray[tempId]->... ???
I couldn't access the members of vertex with the vector like i did for the array. I was looking at some examples about vectors, but none of them used structs.
Anyways, i'm looking for the simplest way to convert this program into using a dynamic array, where a new position in the array is created every time a new vertex is read in from the file. If this can be done in an easier way than using a vector, i'm open to suggestions. However, a vector is the only way i've heard that can do this. I also have breadth-first, depth-first, and topological sort functions that are all based on a fixed size array. So, the easiest way to covert this program into a dynamic array, the better.
Any help would be appreciated.
PS: I'm sure i'll have some more questions about using vectors for my program, so i'll keep posting on this thread.