How to Use the Special Graph Constructor G ( int n, int e)

The following program shows how to use the special constructor. In main() it generates a graph with two slots for the nodes and one slot for the edges. Then it generates a random graph with 50 nodes and 100 edges.

The data slots for the nodes and the edges are used as follows. Simply define a node_array, respectively edge_array, with your information type T and call the function use_node_data(G,T t). This function reserves one slot for the array and initializes all entries to t. The information can be accessed by the usual operations for the arrays. If no slot is available, a standard array is used.

The main() function in our example defines three node arrays and two edge arrays of type int for G. For each node array the function node_array_time() is called and for each edge array the function edge_array_time() is called. These functions iterate through all nodes (edges) of G and access and write the node (edge) information. The time needed for this loop is returned.

The lists of nodes and edges of G are randomly permuted in main(), because this is the situation where the performance gap between "usual" node/edge arrays and node/edge data slots is most significant. On the authors machine, the difference was about 60% improvement for the node arrays and 100% for the edge_arrays.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/graph_gen.h> 

using namespace leda;

float node_array_time(const list<node>& LN, node_array<int>& na) 
{
  float t=used_time();
  node v; forall(v,LN) na[v]=na[v]+4711;
  t=used_time(t);
  return t;
}

float edge_array_time(const list<edge>& LE, edge_array<int>& ea) 
{
  float t=used_time();
  edge e; forall(e,LE) ea[e]=ea[e]+4711;
  t=used_time(t);
  return t;
}


int main()
{
  int n_slots=2;
  int e_slots=1;
  
  graph G(n_slots,e_slots);
  random_graph(G,50000,1000000);

  list<node> LN=G.all_nodes();
  LN.permute();
  list<edge> LE=G.all_edges();
  LE.permute();
  
  node_array<int> n1;
  n1.use_node_data(G,1);   //node data slot
  std::cout << "tn1=" << node_array_time(LN,n1)  << std::endl;

  node_array<int> n2;
  n2.use_node_data(G,2);   //node data slot 
  std::cout << "tn2=" << node_array_time(LN,n2) << std::endl;

  node_array<int> n3;
  n3.use_node_data(G,3);   //standard node_array
  std::cout << "tn3=" << node_array_time(LN,n3) << std::endl;

  edge_array<int> e1;
  e1.use_edge_data(G,1);   //edge data slot
  std::cout << "te1=" << edge_array_time(LE,e1) << std::endl;

  edge_array<int> e2;
  e2.use_edge_data(G,2);  //standard edge_array 
  std::cout << "te2=" << edge_array_time(LE,e2) << std::endl;

  return 0;
}   

See also:

Special Graph Constructor G(int n, int e)

Graphs and Related Data Types

Graph Generators

Node Arrays

Edge Arrays

Associate Information with Graphs

Manual Entries:

Manual Page Graphs