Skip to content

Tip #2

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
korthaj merged 7 commits into from
May 10, 2017
Merged

Tip #2

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
7 commits
Select commit Hold shift + click to select a range
91a2aba
Remove duplicate declaration of edge
korthaj Apr 30, 2017
5f05f60
Cleanup
korthaj Apr 30, 2017
b9ba693
Cleanup
korthaj Apr 30, 2017
d167321
Add installation instructions
korthaj May 1, 2017
8834c93
Remove -u
korthaj May 2, 2017
ff853e7
Update README
korthaj May 8, 2017
65f457e
Minor refactoring
korthaj May 10, 2017
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
16 changes: 15 additions & 1 deletion README.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -41,12 +41,24 @@ they are instead computed as needed. New virtual graphs are constructed
by composing and filtering a set of standard graphs, or by writing
functions that describe the edges of a graph.

### Installation

Once you have [installed Go][golang-install], run this command
to install the `graph` package:

go get github.com/yourbasic/graph

### Documentation

There is an online reference for the package at
[godoc.org/github.com/yourbasic/graph][godoc-graph].

### Roadmap

* The API of this library is frozen.
* Bug fixes and performance enhancement can be expected.
* New functionality might be included.
* The version numbers adhere to [semantic versioning][sv].
* Version numbers adhere to [semantic versioning][sv].

The only accepted reason to modify the API of this package is to
handle bug fixes that can't be resolved in any other reasonable way.
Expand All @@ -57,6 +69,8 @@ in a computer science textbook.

Stefan Nilsson – [korthaj](https://github.com/korthaj)

[godoc-graph]: https://godoc.org/github.com/yourbasic/graph
[golang-install]: http://golang.org/doc/install.html
[cc010]: https://creativecommons.org/publicdomain/zero/1.0/deed.en
[de]: https://commons.wikimedia.org/wiki/User:David_Eppstein
[sv]: http://semver.org/
Expand Down
7 changes: 3 additions & 4 deletions bfs_test.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -6,7 +6,7 @@ import (
)

func TestBFS(t *testing.T) {
gm := New(10)
g := New(10)
for _, e := range []struct {
v, w int
}{
Expand All @@ -15,12 +15,11 @@ func TestBFS(t *testing.T) {
{2, 3}, {5, 6},
{3, 6}, {8, 9}, {4, 4},
} {
gm.AddBoth(e.v, e.w)
g.AddBoth(e.v, e.w)
}
g := Sort(gm)
exp := "0147925836"
res := "0"
BFS(g, 0, func(v, w int, c int64) {
BFS(Sort(g), 0, func(v, w int, c int64) {
res += strconv.Itoa(w)
})
if mess, diff := diff(res, exp); diff {
Expand Down
18 changes: 8 additions & 10 deletions build/build.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -78,21 +78,19 @@ type CostFunc func(v, w int) int64

// Cost returns a CostFunc which always returns n.
func Cost(n int64) CostFunc {
return func(_, _ int) int64 { return n }
return func(int, int) int64 { return n }
}

func neverEdge(_, _ int) bool { return false }
func neverEdge(int, int) bool { return false }
func alwaysEdge(v, w int) bool { return v != w }

func zero(_, _ int) int64 { return 0 }
func zero(int, int) int64 { return 0 }

func degreeZero(_ int) int { return 0 }
func degreeOne(_ int) int { return 1 }
func degreeZero(int) int { return 0 }
func degreeOne(int) int { return 1 }

func noNeighbors(_ int, _ int, _ func(w int, c int64) bool) bool { return false }
func noNeighbors(int, int, func(w int, c int64) bool) bool { return false }

const maxint = int(^uint(0) >> 1)
const minint = -maxint - 1
const bitsPerWord = 32 << uint(^uint(0)>>63)

func min(m, n int) int {
Expand Down Expand Up @@ -196,7 +194,7 @@ func generic(n int, cost CostFunc, edge func(v, w int) bool) *Virtual {
cost: cost,
}
g.degree = func(v int) (deg int) {
g.visit(v, 0, func(_ int, _ int64) (skip bool) {
g.visit(v, 0, func(int, int64) (skip bool) {
deg++
return
})
Expand Down Expand Up @@ -229,7 +227,7 @@ func generic0(n int, edge func(v, w int) bool) *Virtual {
cost: zero,
}
g.degree = func(v int) (deg int) {
g.visit(v, 0, func(_ int, _ int64) (skip bool) {
g.visit(v, 0, func(int, int64) (skip bool) {
deg++
return
})
Expand Down
18 changes: 10 additions & 8 deletions build/connect.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -25,8 +25,9 @@ func (g1 *Virtual) Connect(v1 int, g2 *Virtual) *Virtual {
return g2.cost(0, w-t)
case w == v1:
return g2.cost(v-t, 0)
default:
return 0
}
return 0
}

res := generic(n, newCost, func(v, w int) bool {
Expand All @@ -39,8 +40,9 @@ func (g1 *Virtual) Connect(v1 int, g2 *Virtual) *Virtual {
return g2.edge(0, w-t)
case w == v1:
return g2.edge(v-t, 0)
default:
return false
}
return false
})

res.degree = func(v int) (deg int) {
Expand All @@ -55,23 +57,23 @@ func (g1 *Virtual) Connect(v1 int, g2 *Virtual) *Virtual {
}

res.visit = func(v int, a int, do func(w int, c int64) bool) (aborted bool) {
if v > t {
switch {
case v > t:
return g2.visit(v-t, max(0, a-t), func(w int, c int64) (skip bool) {
if w == 0 {
return v1 >= a && do(v1, c)
}
return do(w+t, c)
})
}
if g1.visit(v, a, do) {
case g1.visit(v, a, do):
return true
}
if v == v1 {
case v == v1:
return g2.visit(0, max(0, a-t), func(w int, c int64) (skip bool) {
return do(w+t, c)
})
default:
return
}
return
}
return res
}
30 changes: 16 additions & 14 deletions build/edgeset.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -73,6 +73,7 @@ func newEdges(n int, e EdgeSet) *Virtual {
case n == 1:
return singleton()
}

var noCost bool
if e.Cost == nil {
noCost = true
Expand All @@ -83,12 +84,12 @@ func newEdges(n int, e EdgeSet) *Virtual {
noFilter = true
e.Keep = alwaysEdge
}

from := e.From.And(Range(0, n))
to := e.To.And(Range(0, n))
if from.size() == 0 || to.size() == 0 {
return Empty(n)
}

res := generic(n, e.Cost, func(v, w int) (edge bool) {
return e.Contains(v, w)
})
Expand All @@ -104,13 +105,15 @@ func newEdges(n int, e EdgeSet) *Virtual {
return to.size()
case to.Contains(v):
return from.size()
default:
return
}
return
}
}

visit := func(v int, a int, do func(w int, c int64) bool) (aborted bool) {
if intersect.Contains(v) {
switch {
case intersect.Contains(v):
for _, in := range union.And(Range(a, n)).set {
for w := in.a; w < in.b; w++ {
if v != w && e.Keep(v, w) && do(w, e.Cost(v, w)) {
Expand All @@ -119,8 +122,7 @@ func newEdges(n int, e EdgeSet) *Virtual {
}
}
return
}
if from.Contains(v) {
case from.Contains(v):
for _, in := range to.And(Range(a, n)).set {
for w := in.a; w < in.b; w++ {
if e.Keep(v, w) && do(w, e.Cost(v, w)) {
Expand All @@ -129,8 +131,7 @@ func newEdges(n int, e EdgeSet) *Virtual {
}
}
return
}
if to.Contains(v) {
case to.Contains(v):
for _, in := range from.And(Range(a, n)).set {
for w := in.a; w < in.b; w++ {
if e.Keep(v, w) && do(w, e.Cost(v, w)) {
Expand All @@ -139,12 +140,14 @@ func newEdges(n int, e EdgeSet) *Virtual {
}
}
return
default:
return
}
return
}

visit0 := func(v int, a int, do func(w int, c int64) bool) (aborted bool) {
if intersect.Contains(v) {
switch {
case intersect.Contains(v):
for _, in := range union.And(Range(a, n)).set {
for w := in.a; w < in.b; w++ {
if v != w && e.Keep(v, w) && do(w, 0) {
Expand All @@ -153,8 +156,7 @@ func newEdges(n int, e EdgeSet) *Virtual {
}
}
return
}
if from.Contains(v) {
case from.Contains(v):
for _, in := range to.And(Range(a, n)).set {
for w := in.a; w < in.b; w++ {
if e.Keep(v, w) && do(w, 0) {
Expand All @@ -163,8 +165,7 @@ func newEdges(n int, e EdgeSet) *Virtual {
}
}
return
}
if to.Contains(v) {
case to.Contains(v):
for _, in := range from.And(Range(a, n)).set {
for w := in.a; w < in.b; w++ {
if e.Keep(v, w) && do(w, 0) {
Expand All @@ -173,8 +174,9 @@ func newEdges(n int, e EdgeSet) *Virtual {
}
}
return
default:
return
}
return
}

if noCost {
Expand Down
35 changes: 20 additions & 15 deletions build/join.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -20,11 +20,13 @@ func (g1 *Virtual) Join(g2 *Virtual, bridge EdgeSet) *Virtual {
bridge.Cost = zero
}
joinCost := func(v, w int) int64 {
if v < t && w < t {
switch {
case v < t && w < t:
return g1.cost(v, w)
}
if v >= t && w >= t {
case v >= t && w >= t:
return g2.cost(v-t, w-t)
default:
return bridge.Cost(v, w)
}
return bridge.Cost(v, w)
}
Expand All @@ -38,32 +40,35 @@ func (g1 *Virtual) Join(g2 *Virtual, bridge EdgeSet) *Virtual {
s2 := bridge.To.And(Range(t, g2.order+t))

res := generic(n, joinCost, func(v, w int) (edge bool) {
if v < t && w < t {
switch {
case v < t && w < t:
return g1.edge(v, w)
}
if v >= t && w >= t {
case v >= t && w >= t:
return g2.edge(v-t, w-t)
}
if !bridge.Keep(v, w) {
case !bridge.Keep(v, w):
return false
default:
return s1.Contains(v) && s2.Contains(w) ||
s1.Contains(w) && s2.Contains(v)
}
return s1.Contains(v) && s2.Contains(w) || s1.Contains(w) && s2.Contains(v)
})

if noFilter {
res.degree = func(v int) (deg int) {
if v < t {
switch {
case v < t:
deg = g1.degree(v)
if s1.Contains(v) {
deg += s2.size()
}
return
default:
deg = g2.degree(v - t)
if s2.Contains(v) {
deg += s1.size()
}
return
}
deg = g2.degree(v - t)
if s2.Contains(v) {
deg += s1.size()
}
return
}
}

Expand Down
29 changes: 15 additions & 14 deletions build/match.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -21,13 +21,14 @@ func (g1 *Virtual) Match(g2 *Virtual, bridge EdgeSet) *Virtual {
bridge.Cost = zero
}
matchCost := func(v, w int) int64 {
if v < t && w < t {
switch {
case v < t && w < t:
return g1.cost(v, w)
}
if v >= t && w >= t {
case v >= t && w >= t:
return g2.cost(v-t, w-t)
default:
return bridge.Cost(v, w)
}
return bridge.Cost(v, w)
}

if bridge.Keep == nil {
Expand All @@ -37,20 +38,20 @@ func (g1 *Virtual) Match(g2 *Virtual, bridge EdgeSet) *Virtual {
s2 := bridge.To.And(Range(t, g2.order+t))

res := generic(n, matchCost, func(v, w int) (edge bool) {
if v < t && w < t {
switch {
case v < t && w < t:
return g1.edge(v, w)
}
if v >= t && w >= t {
case v >= t && w >= t:
return g2.edge(v-t, w-t)
}
if !bridge.Keep(v, w) {
case !bridge.Keep(v, w):
return false
default:
s1v := s1.rank(v)
s1w := s1.rank(w)
s2v := s2.rank(v)
s2w := s2.rank(w)
return s1v != -1 && s1v == s2w || s1w != -1 && s1w == s2v
}
s1v := s1.rank(v)
s1w := s1.rank(w)
s2v := s2.rank(v)
s2w := s2.rank(w)
return s1v != -1 && s1v == s2w || s1w != -1 && s1w == s2v
})

res.visit = func(v int, a int, do func(w int, c int64) bool) (aborted bool) {
Expand Down
9 changes: 5 additions & 4 deletions build/subgraph.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -29,14 +29,15 @@ func (g *Virtual) Subgraph(s VertexSet) *Virtual {
s0 := s.And(Range(s.get(a), n))
for _, in := range s0.set {
if more := false; g.visit(v0, in.a, func(w0 int, c int64) (skip bool) {
if w0 >= in.b {
switch {
case w0 >= in.b:
more, skip = true, true
return
}
if do(s.rank(w0), c) {
case do(s.rank(w0), c):
return true
default:
return
}
return
}) && !more {
return true
}
Expand Down
Loading