6
\$\begingroup\$

My Code measures the longest path, not allowing cycles. For the example input below, the longest chain would be 4

Please can you review my code?

import numpy as np
inputgrid = np.array([['.','.','.','.','.'],
                      ['C','-','C','-','C'],
                      ['.','.','|','.','.'],
                      ['.','.','C','.','.'],
                      ['.','.','|','.','.'],
                      ['.','.','C','.','.'],
                      ['.','.','.','.','.']])# This Is Input


inputgrid = np.where(inputgrid=='.', 0, inputgrid)
inputgrid = np.where(inputgrid=='C', 1, inputgrid)
inputgrid = np.where(inputgrid=='-', 9, inputgrid)
inputgrid = np.where(inputgrid=='|', 9, inputgrid)

np.array(inputgrid).tolist()

grid = [[int(item) for item in row] for row in inputgrid]

def display(grid):
    for row in grid:
      print(row)

display(grid)


lst = []
for rows, row in enumerate(grid):
    for cols, col in enumerate(row):
        if grid[rows][cols] in [1]:
            lst.append((rows, cols))

bondlst = []            
for rows, row in enumerate(grid):
    for cols, col in enumerate(row):
        if grid[rows][cols] in [9]:
            bondlst.append((rows, cols))       


print(lst)
print(bondlst)

bondx = []
bondy = []

for item in bondlst:
    (bondx).append(item[0])
    (bondy).append(item[1])

print(bondx)
print(bondy)


adjacencylist = []

def adjacentnode(nodea ,nodeb):
    if nodea[0] == nodeb[0] and nodea[1] == nodeb[1]+2:
        adjacent = True
    elif nodea[0] == nodeb[0] and nodea[1] == nodeb[1]-2:
        adjacent = True
    elif nodea[1] == nodeb[1] and nodea[0] == nodeb[0]+2:
        adjacent = True
    elif nodea[1] == nodeb[1] and nodea[0] == nodeb[0]-2:
        adjacent = True
    else:
        adjacent = False
    return adjacent

print (adjacentnode((1,0),(1,2)))

count = 0 

tempgraph = {}
for node in range(len(lst)):
    print (node)
    adjacencylist.append((lst[node] ,[]))
    for neighbour in range(len(lst)):
        adjacentnodes = (adjacentnode(lst[node] ,lst[neighbour]))
        print(adjacentnodes)
        if adjacentnodes == True:
            count = count +1
            adjacencylist[node][1].append(lst[neighbour])
            # adjacencylist.append((lst[node],[]))
            # adjacencylist.append(lst[node])
            # adjacencylist.append(lst[neighbour])

print (count)            
print (adjacencylist)

for item in adjacencylist:
    tempgraph[str(item[0])] = (item[(1)])



carbongraph = {}
for i in tempgraph:
    carbongraph[i] = [str(k) for k in tempgraph[i]]

print(carbongraph)

#print(adjacencylist)

#print (carbongraph)
'''
carbongraph = {'(0, 1)' :['(0, 2)'], '(0, 2)' :['(0, 1)' ,'(0, 3)' ,'(1, 2)'],
               '(0, 3)' :['(0, 2)'], '(1, 2)' :['(0, 2)', '(2, 2)'], '(2, 2)': ['(1, 2)']}

WEIGHTS = 1
'''
def shortestpath(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    if start not in graph:
        return None
    for node in graph[start]:
        if node not in path:
            newpath = shortestpath(graph, node, end, path)
            if newpath:
                return newpath
    return None

LeafArray = []
for leaf in carbongraph:
    degree = (len(carbongraph[leaf]))
    if degree == 1:
        LeafArray.append(leaf)



print(LeafArray)

chainlist = []
for node in LeafArray:
    for neighbour in LeafArray:
        currentpath = (shortestpath(carbongraph, node, neighbour))
        carbonchain = len(currentpath)
        print(currentpath)
        chainlist.append(carbonchain)

longestchain = max(chainlist)
print(longestchain)


def Prfix():
    global prefix
    if longestchain == 4:
        prefix = "But"
    elif longestchain == 5:
        prefix = "Pent"
    elif longestchain == 6:
        prefix = "Hex"
    elif longestchain == 7:
        prefix = "Hept"
    elif longestchain == 8:
        prefix = "Oct"
    return prefix

print(Prfix())
```
\$\endgroup\$
7
\$\begingroup\$

Welcome back to CodeReview. Your code and your problem seemed familiar, so I searched and found your previous attempt. This version runs to completion on my machine, so congratulations!

What is this?

First, I have to ask, what are you doing? The code runs to completion, and prints an answer that looks like what you're trying to get, but that answer is lost in the noise of a bunch of other stuff. This is nuts! When you're asking for review, you want to make sure everything is clear. Please, make your output more clear!

$ python carbon.py
[0, 0, 0, 0, 0]
[1, 9, 1, 9, 1]
[0, 0, 9, 0, 0]
[0, 0, 1, 0, 0]
[0, 0, 9, 0, 0]
[0, 0, 1, 0, 0]
[0, 0, 0, 0, 0]
[(1, 0), (1, 2), (1, 4), (3, 2), (5, 2)]
[(1, 1), (1, 3), (2, 2), (4, 2)]
[1, 1, 2, 4]
[1, 3, 2, 2]
True
0
False
True
False
False
False
1
True
False
True
True
False
2
False
True
False
False
False
3
False
True
False
False
True
4
False
False
False
True
False
8
[((1, 0), [(1, 2)]), ((1, 2), [(1, 0), (1, 4), (3, 2)]), ((1, 4), [(1, 2)]), ((3, 2), [(1, 2), (5, 2)]), ((5, 2), [(3, 2)])]
{'(1, 0)': ['(1, 2)'], '(1, 2)': ['(1, 0)', '(1, 4)', '(3, 2)'], '(1, 4)': ['(1, 2)'], '(3, 2)': ['(1, 2)', '(5, 2)'], '(5, 2)': ['(3, 2)']}
['(1, 0)', '(1, 4)', '(5, 2)']
['(1, 0)']
['(1, 0)', '(1, 2)', '(1, 4)']
['(1, 0)', '(1, 2)', '(3, 2)', '(5, 2)']
['(1, 4)', '(1, 2)', '(1, 0)']
['(1, 4)']
['(1, 4)', '(1, 2)', '(3, 2)', '(5, 2)']
['(5, 2)', '(3, 2)', '(1, 2)', '(1, 0)']
['(5, 2)', '(3, 2)', '(1, 2)', '(1, 4)']
['(5, 2)']
4
But

Why use numpy?

Next question: why are you using numpy? Here's the top of your code:

import numpy as np
inputgrid = np.array([['.','.','.','.','.'],
                      ['C','-','C','-','C'],
                      ['.','.','|','.','.'],
                      ['.','.','C','.','.'],
                      ['.','.','|','.','.'],
                      ['.','.','C','.','.'],
                      ['.','.','.','.','.']])# This Is Input


inputgrid = np.where(inputgrid=='.', 0, inputgrid)
inputgrid = np.where(inputgrid=='C', 1, inputgrid)
inputgrid = np.where(inputgrid=='-', 9, inputgrid)
inputgrid = np.where(inputgrid=='|', 9, inputgrid)

np.array(inputgrid).tolist()

grid = [[int(item) for item in row] for row in inputgrid]

You import numpy, create a numpy 2d array, process it minimally, and then convert the numpy array into a standard Python list of lists.

My first suggestion is this: stop using numpy. You aren't doing anything (yet) that justifies numpy. (Numpy isn't bad. But numpy is for numbers, and you're doing graphs. Maybe use a graph package instead?)

Style

I have two major objections to your code as presented. First, much of your code is "up against the wall" -- you are writing code that is executed immediately, rather than put it into functions that allow you to call or not-call your code as you like, and which furthermore logically group related parts of your code together. Please organize your code into descriptive functions!

Second, towards the end you have functions shortestpath and Prfix. Those are both PEP-8 violations. They should be shortest_path and prefix respectively. Every time you ask a question on here, you're going to get dinged for not following PEP8, so ... CONFORM!!!

Organization

As I see it, your code does a few things in sequence:

  • Converts a text representation of a molecule into a data structure of some kind.

  • Builds an adjacency graph

  • Computes the length of the longest carbon chain

  • Prints the length of the longest chain

  • Prints a prefix?

Let's see if we can improve on those.

Input

You represent your input as an ndarray, carefully and meticulously (& painfully) entered, with each element requiring 4 keystrokes: 'C', (apostrophe, C, apostrophe, comma). That's not going to scale very well, and it's going to be very prone to errors.

I suggest you use Python's triple-quoted strings to create a single large block of text, and then parse that as a text-processing problem in order to get your data:

Molecule = """

     C-C-C
       |
       C
       |
       C

""".strip()

You should strip all the starting and stopping whitespace, since that contributes nothing. You should remove tabs, replacing them with spaces in a rational way. The str.expandtabs() method will do that for you. You can then look at textwrap.dedent to evenly remove leading whitespace. This will give you a "minimal" ASCII-picture to parse for your graph.

If you have learned classes, I suggest you create an Atom class for your initial data structure. You can use it to build up the graph:

class Atom:
    def __init__(self, element='C', bonds=[]):
        self.element = element
        self.bonds = bonds

I don't know if this is meaningful in your case, but some graphs I have seen use multiple lines to indicate bonds, like:

C=C-C

Depending on what you're using this for, you may or may not care about that. You could just store that as a tuple in the bonds list, or create a duplicate bond entry, or a separate "weights" list to maintain in parallel, or create a Bond class that would represent the link and the number, etc.

Path length

There are a lot of ways to do path length. If you want to support large molecules or arbitrary diagrams, you might want to look at a package graph library. For example, what should your code return given this diagram?

C-C    C-C-C

Is that two molecules? Should it return the longest (3) or a list of the various longest-paths ([2, 3]) or what? It's up to you. I'd suggest that this is an error in input. But if you try to support this, it will change what graphing approach you use, since connectivity is a major concern in most graph traversal algorithms.

If you elect do compute path length yourself, you will likely find that a simple recursive traversal works for most simple cases (depth-first search). Just compute the max length of each outward bond, then sum the two highest.

Bug

Beware of this bug in your current code:

C-C
| |
C C

Your adjacentnode function doesn't check the intervening space, so it considers the bottom two carbons to be "adjacent" (which is true) but you're using that for your adjacency list computation (which would be wrong).

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.