Dgraph - Schema for University PhD Students and Research Projects

Aim

Create Dgraph schema for managing university PhD students and their research projects. Click here to view complete problem statement.

Graph

Schema

mutation{
  schema{
    type: string @index .
    
    ssn: string @index .
    name: string @index .
    dob: date @index .
    rank: int @index .
    researchSpeciality: string @index .
    
    projectNumber: string @index .
    startDate: date @index .
    endDate: date @index .
    budget: float @index .
    
    degreeProgram: string @index .
    
    deptNumber: string @index .
    officeAddress: string .
    
    startTime: date @index .
    endTime: date @index .
    
    principal_investigator: uid @reverse .
    co_investigator: uid @reverse .
    supervisor: uid @reverse .
    sponsor: uid @reverse .
    research_assistant: uid @reverse .
    
    student_advisor: uid @reverse .
    major_department: uid @reverse .
    
    chairman: uid @reverse .
    
    has_department: uid @reverse .
    has_professor: uid @reverse .
  }
}

*** END ***

Dgraph - Schema for Music Company

Aim

Create a dgraph schema for a Music Company. Click here to view complete problem statement. 

Graph

Schema

mutation{
  schema{
    type: string @index .
    
    name: string @index .
    ssn: string .
    
    title: string @index .
    copyrightDate: date @index .
    format: string @index .
    albumIdentifier: string @index .
    
    addressLine: string .
    city: string @index .
    telephoneNumber: string .
    
    musicalKey: string .
    
    recorded_at: uid @reverse .
    produced_by: uid @reverse .
    
    belongs_to: uid @reverse .
    uses: uid @reverse .
    writer: uid @reverse .
    performer: uid @reverse .
    
    plays: uid @reverse .
    stays: uid @reverse .
  }
}

*** END ***

Dijkstra Algorithm Program

import java.io.*;

class DijDemo 
{
 public static void main(String[] args) 
 {
  try
  {
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   System.out.print("Enter number of nodes: - ");
      Dijkstra obj = new Dijkstra(Integer.parseInt(br.readLine()));  
   obj.Start(); 
  }
  catch (Exception e)
  {
   e.printStackTrace();
  }
  
 }
}

class Dijkstra
{
 private String[] name; //to store names of the vertex
 private int[][] matrix; //to store values of the connections
 private Vertex[] v; //to keep tag values of each vertex

 BufferedReader br;

 Dijkstra(int n)
 {
  name = new String[n];
  matrix = new int[n][n]; 
  v = new Vertex[n];

  try
  {
   br = new BufferedReader(new InputStreamReader(System.in));
  }
  catch(Exception e)
  {
   e.printStackTrace();
  }
 }


 private void initialize() //set the intial tag for each vertex
 {
  for(int i=0; i<v.length; i++)
  {
   v[i] = new Vertex();
   v[i].dist = -1;
   v[i].prev_index = -1;
   v[i].permanent = false;
  }
 }

 private String getName(int index) //of the vertex at a particular index
 {
  return name[index]; 
 }

 private int getIndex(String nm) //of the vertext
 {
  for(int i=0; i<name.length; i++)
   if(name[i].equals(nm))
    return i;
  return -1;
 }

 private void setNames() //of the vertices
 {
  try
  {
   for(int i=0; i<name.length; i++) 
    name[i] = br.readLine();
  }
  catch(Exception e)
  {
   e.printStackTrace();
  }
 }

 private int getStart() //accept the start vertex for the graph
 {
  try
  {
   return getIndex(br.readLine());
  }
  catch(Exception e)
  {
   e.printStackTrace();
  }

  return -1;
 } 

 private void setEdgeDetails() //get connection details
 {
  for(int i=0; i<matrix.length; i++)
  {

   System.out.println("== "  + getName(i) + " ==");

   for(int j=i; j<matrix[i].length; j++)
   {

    if(i==j)
    {
     matrix[i][j] = 0;
     continue;
    }


    try
    {
     System.out.print(getName(j) + ": ");
     matrix[j][i] = matrix[i][j] = Integer.parseInt(br.readLine());
    }
    catch(Exception e)
    {
     e.printStackTrace();
    } 
   }
  }
 }
 
 
 private void dijkstra(int cvx)
 {
  Vertex cur = v[cvx];
  cur.dist=0;
  cur.permanent = true;
  cur.prev_index=-1; 

  

  while(true)
  {
   int[] vertexRow = matrix[cvx];

   System.out.println("For parent node " + getName(cvx));

   for(int j=0; j<vertexRow.length; j++)
   {
    if(vertexRow[j] > 0)
    {
     int newDistance = (cur.dist+vertexRow[j]);
     setTag(j, cvx, newDistance);
    }
   }

   cvx = findNonPermanentVertexWithMinimumDist();

   if(cvx==-1)
    break;

   v[cvx].permanent = true;

   cur = v[cvx];
  }
 }

 private void setTag(int current_vertex, int parent_vertex, int distance)
 {
  Vertex cur = v[current_vertex];

  if(cur.permanent!=true)
  {
   if(cur.dist!=-1 && cur.dist!=0)
   {
     if (cur.dist>distance)
     {
     cur.prev_index = parent_vertex;
     cur.dist = distance;
     }
   }
   else
   {
     cur.prev_index = parent_vertex;
     cur.dist = distance;
   }
   
  }
 }

 private int findNonPermanentVertexWithMinimumDist()
 {  
  int minDist=-1;
  int minIndex=-1;
  int i=0;

  for(; i<v.length; i++)
  {
   if(v[i].permanent==false)
   {
    if(v[i].dist!=-1)
    {
     if(minIndex==-1)  //if the first node encountered then
     {
      minDist=v[i].dist;
      minIndex=i;
     }
     else
     {
      if(v[i].dist<minDist)
      {
       minDist=v[i].dist;
       minIndex=i; 
      }
     }
    }
   }
  }
  
  return minIndex;
 }

 private void showVertexDetails(int i) //vertex details
 {
   System.out.println("Vertex: " + getName(i));
   System.out.println("Distance= " + v[i].dist);
   if(v[i].prev_index!=-1)
   System.out.println("Previous= " + name[v[i].prev_index]);
   System.out.println("Permanent= " + v[i].permanent);
  
 }

 public void Start()
 {
  System.out.println("Enter names of vertices: ");
  setNames();

  System.out.println("Enter wt. for each edge. if edge does not exists (-1)");
  setEdgeDetails();

  initialize();

  System.out.print("Enter name of start vertex - ");

  dijkstra(getStart());

  for(int i=0; i<name.length; i++)
   System.out.println(traversePath(i) + ": " + v[i].dist);

 }

 private String traversePath(int vx)
 {
  StringBuffer path = new StringBuffer(getName(vx) + " - ");

  int prev = v[vx].prev_index;

  while(prev!=-1)
  {
   path.append(getName(prev) + " - ");
   prev=v[prev].prev_index;   
  }

  return path.reverse().toString().substring(2);
 }

}


class Vertex //tag structure
{
 int dist;
 int prev_index;
 boolean permanent;
}

---

Undirected Graph on which Dijkstra Algorithm worked to find the shortest path for each node.

Result of the Dijkstra Algorithm

Dijkstra Algorithm

Consider each node with a tag associated as (flag, previous, distance); where flag is true if the node is made permanent else false, previous indicates the name of the previous node and distance is the distance of the current node from the start node.

Algorithm 1 (To set the traversal path and find minimum distance)

1. Set  the tags of all the nodes as (F, -, infinity) i.e.
   F -> permanent false
   (dash - ) -> No previous node and
   distance is infinity
2. Accept the start node and set the tag for the start node as (T, -, 0) i.e.
   permanent
   No previous node and
   distance is 0
3. Set the tags of all reachable nodes from start node; previous node is start node and distance from the start node
4. Find  a node with minimum distance and permanent = false; Note: don’t compare with nodes having distance infinity
5. If no such node exists then go to step 9
6. Mark this node permanent i.e. set the permanent flag true
7. Find all reachable nodes from this node
   Dist = this.distance + distance of reachable node from this node
   If distance of the new node is infinity then
   Set the distance = Dist
   Set the previous node = this
   Else
   If (reachable.distance>Dist) then
   Set the distance = Dist
   Set the previous node = this
   End If
   End If
8. Go to Step 4
9. Print traversal path and distance of each node from start node
10. Stop

Algorithm 2 (Print traversal path and distance of each node from start node)

1. Take a node from the tree
2. Print the distance value from tag
3. Print current nod name
4. If distance=0 then go to step 7
5. Current = Current.previous
6. Go to step 3
7. Take next node
8. If node exists then go to step 2
9. Stop