search

pysal / libpysal

Core components of Python Spatial Analysis Library
http://pysal.org/libpysal
Other
259 stars 78 forks source link

W.id2i misses nodes with zero outdegree #322

Open ljwolf opened 4 years ago

ljwolf commented 4 years ago

The id2i dictionary ignores any nodes with zero outdegree. For example, 

neighbors = {0: [1], 1:[2,3], 2:[3]}
test = weights.W(neighbors, silence_warnings=True) 
# otherwise construction fails because the sparse constructor correctly tries to include *every* observation.
test.id2i

I think the proper fix for this is:

  1. find the set of all ids (so, the set of neighbors.keys() unioned with all the neighbors.values)
  2. find set(all_labels).difference(set(neighbors.keys()), and call that out_islands
  3. for every out-island in out_islands, add it to neighbors with an empty list as its value.

This should happen at construction.

jGaboardi commented 4 years ago 
In [1]: from libpysal import weights                                                                                                                   
In [2]: neighbors = {0: [1], 1:[2,3], 2:[3]}                                                                                                           
In [3]: test = weights.W(neighbors, silence_warnings=True)                                                                                             
In [4]: test.id2i                                                                                                                                      
Out[4]: {0: 0, 1: 1, 2: 2}
jGaboardi commented 4 years ago
  1. find set(all_labels).difference(set(neighbors.keys()), and call that out_islands.

What is the reasoning for naming this set out_islands?

ljwolf commented 4 years ago

They're out-degree islands! they have no directed link from them to something else. Idk, I thought it was clear & short. Happy to adopt a more clear name.

jGaboardi commented 4 years ago

They're out-degree islands! they have no directed link from them to something else. Idk, I thought it was clear & short. Happy to adopt a more clear name.

Ah! That makes sense. I had just never heard that term. I have always used "0-degree node" in graphs.

weikang9009 commented 4 years ago

This makes a lot of sense. One concern I have is regarding how this change will impact the property islands. Will the out-degree islands be considered as islands?

ljwolf commented 4 years ago

Ah! That makes sense. I had just never heard that term. I have always used "0-degree node" in graphs.

Well... they're not 0-degree, they have 0 outdegree. In my example above, node 3 is implicit, in that it has no explicit key in the weights dictionary. But, It's not a zero-degree node in total, since it has an in-degree of 1. We need to find and fix this for weights to work with things that come this way, otherwise it's a rough edge. We can say it's the user's issue for inputting a network with implicit nodes, but we should be robust

Will the out-degree islands be considered as islands?

Good question! By our current definition, they would be since their neighbor list is empty. This also means that their spatial lag is always zero.

weikang9009 commented 4 years ago

Will the out-degree islands be considered as islands?

Good question! By our current definition, they would be since their neighbor list is empty. This also means that their spatial lag is always zero.

I figure this could be an issue as they (out-degree islands) are not really islands (still receiving edges from other nodes)? Not sure whether this will cause other issues upstream...