Hacky way to find distance (number of hops) from one node to other nodes

Users Dgraph
,
1

Schema:

		name: string @index(exact) .
		age: int .
		city: string .
		knows: [uid] .

I Want to Do

Find friends (connected via knows) up to three hops away and also return the distance in the query. Example: Anurag -> Manish -> Pawan and I wish to find friends which are at most two hops away, I want result:

{
     Manish
     dist: 1
},
{
     Pawan
     dist: 2
}

What I Did

q1(func: eq(name, $ID)){	
		v1 as knows{
			dist1 as math(1)
			v2 as knows{
				dist2 as math(2)
				v3 as knows{
					dist3 as math(3)
				}
			}
		}
	}
	q(func: uid(v1,v2,v3)){
		distance1: val(dist1)
		distance2: val(dist2)
		distance3: val(dist3)
		name
		city
		age
	}

Why isn’t it great

  1. I have to define different variables (dist1, dist2, dist3) at each level.
  2. In case there are multiple ways to reach a node the output would have both distances.
    Example:
   "q": [
      {
         "distance1": 1,
         "name": "Manish",
         "city": "SF",
         "age": 35
      },
      {
         "distance1": 1,
         "name": "Chetan",
         "city": "Udaipur",
         "age": 35
      },
      {
         "distance2": 2,
         "name": "Pawan",
         "age": 45
      },
      {
         "distance2": 2,
         "distance3": 3,
         "name": "Ashish",
         "city": "Varanasi",
         "age": 35
      }
   ]

Data

{
  set {
		_:n1 <name> "Anurag" .
		_:n1 <age> "25" .
		_:n1 <city> "Delhi" .
		_:n1 <knows> _:n2 .
		_:n1 <knows> _:n5 .
		_:n2 <name> "Manish" .
		_:n2 <age> "35" .
		_:n2 <city> "SF" .
		_:n2 <knows> _:n3 .
		_:n3 <name> "Pawan" .
		_:n3 <age> "45" .
		_:n3 <knows> _:n4 .
		_:n4 <name> "Ashish" .
		_:n4 <age> "35" .
		_:n4 <city> "Varanasi" .
		_:n5 <name> "Chetan" .
		_:n5 <age> "35" .
		_:n5 <city> "Udaipur" .
		_:n5 <knows> _:n4 .
  }
}
1 Like
2

Following that query, I think if we had loops this would be much more precise.
Bellow an idea of a loop generating a shortest path on each person found. And the _weight_ tells us the distance automatically.

Feature: Add foreach() function

{
   var(func: eq(name, "Anurag")) @recurse(depth: 3){
    all as uid
    knows
   }
	targets as var(func: uid(all)){
		name
		city
		age
	}

 q(func: foreach(in: targets, title: name)) {
  A as var(func: eq(name, "Anurag"))
  M as var(func: eq(name, this.name))

   path as shortest(from: uid(A), to: uid(M), numpaths: 2) {
    knows
   }
   path(func: uid(path)) {
     name
   }
 }

}

Result

{
   "data": {
      "q": [
         {
            "name": "Manish",
            "city": "SF",
            "age": "35",
            "path": [
               {
                  "name": "Anurag"
               },
               {
                  "name": "Manish"
               }
            ],
            "_path_": [
               {
                  "knows": {
                     "uid": "0x84"
                  },
                  "uid": "0x83",
                  "_weight_": 1
               }
            ]
         },
         {
            "name": "Chetan",
            "city": "Udaipur",
            "age": "35",
            "path": [
               {
                  "name": "Anurag"
               },
               {
                  "name": "Chetan"
               }
            ],
            "_path_": [
               {
                  "knows": {
                     "uid": "0x85"
                  },
                  "uid": "0x83",
                  "_weight_": 1
               }
            ]
         },
         {
            "name": "Pawan",
            "age": "45",
            "path": [
               {
                  "name": "Anurag"
               },
               {
                  "name": "Manish"
               },
               {
                  "name": "Pawan"
               }
            ],
            "_path_": [
               {
                  "knows": {
                     "knows": {
                        "uid": "0x86"
                     },
                     "uid": "0x84"
                  },
                  "uid": "0x83",
                  "_weight_": 2
               }
            ]
         },
         {
            "name": "Ashish",
            "city": "Varanasi",
            "age": "35",
            "path": [
               {
                  "name": "Anurag"
               },
               {
                  "name": "Chetan"
               },
               {
                  "name": "Ashish"
               }
            ],
            "_path_": [
               {
                  "knows": {
                     "knows": {
                        "uid": "0x87"
                     },
                     "uid": "0x85"
                  },
                  "uid": "0x83",
                  "_weight_": 2
               },
               {
                  "knows": {
                     "knows": {
                        "knows": {
                           "uid": "0x87"
                        },
                        "uid": "0x86"
                     },
                     "uid": "0x84"
                  },
                  "uid": "0x83",
                  "_weight_": 3
               }
            ]
         }
      ]
   }
}