calculates differences between topologies 'old' and 'new'
    returns a tuple with two network graph objects
    the first graph contains the added nodes, the secnod contains the added links
8775
def _make_diff(old, new, both):
    
    # make a copy of old topology to avoid tampering with it
    diff_edges = new.copy()
    not_different = [tuple(edge) for edge in both]
    diff_edges.remove_edges_from(not_different)
    # repeat operation with nodes
    diff_nodes = new.copy()
    not_different = []
    for new_node in new.nodes():
        if new_node in old.nodes():
            not_different.append(new_node)
    diff_nodes.remove_nodes_from(not_different)
    # return tuple with modified graphs
    # one for nodes and one for links
    return diff_nodes, diff_edges
659314
def _merge_cfgnodes(self, cfgnode_0, cfgnode_1):
        

        assert cfgnode_0.addr + cfgnode_0.size == cfgnode_1.addr
        addr0, addr1 = cfgnode_0.addr, cfgnode_1.addr
        new_node = cfgnode_0.merge(cfgnode_1)

        # Update the graph and the nodes dict accordingly
        if addr1 in self._nodes_by_addr:
            self._nodes_by_addr[addr1].remove(cfgnode_1)
            if not self._nodes_by_addr[addr1]:
                del self._nodes_by_addr[addr1]
        del self._nodes[cfgnode_1.block_id]

        self._nodes_by_addr[addr0].remove(cfgnode_0)
        if not self._nodes_by_addr[addr0]:
            del self._nodes_by_addr[addr0]
        del self._nodes[cfgnode_0.block_id]

        in_edges = list(self.graph.in_edges(cfgnode_0, data=True))
        out_edges = list(self.graph.out_edges(cfgnode_1, data=True))

        self.graph.remove_node(cfgnode_0)
        self.graph.remove_node(cfgnode_1)

        self.graph.add_node(new_node)
        for src, _, data in in_edges:
            self.graph.add_edge(src, new_node, **data)
        for _, dst, data in out_edges:
            self.graph.add_edge(new_node, dst, **data)

        # Put the new node into node dicts
        self._nodes[new_node.block_id] = new_node
        self._nodes_by_addr[addr0].append(new_node)
483751
def _compute_diff(existing, expected):

    '''
    
    '''

    diff = {}

    for key in ['location', 'contact', 'chassis_id']:
        if existing.get(key) != expected.get(key):
            _create_diff(diff,
                         _valid_str,
                         key,
                         existing.get(key),
                         expected.get(key))

    for key in ['community']:  # for the moment only onen
        if existing.get(key) != expected.get(key):
            _create_diff(diff,
                         _valid_dict,
                         key,
                         existing.get(key),
                         expected.get(key))

    return diff
662579
def prevnode(edges, component):
    """"""
    e = edges
    c = component
    n2c = [(a, b) for a, b in e if type(a) == tuple]
    c2n = [(a, b) for a, b in e if type(b) == tuple]
    node2cs = [(a, b) for a, b in e if b == c]
    c2nodes = []
    for node2c in node2cs:
        c2node = [(a, b) for a, b in c2n if b == node2c[0]]
        if len(c2node) == 0:
            # return []
            c2nodes = []
            break
        c2nodes.append(c2node[0])
    cs = [a for a, b in c2nodes]
    # test for connections that have no nodes
    # filter for no nodes
    nonodes = [(a, b) for a, b in e if type(a) != tuple and type(b) != tuple]
    for a, b in nonodes:
        if b == component:
            cs.append(a)
    return cs
179446
def merge_nodes(self, n1: str, n2: str, same_polarity: bool = True):
        

        for p in self.predecessors(n1):
            for st in self[p][n1]["InfluenceStatements"]:
                if not same_polarity:
                    st.obj_delta["polarity"] = -st.obj_delta["polarity"]
                st.obj.db_refs["UN"][0] = (n2, st.obj.db_refs["UN"][0][1])

            if not self.has_edge(p, n2):
                self.add_edge(p, n2)
                self[p][n2]["InfluenceStatements"] = self[p][n1][
                    "InfluenceStatements"
                ]

            else:
                self[p][n2]["InfluenceStatements"] += self[p][n1][
                    "InfluenceStatements"
                ]

        for s in self.successors(n1):
            for st in self.edges[n1, s]["InfluenceStatements"]:
                if not same_polarity:
                    st.subj_delta["polarity"] = -st.subj_delta["polarity"]
                st.subj.db_refs["UN"][0] = (n2, st.subj.db_refs["UN"][0][1])

            if not self.has_edge(n2, s):
                self.add_edge(n2, s)
                self[n2][s]["InfluenceStatements"] = self[n1][s][
                    "InfluenceStatements"
                ]
            else:
                self[n2][s]["InfluenceStatements"] += self[n1][s][
                    "InfluenceStatements"
                ]

        self.remove_node(n1)
19382
def _find_changed(old, new, both):
    
    # create two list of sets of old and new edges including cost
    old_edges = []
    for edge in old.edges(data=True):
        # skip links that are not in both
        if set((edge[0], edge[1])) not in both:
            continue
        # wrap cost in tuple so it will be recognizable
        cost = (edge[2]['weight'],)
        old_edges.append(set((edge[0], edge[1], cost)))
    new_edges = []
    for edge in new.edges(data=True):
        # skip links that are not in both
        if set((edge[0], edge[1])) not in both:
            continue
        # wrap cost in tuple so it will be recognizable
        cost = (edge[2]['weight'],)
        new_edges.append(set((edge[0], edge[1], cost)))
    # find out which edge changed
    changed = []
    for new_edge in new_edges:
        if new_edge not in old_edges:
            # new_edge is a set, convert it to list
            new_edge = list(new_edge)
            for item in new_edge:
                if isinstance(item, tuple):
                    # unwrap cost from tuple and put it in a dict
                    cost = {'weight': item[0]}
                    new_edge.remove(item)
            changed.append((new_edge[0], new_edge[1], cost))
    return changed
1010877
def __calculate_adjacency_lists(graph):
    """"""
    adj = {}
    for node in graph.get_all_node_ids():
        neighbors = graph.neighbors(node)
        adj[node] = neighbors
    return adj
1240839
def find_best_matching_node(self, new, old_nodes):
        
        name = new.__class__.__name__
        #: TODO: We should pick the BEST one from this list
        #: based on some "matching" criteria (such as matching ref name or params)
        matches = [c for c in old_nodes if name == c.__class__.__name__]
        if self.debug:
            print("Found matches for {}: {} ".format(new, matches))
        return matches[0] if matches else None
146385
def edges(self):
        
        canonical_edges = set()
        for v1, neighbours in self._vertices.items():
            for v2 in neighbours:
                edge = self.canonical_order((v1, v2))
                canonical_edges.add(edge)
        return canonical_edges
132773
def _find_new_additions(self):
        
        for node, in_degree in self.graph.in_degree_iter():
            if not self._already_known(node) and in_degree == 0:
                self.inner.put((self._scores[node], node))
                self.queued.add(node)
815577
def diff_op(self):
        
        if self.graph is not None:
            if isinstance(self.graph, graphtools.graphs.LandmarkGraph):
                diff_op = self.graph.landmark_op
            else:
                diff_op = self.graph.diff_op
            if sparse.issparse(diff_op):
                diff_op = diff_op.toarray()
            return diff_op
        else:
            raise NotFittedError("This PHATE instance is not fitted yet. Call "
                                 "'fit' with appropriate arguments before "
                                 "using this method.")
782288
def merge_graphs(self, other_docgraph, verbose=False):
        
        # keep track of all merged/old root nodes in case we need to
        # delete them or their attributes (e.g. 'metadata')
        if hasattr(self, 'merged_rootnodes'):
            self.merged_rootnodes.append(other_docgraph.root)
        else:
            self.merged_rootnodes = [other_docgraph.root]

        # renaming the tokens of the other graph to match this one
        rename_tokens(other_docgraph, self, verbose=verbose)
        self.add_nodes_from(other_docgraph.nodes(data=True))

        # copy token node attributes to the current namespace
        for node_id, node_attrs in other_docgraph.nodes(data=True):
            if istoken(other_docgraph, node_id) and \
                self.ns+':token' not in self.node[node_id]:
                    self.node[node_id].update({self.ns+':token': other_docgraph.get_token(node_id)})
        self.add_edges_from(other_docgraph.edges(data=True))

        # workaround for issues #89 and #96
        # copy the token node IDs / sentence node IDs from the other graph,
        # if this graph doesn't have such lists, yet
        if other_docgraph.name and not self.name:
            self.name = other_docgraph.name
        if other_docgraph.tokens and not self.tokens:
            self.tokens = other_docgraph.tokens
        if other_docgraph.sentences and not self.sentences:
            self.sentences = other_docgraph.sentences

        # there should be no dangling, unused root nodes in a merged graph
        self.merge_rootnodes(other_docgraph)
422294
def equiv_graph(self):
        
        eg = nx.Graph()
        for (u,v,d) in self.get_graph().edges(data=True):
            if d['pred'] == 'equivalentTo':
                eg.add_edge(u,v)
        return eg
1308402
def adjacent(self, node_a, node_b):
        """"""
        neighbors = self.neighbors(node_a)
        return node_b in neighbors
311881
def _diff_interface_lists(old, new):
    '''
    
    '''
    diff = _diff_lists(old, new, _nics_equal)

    # Remove duplicated addresses mac addresses and let libvirt generate them for us
    macs = [nic.find('mac').get('address') for nic in diff['unchanged']]
    for nic in diff['new']:
        mac = nic.find('mac')
        if mac.get('address') in macs:
            nic.remove(mac)

    return diff
396602
def diff(self):
        
        latest = self.latest
        current = NetJsonParser(self.json())
        return diff(current, latest)
1321147
def get_halfs(self, vertex1, vertex2):
        
        def grow(origin, other):
            frontier = set(self.neighbors[origin])
            frontier.discard(other)
            result = set([origin])
            while len(frontier) > 0:
                pivot = frontier.pop()
                if pivot == other:
                    raise GraphError("The graph can not be separated in two halfs "
                                     "by disconnecting vertex1 and vertex2.")
                pivot_neighbors = set(self.neighbors[pivot])
                pivot_neighbors -= result
                frontier |= pivot_neighbors
                result.add(pivot)
            return result

        vertex1_part = grow(vertex1, vertex2)
        vertex2_part = grow(vertex2, vertex1)
        return vertex1_part, vertex2_part