Нахождение цикла 3 узлов (или треугольники) в графике

Не хочу показаться резким, но пробовали ли вы это погуглить? Первая ссылка - это довольно быстрый алгоритм для этого: http://www.mail-archive.com/ algogeeks@googlegroups.com /msg05642.html

И еще есть эта статья об ACM (к которой у вас может быть доступ): http://portal.acm.org/citation.cfm?id=244866 (и если у вас нет доступа, я уверен, что если вы любезно спросите женщину, которая его написала, вы получите копию.)

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

Миллион ребер - это довольно мало. Если вы не делаете это тысячи раз, просто используйте наивную реализацию.

Я предполагаю, что у вас есть словарь node_id, который указывает на последовательность своих соседей, и что граф направлен.

Например:

nodes = {}
nodes[0] = 1,2
nodes[1] = tuple() # empty tuple
nodes[2] = 1

Мое решение:

def generate_triangles(nodes):
    """Generate triangles. Weed out duplicates."""
    visited_ids = set() # remember the nodes that we have tested already
    for node_a_id in nodes:
        for node_b_id in nodes[node_a_id]:
            if nod_b_id == node_a_id:
                raise ValueError # nodes shouldn't point to themselves
            if node_b_id in visited_ids:
                continue # we should have already found b->a->??->b
            for node_c_id in nodes[node_b_id]:
                if node_c_id in visited_ids:
                    continue # we should have already found c->a->b->c
                if node_a_id in nodes[node_c_id]:
                    yield(node_a_id, node_b_id, node_c_id)
        visited_ids.add(node_a_id) # don't search a - we already have all those cycles

Проверка производительности:

from random import randint
n = 1000000
node_list = range(n)
nodes = {}
for node_id in node_list:
    node = tuple()
    for i in range(randint(0,10)): # add up to 10 neighbors
        try:
            neighbor_id = node_list[node_id+randint(-5,5)] # pick a nearby node
        except:
            continue 
        if not neighbor_id in node:
            node = node + (neighbor_id,)
    nodes[node_id] = node

cycles = list(generate_triangles(nodes))
print len(cycles)

Когда я попробовал это, на построение случайного графа ушло больше времени, чем на подсчет циклов.

Возможно, вы захотите его проверить;) Я не гарантирую, что это правильно.

Вы также можете изучить networkx, большая библиотека графов Python.

Даже если это неэффективно, вы можете захотеть реализовать решение, поэтому используйте циклы. Напишите тест, чтобы понять, сколько времени он займет.

Затем, пробуя новые подходы, вы можете сделать две вещи: 1) Убедитесь, что ответ остался прежним. 2) Посмотрите, в чем состоит улучшение.

Наличие более быстрого алгоритма, который что-то упускает, вероятно, будет хуже, чем наличие более медленного.

После того, как у вас будет медленный тест, вы можете увидеть, сможете ли вы сделать это параллельно и посмотрите, каков прирост производительности.

Затем вы можете увидеть, можете ли вы отметить все узлы, у которых меньше 3 вершин.

В идеале, вы можете сначала уменьшить его до 100 или около того, чтобы вы может нарисовать его и увидеть, что происходит графически.

Иногда ваш мозг видит закономерность, которая не так очевидна при просмотре алгоритмов.

Вам нужно найти «все» из «треугольников» или просто «некоторые» / «любые»? Или, может быть, вам просто нужно проверить, является ли конкретный узел частью треугольника?

Проверка проста - для узла A есть ли какие-либо два соединенных узла B и C, которые также напрямую связаны.

Если вы необходимо найти все треугольники - в частности, все группы из 3 узлов, в которых каждый узел соединен с двумя другими - тогда вам нужно проверить каждую возможную группу в очень длительном цикле «для каждого».

Единственный Оптимизация гарантирует, что вы не проверяете одну и ту же «группу» дважды, например, если вы уже проверили, что B и C не находятся в группе с A, тогда не проверяйте, находятся ли A и C в группе с B .