Как реализовать неориентированного графа в Ruby on Rails?

Question

Как реализовать неориентированного графа в Ruby on Rails?

Одним из способов может быть перечисление всех открытых дескрипторов в системе или, по крайней мере, открытых дескрипторов заданного целевого процесса, пока вы не найдете интересующий дескриптор SOCKET (см. HOWTO: Перечислить дескрипторы [ 118], Дескрипторы сокетов и C ++ Получить дескриптор открытых сокетов программы - хотя я не уверен, как вы сможете получить пары IP / порт для [ 111], чтобы сравнить с интересующим вас активным соединением, не вводя удаленные вызовы getsockname() / getpeername() в процесс владения SOCKET).

Как только вы нашли нужный дескриптор SOCKET, вы можете закрыть его, используя DuplicateHandle() с флагом DUPLICATE_CLOSE_SOURCE ^{1 sup>.}

^{1: так работает функция «Закрыть дескриптор» в Process Explorer. Sup>}

5

algorithm ruby ruby-on-rails

задан Javier 23 February 2009 в 15:46

1 ответ

Другие вопросы по тегам:

algorithm ruby ruby-on-rails

Похожие вопросы:

score 9 · Accepted Answer

Не знающий о любой существующей библиотеке, которая предлагает логику графика сверху ActiveRecord.

Вам, вероятно, придется реализовать Вашу собственную Вершину, Край ActiveRecord-поддержанные модели (см. vertex.rb и edge.rb в Вашей установке направляющих rails/activerecord/test/fixtures каталог), например.

### From Rails: ###

# This class models an edge in a directed graph.
class Edge < ActiveRecord::Base
  belongs_to :source, :class_name => 'Vertex', :foreign_key => 'source_id'
  belongs_to :sink,   :class_name => 'Vertex', :foreign_key => 'sink_id'
end

# This class models a vertex in a directed graph.
class Vertex < ActiveRecord::Base
  has_many :sink_edges, :class_name => 'Edge', :foreign_key => 'source_id'
  has_many :sinks, :through => :sink_edges

  has_and_belongs_to_many :sources,
    :class_name => 'Vertex', :join_table => 'edges',
    :foreign_key => 'sink_id', :association_foreign_key => 'source_id'
end

Чтобы заставить вышеупомянутое вести себя как adirected график, думайте о вставке дополнительного края также при вставке края. Также обратите внимание что использование has_and_belongs_to_many теперь препятствуется, можно использовать has_many :sources ... :through => :edges вместо этого. Любые осуществления могут быть сделаны посредством проверки (т.е. вершина не имеет края к себе) и/или ограничения базы данных (ограничение/индекс уникальности на [source_id,sink_id] в edges гарантирует, что вершины V1---> V2 не соединены больше чем одним ориентированным ребром и вершинами V1 <---V2 не соединен больше чем одним ориентированным ребром также.)

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

запишите минимальную сумму логики графика, требуемой Вашим приложением сверху вышеупомянутых моделей, с помощью ActiveRecord отношения (например. vertex1.edges.first.sink.edges ...); это приведет к значительному количеству поездок в прямом и обратном направлениях, совершенных в базу данных
импорт RGL; выберите все вершины и края от DB в RGL, и используйте RGL, чтобы сделать обход графика, например.

.

    edges = Edge.find(:all)
    dg = RGL::AdjacencyGraph.new(edges.inject([]) { |adj,edge|
      adj << edge.source_id << edge.sink_id
    })
    # have fun with dg
    # e.g. isolate a subset of vertex id's using dg, then
    # load additional info from the DB for those vertices:
    vertices = Vertex.find(vertex_ids)

Вышеупомянутое снижает Ваше общее количество SQL-операторов (в операциях только для чтения) к 2, но может поместить деформацию на Вашу базу данных или память если график (Edge.find(:all)) является большим - в которой точке можно думать о дальнейших способах ограничить объем данных, которого Вы на самом деле требуете, например, только заботитесь о red соединения вершин:

    Edge.find(:all,
              :joins => :sources, # or sinks; indifferent since symmetric
              :conditions => [ 'vertices.red = ?', true ]
    )