How to skip nodes in dgraph traversal when nodes is traversed already(BFS)

Users Dgraph
1

I have nodes as below
image

So a recursive query from FRE99 will lead me to Alarm twice, both the times thru TPE. How can i remove Alarm from my query output the second time(since TPE has already been visited thru FRE1)?
In simple terms, when the traversal begun it traversed FRE99->FRE1->TPE->Alarm, then while traversing the other path, FRE99->FRE2->TPE, it should stop traversing further here, since TPE has already been visited now… So how can that be achieved?

2

Hi @onkarbanerjee, Here is an approach.

  • Schema
<hasC>: [uid] @reverse .
<name>: string @index(term) .

Data to reflect the diagram you shared is as below.

{
  set{
    _:fre99 <name> "FRE99" .
    _:fre99 <hasC> _:fre1 .
    _:fre99 <hasC> _:fre2 .
    
    _:fre1 <hasC> _:tpe .
    _:fre1 <name> "fre1" .
    
    _:fre2 <hasC> _:tpe .
    _:fre2 <name> "fre2" .
    
    _:tpe <hasC> _:alarm .
    _:tpe <name> "tpe" .    
    
    _:alarm <name> "Alarm" .
    
  }
}

Here is the query that begins from “FRE99” and lands a single alarm.

{
  topfre as var(func: allofterms(name,"FRE99") ){
    name
    hasC{

      name
      tpe as hasC{

        name
				hasC{
          name
        }        
      }
    }
  }
  
  getAlarm(func: uid(tpe)){
    name
    tpe: hasC{
      name
    }
    intermediateStep:~hasC{
      name
      origin:~hasC @filter(uid(topfre)){
        name
      }
    }
    
  }
}

… resulting in the output.

"data": {
    "getAlarm": [
      {
        "name": "tpe",
        "tpe": [
          {
            "name": "Alarm"
          }
        ],
        "intermediateStep": [
          {
            "name": "fre2",
            "origin": [
              {
                "name": "FRE99"
              }
            ]
          },
          {
            "name": "fre1",
            "origin": [
              {
                "name": "FRE99"
              }
            ]
          }
        ]
      }
    ]
  }
3

What if we need a recursive query here… The data i have shown is a sample, in reality, there are 1 million nodes and there will be recursive traversals of varying depths possible. Also, the query you have shown requires knowledge of the existing nodes before hand. What i really need here is how to skip a visited node(and thereby not traverse through it anymore) while doing a recursive query.

For example, if TPE has been explored already(and we got Alarm that way), we do not traverse it again ever throughout that same recursive query. Is that possible?

Till now from what i have seen and worked with, this doesn’t seem possible in dgraph yet.

When there are many nodes in dgraph, this property of dgraph where it keeps traversing some nodes and their consequent paths in recursive query again and again is a serious hit to the scalibility. In my case, we tested with 100k nodes and some recursive queries were taking as much as 6 mins even and some are even failing to complete. We are looking for dgraph to be used in our case where we expect 1 million nodes and wanted to test for upto 10 million even. But the scalibility is under serious consideration for us here. Unless, i am missing something…

5

The ask certainly makes sense to me. From what I can gather, the Dgraph Query language does not have a query construct that deals with the traversal you are looking for.

6

hey @onkarbanerjee, is this a GraphQL question or Dgraph? Feels like Dgraph, but you have posted ate users/graphql.

7

True, my bad!! I should have known better