Related Wolfram Community question.
I am looking for the fastest way to achieve the following:
Given a Graph, retrieve its edge list in terms of vertex indices (not actual vertices).
For example, given
Graph[{a, b, c}, {a <-> b, a <-> c}]
I am looking to get the output
{{1,2}, {1,3}}
as a packed array. Alternatively the flattened version would do just as well:
{1,2, 1,3}
Here {1,2} corresponds to UndirectedEdge[a,b] as a has vertex index 1 and b has vertex index 2.
What I have so far is the very straightforward
idxEdgeList[graph_] :=
Developer`ToPackedArray[
List @@@ EdgeList[graph] /. AssociationThread[VertexList[graph] -> Range@VertexCount[graph]]
]
g = GridGraph[{250,250}];
idxEdgeList[g]; // AbsoluteTiming
(* 0.27 seconds *)
Using undocumented features or poking inside of the Graph object is okay for as long as the method is proven to be reliable for 10.0 – 10.2 for various directed and undirected, simple and non-simple graphs. Multigraphs (multiple edges between the same vertices) must be supported, but mixed graphs (both directed and undirected edges) do not. A documented way is of course always preferred!
This is admittedly a fairly boring performance tuning problem, but this turned out to be a bottleneck in some cases, and I don't want to lose out on any possible performance improvements I may have missed.
Use case: The edge list will eventually be passed to a LibraryLink function. What hasn't occurred to me before typing up the question is that maybe I should be using sparse arrays, which are directly supported by LibraryLink.
Update:
The solution proposed by @halmir, through IndexGraph, works well for the GridGraph above. But it is not fast for all graphs. In particular:
g = GridGraph[{250, 250}];
IndexGraph[g]; // AbsoluteTiming
(* {4.*10^-6, Null} *)
g = Graph[VertexList[g], EdgeList[g]];
IndexGraph[g]; // AbsoluteTiming
(* {0.259276, Null} *)
We are now back to the same speed as the Replace method. Re-creating the graph from its vertex and edge lists somehow made IndexGraph be slow on it, and no matter what I try I cannot convert the graph back to a "fast" format.
The SparseArray-based method is much faster, and proves that it is technically possible to extract the information quickly. But it has a big problem: it does not preserve the edge order, which means that I cannot match up the edges with an EdgeWeight vector anymore. It's also difficult to handle for multigraphs, though that would be solvable if I could preserve the ordering ...
Update / 2017
@Ramble suggests using the IncidenceMatrix of the graph. The fastest way I found so far is to process the incidence matrix in C, using LibraryLink, to extract the index-based edge list.
According to the documentation, an incidence matrix uses the following values:
-1represents the starting point of a directed edge1represents the endpoint of a directed edge or an undirected egde2represents an undirected self-loop-2represents a directed self-loop
This is not accurate. Between 10.0-11.2, both directed and undirected self-loops are represented with a positive 2. This prevents the correct representation of mixed graphs (MixedGraphQ), but I do not need that anyway. Multigraphs are easily handled by this approach.
This is now available in IGraph/M 0.3.95 as IGEdgeIndexList.
This function is actually faster than EdgeList, and can be used to implement many edge-list based operations efficiently. An index-based edge list can be used to reconstruct a graph using the undocumented syntax Graph[vertexList, indexEdgeList], e.g. Graph[{a,b}, {{1,2}}].
Here's the LTemplate code I used for this:
mma::IntTensorRef incidenceToEdgeList(mma::SparseMatrixRef<mint> im, bool directed) {
auto edgeList = mma::makeVector<mint>(2*im.cols());
if (directed) {
for (auto it = im.begin(); it != im.end(); ++it) {
switch (*it) {
case -1:
edgeList[2*it.col()] = it.row();
break;
case 1:
edgeList[2*it.col() + 1] = it.row();
break;
case 2:
case -2:
edgeList[2*it.col()] = it.row();
edgeList[2*it.col() + 1] = it.row();
break;
default:
throw mma::LibraryError("Invalid incidence matrix.");
}
}
} else {
for (auto &el : edgeList)
el = -1;
for (auto it = im.begin(); it != im.end(); ++it) {
switch (*it) {
case 1:
if (edgeList[2*it.col()] == -1)
edgeList[2*it.col()] = it.row();
else
edgeList[2*it.col() + 1] = it.row();
break;
case 2:
edgeList[2*it.col()] = it.row();
edgeList[2*it.col() + 1] = it.row();
break;
default:
throw mma::LibraryError("Invalid incidence matrix.");
}
}
}
return edgeList;
}
