Share Email Print
cover

Proceedings Paper

Storage and manipulations of directed graph based on OBDD
Author(s): Yanru Zhong; Meifa Huang; Tianlong Gu
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

Ordered binary decision diagram (OBDD) is a new kind of typical graph-based data structures for representing Boolean expressions. Combinatorial explosions are inevitable when storing and manipulating large graphs by conventional data structures. OBDD provides the deleting and merging rules to realize the compressed storage of graphs. This paper presents a new method of storage and manipulations of directed graph based on OBDD. The vertices of directed graph are coded in binary scale so as to express the vertices in Boolean expressions. The edges of directed graph are therefore expressed in Boolean relations. In this way, the directed graph can be represented by OBDD. With such representations, we can use the available algorithms based on OBDD and the manipulations of directed graph are implemented by employing the operations of Boolean functions. The manipulations realized in this paper include computing the input and/or output degrees of the vertices of directed graphs, inserting edges into the graph, deleting edges from the graph, locating the edges, and traversing the graph in breadth-first search. A simulation experiment is provided with various kinds of random generated directed graph. The experimental results demonstrate that the storage of directed graph based on OBDD is more efficient than that of by adjacency list when dealing with large directed graph.

Paper Details

Date Published: 30 October 2006
PDF: 6 pages
Proc. SPIE 6358, Sixth International Symposium on Instrumentation and Control Technology: Sensors, Automatic Measurement, Control, and Computer Simulation, 63585I (30 October 2006); doi: 10.1117/12.718310
Show Author Affiliations
Yanru Zhong, Guilin Univ. of Electronic Technology (China)
Meifa Huang, Guilin Univ. of Electronic Technology (China)
Tianlong Gu, Guilin Univ. of Electronic Technology (China)


Published in SPIE Proceedings Vol. 6358:
Sixth International Symposium on Instrumentation and Control Technology: Sensors, Automatic Measurement, Control, and Computer Simulation
Jiancheng Fang; Zhongyu Wang, Editor(s)

© SPIE. Terms of Use
Back to Top