Рисование графических структур с использованием только Python и Matplotlib?

Question

Чтобы нарисовать набор объектов в порядке поиска в ширину

Чтобы с самого начала это не понимать, я довольно заурядный программист в целом, поэтому прошу прощения за явно нубистские вещи, которые я сделал бы в следующем проекте.

Цель этого проекта - получить структуру графа, если вы дадите ей таблицу узлов, их описания и узлы, к которым он подключен. Однако препятствием является то, что я не могу использовать какие-либо внешние библиотеки для этого, кроме matplotlib.

Ввод будет выглядеть примерно так:

входные данные в виде таблицы

Ожидаемый результат должен быть примерно таким: (обратите внимание, эта диаграмма игнорирует размеры)

Ожидаемый результат

Логика, которую я разработал:

Преобразование необработанных данных списка в объект класса, который имеет все атрибуты из списка.

2) Перейдите к поиску узлов в ширину

3) Поместить последовательность пробелов, которые BFS искала в список

4) Затем нарисуйте пробелы, как они появились в списке (обратите внимание, расстояние между ними необходимо для того, для чего оно мне нужно)

Как далеко я добрался:

Я разобрался со всем до шага № 3. У меня проблема в том, что теперь я должен установить координаты x и y для каждого пробела.

Чтобы сломать то, что я имею в виду, это:

Если первый узел является узлом типа записи, он выводит его в середине максимальной ширины графа

Подсчитайте количество внешних подключений, которые у него есть, а затем вытяните их как (максимальная ширина / число подключений, увеличивая их. Таким образом, в гостиной нет ни одного, поэтому она вытянет его посередине. В гостиной есть 5 соединений (из которых одно уже нарисовано, т.е. запись, поэтому мы перебираем следующий набор из четырех пространств, движущихся только по оси x). Затем мы повышаем y и снова рисуем.

Чтобы выполнить это, я намеревался создать цикл, который проходит через упорядоченный список пробелов и имеет счетчик. Процесс:

1) если встреченный узел относится к одному из узлов типа входа, то мы вытягиваем этот узел и устанавливаем счетчик на число соединений.

2) если счетчик равен 1, то мы перемещаем ось Y вверх. и вытянуть это пространство

3) если счетчик> 1, то мы делим значение счетчика на максимальное значение глубины

У меня проблема:

Приведенный здесь пример учитывает только одну запись.

2) При использовании метода счетчика порядок пробелов неправильный.

3) Метод счетчика неправильно выводит узлы завершения.

И когда я на самом деле записываю это в python, я получаю это, что означает, что я явно потерпел неудачу:

Выход, который я получил

Сценарий в его нынешнем виде:

Pastebin link

И на данный момент у меня нет идей, как мне на самом деле решить эту проблему. Любая помощь очень ценится:)

#imports
import matplotlib.pyplot as plt
import matplotlib.patches as patches
from math import pi , sin

#raw data
connections = ['1', '0,2,5,7,8', '1,3', '2,4', '3', '1,6', '5', '1', '1']
indices = ['0', '1', '2', '3', '4', '5', '6', '7', '8']
spaceTags = ['entry ', 'living area', 'dining area', 'Kitchen', 'Utility', 
            'Bedroom1', 'Toilet attached', 'Toilet common', 'Bedroom2']
area = ['1', '40', '20', '15', '6', '20', '6', '6', '20']
minimumDimension = ['1', '5', '4', '3', '2', '4', '2', '2', '4']

#define the space class
class Space(object):
    def __init__(self,index,spaceName,connections,area,minimumDimension):
        self.index = index
        self.spaceName = spaceName
        self.connections = connections
        self.area = area
        self.ydim = minimumDimension
        self.xdim = (self.area / self.ydim)
        self.x = 0
        self.y = 0
        self.isExplored = False
        self.polarAngle = 0
        self.spaceType = 0 
        # 0= not assigned ; 1 = entry; 2 = intermediate; 3 = termination

    def ObjectAttributes(self):
        return (self.index,
                self.spaceName,
                self.connections,
                self.area,
                self.y,self.x,
                self.xdim,self.ydim,
                self.isExplored,
                self.spaceType)

#definations
#process integers
def convert_to_int_vals (input_list):
    output_list = []
    i = 0
    while i < len(input_list):
        output_list.append(int(input_list[i]))
        i += 1
    return output_list

#process floats
def convert_to_float_vals (input_list):
    output_list = []
    i = 0
    while i < len(input_list):
        output_list.append(float(input_list[i]))
        i += 1
    return output_list

#process 2D lists for connections
def process_2d_connections (input_list):
    output_list = []
    for item in input_list:
        if len(item) <= 1:
            lst = []
            lst.append(int(item))
            output_list.append(lst)
        else:
            var = item
            var = (var.split(','))
            var = convert_to_int_vals(var)
            output_list.append(var)
    return output_list

#make data into objects i.e. spaces
def convertDataToSpaces(index,spaceTag,connections,area,minimumDimension):
    print('Processing data...')
    if (len(index)==len(spaceTag)==len(connections)==len(area)==len(minimumDimension)):
        i = 0
        output_list = []
        while i < len(spaceTag):
            space = Space(index[i],spaceTag[i],connections[i],area[i],minimumDimension[i])
            output_list.append(space)
            i += 1
        print('Done.')
        return output_list
    else:
        print('Number of lists dont match')

#find first node
def FindFirstNode(spaceList):
    output = 'null'
    for item in spaceList:
        if item.spaceName == 'entry ' or item.spaceName =='entry':
            item.spaceType = 1
            output = item

    if output == 'null':
        print('No entry defined. Please define entry!')

    return output

#Calculate hypotenuse
def calculate_hypotenuse(arg1,arg2):
    val = ((arg1**2)+(arg2**2))**(0.5)
    return val

#Calculate max hypotenuse
def calculate_max_hypotenuse (spaceList):
    outputval = 0
    for item in spaceList:
        var = calculate_hypotenuse(item.xdim,item.ydim)
        if var > outputval:
            outputval = var
        else:
            outputval
    return outputval

# Note this is a FIFO list
def FindAndQueueNextNode(spaceList,searchNode,queue):
    searchNode.isExplored = True

    if len(searchNode.connections) == 1:
        if searchNode.spaceName == 'entry ' or searchNode.spaceName =='entry':
            searchNode.spaceType = 1
        else:
            searchNode.spaceType = 3
    elif len(searchNode.connections) > 1:
        searchNode.spaceType = 2
    else:
        searchNode.spaceType = 0

    for item in spaceList:
        if ( item.index in searchNode.connections) and (item.isExplored == False) :
            queue.append(item)

# Calculate the position based on the dimension (inputs are the object dimensions and current floating dim) 
def CalculatePosition(currentx, currenty, space):
    spaceXdimadjusted = (space.xdim / 2)* -1
    spaceYdimadjusted = (space.ydim / 2)* -1
    adjustedx = currentx + spaceXdimadjusted
    adjustedy = currenty + spaceYdimadjusted

    return (adjustedx,adjustedy)

#core algorithm
def coreAlgorithm(spacesList):
    ## variable holding max hypotenuse distance
    grid_dimension = int((calculate_max_hypotenuse(spacesList))*(1.5))
    print('Grid dimensions are : ' + str(grid_dimension) + (' units'))

    ## create empty processing variables
    processingQueue = []
    orderedListOfSpacesInBFS = []
    maxTreeWidth = 0

    ## find the first space
    firstSpace = FindFirstNode(spacesList)
    orderedListOfSpacesInBFS.append(firstSpace)
    print('The first node is : ' + str(firstSpace.spaceName) +
        '; Index being : ' + str(firstSpace.index))

    ## queue the next space
    FindAndQueueNextNode(spacesList,firstSpace,processingQueue)

    ##start while loop (while queue length loop  > 0)
    while len(processingQueue) > 0 :
        if len(processingQueue) > maxTreeWidth:
            maxTreeWidth = len(processingQueue)
        else:
            maxTreeWidth = maxTreeWidth
        item = processingQueue.pop(0)
        orderedListOfSpacesInBFS.append(item)
        FindAndQueueNextNode(spacesList,item,processingQueue)

    ## second loop to loop through spaces and draw them
    maxXDepthDimension = grid_dimension * maxTreeWidth
    ypos = grid_dimension 
    counter = 0

    while len(orderedListOfSpacesInBFS) > 0:
        item = orderedListOfSpacesInBFS.pop(0)

        if item.spaceType == 1:
            xpos = maxXDepthDimension / 2
            (item.x , item.y) = CalculatePosition(xpos,ypos, item)
            ypos += grid_dimension
            counter = len(item.connections)

        elif counter == 1:
            xpos = maxXDepthDimension / 2
            (item.x , item.y) = CalculatePosition(xpos,ypos, item)
            ypos += grid_dimension
            counter = len(item.connections) - 1

        elif counter > 1:
            xpos = (maxXDepthDimension / counter)
            (item.x, item.y) = CalculatePosition(xpos, ypos, item)
            counter -= 1



#draw lines as a separete method

#core algorithm preprocess
def coreAlgorithmLoop (spaces_list):

    #check object feasibility and if the algorithm can run.
    print('Starting algorithm...')
    startrun = False
    floatingvartoggle = 1

    for item in spaces_list:
        if type(item) == Space:
            floatingvartoggle = floatingvartoggle * 1
        else:
            floatingvartoggle = floatingvartoggle * 0

    if floatingvartoggle == 1:
        startrun = True
    else:
        print('Objects should be spaces.')

    #start of  core-algorithm.
    if startrun == True:
        coreAlgorithm(spaces_list)

#implementation
#pre-process data
indices = convert_to_int_vals(indices)
spaceTags = spaceTags
connections = process_2d_connections(connections)
area = convert_to_float_vals(area)
minimumDimension = convert_to_float_vals(minimumDimension)

#initialize processing
listOfSpaces = convertDataToSpaces(indices,
                                spaceTags,
                                connections,
                                area,
                                minimumDimension)
coreAlgorithmLoop(listOfSpaces)

#matplotlibtester - start
fig, ax = plt.subplots()
ax.set_xlim((0, 100))
ax.set_ylim((0, 70))


for space in listOfSpaces:
    var = space.area
    print(space.ObjectAttributes())
    rect = patches.Rectangle((space.x,space.y),
                            space.xdim,space.ydim,0,
                            linewidth=1,
                            edgecolor='r',
                            facecolor='none')
    ax.add_patch(rect)

plt.show()
#matplotlibtester - end

Answer 1

Так что это неловко, но на всякий случай это кому-то помогает, метод для его решения:

• Создание изученных атрибутов и глубины
• Затем в очереди следите за тем, как был исследован узел и какова его глубина (текущий поисковый узел назначен элементам, ставящимся в очередь, глубина поискового узла равна глубине узла, который он исследовал с +1
• Используя это, создайте многоуровневую диаграмму, чтобы понять, куда направляется каждый объект (глубина - это номер строки / уровня / уровня), а экземпляр того, что объект находится на этом уровне, - это номер столбца

Это проще сделать с другим классом. Вот модифицированная версия кода: (обратите внимание, что он рисует асимметричную диаграмму, которая подходит для моих целей, и я до сих пор не решил проблему с более чем одной отправной точкой, что пока нормально)

#imports
import matplotlib.pyplot as plt
import matplotlib.patches as patches
from math import pi , sin

#raw data
connections = ['1', '0,2,5,7,8', '1,3', '2,4', '3', '1,6', '5', '1', '1']
indices = ['0', '1', '2', '3', '4', '5', '6', '7', '8']
spaceTags = ['entry ', 'living area', 'dining area', 'Kitchen', 'Utility', 
            'Bedroom1', 'Toilet attached', 'Toilet common', 'Bedroom2']
area = ['1', '40', '20', '15', '6', '20', '6', '6', '20']
minimumDimension = ['1', '5', '4', '3', '2', '4', '2', '2', '4']

#define the space class
class Space(object):
    def __init__(self,index,spaceName,connections,area,minimumDimension):
        self.index = index
        self.spaceName = spaceName
        self.connections = connections
        self.area = area
        self.ydim = minimumDimension
        self.xdim = (self.area / self.ydim)
        self.x = 0
        self.y = 0
        self.isExplored = False
        self.isExploredFrom = 0
        self.Depth = 0
        self.spaceType = 0 
        # 0= not assigned ; 1 = entry; 2 = intermediate; 3 = termination
        self.CentroidX = 0
        self.CentroidY = 0

    def ObjectAttributes(self):
        return (self.index,
                self.spaceName,
                self.y,self.x,
                self.Depth)

class DrawingStructure(object):
    def __init__(self,Depth):
        self.Depth = Depth
        self.numberOfInstances = 0
        self.count = 0
#definations
#process integers
def convert_to_int_vals (input_list):
    output_list = []
    i = 0
    while i < len(input_list):
        output_list.append(int(input_list[i]))
        i += 1
    return output_list

#process floats
def convert_to_float_vals (input_list):
    output_list = []
    i = 0
    while i < len(input_list):
        output_list.append(float(input_list[i]))
        i += 1
    return output_list

#process 2D lists for connections
def process_2d_connections (input_list):
    output_list = []
    for item in input_list:
        if len(item) <= 1:
            lst = []
            lst.append(int(item))
            output_list.append(lst)
        else:
            var = item
            var = (var.split(','))
            var = convert_to_int_vals(var)
            output_list.append(var)
    return output_list

#make data into objects i.e. spaces
def convertDataToSpaces(index,spaceTag,connections,area,minimumDimension):
    print('Processing data...')
    if (len(index)==len(spaceTag)==len(connections)==len(area)==len(minimumDimension)):
        i = 0
        output_list = []
        while i < len(spaceTag):
            space = Space(index[i],spaceTag[i],connections[i],area[i],minimumDimension[i])
            output_list.append(space)
            i += 1
        print('Done.')
        return output_list
    else:
        print('Number of lists dont match')

#find first node
def FindFirstNode(spaceList):
    output = 'null'
    for item in spaceList:
        if item.spaceName == 'entry ' or item.spaceName =='entry':
            item.spaceType = 1
            output = item

    if output == 'null':
        print('No entry defined. Please define entry!')

    return output

#Calculate hypotenuse
def calculate_hypotenuse(arg1,arg2):
    val = ((arg1**2)+(arg2**2))**(0.5)
    return val

#Calculate max hypotenuse
def calculate_max_hypotenuse (spaceList):
    outputval = 0
    for item in spaceList:
        var = calculate_hypotenuse(item.xdim,item.ydim)
        if var > outputval:
            outputval = var
        else:
            outputval
    return outputval

# Note this is a FIFO list
def FindAndQueueNextNode(spaceList,searchNode,queue):
    searchNode.isExplored = True

    if len(searchNode.connections) == 1:
        if searchNode.spaceName == 'entry ' or searchNode.spaceName =='entry':
            searchNode.spaceType = 1
        else:
            searchNode.spaceType = 3
    elif len(searchNode.connections) > 1:
        searchNode.spaceType = 2
    else:
        searchNode.spaceType = 0

    for item in spaceList:
        if ( item.index in searchNode.connections) and (item.isExplored == False) :
            item.isExploredFrom = searchNode.index
            item.Depth = searchNode.Depth + 1
            queue.append(item)

# Calculate the position based on the dimension (inputs are the object dimensions and current floating dim) 
def CalculatePosition(currentx, currenty, space):
    spaceXdimadjusted = (space.xdim / 2)* -1
    spaceYdimadjusted = (space.ydim / 2)* -1
    adjustedx = currentx + spaceXdimadjusted
    adjustedy = currenty + spaceYdimadjusted

    return (adjustedx,adjustedy)

#def return only unique values in a list
def ReturnUniqueValues(input_list):
    output_list = []
    for i in input_list:
        if i not in output_list:
            output_list.append(i)

    return output_list

#core algorithm
def coreAlgorithm(spacesList):
    ## variable holding max hypotenuse distance
    grid_dimension = int((calculate_max_hypotenuse(spacesList))*(1.5))
    print('Grid dimensions are : ' + str(grid_dimension) + (' units'))

    ## create empty processing variables
    processingQueue = []
    orderedListOfSpacesInBFS = []
    maxTreeWidth = 0

    ## find the first space
    firstSpace = FindFirstNode(spacesList)
    orderedListOfSpacesInBFS.append(firstSpace)
    print('The first node is : ' + str(firstSpace.spaceName) +
        '; Index being : ' + str(firstSpace.index))

    ##initialize first space
    firstSpace.Depth = 0
    firstSpace.isExploredFrom = 0  
    FindAndQueueNextNode(spacesList,firstSpace,processingQueue)

    ##start while loop (while queue length loop  > 0)
    while len(processingQueue) > 0 :
        if len(processingQueue) > maxTreeWidth:
            maxTreeWidth = len(processingQueue)
        else:
            maxTreeWidth = maxTreeWidth
        item = processingQueue.pop(0)
        orderedListOfSpacesInBFS.append(item)
        FindAndQueueNextNode(spacesList,item,processingQueue)

    #second loop for figuring out the depth and column number to draw
    DepthList = []
    uniquelist = []
    DrawingList = []

    for item in orderedListOfSpacesInBFS:
        DepthList.append(item.Depth)

    uniquelist = ReturnUniqueValues(DepthList)

    for item in uniquelist:
        var = DrawingStructure(item)
        DrawingList.append(var)

    copyList = orderedListOfSpacesInBFS

    while len(copyList) > 0:
        space = copyList.pop(0)
        for thing in DrawingList:
            if int(thing.Depth) == int(space.Depth):
                thing.numberOfInstances += 1

    ##actually setting the values to later draw
    for item in spacesList:
        rowNum = item.Depth
        rowData = 'null'

        for entry in DrawingList:
            if rowNum == entry.Depth:
                rowData = entry

        colNum = rowData.count
        rowData.count += 1

        xpos = rowNum * grid_dimension
        ypos = colNum * grid_dimension

        item.CentroidY =   xpos
        item.CentroidX =   ypos 

        (item.x, item.y) = CalculatePosition(ypos,xpos,item)


#draw lines as a separete method
def DrawConnectionLines(spacesList):
    for item in spacesList:
        centroid = [item]

#core algorithm preprocess
def coreAlgorithmLoop (spaces_list):

    #check object feasibility and if the algorithm can run.
    print('Starting algorithm...')
    startrun = False
    floatingvartoggle = 1

    for item in spaces_list:
        if type(item) == Space:
            floatingvartoggle = floatingvartoggle * 1
        else:
            floatingvartoggle = floatingvartoggle * 0

    if floatingvartoggle == 1:
        startrun = True
    else:
        print('Objects should be spaces.')

    #start of  core-algorithm.
    if startrun == True:
        coreAlgorithm(spaces_list)
        DrawConnectionLines(spaces_list)

#implementation
#pre-process data
indices = convert_to_int_vals(indices)
spaceTags = spaceTags
connections = process_2d_connections(connections)
area = convert_to_float_vals(area)
minimumDimension = convert_to_float_vals(minimumDimension)

#initialize processing
listOfSpaces = convertDataToSpaces(indices,
                                spaceTags,
                                connections,
                                area,
                                minimumDimension)
coreAlgorithmLoop(listOfSpaces)

#matplotlibtester - start
fig, ax = plt.subplots()
ax.set_xlim((-10, 60))
ax.set_ylim((0, 70))

xvals = []
yvals = []

for space in listOfSpaces:
    print(space.ObjectAttributes())
    rect = patches.Rectangle((space.x,space.y),
                            space.xdim,space.ydim,0,
                            linewidth=1,
                            edgecolor='r',
                            facecolor='none')
    ax.add_patch(rect)
    xvals.append(space.CentroidX)
    yvals.append(space.CentroidY)

plt.scatter(xvals,yvals)

plt.show()
#matplotlibtester - end