Monthly Archives: November 2006
Implementing Dijkstra using (Fibonacci) Heap
Dijkstra Alogrithm:
Input: Graph G, vertices S (start), T (terminate) Declare: H (initially empty heap) 1: For all vertices v 2: if v == S then v.cost := 0 3: else v.cost := infinity 3: Insert v into H 4: Repeat 5: M := ExtractMin(H) 6: For each vertex A attached to M 7: w := cost of edge from M to A 8: if (M.cost + w < A.cost) 9: DecreaseKey(A,M.cost + w) 10: A.backlink := M 11: Until M = T 12: Output T.cost 13: Output vertices on chain of backlinks from T to S
Dijkstra’s algorithm sets the cost of each vertex (except the starting vertex) to infinity and puts all the vertices onto a heap. You then extract the cheapest vertex from the heap — call it M — and examine each vertex A adjacent to M. If the cost of M plus the cost of the edge joining M to A is cheaper than the current cost of A (that is, if there’s a cheap path to A through M), you create a link from A to M and decrease A’s key to represent the new cost. You continue extracting successive nodes until you reach T, the target vertex. The value of T is the cost of the shortest path. The links from T back to the starting vertex indicate the shortest path.
As you can see in Figure 1, the DecreaseKey() on line 9 is the most time-consuming operation of the inner loop. Since Dijkstra’s algorithm is important in network routing and other applications, it would be nice to find a heap implementation that makes this operation as fast as possible. This is the primary motivation for the Fibonacci heap.
—- By John Boyer
Running Time: (http://en.wikipedia.org/wiki/Dijkstra’s_algorithm)
The simplest implementation of the Dijkstra’s algorithm stores vertices of set Q in an ordinary linked list or array, and operation Extract-Min(Q) is simply a linear search through all vertices in Q. In this case, the running time is O(V^2).
For sparse graphs, that is, graphs with much less than V^2 edges, Dijkstra’s algorithm can be implemented more efficiently by storing the graph in form of adjaceny lists and using a binary heap or Fibonacci heap as a priority queue to implement the Extract-Min function. With a binary heap, the algorithm requires O((E+V)logV) time, and the Fibonacci heap improves this to O(E+VlogV).
Sparse matrix solver
Add popup menu for right click
IDR_MENU1 MENU
BEGIN
POPUP ""
BEGIN
MENUITEM "Poisson Image Editing", ID_DSTVIEW_POISSON
MENUITEM "Drag and Drop Pasting", ID_DSTVIEW_DDPASTING
END
END
void CDstView::OnContextMenu(CWnd* /*pWnd*/, CPoint point)
{
CMenu popupmenu;
popupmenu.LoadMenu(IDR_MENU1);
CMenu* popup=popupmenu.GetSubMenu(0);
popup->TrackPopupMenu(TPM_LEFTALIGN,point.x,point.y,this);}
google黑板报
Double buffer drawing
// declare memory dcCDC MemDC;
CBitmap MemBitmap;// create bitmap object so that there is some space for the memory dc to draw
MemDC.CreateCompatibleDC(pDC/*NULL*/);
MemBitmap.CreateCompatibleBitmap(pDC,nWidth,nHeight);
CBitmap *pOldBit=MemDC.SelectObject(&MemBitmap);// erase the background of the bitmap object,// if so, you don’t need to re-define the OnEraseBkg(), I think
MemDC.FillSolidRect(0,0,nWidth,nHeight,RGB(255,255,255));// drawing
…// copy data from memory to screen
pDC->BitBlt(0,0,nWidth,nHeight,&MemDC,0,0,SRCCOPY);// delete memory dc
MemBitmap.DeleteObject();
MemDC.DeleteDC();
在画曲线时用MouseMove()时会把一些点丢掉,可能是没有来的及响应吧。这时我用Bresenham把相邻两个点Rasterize了一下。可以search了一下 LineBresenham,就可以找到相应的code。
Using 2 views for a single document
BOOL CPhotograph2App::OnDstTemplate()
{
pDstTemplate = new CMultiDocTemplate(IDR_Photograph2TYPE,
RUNTIME_CLASS(CPhotograph2Doc),
RUNTIME_CLASS(CChildFrame), // custom MDI child frame
RUNTIME_CLASS(CDstView));
if (!pDstTemplate)
return FALSE;AddDocTemplate(pDstTemplate);
ASSERT_VALID(pDstTemplate);
return TRUE;
}
// CMainFrame message handlers
BOOL CMainFrame::OnDstWindow()
{
CMDIChildWnd* pActiveChild = MDIGetActive();
CDocument* pDocument;
if (pActiveChild == NULL ||
(pDocument = pActiveChild->GetActiveDocument()) == NULL) {
TRACE0("Warning: No active document for WindowNew command.\n");
AfxMessageBox(AFX_IDP_COMMAND_FAILURE);
return FALSE; // command failed
}
CPhotograph2App* pApp = (CPhotograph2App*)AfxGetApp();
ASSERT_POINTER(pApp, CPhotograph2App);
//CDocTemplate* pTemplate = pDocument->GetDocTemplate();CMultiDocTemplate* pDstTemplate = pApp->GetDstTemplate();
ASSERT_VALID(pDstTemplate);
CFrameWnd* pFrame = pDstTemplate->CreateNewFrame(pDocument, pActiveChild);
if (pFrame == NULL) {
TRACE0("Warning: failed to create new frame.\n");
return FALSE; // command failed
}
pDstTemplate->InitialUpdateFrame(pFrame, pDocument);}
Usage of CScrollView
void CSrcView::OnInitialUpdate()
{
CScrollView::OnInitialUpdate();
CPhotograph2Doc* pDoc = GetDocument();CSize sizeTotal;
// TODO: calculate the total size of this view
sizeTotal.cx = pDoc->pSrcImg->Width();
sizeTotal.cy = pDoc->pSrcImg->Height();SetScrollSizes(MM_TEXT, sizeTotal);
}
// some drawingSetScrollSizes(MM_TEXT, CSize(pDoc->pSrcImg->Width(), pDoc->pSrcImg->Height()));
CChildFrame *pParentFrame = (CChildFrame *)this->GetParentFrame();
pParentFrame->RecalcLayout();
// ResizeParentToFit();
BOOL CSrcView::OnEraseBkgnd(CDC* pDC)
{
// Set brush to desired background color
CBrush backBrush(RGB(255, 255, 255));
// Save old brush
CBrush* pOldBrush = pDC->SelectObject(&backBrush);
CRect rect;
pDC->GetClipBox(&rect); // Erase the area needed
pDC->PatBlt(rect.left, rect.top, rect.Width(), rect.Height(),
PATCOPY);
pDC->SelectObject(pOldBrush);
return TRUE;//return CScrollView::OnEraseBkgnd(pDC);}