Thread: sink detection algorithm

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

    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

    Code:
                 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 :

    Code:
    UNIVERSAL_SINK(A)
    
    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
    
    s<-0 
    
    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"
    Code:
    IS_SINK(A,k) 
    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
    Posts
    1,485
    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
    Location
    Athens , Greece
    Posts
    357
    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 Cprogramming.com
    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