Converting the paths in a graph to sum of products of each point

Hi,

First of all, I'm trying to find all possible paths between [1-8], [1-10],[1-12],[3-8],[3-10], [3-12], [5-8],[5-10],[5-12] in a graph as below, I did that part.

But the part I'm struggling is that I want every node's AND in each path and all of the path's OR , i.e. x1*x2*x7*x8 + x1*x2*x3*x4*x9*x8 + x1*x2*x3*x4*x5*x6*x11*x10*x9*x8 + .....and so on and after that I would like to simplify that whole summation in Boolean Algebraic.

Any help would be much appreciated.

Answer 1

[Anunay Yadav]

Hi,

I don't think there is an O(1) algebraic solution to this problem. But you can find the solution for a specific start and end point by checking if they are in the same connected component in a subgraph only containing nodes with Boolean value 1.

Explanation : SOP algebraic equations when worded imply that : check if there exists ( because of OR operation) a path between start and end node such that all the points in that path have Boolean value 1 (because of AND operation) hence to check that we only need to create a subgraph containing nodes which have Boolean value 1 only and then check whether two nodes are connected. If they are connected, then there exists a path between them such that all the nodes have Boolean value 1 in that path which therefore solves our problem.

So your problem reduces to finding whether two nodes are in the same connected component in the subgraph which contains nodes which have Boolean value 1 only. Checking whether two nodes are in the same connected component can be done with simple dfs, bfs traversal.

Resources :

https://en.wikipedia.org/wiki/Component_(graph_theory)

[Akay Caner Yalcin]

Thank you for your response,sorry I think I wasn't clear enough but I am afraid I don't think this is the solution I needed because in the end, problem is to find those paths eliminate each other by nature of Boolean algebra summation and finally simplify the whole summation which leaves us with only irredundant paths, not determining whether they are connected or not. For example; let's say upmost nodes (1, 3, 5) are inputs and downmost nodes (8, 10, 12) are outputs. In Boolean manner, if you take summation of x3x4x9x10 + x1x2x3x4x9x10, this equals to x3x4x9x10. The aim of the problem is to achieve this.