Posts Tagged ‘example’

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();
}

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.