fqqdk/igraph (0.9.0)
Installation
{
"repositories": [{
"type": "composer",
"url": "composer require fqqdk/igraph:0.9.0About this package
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_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`
Dependencies
Dependencies
| ID | Version |
|---|---|
| php | >=8.1 |