graphid.core.mixin_redundancy module¶
Functionality related to the k-edge redundancy measures
- class graphid.core.mixin_redundancy._RedundancyComputers[source]¶
Bases:
object
methods for computing redundancy
These are used to compute redundancy bookkeeping structures. Thus, they should not use them in their calculations.
- is_pos_redundant(cc, k=None, relax=None, assume_connected=False)[source]¶
Tests if a group of nodes is positive redundant. (ie. if the group is k-edge-connected)
CommandLine
python -m graphid.core.mixin_dynamic _RedundancyComputers.is_pos_redundant
Example
>>> from graphid import demo >>> infr = demo.demodata_infr(ccs=[(1, 2, 3)], pos_redun=1) >>> cc = infr.pos_graph.connected_to(1) >>> flag1 = infr.is_pos_redundant(cc) >>> infr.add_feedback((1, 3), POSTV) >>> flag2 = infr.is_pos_redundant(cc, k=2) >>> flags = [flag1, flag2] >>> print('flags = %r' % (flags,)) flags = [False, True] >>> # xdoc: +REQUIRES(--show) >>> from graphid import util >>> infr.show() >>> util.show_if_requested()
- is_neg_redundant(cc1, cc2, k=None)[source]¶
Tests if two disjoint groups of nodes are negative redundant (ie. have at least k negative edges between them).
CommandLine
python -m graphid.core.mixin_dynamic _RedundancyComputers.is_neg_redundant --show
Example
>>> from graphid import demo >>> infr = demo.demodata_infr(ccs=[(1, 2), (3, 4)], ignore_pair=True) >>> infr.params['redun.neg'] = 2 >>> cc1 = infr.pos_graph.connected_to(1) >>> cc2 = infr.pos_graph.connected_to(3) >>> flag1 = infr.is_neg_redundant(cc1, cc2) >>> infr.add_feedback((1, 3), NEGTV) >>> flag2 = infr.is_neg_redundant(cc1, cc2) >>> infr.add_feedback((2, 4), NEGTV) >>> flag3 = infr.is_neg_redundant(cc1, cc2) >>> flags = [flag1, flag2, flag3] >>> print('flags = %r' % (flags,)) >>> assert flags == [False, False, True] >>> # xdoc: +REQUIRES(--show) >>> from graphid import util >>> infr.show() >>> util.show_if_requested()
- find_neg_nid_freq_to(cc)[source]¶
Find the number of edges leaving cc and directed towards specific names.
- find_neg_redun_nids_to(cc)[source]¶
Get PCCs that are k-negative redundant with cc
Example
>>> from graphid import demo >>> infr = demo.demodata_infr() >>> node = 20 >>> cc = infr.pos_graph.connected_to(node) >>> infr.params['redun.neg'] = 2 >>> infr.find_neg_redun_nids_to(cc)
- find_non_neg_redun_pccs(k=None, cc=None)[source]¶
Get pairs of PCCs that are not complete.
- Parameters:
k (int) – level of redunency to be considered complete
cc (set, optional) – if specified only search for other pccs that are not negative redundant to this particular cc
Example
>>> from graphid import demo >>> infr = demo.demodata_infr(pcc_sizes=[1, 1, 2, 3, 5, 8], ignore_pair=True) >>> non_neg_pccs = list(infr.find_non_neg_redun_pccs(k=2)) >>> assert len(non_neg_pccs) == (6 * 5) / 2
- class graphid.core.mixin_redundancy._RedundancyAugmentation[source]¶
Bases:
object
- find_neg_augment_edges(cc1, cc2, k=None)[source]¶
Find enough edges to between two pccs to make them k-negative complete The two CCs should be disjoint and not have any positive edges between them.
- Parameters:
cc1 (set) – nodes in one PCC
cc2 (set) – nodes in another positive-disjoint PCC
k (int) – redundnacy level (if None uses infr.params[‘redun.neg’])
Example
>>> from graphid import demo >>> k = 2 >>> cc1, cc2 = {1}, {2, 3} >>> # --- return an augmentation if feasible >>> infr = demo.demodata_infr(ccs=[cc1, cc2], ignore_pair=True) >>> edges = set(infr.find_neg_augment_edges(cc1, cc2, k=k)) >>> assert edges == {(1, 2), (1, 3)} >>> # --- if infeasible return a partial augmentation >>> infr.add_feedback((1, 2), INCMP) >>> edges = set(infr.find_neg_augment_edges(cc1, cc2, k=k)) >>> assert edges == {(1, 3)}
- find_pos_augment_edges(pcc, k=None)[source]¶
# [[1, 0], [0, 2], [1, 2], [3, 1]] pos_sub = nx.Graph([[0, 1], [1, 2], [0, 2], [1, 3]])
- find_pos_redun_candidate_edges(k=None, verbose=False)[source]¶
Searches for augmenting edges that would make PCCs k-positive redundant
CommandLine
python -m graphid.core.mixin_dynamic _RedundancyAugmentation.find_pos_redun_candidate_edges
Doctest
>>> from graphid.core.mixin_redundancy import * # NOQA >>> from graphid import demo >>> # FIXME: this behavior seems to change depending on Python version >>> infr = demo.demodata_infr(ccs=[(1, 2, 3, 4, 5), (7, 8, 9, 10)], pos_redun=1) >>> infr.add_feedback((2, 5), POSTV) >>> infr.add_feedback((1, 5), INCMP) >>> infr.params['redun.pos'] = 2 >>> candidate_edges = sorted(infr.find_pos_redun_candidate_edges()) ... >>> result = ('candidate_edges = ' + ub.urepr(candidate_edges, nl=0)) >>> print(result) candidate_edges = [(1, 4), ..., (7, 10)]
- find_neg_redun_candidate_edges(k=None)[source]¶
Get pairs of PCCs that are not complete. Finds edges that might complete them.
Example
>>> from graphid import demo >>> infr = demo.demodata_infr(ccs=[(1,), (2,), (3,)], ignore_pair=True) >>> edges = list(infr.find_neg_redun_candidate_edges()) >>> assert len(edges) == 3, 'all should be needed here' >>> infr.add_feedback_from(edges, evidence_decision=NEGTV) >>> assert len(list(infr.find_neg_redun_candidate_edges())) == 0
Example
>>> from graphid import demo >>> infr = demo.demodata_infr(pcc_sizes=[3] * 20, ignore_pair=True) >>> ccs = list(infr.positive_components()) >>> gen = infr.find_neg_redun_candidate_edges(k=2) >>> for edge in gen: >>> # What happens when we make ccs positive >>> print(infr.node_labels(edge)) >>> infr.add_feedback(edge, evidence_decision=POSTV) >>> import ubelt as ub >>> infr = demo.demodata_infr(pcc_sizes=[1] * 30, ignore_pair=True) >>> ccs = list(infr.positive_components()) >>> gen = infr.find_neg_redun_candidate_edges(k=3) >>> for chunk in ub.chunks(gen, 2): >>> for edge in chunk: >>> # What happens when we make ccs positive >>> print(infr.node_labels(edge)) >>> infr.add_feedback(edge, evidence_decision=POSTV)
list(gen)
- class graphid.core.mixin_redundancy.Redundancy[source]¶
Bases:
_RedundancyComputers
,_RedundancyAugmentation
methods for dynamic redundancy book-keeping
- filter_edges_flagged_as_redun(edges)[source]¶
Returns only edges that are not flagged as redundant. Uses bookkeeping structures
Example
>>> from graphid import demo >>> infr = demo.demodata_infr(num_pccs=1, size=4) >>> infr.clear_edges() >>> infr.ensure_cliques() >>> infr.clear_feedback() >>> print(ub.urepr(infr.status())) >>> nonredun_edges = list(infr.filter_edges_flagged_as_redun( >>> infr.unreviewed_graph.edges())) >>> assert len(nonredun_edges) == 6
- update_extern_neg_redun(nid, may_add=True, may_remove=True, force=False)[source]¶
Checks if nid is negative redundant to any other cc it has at least one negative review to. (TODO: NEG REDUN CAN BE CONSOLIDATED VIA NEG-META-GRAPH)
- update_neg_redun_to(nid1, other_nids, may_add=True, may_remove=True, force=False)[source]¶
Checks if nid1 is neg redundant to other_nids. Edges are either removed or added to the queue appropriately. (TODO: NEG REDUN CAN BE CONSOLIDATED VIA NEG-META-GRAPH)
- update_pos_redun(nid, may_add=True, may_remove=True, force=False)[source]¶
Checks if a PCC is newly, or no longer positive redundant. Edges are either removed or added to the queue appropriately.