Доступ к элементам в списке и формирование графиков - PullRequest
Новая
       2

Доступ к элементам в списке и формирование графиков

0 голосов
/ 10 марта 2020

У меня есть список массивов 2D numpy: 

linelist = [[[0,0],[1,0]],[[0,0],[0,1]],[[1,0],[1,1]],[[0,1],[1,1]],[[1,2],[3,1]],[[1,2],[2,2]],[[3,1],[3,2]],[[2,2],[3,2]]]

Каждая строка в списке строк - это массив вершин, соединяющих ребро. Эти элементы являются линиями, которые образуют два квадрата: 

-----
|   |
-----

    -----
    |   |
    -----

Я хочу сформировать два графика, по одному для каждого квадрата. Для этого я использую a для l oop. Если в графе нет ни одной вершины, мы формируем новый граф. Если в списке строк присутствует одна вершина, то она добавляется в текущий граф. Для того, чтобы две линии были соединены, они должны иметь общую вершину. Однако у меня возникли проблемы с кодированием. Это то, что я до сих пор: 

    graphs = [[]]
    i=0
    for elements in linelist:
        for graph in graphs:
            if elements[0] not in graph[i] and elements[1] not in graph[i]:
                graphs.append([])
                graphs[i].append(elements)
                i=i+1
            else:
                graphs[i].append(elements)

Ответы [ 2 ]

1 голос
/ 11 марта 2020

Я предлагаю сделать «диффузионный» процесс над графом, чтобы найти непересекающиеся подграфы. В голову приходит один алгоритм поиск в ширину ; это работает, ища, какие узлы могут быть достигнуты от начального узла 

linelist = [[[0,0],[1,0]],[[0,0],[0,1]],[[1,0],[1,1]],[[0,1],[1,1]],[[1,2],[3,1]],[[1,2],[2,2]],[[3,1],[3,2]],[[2,2],[3,2]]] 

# edge list usually reads v1 -> v2
graph = {}
# however these are lines so symmetry is assumed
for l in linelist:
    v1, v2 = map(tuple, l)
    graph[v1] = graph.get(v1, ()) + (v2,)      
    graph[v2] = graph.get(v2, ()) + (v1,)

def BFS(graph):
    """
    Implement breadth-first search
    """
    # get nodes
    nodes = list(graph.keys())
    graphs = []
    # check all nodes 
    while nodes:
        # initialize BFS
        toCheck = [nodes[0]]
        discovered = []
        # run bfs
        while toCheck:
            startNode = toCheck.pop()
            for neighbor in graph.get(startNode):
                if neighbor not in discovered:
                    discovered.append(neighbor)
                    toCheck.append(neighbor)
                    nodes.remove(neighbor)
        # add discovered graphs
        graphs.append(discovered)
    return graphs
print(BFS(graph))
for idx, graph in enumerate(BFS(graph)):
    print(f"This is {idx} graph with nodes {graph}")

Вывод 

This is 0 graph with nodes [(1, 0), (0, 1), (0, 0), (1, 1)]
This is 1 graph with nodes [(3, 1), (2, 2), (1, 2), (3, 2)]

Вас может заинтересовать пакет networkx для анализа графиков. Например, найти непересекающиеся подграфы довольно тривиально: 

import networkx as nx
tmp = [tuple(tuple(j) for j in i) for i in linelist]
graph = nx.Graph(tmp);
for idx, graph in enumerate(nx.connected_components(graph)):
    print(idx, graph)
1 голос
/ 10 марта 2020

Мой подход включает 2 прохода по списку. На первом этапе я посмотрю на вершины и назначу номер графа каждому (1, 2, ...). Если обе вершины не были видны, я назначу новый номер графа. В противном случае присвойте его существующему.

Во втором проходе я go перебираю список и группирую ребра, принадлежащие одному и тому же номеру графа, вместе. Вот код: 

import collections
import itertools
import pprint


linelist = [[[0,0],[1,0]],[[0,0],[0,1]],[[1,0],[1,1]],[[0,1],[1,1]],[[1,2],[3,1]],[[1,2],[2,2]],[[3,1],[3,2]],[[2,2],[3,2]]]


# First pass: Look at the vertices and figure out which graph they
# belong to
vertices = {}
graph_numbers = itertools.count(1)
for v1, v2 in linelist:
    v1 = tuple(v1)
    v2 = tuple(v2)
    graph_number = vertices.get(v1) or vertices.get(v2) or next(graph_numbers)
    vertices[v1] = graph_number
    vertices[v2] = graph_number

print('Vertices:')
pprint.pprint(vertices)


# Second pass: Sort edges
graphs = collections.defaultdict(list)
for v1, v2 in linelist:
    graph_number = vertices[tuple(v1)]
    graphs[graph_number].append([v1, v2])

print('Graphs:')
pprint.pprint(graphs)

Вывод: 

Vertices:
{(0, 0): 1,
 (0, 1): 1,
 (1, 0): 1,
 (1, 1): 1,
 (1, 2): 2,
 (2, 2): 2,
 (3, 1): 2,
 (3, 2): 2}
Graphs:
defaultdict(<type 'list'>, {1: [[[0, 0], [1, 0]], [[0, 0], [0, 1]], [[1, 0], [1, 1]], [[0, 1], [1, 1]]], 2: [[[1, 2], [3, 1]], [[1, 2], [2, 2]], [[3, 1], [3, 2]], [[2, 2], [3, 2]]]})

Примечания

  • Мне нужно преобразовать каждую вершину из списка в кортеж, потому что список не может быть ключом словаря.
  • graphs ведет себя как словарь, ключи - номера графиков (1, 2, ...), а значения - список ребер

A небольшое объяснение линии 

graph_number = vertices.get(v1) or vertices.get(v2) or next(graph_numbers)

Эта строка примерно равна: 

number1 = vertices.get(v1)
number2 = vertices.get(v2)
if number1 is None and number2 is None:
    graph_number = next(graph_numbers)
elif number1 is not None:
    graph_number = number1
else:
    graph_number = number2

Что говорит: если v1 и v2 не находятся в вершинах, сгенерируйте новое число (т.е. next(graph_numbers)). В противном случае присвойте graph_number какому-либо значению, отличному от None.

Эта строка не только краткая, но и использует функцию короткого замыкания Python: интерпретатор сначала оценивает vertices.get(v1). Если это возвращает число (1, 2, ...), то интерпретатор возвращает это число и пропускает оценку vertices.get(v2) or next(graph_numbers).

Если vertices.get(v1) возвращает None, то есть False в Python интерпретатор оценит следующий сегмент or: vertices.get(v2). Опять же, если это возвращает ненулевое число, то оценка останавливается, и это число возвращается. Если vertices.get(v2) возвращает None, то интерпретатор оценивает последний сегмент, next(graph_numbers) и возвращает это значение.

...