Storage and manipulations of directed graph based on OBDD

Yanru Zhong; Meifa Huang; Tianlong Gu

doi:10.1117/12.718310

30 October 2006 Storage and manipulations of directed graph based on OBDD

Yanru Zhong, Meifa Huang, Tianlong Gu

Proceedings Volume 6358, Sixth International Symposium on Instrumentation and Control Technology: Sensors, Automatic Measurement, Control, and Computer Simulation; 63585I (2006) https://doi.org/10.1117/12.718310
Event: Sixth International Symposium on Instrumentation and Control Technology, 2006, Beijing, China

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.

Citation Download Citation

Yanru Zhong, Meifa Huang, and Tianlong Gu "Storage and manipulations of directed graph based on OBDD", Proc. SPIE 6358, Sixth International Symposium on Instrumentation and Control Technology: Sensors, Automatic Measurement, Control, and Computer Simulation, 63585I (30 October 2006); https://doi.org/10.1117/12.718310

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available