Copy graph?

[mforbes]

Is there a way to copy a graph? I am trying to implement L1-TV denoising as discussed in Multiscale Flat Norm Signatures for Shapes and Images, which can reuse the original network, but needs to update the tedges multiple times. Here is the algorithm:

import numpy as np
import maxflow

u_noise = <some image with data between 0 and 1>
threshold = 0.5  # Threshold
lam = 0.2        # Curvature

g = maxflow.Graph[float]()
nodeids = g.add_grid_nodes(u_noise.shape)
a, b, c = 0.1221, 0.0476, 0.0454
structure = np.array([
    [0, c, 0, c, 0],
    [c, b, a, b, c],
    [0, a, 0, a, 0],
    [c, b, a, b, c],
    [0, c, 0, c, 0]])
g.add_grid_edges(nodeids, structure=structure, symmetric=True)

# I would like to store this graph, and then make copies for processing
# with different thresholds and smoothing parameters:

g1 = g.copy()   # <<<<<<<<<<<< How to do this?
sources = u_noise >= threshold
g1.add_grid_tedges(nodeids, lam * sources, lam * (1 - sources))
g1.maxflow()
u_clean = g.get_grid_segments(nodeids)

Thanks for wrapping this!

P.S. Is there any support for different boundary conditions? I assume that the current implementation uses Dirichlet boundaries... I suppose I could just update the boundary edges, but it would be nice if g.add_grid_edges() could do this when sliding the structure window... I can open a new ticket for this if reasonable.

[pmneila]

Hi, @mforbes

Thank you for your question. Just implemented a copy method and periodic boundary conditions. Just update the library to the latest version with

python -m pip install --upgrade PyMaxflow

Once you have updated the library, you can copy a graph by using the following code:

g1 = g.copy()

If you would like to add edges with periodic boundary conditions, you can use the following code:

g.add_grid_edges(nodeids, structure=structure, symmetric=False, periodic=True)

If you only want periodic behavior in certain directions, you can pass a list or array of booleans, for example:

# Periodic boundary condition only along the first dimension
g.add_grid_edges(nodeids, structure=structure, symmetric=False, periodic=[True, False])

Also, note that given that your structure is symmetric, you should set symmetric=False. This is because symmetric=True would double the capacity of each edge (once because of the symmetry of the structure and once because of the symmetric=True setting). I guess the symmetric parameter is pretty misleading and and I'm considering removing it in the future (tbh, I don't even remember why I included it in the first place). It's only there for backwards compatibility at this point.

Hope that helps.

[mforbes]

@pmneila Thanks! That works nicely, except that if I used symmetric=False I need to set weights=2... The doubling seems to be important (unless I messed up another factor somewhere).