Графический инструмент Python: генерирует, например, onet до n-й степени - PullRequest
Новая
       60

Графический инструмент Python: генерирует, например, onet до n-й степени

1 голос
/ 27 января 2020

Кажется, в библиотеке графических инструментов нет встроенной функции для генерации подграфа, который содержит всех соседей определенного узла вплоть до n-й степени. Проблема также может быть сформулирована как построение, например, onet вокруг узла с использованием соседей n-степени. Давайте рассмотрим следующий игрушечный пример: 

from graph_tool.all import *

edge_list = [
    [('node', 0), ('node', 1), 'xyz'],
    [('node', 1), ('node', 2)],
    [('node', 2), ('node', 3)],
    [('node', 3), ('node', 4), 'abc'],
    [('node', 0), ('node', 4)],
    [('node', 4), ('node', 5)],
    [('node', 5), ('node', 6)],
    [('node', 6), ('node', 7)],
    [('node', 0), ('node', 8)],
    [('node', 7), ('node', 8)],
    [('node', 7), ('node', 9)],
    [('node', 9), ('node', 10)]
]

g = Graph(directed=False)

Я добавляю несколько свойств (вершин и ребер), чтобы проверить, распространяются ли они на подграф: 

edge_attributes = g.new_edge_property("string")
g.edge_properties['edge_attributes'] = edge_attributes

nodes_id = g.add_edge_list(edge_list, hashed=True, eprops = [edge_attributes] )
g.vertex_properties['nodes_id'] = nodes_id

bool_flg = g.new_vertex_property('int')
bool_flg.set_value(0)
bool_flg[4] = 1
g.vertex_properties['bool_flg'] = bool_flg

Так как я начинаю с внешним именем узла, например ('node', 0) (библиотека graph-tool работает с последовательными неотрицательными целыми числами). Я определяю функцию поиска идентификатора узла: 

def find_vertex_id(G, node, id_mapping='nodes_id'):
    return int(find_vertex(G, G.vertex_properties[id_mapping], node)[0])

Первая (и самая Шаг (основанный на решении networkx) - это этап, который генерирует идентификаторы узлов, подключенных к root (удовлетворяющих, например, требованию onet): 

def get_neighbours_n_degree(G, source, cutoff=None):
    seen = set()
    level = 0

    source_id = find_vertex_id(G, source) # translate into int id

    nextlevel={source_id}

    while nextlevel:
        thislevel = nextlevel
        nextlevel = set()
        for v in thislevel:
            if v not in seen:
                seen.update([v]) #set must be updated with an iterable
                nextlevel.update(g.get_all_neighbors(v)) #add neighbours
        if (cutoff is not None and cutoff <= level):
            break
        level = level + 1

    return seen # include the root

Подграф следующее поколение: 

def generate_subgraph(G, source, cutoff=None):
    subgraph_nodes = get_neighbours_n_degree(G=G, source=source, cutoff=cutoff)

    vfilt = G.new_vertex_property('bool')
    for i in subgraph_nodes:
        vfilt[i] = True

    sub = GraphView(G, vfilt)
    sub = Graph(sub, prune=True) #create independent copy; restart the node index

    return sub

Я также определяю функцию рисования: 

def graph_draw_enhanced(graph):
    graph_draw(graph, vertex_text=graph.vertex_index,
              vertex_fill_color = graph.vertex_properties['bool_flg'])

Моя пользовательская функция работает нормально для предоставленного примера, но начинает работать медленнее, когда предоставляется сеть из 8M узлов - вычисление 4-й степени, например onet, занимает около 2,5 минут. Есть ли более оптимальный способ создать, например, onet в graph-tool?

Решение должно вернуть подграф, содержащий ту же информацию о вершине и ребре, что и у исходного графа. 

subgraph = generate_subgraph(g, ('node', 0), cutoff=2)

# check for edges
for edge in subgraph.edges():
    print(edge, g.edge_properties['edge_attributes'][edge])

# check for nodes
for node in subgraph.vertices():
    print(node, g.vertex_properties['bool_flg'][node])

1 Ответ

2 голосов
/ 28 января 2020

Это значительно проще сделать с помощью функции фильтрации графического инструмента. Вот простая функция, которая генерирует e go net до порядка n: 

def ego_net(g, ego, n): 
    d = shortest_distance(g, ego, max_dist=n) 
    u = GraphView(g, vfilt=d.a < g.num_vertices()) 
    return u

Это возвращает GraphView в исходный граф и, следовательно, сохраняет все внутренние карты свойств и вершинные индексы. Если требуется автономный график, это можно сделать, создав новый сокращенный график: 

u = ego_net(g, ego, n)
u = Graph(u, prune=True)

. Приведенный выше подход должен быть намного быстрее, чем было предложено в вопросе.

...