partition

func GirvanNewman ¶

func GirvanNewman[T comparable](g gograph.Graph[T], k int) ([]gograph.Graph[T], error)

GirvanNewman implements the Girvan-Newman community detection algorithm for undirected graphs, and splits a directed graph as if it were undirected. It partitions a graph into communities by iteratively removing edges with the highest betweenness centrality until either the specified number of connected components `k` is reached, or no edges remain if k <= 0.

The algorithm proceeds as follows:

1. Compute edge betweenness centrality for all edges using Brandes algorithm. - BFS is used from each vertex to determine the shortest paths. - Dependencies are accumulated to assign betweenness values to edges.
2. Identify the edge with the highest betweenness. When several edges tie, take the first one in the order of AllEdges(). Values within one part in a billion of the highest count as tied, since sums of the same paths added in a different order can round differently.
3. Remove that edge.
4. Update connected components using a non-recursive BFS traversal.
5. Repeat steps 1-4 until the desired number of components (`k`) is reached. If k <= 0, continue until all edges are removed.

Removing one edge adds at most one component, so the result has exactly k communities when g has at least k vertices and at most k connected components. If g already has more than k connected components, they are returned as they are. If g has fewer than k vertices, every vertex ends up in its own community.

The communities of a directed graph are directed, and each edge of g in a community keeps its own direction, weight and label.

Important details:

• High betweenness edges typically act as bridges between clusters and are removed first, effectively separating communities.
• BFS is used exclusively for both shortest path computation and component identification to avoid recursion and stack overflow issues.
• The input graph `g` is cloned internally to prevent mutation.

Parameters:

• g: The input graph, directed or undirected.
• k: The desired number of communities (connected components). If k <= 0, the algorithm continues removing edges until no edges remain.

Returns:

• A slice of gograph.Graph[T], each representing a connected component (community). The order of the communities and of the vertices in them is stable: a graph built the same way gives the same result on every run. Each community has every edge of g between its vertices, including edges the algorithm removed while splitting the graph. The communities keep the vertex and edge weights, and are weighted if g is weighted.
• An error if g is nil, or if two vertices have more shortest paths between them than a float64 can count (about 1.8e308).

Time Complexity:

• Each iteration requires computing betweenness for all edges using BFS from each node.
• Let V = number of vertices, E = number of edges.
• Computing betweenness: O(V * (V + E)) per iteration.
• In the worst case, up to O(E) edges can be removed one by one.
• Total worst-case time complexity: O(E * V * (V + E)).

Space Complexity:

• Storing the cloned graph: O(V + E)
• BFS traversal queues and dependency maps: O(V + E)
• Storing betweenness values for edges: O(E)
• Total space complexity: O(V + E)

func MaximalCliques ¶

func MaximalCliques[T comparable](g gograph.Graph[T]) [][]*gograph.Vertex[T]

MaximalCliques finds all maximal cliques in the input graph using the Bron–Kerbosch algorithm with pivot selection, degeneracy ordering, and bitsets.

A **clique** is a subset of vertices where every two distinct vertices are connected by an edge. A **maximal clique** is a clique that cannot be extended by adding another adjacent vertex.

This implementation is optimized for performance:

1. **Degeneracy ordering**: processes vertices in a specific order to reduce recursive calls and improve efficiency.
2. **Pivot selection**: selects a pivot vertex at each recursive call to reduce the number of branches.
3. **Bitsets**: represents candidate sets (P, X) efficiently using []uint64 to speed up set operations on large graphs.

Parameters:

• g: a gograph.Graph[T] representing the graph. T must be a comparable type. Each vertex in the graph can be accessed via g.GetAllVertices() and neighbors via Vertex.AllNeighbors().

Returns:

• [][]*gograph.Vertex[T]: a slice of maximal cliques. Each clique is a slice of pointers to Vertex[T]. Vertices in a clique are guaranteed to be fully connected, and no clique is a subset of another.

Complexity:

• **Time Complexity**: O(3^(n/3)) in the worst case for general graphs, where n is the number of vertices. This is the known bound for enumerating all maximal cliques. In practice, degeneracy ordering + pivoting reduces the number of recursive calls significantly on sparse graphs.
• **Space Complexity**: O(n^2 / 64) for bitsets plus O(k*n) for storing cliques, where k is the number of maximal cliques. Additional recursion stack space is O(n) in depth.

Example usage:

g := gograph.New[string]()
a := g.AddVertexByLabel("A")
b := g.AddVertexByLabel("B")
c := g.AddVertexByLabel("C")
_, _ = g.AddEdge(a, b)
_, _ = g.AddEdge(b, c)
_, _ = g.AddEdge(c, a)

cliques := MaximalCliques(g)
for _, clique := range cliques {
    for _, v := range clique {
        fmt.Print(v.Label(), " ")
    }
    fmt.Println()
}

Notes:

• Self-loops are ignored.
• In a directed graph, edges are treated as undirected: two vertices are adjacent if there is an edge between them in either direction.
• The function returns the actual Vertex pointers from the input graph; do not modify the vertices while iterating the results.
• The order of cliques and of the vertices within a clique is stable: it only depends on the order of the vertices and edges in the graph, so a graph built the same way gives the same result on every run. The order itself is not specified. If a specific order is required, sort the result (e.g., by vertex label).