Thread: sink detection algorithm

  1. #1
    Registered User
    Join Date
    Sep 2011
    Athens , Greece

    sink detection algorithm

    Hello to all.... I have an exercise that I want to do .... I am trying but I face some difficulties... I have found the algorithm..... I know the nature of the problem but I can't describe completely the work of the algorithm ...

    A sink is a node without outcoming edges .... and I found an algorithm that it finds a sink. For example all are starting by a adjacency matrix for example

                 V1     V2     V3    V4    V5
     V1       0         1        1      1      1
     V2      0         0         0      1       1
     V3      0          1        0       1       1
     V4      0          0        0        0      1
     V5      0          0         0       0       0
    Wherever we have an '1' there is a connection in the graph for example V1 (Vertex1) does not connected with its self

    V2 does not connected with V3 but with V4 and V5.

    The sink here is the Vertex V5 , in order to determine the sink we should find the vertex that it has a row with only zeros and a column with only ones .....

    The algorithm is :

    let A be |V| X |V|   (|V| number of vertex)
    i <- j <- 1
    while i <= |V| and j<= |V|
    do if aij =1
    then i <- i+1
    else j<- j+1
    if i > |V|
    then return "there is no universal sink"
    elseif IS_SINK (A,i) = FALSE
    then return "there is no universal sink"
    else return i "is a universal sink"
    let A be |V| X |V|
    for j<- 1 to |V|
    do if akj =1   //Check for 1 in row k
    then return FALSE
    for i<-1 to |V|
    do if aik =0 and i!=k   //Check for 0 in column k
    then return FALSE
    return TRUE
    where i and j are incremented above???? Is there anyone who can trace this algorithm??? the complexity here is O(n^2) ?

    Thank you in advance
    Last edited by Mr.Lnx; 03-25-2013 at 03:58 PM.

  2. #2
    Registered User
    Join Date
    Jan 2009
    Since this is a digraph couldn't you do a topological sort on it? The nodes without any incoming edges should appear in either end, depending on sort order afaik.

  3. #3
    Registered User
    Join Date
    Sep 2011
    Athens , Greece
    Do you want to give you the figure ????

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Client Server sensor - sink
    By Nemerniku in forum Networking/Device Communication
    Replies: 0
    Last Post: 06-18-2009, 08:49 AM
  2. Breakout Collision Detection Algorithm Help
    By xmltorrent in forum Game Programming
    Replies: 8
    Last Post: 08-24-2006, 02:32 PM
  3. Entropy Sink down?
    By face_master in forum A Brief History of
    Replies: 7
    Last Post: 04-08-2005, 06:41 AM
  4. duplicate detection algorithm
    By Gustaff in forum C Programming
    Replies: 4
    Last Post: 01-28-2003, 12:26 PM
  5. Collision detection algorithm
    By Hannwaas in forum Game Programming
    Replies: 5
    Last Post: 11-30-2001, 01:27 PM