1

I am looking at an edge and adjacent edges. Edge priority decreases with (1) Decrease of edge weight (2) Increase of the number of neighboring edges (3) Increase in total weight of shortest distinct adjacent edges.

I have my_table t

id in_node out_node weight   

  1  'A'      'B'    17
  2  'B'      'A'     4  
  3  'C'      'A'    35   
  4  'A'      'D'    26
  ... 
  5  'C'      'G'    33     
  6  'X'      'Z'    12  
  7  'Z'      'Y'    15    
  8  'X'      'Y'    42   
  9  'K'      'M'    66   
  ...
 10  'A'      'Z'    20  

Desired behavior

select id, in_count, in_weight, out_count,out_weight from t where  id = 10
  10      3          65          2        27            
         2,3,4      4+35+26     6,7      12+15            
   (1 is duplicate)                                                   

Steps to count number of distinct in_neighbors:

  • $A: select in_node from t where id = 10
  • @B: select id from t where in_node = $A or out_node = $A --select in neighbor ids (1,2,3,4,10)
  • @C: select in_node as that_node from t where id in (@B) -- ('A', 'B', 'C')      
       union all       
       select out_node as that_node from t where id in (@B)  --('A','B','Z','D')
  • (count distinct @C)  --5 now we can subtract two ('A' and 'Z' nods) to get the number of neighbors from in_node side

    To count in_weight we should select sum(weight) from t where id in (2,3,4). We shouldn't count weight for id=1 because

    select in_node from t where id = 1     
    union all      
    select out_node from t where id = 1      
    --'A','B'
    

    produces the same set as

    select in_node from t where id = 2      
    union all     
    select out_node from t where id = 2     
    --'A','B'
    

    while

    select weight from t where id = 2
    

    is smaller than

    select weight from t where id = 1
    

Is it possible to do this sort of selects from PL SQL or is it easier to just pass the result set to Java?

This table represents a graph. Vertices are in_node and out_node, id corresponds to the edge and weight corresponds to the weight of the edge. I want to find all neighbor edges along with their weights. If there are several edges connecting two vertices only the the lightest edge should be accounted for.

So, 'in_total' corresponds to the total sum of the weights of "distinct" neighbor edges. By distinct I mean lightest edge connecting two given vertices.

I am modelling maximum travel distance across a graph. Sometimes A-B route is reported several times. In this case I want to only pick one A-B route with the lightest weight.

Total weight of neighbors over the number of neighbors is a useful indicator of connectivity for my problem.

0

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.