Archive for the ‘CPP’ Category

* libboost and read_graphviz_dp

Posted on March 20th, 2013 by Alex. Filed under CPP.


After describing, how graphs can be stored, the question arises, how can they be read? Again we use this graph as an example

Example Graph

Example Graph

which is represented in the file example.dot:

digraph G {
	1 [op=2];
	2 [op=2];
	3 [op=2];
	4 [op=2];
	5 [op=0];
	6 [op=2];
	7 [op=2];
	8 [op=0];
	9 [op=8];
	10 [op=1];
	11 [op=1];
	1->6 ;
	2->6 ;
	3->7 ;
	4->8 ;
	5->9 ;
	6->10 ;
	7->11 ;
	10->11 ;
}

The vertices are a struct in my source code:

struct Vertex {			//-- properties of a node
	unsigned int id;	// The ID of the vertex.
	int asapTime;		// The time index when this vertex can be scheduled EARLIEST.
	int alapTime;		// The time index when this vertex can be scheduled LATEST.
	ops_e op;			// The type of operation that needs to be performed in this vertex
};

ops_e in line 5 is an enum type:

enum ops_e {ADD, SUB, MUL, DIV, RSH, LSH, RSHR, LSHR, CMP, total_ops};

Based on the previous experience the operators << and >> for ops_e are already overloaded and added to the std namespace.

The graph itself is stored as an adjacency list:

typedef adjacency_list<vecS, vecS, bidirectionalS, Vertex, no_property> DFGAdjList;

To read the graph, the dynamic properties need to be defined:

dynamic_properties dpInput;
dpInput.property("id", get(&Vertex::id, dfg));
dpInput.property("op", get(&Vertex::op, dfg));
	

//-- open the file
string filename = argv[1];
ifstream fin(filename.c_str());

//-- Fill dfg with the content of the file
read_graphviz(fin, dfg, dpInput, "id");

Have a look at the directory libboost/read_graphviz_dp in the zip file which can be downloaded below, to see the whole source code used in this example. If you get an error message such as

$ ./main graph.dot
terminate called after throwing an instance of 'boost::exception_detail::clone_impl >'
what(): Property not found: alapTime.
Aborted

check the graph.dot, if all properties are included. As you can see, in the source code, the property alapTime has not been defined. It might also necessary to use a current library to run this code which has been tested with version 1.53. To update a newer version, please refer the installation manual in the section "Option 2: write_graphviz_dp()".

Download

The source code can be downloaded here: libboost.tar.bz2

.



* libboost and write_graphviz(_dp)?

Posted on March 20th, 2013 by Alex. Filed under CPP.


Currently I am working with the boost library to handle graph operations. A requirement is to read and write the graphs from and to a file, which caused me a lot of head ache and time consuming searches for examples, how other developers implemented it. The found examples were somewhat not applicable to my problem. Hence I am summarizing here what I found out to write a graph to a file, so that other may simply copy and past most of the code. In another posting I am going to show, how I read the graph from a file. The code for the whole program can be downloaded at the bottom.

Lets assume I have the following graph which is used for all examples.

Example Graph

Example Graph


Probably you will recognize this graph from the paper “Force-directed scheduling for the behavioral synthesis of ASIC’s” by Pierre G. Paulin and John P. Knight.

This graph is a data flow graph (DFG). The vertices of this graph contain some properties such as operations to be executed and some integers for the sake of an example. The edges show the dependencies between the operations. The properties of each vertex are defined in a struct:

struct Vertex {			//-- properties of a node
	unsigned int id;	// The ID of the vertex.
	int asapTime;		// The time index when this vertex can be scheduled EARLIEST.
	int alapTime;		// The time index when this vertex can be scheduled LATEST.
	ops_e op;			// The type of operation that needs to be performed in this vertex
};

ops_e in line 5 is an enum type:

enum ops_e {ADD, SUB, MUL, DIV, RSH, LSH, RSHR, LSHR, CMP, total_ops};

For the graph I am using a adjacency_list. As you can see, I am using the struct Vertex to define the vertex properties. I do not care about the edges, so they have no_property. Apart form that I am using a bidirectional graph so that I can nicely walk through outgoing and incoming edges.

typedef adjacency_list<vecS, vecS, bidirectionalS, Vertex, no_property> DFGAdjList;

Now the graph needs to be filled to get the example:

// the definition of Vertex, ops_e and DFGAdjList are omitted here
enum nodes_e {N1, N2, N3, N4, N5, N6, N7, N8, N9, N10, N11, N12, N13, N14, N15, total_nodes};
typedef graph_traits<DFGAdjList>::vertex_descriptor VertexDesc;

int main(void) {
	VertexDesc curVertexDFG;
	DFGAdjList dfg;

	//-- Fill the verices with operations
	ops_e operations[11];
	operations[0] = MUL;
	operations[1] = MUL;
	operations[2] = MUL;
	operations[3] = MUL;
	operations[4] = ADD;
	operations[5] = MUL;
	operations[6] = MUL;
	operations[7] = ADD;
	operations[8] = CMP;
	operations[9] = SUB;
	operations[10] = SUB;

	for(int i=0; i<11; ++i) {
		curVertexDFG = add_vertex(dfg);
		dfg[curVertexDFG].id = i;
		dfg[curVertexDFG].asapTime = -1;
		dfg[curVertexDFG].alapTime = -1;
		dfg[curVertexDFG].op = operations[i];
	}

	//-- Add the edges
	add_edge(N1, N6, dfg);
	add_edge(N2, N6, dfg);
	add_edge(N3, N7, dfg);
	add_edge(N4, N8, dfg);
	add_edge(N5, N9, dfg);
	add_edge(N6, N10, dfg);
	add_edge(N7, N11, dfg);
	add_edge(N10, N11, dfg);

	return EXIT_SUCCESS;
}

So, now this graph needs to be stored. There are two options: Using a writer class telling write_graphviz() how this graph is stored. This option works at least in libboost 1.41. Or using dynamic properties by using write_graphviz_dp(). For that I have to update the library, which is quite an easy job. I would like to show you both options:

Option 1: write_graphviz()

A writer class is quite simply implemented. You do not need to understand the whole thing, just the places that you need to adapt to work for your graph. In this example the helper class looks like the following one:

template <class GraphType> class myVertexWriter {
	public:
	myVertexWriter(GraphType _graphType) : graphType(_graphType) {}
	template <class VertexOrEdge> void operator()(std::ostream &out, const VertexOrEdge &v) const {
		out << "[id=\"" << graphType[v].id << "\", " <<
			"op=\"" << graphType[v].op  << "\", " <<
			"asapTime=\"" << graphType[v].asapTime << "\", " <<
			"alapTime=\"" << graphType[v].alapTime << "\", " <<
			"label=\"" << graphType[v].id << "\\nop:" << graphType[v].op << "\"]"; // for dotty
	}

	private:
	GraphType graphType;
};

As you can see, the class is templated so it can be used for all kind of graph types (DFGAdjList) in this example. So it tells the function write_graphviz() how the graph is stored. The main program is extended to call the function:

//...
	add_edge(N7, N11, dfg);
	add_edge(N10, N11, dfg);

	myVertexWriter<DFGAdjList> vw(dfg); //-- instantiate the writer class
	ofstream fout("graph.dot");
	write_graphviz_dp(fout, dfg, vw);

	return EXIT_SUCCESS;
}

The files are located in the directory libboost/write_graphviz in the zip-file. After compiling the code by executing make in the console, a new file “graph.dot” is created with the following content:

digraph G {
0[id="0", op="2", asapTime="-1", alapTime="-1", label="0\nop:2"];
1[id="1", op="2", asapTime="-1", alapTime="-1", label="1\nop:2"];
2[id="2", op="2", asapTime="-1", alapTime="-1", label="2\nop:2"];
3[id="3", op="2", asapTime="-1", alapTime="-1", label="3\nop:2"];
4[id="4", op="0", asapTime="-1", alapTime="-1", label="4\nop:0"];
5[id="5", op="2", asapTime="-1", alapTime="-1", label="5\nop:2"];
6[id="6", op="2", asapTime="-1", alapTime="-1", label="6\nop:2"];
7[id="7", op="0", asapTime="-1", alapTime="-1", label="7\nop:0"];
8[id="8", op="8", asapTime="-1", alapTime="-1", label="8\nop:8"];
9[id="9", op="1", asapTime="-1", alapTime="-1", label="9\nop:1"];
10[id="10", op="1", asapTime="-1", alapTime="-1", label="10\nop:1"];
0->5 ;
1->5 ;
2->6 ;
3->7 ;
4->8 ;
5->9 ;
6->10 ;
9->10 ;
}

which is the representation of the example graph in .dot format. dot -Tjpg graph.dot > graph.jpg in the console converts graph.dot into graph.jpg:Graph after write_graphviz()

Option 2: write_graphviz_dp()

This function call uses dynamic properties (dp) to store the vertex properties. As far as I remember this function was introduced into libboost with version 1.44. Hence if you are running on an Debian stable system or another one, which does not have a current libboost, the road does not have to end here. A new version of libboost is easily installed and can be done, if you do not have root access to the system. Without using graphviz functions, nothing has to be compiled anyway. Here is a short description of the commands that I executed to get the libraries compiled to allow me to use write_graphviz_dp():

  1. Download the latest stable boost library from here. There is a “Download” link in the gray box.
  2. Download the .bz file and save it somewhere, where you have space and where you find it.
  3. Execute tar xfj boost_1_53_0.tar.bz2 in the console to unpack the files. As you can see at the time of writing this post, version 1.53 was the current release.
  4. Change into the newly created directory with cd boost_1_53_0, execute ./bootstrap --prefix=YOUR_DESTINATION_DIR --with-libraries=graph,regex
  5. It takes around 10 seconds, till the command prompt comes back. After that execute ./b2 -j6 install, which compiles the required parts using 6 cores (-j6) and copies everything to YOUR_DESTINATION_DIR.
  6. Now we have to tell the compiled programs using the graph and regex library to use the new library: export LD_LIBRARY_PATH=YOUR_DESTINATION_DIR/lib/:$LD_LIBRARY_PATH.
  7. And we have to tell the compiler to use the new header files (.hpp) during compilation and linking process by adding -IYOUR_DESTINATION_DIR/include -LYOUR_DESTINATION_DIR/lib/ -lboost_graph -lboost_regex to the c++ command. Have a look at the Makefile in libboost/write_graphviz_dp in the zip-file which can be downloaded below.

After the new library is installed, the main file is modified to

//...
	add_edge(N7, N11, dfg);
	add_edge(N10, N11, dfg);

	//-- what is stored?
	dynamic_properties dpOutput;
	dpOutput.property("id", get(&Vertex::id, dfg));
	dpOutput.property("op", get(&Vertex::op, dfg));
	dpOutput.property("asapTime", get(&Vertex::asapTime, dfg));
	dpOutput.property("alapTime", get(&Vertex::alapTime, dfg));

	//-- save the graph in a file
	ofstream fout("graph.dot");
	write_graphviz_dp(fout, dfg, dpOutput, string("id"));

	//-- send it to the console
	write_graphviz_dp(std::cout, dfg, dpOutput, string("id"));

	return EXIT_SUCCESS;
}

and the writer class myVertexWriter is removed, since there is no need for it anymore. If this is compiled, the compiler throws a long list of error messages at you. Somewhere down in these lines is the following is written:

YOUR_DESTINATION_DIR/include/boost/lexical_cast.hpp:1513: error: no match for ‘operator<<’ in ‘((boost::detail::lexical_stream_limited_src, true>*)this)->boost::detail::lexical_stream_limited_src, true>::out_stream << input’

and

YOUR_DESTINATION_DIR/include/boost/lexical_cast.hpp:1899: error: no match for ‘operator>>’ in ‘stream >> output’

So something could not be stored. Since the struct of Vertex only uses mostly primitives (integers here), it has something to do with the enum type. If line 8 in the code above is commented, it compiles. But how to include the enum type into the output? By overloading the << and >> operator:

enum ops_e {ADD, SUB, MUL, DIV, RSH, LSH, RSHR, LSHR, CMP, total_ops};
std::ostream& operator<<(std::ostream &os, const ops_e op) {
	os << (int)op;
	return os;
}
std::istream& operator>>(std::istream &is, ops_e &op) {
	int operation;
	is >> operation;
	op = static_cast<ops_e>(operation);
	return is;
}

Unfortunately this does not work and the error messages do not change at all. On Stackoverflow a user reported the same error message. The problem is that the overloading << and >> operators are defined globally, but the function lexical_cast only looks into the namespaces of std and boost and hence cannot find any of these defined operators. Hence they need to be added to std:

enum ops_e {ADD, SUB, MUL, DIV, RSH, LSH, RSHR, LSHR, CMP, total_ops};
namespace std {
	std::ostream& operator<<(std::ostream &os, const ops_e op) {
		os << (int)op;
		return os;
	}
	std::istream& operator>>(std::istream &is, ops_e &op) {
		int operation;
		is >> operation;
		op = static_cast<ops_e>(operation);
		return is;
	}
}

Now it compiles and works. The question is, why should somebody go through the pain in choosing option 2? The answer is that this can be easily read in by read_graphviz_dp().

Download

The example code can be downloaded here: libboost.tar.bz2

.



RSS Feeds:

Search:


Pages:

Categories:

Archives: