class DirectedGraph::Graph

Attributes

edges[R]

Public Class Methods

new(edges = []) click to toggle source
# File lib/directed_graph/graph.rb, line 7
def initialize(edges = [])
  @edges = edges
end

Public Instance Methods

children(vertex) click to toggle source
# File lib/directed_graph/graph.rb, line 40
def children(vertex)
  edges.select {|e| e.origin_vertex.name == vertex.name}.map{|e| e.destination_vertex}
end
compute_key(external_identifier) click to toggle source

Generate a string key from an array of identifiers

# File lib/directed_graph/graphml.rb, line 7
def compute_key(external_identifier)
  x = [external_identifier].flatten
  x.map! {|xx| xx.to_s}
  x.join("_")
end
longest_path(origin_vertex_name, destination_vertex, result = []) click to toggle source
# File lib/directed_graph/graph.rb, line 33
def longest_path(origin_vertex_name, destination_vertex, result = [])
  return [destination_vertex] + result if origin_vertex_name == destination_vertex.name
  parents(destination_vertex).map do |v|
    longest_path(origin_vertex_name, v, [destination_vertex] + result)
  end.inject([]) {|m, arr| m = arr if arr.length > m.length; m}
end
ordered_edges() click to toggle source
# File lib/directed_graph/graph.rb, line 17
def ordered_edges
  sorted_vertices.inject([]) do |memo, v|
    edge = edges.select {|e| e.destination_vertex == v}
    memo.push(*edge) if edge
    memo
  end
end
parents(vertex) click to toggle source
# File lib/directed_graph/graph.rb, line 44
def parents(vertex)
  edges.select {|e| e.destination_vertex.name == vertex.name}.map{|e| e.origin_vertex}
end
shortest_path(origin_vertex, destination_vertex) click to toggle source
# File lib/directed_graph/graph.rb, line 29
def shortest_path(origin_vertex, destination_vertex)
  simple_graph.shortest_path(origin_vertex, destination_vertex)
end
sorted_vertices() click to toggle source
# File lib/directed_graph/graph.rb, line 25
def sorted_vertices
  JobRunner.sorted_vertices(vertices_and_children)
end
to_graphml() click to toggle source

Return graph as graphml text

# File lib/directed_graph/graphml.rb, line 14
def to_graphml()
  builder = Builder::XmlMarkup.new(:indent => 1)
  builder.instruct! :xml, :version => "1.0"

  graphml_attribs = {
    "xmlns" => "http://graphml.graphdrawing.org/xmlns",
    "xmlns:xsi" => "http://www.w3.org/2001/XMLSchema-instance",
    "xmlns:y" => "http://www.yworks.com/xml/graphml",
    "xmlns:yed" => "http://www.yworks.com/xml/yed/3",
    "xsi:schemaLocation" => "http://graphml.graphdrawing.org/xmlns http://www.yworks.com/xml/schema/graphml/1.1/ygraphml.xsd",
    :directed => "1",
    :label => "test"
  }

  builder.graphml(graphml_attribs) do

    # Define key id's at top of graphml file
    builder.key({:for=>"node", :id=>"d3", "yfiles.type"=>"nodegraphics"})

    # Build Graph
    #
    builder.graph({:id=>"G"}) do

      vertices.each do |vertex|

        builder.node(:id => compute_key([vertex.name, vertex.object_id])) do

          builder.data({:key=>"d3"}) do
            builder.tag!("y:ShapeNode") do

              graphics = vertex.data.fetch(:graphics, {})
              graphics.fetch(:fill, []).each    {|f| builder.tag! "y:Fill",    {:color=>f, :transparent=>"false"}}
              graphics.fetch(:shape,[]).each    {|s| builder.tag! "y:Shape",   {:type=>s}}
              graphics.fetch(:geometry,[]).each {|s| builder.tag! "y:Geometry", s}
              graphics.fetch(:label,[]).each    {|l| builder.tag! "y:NodeLabel", l}
            end
          end
        end
      end

      edges.each do |edge|
        source = edge.origin_vertex
        target = edge.destination_vertex

        options = edge.data[:options]
        label   = ""

        builder.edge(
          :source => s = compute_key([source.name, source.object_id]), 
          :target => t = compute_key([target.name, target.object_id]), 
          :id => compute_key([source.name, target.name, edge.object_id]),
          :label => "#{label}"
        ) do
          #edge[:attributes].each_pair { |k, v|
          #  id_str = compute_key([k,:edge_attr])
          #  builder.data(v.to_s, {:key=>@guid[id_str]})
          #}
        end
      end
    end
  end
  builder.target!
end
vertices() click to toggle source
# File lib/directed_graph/graph.rb, line 11
def vertices
  r = []
  edges.each {|e| r.push(e.origin_vertex, e.destination_vertex)}
  r.uniq {|e| e.object_id}
end

Private Instance Methods

simple_graph() click to toggle source
# File lib/directed_graph/graph.rb, line 54
def simple_graph
  graph = SimpleGraph::Graph.new
  vertices.each do |v|
    graph.add_vertex(v)
  end
  edges.each do |e|
    graph.add_edge(e.origin_vertex, e.destination_vertex)
  end
  graph
end
vertices_and_children() click to toggle source
# File lib/directed_graph/graph.rb, line 50
def vertices_and_children
  vertices.map {|v| [v, children(v)]}
end