chiark
/
gitweb
/
~ian
/
moebius2.git
/ commitdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
| commitdiff |
tree
raw
|
patch
|
inline
| side by side (parent:
7467995
)
wip; justify choice of Dijkstra
author
Ian Jackson
<ian@davenant.relativity.greenend.org.uk>
Sat, 29 Dec 2007 15:47:56 +0000
(15:47 +0000)
committer
Ian Jackson
<ian@davenant.relativity.greenend.org.uk>
Sat, 29 Dec 2007 15:47:56 +0000
(15:47 +0000)
bgl.cpp
patch
|
blob
|
history
diff --git
a/bgl.cpp
b/bgl.cpp
index cdfd8580e25dea55cc113745f967e70ea5e38764..774be825a1cc53bc017884e94876ddd49c134984 100644
(file)
--- a/
bgl.cpp
+++ b/
bgl.cpp
@@
-13,26
+13,20
@@
extern "C" {
*/
/*
*/
/*
- * 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)
*/
#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.
namespace boost {
// We make Layout a model of various BGL Graph concepts.
// This mainly means that graph_traits<Layout> has lots of stuff.
@@
-49,16
+43,6
@@
namespace boost {
OutEdgeIncrable& operator++() { f += 1<<ESHIFT; return self; }
OutEdgeIncrable(int v, int e) : f(v | (e << ESHIFT)) { }
};
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> {
struct graph_traits<Layout> {
@@
-95,28
+79,35
@@
namespace boost {
}
inline unsigned num_vertices(const Layout&) { return N; }
}
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) {
FOR_VERTEX(v1) {
- boost::dijkstra_shortest_paths(g, v1, 0);
+
+ 0);
/* weight_map(). ? */
/* weight_map(). ? */
- /*
vertex_index_map(vimap). */
+ /*
predecessor_map().
predecessor_map().