Context Navigation

Changeset 167:7949a29a334e in lemon-0.x for src/work

Timestamp:

03/11/04 13:55:50 (21 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@238

Message:

* empty log message *

Location:

src/work/jacint

Files:

-                      r160
+                      r167
   double pre_time=currTime();
     Dijkstra<ListGraph, int> dijkstra_test(G, s, cap);
+    dijkstra_test.run();
   double post_time=currTime();
   std::cout << "running time: " << post_time-pre_time << " sec"<< std::endl;
+  int hiba=0;
   EachEdgeIt e;
   for ( G.getFirst(e) ; G.valid(e); G.next(e) ) {
     NodeIt u=G.tail(e);
     NodeIt v=G.head(e);
+    assert ( dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap.get(e) );
+    if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap.get(e) ) {
+      std::cout<<"Hiba: "<<dijkstra_test.dist(v) - dijkstra_test.dist(u) - cap.get(e)<<std::endl;
+      ++hiba;
+    }
+  }
+  std::cout << "Hibas elek szama: " << hiba << " a " << G.edgeNum() <<"-bol."<< std::endl;
   return 0;

r160	r167
3	3	*template <Graph, T, Heap=FibHeap>
4	4	*
5		*
6	5	*Constructor:
7	6	*
8	7	*Dijkstra(Graph G, NodeIt s, Graph::EdgeMap<T> length)
9		*
10	8	*
11	9	*
…	…
16	14	* The following function should be used after run() was already run.
17	15	*
18		*
19	16	*T dist(NodeIt v) : returns the distance from s to v.
20	17	* It is 0 if v is not reachable from s.
21		*
22	18	*
23	19	*EdgeIt pred(NodeIt v) : returns the last edge
24	20	* of a shortest s-v path. Returns an invalid iterator
25	21	* if v=s or v is not reachable from s.
26		*
27	22	*
28	23	*bool reach(NodeIt v) : true iff v is reachable from s
…	…
77	72	NodeIt v=heap.top();
78	73	T oldvalue=heap.get(v);
	74	heap.pop();
79	75	distance.set(v, oldvalue);
80		heap.pop();
81
	76
82	77	OutEdgeIt e;
83	78	for( G.getFirst(e,v); G.valid(e); G.next(e)) {
…	…
89	84	heap.push(w,oldvalue+length.get(e));
90	85	predecessor.set(w,e);
91
92	86	} else if ( oldvalue+length.get(e) < heap.get(w) ) {
93	87	predecessor.set(w,e);
…	…
115	109	return reached.get(v);
116	110	}
117
	111
118	112	};
119
	113
120	114	}
121	115

Note: See TracChangeset for help on using the changeset viewer.