How to eliminate cycle's in BOM (Bill of Material) hierarchical graph ?

[pm-hwks]

In manufacturing, it is typical to have multi level hierarchy of bill of materials to build / assemble products. Due to human error or other reason's some times cyclic relationships are entered in to the data. This cyclic relationships leads to several issue with BOM traversal and analytics.

How to detect and eliminate such cyclic relationships?

simple example : In the invalid tree, there is an edge from F to C which needs to be detected and deleted.

Valid trees:
a)
      A              
     / \             
    B   C               
         \
          D
         / \
        E   F

b)

      K -> E
     / \
    G   B
   /|\ 
  H I J


Invalid tree (closed loop)
      A             
     / \ 
    B   C<----\
         \     |
          D   /
         / \ /
        E   F
             \
              G
             /|\
            H I J

[semihsalihoglu-uw]

Hi @pm-hwks: If you are inserting a single edge, say F -> C, before you insert the edge, you can check if C has a path to F. This would only work if you are inserting edges using CREATE/MERGE statements (so it would not work if you're doing bulk insertion).

So in python you can do something like this (suppose con is a Connection object):

con.execute("BEGIN TRANSACTION");
res = con.execute("MATCH (a:N)-[e:R*]->(b) WHERE a.id = 'C' AND b.id = 'F' RETURN count(*)");
if (res.getNextTuple()[0] > 0) {
   print("Adding F -> C edge creates cycle!")
   con.execute("ROLLBACK")
} else {
   con.execute("MATCH (a:N), (b:N) WHERE a.id = 'F' AND b.id ='C' CREATE (a)-[:R]->(b) RETURN *");
   con.execute("COMMIT")
}

I am assuming your nodes have type N and edges have type R. I am sure I'm making syntax errors and the code above probably won't run/compile but it should give you the general idea. You can also not use transactions and just write a single query with CASE WHEN THEN clauses that achieves the same.

[pm-hwks]

Unfortunately the system of records where these changes are made doesn't check for cyclic references. I am bulk loading the data into the graph for further analytics and applying scheduling algorithms. Is there any option to check for these cyclic reference after bulk loading the graph ?

[andyfengHKU]

I wanna add some of my thoughts here too.

A common way to detect cycles between two nodes is through the following statement

MATCH (a)-[e1]->(b), (b)-[e2]->(a)

The above statement only checks 1 level edge. if the cycle can be deep, you may change e1 and e2 to recursive relationship, i.e. [e1*<lowerBound>..<upperBound>]

Once a cycle is found, you can further decide if you wanna delete the forward or backward edge.

[pm-hwks]

there can be multiple levels of edges. We have bom tree's more 50 levels deep.