I believe that for practical network-analysis work, the following is the single most important issue with Graph
. This problem is going to be very difficult to fix. Therefore, it would be encouraging for us users to hear not just a promise that it will be fixed, but something about how it could be fixed at all without compromising existing functionality.
Property
API design is flawed because it can't handle multigraphs
Properties are accessed like this in WL:
PropertyValue[{obj, item}, propname]
For edge properties of graphs, this looks like
PropertyValue[{graph, v1 <-> v2}, propname]
In other words, in order to access a property of an edge, we need to refer to that edge by its endpoints (v1
and v2
).
Now what if there are multiple edges between the very same two vertices?
Graph[{1<->2, 1<->2}]
It is simply not possible to distinguish these two edges using this notation, so it's not possible to work with edge properties of multigraphs. (Also, if we try to do it anyway, we get no clear error message about what is going wrong. Things just fail silently. This sort of behaviour is unfortunately standard for Graph
stuff, see redmine #101this should be discussed too.)
The API simply provides no way to unambiguously refer to one of these two edges.
This extends to styling too since edge styles are stored as properties. It is not possible to style parallel edges differently.
I think that this is one of the most serious issues with Graph
because it's not just a simple wrong behaviour bug which could in principle be just corrected. The flaw is in the design of the API. It seems to me that a proper fix would involve changing the API and breaking backwards compatibility. Because of this, I am very worried that this will never get fixed.
I asked about this countless times through various channels and never got a proper response (of course, it is a very difficult issue).
Supporting edge properties for multigraphs is absolutely critical if Mathematica wants to be a serious tool for network analysis.
This issue also ties into several others, e.g. Import
mishandling graph exchange formats when they can contain multi-edges with properties.
Related issues
Graph property system is not clearly described in the documentation, so we have to do some guesswork to be able to work effectively. See e.g. https://mathematica.stackexchange.com/q/118196/12 For example, certain build-in properties like EdgeWeight
, EdgeCapacity
and EdgeCost
do work with multigraphs. However, this is undocumented and one must take special care to avoid using the standard property API. The fact that these do work is what keeps Mathematica usable for me for many network analysis tasks. Unfortunately, working with these requires some esoteric knowledge ... (because of the lack of proper documentation).
Property inheritance was added to M12.0, but it's still completely undocumented (other than a single mention in the list of new features). Some of the details are not obvious and can't be guessed. This also ties into the issue with edge properties for multigraphs. E.g., functions like SimpleGraph
now handle the EdgeWeight
of multigraphs and add them up when merging parallel edges. This is extremely useful and completely undocumented.
Suggestion for interim solution
Above, I mentioned multiple times that this is the single biggest issue with Graph
for my work, and also that this is going to be very difficult to fix.
I'd like to suggest an interim solution. EdgeWeight
, etc. also sort of work with multigraphs, but this is undocumented, and therefore effectively unsupported. Please document, polish, and support this limited solution until a more general solution can be implemented.
This is one of the most talked-about issues with Graph
The following is a list of links to discussions about this issue to demonstrate that many users care about it:
How do other libraries deal with this?
How do other network analysis libraries (in other programming languages) deal with this issue?
- igraph refers to edges by their index (their position in the edge list)
- networkx uses an extra "tag" to distinguish parallel edges. There's
(v1, v2, tag1)
and (v1, v2, tag2)
.
- Some C++ libraries like LEMON use pointers to edge objects, but this sort of solution doesn't apply to WL
It's not just about edge propertiesit's about the distinguishability of edges
There's more to this problem than just edge properties. In practice, this is a big issue when doing network analysis (working with empirical data). But similar issues also come up in graph theory (pure mathematics). For example, when working with planar graph (or other topological topics), using multigraphs instead of simple graphs is a natural choice. We may ask:
Which edges belong to a face of a planar graph? We need a notation to distinguish between parallel edges.
When specifying a combinatorial embedding of a graph (i.e. an ordering of edges around each vertex), we also need to distinguish edges. We need a notation to distinguish them.
When finding cycle bases, the same problem arises. Mathematica has FindFundamentalCycles
but its result is ambiguous because parallel edges are indistinguishable. Mathematica also has EdgeCycleMatrix
, which does not suffer from this problem because effectively it refers to edges by their index (i.e. row i
of the matrix corresponds to the i
th edge of the graph).
We may even want to first find the faces of a planar graph, then look at the weights (i.e. property) of edges for each face. This is not just a theoretical example. Here's a paper which does exactly this. It should be feasible to implement the analysis technique from this paper in WL.
Another example where cycles and multi-edges come up is resistor networks (electrical circuits). Think resistors in parallel (multi-edges with weights).