Talk:Binary decision diagram

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated C-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 

"The resulting BDD is shown in the right figure." -- eh? What right figure? —Preceding unsigned comment added by 200.188.209.86 (talk) 03:44, 30 April 2008 (UTC)

the sentence "For a long time, this representation was called Alternative Graphs, until it was once renamed." needs fixing... either until it was renamed or until it was once again renamed ???

Two years before Lee the same idea was introduced in former Soviet Union, in Tallinn University of 
Technology  (Ubar 1976). For a long time, this representation was called Alternative Graphs, 
until it was once renamed.

I removed the above from the article, because (Ubar 1976) is not two years before (Lee 1959). Or does it mean before Akers??? I also don't understand the renaming thing. --Dirk 12:34, 1 September 2005 (UTC)

It means before Akers - Ubar from my understanding was the first to impose the sorted restriction on the tree (according to section 3.1 of Jaan Raik's masters thesis also from the same source it doesnt seem like the names are conflicting since there are diffrences in the graphs and the ROBDD can apparently be considered a specialization of the Alternative Graph (havent seen Ubars paper but Raik has co-authered papers with Ubar since then so it would seem he got his information directly from the source) Doctus (20 minutes before I learnt to insert four instead of 3 tilders)

After some more searching it turns out that Alternative Graphs eventually became known as Structurally synthesized binary decision diagrams and the reason nobody new about Ubars work was because it was published in Rusion. Doctus 03:04, 17 April 2006 (UTC)


Implementation[edit]

I have moved the section "Implementation" here (see below). Wikipedia is not a dumping ground for code, and not an implementation howto (see WP:NOTHOWTO for the official policy. Perhaps it is useful for one of the sister projects, such as wikisource. If someone disagrees and intends to put the implementation back into the article, please provide an argument before doing so. Hermel (talk) 19:18, 16 June 2009 (UTC)


This is a crude way to build a BDD in a C like language. Declare the data structure as follows and then proceed accordingly.

 /* The basic data structure */	
 struct vertex
 {
    char *φ;
    struct vertex *hi, *lo;
    ..
 }
 
 /* The interface to the Unique Table */
 struct vertex *old_or_new(char *φ, struct vertex *hi, *lo)
 {
    if(“a vertex  v = (φ, hi, lo) exists”)
        return  v;
    else {
        v <- “new vertex pointing at (φ, hi, lo);
        return  v;
    }
 }

Data Structure for Building the ROBDD

 struct vertex *robdd_build(struct expr <math>f</math>, int i)
 {
    struct vertex *hi, *lo;
    struct char *φ;
 
    if(equal(f, '0'))
       return v0;
    else if (equal(f, '1'))
       return v1;
    else {
       φ ← п(i);
       hi ← robdd_build( <math>f (xi = 1)</math>, i+1);
       lo ← robdd_build( <math>f (xi = 0)</math>, i+1);
 
       if(lo == hi) 
          return lo;
       else
          return old_or_new(φ, hi, lo);
    }
 }

Ext links[edit]

Should all of those links be removed? Seems like it goes against WP:NOTLINK. LogicalFinance33 (talk) 22:55, 31 January 2012 (UTC)

The policy states that at Wikipedia we don't allow collection of links as that may dwarf the page but this could be one of those borderline cases where the number of links might be high but each of them quite important from the article's perspective. Any ideas?--Wikishagnik (talk) 18:19, 28 March 2012 (UTC)
I removed the 404 and ones requesting contact by email to get program, others had like 32 downloads or were not even full releases. I kept the best looking ones and removed the tag. Its not really a problem I think. They are different and don't dwarf the article. ChrisGualtieri (talk) 05:50, 16 May 2012 (UTC)
Some (like CMU, CAL and CUDD) are included for historical reasons but some others are actually used by people. I added back JDD and BuDDy and removed some others I felt could be left out instead. Behandeem (talk) 16:41, 5 February 2013 (UTC)

Lead[edit]

The lead currently begins:

In the field of computer science, a binary decision diagram (BDD) or branching program, like a negation normal form (NNF) or a propositional directed acyclic graph (PDAG), is a data structure that is used to represent a Boolean function.

I don't understand why the lead is mentioning NNF and PDAG here. Yes, they are other representations of Boolean functions, but there are many others. Why mention them at all? And why in the lead? --Macrakis (talk) 22:56, 13 December 2013 (UTC)