flann function in opencv is good for point match, which find nearest point from A points to B points, it is useful for tracking, iterative closest point (ICP) algorithm...
I copy the code from this website:
https://github.com/royshil/morethantechnical/blob/master/ICP/MyICP.cpp
and make it simple for me to understand.
code:
#include "cv.h"
#include "highgui.h"
#include <iostream>
#include <vector>
#include <limits>
using namespace cv;
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
Mat X(5,2,CV_32SC1);
X.at<Point>(0,0)=Point(1,1);
X.at<Point>(1,0)=Point(5,5);
X.at<Point>(2,0)=Point(10,10);
X.at<Point>(3,0)=Point(15,15);
X.at<Point>(4,0)=Point(20,20);
Mat destinations(10,2,X.type());
destinations.at<Point>(0,0)=Point(30,30);
destinations.at<Point>(1,0)=Point(6,6);
destinations.at<Point>(2,0)=Point(11,11);
destinations.at<Point>(3,0)=Point(17,17);
destinations.at<Point>(4,0)=Point(23,23);
destinations.at<Point>(5,0)=Point(25,25);
destinations.at<Point>(6,0)=Point(2,2);
destinations.at<Point>(7,0)=Point(16,16);
destinations.at<Point>(8,0)=Point(40,40);
destinations.at<Point>(9,0)=Point(21,21);
cv::Mat m_indices(X.rows, 1, CV_32S);
cv::Mat m_dists(X.rows, 1, CV_32F);
Mat dest_32f; destinations.convertTo(dest_32f,CV_32FC2); //convert
Mat X_32f; X.convertTo(X_32f,CV_32FC2);
cv::flann::Index flann_index(dest_32f, cv::flann::KDTreeIndexParams(2)); // using 2 randomized kdtrees, 1 is ok ,too
flann_index.knnSearch(X_32f, m_indices, m_dists, 1, cv::flann::SearchParams(64) );
cout<<"indice:"<<m_indices<<endl;
cout<<"dist :"<<m_dists<<endl;
for(int i=0;i<5;i++)
{
cout<<i<<" in X match to "<<m_indices.at<int>(i)<<" in destinations"<<endl;
cout<<"distance is : "<<m_dists.at<float>(i)<<endl;
}
system("pause");
}
the output should be:
indice:[6;
1;
2;
7;
9]
dist :[2;
2;
2;
2;
2]
0 in X match to 6 in destinations
distance is : 2
1 in X match to 1 in destinations
distance is : 2
2 in X match to 2 in destinations
distance is : 2
3 in X match to 7 in destinations
distance is : 2
4 in X match to 9 in destinations
distance is : 2
Press any key to continue . . .
2017年6月2日 星期五
2017年2月1日 星期三
simple opencv drawing opengl example
the opencv should be cmaked and check the "WITH_OPENGL"draw 2 sphere and a rotating cube in opencv by opengl using opencv setopengldrawcallback
float gggg=55;
float gginin=3.14/6;
void on_opengl(void* param)
{
//draw a cube
glLoadIdentity();
gluLookAt(20*cos(gginin), 0, 20*sin(gginin), 0.0, 0.0, 0.0, 0.0, 1.0, 0.0);
glTranslated(0.0, 0.0, -1.0);
glDrawArrays(GL_POINTS, 0, 1);
glRotatef( gggg, 1, 0, 0 );
//glRotatef( gggg, 0, 1, 0 );
//glRotatef( gggg, 0, 0, 1 );
static const int coords[6][4][3] = {
{ { +1, -1, -1 }, { -1, -1, -1 }, { -1, +1, -1 }, { +1, +1, -1 } },
{ { +1, +1, -1 }, { -1, +1, -1 }, { -1, +1, +1 }, { +1, +1, +1 } },
{ { +1, -1, +1 }, { +1, -1, -1 }, { +1, +1, -1 }, { +1, +1, +1 } },
{ { -1, -1, -1 }, { -1, -1, +1 }, { -1, +1, +1 }, { -1, +1, -1 } },
{ { +1, -1, +1 }, { -1, -1, +1 }, { -1, -1, -1 }, { +1, -1, -1 } },
{ { -1, -1, +1 }, { +1, -1, +1 }, { +1, +1, +1 }, { -1, +1, +1 } }
};
for (int i = 0; i < 6; ++i) {
glColor3ub( i*20, 100+i*10, i*42 );
glBegin(GL_QUADS);
for (int j = 0; j < 4; ++j) {
glVertex3d(0.2 * coords[i][j][0], 0.2 * coords[i][j][1], 0.2 * coords[i][j][2]);
}
glEnd();
}
//draw a sphere
glLoadIdentity();
gluLookAt(20*cos(gginin), 0, 20*sin(gginin), 0.0, 0.0, 0.0, 0.0, 1.0, 0.0);
glTranslatef(1.0f,2.0f,1.0f);
glColor3ub( 255,0,0);
glBegin(GL_TRIANGLES);
GLUquadricObj *quadric;
quadric = gluNewQuadric();
gluQuadricDrawStyle(quadric, GLU_FILL );
gluSphere( quadric , .1 , 36 , 18 );
glEnd();
//draw another sphere
glLoadIdentity();
gluLookAt(20*cos(gginin), 0, 20*sin(gginin), 0.0, 0.0, 0.0, 0.0, 1.0, 0.0);
glTranslatef(4.1f, 2.45f, 10.0f);
glBegin(GL_TRIANGLES);
GLUquadricObj *quadric2;
quadric2 = gluNewQuadric();
gluQuadricDrawStyle(quadric2, GLU_FILL );
gluSphere( quadric , .6 , 36 , 18 );
glEnd();
glLoadIdentity();
}
int _tmain(int argc, _TCHAR* argv[])
{
string openGLWindowName = "OpenGL Test";
namedWindow(openGLWindowName, WINDOW_OPENGL);
resizeWindow(openGLWindowName, 640, 480);
glMatrixMode( GL_PROJECTION );
glLoadIdentity();
gluPerspective(90.0, 640/480, 1, 1000000.0);
glMatrixMode(GL_MODELVIEW);
setOpenGlContext(openGLWindowName);
setOpenGlDrawCallback(openGLWindowName, on_opengl, NULL);
while(true)
{
updateWindow(openGLWindowName);// when needed
gggg++;
gginin+=3.14/36;
cvWaitKey(30);
cout<<"ggininder"<<endl;
}
return 0;
}
2016年12月30日 星期五
2D tip detection的一點心得
最近工作做human computer interface的東西需要找到端點，一般會把這問題當成2D local maxium的問題，像是影像中的手指或是人體的頭、手等端點，local maxium的方法很多但是網路上能找到的跟所謂要做的tip detection大抵上都是雞同鴨講、鴨同雞講。最近一些方法做一做寫點心得留在後人驗證。
遇到的影像類型大概是這兩種：
1.影像中的極值本身很接近、平緩區域多，通常發生在物體離攝影機靠得很近的狀況，例如手指偵測(通常手指不能離攝影機太遠，會偵測不到)，stackoverflow上面這類問題最多人點讚的一篇做狗的手掌指點的大概也是這問題。
畫成波形圖大概是這種感覺，其中紅色星號是要找的地方
2.影像中極值距離遠、每個極值之間大小有一定差距、通常出現在目標物較遠的影像中。
畫成圖大概像這樣：
這種問題就比較像一般local maxium會討論的問題，在影像上通常目標物夠大，不用很精準的抓到一個特定的點也是能輸出的很好。用一階微分(如laplace filter或canny filter)效果通常不會太差，但是要抓到tip點有時候會有問題。最近在網路上看到一個Local Binary Patterns的方法還行，最近在嘗試。
做法大概是這樣：
1.先選一個點，比較外圍一圈的pixel值，如果大於中間一定的threshold則填1
所以一個圓形的feature可能是000000或1111111，大多數都是0100101這種，我們選擇只有一端開口或沒有開口的0000000、1111111、0111111、0011111這種，開口數可以比較0轉換成1和1轉換成0的次數(記得尾端要跟第一個數字比)，像0110111就是4、0010111也是4，我們選擇2跟0。然後再限制一下開口的0的次數，例如7/4這樣。
最後就會如下圖，紅色是找到的地方，黑色是沒找到的地方，大致上可以把身體濾掉。
詳細的論文請看An adaptive local binary pattern for 3D hand tracking這篇論文
遇到的影像類型大概是這兩種：
1.影像中的極值本身很接近、平緩區域多，通常發生在物體離攝影機靠得很近的狀況，例如手指偵測(通常手指不能離攝影機太遠，會偵測不到)，stackoverflow上面這類問題最多人點讚的一篇做狗的手掌指點的大概也是這問題。
畫成波形圖大概是這種感覺，其中紅色星號是要找的地方
這種近距離的影像找極值會遇到的困難點是什麼，第一、有些地方是平緩的、有些地方不是端點卻有微微凸起，用一階微分來找正負號變換處的話平緩的地方會變消掉、微凸的地方會被標到。當然還有些模擬退火法之類的，但是我在2d的狀況遇到了點問題。
所以後來我就用opencv裡的floodfill做了很簡單的事，先掃過一遍找山頂，用floodfill把山挖掉，接下來就能找下一座山頭了。floodfill中有參數可以調整pixel值最多上升多少或下降多少，善用這功能可以一座一座山挖掉。
假設今天有這樣一隻手
先找到極值
然後用floodfill向下填滿
找下一個極值
再挖掉
再找下一個
再挖掉
最後剩一個
找了極值、挖掉
大概是這樣，有點慢，但是沒啥好方法的話可以考慮。
2.影像中極值距離遠、每個極值之間大小有一定差距、通常出現在目標物較遠的影像中。
畫成圖大概像這樣：
做法大概是這樣：
1.先選一個點，比較外圍一圈的pixel值，如果大於中間一定的threshold則填1
所以一個圓形的feature可能是000000或1111111，大多數都是0100101這種，我們選擇只有一端開口或沒有開口的0000000、1111111、0111111、0011111這種，開口數可以比較0轉換成1和1轉換成0的次數(記得尾端要跟第一個數字比)，像0110111就是4、0010111也是4，我們選擇2跟0。然後再限制一下開口的0的次數，例如7/4這樣。
最後就會如下圖，紅色是找到的地方，黑色是沒找到的地方，大致上可以把身體濾掉。
2016年12月11日 星期日
不懂git bash 打槍槍
寫在這裡防止忘記
裝好git後
準備好repo檔案
https://github.com/esrlabs/git-repo
首先呢要sync東西下來，假設你有一個資料夾在D:/ggininder
git bash中(要開Run as administrator)
先
cd /D/ggininder/
裝好git後
準備好repo檔案
https://github.com/esrlabs/git-repo
首先呢要sync東西下來，假設你有一個資料夾在D:/ggininder
git bash中(要開Run as administrator)
先
cd /D/ggininder/
mkdir ~/bin
curl https://raw.githubusercontent.com/esrlabs/git-repo/stable/repo > ~/bin/repo
curl https://raw.githubusercontent.com/esrlabs/git-repo/stable/repo.cmd > ~/bin/repo.cmd
這時候資料夾裡就有.repo資料夾了，可以開始init跟sync
repo init -u ssh://[gerrit account]@192.168.1.1:5566/biggg_project -g common,all –q
repo sync
2016年9月8日 星期四
看看教育史打槍槍
人生的理想大概無望了，得找下一個目標來作。對於我這種不上不下的人來說呢，搞教育也許是滿足小小金字塔頂端的一種麻痺吧。教師是當不成了，然而這世界上知識業已爆炸，某些領域之間的交流甚至是資訊化程度卻是少得令人發汗，也許可以朝著這方面努力吧。
我一直相信教育有某種萬用解，不管是抽象或具體的，能用一句話解釋的概念便不用兩句來使人明瞭，亦或相反，能用兩句話使人永生難忘，又何妨吝嗇於只肯付出一句話的心力。我想這該稱作教育法或教學法吧。搜索網路，教育法這詞定義分歧。就我手邊看到的資料，不外乎怎麼跟學童玩樂間讓學童肯坐在位置上乖乖聽課，要怎麼用尖銳的聲音使學童聽到媽媽聲音的感覺。學童學童，台灣的初等教育沒那麼不堪，我想考慮的是大人的問題，至少是年長於大學生的對象。
在網路上問了成人教學法的問題，被專業人士薛了一頓，大意上是學童才有可塑性，成人沒救了，聽得懂就聽，聽不懂就放他去死。這顯然與我所追求的萬用解不僅是背道而馳，根本是信仰上的針鋒相對了。
http://www.ryerson.ca/content/dam/lt/resources/handouts/adult-education-methods_handout.pdf
網路上找了一下，中文找成人教育法不外乎失學者的成人教育跟社區大學這種學不學也無所謂的教育體系，用英文找就至少還有一些。內容與我的經驗非常相容，也非常合理，即使我根本沒經驗。
上面連結的這篇還沒看完，但大致上是說成人受教育時非常的目的導向，成人知道--或是他覺得自己知道--自己要什麼，你教的東西必須非常合用於他的生活或工作。適當的與過去經驗結合可以幫助學習，意思是要很多機會給他發表言論多講話。然後增加互動，不論是討論、實驗課或是情境演練。
就像我研究所養蜜蜂的經驗，當實驗者試圖讓蜜蜂飛到一個平常不可能飛到的地方喝糖水就必須一步一步從巢箱洞口開始，先從近的地方放糖水再慢慢把糖水拉遠，而當中最關鍵的訣竅在於必須提供蜜蜂一個可預測的獎勵以及明瞭的目的地。換成成人教育就像是成人要知道學這要幹嘛以及要學到哪些程度。聽起來合情合理，但我想，只少以我的大學就學經驗來說，系上開的本科課程倒是從來沒做到這點，而往後不管是跳船的我還是繼續深造的同學們，事實證明沒有釐清目的的課程對於往後發展即使在相同領域也沒有幫助，特別是生物這種跨了一個走廊的兩間實驗室的分歧與跨了一個系館的分歧差不多的地方。
台大葉丙成教授推展翻轉教室大概也是基於成人教育的理念吧。大學生該作為成人對待了，然而台灣教育這塊卻對成人教育法毫無聞問(從我網路發問被專業人士洗臉可見)，當我研究所跑去多個系館看所謂有用的科系的上課以及教課態度中我看到了希望。而那些力倡不要作為職業訓練所的科系、那些有著「博雅」妄想的學院，不僅在教學上沉淪無力，在學習品質以及成果展現上更是一塌糊塗。人有追求職業價值的本能，一想著畢業後不工作用遺產過一輩子的貴族生活肉體上精神上便會自動關機了。
所以還有很多要實驗的呢，等我解完現階段bug再來考慮考慮。
我一直相信教育有某種萬用解，不管是抽象或具體的，能用一句話解釋的概念便不用兩句來使人明瞭，亦或相反，能用兩句話使人永生難忘，又何妨吝嗇於只肯付出一句話的心力。我想這該稱作教育法或教學法吧。搜索網路，教育法這詞定義分歧。就我手邊看到的資料，不外乎怎麼跟學童玩樂間讓學童肯坐在位置上乖乖聽課，要怎麼用尖銳的聲音使學童聽到媽媽聲音的感覺。學童學童，台灣的初等教育沒那麼不堪，我想考慮的是大人的問題，至少是年長於大學生的對象。
在網路上問了成人教學法的問題，被專業人士薛了一頓，大意上是學童才有可塑性，成人沒救了，聽得懂就聽，聽不懂就放他去死。這顯然與我所追求的萬用解不僅是背道而馳，根本是信仰上的針鋒相對了。
http://www.ryerson.ca/content/dam/lt/resources/handouts/adult-education-methods_handout.pdf
網路上找了一下，中文找成人教育法不外乎失學者的成人教育跟社區大學這種學不學也無所謂的教育體系，用英文找就至少還有一些。內容與我的經驗非常相容，也非常合理，即使我根本沒經驗。
上面連結的這篇還沒看完，但大致上是說成人受教育時非常的目的導向，成人知道--或是他覺得自己知道--自己要什麼，你教的東西必須非常合用於他的生活或工作。適當的與過去經驗結合可以幫助學習，意思是要很多機會給他發表言論多講話。然後增加互動，不論是討論、實驗課或是情境演練。
就像我研究所養蜜蜂的經驗，當實驗者試圖讓蜜蜂飛到一個平常不可能飛到的地方喝糖水就必須一步一步從巢箱洞口開始，先從近的地方放糖水再慢慢把糖水拉遠，而當中最關鍵的訣竅在於必須提供蜜蜂一個可預測的獎勵以及明瞭的目的地。換成成人教育就像是成人要知道學這要幹嘛以及要學到哪些程度。聽起來合情合理，但我想，只少以我的大學就學經驗來說，系上開的本科課程倒是從來沒做到這點，而往後不管是跳船的我還是繼續深造的同學們，事實證明沒有釐清目的的課程對於往後發展即使在相同領域也沒有幫助，特別是生物這種跨了一個走廊的兩間實驗室的分歧與跨了一個系館的分歧差不多的地方。
台大葉丙成教授推展翻轉教室大概也是基於成人教育的理念吧。大學生該作為成人對待了，然而台灣教育這塊卻對成人教育法毫無聞問(從我網路發問被專業人士洗臉可見)，當我研究所跑去多個系館看所謂有用的科系的上課以及教課態度中我看到了希望。而那些力倡不要作為職業訓練所的科系、那些有著「博雅」妄想的學院，不僅在教學上沉淪無力，在學習品質以及成果展現上更是一塌糊塗。人有追求職業價值的本能，一想著畢業後不工作用遺產過一輩子的貴族生活肉體上精神上便會自動關機了。
所以還有很多要實驗的呢，等我解完現階段bug再來考慮考慮。
2016年8月5日 星期五
2016年7月15日 星期五
ggininder
modify from http://www.geeksforgeeks.org/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-representation/
solve the memory leak problem
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include<iostream>
using namespace std;
// A structure to represent a node in adjacency list
struct AdjListNode
{
int dest;
int weight;
struct AdjListNode* next;
};
// A structure to represent an adjacency liat
struct AdjList
{
struct AdjListNode *head; // pointer to head node of list
};
// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
int V;
struct AdjList* array;
};
// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest, int weight)
{
struct AdjListNode* newNode =
(struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->weight = weight;
newNode->next = NULL;
return newNode;
}
// A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
// Create an array of adjacency lists. Size of array will be V
graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
// Initialize each adjacency list as empty by making head as NULL
for (int i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
void delete_graph(Graph* old_graph)
{
// struct AdjListNode* ptr;
for(int i=0;i<old_graph->V;i++)
{
free(old_graph->array[i].head);
}
free (old_graph->array);
free(old_graph);
}
// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest, int weight)
{
// Add an edge from src to dest. A new node is added to the adjacency
// list of src. The node is added at the begining
struct AdjListNode* newNode = newAdjListNode(dest, weight);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
// Since graph is undirected, add an edge from dest to src also
newNode = newAdjListNode(src, weight);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
void delete_all_Edge(struct Graph* graph)
{
for(int i=0;i<graph->V;i++)
{
if(graph->array[i].head==NULL)
{
}
while (graph->array[i].head!=NULL)
{
struct AdjListNode* ptr;
ptr=graph->array[i].head;
ptr->dest=graph->array[i].head->dest;
graph->array[i].head=graph->array[i].head->next;
free(ptr);
}
}
}
void see_all_Edge(struct Graph* graph)
{
//to see if there is any edge between node, just for debugging
struct AdjListNode* ptr;
for(int i=0;i<graph->V;i++)
{
if(graph->array[i].head==NULL)
{
cout<<i<<": nothing here!"<<endl;
}
if(graph->array[i].head!=NULL)
{
ptr=graph->array[i].head;
//ptr->dest=graph->array[i].head->dest;
while (ptr->next!=NULL)
{
cout<<i<<":"<<ptr->dest<<endl;
ptr=ptr->next;
}
cout<<i<<":"<<ptr->dest<<endl;
ptr=ptr->next;
}
}
}
// Structure to represent a min heap node
struct MinHeapNode
{
int v;
int dist;
};
// Structure to represent a min heap
struct MinHeap
{
int size; // Number of heap nodes present currently
int capacity; // Capacity of min heap
int *pos; // This is needed for decreaseKey()
struct MinHeapNode **array;
};
// A utility function to create a new Min Heap Node
struct MinHeapNode* newMinHeapNode(int v, int dist)
{
struct MinHeapNode* minHeapNode =
(struct MinHeapNode*) malloc(sizeof(struct MinHeapNode));
minHeapNode->v = v;
minHeapNode->dist = dist;
return minHeapNode;
}
// A utility function to create a Min Heap
struct MinHeap* createMinHeap(int capacity)
{
struct MinHeap* minHeap =
(struct MinHeap*) malloc(sizeof(struct MinHeap));
minHeap->pos = (int *)malloc(capacity * sizeof(int));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array =
(struct MinHeapNode**) malloc(capacity * sizeof(struct MinHeapNode*));
return minHeap;
}
void delete_minHeap(MinHeap* minHeap)
{
cout<<"size"<<minHeap->capacity<<endl;
free(minHeap->pos);
free(minHeap->array);
free(minHeap);
}
// A utility function to swap two nodes of min heap. Needed for min heapify
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b)
{
struct MinHeapNode* t = *a;
*a = *b;
*b = t;
}
// A standard function to heapify at given idx
// This function also updates position of nodes when they are swapped.
// Position is needed for decreaseKey()
void minHeapify(struct MinHeap* minHeap, int idx)
{
int smallest, left, right;
smallest = idx;
left = 2 * idx + 1;
right = 2 * idx + 2;
if (left < minHeap->size &&
minHeap->array[left]->dist < minHeap->array[smallest]->dist )
smallest = left;
if (right < minHeap->size &&
minHeap->array[right]->dist < minHeap->array[smallest]->dist )
smallest = right;
if (smallest != idx)
{
// The nodes to be swapped in min heap
MinHeapNode *smallestNode = minHeap->array[smallest];
MinHeapNode *idxNode = minHeap->array[idx];
// Swap positions
minHeap->pos[smallestNode->v] = idx;
minHeap->pos[idxNode->v] = smallest;
// Swap nodes
swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
minHeapify(minHeap, smallest);
}
}
// A utility function to check if the given minHeap is ampty or not
int isEmpty(struct MinHeap* minHeap)
{
return minHeap->size == 0;
}
// Standard function to extract minimum node from heap
struct MinHeapNode* extractMin(struct MinHeap* minHeap)
{
if (isEmpty(minHeap))
return NULL;
// Store the root node
struct MinHeapNode* root = minHeap->array[0];
// Replace root node with last node
struct MinHeapNode* lastNode = minHeap->array[minHeap->size - 1];
minHeap->array[0] = lastNode;
// Update position of last node
minHeap->pos[root->v] = minHeap->size-1;
minHeap->pos[lastNode->v] = 0;
// Reduce heap size and heapify root
--minHeap->size;
minHeapify(minHeap, 0);
return root;
}
// Function to decreasy dist value of a given vertex v. This function
// uses pos[] of min heap to get the current index of node in min heap
void decreaseKey(struct MinHeap* minHeap, int v, int dist)
{
// Get the index of v in heap array
int i = minHeap->pos[v];
// Get the node and update its dist value
minHeap->array[i]->dist = dist;
// Travel up while the complete tree is not hepified.
// This is a O(Logn) loop
while (i && minHeap->array[i]->dist < minHeap->array[(i - 1) / 2]->dist)
{
// Swap this node with its parent
minHeap->pos[minHeap->array[i]->v] = (i-1)/2;
minHeap->pos[minHeap->array[(i-1)/2]->v] = i;
swapMinHeapNode(&minHeap->array[i], &minHeap->array[(i - 1) / 2]);
// move to parent index
i = (i - 1) / 2;
}
}
// A utility function to check if a given vertex
// 'v' is in min heap or not
bool isInMinHeap(struct MinHeap *minHeap, int v)
{
if (minHeap->pos[v] < minHeap->size)
return true;
return false;
}
// A utility function used to print the solution
void printArr(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < n; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}
void showminheap(struct MinHeap* minHeap)
{
int V=minHeap->size;
for(int i=0;i<V;i++)
{
cout<<minHeap->pos[i]<<"this!!"<<endl;
cout<<minHeap->array[i]->v<<"this v!!"<<endl;
}
}
// The main function that calulates distances of shortest paths from src to all
// vertices. It is a O(ELogV) function
void dijkstra(struct Graph* graph, int src)
{
int V = graph->V;// Get the number of vertices in graph
int* dist=new int[V]; // dist values used to pick minimum weight edge in cut
// minHeap represents set E
struct MinHeap* minHeap = createMinHeap(V);
// Initialize min heap with all vertices. dist value of all vertices
for (int v = 0; v < V; ++v)
{
dist[v] = INT_MAX;
minHeap->array[v] = newMinHeapNode(v, dist[v]);
minHeap->pos[v] = v;
}
// Make dist value of src vertex as 0 so that it is extracted first
dist[src] = 0;
decreaseKey(minHeap, src, dist[src]);
// Initially size of min heap is equal to V
minHeap->size = V;
// In the followin loop, min heap contains all nodes
// whose shortest distance is not yet finalized.
while (!isEmpty(minHeap))
{
// Extract the vertex with minimum distance value
struct MinHeapNode* minHeapNode = extractMin(minHeap);
int u = minHeapNode->v; // Store the extracted vertex number
// Traverse through all adjacent vertices of u (the extracted
// vertex) and update their distance values
struct AdjListNode* pCrawl = graph->array[u].head;
while (pCrawl != NULL)
{
int v = pCrawl->dest;
// If shortest distance to v is not finalized yet, and distance to v
// through u is less than its previously calculated distance
if (isInMinHeap(minHeap, v) && dist[u] != INT_MAX &&
pCrawl->weight + dist[u] < dist[v])
{
dist[v] = dist[u] + pCrawl->weight;
// update distance value in min heap also
decreaseKey(minHeap, v, dist[v]);
}
pCrawl = pCrawl->next;
}
free(pCrawl);
free(minHeapNode);
}
delete_minHeap(minHeap);
// print the calculated shortest distances
printArr(dist, V);
delete dist;
}
// Driver program to test above functions
int main()
{
// create the graph given in above fugure
int V = 9;
struct Graph* graph = createGraph(V);
while(true)
{
addEdge(graph, 0, 1, 4);
addEdge(graph, 0, 7, 8);
addEdge(graph, 1, 2, 8);
addEdge(graph, 1, 7, 11);
addEdge(graph, 2, 3, 7);
addEdge(graph, 2, 8, 2);
addEdge(graph, 2, 5, 4);
addEdge(graph, 3, 4, 9);
addEdge(graph, 3, 5, 14);
addEdge(graph, 4, 5, 10);
addEdge(graph, 5, 6, 2);
addEdge(graph, 6, 7, 1);
addEdge(graph, 6, 8, 6);
addEdge(graph, 7, 8, 7);
dijkstra(graph, 0);
delete_all_Edge(graph);
}
return 0;
}
solve the memory leak problem
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include<iostream>
using namespace std;
// A structure to represent a node in adjacency list
struct AdjListNode
{
int dest;
int weight;
struct AdjListNode* next;
};
// A structure to represent an adjacency liat
struct AdjList
{
struct AdjListNode *head; // pointer to head node of list
};
// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
int V;
struct AdjList* array;
};
// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest, int weight)
{
struct AdjListNode* newNode =
(struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->weight = weight;
newNode->next = NULL;
return newNode;
}
// A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
// Create an array of adjacency lists. Size of array will be V
graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
// Initialize each adjacency list as empty by making head as NULL
for (int i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
void delete_graph(Graph* old_graph)
{
// struct AdjListNode* ptr;
for(int i=0;i<old_graph->V;i++)
{
free(old_graph->array[i].head);
}
free (old_graph->array);
free(old_graph);
}
// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest, int weight)
{
// Add an edge from src to dest. A new node is added to the adjacency
// list of src. The node is added at the begining
struct AdjListNode* newNode = newAdjListNode(dest, weight);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
// Since graph is undirected, add an edge from dest to src also
newNode = newAdjListNode(src, weight);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
void delete_all_Edge(struct Graph* graph)
{
for(int i=0;i<graph->V;i++)
{
if(graph->array[i].head==NULL)
{
}
while (graph->array[i].head!=NULL)
{
struct AdjListNode* ptr;
ptr=graph->array[i].head;
ptr->dest=graph->array[i].head->dest;
graph->array[i].head=graph->array[i].head->next;
free(ptr);
}
}
}
void see_all_Edge(struct Graph* graph)
{
//to see if there is any edge between node, just for debugging
struct AdjListNode* ptr;
for(int i=0;i<graph->V;i++)
{
if(graph->array[i].head==NULL)
{
cout<<i<<": nothing here!"<<endl;
}
if(graph->array[i].head!=NULL)
{
ptr=graph->array[i].head;
//ptr->dest=graph->array[i].head->dest;
while (ptr->next!=NULL)
{
cout<<i<<":"<<ptr->dest<<endl;
ptr=ptr->next;
}
cout<<i<<":"<<ptr->dest<<endl;
ptr=ptr->next;
}
}
}
// Structure to represent a min heap node
struct MinHeapNode
{
int v;
int dist;
};
// Structure to represent a min heap
struct MinHeap
{
int size; // Number of heap nodes present currently
int capacity; // Capacity of min heap
int *pos; // This is needed for decreaseKey()
struct MinHeapNode **array;
};
// A utility function to create a new Min Heap Node
struct MinHeapNode* newMinHeapNode(int v, int dist)
{
struct MinHeapNode* minHeapNode =
(struct MinHeapNode*) malloc(sizeof(struct MinHeapNode));
minHeapNode->v = v;
minHeapNode->dist = dist;
return minHeapNode;
}
// A utility function to create a Min Heap
struct MinHeap* createMinHeap(int capacity)
{
struct MinHeap* minHeap =
(struct MinHeap*) malloc(sizeof(struct MinHeap));
minHeap->pos = (int *)malloc(capacity * sizeof(int));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array =
(struct MinHeapNode**) malloc(capacity * sizeof(struct MinHeapNode*));
return minHeap;
}
void delete_minHeap(MinHeap* minHeap)
{
cout<<"size"<<minHeap->capacity<<endl;
free(minHeap->pos);
free(minHeap->array);
free(minHeap);
}
// A utility function to swap two nodes of min heap. Needed for min heapify
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b)
{
struct MinHeapNode* t = *a;
*a = *b;
*b = t;
}
// A standard function to heapify at given idx
// This function also updates position of nodes when they are swapped.
// Position is needed for decreaseKey()
void minHeapify(struct MinHeap* minHeap, int idx)
{
int smallest, left, right;
smallest = idx;
left = 2 * idx + 1;
right = 2 * idx + 2;
if (left < minHeap->size &&
minHeap->array[left]->dist < minHeap->array[smallest]->dist )
smallest = left;
if (right < minHeap->size &&
minHeap->array[right]->dist < minHeap->array[smallest]->dist )
smallest = right;
if (smallest != idx)
{
// The nodes to be swapped in min heap
MinHeapNode *smallestNode = minHeap->array[smallest];
MinHeapNode *idxNode = minHeap->array[idx];
// Swap positions
minHeap->pos[smallestNode->v] = idx;
minHeap->pos[idxNode->v] = smallest;
// Swap nodes
swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
minHeapify(minHeap, smallest);
}
}
// A utility function to check if the given minHeap is ampty or not
int isEmpty(struct MinHeap* minHeap)
{
return minHeap->size == 0;
}
// Standard function to extract minimum node from heap
struct MinHeapNode* extractMin(struct MinHeap* minHeap)
{
if (isEmpty(minHeap))
return NULL;
// Store the root node
struct MinHeapNode* root = minHeap->array[0];
// Replace root node with last node
struct MinHeapNode* lastNode = minHeap->array[minHeap->size - 1];
minHeap->array[0] = lastNode;
// Update position of last node
minHeap->pos[root->v] = minHeap->size-1;
minHeap->pos[lastNode->v] = 0;
// Reduce heap size and heapify root
--minHeap->size;
minHeapify(minHeap, 0);
return root;
}
// Function to decreasy dist value of a given vertex v. This function
// uses pos[] of min heap to get the current index of node in min heap
void decreaseKey(struct MinHeap* minHeap, int v, int dist)
{
// Get the index of v in heap array
int i = minHeap->pos[v];
// Get the node and update its dist value
minHeap->array[i]->dist = dist;
// Travel up while the complete tree is not hepified.
// This is a O(Logn) loop
while (i && minHeap->array[i]->dist < minHeap->array[(i - 1) / 2]->dist)
{
// Swap this node with its parent
minHeap->pos[minHeap->array[i]->v] = (i-1)/2;
minHeap->pos[minHeap->array[(i-1)/2]->v] = i;
swapMinHeapNode(&minHeap->array[i], &minHeap->array[(i - 1) / 2]);
// move to parent index
i = (i - 1) / 2;
}
}
// A utility function to check if a given vertex
// 'v' is in min heap or not
bool isInMinHeap(struct MinHeap *minHeap, int v)
{
if (minHeap->pos[v] < minHeap->size)
return true;
return false;
}
// A utility function used to print the solution
void printArr(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < n; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}
void showminheap(struct MinHeap* minHeap)
{
int V=minHeap->size;
for(int i=0;i<V;i++)
{
cout<<minHeap->pos[i]<<"this!!"<<endl;
cout<<minHeap->array[i]->v<<"this v!!"<<endl;
}
}
// The main function that calulates distances of shortest paths from src to all
// vertices. It is a O(ELogV) function
void dijkstra(struct Graph* graph, int src)
{
int V = graph->V;// Get the number of vertices in graph
int* dist=new int[V]; // dist values used to pick minimum weight edge in cut
// minHeap represents set E
struct MinHeap* minHeap = createMinHeap(V);
// Initialize min heap with all vertices. dist value of all vertices
for (int v = 0; v < V; ++v)
{
dist[v] = INT_MAX;
minHeap->array[v] = newMinHeapNode(v, dist[v]);
minHeap->pos[v] = v;
}
// Make dist value of src vertex as 0 so that it is extracted first
dist[src] = 0;
decreaseKey(minHeap, src, dist[src]);
// Initially size of min heap is equal to V
minHeap->size = V;
// In the followin loop, min heap contains all nodes
// whose shortest distance is not yet finalized.
while (!isEmpty(minHeap))
{
// Extract the vertex with minimum distance value
struct MinHeapNode* minHeapNode = extractMin(minHeap);
int u = minHeapNode->v; // Store the extracted vertex number
// Traverse through all adjacent vertices of u (the extracted
// vertex) and update their distance values
struct AdjListNode* pCrawl = graph->array[u].head;
while (pCrawl != NULL)
{
int v = pCrawl->dest;
// If shortest distance to v is not finalized yet, and distance to v
// through u is less than its previously calculated distance
if (isInMinHeap(minHeap, v) && dist[u] != INT_MAX &&
pCrawl->weight + dist[u] < dist[v])
{
dist[v] = dist[u] + pCrawl->weight;
// update distance value in min heap also
decreaseKey(minHeap, v, dist[v]);
}
pCrawl = pCrawl->next;
}
free(pCrawl);
free(minHeapNode);
}
delete_minHeap(minHeap);
// print the calculated shortest distances
printArr(dist, V);
delete dist;
}
// Driver program to test above functions
int main()
{
// create the graph given in above fugure
int V = 9;
struct Graph* graph = createGraph(V);
while(true)
{
addEdge(graph, 0, 1, 4);
addEdge(graph, 0, 7, 8);
addEdge(graph, 1, 2, 8);
addEdge(graph, 1, 7, 11);
addEdge(graph, 2, 3, 7);
addEdge(graph, 2, 8, 2);
addEdge(graph, 2, 5, 4);
addEdge(graph, 3, 4, 9);
addEdge(graph, 3, 5, 14);
addEdge(graph, 4, 5, 10);
addEdge(graph, 5, 6, 2);
addEdge(graph, 6, 7, 1);
addEdge(graph, 6, 8, 6);
addEdge(graph, 7, 8, 7);
dijkstra(graph, 0);
delete_all_Edge(graph);
}
return 0;
}
訂閱：
文章 (Atom)