Archive for the ‘C++’ category

install igraph (C) on Linux(ubuntu) and use it in Eclipse

November 30th, 2011

Build and install igraph.

      download the source code package;
      unpack it into a directory, eg. igraph-0.5.4 (I’ll use IGRAPH_DIR instead below)
      enter the directory: user> cd IGRAPH_DIR
          user> make
          user> sudo make install This will install the igraph libary files into /usr/local/lib

Add igraph libraries to the shared libraries search path

If you haven’t include /usr/local/lib into your shared libraries search path as defined in /etc/ld.so.conf, add it. Otherwise, you will see an error like this: error while loading shared libraries: libigraph.so.0: cannot open shared object file: No such file or directory.

And DON’T forget to reload the config:user> sudo ldconfig

Use igraph in Eclipse

      Go to Project -> Properties-> C/C++ Build -> Settings
      Go to GCC C++ Compiler -> Directories, add /usr/loccal/include/igraph.
      Go to GCC C++ Linker -> Libraries, add “igraph” to Libraries (-l) and add “/usr/loca/lib” to Library search path (-L).

An example of Boost Betweenness Centrality

November 28th, 2011

Here is an example of using Boost to calculate Betweenness Centrality for a graph. The example is original from: http://programmingexamples.net/index.php?title=CPP/Boost/BGL/BetweennessCentralityClustering.

But now the page is down, so I cache it here:

BetweennessCentralityClustering.cpp

/*
 * In the included example, the max centrality of the graph is 14. So specifying
 * the required input argument 14 gives the "first" decomposition of the graph.
 * That is, removal of one edge (with the maximal edge centrality). Specifying a value
 * greater than 14 yields no decomposition.
 */
 
#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
 
// For clustering
#include <boost/graph/bc_clustering.hpp>
#include <boost/graph/iteration_macros.hpp>
 
 
// Graph edge properties (bundled properties)
struct EdgeProperties
{
  int weight;
};
 
typedef boost::adjacency_list< boost::setS, boost::vecS, boost::undirectedS, boost::no_property, EdgeProperties > Graph;
typedef Graph::vertex_descriptor Vertex;
typedef Graph::edge_descriptor Edge;
 
void WriteGraph(const Graph& g, const std::string& filename);
 
int main(int argc, char** argv)
{
  // Verify arguments
  if( argc != 2 )
  {
    std::cerr << "USAGE: " << argv[0] << " <Max centrality>" << std::endl;
    return -1;
  }
 
  // Convert the input argument to a double
  std::stringstream ss;
  ss << argv[1];
  double max_centrality;
  ss >> max_centrality;
 
  // Create a star graph
  Graph g;
 
  // Central vertex
  Vertex centerVertex = boost::add_vertex(g);
 
  // Surrounding vertices
  Vertex v;
  v = boost::add_vertex(g);
  boost::add_edge(centerVertex, v, g);
  v = boost::add_vertex(g);
  boost::add_edge(centerVertex, v, g);
  v = boost::add_vertex(g);
  boost::add_edge(centerVertex, v, g);
  v = boost::add_vertex(g);
  boost::add_edge(centerVertex, v, g);
  v = boost::add_vertex(g);
  boost::add_edge(centerVertex, v, g);
  v = boost::add_vertex(g);
  boost::add_edge(centerVertex, v, g);
  v = boost::add_vertex(g);
  boost::add_edge(centerVertex, v, g);
 
  // Attach an additional vertex to one of the star arm vertices
  Vertex x = boost::add_vertex(g);
  boost::add_edge(v, x, g);
 
  // std::map used for convenient initialization
  typedef std::map<Edge, int> StdEdgeIndexMap;
  StdEdgeIndexMap my_e_index;
  // associative property map needed for iterator property map-wrapper
  typedef boost::associative_property_map< StdEdgeIndexMap > EdgeIndexMap;
  EdgeIndexMap e_index(my_e_index);
 
  // We use setS as edge-container -> no automatic indices
  // -> Create and set it explicitly
  int i = 0;
  BGL_FORALL_EDGES(edge, g, Graph)
  {
    my_e_index.insert(std::pair< Edge, int >( edge, i));
    ++i;
  }
 
  // Define EdgeCentralityMap
  std::vector< double > e_centrality_vec(boost::num_edges(g), 0.0);
  // Create the external property map
  boost::iterator_property_map< std::vector< double >::iterator, EdgeIndexMap >
          e_centrality_map(e_centrality_vec.begin(), e_index);
 
  // Define VertexCentralityMap
  typedef boost::property_map< Graph, boost::vertex_index_t>::type VertexIndexMap;
  VertexIndexMap v_index = get(boost::vertex_index, g);
  std::vector< double > v_centrality_vec(boost::num_vertices(g), 0.0);
  // Create the external property map
  boost::iterator_property_map< std::vector< double >::iterator, VertexIndexMap >
          v_centrality_map(v_centrality_vec.begin(), v_index);
 
 
  std::cout << "Before" << std::endl;
  print_graph(g);
 
  BGL_FORALL_EDGES(edge, g, Graph)
  {
    std::cout << edge << ": " << e_centrality_map[edge] << std::endl;
  }
 
  // Write to graphviz -> illustrate the graph via 'neato -Tps before.dot > before.ps'
  WriteGraph(g, "before.dot");
 
  // Calculate the vertex and edge centralites
  // Can be used to get an initial impression about the edge centrality values for the graph
  //brandes_betweenness_centrality( g, v_centrality_map, e_centrality_map );
 
  // Define the done-object:
  // 'false' means here that no normalization is performed, so edge centrality-values can become big
  // If set to 'true', values will range between 0 and 1 but will be more difficult to use for this
  // illustrative example.
  boost::bc_clustering_threshold< double > terminate(max_centrality, g, false);
 
  //
  // Do the clustering
  // Does also calculate the brandes_betweenness_centrality and stores it in e_centrality_map
  //
  betweenness_centrality_clustering( g, terminate, e_centrality_map );
 
  // Print the results
  std::cout << "\nAfter" << std::endl;
  print_graph(g);
 
  BGL_FORALL_EDGES(edge, g, Graph)
  {
    std::cout << edge << ": " <<e_centrality_map[edge] << std::endl;
  }
 
  // Write to graphviz -> illustrate the graph via 'neato -Tps after.dot > after.ps'
  WriteGraph(g, "after.dot");
 
  return 0;
}
 
void WriteGraph(const Graph& g, const std::string& filename)
{
  std::ofstream graphStream;
  graphStream.open(filename.c_str());
  boost::write_graphviz(graphStream, g );
  graphStream.close();
}

CPP (C++) time

October 21st, 2011

There are may ways to estimate how long a program (or a part of the program) elapsed.

Use clock()

clock() is a standard function defined in . Here is the usage:

#include <ctime>

int main() {
  clock_t start, end;
  start = clock();
  // do sth...
  end = clock();

  double elapsedSeconds = (end - start) / CLOCKS_PER_SEC;
}
 

Use gettimeofday()

clock() is a linux function defined in . Here is the usage: #include <sys/time.h> int main() { timeval start, end; gettimeofday(&start, 0); // the second parameter is the timezone. // do sth... gettimeofday(&end, 0); double elapsedSeconds = (end.tv_sec - start.tv_sec + 1e-6*(end.tv_usec - start.tv_usec)); }

solve the problem of no output in console on windows eclipse with MinGW

October 14th, 2011

If you are experiencing the problem of no output in console on windows eclipse with MinGW, here is the solution.

And actually the solution the is very simple, you only have to add a PATH variable to your MinGW bin directory in the run configuration.

Here are the steps:

From menu: Run -> Run Configuration…, open the run configuration window, and add the PATH variable to your MinGW bin directory (as shown in the picture below).

Differences between new/delete and malloc/free in C and CPP

October 4th, 2011

There is a very good post about this: http://www.codeproject.com/KB/tips/newandmalloc.aspx.

Here I’ll just list some of the differences concisely:

  • new & delete will call the object’s default constructor & destructor respectively; while malloc & free will not. This is also why dynamically array will call it’s element’s default constuctor. See http://liuweipingblog.cn/cpp/array-initialization-in-cpp/.
  • malloc returns a void*, so it’s result always needs cast. Such as: FooCls* t = (FooCls*) malloc(sizeof FooCls);
  • when using new to create an array, delete[] is needed. And never delete[] a single object, it's even worse.
  • realloc only exists with malloc/free pair. It's handy when resize an object to the same or less size.
  • new & delete are based on malloc & free. Malloc additionally allocate a header storing the size allocated, so free() knows the size to free. new[] not only keeps the malloc header, but also has an extra header storing the size of the array/vector, so delete[] knows how many objects are in the array/vector, and thus knows how many times to call the destructor.
    details of new[] & delete[] can be found at: Mismatching scalar and vector new and delete

mysqlpp connection timeout problem

October 3rd, 2011

If you have a application having long time connection with mysql using mysqlpp. You may at first think of using Connection::connected() to determine whether the connection is still valid. But actually this doesn’t work if the connection gets timeout.

After checking the reference, I found out Connection::ping() would be a good way to determine timeout.

Here is a piece of test code:

#include <iostream>
#include <string>
#include <mysql++.h>

using namespace std;

int main() {
	string db_schema("DB_SCHEMA");
	string db_host("DB_HOST");
	string db_user("DB_USER");
	string db_pass("DB_PASS");
	string qry_str("SELECT MAX(user_id) FROM users");

	mysqlpp::Connection cn;
	cn.connect(db_schema.c_str(), db_host.c_str(), db_user.c_str(), db_pass.c_str());
	mysqlpp::Query qry = cn.query(qry_str);
	mysqlpp::StoreQueryResult res = qry.store();
	cout << "frist query result: " << res[0][0] << endl;

	string tmp;
	cout << "Wait for a period of time to let the connection timeout, and then input whatever a string to continue: " << endl;
	cin >> tmp;

	cout << "ping result: " << cn.ping() << endl;
	cout << "connected: " << cn.connected() << endl;
	
	if(!cn.ping())
		cn.connect(db_schema.c_str(), db_host.c_str(), db_user.c_str(), db_pass.c_str());
	mysqlpp::Query qry2 = cn.query(qry_str);
	res = qry2.store();
	cout << "second query result: " << res[0][0] << endl;

	cn.disconnect();
	
	return 0;	
}

But of course, I’m still new to mysqlpp. There may be a better way to do this. Please comment below if you have a better way.

NOTE: Here is how to change mysql connection idle timeout.

UPDATE: Just found another way to handle the timeout problem: use Connection::set_option(new mysqlpp::ReconnectOption(true));. This is much more elegant.
Here is a piece of sample code:

mysqlpp::Connection cn;
cn.set_option(new mysqlpp::ReconnectOption(true));
cn.connect(db_schema.c_str(), db_host.c_str(), db_user.c_str(), db_pass.c_str());

System V message queue example (msgget, msgctl, msgsnd, msgrcv)

September 21st, 2011

Found a very good example of message queue showing how to use msgget, msgctl, msgsnd, and msgrcv at http://www.dps.uibk.ac.at/~tf/lehre/ss04old/bs/tutorials/prozesse-syscalls/29.htm. Here I list the code with tiny fix and some of my comments.

The linux man page of msgsnd & msgrcv can be found here: http://linux.die.net/man/2/msgrcv.

———————————————-
msg_queue.c
———————————————-

#include<string.h>
#include<time.h>
#include<sys/ipc.h>
#include<sys/msg.h>
#include<sys/wait.h>
#include<sys/errno.h>
     
extern int errno;       // error NO.
#define MSGPERM 0600    // msg queue permission
#define MSGTXTLEN 128   // msg text length

int msgqid, rc;
int done;

struct msg_buf {
  long mtype;
  char mtext[MSGTXTLEN];
} msg;

int main(int argc,char **argv)
{
  // create a message queue. If here you get a invalid msgid and use it in msgsnd() or msgrcg(), an Invalid Argument error will be returned.
  msgqid = msgget(IPC_PRIVATE, MSGPERM|IPC_CREAT|IPC_EXCL);
  if (msgqid < 0) {
    perror(strerror(errno));
    printf("failed to create message queue with msgqid = %d\n", msgqid);
    return 1;
  }
  printf("message queue %d created\n",msgqid);
  
  // message to send
  msg.mtype = 1; // set the type of message
  sprintf (msg.mtext, "%s\n", "a text msg..."); /* setting the right time format by means of ctime() */

  // send the message to queue
  rc = msgsnd(msgqid, &msg, sizeof(msg.mtext), 0); // the last param can be: 0, IPC_NOWAIT, MSG_NOERROR, or IPC_NOWAIT|MSG_NOERROR.
  if (rc < 0) {
    perror( strerror(errno) );
    printf("msgsnd failed, rc = %d\n", rc);
    return 1;
  }

  // read the message from queue
  rc = msgrcv(msgqid, &msg, sizeof(msg.mtext), 0, 0); 
  if (rc < 0) {
    perror( strerror(errno) );
    printf("msgrcv failed, rc=%d\n", rc);
    return 1;
  } 
  printf("received msg: %s\n", msg.mtext);

  // remove the queue
  rc=msgctl(msgqid,IPC_RMID,NULL);
  if (rc < 0) {
    perror( strerror(errno) );
    printf("msgctl (return queue) failed, rc=%d\n", rc);
    return 1;
  }
  printf("message queue %d is gone\n",msgqid);

  return 0;
}

————– Update 14/Dec/2011 ——————
A note about the struct msg_buf. From: “The Linux Programmer’s Guide” http://tldp.org/LDP/lpg/node30.html.

The ability to assign a given message a type, essentially gives you the capability to multiplex messages on a single queue. For instance, client processes could be assigned a magic number, which could be used as the message type for messages sent from a server process. The server itself could use some other number, which clients could use to send messages to it. In another scenario, an application could mark error messages as having a message type of 1, request messages could be type 2, etc. The possibilities are endless.

On another note, do not be misled by the almost too-descriptive name assigned to the message data element (mtext). This field is not restricted to holding only arrays of characters, but any data, in any form. The field itself is actually completely arbitrary, since this structure gets redefined by the application programmer. Consider this redefinition:


struct my_msgbuf {
long mtype; /* Message type */
long request_id; /* Request identifier */
struct client info; /* Client information structure */
};

Here we see the message type, as before, but the remainder of the structure has been replaced by two other elements, one of which is another structure! This is the beauty of message queues. The kernel makes no translations of data whatsoever. Any information can be sent.

Install & use mysql++ on linux(debian squeeze, ubuntu)

July 28th, 2011

The key to use mysql++ on debian/ubuntu system is to find where the mysql++ .h head files and the .so binary files.

Firrst install mysqlclient and mysql++ on debian squeeze:

root# apt-get install libmysqlclient-dev libmysqld-dev libmysql++-dev libmysql++-doc libmysql++3

This will install the mysql head files in /usr/include/mysql, mysql++ head files in /usr/include/mysql, and libmysqlpp.so and libmysqlclient.so in /usr/lib. These are all the files we need.

Now let us use the mysql++ library.

Save the simple code below as test.cpp

#include <iostream>
#include <mysql++.h>

int main() {

mysqlpp::String s(“hello, world”);

std::cout << s << std::endl;

return 0;

}

And save the makefile as Makefile:

CXX := g++
CXXFLAGS := -I/usr/include/mysql -I/usr/include/mysql++

LDFLAGS := -L/usr/lib -lmysqlpp -lmysqlclient -lnsl -lz -lm
EXECUTABLE := main

all: test
clean:        rm -f $(EXECUTABLE) *.o

Finally, excute

make all

The compile result would be test.

problem of returning *this in C++

July 5th, 2011

I have a small class, in one of whose methods I want to return the instance itself so I can continue to use the instance and thus save inputting. However, “return *this” seems not working as waht I expected. The class is like this:

UndirectedGraph.h

/*
* UndirectedGraph.h
*/

#ifndef UNDIRECTEDGRAPH_H_
#define UNDIRECTEDGRAPH_H_

#include <utility>
#include <set>

using namespace std;

namespace wp {

class UndirectedGraph {
public:
UndirectedGraph(size_t n);
virtual ~UndirectedGraph();

UndirectedGraph
//void
addEdge(size_t node1, size_t node2);

private:
size_t len;
set *nbs;
};

}

 

#endif /* UNDIRECTEDGRAPH_H_ */

UndirectedGraph.cpp

/*
* UndirectedGraph.cpp
*/
#include <utility>
#include <set>
#include <iostream>
#include "UndirectedGraph.h"

using namespace std;

namespace wp {

UndirectedGraph::UndirectedGraph(size_t n) : len(n) {
std::cout << "constructor with len: " << this->len << std::endl;
for(size_t node = 0; node != n; ++node) {
nbs = new set[this->len];
}
}

UndirectedGraph::~UndirectedGraph() {
delete[] nbs;
std::cout << "destructor finished" << std::endl;
}

UndirectedGraph
//void
UndirectedGraph::addEdge(size_t node1, size_t node2) {
if(node1 >= this->len || node2 >= this->len)
throw 1;
if(node1 == node2)
throw 2;
this->nbs[node1].insert(node2);
this->nbs[node2].insert(node1);
return *this;
}

 

 

}

And in the main() function:

int main() {
UndirectedGraph g(7);
g.addEdge(0, 1).addEdge(0, 2)
.addEdge(1, 3).addEdge(1, 5);
return EXIT_SUCCESS;
}

What am I missing?

————– EDIT ————-
The solution to the problem is to return *this as a reference to itself, as below:
UndirectedGraph & addEdge(size_t node1, size_t node2);

c++ arrays memo

November 30th, 2010

1. arrays initialization

under GCC, when you create an array statically, it’s not initialized. while you create it dynamically, it’s initialized.
here is the test code:

int main () {

	int N(1000000);

	// statically created array, not initialized
	int a[N];
	for(int i = 0; i < N; ++i) {
		if(a[i] != 0) {
			cout << "a[N] is not all zero!!!" << endl;
			break;
		}
	}

	// dynamically created array, initialized
	int *b;
	b = new int[N];
	for(int i = 0; i < N; ++i) {
		if(b[i] != 0) {
			cout << "b[N] is not all zero!!!" << endl;
			break;
		}
	}
	// dynamically created array, initialized	
	int *c;
	c = new int[N]();
	for(int i = 0; i < N; ++i) {
		if(c[i] != 0) {
			cout << "c[N] is not all zero!!!" << endl;
			break;
		}
	}
}

2. return array from function

Arrays of other types are typically returned via reference:

void retArray( (int*)& p, unsigned& size )
{
	size = 4;
	p = new int[ size ];
	for (int n = 1; n < 4; n++)
		p[ n ] = n;
}