graphid.util.nx_dynamic_graph module

The main data structure for maintaining positive connected components and supporting dynamic addition and deletion of edges.

This uses a union-find-like algorithm (extended to support CC lookup) in the background, but could be implemented with another algorithm like Euler Tour Trees. UnionFind is good if you are mostly adding edges, but if you expect to remove edges a lot, then using a forest of ETTs may be better.

class graphid.util.nx_dynamic_graph.GraphHelperMixin

Bases: NiceRepr

Ensures that we always return edges in a consistent order

has_nodes(nodes)

has_edges(edges)

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

class graphid.util.nx_dynamic_graph.NiceGraph(incoming_graph_data=None, **attr)

Bases: Graph, GraphHelperMixin

Initialize a graph with edges, name, or graph attributes.

Parameters:

• incoming_graph_data (input graph (optional, default: None)) – Data to initialize graph. If None (default) an empty graph is created. The data can be an edge list, or any NetworkX graph object. If the corresponding optional Python packages are installed the data can also be a 2D NumPy array, a SciPy sparse array, or a PyGraphviz graph.

• attr (keyword arguments, optional (default= no attributes)) – Attributes to add to graph as key=value pairs.

See also

convert

Examples

>>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> G = nx.Graph(name="my graph")
>>> e = [(1, 2), (2, 3), (3, 4)]  # list of edges
>>> G = nx.Graph(e)

Arbitrary graph attribute pairs (key=value) may be assigned

>>> G = nx.Graph(e, day="Friday")
>>> G.graph
{'day': 'Friday'}

class graphid.util.nx_dynamic_graph.nx_UnionFind(elements=None)

Bases: object

Based off code in networkx

clear()

rebalance(elements=None)

to_sets()

union(*objects)

Find the sets containing the objects and merge them all.

remove_entire_cc(elements)

add_element(x)

add_elements(elements)

class graphid.util.nx_dynamic_graph.DynConnGraph(*args, **kwargs)

Bases: 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

Data Structure | Insertion | Deletion | CC Find |

UnionFind | lg(n) | n | No UnionFind2 | n* | n | 1 EulerTourForest | lg^2(n) | lg^2(n) | lg(n) / lglg(n) - - Ammortized

• O(n) is worst case, but it seems to be very quick in practice. The average runtime should be close to lg(n), but I’m writing this doc 8 months after working on this algo, so I may not remember exactly.

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

Example

>>> 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())
>>> # xdoctest: +REQUIRES(--show)
>>> import plottool_ibeis as pt
>>> pt.qtensure()
>>> pt.show_nx(self)

# todo: check if nodes exist when adding

clear()

number_of_components()

component(label)

component_nodes(label)

connected_to(node)

node_label(node)

Example

>>> 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)

are_nodes_connected(u, v)

connected_components()

Example

>>> self = DynConnGraph()
>>> self.add_edges_from([(1, 2), (2, 3), (4, 5), (6, 7)])
>>> ccs = list(self.connected_components())
>>> result = 'ccs = {}'.format(ub.urepr(ccs, nl=0))
>>> print(result)
ccs = [{1, 2, 3}, {4, 5}, {6, 7}]

component_labels()

_cut(u, v)

Decremental connectivity (slow)

_union(u, v)

Incremental connectivity (fast)

_add_node(n)

_remove_node(n)

add_edge(u, v, **attr)

Example

>>> 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_node(n, **attr)

add_nodes_from(nodes, **attr)

remove_edge(u, v)

Example

>>> 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_nodes_from(nodes)

remove_node(n)

Example

>>> 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}}

subgraph(nbunch, dynamic=False)