vertex_index_map(identity_property_map()).
distance_map(vertex_distances));
}
-
+
+static int distances[N][N];
+
+void graph_layout_prepare() {
+ Graph g;
+ int v1, v2;
+
+ FOR_VERTEX(v1) {
+ int *d= distances[v1];
+ FOR_VERTEX(v2) d[v2]= -1;
+ d[v1]= 0;
+ breadth_first_search
+ (g, v1,
+ vertex_index_map(identity_property_map()).
+ visitor(make_bfs_visitor(record_distances(d,on_tree_edge()))));
+ printf("%02x:",v1);
+ FOR_VERTEX(v2) printf(" %02x:%d",v2,d[v2]);
+ putchar('\n');
+ }
+ printf("---\n");
+ FOR_VERTEX(v1) {
+ int *d= distances[v1];
+ printf("%02x:",v1);
+ FOR_VERTEX(v2) printf(" %02x:%d",v2,d[v2]);
+ putchar('\n');
+ }
+}
+
double graph_layout_cost(const Vertices v, const double vertex_areas[N]) {
/* For each (vi,vj) computes shortest path s_ij = |vi..vj|
* along edges, and actual distance d_ij = |vi-vj|.
* divisions, to avoid division by zero.)
*/
static const double d2_epsilon= 1e-6;
-
- double edge_weights[V6<<ESHIFT], vertex_distances[N], total_cost=0;
- int v1,v2,e,f;
- FOR_VERTEX(v1)
- FOR_VEDGE_X(v1,e,v2,
- f= v1 | e << ESHIFT,
- edge_weights[f]= NAN)
- edge_weights[f]= hypotD(v[v1], v[v2]);
+ // double edge_weights[V6<<ESHIFT], vertex_distances[N],
+ double total_cost=0;
+ int v1,v2,e, nedges=0;
+ double totaledgelength=0, meanedgelength;
+
+ FOR_EDGE(v1,e,v2) {
+ totaledgelength += hypotD(v[v1], v[v2]);
+ nedges++;
+ }
+ meanedgelength= totaledgelength / nedges;
+
FOR_VERTEX(v1) {
- //double a1= vertex_areas[v1];
- single_source_shortest_paths(v1, edge_weights, vertex_distances);
FOR_VERTEX(v2) {
if (v1 == v2) continue;
- //double a2= vertex_areas[v2];
- double d2= hypotD2plus(v[v1],v[v2], d2_epsilon);
- double s= vertex_distances[v2];
- double s2= s*s + d2_epsilon;
- double sd2= s2 / d2;
+
+ double d= hypotD(v[v1],v[v2]);
+
+ int dist= distances[v1][v2];
+ assert(dist>=0);
+
+ double s= dist * meanedgelength * 0.03;
+
+ double enoughdistance= d - s;
+ if (enoughdistance > 1e-6) continue;
+
+ /* energy = 1/2 stiffness deviation^2
+ * where stiffness = 1/d
+ */
+
+ double cost= pow(enoughdistance,4);
+
+ //double s2= s*s + d2_epsilon;
+ //double sd2= s2 / d2;
//double cost_contrib= a1*a2 * (sd2 - 1) / (d2*d2);
- double cost_contrib= sd2;
- //if (cost_contrib < -1e-4) {
- // printf("layout %03x..%03x (a=%g,%g) s=%g s2=%g d2=%g sd2=%g"
- // " cost+=%g\n", v1,v2, a1,a2, s,s2,d2,sd2, cost_contrib);
- // abort();
- // }
- total_cost += cost_contrib;
+ //double cost_contrib= sd2;
+
+ printf("layout %03x..%03x dist=%d mean=%g s=%g d=%g enough=%g"
+ " cost+=%g\n", v1,v2, dist, meanedgelength,
+ s,d, enoughdistance, cost);
+ total_cost += cost;
}
}
return total_cost;