igraph

The igraph graph-algorithms C library packaged as a PHP extension — a sibling to planarity, built to the same recipe: a tiny, audited wrapper (igraph.c, the only code we author) over a vendored C library, with a .phpt suite, a reproducible Docker build, Forgejo CI, and a Composer php-ext package.

API

igraph_is_dag(int $n, array $edges): bool
//   $n     — vertex count; vertices are 0 .. n-1.
//   $edges — list of [u, v] integer pairs, each a DIRECTED edge u -> v (0-based). Multigraphs are
//            accepted: parallel edges are fine; a self-loop (u -> u) or an anti-parallel pair
//            (u -> v and v -> u) forms a cycle. Nothing is dropped.
//   →  bool — true iff the directed graph is acyclic (a DAG: no directed cycle). The empty and any
//             edgeless graph are DAGs.
//   throws ValueError on malformed input (endpoint out of range, n out of range, bad edge shape).

igraph_topological_sort(int $n, array $edges): array
//   $n, $edges — same shape as above; edges are DIRECTED (u -> v).
//   →  list<int> — a topological ordering of the vertices: every vertex appears before all vertices
//                  it points to. The empty graph yields []. One valid ordering is returned.
//   throws ValueError on malformed input, or if the graph is not acyclic (no order exists).

igraph_is_connected(int $n, array $edges, bool $strong = false): bool
//   $n, $edges — same shape; edges are DIRECTED (u -> v).
//   $strong    — false (default): WEAK connectivity (edge direction ignored — is the graph in one
//                piece?). true: STRONG connectivity (every vertex reachable from every other).
//   →  bool. Per igraph: the 1-vertex graph is connected; the null graph (n=0) is not.
//   throws ValueError on malformed input.

igraph_connected_components(int $n, array $edges, bool $strong = false): array
//   $n, $edges — same shape; edges are DIRECTED (u -> v).
//   $strong    — false (default): WEAK components; true: STRONG components.
//   →  list<int> of length $n — membership[v] is the 0-based id of v's component (ids contiguous
//                [0, k)). Group vertices by id to recover the components. Null graph (n=0) → [].
//   throws ValueError on malformed input.

igraph_degree(int $n, array $edges, string $mode = 'all'): array
//   $n, $edges — same shape; edges are DIRECTED (u -> v).
//   $mode      — 'all' (default) total degree, 'in' in-degree, or 'out' out-degree.
//   →  list<int> of length $n — the degree of each vertex. Self-loops count twice for 'all',
//                once each for 'in'/'out'. Null graph (n=0) → [].
//   throws ValueError on malformed input or an unknown $mode.

igraph_is_simple(int $n, array $edges): bool
//   $n, $edges — same shape; edges are DIRECTED (u -> v).
//   →  bool — true iff no self-loops and no duplicate DIRECTED edges. Directions are considered,
//             so an anti-parallel pair (u->v and v->u) is simple; a repeated pair or self-loop is
//             not. This is the function that distinguishes multigraph input the others tolerate.
//   throws ValueError on malformed input.

igraph_is_tree(int $n, array $edges, string $mode = 'all'): bool
//   $n, $edges — same shape; edges are DIRECTED (u -> v).
//   $mode      — 'all' (default): the undirected graph is a tree (connected, n-1 edges, acyclic);
//                'out': a directed out-tree (edges point away from one root); 'in': an in-tree.
//   →  bool. The single-vertex graph is a tree; the null graph (n=0) is not.
//   throws ValueError on malformed input or an unknown $mode.

igraph_diameter(int $n, array $edges, bool $directed = true): int
//   $n, $edges — same shape; edges are DIRECTED (u -> v).
//   $directed  — true (default): follow edge directions; false: ignore them.
//   →  int — the diameter (longest shortest path, in edges), unweighted. For a disconnected graph
//            the longest FINITE shortest path is returned. A graph with < 2 vertices → 0.
//   throws ValueError on malformed input.

igraph_shortest_path_length(int $n, array $edges, int $from, int $to, bool $directed = true): int
//   $n, $edges — same shape; edges are DIRECTED (u -> v).
//   $from,$to  — source/target vertex ids (0-based, each in [0, n)).
//   $directed  — true (default): follow edge directions; false: ignore them.
//   →  int — number of edges on a shortest $from→$to path (0 if equal), or -1 if unreachable.
//   throws ValueError on malformed input or out-of-range $from/$to.

igraph_pagerank(int $n, array $edges, float $damping = 0.85, bool $directed = true): array
//   $n, $edges — same shape; edges are DIRECTED (u -> v).
//   $damping   — damping factor in [0, 1] (default 0.85). $directed — follow directions (default true).
//   →  list<float> of length $n — the PageRank score of each vertex (scores sum to ~1). Unweighted.
//   throws ValueError on malformed input or a $damping outside [0, 1].

igraph_betweenness(int $n, array $edges, bool $directed = true, bool $normalized = false): array
//   $n, $edges  — same shape; edges are DIRECTED (u -> v).
//   $directed   — follow directions (default true). $normalized — divide by the pair count → [0,1].
//   →  list<float> of length $n — the betweenness centrality of each vertex. Unweighted.
//   throws ValueError on malformed input.

igraph_closeness(int $n, array $edges, string $mode = 'out', bool $normalized = true): array
//   $n, $edges  — same shape; edges are DIRECTED (u -> v).
//   $mode       — 'out' (default) / 'in' / 'all' distance direction. $normalized — mean inverse
//                 distance (default) vs inverse summed distance.
//   →  list<float> of length $n — closeness centrality. A vertex that can reach no other is NAN
//                (isolated vertices, sinks in 'out' mode, the single-vertex graph). Unweighted.
//   throws ValueError on malformed input or an unknown $mode.

igraph_eigenvector_centrality(int $n, array $edges, bool $directed = false): array
//   $n, $edges  — same shape; edges are DIRECTED (u -> v).
//   $directed   — false (default): treat as undirected; true: follow out-edges.
//   →  list<float> of length $n — eigenvector centrality, scaled so the maximum is 1. Unweighted.
//   throws ValueError on malformed input.

igraph_transitivity(int $n, array $edges): float
//   $n, $edges  — same shape; the graph is read as UNDIRECTED (direction ignored).
//   →  float — global transitivity / clustering coefficient (closed triples / all connected
//              triples) in [0, 1]. A graph with no connected triple returns 0.
//   throws ValueError on malformed input.

igraph_girth(int $n, array $edges): int
//   $n, $edges  — same shape; read as UNDIRECTED (self-loops and multi-edges ignored).
//   →  int — length of the shortest cycle, or -1 if the graph is acyclic (a forest).
//   throws ValueError on malformed input.

igraph_edge_connectivity(int $n, array $edges, bool $directed = true): int
//   $n, $edges  — same shape; edges are DIRECTED (u -> v).
//   $directed   — true (default): directed edge connectivity (0 unless strongly connected);
//                 false: undirected edge connectivity.
//   →  int — minimum number of edges whose removal disconnects the graph (0 if already
//            disconnected, or < 2 vertices).
//   throws ValueError on malformed input.

igraph_minimum_spanning_tree(int $n, array $edges): array
//   $n, $edges  — same shape; the graph is read as UNDIRECTED and unweighted.
//   →  list<[int,int]> — the MST edges as [u,v] pairs. Unweighted, so it's any spanning tree
//                (n-1 edges when connected) or a spanning FOREST (n - #components edges) otherwise.
//   throws ValueError on malformed input.

igraph_articulation_points(int $n, array $edges): array
//   $n, $edges  — same shape; the graph is read as UNDIRECTED.
//   →  list<int> — the cut vertices (whose removal increases the component count). Order is
//                igraph's; sort for a canonical list.
//   throws ValueError on malformed input.

igraph_coreness(int $n, array $edges, string $mode = 'all'): array
//   $n, $edges  — same shape; edges are DIRECTED (u -> v).
//   $mode       — 'all' (default) ignore direction; 'in'/'out' use in-/out-degree.
//   →  list<int> of length $n — each vertex's coreness (largest k with the vertex in the k-core).
//   throws ValueError on malformed input or an unknown $mode.

igraph_vertex_connectivity(int $n, array $edges, bool $directed = true): int
//   $n, $edges  — same shape; edges are DIRECTED (u -> v).
//   $directed   — true (default): directed; false: undirected.
//   →  int — minimum number of vertices whose removal disconnects the graph. 0 for a disconnected
//            graph (or, directed, one not strongly connected) and for < 2 vertices.
//   throws ValueError on malformed input.

igraph_reciprocity(int $n, array $edges): float
//   $n, $edges  — same shape; edges are DIRECTED (u -> v).
//   →  float — fraction of directed edges that are reciprocated (u->v with v->u), in [0, 1].
//              Self-loops ignored. A graph with no edges returns NAN (undefined).
//   throws ValueError on malformed input.

igraph_assortativity_degree(int $n, array $edges, bool $directed = true): float
//   $n, $edges  — same shape; edges are DIRECTED (u -> v).
//   $directed   — true (default): out-degree vs in-degree; false: undirected.
//   →  float — degree assortativity coefficient in [-1, 1] (Pearson correlation of endpoint
//              degrees). NAN when undefined (all degrees equal, or too few edges).
//   throws ValueError on malformed input.

igraph_community_multilevel(int $n, array $edges, float $resolution = 1.0): array
//   $n, $edges  — same shape; the graph is read as UNDIRECTED.
//   $resolution — resolution parameter (default 1.0); higher → more, smaller communities.
//   →  list<int> of length $n — community id per vertex (modularity-maximizing Louvain partition,
//                ids contiguous [0, k)). Randomized tie-breaking, so ids/ordering may vary.
//   throws ValueError on malformed input.

igraph_harmonic_centrality(int $n, array $edges, string $mode = 'out', bool $normalized = true): array
//   $n, $edges  — same shape; edges are DIRECTED (u -> v).
//   $mode       — 'out' (default) / 'in' / 'all'. $normalized — divide by n-1 (default) or raw sum.
//   →  list<float> of length $n — harmonic centrality (sum of inverse distances; unreachable
//                vertices contribute 0). Finite on disconnected graphs — no NAN (unlike closeness).
//   throws ValueError on malformed input or an unknown $mode.

igraph_average_path_length(int $n, array $edges, bool $directed = true): float
//   $n, $edges  — same shape; edges are DIRECTED (u -> v). $directed — follow directions (default).
//   →  float — mean shortest-path length over all reachable ordered pairs (unweighted). A graph
//                with no reachable pair (< 2 vertices or edgeless) returns NAN.
//   throws ValueError on malformed input.

igraph_is_bipartite(int $n, array $edges): bool
//   $n, $edges  — same shape; the graph is read as UNDIRECTED.
//   →  bool — true iff the graph is 2-colourable (no odd cycle). Empty/edgeless are bipartite; a
//                self-loop makes it non-bipartite.
//   throws ValueError on malformed input.

igraph_eccentricity(int $n, array $edges, string $mode = 'all'): array
//   $n, $edges  — same shape; edges are DIRECTED (u -> v). $mode — 'all' (default)/'out'/'in'.
//   →  list<int> of length $n — each vertex's eccentricity: greatest distance to any REACHABLE
//                vertex (unreachable ignored, so finite; a lone vertex is 0). Unweighted.
//   throws ValueError on malformed input or an unknown $mode.

igraph_radius(int $n, array $edges, string $mode = 'all'): int
//   Graph radius (minimum vertex eccentricity), unweighted; < 1 vertex → 0.

igraph_density(int $n, array $edges, bool $loops = false): float
//   Ratio of actual to possible edges (directed count n*(n-1), +n with $loops).

igraph_mean_degree(int $n, array $edges, bool $loops = true): float
//   Average vertex degree; NAN for the null graph.

igraph_maxdegree(int $n, array $edges, string $mode = 'all'): int
//   Maximum vertex degree ('all'/'out'/'in'); null graph → 0.

igraph_is_forest(int $n, array $edges, string $mode = 'all'): bool
//   Whether the graph is a forest (disjoint trees) in the $mode sense.

igraph_has_loop(int $n, array $edges): bool           // any self-loop present
igraph_has_multiple(int $n, array $edges): bool       // any duplicate DIRECTED edge present

igraph_is_complete(int $n, array $edges): bool
//   Whether every pair of vertices is adjacent (UNDIRECTED reading).

igraph_is_perfect(int $n, array $edges): bool
//   Whether the (UNDIRECTED) graph is perfect (no odd hole/antihole).

igraph_transitivity_local(int $n, array $edges): array
//   list<float> — local clustering coefficient per vertex (UNDIRECTED); degree-<2 → 0.

igraph_transitivity_avglocal(int $n, array $edges): float
//   Average of the local clustering coefficients (UNDIRECTED).

igraph_constraint(int $n, array $edges): array
//   list<float> — Burt's constraint per vertex (UNDIRECTED); no-neighbour vertex → NAN.

igraph_bridges(int $n, array $edges): array
//   list<[int,int]> — the bridge edges (removal increases components), UNDIRECTED.

igraph_community_label_propagation(int $n, array $edges): array
//   list<int> — community membership from label propagation (UNDIRECTED, randomized).

igraph_version(): string
//   → the linked (vendored) libigraph version, e.g. "1.0.1".

The input shape mirrors the sibling planarity($n, $edges). More igraph capabilities will be added behind the same tiny-surface, single-cleanup-path discipline.

How igraph is vendored

Unlike planarity (a flat set of .c files listed in config.m4), igraph is a large CMake library with generated headers and bundled dependencies, so we pin it as a git submodule (vendor/igraph @ tag 1.0.1) and drive its own build: config.m4 runs cmake to produce a self-contained static libigraph.a (all deps internal), then links it into the extension. See vendor/VENDOR.md for the full rationale and the licensing note.

License: igraph is GPL-2.0-or-later; because we statically link it, so is this extension.

Build (host)

Requires cmake, flex, bison, libxml2-dev, and a C++ compiler in addition to the usual phpize toolchain (see vendor/VENDOR.md). Fetch the submodule first:

git submodule update --init vendor/igraph
phpize && ./configure --enable-igraph && make

The first ./configure builds the vendored igraph static library (several minutes); it is cached by the presence of vendor/igraph-build/src/libigraph.a, so re-make is fast.

Two PHP installs may coexist on a dev host. The extension loads in the distro php (/usr/bin/php8.5); a static /usr/local/bin/php build can have dynamic loading disabled. Use the binary that loads it:

/usr/bin/php8.5 -d extension="$(pwd)/modules/igraph.so" --ri igraph

Tests

The behavioural suite is .phpt (PHP's native extension test format) under tests/, run by the run-tests.php harness that phpize drops in — no phpunit/composer needed.

make test                      # after phpize && ./configure --enable-igraph && make

On a host without the full build toolchain, the bundled image builds the extension and runs the suite:

docker build -t php-igraph .
docker run --rm php-igraph                 # runs `make test`