triangle_count.md

Triangle Count

← Back to Algorithm Catalog

Table of Contents

• Overview
• When to Use
• Include
• Signature
• Parameters
• Supported Graph Properties
• Examples
  • Counting Triangles
  • Complete Graph K4
  • Triangle-Free Graphs
  • Multiple Sharing Triangles
  • Pre-sorting vov Adjacency Lists
• Mandates
• Preconditions
• Effects
• Returns
• Throws
• Complexity
• Remarks
• See Also

Overview

Counts the number of triangles (3-cliques) in an undirected graph using merge-based sorted-list intersection. A triangle is a set of three mutually adjacent vertices {u, v, w}.

The graph must satisfy adjacency_list<G> — both index-based (contiguous integer-indexed) and map-based (sparse vertex ID) graphs are supported.

The algorithm additionally requires ordered_vertex_edges<G>, meaning each vertex's adjacency list is sorted by target ID. This is naturally the case for set-based containers (e.g., vos traits) and undirected_adjacency_list.

When to Use

• Social network analysis — the triangle count and derived clustering coefficient (ratio of actual to possible triangles per vertex) measure how tightly knit a network is.
• Community detection preprocessing — a high local triangle density indicates a cohesive community.
• Graph quality metrics — triangle count is a fundamental structural statistic used in network science, bioinformatics, and fraud detection.

Not suitable when:

• You need to enumerate each triangle (the algorithm only counts them).
• The graph is directed — this algorithm treats the graph as undirected.
• Adjacency lists are unsorted and cannot be sorted — the algorithm requires the ordered_vertex_edges concept.

Include

#include <graph/algorithm/tc.hpp>

Signature

size_t triangle_count(G&& g);

Returns the total number of triangles in the graph.

Parameters

Parameter	Description
g	Graph satisfying adjacency_list and ordered_vertex_edges (sorted adjacency lists)

Supported Graph Properties

Directedness:

• ✅ Undirected graphs (primary use case)
• ❌ Directed graphs — algorithm treats graph as undirected

Edge Properties:

• ✅ Unweighted edges
• ✅ Weighted edges (weights ignored)
• ✅ Multi-edges (do not affect triangle count)
• ✅ Self-loops (ignored — do not count as triangles)

Graph Structure:

• ✅ Connected graphs
• ✅ Disconnected graphs (triangles counted per component)
• ✅ Empty graphs (returns 0)

Container Requirements:

• Required: adjacency_list<G> and ordered_vertex_edges<G>
• Adjacency lists must be sorted by target ID (use vos/dos traits or undirected_adjacency_list)

Examples

Example 1: Counting Triangles

Count triangles in a simple graph with one triangle.

#include <graph/algorithm/tc.hpp>
#include <graph/container/dynamic_graph.hpp>
#include <vector>

// Using sorted-edge traits (vos = vector of sets)
using Graph = container::dynamic_graph<void, void, void, uint32_t, false,
    container::vos_graph_traits<void>>;

// Triangle: 0-1-2
// Edges stored bidirectionally (both directions)
Graph g({{0,1}, {1,0}, {0,2}, {2,0}, {1,2}, {2,1}});

size_t count = triangle_count(g);
// count == 1

Or with undirected_adjacency_list which keeps edges sorted automatically:

#include <graph/container/undirected_adjacency_list.hpp>

undirected_adjacency_list<int, int> g({{0,1,1}, {0,2,1}, {1,2,1}});

size_t count = triangle_count(g);
// count == 1

Example 2: Complete Graph K4

K4 has $\binom{4}{3} = 4$ triangles. Every 3-vertex subset forms a triangle.

// K4: every pair of 4 vertices connected
Graph g({{0,1},{1,0}, {0,2},{2,0}, {0,3},{3,0},
         {1,2},{2,1}, {1,3},{3,1}, {2,3},{3,2}});

size_t count = triangle_count(g);
// count == 4
// Triangles: {0,1,2}, {0,1,3}, {0,2,3}, {1,2,3}

Example 3: Triangle-Free Graphs

Graphs without triangles return 0 — paths, stars, trees, and bipartite graphs are all triangle-free.

// Star graph: center 0 connected to leaves 1, 2, 3
Graph star({{0,1},{1,0}, {0,2},{2,0}, {0,3},{3,0}});
// triangle_count(star) == 0  — no pair of leaves is connected

// Path: 0 - 1 - 2 - 3
Graph path({{0,1},{1,0}, {1,2},{2,1}, {2,3},{3,2}});
// triangle_count(path) == 0

// Tree: any tree is triangle-free
// triangle_count(tree) == 0

// Bipartite K3,3 — no odd cycles, hence no triangles
// triangle_count(k33) == 0

Example 4: Multiple Sharing Triangles

Triangles can share edges. A "diamond" graph (K4 minus one edge) has 2 triangles that share an edge.

// Diamond: vertices 0-1-2-3, edges {0,1},{0,2},{1,2},{1,3},{2,3}
// Missing edge: {0,3}
Graph diamond({{0,1},{1,0}, {0,2},{2,0}, {1,2},{2,1},
               {1,3},{3,1}, {2,3},{3,2}});

size_t count = triangle_count(diamond);
// count == 2
// Triangles: {0,1,2} and {1,2,3}
// Edge 1-2 is shared between both triangles

Example 5: Pre-sorting vov Adjacency Lists

If you use vov-based traits (vectors of vectors), adjacency lists may not be sorted. Sort them before calling triangle_count.

#include <graph/algorithm/tc.hpp>
#include <graph/container/dynamic_graph.hpp>
#include <algorithm>

// vov traits: adjacency lists are unsorted vectors
using Graph = container::dynamic_graph<void, void, void, uint32_t, false,
    container::vov_graph_traits<void>>;

Graph g({{0,2}, {2,0}, {0,1}, {1,0}, {1,2}, {2,1}});
// Adjacency list for vertex 0 might be [2, 1] — NOT sorted

// Sort each adjacency list by target ID
for (auto&& [uid, u] : vertices(g)) {
    auto& edges_of_u = edges(g, u);
    std::ranges::sort(edges_of_u, [&](auto& a, auto& b) {
        return target_id(g, a) < target_id(g, b);
    });
}

size_t count = triangle_count(g);
// count == 1

// Tip: prefer vos_graph_traits or undirected_adjacency_list to avoid
//      manual sorting.

Mandates

• G must satisfy adjacency_list<G> and ordered_vertex_edges<G>

Preconditions

• Adjacency lists must be sorted by target ID. Use sorted-edge traits (vos, dos) or undirected_adjacency_list.
• For vov-based graphs, pre-sort each adjacency list before calling (see Example 5).
• Self-loops are ignored and do not count as triangles.

Effects

• Does not modify the graph g
• Reads adjacency lists via sorted merge-based intersection

Returns

size_t — the total number of triangles in the graph. Each triangle is counted exactly once, not three times (once per vertex). Declared [[nodiscard]] noexcept.

Throws

Does not throw — declared noexcept.

Complexity

Metric	Value
Time	O(m^{3/2}) average for sparse graphs, where m = number of edges
Space	O(1) auxiliary — uses sorted adjacency lists directly

The merge-based intersection exploits sorted neighbor lists, making it efficient for sparse graphs. For dense graphs with m ≈ V², the complexity approaches O(V³).

Remarks

• The algorithm counts each triangle exactly once, not three times (once per vertex).
• Only the count is returned, not the vertex triples. If you need to enumerate triangles, you would need to implement enumeration separately.
• ordered_vertex_edges is a compile-time concept — the library will give a concept error if the graph's edge ranges aren't sorted.

See Also

• Algorithm Catalog — full list of algorithms
• test_triangle_count.cpp — test suite