package main
// export PATH=/users/j0sh/local/go/bin:$PATH

import (
  "os"
  "bufio"
  "fmt"
  // "math"
  "math/rand"
  "sort"
)

type edge struct {
  source, dest int
}

func main() {
  nodes := 0

  println("allocate")
  edge_set := make(map[edge]bool)

  infline, err := os.Open("com-orkut.ungraph.txt")
  if err != nil { panic(err) }
  defer infline.Close()

  outfile, err := os.Create("orkut-relabeled.edgelist")
  if err != nil { panic(err) }
  defer outfile.Close()

  scanner := bufio.NewScanner(infline)
  scanner.Split(bufio.ScanLines)

  println("read graph")
  for scanner.Scan() {
    line := scanner.Text()
    if line[0] == '#' {
      continue
    }
    var a,b int
    n, err := fmt.Sscanf(line, "%d\t%d\n", &a, &b)
    if n != 2 {
      println("failed to scan")
      println(line)
    }
    if err != nil {
      panic(err)
    }

    if a > b {
      a,b = b,a
    }
    if b > nodes {
      nodes = b
    }
    if a > nodes {
      nodes = a
    }

    edge_set[edge{a,b}] = true

  }
  nodes += 1

  // node_degrees := make([]int, nodes)
  // for edge, _ := range edge_set {
  //   node_degrees[edge.source]++;
  //   node_degrees[edge.dest]++;
  // }
  // sorted_slice := NewSlice(node_degrees...)


  println("permute")
  new_node_descriptors := rand.Perm(nodes)

  edges := len(edge_set)
  fmt.Fprintln(outfile, nodes, edges)
  for edge, _ := range edge_set {
    fmt.Fprintln(outfile,
      new_node_descriptors[edge.source],
      new_node_descriptors[edge.dest],
      // sorted_slice.idx[edge.source],
      // sorted_slice.idx[edge.dest],
    )
  }

}

type Slice struct {
  sort.IntSlice
  idx []int
}

func (s Slice) Swap(i, j int) {
  s.IntSlice.Swap(i, j)
  s.idx[i], s.idx[j] = s.idx[j], s.idx[i]
}

func NewSlice(n ...int) *Slice {
  s := &Slice{IntSlice: sort.IntSlice(n), idx: make([]int, len(n))}
  for i := range s.idx {
    s.idx[i] = i
  }
  return s
}