# Some graph examples

require 'rgl/adjacency'
require 'rgl/implicit'

# partite 8, 5
def partite(n, m)
  result = RGL::DirectedAdjacencyGraph.new
  1.upto(n) { |i|
    1.upto(m) { |j|
      result.add_edge('a' + i.to_s, 'b' + j.to_s)
    }
  }
  result
end

# modulo(30, 5).dotty
def modulo (n, m)
  result = RGL::AdjacencyGraph.new
  1.upto(n) { |x|
    1.upto(n) { |y|
      result.add_edge x, y if x != y && x % m == y % m }
  }
  result
end

# Cyclic graph with _n_ vertices
def cycle (n)
  RGL::ImplicitGraph.new { |g|
    g.vertex_iterator { |b| 0.upto(n - 1, &b) }
    g.adjacent_iterator { |x, b| b.call((x + 1) % n) }
    g.directed = true
  }
end

# Complete Graph with _n_ vertices
def complete (n)
  set = n.integer? ? (1..n) : n
  RGL::ImplicitGraph.new { |g|
    g.vertex_iterator { |b| set.each(&b) }
    g.adjacent_iterator { |x, b|
      set.each { |y| b.call(y) unless x == y }
    }
  }
end

# Directed graph of ruby modules. Edges are defined by the method _ancestors_
def module_graph
  RGL::ImplicitGraph.new { |g|
    g.vertex_iterator { |b|
      ObjectSpace.each_object(Module, &b)
    }
    g.adjacent_iterator { |x, b|
      x.ancestors.each { |y|
        b.call(y) unless x == y || y == Kernel || y == Object
      }
    }
    g.directed = true
  }
end

# Shows graph of divisors of all integers from 2 to _n_.
def divisors(n)
  RGL::ImplicitGraph.new { |g|
    g.vertex_iterator { |b| 2.upto(n, &b) }
    g.adjacent_iterator { |x, b|
      n.downto(x + 1) { |y| b.call(y) if y % x == 0 }
    }
    g.directed = true
  }
end

def bfs_example(g = cycle(5), start = g.detect { |x| true })
  require 'rgl/traversal'

  g.bfs_search_tree_from(start)
end

# Would like to have GraphXML here
def graph_from_dotfile(file)
  g = RGL::AdjacencyGraph.new
  pattern = /\s*([^\"]+)[\"\s]*--[\"\s]*([^\"\[\;]+)/ # ugly but works
  IO.foreach(file) { |line|
    case line
      when /^digraph/
        g = RGL::DirectedAdjacencyGraph.new
        pattern = /\s*([^\"]+)[\"\s]*->[\"\s]*([^\"\[\;]+)/
      when pattern
        g.add_edge $1, $2
      else
        nil
    end
  }
  g
end

# ruby -Ilib examples/examples.rb
if $0 == __FILE__
  require 'rgl/dot'

  dg = RGL::DirectedAdjacencyGraph[1,2, 2,3, 2,4, 4,5, 6,4, 1,6]
  dg.write_to_graphic_file

  # BFS tree from 1 of dg:
  bfs_example(dg, 1).write_to_graphic_file('png', 'bfs_example')

  # Unix history as a graph:
  g = bfs_example(graph_from_dotfile('examples/unix.dot'), 'Interdata')
  g.write_to_graphic_file('png', 'unix', { 'label' => 'Interdata Nachfolger', 'fontsize' => 12 })

  # Modules included by AdjacencyGraph:
  g = module_graph
  tree = bfs_example(module_graph, RGL::AdjacencyGraph)
  g = g.vertices_filtered_by { |v| tree.has_vertex? v }
  g.write_to_graphic_file('png', 'module_graph')
end