Databases
StackOverflow2013
Postsdbo
POOptimization on Algorithm to check "Whether for a given directed graph there is only one way to sort the graph using topological sort or not"
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POOptimization on Algorithm to check "Whether for a given directed graph there is only one way to sort the graph using topological sort or not"
    primarykey
    data
    text
    <p>My algorithm for this is :</p> <ol> <li>First to calculate Indegree of every node , i.e. count of how many edges are there for which this node is sink for them.</li> <li>Now, will push only those in queue which have indegree==0 because these will be the first to appear in topological sorted list of graph.</li> <li>If now starting size of Queue is zero. that means <strong>"Graph can't be sorted"</strong>.</li> <li>else we start Sorting method.</li> <li>If we encounter that more than 2 vertices are present in queue at any time that means that <strong>"Multiple sequences are possible"</strong></li> <li>But there may be a case where further Sequence might not be possible.</li> <li>So I keep track of the node that popped(deleted from Front) from Queue. and Count of them too.</li> <li><strong>If lastly count==number of nodes.and flag for multiple sequence is unset then sequence is possible "Graph can be sorted".</strong></li> <li><strong>or if count==number of nodes and flag for Mutiple sequence was set . we say "Multiple Sequence is Possible"</strong></li> <li><strong>if count!=number of nodes. then "Graph can't be sorted"</strong></li> </ol> <p>Here is My implementation of my Idea</p> <pre><code>vector&lt;vector&lt;int&gt; &gt;list(10000); // Graph is represented as Adjacency list void topological_sort() { int i,l,item,j; k=0; queue&lt;int&gt;q; // Queue vector&lt;int&gt;:: iterator it; for(i=1;i&lt;=n;i++) // Pushing nodes those who have indegree=0 { if(indegree[i]==0) q.push(i); } l=q.size(); if(l==0) { flag=2; // means no sequence is possible return; } while(q.empty()==0) { l=q.size(); if(l&gt;1) flag=1; // multiple sequence possible for sure but check whether this is fully possible or not item=q.front(); q.pop(); ans[k++]=item; for(it=list[item].begin();it!=list[item].end();it++) { j=*it; indegree[j]--; if(indegree[j]==0) q.push(j); } } if(k!=n) flag=2; // no sequence is possible. } </code></pre> <p>This algorithm is too slow! or just a naive implementation. What further Improvements are possible for this. or how can i use toplogical sort using DFS for this ?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USShashank Jain
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POOptimization on Algorithm to check "Whether for a given directed graph there is only one way to sort the graph using topological sort or not"
      1. USShashank Jain
      1. VTFavorite
    2. VO
      singulars
      1. POOptimization on Algorithm to check "Whether for a given directed graph there is only one way to sort the graph using topological sort or not"
      1. This table or related slice is empty.
      1. VTUpMod
    1. COSuggest this Q is more appropriate for [Code Review](http://codereview.stackexchange.com/).
      singulars
      1. POOptimization on Algorithm to check "Whether for a given directed graph there is only one way to sort the graph using topological sort or not"
      1. USBoBTFish
    2. COThanks ! posting it there ! much appreciated ! But i was hoping some help from here too !
      singulars
      1. POOptimization on Algorithm to check "Whether for a given directed graph there is only one way to sort the graph using topological sort or not"
      1. USShashank Jain
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload