Contents

require 'tangle/directed/graph'
require 'tangle/directed/acyclic/partial_order'

module Tangle
  module Directed
    module Acyclic
      # A directed acyclic graph
      class Graph < Tangle::Directed::Graph
        # Return a topological ordering of a set of vertices, or all
        # vertices in the graph.
        def topological_ordering(*vertices)
          PartialOrder[self, *vertices].sort!.map(&:vertex)
        end

        protected

        def insert_edge(edge)
          raise CyclicError if successor?(edge.head, edge.tail) ||
                               predecessor?(edge.tail, edge.head)
          super
        end
      end
    end
  end
end

Version data entries

4 entries across 4 versions & 1 rubygems

Version	Path
tangle-0.9.0	lib/tangle/directed/acyclic/graph.rb
tangle-0.8.2	lib/tangle/directed/acyclic/graph.rb
tangle-0.8.1	lib/tangle/directed/acyclic/graph.rb
tangle-0.8.0	lib/tangle/directed/acyclic/graph.rb