Support for NetworkX Multigraph?

[neurorishika]

Hi,
I have been trying to plot multigraphs using netgraph but it seems it is not supported. Here is a minimal example and error message:

# Simple example of a graph with two nodes and two parallel edges between them
G = nx.MultiDiGraph()
G.add_nodes_from(range(2))
G.add_edge(0, 1, key=0, weight=1)
G.add_edge(0, 1, key=1, weight=1)
# plot the graph using netgraph
Graph(G,node_labels={0:'a',1:'b'},edge_layout='curved',arrows=True)

Error Trace:

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
/var/folders/8t/nc0dxp394llg8dc047hmbqsh0000gn/T/ipykernel_54472/3976304237.py in <module>
      5 G.add_edge(0, 1, key=1, weight=1)
      6 # plot the graph using netgraph
----> 7 Graph(G,node_labels={0:'a',1:'b'},edge_layout='curved',arrows=True)

/opt/anaconda3/lib/python3.9/site-packages/netgraph/_main.py in __init__(self, graph, edge_cmap, *args, **kwargs)
   1352             kwargs.setdefault('node_zorder', node_zorder)
   1353 
-> 1354         super().__init__(edges, *args, **kwargs)
   1355 
   1356 

/opt/anaconda3/lib/python3.9/site-packages/netgraph/_main.py in __init__(self, edges, nodes, node_layout, node_layout_kwargs, node_shape, node_size, node_edge_width, node_color, node_edge_color, node_alpha, node_zorder, node_labels, node_label_offset, node_label_fontdict, edge_width, edge_color, edge_alpha, edge_zorder, arrows, edge_layout, edge_layout_kwargs, edge_labels, edge_label_position, edge_label_rotate, edge_label_fontdict, origin, scale, prettify, ax, *args, **kwargs)
    267                  *args, **kwargs
    268     ):
--> 269         self.edges = _parse_edge_list(edges)
    270 
    271         self.nodes = self._initialize_nodes(nodes)

/opt/anaconda3/lib/python3.9/site-packages/netgraph/_parser.py in _parse_edge_list(edges)
    138     """Ensures that the type of edges is a list, and each edge is a 2-tuple."""
    139     # Edge list may be an array, or a list of lists. We want a list of tuples.
--> 140     return [(source, target) for (source, target) in edges]
    141 
    142 

/opt/anaconda3/lib/python3.9/site-packages/netgraph/_parser.py in <listcomp>(.0)
    138     """Ensures that the type of edges is a list, and each edge is a 2-tuple."""
    139     # Edge list may be an array, or a list of lists. We want a list of tuples.
--> 140     return [(source, target) for (source, target) in edges]
    141 
    142 

ValueError: too many values to unpack (expected 2)

[paulbrodersen]

Hi,

Unfortunately, netgraph doesn't properly support multi-graphs, yet. However, it is a planned feature, albeit still some way off.

Currently, if given a multi-graph, netgraph should raise a warning, remove duplicate edges, and plot the simplified graph.
So the error that you encountered isn't the expected behaviour either. I will look into that presently.

In the meantime, I know that pyvis has some support for multigraphs, although not without issues. If the graphs are layered multi-graphs, there is also pymnet, or this stackoverflow answer. All in all, however, the state of multigraph visualisation tools is pretty poor in python, so personally, I would probably export my network to a dot file, and then draw the graph with graphviz.

[kcharlie2]

I was able to plot MultiGraph and MultiDiGraph objects (with collapsed edges) by modifying _parse_edge_list in _parser.py as shown below.

def _parse_edge_list(edges):
    # Edge list may be an array, or a list of lists. We want a list of tuples.
    # return [(source, target) for (source, target) in edges] 
    return [(edge[0], edge[1]) for edge in edges]

[paulbrodersen]

Hi @kcharlie2, the _handle_multigraphs decorator should do the collapsing for you. What error did you run into before implementing this change?

def _handle_multigraphs(parser):
    """Raise a warning if the given graph appears to be a multigraph, and remove duplicate edges."""
    def wrapped_parser(graph, *args, **kwargs):
        nodes, edges, edge_weight = parser(graph, *args, **kwargs)

        new_edges = list(set([(edge[0], edge[1]) for edge in edges]))
        if len(new_edges) < len(edges):
            msg = "Multi-graphs are not properly supported. Duplicate edges are plotted as a single edge; edge weights (if any) are summed."
            warnings.warn(msg)
            if edge_weight: # sum weights
                new_edge_weight = dict()
                for edge, weight in edge_weight.items():
                    if (edge[0], edge[1]) in new_edge_weight:
                        new_edge_weight[(edge[0], edge[1])] += weight
                    else:
                        new_edge_weight[(edge[0], edge[1])] = weight
            else:
                new_edge_weight = edge_weight
            return nodes, new_edges, new_edge_weight

        return nodes, edges, edge_weight

    return wrapped_parser

[kcharlie2]

It looks like the collapsed edges are only returned if there are duplicate edges. If you have a networkx.MultiDiGraph with no duplicate edges, new_edges isn't returned. I think fixing this as simple as making the second to last line above

        # return nodes, edges, edge_weight
        return nodes, new_edges, edge_weight

[tschoellhorn]

I have this problem as well and it would be great if that issue might be mitigated. Would a pull-request help?

[paulbrodersen]

Pull requests are always welcome but a minimum working example (including data) that results in an error would help me most. Then I can write some tests to prevent this and similar issues arising in the future.

[dgrigonis]

Very desirable feature. A lot of issues drawing multi-graphs across the graph library space. Some libraries support edge_drawing, but can't plot labels, others can draw only 2 edges, etc, etc. In short, couldn't find anything that just does the plot fine with all the data nicely.

For now I wrote custom drawing functions for networkx that handle multiedges with labels, but I would rather see it implemented in a place where it belongs.

I hacked the nx.draw_edges function to be called multiple times for edges and extended function from stack to handle more than 2 labels:
Stack link

[paulbrodersen]

Multi-graph support is already implemented on the dev branch.

pip install https://github.com/paulbrodersen/netgraph/archive/dev.zip

Edge labels track edges as they should.

import numpy as np
import matplotlib.pyplot as plt

from netgraph import MultiGraph # see also: InteractiveMultiGraph, EditableMultiGraph

# Define the multi-graph.
# Adjacency matrix stacks (i.e. arrays with dimensions (layers, nodes, nodes)),
# networkx multi-graph, and igraph multi-graph objects are also supported.
my_multigraph = [
    (0, 1, 0),
    (0, 1, 1),
    (0, 1, 2),
    (1, 1, 0),
    (1, 2, 0),
    (2, 0, 0),
    (0, 2, 0),
    (0, 2, 1),
]

# Color edges by edge ID / type.
colors = ['tab:blue', 'tab:orange', 'tab:red']
edge_color = {(source, target, eid) : colors[eid] for (source, target, eid) in my_multigraph}

# Plot
node_positions = {
    0 : np.array([0.2, 0.2]),
    1 : np.array([0.5, 0.7]),
    2 : np.array([0.8, 0.2]),
}
MultiGraph(
    my_multigraph,
    node_layout=node_positions,
    edge_color=edge_color,
    edge_layout='curved',
    edge_layout_kwargs=dict(bundle_parallel_edges=False),
    edge_labels=True,
    edge_label_fontdict=dict(fontsize=6),
    arrows=True,
)
plt.show()

I am in the process of preparing a new major release. User-exposed functions and classes should have remained backwards compatible, but internally, I have changed a few things, primarily to facilitate writing the multi-graph classes.
However, all of that is done now, and I am just doing some cleanup work in other parts of the library that need some love.
In other words: I won't be making any backwards-compatibility breaking changes to the multi-graph classes any time soon, so they are already safe to use, even if the corresponding code hasn't been properly released via the usual channels.

[dgrigonis]

That's great. I will wait for a release then. Don't like messing with dev versions if there is no big need for it.

[paulbrodersen]

Just a heads up that it might still be some time until the next release (months, not days). This library is maintained by an army of one, and mostly only during lunch breaks, as that one dude has a toddler and wife at home that both demand attention as well.

[dgrigonis]

Understandable.

Changed my mind.

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
from netgraph import MultiGraph

G = nx.MultiDiGraph()
G.add_edge('a', 'b', w=1)
G.add_edge('a', 'b', w=2)
G.add_edge('a', 'b', w=3)
G.add_edge('b', 'c', w=4)
G.add_edge('b', 'c', w=5)
G.add_edge('c', 'a', w=6)

# Color edges by edge ID / type.
colors = ['tab:blue', 'tab:orange', 'tab:red']
edge_color = {(source, target, eid) : colors[eid] for (source, target, eid) in G.edges(keys=True)}
node_positions = {
    'a': np.array([0.2, 0.8]),
    'b' : np.array([0.5, 0.7]),
    'c' : np.array([0.8, 0.2]),
}
edge_labels = {v[:3]: f'w={v[3]}' for v in G.edges(keys=True, data='w')}
MultiGraph(G,
    node_layout=node_positions,
    node_labels=True,
    edge_color=edge_color,
    edge_layout='curved',
    edge_layout_kwargs=dict(bundle_parallel_edges=False),
    edge_labels=edge_labels,
    edge_label_fontdict=dict(fontsize=6),
    arrows=True
)
plt.show()

It might be convenient if edge labels could take in string of an attribute to use. But it would only save 1 fairly short line of code so not sure it's worth it...

Do any of interactive and editable graphs work for MultiGraphs?

[dgrigonis]

Ok, checked it myself. All works, just 1 bug:

https://github.com/paulbrodersen/netgraph/blob/dev/netgraph/_interactive_variants.py#L804

graph is not passed further here. Replacing with this worked for me.

super().__init__(graph, *args, **kwargs)

By "all works", I mean it plots ok, but not sure about editing. But I use 'qtagg' backend. wx and tkinter are pain to install on mac so can't check.

[paulbrodersen]

It might be convenient if edge labels could take in string of an attribute to use. But it would only save 1 fairly short line of code so not sure it's worth it...

It would be convenient and I did think about it but the way everything else is structured (or at least was structured at the time) meant that the code complexity would have increased quite a bit. Hard to justify working for long on such a small convenience feature when there are elephants in the room -- as e.g. multi-graph support.

graph is not passed further here. Replacing with this worked for me.

Good catch. I messed around with that part just the other day, when I was trying to improve the readability of some of the more cryptic parts of the code base. Go figure. Will fix presently.

I mean it plots ok, but not sure about editing. But I use 'qtagg' backend. wx and tkinter are pain to install on mac so can't check.

Editing should work, too, if you are using QtAgg. I have only had issues with the MacOsX backend.

[dgrigonis]

It plots, but can't do anything with it. I installed PyQt6. I have never seen editable matplotlib plots, maybe I am missing something?

[paulbrodersen]

Are you using an IDE such as pycharm or a notebook such as google colabs or jupyter?

[dgrigonis]

Are you using an IDE or notebook?

Just running script from shell. I get a pop-up window, which is interactive. I can zoom, drag, etc. But can't drag nodes.

[paulbrodersen]

Are you retaining a reference to the InteractiveMultiGraph / EditableMultiGraph object? Otherwise, it will be garbage collected once the figure is drawn as explained here and then cannot be altered further.

g = EditableMultiGraph(my_multigraph, ...)
plt.show()

[dgrigonis]

That was it, thank you!

Great work. I am starting to use graphs more and more, this library will definitely be useful. Not only works, but looks super nice too.

[paulbrodersen]

Cheers. Let me know if you find any other bugs. ;-)

[dgrigonis]

Same bug here:
https://github.com/paulbrodersen/netgraph/blob/dev/netgraph/_interactive_variants.py#L130

[dgrigonis]

Ok, here are some thoughts.

Say I just want to draw a double(Directed) /multi - edge graph. Most important thing is that edge lines do not overlap and labels are seen clearly.

"arc" is too exotic.
"bundled" has similar issues to "curved" below, but additionally: It has its own progress bar, indicating it can be expensive. (Also PB floods my terminal)

So 2 options left: "curved" and straight.

"curved" edge layout is unreliable. Tried playing with it, but it's just too "risky" for me to use it. And same issue of overlap is occurring in both Graph and MultiGraph.

Simple Graph's "straight" doesn't do well (nx.DiGraph):

MultiGraph does a good job with "straight" edge layout:

So my suggestion would be to have analogous "straight" method for a simple Graph. And as it is reliable and works fairly well, add extra argument to control the distance between edge lines. This way it would be the one reliable option that the user can count on.

Update:
There is a simple solution: Convert nx.DiGraph to nx.MultiDiGraph and then use netgraph.MultiGraph. Good enough for me.

[dgrigonis]

One more thing, these label params work nice:

edge_label_fontdict=dict(
                fontsize=6, bbox=dict(color='white', pad=0)),

pad is essential, otherwise big background boxes may overlap nearby labels if graph is zoomed out.

I wouldn't suggest this if it was top level parameter, but it is 3 layers down, thought maybe having a good default is convenient.

[paulbrodersen]

"arc" is too exotic.

Whatever that means... (I do get it though. It's mostly there for arc diagrams.)

"bundled" has similar issues to "curved" below, but additionally: It has its own progress bar, indicating it can be expensive. (Also PB floods my terminal)

"bundled" is very expensive. Anything above a few hundred edges can take minutes and even hours to compute. Also, it will never work well with edge labels as edges are meant to bundle and hence overlap. So, yeah.
The PB should not flood your terminal though. What shell are you running on what operating system?

"curved" edge layout is unreliable. Tried playing with it, but it's just too "risky" for me to use it.

I am working on making it more reliable but I do know what you mean. When I first implemented it, the algorithm seemed nice on the surface (a straightforward extension of the Fruchterman-Reingold algrithm for node layouts). Since then, it has been the bane of my existence as it is very brittle and you keep running into edge cases. Easily the most time spent / line of code in the whole library.

There is a simple solution: Convert nx.DiGraph to nx.MultiDiGraph and then use netgraph.MultiGraph. Good enough for me.

I think this is the best solution for this particular problem. I really don't want to complicate the basic "straight" edge routing as that one needs to be fast to support a variety of computations.

[dgrigonis]

Does one get notifications from closed issues when someone comments?

Just in case one doesn't. I found one more issue and commented in: #76

[dgrigonis]

Few missing imports are missing from _interactive_multigraph_classes.py for latest dev version:

from matplotlib.backend_bases import key_press_handler
from ._artists import EdgeArtist
from ._parser import is_order_zero, is_empty, parse_graph

Maybe it would be a good time to merge it to master? :)

[paulbrodersen]

I will fix the imports on the dev branch, but I can't merge yet, as I am still in the process of implementing other features for this release. I would rather not have multiple major releases in rapid succession.

[paulbrodersen]

@dgrigonis I just found a few minutes to look into your import issues.

Few missing imports are missing from _interactive_multigraph_classes.py for latest dev version:

What exactly is the problem? As far as I can tell, the imports are all there?

[dgrigonis]

When I open the link, I can not see them. 🤷‍♂️

[paulbrodersen]

l. 26: from matplotlib.backend_bases import key_press_handler
l. 33. EdgeArtist
l. 42 from ._parser import is_order_zero, is_empty, parse_graph

[dgrigonis]

Now I see them too. Strange stuff.

[paulbrodersen]

Maybe your computer is being haunted by a disgruntled github employee turned poltergeist. I am glad it's sorted now though (yes?).

[dgrigonis]

I hope I get to have a chat with him. I have a few questions...

Yes, all good.