+void Vertex::del_leaving_edge(Edge *e) {
+ if(e == leaving_edge_list_root) {
+ leaving_edge_list_root = e->next_leaving_edge;
+ }
+ if(e->pred_leaving_edge) {
+ e->pred_leaving_edge->next_leaving_edge = e->next_leaving_edge;
+ }
+ if(e->next_leaving_edge) {
+ e->next_leaving_edge->pred_leaving_edge = e->pred_leaving_edge;
+ }
+}
+
+void Vertex::decrease_distance_in_heap(Vertex **heap) {
+ Vertex **p, **h;
+ // There is some beauty in that
+ h = heap_slot;
+ while(h > heap &&
+ (p = heap + (h - heap + 1) / 2 - 1,
+ (*p)->distance_from_source > (*h)->distance_from_source)) {
+ swap(*p, *h);
+ swap((*p)->heap_slot, (*h)->heap_slot);
+ h = p;
+ }
+}
+
+void Vertex::increase_distance_in_heap(Vertex **heap, Vertex **heap_bottom) {
+ Vertex **c1, **c2, **h;
+ // omg, that's beautiful
+ h = heap_slot;
+ while(c1 = heap + 2 * (h - heap) + 1,
+ c1 < heap_bottom &&
+ (c2 = c1 + 1,
+ (*c1)->distance_from_source < (*h)->distance_from_source
+ ||
+ (c2 < heap_bottom && (*c2)->distance_from_source < (*h)->distance_from_source)
+ )) {
+ if(c2 < heap_bottom && (*c2)->distance_from_source <= (*c1)->distance_from_source) {
+ swap(*c2, *h);
+ swap((*c2)->heap_slot, (*h)->heap_slot);
+ h = c2;
+ } else {
+ swap(*c1, *h);
+ swap((*c1)->heap_slot, (*h)->heap_slot);
+ h = c1;
+ }
+ }
+}
+
+//////////////////////////////////////////////////////////////////////
+
+static int compare_vertices_on_distance(const void *v1, const void *v2) {
+ scalar_t delta =
+ (*((Vertex **) v1))->distance_from_source -
+ (*((Vertex **) v2))->distance_from_source;
+ if(delta < 0) return -1;
+ else if(delta > 0) return 1;
+ else return 0;