Skip to content

Commit

Permalink
add edge weighted digraph
Browse files Browse the repository at this point in the history
shellfly committed Feb 5, 2020
1 parent 5bc0538 commit ede14b1
Showing 4 changed files with 169 additions and 0 deletions.
2 changes: 2 additions & 0 deletions README.md
Original file line number Diff line number Diff line change
@@ -72,6 +72,8 @@ To test each algorithm(data structure), instead of running the file directly, yo
* [LazyPrimMST](lazy_prim_mst.go)
* [PrimMST](prim_mst.go)
* [KruskalMST](kruskal_mst.go)
* Shortest Paths
* [EdgeWeightedDigraph](edge_weighted_digraph.go)

* 5 STRING

36 changes: 36 additions & 0 deletions cmd/edge-weighted-digraph/main.go
Original file line number Diff line number Diff line change
@@ -0,0 +1,36 @@
/******************************************************************************
* Execution: go run cmd/edge-weighted-graph/main.go filename.txt
* Data files: https://algs4.cs.princeton.edu/43mst/tinyEWG.txt
* https://algs4.cs.princeton.edu/43mst/mediumEWG.txt
* https://algs4.cs.princeton.edu/43mst/largeEWG.txt
*
* An edge-weighted undirected graph, implemented using adjacency lists.
* Parallel edges and self-loops are permitted.
*
* % go run cmd/edge-weighted-graph/main.go tinyEWG.txt
* 8 16
* 0: 6-0 0.58000 0-2 0.26000 0-4 0.38000 0-7 0.16000
* 1: 1-3 0.29000 1-2 0.36000 1-7 0.19000 1-5 0.32000
* 2: 6-2 0.40000 2-7 0.34000 1-2 0.36000 0-2 0.26000 2-3 0.17000
* 3: 3-6 0.52000 1-3 0.29000 2-3 0.17000
* 4: 6-4 0.93000 0-4 0.38000 4-7 0.37000 4-5 0.35000
* 5: 1-5 0.32000 5-7 0.28000 4-5 0.35000
* 6: 6-4 0.93000 6-0 0.58000 3-6 0.52000 6-2 0.40000
* 7: 2-7 0.34000 1-7 0.19000 0-7 0.16000 5-7 0.28000 4-7 0.37000
*
******************************************************************************/

package main

import (
"fmt"
"os"

"github.com/shellfly/algo"
"github.com/shellfly/algo/stdin"
)

func main() {
graph := algo.NewEdgeWeightedGraph(stdin.NewIn(os.Args[1]))
fmt.Println(graph)
}
46 changes: 46 additions & 0 deletions directed_edge.go
Original file line number Diff line number Diff line change
@@ -0,0 +1,46 @@
package algo

import "fmt"

// DirectedEdge is a ADT for DirectedEdgeWeightedGraph
type DirectedEdge struct {
v, w int
weight float32
}

// NewDirectedEdge ...
func NewDirectedEdge(v, w int, weight float32) *DirectedEdge {
return &DirectedEdge{v, w, weight}
}

// Weight ...
func (e *DirectedEdge) Weight() float32 {
return e.weight
}

// From ...
func (e *DirectedEdge) From() int {
return e.v
}

// To ...
func (e *DirectedEdge) To() int {
return e.w
}

// String ...
func (e *DirectedEdge) String() string {
return fmt.Sprintf("%d-%d %.5f", e.v, e.w, e.weight)
}

// CompareTo implements PQItem interface
func (e *DirectedEdge) CompareTo(other interface{}) int {
ee := other.(*DirectedEdge)
if e.weight > ee.weight {
return 1
} else if e.weight < ee.weight {
return -1
} else {
return 0
}
}
85 changes: 85 additions & 0 deletions edge_weighted_digraph.go
Original file line number Diff line number Diff line change
@@ -0,0 +1,85 @@
package algo

import (
"fmt"

"github.com/shellfly/algo/stdin"
)

// EdgeWeightedDigraph ...
type EdgeWeightedDigraph struct {
v, e int
adj []*Bag
}

// NewEdgeWeightedDigraph ...
func NewEdgeWeightedDigraph(in *stdin.In) *EdgeWeightedDigraph {
v := in.ReadInt()
adj := make([]*Bag, v)
for i := 0; i < v; i++ {
adj[i] = NewBag()
}
g := &EdgeWeightedDigraph{v: v, e: 0, adj: adj}
e := in.ReadInt()
for i := 0; i < e; i++ {
v, w, weight := in.ReadInt(), in.ReadInt(), in.ReadFloat32()
g.AddEdge(NewDirectedEdge(v, w, weight))
}
return g
}

// NewEdgeWeightedDigraphV ...
func NewEdgeWeightedDigraphV(v int) *EdgeWeightedDigraph {
adj := make([]*Bag, v)
for i := 0; i < v; i++ {
adj[i] = NewBag()
}
return &EdgeWeightedDigraph{v: v, e: 0, adj: adj}
}

// V ...
func (g *EdgeWeightedDigraph) V() int {
return g.v
}

// E ...
func (g *EdgeWeightedDigraph) E() int {
return g.e
}

// AddEdge ...
func (g *EdgeWeightedDigraph) AddEdge(e *DirectedEdge) {
g.adj[e.From()].Add(e.To())
g.e++
}

// Adj ...
func (g *EdgeWeightedDigraph) Adj(v int) []*DirectedEdge {
var items []*DirectedEdge
for _, item := range g.adj[v].Slice() {
items = append(items, item.(*DirectedEdge))
}
return items
}

// Edges ...
func (g *EdgeWeightedDigraph) Edges() (edges []*DirectedEdge) {
for v := 0; v < g.v; v++ {
for _, e := range g.Adj(v) {
edges = append(edges, e)
}
}
return
}

func (g *EdgeWeightedDigraph) String() string {
s := fmt.Sprintf("%d vertices, %d edges\n", g.v, g.e)
for i := 0; i < g.v; i++ {
var adjs string
for _, e := range g.Adj(i) {
adjs = fmt.Sprintf("%s %s ", adjs, e)
}
s += fmt.Sprintf("%d: %s\n", i, adjs)
}
return s
}

0 comments on commit ede14b1

Please sign in to comment.