3
\$\begingroup\$

I have a sample list which contains nodes and their neighbors, if they have any. The task is to find the node which have the highest number of neighbors.

neigh = [['A'],['A','B'],['A','C'],['B','D'],['C','A']]

The input is undirected. Meaning that ['A', 'B'] are neighbors. While ['A'] doesn't have any neighbors since it has no other value within its own list. If a sublist has 2 elements, then they are neighbors. Otherwise they are not neighbors.

My solution is below, it has a lot of if-else statements. Is there a more elegant way to solve this?

def find_neighbors(neigh):
    d = {}
    for i in neigh:
        if i:
                if len(i)==2:
                    if i[0] in d.keys():
                        d[i[0]] +=1.0
                    else:
                        d[i[0]] = 1.0

                    if i[1] in d.keys():
                        d[i[1]] +=1.0
                    else:
                        d[i[1]] = 1.0

    max = 0
    for i,j in d.items():
        if j > max:
            max = j
    return [i for i, j in d.items() if j == max]

find_neighbors(neigh)

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I am a little confused with your example where A doesn't have any neighbors, yet ['A', 'B'] are neighbors to each other. \$\endgroup\$ – Alexander Dec 8 '19 at 4:52
  • 1
    \$\begingroup\$ I agree with the other @Alexander that this is still quite unclear, I have flagged the post as such. Why are you using floats to count the number of neighbours? Are you expecting some nodes to have 0.5 neighbours? \$\endgroup\$ – AMC Dec 8 '19 at 6:20
  • \$\begingroup\$ I agree with both Alexander's comment, the definition of neigh is ambiguous, does neigh = [['A'], ['A','B']] mean that B has a neighbor and A has not? You might post a better defined code review request to code review (and delete this one). \$\endgroup\$ – Jan Kuiken Dec 8 '19 at 20:11
1
\$\begingroup\$
  1. Use better variable names, d, i and j are quite poor.
    Don't overwrite bultins, max is already defined.
  2. You can use max rather than have your own loop.

    max_neighbours = max(d.values())
    
  3. You don't need to use in d.keys(), in d works just fine.

  4. You can use collections.defaultdict rather than a dict for d so that you don't need the if i[0] in d.keys().

    d = collections.defaultdict(int)
    for i in neigh:
        if len(i) == 2:
            d[i[0]] += 1
            d[i[1]] += 1
    
  5. You can use itertools.chain.from_iterable along with a small comprehension to remove the need to specify d[i[...]] += 1 twice.

    neighbours = (
        nodes
        for nodes in neigh
        if len(nodes) == 2
    )
    for node in itertools.chain.from_iterable(neighbours):
        d[node] += 1
    
  6. You can use collections.Counter to count the neighbours for you.

    d = collections.Counter(itertools.chain.from_iterable(neighbours))
    

All together this can get:

import collections
import itertools


def find_neighbors(neigh):
    neighbours = collections.Counter(itertools.chain.from_iterable(
        nodes
        for nodes in neigh
        if len(nodes) == 2
    ))
    max_neighbours = max(neighbours.values())
    return [
        node
        for node, count in neighbours.items()
        if count == max_neighbours
    ]
\$\endgroup\$
1
\$\begingroup\$

This checks if there is a neighbor of an element and if so, adds it to the count.

import operator 
def find_max_letter_in_array(neighborhood):
  all_neighbors_with_count = {}
  for neighbor_set in [pair_of_neighbors for pair_of_neighbors in neighborhood if len(pair_of_neighbors) > 1]:
    for neighbor in neighbor_set:
      all_neighbors_with_count.update({neighbor[0]: 1 if neighbor[0] not in all_neighbors_with_count else all_neighbors_with_count[neighbor[0]]+ 1})

  #return all_neighbors_with_count
  return max(all_neighbors_with_count.items(), key=operator.itemgetter(1))[0]


neigh = [['A'],['A','B'],['A','C'],['B','D'],['C','A']]
print(find_max_letter_in_array(neigh))

output: 
#{'A': 3, 'B': 2, 'C': 2, 'D': 1}
A
  1. You can loop over lists with conditions in them so that you only iterate over items you actually need
for each_element in [element for element in list if len(element) > 1]:
  1. Another important part is, you can use dict.update to do both insert and update.
  2. You can use the if statement while doing the assignment of a value as well
x = y if something_is_true else 
  1. At the end, using the operator.max, you can simply your code to get the max element key from dictionary based on all keys' values.

Hope it helps in how you can compress your code.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. \$\endgroup\$ – Peilonrayz Dec 8 '19 at 13:26
  • \$\begingroup\$ Adding details to the suggestion of a compressed code. \$\endgroup\$ – Jawad Dec 8 '19 at 17:29
0
\$\begingroup\$

For good programming we need to create and manipulate reusable code, so that every time when we are using list, tuple or dictionary, we can realize, Is it possible to use this for solving my another problem? And this is the good programming habit. For example we are using a list of list for neighbors item, the list containing neighbors against a neighbor, so that we can simply split them and we can use it for count maximum neighbors also whenever time we need the compared list or neighbors list we can use it, so this program will be most shorter and in efficient way also re usable. Another thing is that, it is the good example of one line looping and one line conditions.

Try the following code to print all of the matched items:

neigh = [['A'],['A','B'],['A','C'],['B','D'],['C','A']]
first_list = [str(item[0]) for item in neigh]
second_list = [(len(item) - 1) for item in neigh]

for i in range(len(second_list)):
    if second_list[i] == max(second_list):
        neigh_max = first_list[i]
        print(neigh_max)

If you want to print just one time one item, you can use this:

neigh_max = first_list[second_list.index(max(second_list))]

Instead of using:

for i in range(len(second_list)):
    if second_list[i] == max(second_list):
        neigh_max = first_list[i]
        print(neigh_max)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. \$\endgroup\$ – Peilonrayz Dec 8 '19 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy