next up previous contents index
Next: Graph Generators ( graph_gen Up: Graphs and Related Data Previous: Node Priority Queues (   Contents   Index


Bounded Node Priority Queues ( b_node_pq )

Definition

An instance of the data type b_node_pq<N> is a priority queue of nodes with integer priorities with the restriction that the size of the minimal interval containing all priorities in the queue is bounded by N , the sequence of the priorities of the results of calls of the method del_min is monotone increasing, and every node is contained in at most one queue. When applied to the empty queue the del_min - operation returns a special default minimum node defined in the constructor of the queue.

#include < LEDA/graph/b_node_pq.h >

Creation

b_node_pq< N> PQ introduces a variable PQ of type b_node_pq<N> and initializes it with the empty queue with default minimum node nil .

b_node_pq< N> PQ(node v) introduces a variable PQ of type b_node_pq<N> and initializes it with the empty queue with default minimum node v .

Operations

node PQ.del_min() removes the node with minimal priority from PQ and returns it (the default minimum node if PQ is empty).

void PQ.insert(node w, int p) adds node w with priority p to PQ.

void PQ.del(node w, int=0) deletes node w from PQ.

Implementation

Bounded node priority queues are implemented by cyclic arrays of doubly linked node lists.

Example

Using a b$ \_$node$ \_$pq in Dijktra's shortest paths algorithm.

int dijkstra(const GRAPH<int,int>& g, node s, node t) 
{ node_array<int> dist(g,MAXINT);
  b_node_pq<100> PQ(t);  // on empty queue del_min returns t 
  dist[s] = 0;

  for (node v = s;  v != t; v = PQ.del_min() )
  { int dv = dist[v];
    edge e;
    forall_adj_edges(e,v) 
    { node w = g.opposite(v,e);
      int d = dv + g.inf(e);
      if (d < dist[w])
      { if (dist[w] != MAXINT) PQ.del(w);
        dist[w] = d;
        PQ.insert(w,d);
       }
     }
   }
  return dist[t];
}


next up previous contents index
Next: Graph Generators ( graph_gen Up: Graphs and Related Data Previous: Node Priority Queues (   Contents   Index
Christian Uhrig 2017-04-07