*/
/*
- * We use BGL's implementation of Johnson All Pairs Shortest Paths
+ * We use BGL's implementation of Dijkstra's single source shortest
+ * paths. We really want all pairs shortest paths, so Johnson All
+ * Pairs Shortest Paths would seem sensible. But actually Johnson's
+ * algorithm is just a wrapper around Dijkstra's; the extra
+ * functionality is just to deal with -ve edge weights, which we don't
+ * have. So we can use Dijkstra directly and save some cpu (and some
+ * code: we don't have to supply all of the machinery needed for
+ * Johnson's invocation of Bellman-Ford). The overall time cost is
+ * O(VE log V); I think the space used is O(E).
*/
#define VMASK (YMASK|XMASK)
#define ESHIFT (YBITS|XBITS)
-/* When we enumerate the edges we mainly just increment f.
- * To avoid nonexistent edges
- * we start with e=0 | y=1 | x=0
- * and explicitly skip e=1 | y=0 | ...
- * We go only up to e=2 | YMAX | XMAX
- * ie we stop just before e=3 | y=0 | x=0
- * so that we get each edge once rather than twice.
- */
-
-#define F_ALL_MIN (1 << YSHIFT)
-#define F_ALL_MAX (3 << ESHIFT)
-#define F_ALL_SKIP_AT (1 << ESHIFT)
-#define F_ALL_SKIP_SET (1 << YSHIFT)
-
namespace boost {
// We make Layout a model of various BGL Graph concepts.
// This mainly means that graph_traits<Layout> has lots of stuff.
OutEdgeIncrable& operator++() { f += 1<<ESHIFT; return self; }
OutEdgeIncrable(int v, int e) : f(v | (e << ESHIFT)) { }
};
- struct AnyEdgeIncrable {
- int f;
- AnyEdgeIncrable& operator++() {
- f++;
- if (f == F_ALL_SKIP_AT) f |= F_ALL_SKIP_SET
- return self;
- }
- AnyEdgeIncrable(int _f) : f(_f) { }
- AnyEdgeIncrable() : f(F_ALL_MIN) { }
- };
struct graph_traits<Layout> {
}
inline unsigned num_vertices(const Layout&) { return N; }
- // Concept EdgeListGraph:
- typedef counting_iterator<AnyEdgeIncrable,
- forward_iterator_tag> edge_iterator;
- typedef unsigned edges_size_type;
- inline std::pair<edge_iterator,edge_iterator>
- edges(const Layout&) {
- return std::make_pair(edge_iterator(AnyEdgeIncrable()),
- edge_iterator(AnyEdgeIncrable(F_ALL_MAX)));
- }
- unsigned num_edges(const Layout&) {
- return F_ALL_MAX - F_ALL_MIN - ((F_SKIP_SET|F_SKIP_AT) - F_SKIP_AT);
- }
-
}
-void calculate_layout_energy(const Layout*) {
+struct VertexIndexMap;
+
+namespace boost {
+ struct property_traits<VertexIndexMap> {
+ // Concept Readable Property Map:
+ typedef int value_type, reference, key_type;
+ category
+class Boost
+ }};
+
+void single_source_shortest_paths(int v1,
+ const double edge_weights[/*f*/],
+ ) {
+ boost::dijkstra_shortest_paths
+ (g, v1,
+ weight_map(edge_weights).
+ vertex_index_map(identity_property_map()).
+
+
+void all_pairs_shortest_paths(const Layout *g) {
FOR_VERTEX(v1) {
- boost::dijkstra_shortest_paths(g, v1, 0);
+
+ 0);
/* weight_map(). ? */
- /* vertex_index_map(vimap). */
+ /*
predecessor_map().