PFDEP - Project File Dependencies

PFDEP - Project File Dependencies

#sorting

Project managers, such as the UNIX utility make, are used to maintain large software projects made up from many components. Users write a project file specifying which components (called tasks) depend on others and the project manager can automatically update the components in the correct order.

Problem

Write a program that reads a project file and outputs the order in which the tasks should be performed.

Input

For simplicity we represent each task by an integer number from  (where  is the total number of tasks). The first line of input specifies the number  of tasks and the number  of rules, such that .

The rest of the input consists of  rules, one in each line, specifying dependencies using the following syntax:

                ...    

This rule means that task number  depends on  tasks  (we say that task  is the target and  are dependents).

Note that tasks numbers are separated by single spaces and that rules end with a newline. Rules can appear in any order, but each task can appear as target only once.

Your program can assume that there are no circular dependencies in the rules, i.e. no task depends directly or indirectly on itself.

Output

The output should be a single line with the permutation of the tasks  to be performed, ordered by dependencies (i.e. no task should appear before others that it depends on).

To avoid ambiguity in the output, tasks that do not depend on each other should be ordered by their number (lower numbers first).

Example

Input:
5 4
3 2 1 5
2 2 5 3
4 1 3
5 1 1

Output:
1 5 3 2 4

--------------------------------------------EDITORIAL-----------------------------------------------

QUEUE IMPLEMENTATION OF TOPOLOGICAL SORT WILL BE  EASY TO USE IN THIS PROBLEM

#include<bits/stdc++.h>
using namespace std;
vector<int>li[1000000];
int vis[1000000];
vector<int> ans;
int   n,m;
int deg[1000000];
struct compare
{
    bool operator() (const int& l, const int& r)
    {
        return l>r;
    }
};

int toposort()
 {
   priority_queue<int, vector<int>, compare > q;
      for(int i=1;i<=n;i++)
           {
             if(deg[i]==0)
               {
                   q.push(i);
                   //ans.push_back(i);
              }
                  }
                  
                  while(!q.empty())
                  {
                   int node=q.top();
                   ans.push_back(node);
                   q.pop();
                    vis[node]=1;
                      vector<int>:: iterator it;
                      for(it=li[node].begin();it!=li[node].end();it++)
                        {
                            if(deg[*it]!=0)
                            {
                             deg[*it]--;
                             if(deg[*it]==0)
                                  {
                                    //cout<<" push "<<*it<<endl;
                                  // ans.push_back(*it);
                                   q.push(*it);
           }
         }
       }
                      
      }
  
 }
 
 
int main()
{

 cin>>n>>m;
 for(int i=0;i<m;i++)
 {
  int st,k;
  cin>>st>>k;
  for(int j=0;j<k;j++)
  {
   int a;
    cin>>a;
   li[a].push_back(st);
   deg[st]++;
  }
  
  }
  
    toposort();
    for(int i=0;i<n;i++) cout<<ans[i]<<" ";
   
}

queue implementation of toposort

#include<bits/stdc++.h>
using namespace std;
vector<int>li[1000000];
int vis[1000000];
vector<int> ans;
int   n,m;
int deg[1000000];


int toposort()
 {
  queue<int> q ;
      for(int i=1;i<=n;i++)
           {
           if(deg[i]==0)
             {
               q.push(i);
           }
                  }
                 
                  while(!q.empty())
                  {
                  int node=q.front();
                  ans.push_back(node);
                  q.pop();
                  vis[node]=1;
                    vector<int>:: iterator it;
                    for(it=li[node].begin();it!=li[node].end();it++)
                      {
                        if(deg[*it]!=0)
                        {
                        deg[*it]--;
                        if(deg[*it]==0)
                            {
                            q.push(*it);
 }
 }
}
                   
 }
 
 }


int main()
{

 cin>>n>>m;
 for(int i=0;i<m;i++)
 {
  int a,b;
  cin>>a>>b;
  li[a].push_back(b);
  }
 
    toposort();
    for(int i=0;i<n;i++) cout<<ans[i]<<" ";
 
}

stack implementation

#include<bits/stdc++.h>
using namespace std;
vector<int>li[1000000];
int vis[1000000];
vector<int> ans;
int toposort(int start,stack<int> &s,int vis[])
 {
  vector<int>:: iterator it;
  for(it=li[start].begin();it!=li[start].end();it++)
  {
  if(!vis[*it])
  {
 
   vis[*it]=1;
   toposort(*it,s,vis);
}
}

s.push(start);
 
 }


int main()
{
int   n,m;
 cin>>n>>m;
 for(int i=0;i<m;i++)
 {
  int a,b;
  cin>>a>>b;
  li[a].push_back(b);
  }
 
  stack<int> s;
  for(int i=1;i<=n;i++)
  {
  if(!vis[i])
    {
    vis[i]=1;
     toposort(i,s,vis);
  }
  }
  while(!s.empty())
   {
    ans.push_back(s.top());
    s.pop();
   }
   for(int i=n-1;i>=0;i--) cout<<ans[i]<<" ";
 
}

toposort using queue theory

Define the indegree of a vertex as the number of edges pointing to it.

• A node of indegree 0 can be placed at the start of the sorted order, since there is clearly nothing that must precede it.
• There must be at least one vertex of indegree 0.
  
  • If not, the graph has a cycle and no topological sort exists.
• Once we have placed all nodes of indegree 0 in the list, we can then add all nodes whose indegree would be zero except for edges from the nodes already placed.

Repeating this process yields a topological sort.

// A topological sort of a directed graph is any listing of the vertices
// in g such that v1 precedes v2 in the listing only if there exists no
// path from v2 to v1.
//
// The following routine attempts a topological sort of g. If the sort is
// successful, the return value is true and the ordered listing of
// vertices is placed in sorted.  If no topological sort is possible
// (because the graph contains a cycle), false is returned and sorted will
// be empty.
//
bool topologicalSort (const DiGraph& g, list<Vertex>& sorted)
{
  // Step 1: get the indegrees of all vertices. Place vertices with
  // indegree 0 into a queue.
  hash_map<Vertex, unsigned, VertexHash> inDegree;
  queue<list<Vertex> > q;
  for (AllVertices v = g.vbegin(); v != g.vend(); ++v)
    {
      unsigned indeg = g.indegree(*v);
      inDegree[*v] = indeg;
      if (indeg == 0) 
        q.push(*v);  
    }

  // Step 2. Take vertices from the q, one at a time, and add to sorted.
  // As we do, pretend that we have deleted these vertices from the graph,
  // decreasing the indegree of all adjacent nodes. If any nodes attain an
  // indegree of 0 because of this, add them to the queue.
  while (!q.empty())
    {
      Vertex v = q.front();
      q.pop();

      sorted.push_back(v);

      for (AllOutgoingEdges e = g.outbegin(v); e != g.outend(v); ++e)
        {
          Vertex adjacent = (*e).dest();
          inDegree[adjacent] = inDegree[adjacent] - 1; 
          if (inDegree[adjacent] == 0)
            q.push (adjacent);        
        }
    }
  
  // Step 3:  Did we finish the entire graph?
  if (sorted.size() == g.numVertices())
    return true; 
  else
    {
      sorted.clear();
      return false;
    }
}

Here is the code for a topological sort.
Let's consider it a step at a time.

bool topologicalSort (const DiGraph& g, list<Vertex>& sorted)
{
  // Step 1: get the indegrees of all vertices. Place vertices with
  // indegree 0 into a queue.
  hash_map<Vertex, unsigned, VertexHash> inDegree;
  queue<list<Vertex> > q;
  for (AllVertices v = g.vbegin(); v != g.vend(); ++v)
    {
      unsigned indeg = g.indegree(*v);
      inDegree[*v] = indeg;
      if (indeg == 0) 
        q.push(*v);  
    }

In step 1, we get the indegrees of all the vertices, putting them into a map whose key type is Vertex and whose associated data isunsigned. I've chosen to use a hash_map for this code. hash_map is a hash-table implementation of the standard map interface.hash_map isn't actually part of the standard library, but it is a commonly available addition. If I wanted to stay entirely within the standard library, I could just use map, but at the cost of somewhat slower access. Alternatively, I could (and have, in the past) implemented a vector-based implementation of the map interface that simply uses the Vertex::id() function to index into the vector, which would give me true O(1) access time.
As we do this, we also add any vertices whose indegree is zero into a queue, q.

// Step 2. Take vertices from the q, one at a time, and add to sorted.
  // As we do, pretend that we have deleted these vertices from the graph,
  // decreasing the indegree of all adjacent nodes. If any nodes attain an
  // indegree of 0 because of this, add them to the queue.
  while (!q.empty())
    {
      Vertex v = q.front();
      q.pop();

      sorted.push_back(v);

      for (AllOutgoingEdges e = g.outbegin(v); e != g.outend(v); ++e)
        {
          Vertex adjacent = (*e).dest();
          inDegree[adjacent] = inDegree[adjacent] - 1; 
          if (inDegree[adjacent] == 0)
            q.push (adjacent);        
        }
    }

In step 2, we repeatedly remove vertices from the queue and add them to the sorted list output, sorted. We can do this because we know that there is nothing in the graph that needs to come before these vertices.
We then look at the outgoing edges of each vertex, and reduce the inDegree values of the neighboring vertices to simulate having removed v from the graph. If doing this causes any of their (simulated) indegrees to become zero, we add them to the queue, because we know that there is nothing remaining in the graph that needs to come before these vertices.

// Step 3:  Did we finish the entire graph?
  if (sorted.size() == g.numVertices())
    return true; 
  else
    {
      sorted.clear();
      return false;
    }
}

Finally, in step 3, we check to see if all the vertices have been “removed” from the graph and placed into the sorted list. If so, we have successfully found a topological sort. If not, then no topological sort is possible (the graph must have a cycle).
Try running a topological sort.

Analysis

bool topologicalSort (const DiGraph& g, list<Vertex>& sorted)
{
  // Step 1: get the indegrees of all vertices. Place vertices with
  // indegree 0 into a queue.
  hash_map<Vertex, unsigned, VertexHash> inDegree;
  queue<list<Vertex> > q;
  for (AllVertices v = g.vbegin(); v != g.vend(); ++v)
    {
      unsigned indeg = g.indegree(*v);  // O(1)
      inDegree[*v] = indeg;             // O(1) 
      if (indeg == 0)                   // O(1) = O(1) 
        q.push(*v);                     // O(1) 
    }
    ⋮

In analyzing this algorithm, we will assume that the graph is implementing using adjacency lists, and that the inDegree map is implemented using a vector-like structure.
In step 1, therefore, we see that everything in the loop body is O(1). The loop itself goes around once for every vertex in the graph. Following our definition that says that a graph G=(V,E) is a set V of vertices and a set E of edges, we can say that the number of iterations of this loop is |V|, the number of vertices.

bool topologicalSort (const DiGraph& g, list<Vertex>& sorted)
{
  // Step 1: get the indegrees of all vertices. Place vertices with
  // indegree 0 into a queue.
  hash_map<Vertex, unsigned, VertexHash> inDegree;
  queue<list<Vertex> > q;
  for (AllVertices v = g.vbegin(); v != g.vend(); ++v) // O(1) |V|*
    {
      unsigned indeg = g.indegree(*v);  // O(1)
      inDegree[*v] = indeg;             // O(1)
      if (indeg == 0)                   // O(1) = O(1)
        q.push(*v);                     // O(1)
    }
    <[:]>

We therefore conclude that the entire step 1 loop is O(|V|).
(We could also write this as O(g.numVertices()), but |V| is shorter and is the usual way that people describe graphs.)

bool topologicalSort (const DiGraph& g, list<Vertex>& sorted)
{
  O(|V|)

  // Step 2. Take vertices from the q, one at a time, and add to sorted.
  // As we do, pretend that we have deleted these vertices from the graph,
  // decreasing the indegree of all adjacent nodes. If any nodes attain an
  // indegree of 0 because of this, add them to the queue.
  while (!q.empty())
    {
      Vertex v = q.front();
      q.pop();

      sorted.push_back(v);

      for (AllOutgoingEdges e = g.outbegin(v); e != g.outend(v); ++e)
        {
          Vertex adjacent = (*e).dest();
          inDegree[adjacent] = inDegree[adjacent] - 1; 
          if (inDegree[adjacent] == 0)
            q.push (adjacent);        
        }
    }
    ⋮  

Looking at the inner loop of step 2, we see that everything in the body is O(1).

bool topologicalSort (const DiGraph& g, list<Vertex>& sorted)
{
  O(|V|)

  // Step 2. Take vertices from the q, one at a time, and add to sorted.
  // As we do, pretend that we have deleted these vertices from the graph,
  // decreasing the indegree of all adjacent nodes. If any nodes attain an
  // indegree of 0 because of this, add them to the queue.
  while (!q.empty())
    {
      Vertex v = q.front();  // O(1)
      q.pop();               // O(1)

      sorted.push_back(v);   // O(1)

      for (AllOutgoingEdges e = g.outbegin(v); e != g.outend(v); ++e)  // O(1)
        {
          O(1)
        }
    }
    ⋮
}

And the simple statements in the outer loop (everything except for the inner loop) are O(1).

bool topologicalSort (const DiGraph& g, list<Vertex>& sorted)
{
  O(|V|)

  while (!q.empty())
    {
      O(1)
      for (AllOutgoingEdges e = g.outbegin(v); e != g.outend(v); ++e)  // O(1)
        {
          O(1)
        }
    }
   ⋮  

Now, at this point our normal copy-and-paste approach breaks down. The number of iterations of the inner loop may be different for each vertex visited by the outer loop.
But, let's just stop and think about what's going on here.

• Each vertex goes into the queue at most once
• So, in a successful sort, the outer loop will execute |V| times, once for each vertex.
• The inner loop simply visits the edges emanating from the vertex being visited by the outer loop.
• So if the outer loop visits every vertex, and the inner one visits every edge leaving that vertex, over the course of all the outer loop iterations, the inner loop will visit every edge in the graph exactly once.

So the statements in the body of the inner loop get executed |E| times; the other statements in the outer loop get visited |V| times. Since all of these statements are O(1), the total cost is O(|V|+|E|).

bool topologicalSort (const DiGraph& g, list<Vertex>& sorted)
{
  O(|V|)
  O(|V| + |E|)
  
  // Step 3:  Did we finish the entire graph?
  if (sorted.size() == g.numVertices())
    return true;      // O(1)
  else
    {
      sorted.clear(); // O(|V|)
      return false;   // O(1)
    }
}

In step 3, the only non-trivial operations is clearing the sorted list (done when we can't find a solution). Since this list is actually a list of vertices that we have successfully sorted, it contains at most |V| elements, and so the clear operation is O(|V|).
That makes the worst case for the step 3 “if” statement O(|V|) as well.

bool topologicalSort (const DiGraph& g, list<Vertex>& sorted)
{
  O(|V|)
  O(|V| + |E|)
  O(|V|)  
}

So the total cost of the topological sort is O(|V| + |E|)
(Note: this does not mean that topological sorts are faster than conventional sorts --- the number of edges can be as high as |V|², so this is actually more comparable to the slowest of our conventional sorting algorithms. That's the penalty we pay for working with partial orders. We don't write the cost of this algorithm as O(|V|²), though, because the number of edges varies widely in practical problems, and we may sometimes know that |E| will be far less than that maximum, so O(|V| + |E|) is a more accurate portrayal of the behavior.

THEORY

Topological Sorting

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

For example, a topological sorting of the following graph is “5 4 2 3 1 0″. There can be more than one topological sorting for a graph. For example, another topological sorting of the following graph is “4 5 2 3 1 0″. The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no in-coming edges).

Topological Sorting vs Depth First Traversal (DFS):
In DFS, we print a vertex and then recursively call DFS for its adjacent vertices. In topological sorting, we need to print a vertex before its adjacent vertices. For example, in the given graph, the vertex ‘5’ should be printed before vertex ‘0’, but unlike DFS, the vertex ‘4’ should also be printed before vertex ‘0’. So Topological sorting is different from DFS. For example, a DFS of the above graph is “5 2 3 1 0 4″, but it is not a topological sorting

Algorithm to find Topological Sorting:
We recommend to first see implementation of DFS here. We can modify DFS to find Topological Sorting of a graph. In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.

Following are C++ and Java implementations of topological sorting. Please see the code for Depth First Traversal for a disconnected Graph and note the differences between the second code given there and the below code.

• C++
• Java

// A C++ program to print topological sorting of a DAG
#include<iostream>
#include <list>
#include <stack>
using namespace std;

// Class to represent a graph
class Graph
{
    int V;    // No. of vertices'

    // Pointer to an array containing adjacency listsList
    list<int> *adj;

    // A function used by topologicalSort
    void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
public:
    Graph(int V);   // Constructor

     // function to add an edge to graph
    void addEdge(int v, int w);

    // prints a Topological Sort of the complete graph
    void topologicalSort();
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}

// A recursive function used by topologicalSort
void Graph::topologicalSortUtil(int v, bool visited[], 
                                stack<int> &Stack)
{
    // Mark the current node as visited.
    visited[v] = true;

    // Recur for all the vertices adjacent to this vertex
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            topologicalSortUtil(*i, visited, Stack);

    // Push current vertex to stack which stores result
    Stack.push(v);
}

// The function to do Topological Sort. It uses recursive 
// topologicalSortUtil()
void Graph::topologicalSort()
{
    stack<int> Stack;

    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // Call the recursive helper function to store Topological
    // Sort starting from all vertices one by one
    for (int i = 0; i < V; i++)
      if (visited[i] == false)
        topologicalSortUtil(i, visited, Stack);

    // Print contents of stack
    while (Stack.empty() == false)
    {
        cout << Stack.top() << " ";
        Stack.pop();
    }
}

// Driver program to test above functions
int main()
{
    // Create a graph given in the above diagram
    Graph g(6);
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);

    cout << "Following is a Topological Sort of the given graph \n";
    g.topologicalSort();

    return 0;
}

Output:

Following is a Topological Sort of the given graph
5 4 2 3 1 0

Time Complexity: The above algorithm is simply DFS with an extra stack. So time complexity is same as DFS which is O(V+E).

Applications:
Topological Sorting is mainly used for scheduling jobs from the given dependencies among jobs. In computer science, applications of this type arise in instruction scheduling, ordering of formula cell evaluation when recomputing formula values in spreadsheets, logic synthesis, determining the order of compilation tasks to perform in makefiles, data serialization, and resolving symbol dependencies in linkers [2].

References:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/topoSort.htm
http://en.wikipedia.org/wiki/Topological_sorting

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above