### Home Classes Methods

### In Files

- lib/graphviz/theory.rb

### Parent

Object

### Methods

- ::new
- #adjancy_matrix
- #critical_path
- #degree
- #incidence_matrix
- #laplacian_matrix
- #moore_dijkstra
- #range
- #symmetric?

### Files

- AUTHORS
- COPYING
- README.rdoc

### Class/Module Index

Quicksearch

- GraphViz
- GraphViz::Attrs
- GraphViz::Edge
- GraphViz::Elements
- GraphViz::Ext
- GraphViz::FamilyTree
- GraphViz::FamilyTree::Couple
- GraphViz::FamilyTree::Generation
- GraphViz::FamilyTree::Person
- GraphViz::FamilyTree::Sibling
- GraphViz::GraphML
- GraphViz::Math
- GraphViz::Math::CoordinateError
- GraphViz::Math::Matrix
- GraphViz::Math::ValueError
- GraphViz::Node
- GraphViz::Theory
- GraphViz::Types
- GraphViz::Types::Common
- GraphViz::Types::EscString
- GraphViz::Types::GvDouble
- GraphViz::Types::HtmlString
- GraphViz::Types::LblString
- GraphViz::XML
- Constants
- GVUtils
- Hash
- Object
- String

No matching classes.

# GraphViz::Theory

### Public Class Methods

new( graph ) click to toggle source

    # File lib/graphviz/theory.rb, line 5
    def initialize( graph )
      @graph = graph
    end

### Public Instance Methods

adjancy_matrix() click to toggle source

Return the adjancy matrix of the graph

    # File lib/graphviz/theory.rb, line 12
    def adjancy_matrix
      matrix = GraphViz::Math::Matrix.new( @graph.node_count, @graph.node_count )

      @graph.each_edge { |e|
        x = @graph.get_node(e.node_one( false )).index
        y = @graph.get_node(e.node_two( false )).index
        matrix[x+1, y+1] = 1
        matrix[y+1, x+1] = 1 if @graph.type == "graph"
      }

      return matrix
    end

critical_path() click to toggle source

Return the critical path for a PERT network

If the given graph is not a PERT network, return nul

    # File lib/graphviz/theory.rb, line 165
    def critical_path
      return nil if range.include?(nil) or @graph.type != "digraph"
      r = [ [0, [1]] ]

      critical_path_recursion( distance_matrix, adjancy_matrix, r, [], 0 ).inject( {:distance => 0, :path => []} ) { |r, item|
        (r[:distance] < item[0]) ? { :distance => item[0], :path => item[1] } : r
      }
    end

degree( node ) click to toggle source

Return the degree of the given node

    # File lib/graphviz/theory.rb, line 49
    def degree( node )
      degree = 0
      name = node
      if node.kind_of?(GraphViz::Node)
        name = node.id
      end

      @graph.each_edge do |e|
        degree += 1 if e.node_one(false) == name or e.node_two(false) == name
      end

      return degree
    end

incidence_matrix() click to toggle source

Return the incidence matrix of the graph

    # File lib/graphviz/theory.rb, line 28
    def incidence_matrix
      tail = (@graph.type == "digraph") ? -1 : 1
      matrix = GraphViz::Math::Matrix.new( @graph.node_count, @graph.edge_count )

      @graph.each_edge { |e|
        x = e.index

        nstart = @graph.get_node(e.node_one( false )).index
        nend = @graph.get_node(e.node_two( false )).index

        matrix[nstart+1, x+1] = 1
        matrix[nend+1, x+1] = tail
        matrix[nend+1, x+1] = 2 if nstart == nend
      }

      return matrix
    end

laplacian_matrix() click to toggle source

Return the laplacian matrix of the graph

    # File lib/graphviz/theory.rb, line 66
    def laplacian_matrix
      return degree_matrix - adjancy_matrix
    end

moore_dijkstra( dep, arv ) click to toggle source

moore_dijkstra(source, destination)

    # File lib/graphviz/theory.rb, line 80
    def moore_dijkstra( dep, arv )
      dep = @graph.get_node(dep) unless dep.kind_of?(GraphViz::Node)
      arv = @graph.get_node(arv) unless arv.kind_of?(GraphViz::Node)

      m = distance_matrix
      n = @graph.node_count
      # Table des sommets à choisir
      c = [dep.index]
      # Table des distances
      d = []
      d[dep.index] = 0

      # Table des predecesseurs
      pred = []

      @graph.each_node do |name, k|
        if k != dep
          d[k.index] = m[dep.index+1,k.index+1]
          pred[k.index] = dep
        end
      end

      while c.size < n
        # trouver y tel que d[y] = min{d[k];  k sommet tel que k n'appartient pas à c}
        mini = 1.0/0.0
        y = nil
        @graph.each_node do |name, k|
          next if c.include?(k.index)
          if d[k.index] < mini
            mini = d[k.index]
            y = k
          end
        end

        # si ce minimum est ∞ alors sortir de la boucle fin si
        break unless mini.to_f.infinite?.nil?

        c << y.index
        @graph.each_node do |name, k|
          next if c.include?(k.index)
          if d[k.index] > d[y.index] + m[y.index+1,k.index+1]
            d[k.index] = d[y.index] + m[y.index+1,k.index+1]
            pred[k.index] = y
          end
        end
      end

      # Construction du chemin le plus court
      ch = []
      k = arv
      while k.index != dep.index
        ch.unshift(k.id)
        k = pred[k.index]
      end
      ch.unshift(dep.id)

      if d[arv.index].to_f.infinite?
        return nil
      else
        return( {
          :path => ch,
          :distance => d[arv.index]
        } )
      end
    end

range() click to toggle source

Return a liste of range

If the returned array include nil values, there is one or more circuits in the graph

    # File lib/graphviz/theory.rb, line 151
    def range
      matrix = adjancy_matrix
      unseen = (1..matrix.columns).to_a
      result = Array.new(matrix.columns)
      r = 0

      range_recursion( matrix, unseen, result, r )
    end

symmetric?() click to toggle source

Return `true` if the graph if symmetric, `false` otherwise

    # File lib/graphviz/theory.rb, line 73
    def symmetric?
      adjancy_matrix == adjancy_matrix.transpose
    end

[Validate]

Generated with the Darkfish Rdoc Generator 2.