Python Forum
Implement distancematrix to Held karp algorithm
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Implement distancematrix to Held karp algorithm
#1
Hi, this is my first post.
I am an PHP developer that just started learning Python. I installed a Go-package and got a code from the internet. Can someone help me get this code rundning? I need to get a 2d matrix with distances in a .csv file and then send the argument to open the file.

package main

import (
        "bytes"
        "encoding/csv"
        "fmt"
        "io"
        "log"
        "math/bits"
        "math/rand"
        "os"
        "runtime"
        "strconv"
        "strings"
        "time"
)

const MaxInt = int(^uint(0) >> 1)

// IntSet

type IntSet struct {
        Storage uint
}

func (vs IntSet) Contains(value int) bool {
        return (vs.Storage & (1 << uint(value))) != 0
}

func (vs IntSet) Count() int {
        return bits.OnesCount(vs.Storage)
}

func (vs *IntSet) Insert(value int) {
        vs.Storage |= 1 << uint(value)
}

func (vs *IntSet) Remove(value int) {
        vs.Storage &= ^(1 << uint(value))
}

func (vs IntSet) Value() int {
        return int(vs.Storage >> 1)
}

func (vs IntSet) Iter() []int {
        n := vs.Count()
        v := make([]int, n)
        for c, i := 0, 0; c < n; i++ {
                if vs.Contains(i) {
                        v[c] = i
                        c++
                }
        }
        return v
}

func (vs IntSet) String() string {
        buf := bytes.Buffer{}
        buf.WriteString("{")
        delim := ""
        for c, i := 0, 0; c < vs.Count(); i++ {
                if vs.Contains(i) {
                        buf.WriteString(fmt.Sprintf("%s%v", delim, i))
                        delim = ","
                        c++
                }
        }
        buf.WriteString("}")
        return buf.String()
}

// Combinations 'k' integers from a serie '1..n'

type Combs []IntSet

func combWithLen(n, k, first int, vs IntSet, acc Combs) Combs {
        if k > vs.Count() {
                for x := first; x <= n; x++ {
                        s := vs
                        s.Insert(x)
                        acc = combWithLen(n, k, x + 1, s, acc)
                }
        } else {
                acc = append(acc, vs)
        }
        return acc
}

func Comb(n, k int) Combs {
        return combWithLen(n, k, 1, IntSet{}, Combs{})
}

// Held Karp

type Path struct {
        Cost int
        From int
}

func minPath(paths []Path) Path {
        m := paths[0]
        for i := 1; i < len(paths); i++ {
                if m.Cost > paths[i].Cost {
                        m = paths[i]
                }
        }
        return m
}

func pathFromTo(from, to int, c [][]Path, dists CostMatrix, prev IntSet) Path {
        p := Path{}
        p.Cost = c[prev.Value()][from-1].Cost + dists[from][to]
        p.From = from
        return p
}

func reverse(a []int) []int {
        for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 {
                a[i], a[j] = a[j], a[i]
        }
        return a
}

// CostMatrix

type CostMatrix [][]int

func (dists CostMatrix) CalcCostToSubsets(c [][]Path, edges, subsetSz int) {
        maxWorkers := runtime.NumCPU()
        workers := 0
        done := make(chan bool)
        for _, visited := range(Comb(edges, subsetSz))  {
                if workers == maxWorkers {
                        <-done
                } else {
                        workers += 1
                }
                go func(vs IntSet) {
                        subset := vs.Iter()
                        // Find the lowest cost to get to this subset
                        for _, k := range subset {
                                prev := vs
                                prev.Remove(k)
                                res := []Path{}
                                for _, m := range subset {
                                        if m != k {
                                                res = append(res, pathFromTo(m, k, c, dists, prev))
                                        }
                                }
                                if len(res) > 0 {
                                        c[vs.Value()][k-1] = minPath(res)
                                }
                        }
                        done<- true
                }(visited)
        }
        // Wait for all workers to finish
        for ;workers > 0; workers -= 1 {
                <-done
        }
}

func (dists CostMatrix) ShortestPath() (int, []int) {
        n := len(dists)
        c := make([][]Path, 1<<uint(n-1))
        for i := 0; i < len(c); i++ {
                c[i] = make([]Path, n-1)
        }
        // Add paths from start to first steps
        for k := 1; k < n; k++ {
                c[1<<uint(k-1)][k-1] = Path{dists[0][k], 0}
        }
        for s := 2; s < n; s++ {
                dists.CalcCostToSubsets(c, n - 1, s)
        }
        visited := IntSet{}
        for k := 1; k < n; k++ {
                visited.Insert(k)
        }
        // Add path back to start and calculate optimal cost
        res := []Path{}
        for k := 1; k < n; k++ {
                res = append(res, pathFromTo(k, 0, c, dists, visited))
        }
        p := minPath(res)
        cost := p.Cost
        // Backtrack to find path
        steps := make([]int, n+1)
        for i := 1; i < n; i++ {
                steps[i] = p.From
                from := p.From
                p = c[visited.Value()][p.From-1]
                visited.Remove(from)
        }
        return cost, reverse(steps)
}

func (c CostMatrix) MaxDigitWidth() (width int) {
        for row := 0; row < len(c); row++ {
                for col := 0; col < len(c[row]); col++ {
                        w := 0
                        for d := c[row][col]; d > 0; d /= 10 {
                                w += 1
                        }
                        if width < w {
                                width = w
                        }
                }
        }
        return
}

func (c CostMatrix) String() string {
        fmtstr := fmt.Sprintf("%%%vv", c.MaxDigitWidth())
        buf := bytes.Buffer{}
        for row := 0; row < len(c); row++ {
                if row == 0 {
                        buf.WriteString("{\n")
                }
                buf.WriteString("    { ")
                for col := 0; col < len(c[row]); col++ {
                        buf.WriteString(fmt.Sprintf(fmtstr, c[row][col]))
                        if col != len(c[row])-1 {
                                buf.WriteString(", ")
                        }
                }
                buf.WriteString(" },\n")
                if row == len(c)-1 {
                        buf.WriteString("}")
                } else {
                }
        }
        return buf.String()
}

func Abs(n int) int {
        if n < 0 {
                return -n
        }
        return n
}

func Max(a, b int) int {
        if a < b {
                return b
        }
        return a
}

type Location struct {
        shelf int
        level int
}

func cost(from, to Location) int {
        dx := Abs(from.shelf - to.shelf)
        dy := Abs(from.level - to.level) * 2
        return Max(dx, dy)
}

func zeroMatrix(dim int) CostMatrix {
        var c CostMatrix = make([][]int, dim)
        for i := range c {
                c[i] = make([]int, dim)
        }
        return c
}

func genMatrix(nodes, depth, height int) CostMatrix {
        rand.Seed(time.Now().UnixNano())
        c := zeroMatrix(nodes)
        l := make([]Location, nodes)
        for i := range l {
                l[i] = Location{rand.Intn(depth), rand.Intn(height)}
        }
        for row := 0; row < nodes; row++ {
                for col := row + 1; col < nodes; col++ {
                        c[row][col] = cost(l[row], l[col])
                        c[col][row] = c[row][col]
                }
        }
        return c
}

func readMatrix(r io.Reader) CostMatrix {
	cr := csv.NewReader(r)
        rec, err := cr.ReadAll()
        if err != nil {
                log.Fatalln(err)
        }
        M := zeroMatrix(len(rec))
        for row, line := range rec {
                for col, str := range line {
                        v, err := strconv.ParseInt(strings.TrimSpace(str), 10, 32)
                        if err != nil {
                                log.Fatalln(err)
                        }
                        M[row][col] = int(v)
                }
        }

        return M
}

func GetCostMatrix() CostMatrix {
        if len(os.Args) == 1 {
                return readMatrix(os.Stdin)
        }
	arg := os.Args[1]
        if strings.HasSuffix(arg, ".csv") {
                file, err := os.Open(arg)
                if err != nil {
                        log.Fatalln(err)
                }
                return readMatrix(file)
	}
        dim, err := strconv.ParseInt(arg, 10, 32)
        if err != nil {
                log.Fatalln(err)
        }
        return genMatrix(int(dim), 50, 9)
}

// Program entrypoint

func main() {
        c := GetCostMatrix()
	fmt.Println(c)
        fmt.Println(c.ShortestPath())
}
Reply
#2
well this is looks like Go, not Python.
If you can't explain it to a six year old, you don't understand it yourself, Albert Einstein
How to Ask Questions The Smart Way: link and another link
Create MCV example
Debug small programs

Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Right way to implement interfaces yossiy123 1 1,241 May-12-2022, 10:31 AM
Last Post: Gribouillis
Question best way to implement algorithm hamidze 3 2,172 Feb-27-2021, 07:10 PM
Last Post: hamidze

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020