Alternate API for adding edges

[LeeKamentsky]

I have a problem where a node has different edge weights to its connected nodes and since it's a large problem, I'd rather not use add_edge for each edge, so I'd like to add Graph.add_edges(i, j, cap, rev_cap) where i, j, cap and rev_cap are vectors. It's trivial to get the Cython to run this efficiently in a loop.

I will submit a PR with my suggested addition.

[pmneila]

Hi,

If I understand correctly, you want to set different weights from a single node to many nodes. I think you can do that with add_grid_edges with appropriate nodeids and structure.

For example:

import numpy as np
import maxflow

import networkx as nx
import matplotlib.pyplot as plt

# Create a graph with integer capacities.
g = maxflow.Graph[int]()

# Add a few nodes
nodes = g.add_nodes(20)

# We want to connect i to the rest
i = nodes[0]
rest = nodes[1:]
num_connections = len(rest)

# Some arbitrary weights
weights = np.arange(num_connections) + 1

# Create an auxiliary layout of the nodes for setting the edges:
# [[i, i, i, i,...],
#  [j, k, l, m,...]]
nodeids = np.array([[i] * num_connections, rest])

# Create edges in the down direction with given weights
structure = np.zeros((3, 3))
structure[2, 1] = 1
g.add_grid_edges(nodeids, weights, structure)

# Plot the graph
nxg = g.get_nx_graph()
nxg.remove_nodes_from(['s', 't'])
nx.draw_circular(nxg)
plt.show()

This is the resulting graph:

Let me know if I misunderstood your question.

[LeeKamentsky]

I think that wouldn't quite work. I have something like this (not the actual code so pls forgive typos):

import numpy as np
i, j = [_[1:-1, 1:-1].flatten() for _ in np.indices(img.shape)]
edges = np.vstack([np.column_stack([i, j, i+ioff, j+joff] for ioff, joff in ((-1, 0), (0, -1), (1, 0), (0, 1))])
i0, j0, i1, j1 = [edges[idx] for idx in range(4)]
weights = compute_weight(img, i0, j0, i1, j1)
graph = maxflow.Graph[float]()
nodeids = graph.add_grid_nodes(img.shape)
for idx in range(edges.shape[0]):
    graph.add_edge(nodeid, i0[idx], j0[idx], i1[idx], j1[idx], weights[idx], weights[idx]

So every 4-connected edge from a pixel can have an arbitrary weight to its neighbor, assigned by compute_weight. I don't think there's a simple way to do it other than iterate through 4 * width * height pixels, currently.

[pmneila]

Hi,

You can set all edges in a given direction at a time:

import numpy as np
import maxflow

def create_structure(ioff, joff):
    res = np.zeros((3, 3))
    res[ioff+1, joff+1] = 1
    return res

img = np.random.random_sample(size=(10, 10))
i, j = [_[1:-1, 1:-1].flatten() for _ in np.indices(img.shape)]

graph = maxflow.Graph[float]()
nodeids = graph.add_grid_nodes(img.shape)

for ioff, joff in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
    structure = create_structure(ioff, joff)
    i1 = i + ioff
    j1 = j + joff
    weights = compute_weight(img, i, j, i1, j1)
    # I'm assuming weights has the same shape as nodeids. Crop/reshape otherwise.
    graph.add_grid_edges(nodeids, weights, structure)

Of course, a better solution for your case would be having a function that accepts arrays of src nodes, dst nodes and corresponding weights. That would be memory inefficient though, since you have to create several arrays (srsc, dsts and weights) several times larger than the original image. For very large images that might be unfeasible. Nevertheless, if you submit a PR with the implementation of this function I will be happy to accept it.