A quick guide to setting up and installing OpenCV for using in the Netbeans integrated development environment in Linux.
Step 1: Download and extract OpenCV for Linux
Versions of OpenCV can be downloaded from here:
http://opencv.org/downloads.html
Save it to the location of your choice. Open a command prompt, navigate to the download location and unzip:
Breadth First Search
From WikiPedia:
“Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes first, before moving to the next level neighbors”
I have borrowed heavily the C++ code listing used at the ‘Geeks for geeks’ website and made a few modifications of my own, such as using smart pointers. I have also produced C# equivalents of the code. For reference the website is here:
http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/
Full C++/C# code listings:
[tabs]
[tab title=”C++”]
#include <iostream>
#include <list>
#include <memory>
class Graph
{
int _V;
bool _directed;
std::unique_ptr< std::list<int> > adj;
public:
Graph(int V, bool directed);
void AddEdge(int v, int w);
void BreadthFirstSearch(int s);
};
Graph::Graph(int V, bool directed) : adj(new std::list<int>[V])
{
_V = V;
_directed = directed;
}
void Graph::AddEdge(int v, int w)
{
std::list<int>* adjacency = adj.get();
adjacency[v].push_back(w);
if (!_directed)
{
adjacency[w].push_back(v);
}
}
void Graph::BreadthFirstSearch(int s)
{
bool *visited = new bool[_V];
for(int i = 0; i < _V; i++)
visited[i] = false;
// Create a queue for BFS
std::list<int> queue;
visited[s] = true;
queue.push_back(s);
// 'i' will be used to get all adjacent vertices of a vertex
std::list<int>::iterator i;
while(!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
std::cout << s << " ";
queue.pop_front();
// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it visited
// and enqueue it
for(i = (adj.get())[s].begin(); i != (adj.get())[s].end(); ++i)
{
if(!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
}
int main()
{
Graph g(7, true);
g.AddEdge(0, 1);
g.AddEdge(0, 2);
g.AddEdge(0, 3);
g.AddEdge(1, 0);
g.AddEdge(1, 5);
g.AddEdge(2, 5);
g.AddEdge(3, 0);
g.AddEdge(3, 4);
g.AddEdge(4, 6);
g.AddEdge(5, 1);
g.AddEdge(6, 5);
std::cout << "Breadth First Traversal from vertex 2:\n";
g.BreadthFirstSearch(2);
return 0;
}
[/tab]
[tab title=”C#”]
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DFS
{
class Graph
{
private int _V;
private bool _directed;
LinkedList<int>[] _adj;
public Graph(int V, bool directed)
{
_adj = new LinkedList<int>[V];
for (int i = 0; i < _adj.Length; i++)
{
_adj[i] = new LinkedList<int>();
}
_V = V;
_directed = directed;
}
public void AddEdge(int v, int w)
{
_adj[v].AddLast(w);
if (!_directed)
{
_adj[w].AddLast(v);
}
}
public void BreadthFirstSearch(int s)
{
bool[] visited = new bool[_V];
for(int i = 0; i < _V; i++)
visited[i] = false;
// Create a queue for BFS
LinkedList<int> queue = new LinkedList<int>();
visited[s] = true;
queue.AddLast(s);
while(queue.Any())
{
// Dequeue a vertex from queue and print it
s = queue.First();
Console.Write( s + " " );
queue.RemoveFirst();
LinkedList<int> list = _adj[s];
foreach (var val in list)
{
if (!visited[val])
{
visited[val] = true;
queue.AddLast(val);
}
}
}
}
}
class Program
{
static void Main(string[] args)
{
Graph g = new Graph(7, true);
g.AddEdge(0, 1);
g.AddEdge(0, 2);
g.AddEdge(0, 3);
g.AddEdge(1, 0);
g.AddEdge(1, 5);
g.AddEdge(2, 5);
g.AddEdge(3, 0);
g.AddEdge(3, 4);
g.AddEdge(4, 6);
g.AddEdge(5, 1);
g.AddEdge(6, 5);
Console.Write("Breadth First Traversal from vertex 2:\n");
g.BreadthFirstSearch(2);
}
}
}
[/tab]
[/tabs]
Consider the following 6-node directed graph, as created using calls to the AddEdge function shown in the above code:
Running the breadth-first search to traverse the graph gives the following output, showing the graph nodes discovered by the graph traversal:
Depth First Search
From Wikipedia:
“Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.”
Again I’ve modified the version of the Depth First Search algorithm from the ‘Geeks for Geeks’ site and done some modifications, including replacing normal pointers with smart pointers, and allowing the graphs to be directed or undirected:
[tabs]
[tab title=”C++”]
#include <iostream>
#include <list>
#include <memory>
class Graph
{
private:
int _V;
bool _directed;
std::unique_ptr< std::list<int> > adj;
void DFSUtil(int v, bool visited[]);
public:
Graph(int V, bool directed);
void AddEdge(int v, int w);
void DepthFirstSearch(int s);
};
Graph::Graph(int V, bool directed) : adj(new std::list<int>[V])
{
_V = V;
_directed = directed;
}
void Graph::AddEdge(int v, int w)
{
std::list<int>* adjacency = adj.get();
adjacency[v].push_back(w);
if (!_directed)
{
adjacency[w].push_back(v);
}
}
void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
std::cout << v << " ";
// Recur for all the vertices adjacent to this vertex
std::list<int>::iterator i;
for (i = (adj.get())[v].begin(); i != (adj.get())[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
// DFS traversal of the vertices reachable from v. It uses recursive DFSUtil()
void Graph::DepthFirstSearch(int v)
{
// Mark all the vertices as not visited
std::unique_ptr<bool[]> visited(new bool[_V]);
for (int i = 0; i < _V; i++)
visited[i] = false;
// Call the recursive helper function to print DFS traversal
DFSUtil(v, visited.get());
}
int main()
{
// Create a graph given in the above diagram
Graph g(7, true);
g.AddEdge(0, 1);
g.AddEdge(0, 2);
g.AddEdge(0, 3);
g.AddEdge(1, 0);
g.AddEdge(1, 5);
g.AddEdge(2, 5);
g.AddEdge(3, 0);
g.AddEdge(3, 4);
g.AddEdge(4, 6);
g.AddEdge(5, 1);
g.AddEdge(6, 5);
std::cout << "Depth First Traversal starting from vertex 2:\n";
g.DepthFirstSearch(2);
return 0;
}
[/tab]
[tab title=”C#”]
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DFS
{
class Graph
{
private int _V;
private bool _directed;
LinkedList<int>[] _adj;
public Graph(int V, bool directed)
{
_adj = new LinkedList<int>[V];
for (int i = 0; i < _adj.Length; i++)
{
_adj[i] = new LinkedList<int>();
}
_V = V;
_directed = directed;
}
public void AddEdge(int v, int w)
{
_adj[v].AddLast(w);
if (!_directed)
{
_adj[w].AddLast(v);
}
}
public void DepthFirstSearch(int v)
{
// Mark all the vertices as not visited
bool[] visited = new bool[_V];
for (int i = 0; i < _V; i++)
visited[i] = false;
// Call the recursive helper function to print DFS traversal
DFSUtil(v, visited);
}
private void DFSUtil(int v, bool []visited)
{
// Mark the current node as visited and print it
visited[v] = true;
Console.Write( v + " " );
// Recur for all the vertices adjacent to this vertex
LinkedList<int> list = _adj[v];
foreach (var val in list)
{
if (!visited[val])
DFSUtil(val, visited);
}
}
}
class Program
{
static void Main(string[] args)
{
Graph g = new Graph(7, true);
g.AddEdge(0, 1);
g.AddEdge(0, 2);
g.AddEdge(0, 3);
g.AddEdge(1, 0);
g.AddEdge(1, 5);
g.AddEdge(2, 5);
g.AddEdge(3, 0);
g.AddEdge(3, 4);
g.AddEdge(4, 6);
g.AddEdge(5, 1);
g.AddEdge(6, 5);
Console.Write("Depth First Traversal from vertex 2:\n");
g.DepthFirstSearch(2);
}
}
}
[/tab]
[/tabs]
Output of the depth-first search traversal as shown:
A Hamiltonian path in a graph is a path whereby each node is visited exactly once.
A number of graph-related problems require determining if the interconnections between its edges and vertices form a proper Hamiltonian tour, such as traveling salesperson type problems. Such a problem is NP-Complete, that is, the effort required to solve the problem increases dramatically as the size of the problem grows.
This C++ implementation borrows heavily from the ideas and algorithms used in the following article:
http://www.geeksforgeeks.org/backtracking-set-7-hamiltonian-cycle/
(more…)
An example demonstrating how to create and display a tab common control using WinAPI (Win32) C++ programming.
Much credit needs to go to Ken Fitlike’s excellent WinAPI site, from which I orginally learned how to do stuff like this. I don’t think the site has been updated for a number of years but it contains a ton of useful material on showing you how to create various things using the WinAPI.
All that is required to create a Tabbed Dialog is some small modifications to the Simple Window example: the WndProc function handles WM_CREATE and WM_SIZE messages in addition to WM_DESTROY:
LRESULT CALLBACK WndProc(HWND hwnd,UINT uMsg,WPARAM wParam,LPARAM lParam)
{
switch (uMsg)
{
case WM_CREATE:
{
return OnCreate(hwnd,reinterpret_cast<CREATESTRUCT*>(lParam));
}
case WM_DESTROY:
{
OnDestroy(hwnd);
return 0;
}
case WM_SIZE:
{
OnSize(hwnd,LOWORD(lParam),HIWORD(lParam),static_cast<UINT>(wParam));
return 0;
}
default:
return DefWindowProc(hwnd,uMsg,wParam,lParam);
}
}
Note: for configuring FLTK in Linux environments, please refer to this post.
1. Download and extract FLTK
For this particular install I used an old Visual Studio 2003 .NET version. Get the zipped file from the download section of Bill Spitzak’s FLTK site. Unzip the file and place it somewhere suitable such as C:\fltk-1.1.10-source. (more…)