найти клики в графике с помощью golang

Question

Я пытаюсь написать алгоритм, который найдет все Cliques (complete subgraphs) на графике. Каждая входная вершина должна быть только в одной результирующей клике. Алгоритм должен иметь временную сложность O(N^2). Каждая клика в результате должна быть как можно больше.

package main 

import (
    "fmt" 
) 

type Vertex struct { 
    Value int 
} 

type CompleteSubGraph struct { 
    vertecies []Vertex 
} 

func areConnected(vertex1, vertex2 Vertex) bool { 
    // 2 verteces are connected if their value sum is even 
    return (vertex1.Value+vertex2.Value)%2 == 0 
} 

func (vertex1 Vertex) getConnectedVertices(vertices []Vertex, maxVertices int) (verticesConnectedWithVertex1 []Vertex) { 
    for _, vertex2 := range vertices { 
     if areConnected(vertex1, vertex2) { 
      verticesConnectedWithVertex1 = append(verticesConnectedWithVertex1, vertex2) 
     } 
     if len(verticesConnectedWithVertex1) >= maxVertices { 
      break 
     } 
    } 
    return 
} 

func findAllCompleteSubGraphs(
    vertices []Vertex, 
    maximumNumberOfVerticesForSubGraph int, 
) (allCompleteSubgraphs []*CompleteSubGraph) { 
    /* 
     every vertex from input vertices 
     must be only in one CompleteSubGraph 

     the Algorithm must work not slower than O(N^2) 
     where N is len(vertices) 

     each vertex from input vertices must be only in one 
     resulting CompleteSubGraph 

     each CompleteSubGraph must be as big as possible 
    */ 
    for _, vertex1 := range vertices { 
     connectedToVertex1 := vertex1.getConnectedVertices(vertices, 
      maximumNumberOfVerticesForSubGraph) 
     fmt.Println("vertex", vertex1) 
     fmt.Println("is connected to", connectedToVertex1) 
    } 
    return 
} 

func main() { 
    vertices := []Vertex{ 
     Vertex{Value: 1}, Vertex{Value: 2}, Vertex{Value: 3}, 
     Vertex{Value: 4}, Vertex{Value: 5}, Vertex{Value: 6}, 
     Vertex{Value: 7}, Vertex{Value: 8}, Vertex{Value: 9}, 
     Vertex{Value: 10}, Vertex{Value: 11}, Vertex{Value: 12}, 
    } 
    fmt.Println("result", findAllCompleteSubGraphs(vertices, 3)) 
} 

Я проверяю, если 2 vertecies соединены ребром, используя areConnected функцию. Это просто, например, но будет сложнее в реальной жизни.

Я должен использовать func (vertex1 Vertex) getConnectedVertices, как он определен сейчас. я застрял на цикле

 for _, vertex1 := range vertices { 
      connectedToVertex1 := vertex1.getConnectedVertices(vertices, 
       maximumNumberOfVerticesForSubGraph) 
      fmt.Println("vertex", vertex1) 
      fmt.Println("is connected to", connectedToVertex1) 
     } 

Едва ли можно представить себе, как закончить алгоритм. Будет ли указывать какие-либо рекомендации.

Playground

Update

Исходная задача, которую я пытаюсь решить: найти группы людей, которые подходят друг к другу по некоторым характеристикам. AreConnected действительно, когда person1 понравилось person2 и person2 понравилось person1. Задача состоит в том, чтобы создать группы людей с максимальным размером по списку людей. Считается, что большие группы лучше, чем небольшие группы.

Answer 1

O (n^2) не хватает времени для перечисления всех возможных кликов на графике, даже если мы (невероятно оптимистично) предположим, что O (1) обрабатывает время на клику. Рассмотрим n-вершинный граф, состоящий из n/3 непересекающихся треугольников, т. Е. N/3 множества из трех вершин, причем каждая вершина имеет ребра к двум другим вершинам в своей группе и никаким другим вершинам. Обратите внимание, что вы можете самостоятельно выбрать одну вершину из каждого из n/3 треугольников, чтобы получить независимый набор (набор из n/3 вершин, ни один из которых не соединен ребрами). Теперь инвертируем все ребра в этом графе: это дает график, в котором тот же выбор вершин теперь дает клику размером n/3. Есть 3^(n/3) клики этого размера, все из которых максимальны (не могут быть добавлены к ним и остаются кликами). 3^(n/3) - много больше, чем n^2, поэтому вы не можете даже перечислить все эти клики в O (n^2) времени.