problem with node priority queue

Thread View: comp.lang.c++.leda

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by Matthew David Scruggs Wed, 16 Aug 1995 14:08

#42

Author: Matthew David Scruggs
Date: Wed, 16 Aug 1995 14:08

38 lines
1439 bytes

I have code similar to the following(everything's declared, etc):

int foo(graph &G, node_array<double> cost, node_array<node) pred ...)
{

node_pq<double> Q(G);
forall_nodes(n,G) Q.insert(n,cost[n]);

while(!Q.empty()){
  n = Q.del_min();
  if(n){
    forall_adj_nodes(n1,n){
	if(Q.member(n1){
	  cout << index(n1) << " ";
   	  pred[n1] = n;
          ....other stuff.....
	}
    }
  }
}
}

if I pass this function a graph with nodes {a, b, c, d}
where cost[a]<cost[b]<...<cost[d], the a is the minimum
on the first pass, and should be deleted from the node
priority queue Q.  However, "a" shows up as a member of
Q on the next pass (and causes a bus error). "a" is 
assigned to "n" on the first pass.  

Any ideas why?  Any fixes?

Dave  (using LEDA 3.1.2)
--
-----------------------------------------------------------------------
		   Georgia Institute of Technology
      School of Electrical Engineering, Atlanta, GA  30332-0250
		    E-MAIL: scruggs@eecom.gatech.edu
			PHONE: (404) 894-2955

Re: problem with node priority queue

#44

Author: Matthew David Scruggs
Date: Wed, 16 Aug 1995 16:41

12 lines
856 bytes

Apparently, the "Q.member(n)" call always returns true, despite
"n" not being contained in the queue "Q".  The size of Q decrements
consistently.

Dave
--
-----------------------------------------------------------------------
		   Georgia Institute of Technology
      School of Electrical Engineering, Atlanta, GA  30332-0250
		    E-MAIL: scruggs@eecom.gatech.edu
			PHONE: (404) 894-2955

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads