wbia.algo.graph package

Subpackages

• wbia.algo.graph.tests package
  • Submodules
  • wbia.algo.graph.tests.dyn_cases module
  • wbia.algo.graph.tests.mst_debug module
  • wbia.algo.graph.tests.test_graph_iden module
  • wbia.algo.graph.tests.test_neg_metagraph module
  • Module contents

Submodules

wbia.algo.graph.__main__ module

wbia.algo.graph.__main__.main()

wbia.algo.graph.core module

wbia.algo.graph.demo module

wbia.algo.graph.mixin_dynamic module

wbia.algo.graph.mixin_groundtruth module

wbia.algo.graph.mixin_helpers module

wbia.algo.graph.mixin_loops module

wbia.algo.graph.mixin_matching module

wbia.algo.graph.mixin_priority module

wbia.algo.graph.mixin_simulation module

wbia.algo.graph.mixin_viz module

wbia.algo.graph.mixin_wbia module

wbia.algo.graph.nx_dynamic_graph module

class wbia.algo.graph.nx_dynamic_graph.DynConnGraph(*args, **kwargs)

Bases: networkx.classes.graph.Graph, wbia.algo.graph.nx_dynamic_graph.GraphHelperMixin

Dynamically connected graph.

Maintains a data structure parallel to a normal networkx graph that maintains dynamic connectivity for fast connected compoment queries.

Underlying Data Structures and limitations are

• UnionFind | lg(n) | n | No

• UnionFind2 | n* | n | 1

• EulerTourForest | lg^2(n) | lg^2(n) | lg(n) / lglg(n) - - Ammortized

• it seems to be very quick

References

https://courses.csail.mit.edu/6.851/spring14/lectures/L20.pdf https://courses.csail.mit.edu/6.851/spring14/lectures/L20.html http://cs.stackexchange.com/questions/33595/maintaining-connecte https://en.wikipedia.org/wiki/Dynamic_connectivity#Fully_dynamic_connectivity

CommandLine:

python -m wbia.algo.graph.nx_dynamic_graph DynConnGraph

Example

>>> # ENABLE_DOCTEST
>>> from wbia.algo.graph.nx_dynamic_graph import *  # NOQA
>>> self = DynConnGraph()
>>> self.add_edges_from([(1, 2), (2, 3), (4, 5), (6, 7), (7, 4)])
>>> self.add_edges_from([(10, 20), (20, 30), (40, 50), (60, 70), (70, 40)])
>>> self._ccs
>>> u, v = 20, 1
>>> assert self.node_label(u) != self.node_label(v)
>>> assert self.connected_to(u) != self.connected_to(v)
>>> self.add_edge(u, v)
>>> assert self.node_label(u) == self.node_label(v)
>>> assert self.connected_to(u) == self.connected_to(v)
>>> self.remove_edge(u, v)
>>> assert self.node_label(u) != self.node_label(v)
>>> assert self.connected_to(u) != self.connected_to(v)
>>> ccs = list(self.connected_components())
>>> ut.quit_if_noshow()
>>> import wbia.plottool as pt
>>> pt.qtensure()
>>> pt.show_nx(self)

# todo: check if nodes exist when adding

add_edge(u, v, **attr)

Example

>>> # ENABLE_DOCTEST
>>> from wbia.algo.graph.nx_dynamic_graph import *  # NOQA
>>> self = DynConnGraph()
>>> self.add_edges_from([(1, 2), (2, 3), (4, 5), (6, 7), (7, 4)])
>>> assert self._ccs == {1: {1, 2, 3}, 4: {4, 5, 6, 7}}
>>> self.add_edge(1, 5)
>>> assert self._ccs == {1: {1, 2, 3, 4, 5, 6, 7}}

add_edges_from(ebunch, **attr)

Add all the edges in ebunch_to_add.

Parameters

• ebunch_to_add (container of edges) – Each edge given in the container will be added to the graph. The edges must be given as 2-tuples (u, v) or 3-tuples (u, v, d) where d is a dictionary containing edge data.

• attr (keyword arguments, optional) – Edge data (or labels or objects) can be assigned using keyword arguments.

See also

add_edge

add a single edge

add_weighted_edges_from

convenient way to add weighted edges

Notes

Adding the same edge twice has no effect but any edge data will be updated when each duplicate edge is added.

Edge attributes specified in an ebunch take precedence over attributes specified via keyword arguments.

Examples

>>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> G.add_edges_from([(0, 1), (1, 2)])  # using a list of edge tuples
>>> e = zip(range(0, 3), range(1, 4))
>>> G.add_edges_from(e)  # Add the path graph 0-1-2-3

Associate data to edges

>>> G.add_edges_from([(1, 2), (2, 3)], weight=3)
>>> G.add_edges_from([(3, 4), (1, 4)], label="WN2898")

add_node(n, **attr)

Add a single node node_for_adding and update node attributes.

Parameters

• node_for_adding (node) – A node can be any hashable Python object except None.

• attr (keyword arguments, optional) – Set or change node attributes using key=value.

See also

add_nodes_from

Examples

>>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> G.add_node(1)
>>> G.add_node("Hello")
>>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)])
>>> G.add_node(K3)
>>> G.number_of_nodes()
3

Use keywords set/change node attributes:

>>> G.add_node(1, size=10)
>>> G.add_node(3, weight=0.4, UTM=("13S", 382871, 3972649))

Notes

A hashable object is one that can be used as a key in a Python dictionary. This includes strings, numbers, tuples of strings and numbers, etc.

On many platforms hashable items also include mutables such as NetworkX Graphs, though one should be careful that the hash doesn’t change on mutables.

add_nodes_from(nodes, **attr)

Add multiple nodes.

Parameters

• nodes_for_adding (iterable container) – A container of nodes (list, dict, set, etc.). OR A container of (node, attribute dict) tuples. Node attributes are updated using the attribute dict.

• attr (keyword arguments, optional (default= no attributes)) – Update attributes for all nodes in nodes. Node attributes specified in nodes as a tuple take precedence over attributes specified via keyword arguments.

See also

add_node

Examples

>>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> G.add_nodes_from("Hello")
>>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)])
>>> G.add_nodes_from(K3)
>>> sorted(G.nodes(), key=str)
[0, 1, 2, 'H', 'e', 'l', 'o']

Use keywords to update specific node attributes for every node.

>>> G.add_nodes_from([1, 2], size=10)
>>> G.add_nodes_from([3, 4], weight=0.4)

Use (node, attrdict) tuples to update attributes for specific nodes.

>>> G.add_nodes_from([(1, dict(size=11)), (2, {"color": "blue"})])
>>> G.nodes[1]["size"]
11
>>> H = nx.Graph()
>>> H.add_nodes_from(G.nodes(data=True))
>>> H.nodes[1]["size"]
11

are_nodes_connected(u, v)

clear()

Remove all nodes and edges from the graph.

This also removes the name, and all graph, node, and edge attributes.

Examples

>>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> G.clear()
>>> list(G.nodes)
[]
>>> list(G.edges)
[]

component(label)

component_labels()

component_nodes(label)

connected_components()

Example

>>> # ENABLE_DOCTEST
>>> from wbia.algo.graph.nx_dynamic_graph import *  # NOQA
>>> self = DynConnGraph()
>>> self.add_edges_from([(1, 2), (2, 3), (4, 5), (6, 7)])
>>> ccs = list(self.connected_components())
>>> result = 'ccs = {}'.format(ut.repr2(ccs, nl=0))
>>> print(result)
ccs = [{1, 2, 3}, {4, 5}, {6, 7}]

connected_to(node)

node_label(node)

Example

>>> # ENABLE_DOCTEST
>>> from wbia.algo.graph.nx_dynamic_graph import *  # NOQA
>>> self = DynConnGraph()
>>> self.add_edges_from([(1, 2), (2, 3), (4, 5), (6, 7)])
>>> assert self.node_label(2) == self.node_label(1)
>>> assert self.node_label(2) != self.node_label(4)

node_labels(*nodes)

number_of_components()

remove_edge(u, v)

Example

>>> # ENABLE_DOCTEST
>>> from wbia.algo.graph.nx_dynamic_graph import *  # NOQA
>>> self = DynConnGraph()
>>> self.add_edges_from([(1, 2), (2, 3), (4, 5), (6, 7), (7, 4)])
>>> assert self._ccs == {1: {1, 2, 3}, 4: {4, 5, 6, 7}}
>>> self.add_edge(1, 5)
>>> assert self._ccs == {1: {1, 2, 3, 4, 5, 6, 7}}
>>> self.remove_edge(1, 5)
>>> assert self._ccs == {1: {1, 2, 3}, 4: {4, 5, 6, 7}}

remove_edges_from(ebunch)

Remove all edges specified in ebunch.

Parameters

ebunch (list or container of edge tuples) –

Each edge given in the list or container will be removed from the graph. The edges can be:

• 2-tuples (u, v) edge between u and v.

• 3-tuples (u, v, k) where k is ignored.

See also

remove_edge

remove a single edge

Notes

Will fail silently if an edge in ebunch is not in the graph.

Examples

>>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> ebunch = [(1, 2), (2, 3)]
>>> G.remove_edges_from(ebunch)

remove_node(n)

CommandLine:

python -m wbia.algo.graph.nx_dynamic_graph remove_node

Example

>>> # ENABLE_DOCTEST
>>> from wbia.algo.graph.nx_dynamic_graph import *  # NOQA
>>> self = DynConnGraph()
>>> self.add_edges_from([(1, 2), (2, 3), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)])
>>> assert self._ccs == {1: {1, 2, 3}, 4: {4, 5, 6, 7, 8, 9}}
>>> self.remove_node(2)
>>> assert self._ccs == {1: {1}, 3: {3}, 4: {4, 5, 6, 7, 8, 9}}
>>> self.remove_node(7)
>>> assert self._ccs == {1: {1}, 3: {3}, 4: {4, 5, 6}, 8: {8, 9}}

remove_nodes_from(nodes)

Remove multiple nodes.

Parameters

nodes (iterable container) – A container of nodes (list, dict, set, etc.). If a node in the container is not in the graph it is silently ignored.

See also

remove_node

Examples

>>> G = nx.path_graph(3)  # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> e = list(G.nodes)
>>> e
[0, 1, 2]
>>> G.remove_nodes_from(e)
>>> list(G.nodes)
[]

subgraph(nbunch, dynamic=False)

Returns a SubGraph view of the subgraph induced on nodes.

The induced subgraph of the graph contains the nodes in nodes and the edges between those nodes.

Parameters

nodes (list, iterable) – A container of nodes which will be iterated through once.

Returns

G – A subgraph view of the graph. The graph structure cannot be changed but node/edge attributes can and are shared with the original graph.

Return type

SubGraph View

Notes

The graph, edge and node attributes are shared with the original graph. Changes to the graph structure is ruled out by the view, but changes to attributes are reflected in the original graph.

To create a subgraph with its own copy of the edge/node attributes use: G.subgraph(nodes).copy()

For an inplace reduction of a graph to a subgraph you can remove nodes: G.remove_nodes_from([n for n in G if n not in set(nodes)])

Subgraph views are sometimes NOT what you want. In most cases where you want to do more than simply look at the induced edges, it makes more sense to just create the subgraph as its own graph with code like:

# Create a subgraph SG based on a (possibly multigraph) G
SG = G.__class__()
SG.add_nodes_from((n, G.nodes[n]) for n in largest_wcc)
if SG.is_multigraph():
    SG.add_edges_from((n, nbr, key, d)
        for n, nbrs in G.adj.items() if n in largest_wcc
        for nbr, keydict in nbrs.items() if nbr in largest_wcc
        for key, d in keydict.items())
else:
    SG.add_edges_from((n, nbr, d)
        for n, nbrs in G.adj.items() if n in largest_wcc
        for nbr, d in nbrs.items() if nbr in largest_wcc)
SG.graph.update(G.graph)

Examples

>>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> H = G.subgraph([0, 1, 2])
>>> list(H.edges)
[(0, 1), (1, 2)]

class wbia.algo.graph.nx_dynamic_graph.GraphHelperMixin

Bases: utool.util_dev.NiceRepr

edges(nbunch=None, data=False, default=None)

has_edges(edges)

has_nodes(nodes)

class wbia.algo.graph.nx_dynamic_graph.NiceGraph(incoming_graph_data=None, **attr)

Bases: networkx.classes.graph.Graph, wbia.algo.graph.nx_dynamic_graph.GraphHelperMixin

class wbia.algo.graph.nx_dynamic_graph.nx_UnionFind(elements=None)

Bases: object

Based of nx code

add_element(x)

add_elements(elements)

clear()

rebalance(elements=None)

remove_entire_cc(elements)

to_sets()

union(*objects)

Find the sets containing the objects and merge them all.

wbia.algo.graph.nx_edge_augmentation module

Algorithms for finding k-edge-augmentations

A k-edge-augmentation is a set of edges, that once added to a graph, ensures that the graph is k-edge-connected. Typically, the goal is to find the augmentation with minimum weight. In general, it is not gaurenteed that a k-edge-augmentation exists.

class wbia.algo.graph.nx_edge_augmentation.MetaEdge(meta_uv, uv, w)

Bases: tuple

meta_uv

Alias for field number 0

uv

Alias for field number 1

w

Alias for field number 2

wbia.algo.graph.nx_edge_augmentation.bridge_augmentation(G, avail=None, weight=None)

Finds the a set of edges that bridge connects G.

Adding these edges to G will make it 2-edge-connected. If no constraints are specified the returned set of edges is minimum an optimal, otherwise the solution is approximated.

Notes

If there are no constraints the solution can be computed in linear time using unconstrained_bridge_augmentation(). Otherwise, the problem becomes NP-hard and is the solution is approximated by weighted_bridge_augmentation().

wbia.algo.graph.nx_edge_augmentation.collapse(G, grouped_nodes)

Collapses each group of nodes into a single node.

This is similar to condensation, but works on undirected graphs.

Parameters

• G (NetworkX Graph) – A directed graph.

• grouped_nodes (list or generator) – Grouping of nodes to collapse. The grouping must be disjoint. If grouped_nodes are strongly_connected_components then this is equivalent to condensation.

Returns

C – The collapsed graph C of G with respect to the node grouping. The node labels are integers corresponding to the index of the component in the list of strongly connected components of G. C has a graph attribute named ‘mapping’ with a dictionary mapping the original nodes to the nodes in C to which they belong. Each node in C also has a node attribute ‘members’ with the set of original nodes in G that form the group that the node in C represents.

Return type

NetworkX Graph

Examples

>>> # Collapses a graph using disjoint groups, but not necesarilly connected
>>> G = nx.Graph([(1, 0), (2, 3), (3, 1), (3, 4), (4, 5), (5, 6), (5, 7)])
>>> G.add_node('A')
>>> grouped_nodes = [{0, 1, 2, 3}, {5, 6, 7}]
>>> C = collapse(G, grouped_nodes)
>>> members = nx.get_node_attributes(C, 'members')
>>> sorted(members.keys())
[0, 1, 2, 3]
>>> member_values = set(map(frozenset, members.values()))
>>> assert {0, 1, 2, 3} in member_values
>>> assert {4} in member_values
>>> assert {5, 6, 7} in member_values
>>> assert {'A'} in member_values

wbia.algo.graph.nx_edge_augmentation.compat_shuffle(rng, input)

wbia.algo.graph.nx_edge_augmentation.complement_edges(G)

Returns only the edges in the complement of G

Example

>>> G = nx.path_graph((1, 2, 3, 4))
>>> sorted(complement_edges(G))
[(1, 3), (1, 4), (2, 4)]
>>> G = nx.path_graph((1, 2, 3, 4), nx.DiGraph())
>>> sorted(complement_edges(G))
[(1, 3), (1, 4), (2, 1), (2, 4), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)]
>>> G = nx.complete_graph(1000)
>>> sorted(complement_edges(G))
[]

wbia.algo.graph.nx_edge_augmentation.greedy_k_edge_augmentation(G, k, avail=None, weight=None, seed=None)

Greedy algorithm for finding a k-edge-augmentation

Notes

The algorithm is simple. Edges are incrementally added between parts of the graph that are not yet locally k-edge-connected. Then edges are from the augmenting set are pruned as long as local-edge-connectivity is not broken.

This algorithm is greedy and does not provide optimiality gaurentees. It exists only to provide k_edge_augmentation() with the ability to generate a feasible solution for arbitrary k.

Example

>>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7))
>>> sorted(greedy_k_edge_augmentation(G, k=2))
[(1, 7)]
>>> sorted(greedy_k_edge_augmentation(G, k=1, avail=[]))
[]
>>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7))
>>> avail = {(u, v): 1 for (u, v) in complement_edges(G)}
>>> # randomized pruning process can produce different solutions
>>> sorted(greedy_k_edge_augmentation(G, k=4, avail=avail, seed=2))
[(1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (2, 4), (2, 6), (3, 7), (5, 7)]
>>> sorted(greedy_k_edge_augmentation(G, k=4, avail=avail, seed=3))
[(1, 3), (1, 5), (1, 6), (2, 4), (2, 6), (3, 7), (4, 7), (5, 7)]

wbia.algo.graph.nx_edge_augmentation.is_k_edge_connected(G, k)

Tests to see if a graph is k-edge-connected

See also

is_locally_k_edge_connected

Example

>>> G = nx.barbell_graph(10, 0)
>>> is_k_edge_connected(G, k=1)
True
>>> is_k_edge_connected(G, k=2)
False

wbia.algo.graph.nx_edge_augmentation.is_locally_k_edge_connected(G, s, t, k)

Tests to see if an edge in a graph is locally k-edge-connected

See also

is_k_edge_connected

Example

>>> G = nx.barbell_graph(10, 0)
>>> is_locally_k_edge_connected(G, 5, 15, k=1)
True
>>> is_locally_k_edge_connected(G, 5, 15, k=2)
False
>>> is_locally_k_edge_connected(G, 1, 5, k=2)
True

wbia.algo.graph.nx_edge_augmentation.k_edge_augmentation(G, k, avail=None, weight=None, partial=False)

Finds set of edges to k-edge-connect G.

This function uses the most efficient function available (depending on the value of k and if the problem is weighted or unweighted) to search for a minimum weight subset of available edges that k-edge-connects G. In general, finding a k-edge-augmentation is NP-hard, so solutions are not garuenteed to be minimal.

Parameters

• G (NetworkX graph) –

• k (Integer) – Desired edge connectivity

• avail (dict or a set 2 or 3 tuples) –

  The available edges that can be used in the augmentation.

  If unspecified, then all edges in the complement of G are available. Otherwise, each item is an available edge (with an optinal weight).

  In the unweighted case, each item is an edge (u, v).

  In the weighted case, each item is a 3-tuple (u, v, d) or a dict with items (u, v): d. The third item, d, can be a dictionary or a real number. If d is a dictionary d[weight] correspondings to the weight.

• weight (string) – key to use to find weights if avail is a set of 3-tuples where the third item in each tuple is a dictionary.

• partial (Boolean) – If partial is True and no feasible k-edge-augmentation exists, then all available edges are returned.

Returns

aug_edges – the G would become k-edge-connected. If partial is False, an error is raised if this is not possible. Otherwise, all available edges are generated.

Return type

a generator of edges. If these edges are added to G, then

Raises

• NetworkXNotImplemented: – If the input graph is directed or a multigraph.

• ValueError: – If k is less than 1

Notes

When k=1 this returns an optimal solution.

When k=2 and avail is None, this returns an optimal solution. Otherwise when k=2, this returns a 2-approximation of the optimal solution.

For k>3, this problem is NP-hard and this uses a randomized algorithm that

produces a feasible solution, but provides no gaurentees on the solution weight.

Example

>>> # Unweighted cases
>>> G = nx.path_graph((1, 2, 3, 4))
>>> G.add_node(5)
>>> sorted(k_edge_augmentation(G, k=1))
[(1, 5)]
>>> sorted(k_edge_augmentation(G, k=2))
[(1, 5), (5, 4)]
>>> sorted(k_edge_augmentation(G, k=3))
[(1, 4), (1, 5), (2, 5), (3, 5), (4, 5)]
>>> complement = list(k_edge_augmentation(G, k=5, partial=True))
>>> G.add_edges_from(complement)
>>> nx.edge_connectivity(G)
4

Example

>>> # Weighted cases
>>> G = nx.path_graph((1, 2, 3, 4))
>>> G.add_node(5)
>>> # avail can be a tuple with a dict
>>> avail = [(1, 5, {'weight': 11}), (2, 5, {'weight': 10})]
>>> sorted(k_edge_augmentation(G, k=1, avail=avail, weight='weight'))
[(2, 5)]
>>> # or avail can be a 3-tuple with a real number
>>> avail = [(1, 5, 11), (2, 5, 10), (4, 3, 1), (4, 5, 51)]
>>> sorted(k_edge_augmentation(G, k=2, avail=avail))
[(1, 5), (2, 5), (4, 5)]
>>> # or avail can be a dict
>>> avail = {(1, 5): 11, (2, 5): 10, (4, 3): 1, (4, 5): 51}
>>> sorted(k_edge_augmentation(G, k=2, avail=avail))
[(1, 5), (2, 5), (4, 5)]
>>> # If augmentation is infeasible, then all edges in avail are returned
>>> avail = {(1, 5): 11}
>>> sorted(k_edge_augmentation(G, k=2, avail=avail, partial=True))
[(1, 5)]

wbia.algo.graph.nx_edge_augmentation.one_edge_augmentation(G, avail=None, weight=None, partial=False)

Finds minimum weight set of edges to connect G.

Notes

Uses either unconstrained_one_edge_augmentation() or weighted_one_edge_augmentation() depending on whether avail is specified. Both algorithms are based on finding a minimum spanning tree. As such both algorithms find optimal solutions and run in linear time.

wbia.algo.graph.nx_edge_augmentation.partial_k_edge_augmentation(G, k, avail, weight=None)

Finds augmentation that k-edge-connects as much of the graph as possible

When a k-edge-augmentation is not possible, we can still try to find a small set of edges that partially k-edge-connects as much of the graph as possible.

Notes

Construct H that augments G with all edges in avail. Find the k-edge-subgraphs of H. For each k-edge-subgraph, if the number of nodes is more than k, then find the k-edge-augmentation of that graph and add it to the solution. Then add all edges in avail between k-edge subgraphs to the solution.

>>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7))
>>> G.add_node(8)
>>> avail = [(1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 5), (1, 8)]
>>> sorted(partial_k_edge_augmentation(G, k=2, avail=avail))
[(1, 5), (1, 8)]

wbia.algo.graph.nx_edge_augmentation.unconstrained_bridge_augmentation(G)

Finds an optimal 2-edge-augmentation of G using the fewest edges.

This is an implementation of the algorithm detailed in [1]_. The basic idea is to construct a meta-graph of bridge-ccs, connect leaf nodes of the trees to connect the entire graph, and finally connect the leafs of the tree in dfs-preorder to bridge connect the entire graph.

Notes

Input: a graph G. First find the bridge components of G and collapse each bridge-cc into a node of a metagraph graph C, which is gaurenteed to be a forest of trees.

C contains p “leafs” — nodes with exactly one incident edge. C contains q “isolated nodes” — nodes with no incident edges.

Theorem: If p + q > 1, then at least ceil(p / 2) + q edges are

needed to bridge connect C. This algorithm achieves this min number.

The method first adds enough edges to make G into a tree and then pairs leafs in a simple fashion.

Let n be the number of trees in C. Let v(i) be an isolated vertex in the i-th tree if one exists, otherwise it is a pair of distinct leafs nodes in the i-th tree. Alternating edges from these sets (i.e. adding edges A1 = [(v(i)[0], v(i + 1)[1]), v(i + 1)[0], v(i + 2)[1])…]) connects C into a tree T. This tree has p’ = p + 2q - 2(n -1) leafs and no isolated vertices. A1 has n - 1 edges. The next step finds ceil(p’ / 2) edges to biconnect any tree with p’ leafs.

Convert T into an arborescence T’ by picking an arbitrary root node with degree >= 2 and directing all edges away from the root. Note the implementation implicitly constructs T’.

The leafs of T are the nodes with no existing edges in T’. Order the leafs of T’ by DFS prorder. Then break this list in half and add the zipped pairs to A2.

The set A = A1 + A2 is the minimum augmentation in the metagraph.

To convert this to edges in the original graph

References

1

Eswaran, Kapali P., and R. Endre Tarjan. (1975) Augmentation problems. http://epubs.siam.org/doi/abs/10.1137/0205044

Example

>>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7))
>>> sorted(unconstrained_bridge_augmentation(G))
[(1, 7)]
>>> G = nx.path_graph((1, 2, 3, 2, 4, 5, 6, 7))
>>> sorted(unconstrained_bridge_augmentation(G))
[(1, 3), (3, 7)]
>>> G = nx.Graph([(0, 1), (0, 2), (1, 2)])
>>> G.add_node(4)
>>> sorted(unconstrained_bridge_augmentation(G))
[(1, 4), (4, 0)]

wbia.algo.graph.nx_edge_augmentation.unconstrained_one_edge_augmentation(G)

Finds the smallest set of edges to connect G.

This is a variant of the unweighted MST problem. If G is not empty, a feasible solution always exists.

Example

>>> G = nx.Graph([(1, 2), (2, 3), (4, 5)])
>>> G.add_nodes_from([6, 7, 8])
>>> sorted(unconstrained_one_edge_augmentation(G))
[(1, 4), (4, 6), (6, 7), (7, 8)]

wbia.algo.graph.nx_edge_augmentation.weighted_bridge_augmentation(G, avail, weight=None)

Finds an approximate min-weight 2-edge-augmentation of G.

This is an implementation of the approximation algorithm detailed in [1]_. It chooses a set of edges from avail to add to G that renders it 2-edge-connected if such a subset exists. This is done by finding a minimum spanning arborescence of a specially constructed metagraph.

Parameters

• G (NetworkX graph) –

• avail (set of 2 or 3 tuples.) – candidate edges (with optional weights) to choose from

• weight (string) – key to use to find weights if avail is a set of 3-tuples where the third item in each tuple is a dictionary.

Returns

aug_edges (set)

Return type

subset of avail chosen to augment G

Notes

Finding a weighted 2-edge-augmentation is NP-hard. Any edge not in avail is considered to have a weight of infinity. The approximation factor is 2 if G is connected and 3 if it is not. Runs in O(m + n log(n)) time

References

1

Khuller, Samir, and Ramakrishna Thurimella. (1993) Approximation algorithms for graph augmentation. http://www.sciencedirect.com/science/article/pii/S0196677483710102

Example

>>> G = nx.path_graph((1, 2, 3, 4))
>>> # When the weights are equal, (1, 4) is the best
>>> avail = [(1, 4, 1), (1, 3, 1), (2, 4, 1)]
>>> sorted(weighted_bridge_augmentation(G, avail))
[(1, 4)]
>>> # Giving (1, 4) a high weight makes the two edge solution the best.
>>> avail = [(1, 4, 1000), (1, 3, 1), (2, 4, 1)]
>>> sorted(weighted_bridge_augmentation(G, avail))
[(1, 3), (2, 4)]
>>> #------
>>> G = nx.path_graph((1, 2, 3, 4))
>>> G.add_node(5)
>>> avail = [(1, 5, 11), (2, 5, 10), (4, 3, 1), (4, 5, 1)]
>>> sorted(weighted_bridge_augmentation(G, avail=avail))
[(1, 5), (4, 5)]
>>> avail = [(1, 5, 11), (2, 5, 10), (4, 3, 1), (4, 5, 51)]
>>> sorted(weighted_bridge_augmentation(G, avail=avail))
[(1, 5), (2, 5), (4, 5)]

wbia.algo.graph.nx_edge_augmentation.weighted_one_edge_augmentation(G, avail, weight=None, partial=False)

Finds the minimum weight set of edges to connect G if one exists.

This is a variant of the weighted MST problem.

Example

>>> G = nx.Graph([(1, 2), (2, 3), (4, 5)])
>>> G.add_nodes_from([6, 7, 8])
>>> # any edge not in avail has an implicit weight of infinity
>>> avail = [(1, 3), (1, 5), (4, 7), (4, 8), (6, 1), (8, 1), (8, 2)]
>>> sorted(weighted_one_edge_augmentation(G, avail))
[(1, 5), (4, 7), (6, 1), (8, 1)]
>>> # find another solution by giving large weights to edges in the
>>> # previous solution (note some of the old edges must be used)
>>> avail = [(1, 3), (1, 5, 99), (4, 7, 9), (6, 1, 99), (8, 1, 99), (8, 2)]
>>> sorted(weighted_one_edge_augmentation(G, avail))
[(1, 5), (4, 7), (6, 1), (8, 2)]

wbia.algo.graph.nx_edge_kcomponents module

Algorithms for finding k-edge-connected components and subgraphs.

A k-edge-connected component (k-edge-cc) is a maximal set of nodes in G, such that all pairs of node have an edge-connectivity of at least k.

A k-edge-connected subgraph (k-edge-subgraph) is a maximal set of nodes in G, such that the subgraph of G defined by the nodes has an edge-connectivity at least k.

class wbia.algo.graph.nx_edge_kcomponents.EdgeComponentAuxGraph

Bases: object

A simple algorithm to find all k-edge-connected components in a graph.

Constructing the AuxillaryGraph (which may take some time) allows for the k-edge-ccs to be found in linear time for arbitrary k.

Notes

This implementation is based on [1]_. The idea is to construct an auxillary graph from which the k-edge-ccs can be extracted in linear time. The auxillary graph is constructed in O(|V|F) operations, where F is the complexity of max flow. Querying the components takes an additional O(|V|) operations. This algorithm can be slow for large graphs, but it handles an arbitrary k and works for both directed and undirected inputs.

The undirected case for k=1 is exactly connected components. The undirected case for k=2 is exactly bridge connected components. The directed case for k=1 is exactly strongly connected components.

References

1

Wang, Tianhao, et al. (2015) A simple algorithm for finding all k-edge-connected components. http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0136264

Example

>>> from networkx.utils import pairwise
>>> # Build an interesting graph with multiple levels of k-edge-ccs
>>> paths = [
...     (1, 2, 3, 4, 1, 3, 4, 2),  # a 3-edge-cc (a 4 clique)
...     (5, 6, 7, 5),  # a 2-edge-cc (a 3 clique)
...     (1, 5),  # combine first two ccs into a 1-edge-cc
...     (0,),  # add an additional disconnected 1-edge-cc
... ]
>>> G = nx.Graph()
>>> G.add_nodes_from(it.chain(*paths))
>>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))
>>> # Constructing the AuxGraph takes about O(n ** 4)
>>> aux_graph = EdgeComponentAuxGraph.construct(G)
>>> # Once constructed, querying takes O(n)
>>> sorted(map(sorted, aux_graph.k_edge_components(k=1)))
[[0], [1, 2, 3, 4, 5, 6, 7]]
>>> sorted(map(sorted, aux_graph.k_edge_components(k=2)))
[[0], [1, 2, 3, 4], [5, 6, 7]]
>>> sorted(map(sorted, aux_graph.k_edge_components(k=3)))
[[0], [1, 2, 3, 4], [5], [6], [7]]
>>> sorted(map(sorted, aux_graph.k_edge_components(k=4)))
[[0], [1], [2], [3], [4], [5], [6], [7]]

Example

>>> # The auxillary graph is primarilly used for k-edge-ccs but it
>>> # can also speed up the queries of k-edge-subgraphs by refining the
>>> # search space.
>>> from networkx.utils import pairwise
>>> paths = [
...     (1, 2, 4, 3, 1, 4),
... ]
>>> G = nx.Graph()
>>> G.add_nodes_from(it.chain(*paths))
>>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))
>>> aux_graph = EdgeComponentAuxGraph.construct(G)
>>> sorted(map(sorted, aux_graph.k_edge_subgraphs(k=3)))
[[1], [2], [3], [4]]
>>> sorted(map(sorted, aux_graph.k_edge_components(k=3)))
[[1, 4], [2], [3]]

classmethod construct(G)

Builds an auxillary graph encoding edge-connectivity between nodes.

Notes

Given G=(V, E), initialize an empty auxillary graph A. Choose an arbitrary source node s. Initialize a set N of available nodes (that can be used as the sink). The algorithm picks an arbitrary node t from N - {s}, and then computes the minimum st-cut (S, T) with value w. If G is directed the the minimum of the st-cut or the ts-cut is used instead. Then, the edge (s, t) is added to the auxillary graph with weight w. The algorithm is called recursively first using S as the available nodes and s as the source, and then using T and t. Recusion stops when the source is the only available node.

Parameters

G (NetworkX graph) –

k_edge_components(k)

Queries the auxillary graph for k-edge-connected components.

Parameters

k (Integer) – Desired edge connectivity

Returns

k_edge_components

Return type

a generator of k-edge-ccs

Notes

Given the auxillary graph, the k-edge-connected components can be determined in linear time by removing all edges with weights less than k from the auxillary graph. The resulting connected components are the k-edge-ccs in the original graph.

k_edge_subgraphs(k)

Queries the auxillary graph for k-edge-connected subgraphs.

Parameters

k (Integer) – Desired edge connectivity

Returns

k_edge_subgraphs

Return type

a generator of k-edge-subgraphs

Notes

Refines the k-edge-ccs into k-edge-subgraphs. The running time is more than O(|V|).

For single values of k it is faster to use nx.k_edge_subgraphs. But for multiple values of k, it can be faster to build AuxGraph and then use this method.

wbia.algo.graph.nx_edge_kcomponents.bridge_components(G)

Finds all bridge-connected components G.

Parameters

G (NetworkX undirected graph) –

Returns

bridge_components

Return type

a generator of 2-edge-connected components

See also

k_edge_subgraphs()

this function is a special case for an undirected graph where k=2.

biconnected_components()

similar to this function, but is defined using 2-node-connectivity instead of 2-edge-connectivity.

Raises

NetworkXNotImplemented: – If the input graph is directed or a multigraph.

Notes

Bridge-connected components are also known as 2-edge-connected components.

Example

>>> # The barbell graph with parameter zero has a single bridge
>>> G = nx.barbell_graph(5, 0)
>>> sorted(map(sorted, bridge_components(G)))
[[0, 1, 2, 3, 4], [5, 6, 7, 8, 9]]

wbia.algo.graph.nx_edge_kcomponents.general_k_edge_subgraphs(G, k)

General algorithm to find all maximal k-edge-connected subgraphs in G.

Returns

k_edge_subgraphs – Each k-edge-subgraph is a maximal set of nodes that defines a subgraph of G that is k-edge-connected.

Return type

a generator of nx.Graphs that are k-edge-subgraphs

Notes

Implementation of the basic algorithm from _[1]. The basic idea is to find a global minimum cut of the graph. If the cut value is at least k, then the graph is a k-edge-connected subgraph and can be added to the results. Otherwise, the cut is used to split the graph in two and the procedure is applied recursively. If the graph is just a single node, then it is also added to the results. At the end, each result is either gaurenteed to be a single node or a subgraph of G that is k-edge-connected.

This implementation contains optimizations for reducing the number of calls to max-flow, but there are other optimizations in _[1] that could be implemented.

References

1

Zhou, Liu, et al. (2012) Finding maximal k-edge-connected subgraphs from a large graph. ACM International Conference on Extending Database Technology 2012 480-–491. https://openproceedings.org/2012/conf/edbt/ZhouLYLCL12.pdf

Example

>>> from networkx.utils import pairwise
>>> paths = [
...     (11, 12, 13, 14, 11, 13, 14, 12),  # a 4-clique
...     (21, 22, 23, 24, 21, 23, 24, 22),  # another 4-clique
...     # connect the cliques with high degree but low connectivity
...     (50, 13),
...     (12, 50, 22),
...     (13, 102, 23),
...     (14, 101, 24),
... ]
>>> G = nx.Graph(it.chain(*[pairwise(path) for path in paths]))
>>> sorted(map(len, k_edge_subgraphs(G, k=3)))
[1, 1, 1, 4, 4]

wbia.algo.graph.nx_edge_kcomponents.k_edge_components(G, k)

Generates nodes in each maximal k-edge-connected component in G.

Parameters

• G (NetworkX graph) –

• k (Integer) – Desired edge connectivity

Returns

k_edge_components – will have k-edge-connectivity in the graph G.

Return type

a generator of k-edge-ccs. Each set of returned nodes

See also

local_edge_connectivity()

k_edge_subgraphs()

similar to this function, but the subgraph defined by the nodes must also have k-edge-connectivity.

k_components()

similar to this function, but uses node-connectivity instead of edge-connectivity

Raises

• NetworkXNotImplemented: – If the input graph is a multigraph.

• ValueError: – If k is less than 1

Notes

Attempts to use the most efficient implementation available based on k. If k=1, this is simply simply connected components for directed graphs and connected components for undirected graphs. If k=2 on an efficient bridge connected component algorithm from _[1] is run based on the chain decomposition. Otherwise, the algorithm from _[2] is used.

Example

>>> from networkx.utils import pairwise
>>> paths = [
...     (1, 2, 4, 3, 1, 4),
...     (5, 6, 7, 8, 5, 7, 8, 6),
... ]
>>> G = nx.Graph()
>>> G.add_nodes_from(it.chain(*paths))
>>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))
>>> # note this returns {1, 4} unlike k_edge_subgraphs
>>> sorted(map(sorted, k_edge_components(G, k=3)))
[[1, 4], [2], [3], [5, 6, 7, 8]]

References

1

https://en.wikipedia.org/wiki/Bridge_(graph_theory)

2

Wang, Tianhao, et al. (2015) A simple algorithm for finding all k-edge-connected components. http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0136264

wbia.algo.graph.nx_edge_kcomponents.k_edge_subgraphs(G, k)

Generates nodes in each maximal k-edge-connected subgraph in G.

Parameters

• G (NetworkX graph) –

• k (Integer) – Desired edge connectivity

Returns

k_edge_subgraphs – Each k-edge-subgraph is a maximal set of nodes that defines a subgraph of G that is k-edge-connected.

Return type

a generator of k-edge-subgraphs

See also

edge_connectivity()

k_edge_components()

similar to this function, but nodes only need to have k-edge-connctivity within the graph G and the subgraphs might not be k-edge-connected.

Raises

• NetworkXNotImplemented: – If the input graph is a multigraph.

• ValueError: – If k is less than 1

Notes

Attempts to use the most efficient implementation available based on k. If k=1, or k=2 and the graph is undirected, then this simply calls k_edge_components. Otherwise the algorithm from _[1] is used.

Example

>>> from networkx.utils import pairwise
>>> paths = [
...     (1, 2, 4, 3, 1, 4),
...     (5, 6, 7, 8, 5, 7, 8, 6),
... ]
>>> G = nx.Graph()
>>> G.add_nodes_from(it.chain(*paths))
>>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))
>>> # note this does not return {1, 4} unlike k_edge_components
>>> sorted(map(sorted, k_edge_subgraphs(G, k=3)))
[[1], [2], [3], [4], [5, 6, 7, 8]]

References

1

Zhou, Liu, et al. (2012) Finding maximal k-edge-connected subgraphs from a large graph. ACM International Conference on Extending Database Technology 2012 480-–491. https://openproceedings.org/2012/conf/edbt/ZhouLYLCL12.pdf

wbia.algo.graph.nx_utils module

TODO: the k-components will soon be implemented in networkx 2.0 use those instead

wbia.algo.graph.nx_utils.complement_edges(G)

wbia.algo.graph.nx_utils.connected_component_subgraphs(G)

wbia.algo.graph.nx_utils.demodata_bridge()

wbia.algo.graph.nx_utils.demodata_tarjan_bridge()

CommandLine:

python -m wbia.algo.graph.nx_utils demodata_tarjan_bridge –show

Example

>>> # ENABLE_DOCTEST
>>> from wbia.algo.graph.nx_utils import *  # NOQA
>>> G = demodata_tarjan_bridge()
>>> ut.quit_if_noshow()
>>> import wbia.plottool as pt
>>> pt.show_nx(G)
>>> ut.show_if_requested()

wbia.algo.graph.nx_utils.diag_product(s1, s2)

Does product, but iterates over the diagonal first

wbia.algo.graph.nx_utils.e_(u, v)

wbia.algo.graph.nx_utils.edge_df(graph, edges, ignore=None)

wbia.algo.graph.nx_utils.edges_between(graph, nodes1, nodes2=None, assume_disjoint=False, assume_dense=True)

Get edges between two components or within a single component

Parameters

• graph (nx.Graph) – the graph

• nodes1 (set) – list of nodes

• nodes2 (set) – if None it is equivlanet to nodes2=nodes1 (default=None)

• assume_disjoint (bool) – skips expensive check to ensure edges arnt returned twice (default=False)

CommandLine:

python -m wbia.algo.graph.nx_utils –test-edges_between

Example

>>> # ENABLE_DOCTEST
>>> from wbia.algo.graph.nx_utils import *  # NOQA
>>> import utool as ut
>>> edges = [
>>>     (1, 2), (2, 3), (3, 4), (4, 1), (4, 3),  # cc 1234
>>>     (1, 5), (7, 2), (5, 1),  # cc 567 / 5678
>>>     (7, 5), (5, 6), (8, 7),
>>> ]
>>> digraph = nx.DiGraph(edges)
>>> graph = nx.Graph(edges)
>>> nodes1 = [1, 2, 3, 4]
>>> nodes2 = [5, 6, 7]
>>> n2 = sorted(edges_between(graph, nodes1, nodes2))
>>> n4 = sorted(edges_between(graph, nodes1))
>>> n5 = sorted(edges_between(graph, nodes1, nodes1))
>>> n1 = sorted(edges_between(digraph, nodes1, nodes2))
>>> n3 = sorted(edges_between(digraph, nodes1))
>>> print('n2 == %r' % (n2,))
>>> print('n4 == %r' % (n4,))
>>> print('n5 == %r' % (n5,))
>>> print('n1 == %r' % (n1,))
>>> print('n3 == %r' % (n3,))
>>> assert n2 == ([(1, 5), (2, 7)]), '2'
>>> assert n4 == ([(1, 2), (1, 4), (2, 3), (3, 4)]), '4'
>>> assert n5 == ([(1, 2), (1, 4), (2, 3), (3, 4)]), '5'
>>> assert n1 == ([(1, 5), (5, 1), (7, 2)]), '1'
>>> assert n3 == ([(1, 2), (2, 3), (3, 4), (4, 1), (4, 3)]), '3'
>>> n6 = sorted(edges_between(digraph, nodes1 + [6], nodes2 + [1, 2], assume_dense=False))
>>> print('n6 = %r' % (n6,))
>>> n6 = sorted(edges_between(digraph, nodes1 + [6], nodes2 + [1, 2], assume_dense=True))
>>> print('n6 = %r' % (n6,))
>>> assert n6 == ([(1, 2), (1, 5), (2, 3), (4, 1), (5, 1), (5, 6), (7, 2)]), '6'

wbia.algo.graph.nx_utils.edges_cross(graph, nodes1, nodes2)

Finds edges between two sets of disjoint nodes. Running time is O(len(nodes1) * len(nodes2))

Parameters

• graph (nx.Graph) – an undirected graph

• nodes1 (set) – set of nodes disjoint from nodes2

• nodes2 (set) – set of nodes disjoint from nodes1.

wbia.algo.graph.nx_utils.edges_inside(graph, nodes)

Finds edges within a set of nodes Running time is O(len(nodes) ** 2)

Parameters

• graph (nx.Graph) – an undirected graph

• nodes1 (set) – a set of nodes

wbia.algo.graph.nx_utils.edges_outgoing(graph, nodes)

Finds edges leaving a set of nodes. Average running time is O(len(nodes) * ave_degree(nodes)) Worst case running time is O(G.number_of_edges()).

Parameters

• graph (nx.Graph) – a graph

• nodes (set) – set of nodes

Example

>>> # ENABLE_DOCTEST
>>> from wbia.algo.graph.nx_utils import *  # NOQA
>>> import utool as ut
>>> G = demodata_bridge()
>>> nodes = {1, 2, 3, 4}
>>> outgoing = edges_outgoing(G, nodes)
>>> assert outgoing == {(3, 5), (4, 8)}

wbia.algo.graph.nx_utils.ensure_multi_index(index, names)

wbia.algo.graph.nx_utils.group_name_edges(g, node_to_label)

wbia.algo.graph.nx_utils.is_complete(G, self_loops=False)

wbia.algo.graph.nx_utils.is_k_edge_connected(G, k)

wbia.algo.graph.nx_utils.k_edge_augmentation(G, k, avail=None, partial=False)

wbia.algo.graph.nx_utils.random_k_edge_connected_graph(size, k, p=0.1, rng=None)

Super hacky way of getting a random k-connected graph

Example

>>> # ENABLE_DOCTEST
>>> import wbia.plottool as pt
>>> from wbia.algo.graph.nx_utils import *  # NOQA
>>> size, k, p = 25, 3, .1
>>> rng = ut.ensure_rng(0)
>>> gs = []
>>> for x in range(4):
>>>     G = random_k_edge_connected_graph(size, k, p, rng)
>>>     gs.append(G)
>>> ut.quit_if_noshow()
>>> pnum_ = pt.make_pnum_nextgen(nRows=2, nSubplots=len(gs))
>>> fnum = 1
>>> for g in gs:
>>>     pt.show_nx(g, fnum=fnum, pnum=pnum_())

wbia.algo.graph.refresh module

wbia.algo.graph.state module

Module contents

wbia.algo.graph.IMPORT_TUPLES = []

Regen Command: cd /home/joncrall/code/wbia/wbia/algo/graph makeinit.py –modname=wbia.algo.graph

wbia.algo.graph.reassign_submodule_attributes(verbose=1)

Updates attributes in the __init__ modules with updated attributes in the submodules.

wbia.algo.graph.reload_subs(verbose=1)

Reloads wbia.algo.graph and submodules

wbia.algo.graph.rrrr(verbose=1)

Reloads wbia.algo.graph and submodules