igraph
feat: add `as_veincidence_matrix()` for vertex-edge incidence matrices
Implements vertex-edge incidence matrix computation as requested in #1122. The incidence matrix B has vertices as rows and edges as columns, encoding graph connectivity.
Implementation
-
Function:
as_veincidence_matrix(graph, attr = NULL, names = TRUE, sparse = igraph_opt("sparsematrices")) - Dense and sparse implementations for performance on large graphs
-
Matrix semantics:
- Undirected: B[v,e] = 1 (incident), 2 (loop), 0 (not incident)
- Directed: B[v,e] = -1 (tail), +1 (head), 0 (loop or not incident)
- Weighted: values scaled by edge weights via
attrparameter
Usage
# Directed weighted graph with multiple edges
g <- make_graph(c(1,2, 1,2, 2,3), directed = TRUE)
E(g)$weight <- c(2, 3, 5)
as_veincidence_matrix(g, attr = "weight")
# [,1] [,2] [,3]
# 1 -2 -3 0
# 2 2 3 -5
# 3 0 0 5
# Undirected graph with self-loop
g <- make_graph(c(1,1, 1,2), directed = FALSE)
as_veincidence_matrix(g)
# [,1] [,2]
# 1 2 1
# 2 0 1
Notes
- Named after
as_biadjacency_matrix()convention rather thanlaplacian_matrix()style - R implementation (C implementation deferred per maintainer feedback)
- 81 test cases covering directed/undirected, weighted/unweighted, loops, multi-edges, sparse matrices
Original prompt
This section details on the original issue you should resolve
<issue_title>Nice to have: vertex_edge_incidence_matrix().</issue_title> <issue_description>What is the feature or improvement you would like to see?
Nice to have: function to calculate the vertex-edge incidence matrix of a graph. 20240118 - Added argument weights = NULL 20240119 - Added example graph, directed, multiple, weighted. 20240123 - Added example graph with self-loop.
Description
The vertex-edge incidence matrix of a graph.
Usage
as_ve_incidence_matrix <- function( graph , mode = c("all", "out", "in") , loops , multiple , weights = NULL , names = FALSE , attr = "label" , sparse = igraph_opt("sparsematrices") )
Depending on personal taste, we can choose one of the following alternatives:
- as_vertex_edge_incidence_matrix()
- as_veincidence_matrix(), as in as_biadjacency_matrix().
- vertex_edge_incidence_matrix(), as in laplacian_matrix.
- ve_incidence_matrix(), shorter version.
- …
Arguments
graph
- simple or multi-edge
- directed, undirected
- weighted, unweighted
- named, unnamed
- with or without loops
- sparse, non-sparse
mode
- as in incident(), distances().
loops
- As in igraph Reference Manual.
- igraph_adjlist_init_empty — Initializes an empty adjacency list. p. 187.
multiple
- As in igraph Reference Manual.
weights
- as in distances(), cluster_leiden(). For example, Wikipedia, wiki/Incidence_matrix, chapter Weighted graphs.
names
- If NA, ignore names.
- If NULL, copy vertex name and edge label from graph if present, to dimnames.
- If matrix, then copy to dimnames.
attr
- name of the edge attr to be used for colnames of the matrix, default is "label".
sparse
- as in laplacian_matrix()
Details
This function calculates the vertex-edge incidence matrix B of graph g. If g is undirected, Bxe = 1 when vertex x is incident with edge e, 0 otherwise. If g is directed, Bxe = −1,1,0 when vertex x is the head of edge e, the tail of e, or not on e, respectively.
If weights are taken into account, then -1, 1 becomes -w, w, where w is the weight of edge e.
Value
A possibly sparse matrix B with rows indexed by the vertices and columns indexed by the edges.
See Also
The function laplacian_matrix() computes the out-degree Laplacian matrix. To allow the calculation of a symmetric Laplacian matrix, the function should be modified to support mode="all", in particular to ignore the orientation of edges. Currently, a workaround is to convert the graph to its undirected version.
The function as_adjacency_matrix() includes weights using attr = "weight".
See also Github/igraph/rigraph/issue igraph/rigraph#906, as_adjacency_matrix() should use weights instead of attr parameter.
See also Github/igraph/rigraph/issues igraph/rigraph#1125, Treat self-loops in igraph functions consistently.
Examples
library(igraph)
g1 <- make_ring(3, circular=FALSE) # Undirected, simple.
g2 <- graph(c(1,2,1,2,2,3), directed=FALSE ) # Undirected, multi edge.
g2w <- graph(c(1,2,2,3), directed=FALSE ) # Undirected
E(g2w)$weight <- c(2,1); E(g2w)$label <- E(g2w)$weight # Weighted.
g3 <- make_ring(3,circular=FALSE, directed=TRUE) # Directed, simple.
g4 <- graph(c(1,2,1,2,2,3) ) # Directed, multi edge.
g4w<- g4; # Directed, multi edge.
E(g4w)$weight<- c(2,3, 5); E(g4w)$label<- E(g4w)$weight # Weighted.
# Named graph, undirected. From wiki/Incidence_matrix.
g5 <- graph_from_literal(1-2, 1-3, 1-4, 3-4)
E(g5)$label <- paste0("e", seq_len(gsize(g5)) )
# Named graph, directed, From /wiki/Directed_graph (-B).
g6 <- graph_from_literal(a-+b-+c-+a, a-+d, simplify=FALSE)
g6$name <- "g6"; E(g6)$label <- c("1", "2", "3", "4")
# Undirected graph with loops, e.g. edge incident with a single vertex.
# An undirected loop adds two or one to the degree of its vertex (depending on parameters).
g7 <- graph(c(1,1,1,1,1,2,1,2), directed=FALSE)
# A directed loop adds 0 to the degree of its vertex.
g8 <- graph(c(1,1,1,1,1,2,1,2), directed=TRUE)
# Print incidence matrices.
for (g in list(g2, g4w, g6, g7, g8) )
{cat("\n");print(g); print(as_ve_incidence_matrix(g, weights=NULL))}
# Expected output.
# IGRAPH 3371287 U--- 3 3 --
# + edges from 3371287:
# [1] 1--2 1--2 2--3
# [,1] [,2] [,3]
# [1,] 1 1 0
# [2,] 1 1 1
# [3,] 0 0 1
#
# IGRAPH 337f2fd D-W- 3 3 --
# + attr: weight (e/n), label (e/n)
# + edges from 337f2fd:
# [1] 1->2 1->2 2->3
# [,1] [,2] [,3]
# [1,] -2 -3 0
# [2,] 2 3 -5
# [3,] 0 0 5
...
</details>
- Fixes igraph/rigraph#1122
<!-- START COPILOT CODING AGENT TIPS -->
---
💬 We'd love your input! Share your thoughts on Copilot coding agent in our [2 minute survey](https://gh.io/copilot-coding-agent-survey).
