Jeremy Siek wrote:
> ghost> vector< vertex > alternative_s ;
> ghost> iterator_property_map< vector<vertex>::iterator,
> ghost> property_map<G, vertex_index_t> > alternative = ...
> ghost>
> ghost> The problem is that I have to pass alternative_s.begin() when
> ghost> constructig alternative, but I might want to add new vertices.
> ghost> In that case the iterator can be invalidated.
> ghost>
> ghost> Is there a solution to this problem, except for resorting to internal
> ghost> properties?
We currenly do not have a solution for this in the BGL (other than
internal properties). I seem to remember LEDA having a solution for this,
so you might want to look there for ideas.
Jeremy,
I've sketched some solution which works for me. It's merely a property map,
which uses vector for storage and will resize that vector as needed. I attach
the file. Can you take a look and say if you find the approach reasonable.
I might add it to the property map library in that case.
- Volodya
#line 396 "k_shortest.w"
// Copyright (C) 2003 Vladimir Prus
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/graph/dag_shortest_paths.hpp>
#include "vector_property_map.hpp"
#include <iostream>
namespace boost {
#line 142 "k_shortest.w"
template<class G>
class Shortest_paths_finder {
public:
#line 384 "k_shortest.w"
typedef typename graph_traits<G>::vertex_descriptor vertex;
typedef typename graph_traits<G>::edge_descriptor edge;
typedef typename graph_traits<G>::vertex_iterator vertex_iterator;
typedef typename graph_traits<G>::in_edge_iterator in_edge_iterator;
typedef typename graph_traits<G>::out_edge_iterator out_edge_iterator;
#line 146 "k_shortest.w"
#line 293 "k_shortest.w"
template<class PredecessorMap>
struct best_incoming_edge_recorder
: public base_visitor< best_incoming_edge_recorder<PredecessorMap> >
{
typedef on_edge_relaxed event_filter;
best_incoming_edge_recorder(PredecessorMap pm)
: pm(pm)
{}
template<class Edge, class Graph>
void operator()(Edge e, const Graph& g) const {
put(pm, target(e, g), e);
}
PredecessorMap pm;
};
#line 148 "k_shortest.w"
Shortest_paths_finder(const G& g, vertex source, vertex sink)
: g(g), m_source(source), m_sink(sink)
{
best_incoming_edge_recorder< vector_property_map<edge, index_map> > rec(best_incoming);
dag_shortest_paths(this->g, source,
predecessor_map(predecessor).distance_map(distance)
.visitor(make_dijkstra_visitor(rec))
);
vertex_iterator vi, ve;
for (tie(vi, ve) = vertices(g); vi != ve; ++vi) {
alternative[*vi] = *vi;
root[*vi] = *vi;
}
}
#line 253 "k_shortest.w"
bool find_alternative()
{
bool result = find_alternative(m_sink);
m_sink = alternative[m_sink];
cout << "new sink = " << m_sink << "\n";
return result;
}
bool find_alternative(vertex v)
{
// Make sure alternative to 'vertex' is not computed yet.
assert(alternative[v] == v);
if (in_degree(root[v], g) == 0)
return false;
vertex pred = best_predecessor(v);
// If the alternative is not computed, try to compute it now
// The condition also handles the case where alternative does not
// exists, in which case we better avoid recursive call... but anyway.
cout << "at " << v << " pred = " << pred << "\n";
// If there's alternative to the best predecessor, or we can compute it
if (alternative[pred] != pred || find_alternative(pred)) {
cout << "chaning best predecessor to " << alternative[pred] << "\n";
change_best_predecessor(add_alternative(v), alternative[pred]);
} else if (in_degree(root[v], g) > 1) {
cout << "removing best predecessor\n";
remove_best_predecessor(add_alternative(v));
} else {
return false;
}
return true;
}
#line 167 "k_shortest.w"
#line 330 "k_shortest.w"
template<class OutputIterator>
void shortest_path(OutputIterator result) const
{
vector<vertex> path;
for(vertex v = m_sink;; v = predecessor[v]) {
path.push_back(root[v]);
if (predecessor[v] == v)
break;
}
copy(path.rbegin(), path.rend(), result);
}
#line 169 "k_shortest.w"
private:
G g;
vertex m_source;
vertex m_sink;
#line 188 "k_shortest.w"
typedef property_map<G, vertex_index_t>::type index_map;
vector_property_map<vertex, index_map> predecessor;
vector_property_map<edge, index_map> best_incoming;
vector_property_map<int, index_map> distance;
vector_property_map<vertex, index_map> alternative, root;
// Creates an alternative to v. Updates 'alternative' and 'root'
// maps, but does nothing about predecessor and distance.
vertex add_alternative(vertex v);
vertex best_predecessor(vertex v)
{
assert(predecessor[v] == source(best_incoming[v], g));
return predecessor[v];
}
void change_best_predecessor(vertex v, vertex n)
{
int weight = get(edge_weight, g, best_incoming[v]);
remove_edge(best_incoming[v], g);
edge e = add_edge(n, root[v], g).first;
put(edge_weight, g, e, weight);
adjust(v);
}
void remove_best_predecessor(vertex v)
{
remove_edge(best_predecessor(v), root[v], g);
adjust(v);
}
void adjust(vertex v)
{
vertex r = root[v];
typename graph_traits<G>::in_edge_iterator ii, ie;
tie(ii, ie) = in_edges(r, g);
if (ii == ie)
return;
distance[v] = distance[source(*ii, g)] + get(edge_weight, g, *ii);
predecessor[v] = source(*ii, g);
best_incoming[v] = *ii;
while(++ii != ie) {
int nd = distance[source(*ii, g)] + get(edge_weight, g, *ii);
if (nd < distance[v]) {
distance[v] = nd;
predecessor[v] = source(*ii, g);
best_incoming[v] = *ii;
}
}
cout << "best predecessor of " << v << "(root " << root[v] << ") is "
<< predecessor[v] << "\n";
}
#line 176 "k_shortest.w"
};
#line 409 "k_shortest.w"
#line 311 "k_shortest.w"
template<class G>
Shortest_paths_finder<G>::vertex
Shortest_paths_finder<G>::add_alternative(vertex v)
{
// Create the alternative vertex
typename graph_traits<G>::vertex_descriptor alt = add_vertex(g);
alternative[alt] = alt;
alternative[v] = alt;
root[alt] = root[v];
// We duplicate all prec-related data now
predecessor[alt] = predecessor[v];
best_incoming[alt] = best_incoming[v];
distance[alt] = distance[v];
return alt;
}
#line 411 "k_shortest.w"
#line 348 "k_shortest.w"
template<class G>
void k_shortest(const G& g, int k)
{
#line 384 "k_shortest.w"
typedef typename graph_traits<G>::vertex_descriptor vertex;
typedef typename graph_traits<G>::edge_descriptor edge;
typedef typename graph_traits<G>::vertex_iterator vertex_iterator;
typedef typename graph_traits<G>::in_edge_iterator in_edge_iterator;
typedef typename graph_traits<G>::out_edge_iterator out_edge_iterator;
#line 352 "k_shortest.w"
#line 377 "k_shortest.w"
function_requires< BidirectionalGraphConcept<G> >() ;
function_requires< ReadablePropertyGraphConcept<G, edge, edge_weight_t> >();
#line 353 "k_shortest.w"
if (num_vertices(g) == 0)
return;
Shortest_paths_finder<G> f(g, *vertices(g).first, *prior(vertices(g).second));
do {
vector<vertex> p;
f.shortest_path(back_inserter(p));
cout << "---------__";
for (size_t i = 0; i < p.size(); ++i)
cout << p[i] << " ";
cout << "\n";
for (size_t i = 0; i < p.size(); ++i)
cout << p[i]+1 << " ";
cout << "\n";
} while(f.find_alternative());
}
#line 413 "k_shortest.w"
}
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
