craig said:
void Graph::addEdge( Vertex &v1, Vertex &v2, int weight )
{
ind = "compute index of Vertex in vertex list"
Edge *e = new Edge (v1, v2, weight );
list <Edge*> lst; <- how to make dynamic ??
adjLists.push_back (lst); <-how to make dynamic??
adjLists[ind].push_back( e );
}
The list is already dynamic, the push_back will add to the end. The
vector is slightly different though. I think you missed the suggestion
of the resize() somewhere.
What you need is (I'm not g'teeing it will compile directly) is
something like:
vector< list< boost::shared_ptr< Edge > > >::size_type ind = /* Your
calc */;
if ( adjLists.size() < ind + 1 ) // Remember it is zero indexed
adjLists.resize( ind + 1 );
adjLists[ ind ].push_back( boost::shared_ptr< Edge >( new Edge( v1, v2,
weight ) ) );
Why shared_ptrs here? They behave like real pointers but obfuscate the
code, create a dependency to Boost, add the overhead of one
dynamically allocated counter for each Edge object (e.g. 1000 Edges
means 1000 superfluous dynamic allocations), ...
The usual way is to let the destructor do the cleanup.
Things to note:
* The if statement checks to see that the vector is big enough _before_
you access the index.
* The use of the smart pointer. Don't get in the habit of using raw
pointers.
On the contrary. Get the habit to avoid "smart" pointers!!
* The use of the type vector<>::size_type for the index. Your compiler
vendor has gone to a lot of trouble making sure you won't have any
unexpected overflows etc. when they chose this type. Use it rather than
make your own guess about what is right.
* The vector is zero indexed so index 1 means it must be at least size
2
The code may now look like this:
void Graph::addEdge( Vertex &v1, Vertex &v2, int weight )
{
ind = "compute index of Vertex in vertex list"
Edge *e = new Edge (v1, v2, weight );
if (! (ind < adjLists.size()))
{
adjLists.resize(ind + 1);
}
// push_back dynamically grows the list
adjLists[ind].push_back( e );
}
// destructor
Graph::~Graph()
{
for (vector<list<Edge*> >::size_tye ind = 0;
ind < adjLists.size(); ++ind)
{
for (list<Edge*>::iterator it = adjLists[ind].begin();
it != adjLists[ind].end(); ++it)
{
delete *it;
}
}
}