Flows, cuts and traversal

Operation counts of the push-relabel solver.

typedef struct og_maxflow_stats_t {
    og_int_t nopush;      /* pushes */
    og_int_t norelabel;   /* relabels */
    og_int_t nogap;       /* gap heuristic firings */
    og_int_t nogapnodes;  /* vertices dropped by the gap heuristic */
    og_int_t nobfs;       /* exact relabellings by backward breadth-first search */
} og_maxflow_stats_t;

Filled by maxflow and maxflow_value when a non-NULL pointer is passed. The counts describe Open Graph's own solver and are not comparable with other implementations.

Parameters

• nopush Pushes.
• norelabel Relabels.
• nogap Times the gap heuristic fired.
• nogapnodes Vertices the gap heuristic lifted out.
• nobfs Exact relabellings by backward breadth-first search; at least 1, the initial labelling.

Checked

Type; nobfs >= 1 is checked. The numbers are not comparable with igraph's.

C name

og_maxflow_stats_t

In notebooks

Og.MaxflowStats

igraph 1.0

igraph_maxflow_stats_t

See also

maxflow, maxflow_value

Type of the bfs callback.

typedef og_error_t og_bfshandler_t(
    const og_t *graph,
    og_int_t vid,
    og_int_t pred,
    og_int_t succ,
    og_int_t rank,
    og_int_t dist,
    void *extra
);

Called once for every visited vertex, when it is taken from the queue. The return value steers the search: OG_SUCCESS continues, OG_STOP ends it normally, any other code aborts it and is returned by bfs.

Parameters

• graph The graph being searched.
• vid The vertex being visited.
• pred The vertex visited just before it in the same tree, -1 for none.
• succ The vertex that will be visited next in the same tree, -1 for none.
• rank Its position in the visiting order.
• dist Its distance from the root of its tree.
• extra The extra pointer given to bfs.

Returns

OG_SUCCESS to continue, OG_STOP to end the search normally, or an error code to abort it.

Checked

Callback arguments checked against the outputs on every oracle run; OG_STOP and error returns unit-tested.

C name

og_bfshandler_t

In notebooks

Og.Bfshandler

igraph 1.0

igraph_bfshandler_t

See also

bfs

Type of the dfs callbacks.

typedef og_error_t og_dfshandler_t(
    const og_t *graph,
    og_int_t vid,
    og_int_t dist,
    void *extra
);

The same type serves both callbacks: in_callback receives a vertex when it is discovered, out_callback when its subtree is finished. The return value steers the search: OG_SUCCESS continues, OG_STOP ends it normally, any other code aborts it and is returned by dfs.

Parameters

• graph The graph being searched.
• vid The vertex discovered or finished.
• dist Its depth in the search tree.
• extra The extra pointer given to dfs.

Returns

OG_SUCCESS to continue, OG_STOP to end the search normally, or an error code to abort it.

Checked

Callback sequences checked against order and order_out on every oracle run.

C name

og_dfshandler_t

In notebooks

Og.Dfshandler

igraph 1.0

igraph_dfshandler_t

See also

dfs

What st_vertex_connectivity does when source and target are adjacent.

typedef enum og_vconn_nei_t {
    OG_VCONN_NEI_ERROR = 0,           /* fail with OG_EINVAL */
    OG_VCONN_NEI_NUMBER_OF_NODES = 1, /* answer the number of vertices */
    OG_VCONN_NEI_IGNORE = 2,          /* disregard the direct edges */
    OG_VCONN_NEI_NEGATIVE = 3         /* answer -1 */
} og_vconn_nei_t;

No vertex set can separate two adjacent vertices; this enum picks the answer. Other values make st_vertex_connectivity fail with OG_EINVAL.

Parameters

• OG_VCONN_NEI_ERROR 0: fail with OG_EINVAL.
• OG_VCONN_NEI_NUMBER_OF_NODES 1: answer the vertex count.
• OG_VCONN_NEI_IGNORE 2: leave the direct edges out and compute the connectivity without them.
• OG_VCONN_NEI_NEGATIVE 3: answer -1.

Checked

Enum; every value is tested through st_vertex_connectivity against python-igraph.

C name

og_vconn_nei_t

In notebooks

Og.VconnNei

igraph 1.0

igraph_vconn_nei_t

See also

st_vertex_connectivity

What random_walk does at a vertex it cannot leave.

typedef enum og_random_walk_stuck_t {
    OG_RANDOM_WALK_STUCK_ERROR = 0,   /* truncate the walk and fail with OG_ERWSTUCK */
    OG_RANDOM_WALK_STUCK_RETURN = 1   /* truncate the walk and succeed */
} og_random_walk_stuck_t;

Other values make random_walk fail with OG_EINVAL.

Parameters

• OG_RANDOM_WALK_STUCK_ERROR 0: stop, keep the shortened walk and fail with OG_ERWSTUCK.
• OG_RANDOM_WALK_STUCK_RETURN 1: stop and return the shortened walk with success.

Checked

Enum; both values unit-tested with random_walk.

C name

og_random_walk_stuck_t

In notebooks

Og.RandomWalkStuck

igraph 1.0

igraph_random_walk_stuck_t

See also

random_walk

Maximum flow from a source to a target, with the flow on every edge and a minimum cut.

og_error_t og_maxflow(
    const og_t *graph,
    og_real_t *value,
    og_vector_t *flow,
    og_vector_int_t *cut,
    og_vector_int_t *partition,
    og_vector_int_t *partition2,
    og_int_t source,
    og_int_t target,
    const og_vector_t *capacity,
    og_maxflow_stats_t *stats
);

Finds a largest flow from source to target that respects the edge capacities and, on request, the flow on every edge and a minimum cut. In an undirected graph an edge carries flow either way up to its capacity; flow[e] is positive when the flow runs from the edge's smaller endpoint id to its larger one, negative otherwise. Self-loops carry no flow.

The solver is push-relabel (Goldberg and Tarjan 1988) with highest-label selection, the gap heuristic and global relabelling (Cherkassky and Goldberg 1997). A maximum flow is rarely unique; when flow is requested, Open Graph routes it the way igraph does (rules reconstructed by black-box observation), so the vector equals igraph's on almost all graphs. The reported cut is the one with the largest source side: partition holds every vertex that cannot reach the target in the residual network, partition2 the others (both in increasing order), and cut the ids of the edges from the first to the second (for undirected graphs, those crossing in their stored orientation first, then the rest). This cut does not depend on how the flow was routed.

With +inf capacities the value is infinite exactly when a path of infinite edges joins source to target; otherwise each infinite capacity is replaced by a finite stand-in above every finite cut, and the flow vector is a feasible flow.

Parameters

• graph The input graph.
• value Output (may be NULL): the flow value.
• flow Output (may be NULL): the flow on every edge, sign convention as described.
• cut Output (may be NULL): ids of the edges in the minimum cut.
• partition Output (may be NULL): the source side of the cut, increasing.
• partition2 Output (may be NULL): the target side of the cut, increasing.
• source The source vertex.
• target The target vertex.
• capacity Capacity of every edge (non-negative, not NaN, +inf allowed), or NULL for capacity 1 everywhere.
• stats Output (may be NULL): operation counts of the solver.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVVID source or target is not a vertex of the graph.
• OG_EINVAL source and target are the same vertex.
• OG_EINVAL capacity does not have one entry per edge, or an entry is negative or NaN.
• OG_ENOMEM Memory runs out.

Complexity

O(|V|^2 sqrt(|E|)) in the worst case (highest-label push-relabel); far less in practice.

Checked

Used by OpenBI's engine. Value, cut and both partitions identical to python-igraph on 604 cases. The flow vector equals python-igraph's edge by edge on 578 of 581 compared cases and on 99.4% of 1,519 graphs up to 300 vertices (about 75-80% of random graphs of 300-1,500 vertices); every vector is a valid maximum flow. 0.1-0.9x python-igraph's time on graphs of 100k edges. With +inf capacities a feasible flow is returned where python-igraph gives NaN entries; negative or NaN capacities are refused (python-igraph accepts them).

C name

og_maxflow

In notebooks

Og.Maxflow

igraph 1.0

igraph_maxflow

See also

maxflow_value, st_mincut, maxflow_stats_t, all_st_mincuts, gomory_hu_tree

og_t g;
og_vector_t cap, flow;
og_vector_int_t cut;
og_real_t value;

/* edges 0: 0->1, 1: 0->2, 2: 1->3, 3: 2->3, 4: 1->2 */
og_small(&g, 4, OG_DIRECTED, 0,1, 0,2, 1,3, 2,3, 1,2, -1);
og_vector_init_real(&cap, 5, 3.0, 2.0, 2.0, 3.0, 1.0);
og_vector_init(&flow, 0);
og_vector_int_init(&cut, 0);
og_maxflow(&g, &value, &flow, &cut, NULL, NULL, 0, 3, &cap, NULL);
/* value 5; flow 3 2 2 3 1; cut holds edges 2 and 3 */
og_vector_int_destroy(&cut);
og_vector_destroy(&flow);
og_vector_destroy(&cap);
og_destroy(&g);

Value of a maximum flow between two vertices.

og_error_t og_maxflow_value(
    const og_t *graph,
    og_real_t *value,
    og_int_t source,
    og_int_t target,
    const og_vector_t *capacity,
    og_maxflow_stats_t *stats
);

Runs the push-relabel solver of maxflow and stops once the value is known: no flow vector, no cut. Capacities as in maxflow; NULL means capacity 1 on every edge, and +inf is allowed (the value is then infinite exactly when a path of infinite edges joins source to target).

Parameters

• graph The input graph.
• value Output (may be NULL): the flow value.
• source The source vertex.
• target The target vertex.
• capacity Capacity of every edge (non-negative, not NaN, +inf allowed), or NULL for capacity 1 everywhere.
• stats Output (may be NULL): operation counts of the solver.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVVID source or target is not a vertex of the graph.
• OG_EINVAL source and target are the same vertex.
• OG_EINVAL capacity does not have one entry per edge, or an entry is negative or NaN.
• OG_ENOMEM Memory runs out.

Complexity

As maxflow.

Checked

Same fixtures as maxflow; 0.06-0.47x python-igraph's time on four 100k-edge graphs.

C name

og_maxflow_value

In notebooks

Og.MaxflowValue

igraph 1.0

igraph_maxflow_value

See also

maxflow, st_mincut_value, st_edge_connectivity

Minimum s-t cut: the cheapest edge set whose removal separates the target from the source.

og_error_t og_st_mincut(
    const og_t *graph,
    og_real_t *value,
    og_vector_int_t *cut,
    og_vector_int_t *partition,
    og_vector_int_t *partition2,
    og_int_t source,
    og_int_t target,
    const og_vector_t *capacity
);

maxflow without the flow vector: value is the cut's total capacity (equal to the maximum flow), partition the source side (every vertex that cannot reach the target in the residual network), partition2 the rest, and cut the edges between them. In a directed graph only edges from partition to partition2 are in the cut; in an undirected graph the edges crossing in their stored orientation come first, then those crossing the other way.

Parameters

• graph The input graph.
• value Output (may be NULL): the capacity of the cut.
• cut Output (may be NULL): ids of the edges in the cut.
• partition Output (may be NULL): the source side, increasing.
• partition2 Output (may be NULL): the target side, increasing.
• source The source vertex.
• target The target vertex.
• capacity Capacity of every edge (non-negative, not NaN, +inf allowed), or NULL for capacity 1 everywhere.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVVID source or target is not a vertex of the graph.
• OG_EINVAL source and target are the same vertex.
• OG_EINVAL capacity does not have one entry per edge, or an entry is negative or NaN.
• OG_ENOMEM Memory runs out.

Complexity

As maxflow.

Checked

Value, cut and partitions identical to python-igraph's st_mincut on the 344 maximum flow cases and the 260 of the independent check.

C name

og_st_mincut

In notebooks

Og.StMincut

igraph 1.0

igraph_st_mincut

See also

maxflow, st_mincut_value, all_st_mincuts, mincut

Capacity of a minimum cut between two vertices.

og_error_t og_st_mincut_value(
    const og_t *graph,
    og_real_t *value,
    og_int_t source,
    og_int_t target,
    const og_vector_t *capacity
);

Equals the maximum flow value (max-flow min-cut theorem, Ford and Fulkerson 1956) and is computed by maxflow_value. Capacities as in maxflow.

Parameters

• graph The input graph.
• value Output (may be NULL): the capacity of a minimum cut.
• source The source vertex.
• target The target vertex.
• capacity Capacity of every edge (non-negative, not NaN, +inf allowed), or NULL for capacity 1 everywhere.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVVID source or target is not a vertex of the graph.
• OG_EINVAL source and target are the same vertex.
• OG_EINVAL capacity does not have one entry per edge, or an entry is negative or NaN.
• OG_ENOMEM Memory runs out.

Complexity

As maxflow.

Checked

Same fixtures as maxflow.

C name

og_st_mincut_value

In notebooks

Og.StMincutValue

igraph 1.0

igraph_st_mincut_value

See also

st_mincut, maxflow_value

Lists every minimal s-t edge cut of a directed graph.

og_error_t og_all_st_cuts(
    const og_t *graph,
    og_vector_int_list_t *cuts,
    og_vector_int_list_t *partition1s,
    og_int_t source,
    og_int_t target
);

Each cut is the set of edges leaving a source side S, where S holds the source but not the target, every vertex of S is reachable from the source inside S, and every edge leaving S ends at a vertex that can still reach the target outside S. No edge set of the list contains another. Capacities play no role. Vertices on no source-target path are ignored.

The search is Provan and Shier's (1996) binary partition with pivots taken from a dominator tree of the reversed graph (Lengauer and Tarjan), so each cut comes out once. Each cut lists its edge ids in increasing order; partition1s gets, per cut, everything the source still reaches once the cut is removed, in increasing order. The list order is python-igraph's.

Parameters

• graph The input graph.
• cuts Output (may be NULL): the cuts, as edge-id vectors; cleared first.
• partition1s Output (may be NULL): the source side of each cut; cleared first.
• source The source vertex.
• target The target vertex.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_UNIMPLEMENTED The graph is undirected.
• OG_EINVVID source or target is not a vertex of the graph.
• OG_EINVAL source and target are the same vertex.
• OG_ENOMEM Memory runs out.

Complexity

O(|E| alpha) per cut after O(|V| + |E|) preparation, alpha the inverse Ackermann function of the dominator computation.

Checked

Cuts, partitions and order identical to python-igraph on 300 fixture listings and 2,184 one-off ones (up to 2,000 cuts each), and to a brute force over all vertex subsets on 400 digraphs. A family with 3^9 cuts runs in 43 ms (python-igraph 848 ms). Where python-igraph aborts the process (source = target, invalid vertex), Open Graph returns an error code.

C name

og_all_st_cuts

In notebooks

Og.AllStCuts

igraph 1.0

igraph_all_st_cuts

See also

all_st_mincuts, st_mincut, dominator_tree

Lists every minimum-capacity s-t edge cut of a directed graph.

og_error_t og_all_st_mincuts(
    const og_t *graph,
    og_real_t *value,
    og_vector_int_list_t *cuts,
    og_vector_int_list_t *partition1s,
    og_int_t source,
    og_int_t target,
    const og_vector_t *capacity
);

One maximum flow is computed on the edges between vertices that lie on some source-target path. The minimum cuts are then the closed vertex sets of its residual network (Picard and Queyranne 1980), enumerated with the pivot search of all_st_cuts, so each cut appears once. value receives the minimum cut capacity.

Capacities must be strictly positive; NULL means 1 on every edge. Each cut lists its edge ids in increasing order, and partition1s gets the vertices the source still reaches without the cut. When the target cannot be reached the value is 0 and no cut is listed.

Parameters

• graph The input graph.
• value Output (may be NULL): the minimum cut capacity.
• cuts Output (may be NULL): the minimum cuts, as edge-id vectors; cleared first.
• partition1s Output (may be NULL): the source side of each cut; cleared first.
• source The source vertex.
• target The target vertex.
• capacity Capacity of every edge (strictly positive), or NULL for capacity 1 everywhere.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_UNIMPLEMENTED The graph is undirected.
• OG_EINVVID source or target is not a vertex of the graph.
• OG_EINVAL source and target are the same vertex.
• OG_EINVAL capacity does not have one entry per edge, or an entry is not strictly positive (NaN included).
• OG_ENOMEM Memory runs out.

Complexity

One maximum flow, then O(|V| + |E|) per node of the search tree, which has one leaf per minimum cut.

Checked

Value and cuts identical to python-igraph (as sets) on 210 fixture and 1,410 one-off listings, and to a brute force on 400 digraphs. Order identical on all 210 fixture listings; of listings with three or more cuts about 88% follow python-igraph's order, the rest list the same cuts in another order.

C name

og_all_st_mincuts

In notebooks

Og.AllStMincuts

igraph 1.0

igraph_all_st_mincuts

See also

all_st_cuts, st_mincut, maxflow

Minimum edge cut of the whole graph.

og_error_t og_mincut(
    const og_t *graph,
    og_real_t *value,
    og_vector_int_t *partition,
    og_vector_int_t *partition2,
    og_vector_int_t *cut,
    const og_vector_t *capacity
);

Finds edges of least total capacity whose removal disconnects the graph; for a directed graph, leaves it not strongly connected. Undirected graphs use the Stoer-Wagner algorithm (1997) with a binary heap: the first phase reaching the smallest cut wins, partition lists that side in the order its vertices were merged, partition2 the rest in increasing order. Directed graphs take the smallest of the cuts from vertex 0 to every other vertex and back, with maximum flows that stop once they cannot beat the best so far; partition is the source side of that cut. cut lists the crossing edges in increasing id (for directed graphs those from partition to partition2).

capacity NULL means 1 on every edge. A disconnected undirected graph gives 0 (partition: the component of vertex 0). A single vertex gives +inf; a directed graph whose every cut is infinite reports empty partitions and cut.

Parameters

• graph The input graph.
• value Output (may be NULL): the capacity of the minimum cut.
• partition Output (may be NULL): one side of the cut.
• partition2 Output (may be NULL): the other side, increasing.
• cut Output (may be NULL): ids of the crossing edges.
• capacity Capacity of every edge (non-negative, not NaN), or NULL for capacity 1 everywhere.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL capacity does not have one entry per edge, or an entry is negative or NaN.
• OG_ENOMEM Memory runs out.

Complexity

Undirected: O(|V| |E| log |V|). Directed: 2(|V| - 1) maximum flows.

Checked

Values identical to python-igraph on 490 cases. Directed: identical outputs. Undirected: 352 of 360 identical including partition order; 5 list the same side in another order and 3 report another minimum cut of the same value (a different tie among equal heap keys). Zero-weight undirected graphs are not compared with python-igraph 1.0; there Open Graph returns a valid cut of value zero.

C name

og_mincut

In notebooks

Og.Mincut

igraph 1.0

igraph_mincut

See also

mincut_value, st_mincut, edge_connectivity, gomory_hu_tree

Total capacity of a minimum edge cut of the whole graph.

og_error_t og_mincut_value(
    const og_t *graph,
    og_real_t *res,
    const og_vector_t *capacity
);

The value part of mincut. A disconnected graph gives 0 and a single vertex +inf (the undirected null graph gives 0, a directed graph with fewer than two vertices +inf).

Parameters

• graph The input graph.
• res Output (may be NULL): the capacity of a minimum cut.
• capacity Capacity of every edge (non-negative, not NaN), or NULL for capacity 1 everywhere.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL capacity does not have one entry per edge, or an entry is negative or NaN.
• OG_ENOMEM Memory runs out.

Complexity

As mincut.

Checked

Identical to python-igraph on the 360 mincut cases and the independent check.

C name

og_mincut_value

In notebooks

Og.MincutValue

igraph 1.0

igraph_mincut_value

See also

mincut, edge_connectivity, adhesion

Gomory-Hu tree: a tree holding the minimum cut value of every vertex pair.

og_error_t og_gomory_hu_tree(
    const og_t *graph,
    og_t *tree,
    og_vector_t *flows,
    const og_vector_t *capacity
);

For an undirected graph with edge capacities, builds a tree on the same vertices such that, for any two vertices u and v, the minimum u-v cut capacity in the graph equals the smallest flow value on the tree path between them. Built with Gusfield's (1990) method: |V| - 1 maximum flows, no graph contraction. Tree edge i joins vertex i + 1 and its final tree neighbour, and flows[i] holds that edge's value.

Parameters

• graph The input graph.
• tree Output: an uninitialised og_t. The function creates the result graph; free it with destroy. Undirected, |V| vertices and |V| - 1 edges.
• flows Output (may be NULL): an initialised vector, resized to |V| - 1.
• capacity Capacity of every edge (non-negative, not NaN), or NULL for capacity 1 everywhere.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL The graph is directed.
• OG_EINVAL capacity does not have one entry per edge, or an entry is negative or NaN.
• OG_ENOMEM Memory runs out.

Complexity

|V| - 1 maximum flows.

Checked

Tree edges in order and flow values identical to python-igraph on 285 cases. flows is an initialised output vector here, like every output vector of Open Graph. With capacities near 1e-12 one tree in 64 differed in one edge through rounding (both trees valid).

C name

og_gomory_hu_tree

In notebooks

Og.GomoryHuTree

igraph 1.0

igraph_gomory_hu_tree

See also

maxflow, mincut

Smallest number of edges whose removal leaves no path from the source to the target.

og_error_t og_st_edge_connectivity(
    const og_t *graph,
    og_int_t *res,
    og_int_t source,
    og_int_t target
);

By Menger's theorem this is the maximum flow from source to target with capacity 1 on every edge, and also the most paths from source to target that share no edge. Directed graphs use the edge directions.

Parameters

• graph The input graph.
• res Output (may be NULL): the edge connectivity of the pair.
• source The source vertex.
• target The target vertex.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVVID source or target is not a vertex of the graph.
• OG_EINVAL source and target are the same vertex.
• OG_ENOMEM Memory runs out.

Complexity

One maximum flow with unit capacities.

Checked

python-igraph's edge_connectivity(source, target) on 302 graphs with up to 3 pairs each.

C name

og_st_edge_connectivity

In notebooks

Og.StEdgeConnectivity

igraph 1.0

igraph_st_edge_connectivity

See also

edge_connectivity, edge_disjoint_paths, st_vertex_connectivity

Smallest number of edges whose removal disconnects the graph.

og_error_t og_edge_connectivity(
    const og_t *graph,
    og_int_t *res,
    og_bool_t checks
);

For a directed graph, disconnects means: no longer strongly connected. Computed as mincut_value with capacity 1 on every edge. With checks = true two shortcuts come first: a graph that is not (strongly) connected gives 0, and a graph with a vertex of degree 1 (in- or out-degree for directed graphs) gives 1. Graphs with fewer than two vertices give 0.

Parameters

• graph The input graph.
• res Output (may be NULL): the edge connectivity.
• checks Try the quick answers above before the minimum cut.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_ENOMEM Memory runs out.

Complexity

As mincut with unit capacities; O(|V| + |E|) when a check decides.

Checked

checks true and false on 302 graphs (random, dense, complete graphs of 1-6 vertices).

C name

og_edge_connectivity

In notebooks

Og.EdgeConnectivity

igraph 1.0

igraph_edge_connectivity

See also

adhesion, mincut_value, vertex_connectivity, st_edge_connectivity

Smallest number of vertices whose removal leaves no path from the source to the target.

og_error_t og_st_vertex_connectivity(
    const og_t *graph,
    og_int_t *res,
    og_int_t source,
    og_int_t target,
    og_vconn_nei_t neighbors
);

Source and target are never removed. Computed as a unit-capacity maximum flow on the split network, in which each vertex is an entry and an exit copy joined by an arc of capacity 1.

When source and target are adjacent no vertex set separates them, and neighbors decides: OG_VCONN_NEI_ERROR fails with OG_EINVAL, OG_VCONN_NEI_NEGATIVE answers -1, OG_VCONN_NEI_NUMBER_OF_NODES answers the vertex count, and OG_VCONN_NEI_IGNORE leaves the direct edges out and computes the connectivity without them.

Parameters

• graph The input graph.
• res Output (may be NULL): the vertex connectivity of the pair.
• source The source vertex.
• target The target vertex.
• neighbors What to do when source and target are adjacent (vconn_nei_t).

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL source or target is not a vertex (OG_EINVAL here, as igraph reports it), they are the same vertex, neighbors is not a known value, or they are adjacent with OG_VCONN_NEI_ERROR.
• OG_ENOMEM Memory runs out.

Complexity

One unit-capacity maximum flow on a network of 2|V| vertices.

Checked

Every neighbors option, error codes included, on 302 graphs with up to 3 pairs each.

C name

og_st_vertex_connectivity

In notebooks

Og.StVertexConnectivity

igraph 1.0

igraph_st_vertex_connectivity

See also

vconn_nei_t, vertex_connectivity, vertex_disjoint_paths, even_tarjan_reduction

Smallest number of vertices whose removal disconnects the graph.

og_error_t og_vertex_connectivity(
    const og_t *graph,
    og_int_t *res,
    og_bool_t checks
);

Also written kappa(G); for directed graphs, removal must leave the graph not strongly connected. A complete graph on n vertices gives n - 1, and a single vertex 0. Computed with maximum flows on the split network between non-adjacent pairs; following Even (1975) only pairs that involve one of the first kappa + 1 vertices are needed, and each flow stops as soon as it reaches the best value so far. With checks = true a graph that is not (strongly) connected gives 0 and one with a vertex of degree 1 gives 1, without any flow.

Parameters

• graph The input graph.
• res Output (may be NULL): the vertex connectivity.
• checks Try the quick answers above before the flows.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_ENOMEM Memory runs out.

Complexity

O((kappa + 1) |V|) maximum flows (both directions for directed graphs), each on 2|V| vertices.

Checked

checks true and false on 302 graphs, plus 240 dense, complete-minus-a-few, multi-edge, regular and Kautz graphs, all identical.

C name

og_vertex_connectivity

In notebooks

Og.VertexConnectivity

igraph 1.0

igraph_vertex_connectivity

See also

cohesion, st_vertex_connectivity, edge_connectivity, minimum_size_separators

Largest number of source-target paths that share no edge.

og_error_t og_edge_disjoint_paths(
    const og_t *graph,
    og_int_t *res,
    og_int_t source,
    og_int_t target
);

Equal to the edge connectivity of the pair by Menger's theorem; computed by st_edge_connectivity. The paths may share vertices.

Parameters

• graph The input graph.
• res Output (may be NULL): how many edge-disjoint paths exist.
• source The source vertex.
• target The target vertex.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVVID source or target is not a vertex of the graph.
• OG_EINVAL source and target are the same vertex.
• OG_ENOMEM Memory runs out.

Complexity

One maximum flow with unit capacities.

Checked

Same fixture as st_edge_connectivity.

C name

og_edge_disjoint_paths

In notebooks

Og.EdgeDisjointPaths

igraph 1.0

igraph_edge_disjoint_paths

See also

st_edge_connectivity, vertex_disjoint_paths

Largest number of source-target paths that share no vertex apart from their ends.

og_error_t og_vertex_disjoint_paths(
    const og_t *graph,
    og_int_t *res,
    og_int_t source,
    og_int_t target
);

Each direct edge between source and target is a path on its own. The result is the number of such edges plus the vertex connectivity of the pair with those edges left out.

Parameters

• graph The input graph.
• res Output (may be NULL): how many vertex-disjoint paths exist.
• source The source vertex.
• target The target vertex.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVVID source or target is not a vertex of the graph.
• OG_EINVAL source and target are the same vertex.
• OG_ENOMEM Memory runs out.

Complexity

One unit-capacity maximum flow on a network of 2|V| vertices.

Checked

Expected values built from python-igraph as connectivity with neighbours ignored plus the direct edges (python-igraph's vertex_disjoint_paths is an alias of vertex_connectivity), 302 graphs.

C name

og_vertex_disjoint_paths

In notebooks

Og.VertexDisjointPaths

igraph 1.0

igraph_vertex_disjoint_paths

See also

st_vertex_connectivity, edge_disjoint_paths

Adhesion of a graph, which is its edge connectivity.

og_error_t og_adhesion(const og_t *graph, og_int_t *res, og_bool_t checks);

The same computation as edge_connectivity, under the name used in work on structural cohesion (White and Harary 2001).

Parameters

• graph The input graph.
• res Output (may be NULL): the adhesion.
• checks Try the quick answers of edge_connectivity first.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_ENOMEM Memory runs out.

Complexity

As edge_connectivity.

Checked

Same fixture as edge_connectivity.

C name

og_adhesion

In notebooks

Og.Adhesion

igraph 1.0

igraph_adhesion

See also

edge_connectivity, cohesion

Cohesion of a graph, which is its vertex connectivity.

og_error_t og_cohesion(const og_t *graph, og_int_t *res, og_bool_t checks);

The same computation as vertex_connectivity, under the name used in work on structural cohesion (White and Harary 2001).

Parameters

• graph The input graph.
• res Output (may be NULL): the cohesion.
• checks Try the quick answers of vertex_connectivity first.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_ENOMEM Memory runs out.

Complexity

As vertex_connectivity.

Checked

Same fixture as vertex_connectivity.

C name

og_cohesion

In notebooks

Og.Cohesion

igraph 1.0

igraph_cohesion

See also

vertex_connectivity, adhesion, cohesive_blocks

Hierarchy of cohesive blocks of an undirected simple graph (Moody and White 2003).

og_error_t og_cohesive_blocks(
    const og_t *graph,
    og_vector_int_list_t *blocks,
    og_vector_int_t *cohesion,
    og_vector_int_t *parent,
    og_t *block_tree
);

A cohesive block is a vertex set whose vertex connectivity, its cohesion, is higher than that of the block around it. Starting from the whole graph, candidate sets are taken first in, first out. Each is split at the union U of all its minimum-size separators: every component of the candidate without U, together with the vertices of U next to it, becomes a new candidate, and so does U itself (only candidates smaller than the one split are kept). A candidate whose connectivity exceeds that of its nearest block ancestor is a block. Finally a block contained in another block of at least the same cohesion is dropped. These details were inferred from python-igraph's behaviour, so the result matches it.

blocks[0] is the whole graph, with parent -1. Each block lists its vertices in increasing order; cohesion[i] is block i's vertex connectivity and parent[i] the index of its parent block. block_tree gets one vertex per block and an edge parent -> block for every other block.

Parameters

• graph The input graph.
• blocks Output (may be NULL): the blocks as vertex-id vectors.
• cohesion Output (may be NULL): the cohesion of every block.
• parent Output (may be NULL): the parent block of every block, -1 for the first.
• block_tree Output (may be NULL): an uninitialised og_t. The function creates the result graph; free it with destroy. Directed, one vertex per block.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL The graph is directed, or has self-loops or multi-edges.
• OG_ENOMEM Memory runs out.

Complexity

Several maximum flows per candidate set; polynomial per candidate, and the number of candidates depends on the graph's structure.

Checked

Blocks in order, cohesion and parents identical to python-igraph on 284 fixture graphs and about 2,100 more (random, overlapping cliques, preferential attachment, small worlds, Zachary). block_tree follows python-igraph's CohesiveBlocks.hierarchy(); igraph's C output for it was not observable.

C name

og_cohesive_blocks

In notebooks

Og.CohesiveBlocks

igraph 1.0

igraph_cohesive_blocks

See also

cohesion, minimum_size_separators, vertex_connectivity

Immediate dominators of a directed flowgraph, and its dominator tree.

og_error_t og_dominator_tree(
    const og_t *graph,
    og_int_t root,
    og_vector_int_t *dom,
    og_t *domtree,
    og_vector_int_t *leftout,
    og_neimode_t mode
);

With a root r, vertex d dominates v when every path from r to v passes through d. The immediate dominator of v is the strict dominator closest to v; these links form the dominator tree. The algorithm is Lengauer and Tarjan's (1979) with balanced path compression, run without recursion. mode OG_OUT follows edges forward from the root, OG_IN follows them backward (dominators toward a sink); OG_ALL behaves as OG_OUT.

dom[v] is the immediate dominator of v, -1 for the root and -2 for vertices the root cannot reach. leftout lists those unreachable vertices in increasing order. domtree is a directed graph on all vertices with an edge (idom(v), v) for every reachable v other than the root, by increasing v; it keeps the input's graph and vertex attributes, not its edge attributes.

Parameters

• graph The input graph.
• root The root vertex.
• dom Output (may be NULL): the immediate dominator of every vertex.
• domtree Output (may be NULL): an uninitialised og_t. The function creates the result graph; free it with destroy.
• leftout Output (may be NULL): the vertices the root cannot reach.
• mode OG_OUT, OG_IN or OG_ALL (treated as OG_OUT).

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL The graph is undirected.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVVID root is not a vertex of the graph.
• OG_ENOMEM Memory runs out.

Complexity

O(|E| alpha(|E|, |V|)), alpha the inverse Ackermann function.

Checked

dom identical to python-igraph's dominator() on 350 cases (random digraphs in every mode, flowgraphs of 5-200 vertices) and a 50,000-vertex path. leftout and the tree are derived from dom (python-igraph exposes neither); the tree's orientation for OG_IN is not tested against igraph.

C name

og_dominator_tree

In notebooks

Og.DominatorTree

igraph 1.0

igraph_dominator_tree

See also

all_st_cuts, bfs

Breadth-first search with several roots, a restricted vertex set and an optional callback.

og_error_t og_bfs(
    const og_t *graph,
    og_int_t root,
    const og_vector_int_t *roots,
    og_neimode_t mode,
    og_bool_t unreachable,
    const og_vector_int_t *restricted,
    og_vector_int_t *order,
    og_vector_int_t *rank,
    og_vector_int_t *parents,
    og_vector_int_t *pred,
    og_vector_int_t *succ,
    og_vector_int_t *dist,
    og_bfshandler_t *callback,
    void *extra
);

Visits vertices in breadth-first order from root, or from each vertex of roots in turn (root is then ignored); a root already visited is skipped. With unreachable = true the search goes on from every vertex not yet visited, in increasing id. restricted (may be NULL) limits the search to the listed vertices; roots outside it are skipped. Neighbours are visited in increasing id order.

Every output may be NULL and has one entry per vertex. order[k] is the k-th visited vertex (-1 after the last), rank[v] the position of v in that order, parents[v] its parent in the search tree (-1 for a root), pred[v] and succ[v] the vertices visited just before and after it in the same tree (-1 at the tree's start and end), dist[v] its distance from its tree's root. A vertex not visited gets -1 in rank and dist and -2 in parents, pred and succ.

callback (may be NULL) is called for each vertex when it is visited, after its unseen neighbours have been queued, with the same values. OG_STOP from it ends the search normally; any other error code ends it and is returned. Vertices not visited keep the 'not visited' values.

Parameters

• graph The input graph.
• root The single root; ignored when roots is given.
• roots Roots to start from in turn (may be NULL).
• mode OG_OUT follows edges forward, OG_IN backward, OG_ALL both ways; ignored for undirected graphs.
• unreachable true: continue from every unvisited vertex until all are visited.
• restricted Vertices the search may visit (may be NULL: all).
• order Output (may be NULL): the vertices in visiting order.
• rank Output (may be NULL): the position of every vertex in the visiting order.
• parents Output (may be NULL): the parent of every vertex in its search tree.
• pred Output (may be NULL): the vertex visited just before, within the same tree.
• succ Output (may be NULL): the vertex visited just after, within the same tree.
• dist Output (may be NULL): the distance from the tree's root.
• callback Called for every visited vertex (may be NULL); see bfshandler_t.
• extra Passed unchanged to the callback.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVVID root, a vertex of roots or a vertex of restricted is not in the graph.
• callback's code: A callback returned a code other than OG_SUCCESS and OG_STOP; the search ends and that code is returned.
• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E|).

Checked

852 runs on 227 random graphs, tree by tree against python-igraph's bfsiter (python-igraph does not expose this function); the padding values and the callback behaviour follow the description and are unit-tested.

C name

og_bfs

In notebooks

Og.Bfs

igraph 1.0

igraph_bfs

See also

bfs_simple, bfshandler_t, dfs

Breadth-first search from one vertex: visiting order, distance layers and parents.

og_error_t og_bfs_simple(
    const og_t *graph,
    og_int_t root,
    og_neimode_t mode,
    og_vector_int_t *order,
    og_vector_int_t *layers,
    og_vector_int_t *parents
);

Visits the vertices reachable from root, neighbours in increasing id order. order lists the visited vertices only. layers holds the position in order where each distance layer starts, plus a final entry equal to the number of visited vertices, so layer d is order[layers[d]] to order[layers[d+1] - 1]. parents has one entry per vertex: the parent in the search tree, -1 for the root and -2 for vertices not reached. Every output may be NULL.

Parameters

• graph The input graph.
• root The start vertex.
• mode OG_OUT follows edges forward, OG_IN backward, OG_ALL both ways; ignored for undirected graphs.
• order Output (may be NULL): the visited vertices in order.
• layers Output (may be NULL): start positions of the distance layers in order, plus the end.
• parents Output (may be NULL): the parent of every vertex.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVVID root is not a vertex of the graph.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E|).

Checked

order, layers and parents identical to python-igraph's Graph.bfs on 227 graphs.

C name

og_bfs_simple

In notebooks

Og.BfsSimple

igraph 1.0

igraph_bfs_simple

See also

bfs, dfs

og_t g;
og_vector_int_t order, layer, parent;

/* a ladder of two rails, 0-1-2 and 3-4-5, with rungs 0-3, 1-4 and 2-5 */
og_small(&g, 6, OG_UNDIRECTED, 0,1, 1,2, 3,4, 4,5, 0,3, 1,4, 2,5, -1);
og_vector_int_init(&order, 0);
og_vector_int_init(&layer, 0);
og_vector_int_init(&parent, 0);
og_bfs_simple(&g, 4, OG_ALL, &order, &layer, &parent);   /* from the middle of a rail */
/* order 4 1 3 5 0 2; layer 0 1 4 6 (4, then 1 3 5, then 0 2); parent 1 4 1 4 -1 4 */
og_vector_int_destroy(&parent);
og_vector_int_destroy(&layer);
og_vector_int_destroy(&order);
og_destroy(&g);

Depth-first search with discovery and finishing orders and optional callbacks.

og_error_t og_dfs(
    const og_t *graph,
    og_int_t root,
    og_neimode_t mode,
    og_bool_t unreachable,
    og_vector_int_t *order,
    og_vector_int_t *order_out,
    og_vector_int_t *parents,
    og_vector_int_t *dist,
    og_dfshandler_t *in_callback,
    og_dfshandler_t *out_callback,
    void *extra
);

Starts at root and, with unreachable = true, goes on from every unvisited vertex in increasing id. Neighbours are taken in increasing id order. An explicit stack is used, so deep graphs do not exhaust the call stack.

order lists vertices as they are discovered and order_out as their subtrees are finished (both padded with -1); parents[v] is the parent in the search tree (-1 for a root, -2 if not visited) and dist[v] the depth in its tree (-1 if not visited). Every output may be NULL.

in_callback is called when a vertex is discovered, out_callback when its subtree is done; either may be NULL. OG_STOP from either ends the search normally, any other error code ends it and is returned.

Parameters

• graph The input graph.
• root The start vertex.
• mode OG_OUT follows edges forward, OG_IN backward, OG_ALL both ways; ignored for undirected graphs.
• unreachable true: continue from every unvisited vertex until all are visited.
• order Output (may be NULL): vertices in discovery order.
• order_out Output (may be NULL): vertices in finishing order.
• parents Output (may be NULL): the parent of every vertex.
• dist Output (may be NULL): the depth of every vertex in its tree.
• in_callback Called on discovery (may be NULL); see dfshandler_t.
• out_callback Called when a vertex's subtree is finished (may be NULL).
• extra Passed unchanged to both callbacks.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVVID root is not a vertex of the graph.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• callback's code: A callback returned a code other than OG_SUCCESS and OG_STOP; the search ends and that code is returned.
• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E|).

Checked

order, parents and dist identical to python-igraph's dfsiter, tree by tree, on 454 runs over 227 graphs; order_out is derived from them (python-igraph does not expose it); callbacks unit-tested.

C name

og_dfs

In notebooks

Og.Dfs

igraph 1.0

igraph_dfs

See also

dfshandler_t, bfs

Random walk of a given number of steps from a start vertex.

og_error_t og_random_walk(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_int_t *vertices,
    og_vector_int_t *edges,
    og_int_t start,
    og_neimode_t mode,
    og_int_t steps,
    og_random_walk_stuck_t stuck
);

At every step the walk leaves the current vertex along one of its usable edges: uniformly at random without weights, with probability proportional to the edge weight otherwise. mode sets the usable edges of a directed graph (OG_OUT forward, OG_IN backward, OG_ALL both); undirected graphs use all. A self-loop counts as two ways out when both of its ends are usable. vertices receives steps + 1 entries, the start first, and edges the steps edge ids; either may be NULL.

At a vertex with no usable edge the walk stops early: with OG_RANDOM_WALK_STUCK_RETURN the shorter walk is returned with success, with OG_RANDOM_WALK_STUCK_ERROR it is returned and the call fails with OG_ERWSTUCK. A vertex whose usable edges all weigh 0 does not stop the walk: it always leaves by the middle edge of its incidence list, as igraph does. Random numbers come from rng_default().

Parameters

• graph The input graph.
• weights Edge weights (non-negative, not NaN), or NULL for an unweighted walk.
• vertices Output (may be NULL): the vertices visited, start included.
• edges Output (may be NULL): the edges taken.
• start The start vertex.
• mode Usable edges of a directed graph: OG_OUT, OG_IN or OG_ALL.
• steps Number of steps (not negative).
• stuck What to do at a vertex without usable edges (random_walk_stuck_t).

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL start is not a vertex, steps is negative, stuck is not a known value, or weights has the wrong length or a negative or NaN entry.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_ERWSTUCK The walk got stuck and stuck is OG_RANDOM_WALK_STUCK_ERROR (the shortened walk is still returned).
• OG_ENOMEM Memory runs out.

Complexity

O(steps) without weights; O(steps log d + the degrees of the vertices visited) with weights, d the largest degree. Independent of the graph's size.

Checked

Open Graph's own draws, so one seed gives another walk than igraph. One-step transition counts (3,000 walks from every vertex of 36 graphs) agree with python-igraph's and with the exact probabilities by chi-square at p = 1e-6; long-walk visit frequencies are within 0.02 of the stationary distribution.

C name

og_random_walk

In notebooks

Og.RandomWalk

igraph 1.0

igraph_random_walk

See also

random_walk_stuck_t, bfs