# 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_reader :coords, :dist
  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))
      else
        raise "File not found!"
      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
    @coords=Array.new(@n, nil)
    @dist = []
    @adj = Array.new(@n){Array.new(@n, false)}
    @neighbors=Array.new(@n){[]}
    @nodemarks = Array.new(@n,"")
    @edgemarks = []
  end

  def add(u,v, d=nil)
    @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("")
    @dist.push(d)
  end

  def to_s
    res = "#{@n}\n"
    @edges.each.with_index{|e,eid|
      res+="e "+e.join(" ")+"#{@dist[eid] ? " "+@dist[eid].to_s : ""}\n"
    }
    return res
  end

  def to_dot
    dot = "graph {\n"
    dot += @nodes.map.with_index{|n,i|
      c = ""
      if @coords[i]
        c=" pos=\""+@coords[i].map{|x| (x.to_f*1.3).to_s}.join(",")+'!"'
      end
      "#{n} [#{nodemarks[i]}#{c}]\n"
    }.join("")    
    dot += @edges.map.with_index{|e,i|
      d = nil
      if @dist[i]
        d = "label=\"#{@dist[i]}\" "
      end
      "#{@nodes[e[0]]} -- #{@nodes[e[1]]} [#{d}#{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 -Kneato -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]=="c"}.each{|l|
      l = l.split(/\s+/)
      @coords[l[1].to_i] = l[2..3].map{|x| x.to_f}
      @coords[l[1].to_i][1]*=-1
    }
    lines.select{|l| l[0]=="e"}.each{|l|
      l = l.split(/\s+/)
      vs = l[1..2].map{|e| e.to_i}
      d = nil
      if l.size>3
        d = l[3].to_f
      end
      add(vs[0], vs[1], d)
    }
  end

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

  def mark_edges(path)
    (path.size-1).times{|i|
      mark_edge(path[i],path[i+1])
    }
  end
  
  # partial: Unvollständige Weg
  def hamilton(partial=nil, visited=nil)
      # Initialisierung, erster Aufruf
      if (partial==nil)
         partial=[0]
         visited = Array.new(@n, false)
         visited[0] = true
         @counter=0
      end
      @counter+=1
      # Rekursionsabbruch
      if (partial.size==@n)
         if @adj[partial[0]][partial[-1]]  # Kann Weg geschlossen werden
             puts "Calls: #{@counter}"
             return partial+[partial[0]]  # Zyklus schliessen
         end
         return nil  # Sorry, kein Zyklus             
      end
      # Rekursion
      @neighbors[partial[-1]].each{|nbr| # nbr = [knoten, kante]
        unless visited[nbr[0]]
            visited[nbr[0]] = true
            weg = hamilton(partial+[nbr[0]], visited)
            if weg!=nil
                return weg
            end
            visited[nbr[0]] = false
        end
      }
      return nil
  end

  def dijkstra(start)
    
  end
    
end  # Schliesst class Graph



#g = Graph.new("knacknuss.txt")
# g = Graph.new([40,80,42])
g = Graph.new("shortest.txt")
g.to_png("shortest")
g.dijkstra(0)
g.to_png("shortest-sol")

exit

path = g.hamilton()
p path
if path!=nil
    g.mark_edges(path)
    g.to_png("shortest-hamilton")
end