CODEWITHSUNDEEP
javaalgorithmgraphbreadth-first-searchadjacency-list
Kevin Cruijssen
Kevin Cruijssen

Reputation: 9326

Breadth-first graph search with multiple entry and exit points

I am trying to make an adjacent list for a directed graph, while the graph has multiple entry and exit points. In the graph the Nodes would be things like AND, OR, NOT, XOR, etc. and the Entry and Exit points will be a single bit (0 or 1).

I've got the following Nodes:

And the following connections between them:

Picture:

Graph of circuit in question

So now I need to calculate the bytes at the exits of D and E, by following the path of the directed graph.

I found a link of a breath-first graph search with single entry and exit points here:
Graph Algorithm To Find All Connections Between Two Arbitrary Vertices.

How can I adapt this breath-first graph search in the link so I can have multiple entry and exit points, and at the same time remove/change the recursive part (since I'm getting StackOverflowErrors when using the code in the link above, even when I only have 1 entry and exit point).

Upvotes: 0

Views: 1772

Answers (3)

AJMansfield
AJMansfield

Reputation: 4129

The first thing to note is that dependancy flows only one way along each link, and what you call 'nodes' are anything but. A general-purpose graph search is inappropriate for this problem.

You can easily determine the reason this is so if you observe that your list of nodes and links between them does not in fact uniquely specify the graph you have drawn. I could flip all the gates back around, hook their output to their left input, the left input to the right, and the right to the output, or reverse the direction of all the not gates, and the lists of nodes and links you have would still be correct.

If I were to go about modelling this, I would do something entirely different:

interface Component {
    boolean value();
}

class And implements Component {
    Component[] inputs;
    public And(Component ... inputs){ this.inputs = inputs; }
    boolean value(){
        for(Component c:inputs) if(!c.value()) return false;
        return true;
    }
}
class Or implements Component {
    Component[] inputs;
    public Or(Component ... inputs){ this.inputs = inputs; }
    boolean value(){
        for(Component c:inputs) if(c.value()) return true;
        return false;
    }
}
class Not implements Component {
    Component input;
    public Not(Component input){ this.input = input; }
    boolean value(){ return !input.value(); }
}
class Input implements Component {
    boolean value;
    public Input(boolean value){ set(value); }
    void set(boolean newValue){ this.value = value; }
    boolean value(){ return value; }
}

Now that we have our basic logic gates, we can build a more complete model using them:

public static void main(String ... args){
    Input a = new Input(true), b = new Input(true), c = new Input(false);
    Component n1 = new Or(a, b), n2 = new And(a, b), n3 = new And(c, n2),
              n4 = new Not(n2), n5 = new And(n1, n4), n6 = new Or(n2, n3),
              n7 = new Not(c), n8 = new Not(n5), n9 = new And(n5, n7),
              n10 = new And(c, n8), n11 = new Or(n9, n10);
    Component d = n11, e = n6;
}

The resulta are then d.value() and e.value(). If we instead need strings that representing the values as equations, we can override the toString method of each gate:

class And implements Component {
    //...
    public String toString(){
        StringBuilder b = new StringBuilder("(");
        for(Component c:inputs) b.append(c).append("&&");
        return b.replace(b.length()-2,b.length,")").toString();
    }
}
class Or implements Component {
    //...
    public String toString(){
        StringBuilder b = new StringBuilder("(");
        for(Component c:inputs) b.append(c).append("||");
        return b.replace(b.length()-2,b.length,")").toString();
    }
}
class Not implements Component {
    //...
    public String toString(){
        return String.format("!%1$s",input);
    }
}

Now, any Component.toString() will return a logical expression for its value in terms of its inputs, which are themselves expressions in terms of their inputs, and so on, up to the original Inputs.

Upvotes: 0

Catalin Pol
Catalin Pol

Reputation: 261

The problem you described is not a graph problem per se. What you need in fact is a boolean expression evaluator. If you represent the expression as a binary tree, the evaluation is easy.

In your picture, D is the root node for one of the trees. Each internal node of such a tree has 2 children, with the expression in the node itself. To evaluate, you will need a post-order traversal of the tree. The leaves are either A, B, C. For evaluating E, just build a different tree.

Let me know if you need some help with building the trees (I will try to add some pictures if needed).

After you've built your expression trees, just try all possible values for the leaves: eval(A,B,C) with all possible combinations - eval(false,false,false), eval(false,false,true) etc.

If you were only interested in combinations that yield true for one such expression, it's a known NP problem, so don't expect polynomial run-time: Boolean satisfiability problem

Upvotes: 0

Alexei Kaigorodov
Alexei Kaigorodov

Reputation: 13525

The idea to eliminate recursion is as follows: when all connections of a node get known value, that node is enqueued to execution. In your example, at the start these are nodes N1, N2, N7. Executor takes nodes ready for execution from the queue one by one, computes output value and passes it to the next connections, which may cause enqueueing another nodes etc. When the execution queue become empty, the result is ready.

You can program executor and nodes yourself (200-300 lines of code), or take ready-made library. To search for libraries, look for "colored Petri net java implementation". There are numerous java implementations of Petri net engines available. I did not use any of them except for my own df4h-core. Start from FormulaTest.java which computes various mathematical formulas. You'll have to implement your own nodes which compute boolean operations.

Upvotes: 1

Related Questions