Блог

Главная - Вопросы по программированию - networkx: как установить пользовательскую функцию затрат?

networkx: как установить пользовательскую функцию затрат?

#python #networkx #edit-distance

#python #networkx #редактировать-расстояние

Вопрос:

Я следую документации networkx (1), и я хотел бы установить различные штрафы для функции затрат (например node_del_cost , и node_ins_cost ). Допустим, я хотел бы оштрафовать удаление / вставку узла на три балла.

До сих пор я создал два неориентированных графика, которые отличаются маркировкой узла C (ОБНОВЛЕННЫЙ КОД).

 import networkx as nx

G=nx.Graph()
G.add_nodes_from([("A", {'label':'CDKN1A'}), ("B", {'label':'CUL4A'}), 
    ("C", {'label':'RB1'})])

G.add_edges_from([("A","B"), ("A","C")])

H=nx.Graph()
H.add_nodes_from([("A", {'label':'CDKN1A'}), ("B", {'label':'CUL4A'}),
    ("C", {'label':'AKT'})])
H.add_edges_from([("A","B"), ("A","C")])

# arguments
# node_match – a function that returns True if node n1 in G1 and n2 in G2 should be considered equal during matching.
# ignored if node_subst_cost is specified
def node_match(node1, node2):
    return node1['label']==node2['label']

# node_subst_cost - a function that returns the costs of node substitution
# overrides node_match if specified.
def node_subst_cost(node1, node2): 
    return node1['label']==node2['label']

# node_del_cost - a function that returns the costs of node deletion
# if node_del_cost is not specified then default node deletion cost of 1 is used.
def node_del_cost(node1):
    return node1['label']==3    

# node_ins_cost - a function that returns the costs of node insertion
# if node_ins_cost is not specified then default node insertion cost of 1 is used.
def node_ins_cost(node2):
    return node2['label']==3    

paths, cost = nx.optimal_edit_paths(G, H, node_match=None, edge_match=None, 
    node_subst_cost=node_subst_cost, node_del_cost=node_del_cost, node_ins_cost=node_ins_cost, 
    edge_subst_cost=None, edge_del_cost=None, edge_ins_cost=None, 
    upper_bound=None)

# length of the path
print(len(paths))

# optimal edit path cost (graph edit distance).
print(cost)

Это дает мне 2.0 оптимальную стоимость пути и 7.0 длину пути. Однако я не совсем понимаю, почему, потому что я установил штраф в 3.0, поэтому ожидается, что расстояние редактирования будет 3.

Спасибо за ваши предложения!

Olha

Комментарии:

1. Ваша ошибка внизу — from node_del_cost и node_ins_cost parameters , в документации указано, что входные данные для этого параметра являются «вызываемыми». 2 — это целое число, а целые числа являются вызываемыми. Вам нужна какая-то функция для этих параметров.

2. Я выяснил, что len (пути) означает количество разных путей в виде node_tuple и edge_tuple . Но я все еще не понимаю, как установить пользовательскую функцию затрат.

3. еще одно наблюдение заключается в том, что если я укажу параметры ‘node_match’ и ‘edge_match’, несогласованные метки из узлов и несогласованные ребра будут оштрафованы на 1.

4. @OlhaKholod также учтите, что функции затрат должны возвращать float или int , вот они возвращаются bool .

Ответ №1:

Как упоминалось в документации, когда вы передаете node_subst_cost функцию в качестве параметра, она игнорирует node_match функцию и применяет стоимость для любой операции подстановки, даже если узлы равны. Поэтому я бы посоветовал сначала оценить равенство узлов в node_subst_cost функции, а затем соответствующим образом применить стоимость:

 def node_subst_cost(node1, node2):
    # check if the nodes are equal, if yes then apply no cost, else apply 3
    if node1['label'] == node2['label']:
        return 0
    return 3


def node_del_cost(node):
    return 3  # here you apply the cost for node deletion


def node_ins_cost(node):
    return 3  # here you apply the cost for node insertion


paths, cost = nx.optimal_edit_paths(
    G,
    H,
    node_subst_cost=node_subst_cost,
    node_del_cost=node_del_cost,
    node_ins_cost=node_ins_cost
)

print(cost)  # which will return 3.0

Вы также можете сделать то же самое для граничных операций.