Проверьте, является ли график двудольным - PullRequest
Новая
       24

Проверьте, является ли график двудольным

0 голосов
/ 09 марта 2019

, поэтому мне нужно проверить, является ли график двудольным, используя массивы Numpy и Python 2

Это код, который я разработал для проверки графика: 

from __future__ import print_function
import numpy as np

class grafo:
    visited = []

    def __init__(self, n):
        self.vertices = []
        self.adjacency = np.zeros((n,n))
        self.visited.append(True)
        self.size = n
        self.color = [-1] * self.size
        self.color.append(0)

    def isBipartita(self):
        finalRes = str()
        init = 0
        self.color[init] = 1
        self.visited.append(init)
        while self.visited: 
            i = self.visited.pop() 
            print("[FIRST CHECK] adyacencia[" + str(i)+"][" + str(i) + "] == 1?")
            if self.adjacency[i][i] == 1:  //HERE IT CORRUPTS AT SOME POINT
                finalRes = "NO"
                print("True")
                return finalRes; 

            for f in range(self.size): 
                print("[SECOND CHECK] adyacencia[" + str(i)+"][" + str(f) + "] == 1 and color[" + str(f) +"] == -1")
                if self.adjacency[i][f] == 1 and self.color[f] == -1:
                    print("True")
                    self.color[f] = 1 - self.color[i] 
                    self.visited.append(f)
                else:
                    print("[THIRD CHECK] adyacencia[" + str(i)+"][" + str(f) + "] == 1 and color[" + str(f) +"] == color[" + str(i) +"]")
                    if self.adjacency[i][f] == 1 and self.color[f] == self.color[i]:
                        print("True")
                        finalRes = "NO"
                        return finalRes

        finalRes = "YES"
        return finalRes

    def __str__(self):
        return str(self.adjacency)


#PROGRAM

lenV = raw_input("") #This is the length of the Adjacency array for the graph
lenV = int(lenV)
inputs = []

for i in range(0, lenV):
    inputs.append(raw_input())

print("\n-> Inputs:")
print(inputs)
print("\n-> List with Inputs Values:")
tempVal = list()
for numC in inputs:
    tempVal.append(numC)

print(tempVal)

print("\n-> Split and get into array:")
G = grafo(lenV)
for x in range(0,lenV):
    tempList = list(tempVal[x])
    print(tempList)
    for y in range(0, lenV):
        G.adjacency[x][y] = tempList[y]
print("\n-> Array to check:")       
print(G)
print("\n")
print(G.isBipartita())

Проблеманаходится в классе "grafo", в методе isBipartita;в какой-то момент при проверке массив целых чисел возвращает логическое значение и выдает в качестве выходного значения ValueError.

Вот несколько примеров, которые я использовал для проверки этого: 

TEST CASES
3
011
101
110

4
0101
1010
0101
1010

иэто вывод, который я получаю: 

/** LIKE 20 SUCCESSFUL CHECKS LATER **/
[SECOND CHECK] adyacencia[1][3] == 1 and color[3] == -1
[THIRD CHECK] adyacencia[1][3] == 1 and color[3] == color[1]
[FIRST CHECK] adyacencia[True][True] == 1?
Traceback (most recent call last):
  File "bipartitaChecker.py", line 76, in <module>
    print(G.isBipartita())
  File "bipartitaChecker.py", line 23, in isBipartita
    if self.adjacency[i][i] == 1: 
ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()

Как вы можете видеть, перед вызовом Traceback последний "[FIRST CHECK]" имеет adyacencia [True] [True], и ​​это не предназначено длябудь таким ... я провел исследование ValueError, но все приводит меня к тому, что только в некоторых иностранных случаях эта ошибка появляется, но в моем случае она не должна вызывать ее ...

Я не знаю, что происходит?!

Буду признателен за любую помощь.

...