Getting started with using iGraph for max flow

Usage
1

I’m wondering what the procedure is in iGraph for adding in edges with capacity one at a time. In NetworkX, to find max flow, I would do something like:

> G = nx.Graph()
> for edge in edges_with_capacity: # get edge info format like ('a', 'b', 5)
>    G.add_edge(edge[0], edge[1], capacity=edge[2])
> max_flow = nx.maximum_flow_value(G, 'a', 'z')

1 . The issue is that in edges_with_capacity I will have repeated node names (that are the same node) or even edges (that I would want to update). In NetworkX, a new node is only added when adding an edge if the node name doesn’t already exist (otherwise the existing node is used for constructing the new edge) and adding a duplicate edge updates the existing edge, is this something I have to handle manually in iGraph?

2.When using the maxflow method of an iGraph graph, I think using the string node name for source/sink is not supported? If so, what’s the ‘correct way’ of extracting the source and sink node index given string names of the nodes, is it just g.vs[“name”].index(“name of node”)?

3.Similar to the above, what’s the ‘correct way’ to retrieve the edge capacity given just the string name of the to/from vertex?

2

In igraph, adding an edge to a nonexistent vertex yields a ValueError:

>>> g.add_edge("a", "b")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "[...]/igraph/basic.py", line 24, in _add_edge
    graph.add_edges([(source, target)])
  File "[...]/igraph/basic.py", line 42, in _add_edges
    res = GraphBase.add_edges(graph, es)
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ValueError: no such vertex: 'a'

But it is easy to create a helper function:

def add_edge_by_vertex_name(g: Graph, src: str, dest: str) -> None:
    if src not in g.vs["name"]:
        g.add_vertex(src)
    if dest not in g.vs["name"]:
        g.add_vertex(dest)
    g.add_edge(src, dest)

Re updating an existing edge: you need to check manually whether the edge exists already or not as it is possible to add multiple edges between the same pair of vertices, so doing something like g.add_edge("a", "b", capacity=123) will add a new edge even if another edge exists already.

So, again, extending our helper function:

def update_weight(g: Graph, src: str, dest: str, **kwds) -> None:
    if src not in g.vs["name"]:
        g.add_vertex(src)
    if dest not in g.vs["name"]:
        g.add_vertex(dest)
    eid = g.get_eid(src, dest, error=False)
    if eid < 0:
        eid = g.add_edge(src, dest).eid
    for k, v in kwds.items():
        g.es[eid][k] = v

  1. igraph supports referring to a node by its name in every place where a numeric vertex ID is accepted. Names are looked up from the name vertex attribute. If you find a place in igraph where a vertex ID works but a vertex name does not then it’s most likely a bug.

  2. Something like this:

eid = g.get_eid(source, target)
print(g.es[eid]["capacity"])

There are alternatives like g.es.select(_source=source, _target=target) but IMHO g.get_eid() is more explicit.