# coding: utf-8


# Für die Grafik-Ausgabe ist das graphviz Paket nötig
# sudo apt-get install graphviz


# n: Fixnum, Anzahl Knoten
# edges: Array aus Arrays mit 2 Einträgen: Fixnum, Knotenid 0..(n-1)
# neighbors: Array aus Arrays aus Arrays:
#   d(v) Einträge pro Knoten
#   Eintrag [u,eid], u Nachbarsknoten ID, Kanten ID (0..(m-1))
# adj[u][v]: false, wenn u,v nicht Nachbarn, sonst edge ID
#
# nodemarks, edgemarks: String, formatierung für Grafik
#    siehe http://www.graphviz.org/content/attrs
#
class Graph
  attr_reader :n, :edges, :neighbors, :adj
  attr_accessor :nodemarks
  attr_accessor :edgemarks
  #
  # Parameter ist einer von:
  #  - Zahl: Leerer Graph mit n Knote
  #  - String: Dateiname mit Graph
  #  - Array: [n, Float oder Fixnum, Fixnum]. Generiert Zufallsgraph mit Dichte Float oder Fixnum Kanten.
  #           Der dritte Eintrag ist optional und enthält den RandomSeed
  #
  def initialize(n)
    if n.is_a?(Numeric)
      @n=n.to_i
      allocate
    elsif n.is_a?(String)
      if File.exist?(n)
        parse(File.read(n))
      end
    elsif n.is_a?(Array)
      @n=n[0]
      allocate
      m = n[1]
      if (m.is_a?(Float))
        m = (@n*(@n-1)/2*m+0.5).to_i
      end
      if n.size>2
        srand(n[2])
      end
      # Ineffizient für hohe Dichten! (effiziente Mogellösung: Komplement)
      m.times{
        while true
          u = rand(@n)
          v = rand(@n-1)
          v+=1 if (v>=u)
          unless @adj[u][v]
            add(u,v)
            break
          end
        end
      }
    end
  end

  def allocate
    @edges=[]
    @nodes=(0...@n).to_a
    @adj = Array.new(@n){Array.new(@n, false)}
    @neighbors=Array.new(@n){[]}
    @nodemarks = Array.new(@n,"")
    @edgemarks = []
  end

  def add(u,v)
    @edges.push([u,v])
    eid = @edges.size-1
    @neighbors[u].push([v,eid])
    @neighbors[v].push([u,eid])
    @adj[u][v]=eid
    @adj[v][u]=eid
    @edgemarks.push("")
  end

  def to_s
    res = "#{@n}\n"
    @edges.each{|e|
      res+="e "+e.join(" ")+"\n"
    }
    return res
  end

  def to_dot
    dot = "graph {\n"
    dot += @nodes.map.with_index{|n,i| "#{n} [#{nodemarks[i]}]\n"}.join("")
    dot += @edges.map.with_index{|e,i| "#{@nodes[e[0]]} -- #{@nodes[e[1]]} [#{edgemarks[i]}]\n"}.join("")
    dot += "}"
    return dot
  end

  def to_png(file="output")
    if (file =~ /\.png$/i)
      file = file[0..(-5)]
    end
    File.write(file+".dot",self.to_dot)
    cmd = "dot -Tpng -o'#{file}.png' '#{file}.dot'"
    puts cmd
    `#{cmd}`
  end

  def parse(contents)
    lines = contents.split("\n").map(&:strip).select{|l| l.size>0 && l[0]!="#"}
    @n = lines[0].to_i
    allocate
    lines.select{|l| l[0]=="e"}.each{|l|
      vs = l.split(/\s+/)[1..2].map{|e| e.to_i}
      add(vs[0], vs[1])
    }
  end

  def mark_edge(u,v)
    neighbors[u].each{|e|
      if (e[0]==v)
        edgemarks[e[1]]="color=\"red\""
        break
      end
    }
  end

  def mark_edges(path)
    (path.size-1).times{|i|
      mark_edge(path[i],path[i+1])
    }
  end
end



g = Graph.new("knacknuss.txt")
g.to_png("knacknuss")