Фильтровать вершины по нескольким свойствам — Джулия

Я работаю над julia с библиотекой Metagraphs.jl. Чтобы решить проблему оптимизации, я хотел бы получить набор/список ребер в графе, которые указывают на специальный набор вершин, имеющих 2 общих свойства.

Моей первой догадкой было сначала получить набор/список вершин. Но я столкнулся с первой проблемой, которая заключается в том, что функция filter_vertices, похоже, не принимает применение фильтра к более чем одному свойству. Ниже приведен пример того, что я хотел бы сделать:

g = DiGraph(5)
mg = MetaDiGraph(g, 1.0)

add_vertex!(mg)

add_edge!(mg,1,2)
add_edge!(mg,1,3)
add_edge!(mg,1,4)
add_edge!(mg,2,5)
add_edge!(mg,3,5)
add_edge!(mg,5,6)
add_edge!(mg,4,6)

set_props!(mg,3,Dict(:prop1=>1,:prop2=>2))

set_props!(mg,1,Dict(:prop1=>1,:prop2=>0))
set_props!(mg,2,Dict(:prop1=>1,:prop2=>0))
set_props!(mg,4,Dict(:prop1=>0,:prop2=>2))
set_props!(mg,5,Dict(:prop1=>0,:prop2=>2))
set_props!(mg,6,Dict(:prop1=>0,:prop2=>0))

col=collect(filter_vertices(mg,:prop1,1,:prop2,2))

И я хочу, чтобы col нашла вершину 3 и никакие другие.

Но filter_vertices допускает только одно свойство за раз, и тогда становится более затратным выполнять цикл с двумя фильтрами, а затем пытаться сравнивать, чтобы отсортировать список с вершинами, которые имеют оба свойства.

Учитывая размер моего графа, я хотел бы избежать определения этого набора с несколькими и дорогостоящими циклами. Кто-нибудь из вас знает, как решить эту проблему простым и мягким способом?

В итоге я сделал это, чтобы ответить на свой вопрос:

fil3=Array{Int64,1}()
fil1=filter_vertices(mg,:prop1,1)
for f in fil1
    if get_prop(mg,f,:prop2)==2
        push!(fil3,f)
    end
end            
println(fil3)

Но скажи мне, если у тебя есть что-нибудь более интересное

Спасибо за вашу помощь!


filter graph julia vertex
person Alexo    schedule 07.03.2018    source источник
comment
Пожалуйста, рассмотрите возможность открытия задач в репозиториях LightGraphs/MetaGraphs. Таким образом, мы немедленно получаем уведомление и можем помочь напрямую.   -  person sbromberger    schedule 13.04.2018

Ответы (2)


arrow_upward
2
arrow_downward

Пожалуйста, предоставьте минимальный рабочий пример таким образом, чтобы мы могли просто скопировать и вставить его и сразу начать. Также укажите, где в коде возникает проблема. Ниже приведен пример для вашего сценария:

Pkg.add("MetaGraphs")

using LightGraphs, MetaGraphs

g = DiGraph(5)
mg = MetaDiGraph(g, 1.0)

add_vertex!(mg)

add_edge!(mg,1,2)
add_edge!(mg,1,3)
add_edge!(mg,1,4)
add_edge!(mg,2,5)
add_edge!(mg,3,5)
add_edge!(mg,5,6)
add_edge!(mg,4,6)

set_props!(mg,3,Dict(:prop1=>1,:prop2=>2))
set_props!(mg,1,Dict(:prop1=>1,:prop2=>0))
set_props!(mg,2,Dict(:prop1=>1,:prop2=>0))
set_props!(mg,4,Dict(:prop1=>0,:prop2=>2))
set_props!(mg,5,Dict(:prop1=>0,:prop2=>2))
set_props!(mg,6,Dict(:prop1=>0,:prop2=>0))

function my_vertex_filter(g::AbstractMetaGraph, v::Integer, prop1, prop2)
  return has_prop(g, v, :prop1) && get_prop(g, v, :prop1) == prop1 &&
         has_prop(g, v, :prop2) && get_prop(g, v, :prop2) == prop2
end

prop1 = 1
prop2 = 2

col = collect(filter_vertices(mg, (g,v)->my_vertex_filter(g,v,prop1,prop2)))
# returns Int[3]

Пожалуйста, проверьте ?filter_vertices --- это дает вам подсказку о том, что/как написать, чтобы определить ваш собственный фильтр.

ИЗМЕНИТЬ. Для фильтрации краев вы можете посмотреть ?filter_edges, чтобы узнать, что вам нужно для достижения фильтрации краев. Добавьте приведенный ниже отрывок кода к приведенному выше решению, чтобы получить результаты:

function my_edge_filter(g, e, prop1, prop2)
  v = dst(e) # get the edge's destination vertex
  return my_vertex_filter(g, v, prop1, prop2)
end

myedges = collect(filter_edges(mg, (g,e)->my_edge_filter(g,e,prop1,prop2)))
# returns [Edge 1 => 3]
person Arda Aytekin    schedule 07.03.2018
comment
Спасибо за помощь, действительно работает лучше. Но у меня есть вопрос относительно остальной части того, что я собираюсь сделать, я хотел бы, чтобы ребра входили в эти вершины с помощью этих специальных реквизитов, и я использую функцию in_edges, но, похоже, она возвращает вершины. Я хотел бы, чтобы он возвращал края, вы знаете простой способ сделать это? - person Alexo; 07.03.2018
comment
@Alexo Алексо, я обновил свой ответ. Трудно понять из вашего комментария, но я думаю, вам нужно что-то подобное. Пожалуйста, в следующий раз напишите точную проблему, которую вы хотели бы решить. Соответственно, вы можете обновить свой вопрос выше. - person Arda Aytekin; 07.03.2018
comment
Привет @Arda, спасибо, и да, это было то, что мне было нужно. Проблема, касающаяся моей реальной проблемы, которую я хотел бы решить, заключается в следующем: 1. Она довольно огромна и требует нескольких файлов julia с несколькими различными объектами, графиками, переменными. 2. Содержание и данные модели не могут быть размещены в Интернете. Вот почему я попытался объяснить свою проблему с помощью простой модели, и вы правильно поняли. На самом деле я не знал, как определить функцию для ввода функции filter_edges. Еще раз спасибо. - person Alexo; 09.03.2018
comment
@Alexo Честно говоря, я не смог этого сделать с первого раза. Может быть, нам следует открыть запрос на включение документации этого пакета. Если бы был пример по этому сценарию, таким людям, как вы, в будущем было бы легче. Я только что проверил справку по REPL и сделал несколько предположений, используя экспортированные функции из пакета. Согласно вашему MWE, на мой взгляд, достаточно написать свой фрагмент кода с только тремя add_edge! и set_props! и задать вопрос, который вы задали здесь в комментариях: Как я могу отфильтровать ребра на двух характеристики? Я хотел бы получить 1 => 3. - person Arda Aytekin; 09.03.2018
comment
да, я не смог найти объяснения того, как определить эту функцию fn, которую они описывают на страницах Github. Написано только, что ввод должен быть (g,v). Больше информации для людей в будущем может быть только хорошо. И да, для функции in_edges она, похоже, не возвращает края. Однако я не знаю, как открыть запрос на вытягивание или еще... Я только начал julia два месяца назад. - person Alexo; 12.03.2018
comment
Функция filter_vertices, которая принимает граф и вершину, предназначена для возврата логического значения, если вершина должна быть включена. См. juliagraphs.github.io/MetaGraphs.jl/latest. /{MetaGraphs.AbstractMetaGraph,Function}: вернуть итератор для всех вершин... где функция fn возвращает значение true только для вершин, которые должны быть включены в итератор. - person sbromberger; 13.03.2018
comment
Если бы был пример по этому сценарию, таким людям, как вы, в будущем было бы легче. Я согласен, что документация документирует это правильно. Пример был бы хорош. Мне нужно было проверить соответствующую строку пишите код нормально. - person Arda Aytekin; 13.03.2018

arrow_upward
0
arrow_downward

Я нашел это решение:

function filter_function1(g,prop1,prop2)
  fil1=filter_vertices(g,:prop1,prop1)
  fil2=filter_vertices(g,:prop2,prop2)
  filter=intersect(fil1,fil2)
  return filter
end

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

function filter_function2(g,prop1,prop2)
  filter=Set{Int64}()
  fil1=filter_vertices(g,:prop1,prop1)
  for f in fil1
      if get_prop(g,f,:prop2)==prop2
          push!(filter,f)
      end
  end
  return filter
end

Я открыт для любых других ответов, если у вас есть более элегантные.

person Alexo    schedule 07.03.2018
comment
Проверьте мой ответ. Я не думаю, что вы должны проходить цикл дважды --- пакет позволяет вам написать собственный фильтр. Выше filter_function1 дважды перебирает ваш график и вызывает intersect. Сложность огромная. Вы можете улучшить filter_function2 с помощью простого понимания массива. - person Arda Aytekin; 07.03.2018