aboutsummaryrefslogtreecommitdiffstats
path: root/vendor/github.com/soniakeys/graph/undir_RO.go
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/github.com/soniakeys/graph/undir_RO.go')
-rw-r--r--vendor/github.com/soniakeys/graph/undir_RO.go659
1 files changed, 659 insertions, 0 deletions
diff --git a/vendor/github.com/soniakeys/graph/undir_RO.go b/vendor/github.com/soniakeys/graph/undir_RO.go
new file mode 100644
index 0000000..fd8e377
--- /dev/null
+++ b/vendor/github.com/soniakeys/graph/undir_RO.go
@@ -0,0 +1,659 @@
+// Copyright 2014 Sonia Keys
+// License MIT: http://opensource.org/licenses/MIT
+
+package graph
+
+// undir_RO.go is code generated from undir_cg.go by directives in graph.go.
+// Editing undir_cg.go is okay. It is the code generation source.
+// DO NOT EDIT undir_RO.go.
+// The RO means read only and it is upper case RO to slow you down a bit
+// in case you start to edit the file.
+
+// Bipartite determines if a connected component of an undirected graph
+// is bipartite, a component where nodes can be partitioned into two sets
+// such that every edge in the component goes from one set to the other.
+//
+// Argument n can be any representative node of the component.
+//
+// If the component is bipartite, Bipartite returns true and a two-coloring
+// of the component. Each color set is returned as a bitmap. If the component
+// is not bipartite, Bipartite returns false and a representative odd cycle.
+//
+// There are equivalent labeled and unlabeled versions of this method.
+func (g Undirected) Bipartite(n NI) (b bool, c1, c2 Bits, oc []NI) {
+ b = true
+ var open bool
+ var df func(n NI, c1, c2 *Bits)
+ df = func(n NI, c1, c2 *Bits) {
+ c1.SetBit(n, 1)
+ for _, nb := range g.AdjacencyList[n] {
+ if c1.Bit(nb) == 1 {
+ b = false
+ oc = []NI{nb, n}
+ open = true
+ return
+ }
+ if c2.Bit(nb) == 1 {
+ continue
+ }
+ df(nb, c2, c1)
+ if b {
+ continue
+ }
+ switch {
+ case !open:
+ case n == oc[0]:
+ open = false
+ default:
+ oc = append(oc, n)
+ }
+ return
+ }
+ }
+ df(n, &c1, &c2)
+ if b {
+ return b, c1, c2, nil
+ }
+ return b, Bits{}, Bits{}, oc
+}
+
+// BronKerbosch1 finds maximal cliques in an undirected graph.
+//
+// The graph must not contain parallel edges or loops.
+//
+// See https://en.wikipedia.org/wiki/Clique_(graph_theory) and
+// https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm for background.
+//
+// This method implements the BronKerbosch1 algorithm of WP; that is,
+// the original algorithm without improvements.
+//
+// The method calls the emit argument for each maximal clique in g, as long
+// as emit returns true. If emit returns false, BronKerbosch1 returns
+// immediately.
+//
+// There are equivalent labeled and unlabeled versions of this method.
+//
+// See also more sophisticated variants BronKerbosch2 and BronKerbosch3.
+func (g Undirected) BronKerbosch1(emit func([]NI) bool) {
+ a := g.AdjacencyList
+ var f func(R, P, X *Bits) bool
+ f = func(R, P, X *Bits) bool {
+ switch {
+ case !P.Zero():
+ var r2, p2, x2 Bits
+ pf := func(n NI) bool {
+ r2.Set(*R)
+ r2.SetBit(n, 1)
+ p2.Clear()
+ x2.Clear()
+ for _, to := range a[n] {
+ if P.Bit(to) == 1 {
+ p2.SetBit(to, 1)
+ }
+ if X.Bit(to) == 1 {
+ x2.SetBit(to, 1)
+ }
+ }
+ if !f(&r2, &p2, &x2) {
+ return false
+ }
+ P.SetBit(n, 0)
+ X.SetBit(n, 1)
+ return true
+ }
+ if !P.Iterate(pf) {
+ return false
+ }
+ case X.Zero():
+ return emit(R.Slice())
+ }
+ return true
+ }
+ var R, P, X Bits
+ P.SetAll(len(a))
+ f(&R, &P, &X)
+}
+
+// BKPivotMaxDegree is a strategy for BronKerbosch methods.
+//
+// To use it, take the method value (see golang.org/ref/spec#Method_values)
+// and pass it as the argument to BronKerbosch2 or 3.
+//
+// The strategy is to pick the node from P or X with the maximum degree
+// (number of edges) in g. Note this is a shortcut from evaluating degrees
+// in P.
+//
+// There are equivalent labeled and unlabeled versions of this method.
+func (g Undirected) BKPivotMaxDegree(P, X *Bits) (p NI) {
+ // choose pivot u as highest degree node from P or X
+ a := g.AdjacencyList
+ maxDeg := -1
+ P.Iterate(func(n NI) bool { // scan P
+ if d := len(a[n]); d > maxDeg {
+ p = n
+ maxDeg = d
+ }
+ return true
+ })
+ X.Iterate(func(n NI) bool { // scan X
+ if d := len(a[n]); d > maxDeg {
+ p = n
+ maxDeg = d
+ }
+ return true
+ })
+ return
+}
+
+// BKPivotMinP is a strategy for BronKerbosch methods.
+//
+// To use it, take the method value (see golang.org/ref/spec#Method_values)
+// and pass it as the argument to BronKerbosch2 or 3.
+//
+// The strategy is to simply pick the first node in P.
+//
+// There are equivalent labeled and unlabeled versions of this method.
+func (g Undirected) BKPivotMinP(P, X *Bits) NI {
+ return P.From(0)
+}
+
+// BronKerbosch2 finds maximal cliques in an undirected graph.
+//
+// The graph must not contain parallel edges or loops.
+//
+// See https://en.wikipedia.org/wiki/Clique_(graph_theory) and
+// https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm for background.
+//
+// This method implements the BronKerbosch2 algorithm of WP; that is,
+// the original algorithm plus pivoting.
+//
+// The argument is a pivot function that must return a node of P or X.
+// P is guaranteed to contain at least one node. X is not.
+// For example see BKPivotMaxDegree.
+//
+// The method calls the emit argument for each maximal clique in g, as long
+// as emit returns true. If emit returns false, BronKerbosch1 returns
+// immediately.
+//
+// There are equivalent labeled and unlabeled versions of this method.
+//
+// See also simpler variant BronKerbosch1 and more sophisticated variant
+// BronKerbosch3.
+func (g Undirected) BronKerbosch2(pivot func(P, X *Bits) NI, emit func([]NI) bool) {
+ a := g.AdjacencyList
+ var f func(R, P, X *Bits) bool
+ f = func(R, P, X *Bits) bool {
+ switch {
+ case !P.Zero():
+ var r2, p2, x2, pnu Bits
+ // compute P \ N(u). next 5 lines are only difference from BK1
+ pnu.Set(*P)
+ for _, to := range a[pivot(P, X)] {
+ pnu.SetBit(to, 0)
+ }
+ // remaining code like BK1
+ pf := func(n NI) bool {
+ r2.Set(*R)
+ r2.SetBit(n, 1)
+ p2.Clear()
+ x2.Clear()
+ for _, to := range a[n] {
+ if P.Bit(to) == 1 {
+ p2.SetBit(to, 1)
+ }
+ if X.Bit(to) == 1 {
+ x2.SetBit(to, 1)
+ }
+ }
+ if !f(&r2, &p2, &x2) {
+ return false
+ }
+ P.SetBit(n, 0)
+ X.SetBit(n, 1)
+ return true
+ }
+ if !pnu.Iterate(pf) {
+ return false
+ }
+ case X.Zero():
+ return emit(R.Slice())
+ }
+ return true
+ }
+ var R, P, X Bits
+ P.SetAll(len(a))
+ f(&R, &P, &X)
+}
+
+// BronKerbosch3 finds maximal cliques in an undirected graph.
+//
+// The graph must not contain parallel edges or loops.
+//
+// See https://en.wikipedia.org/wiki/Clique_(graph_theory) and
+// https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm for background.
+//
+// This method implements the BronKerbosch3 algorithm of WP; that is,
+// the original algorithm with pivoting and degeneracy ordering.
+//
+// The argument is a pivot function that must return a node of P or X.
+// P is guaranteed to contain at least one node. X is not.
+// For example see BKPivotMaxDegree.
+//
+// The method calls the emit argument for each maximal clique in g, as long
+// as emit returns true. If emit returns false, BronKerbosch1 returns
+// immediately.
+//
+// There are equivalent labeled and unlabeled versions of this method.
+//
+// See also simpler variants BronKerbosch1 and BronKerbosch2.
+func (g Undirected) BronKerbosch3(pivot func(P, X *Bits) NI, emit func([]NI) bool) {
+ a := g.AdjacencyList
+ var f func(R, P, X *Bits) bool
+ f = func(R, P, X *Bits) bool {
+ switch {
+ case !P.Zero():
+ var r2, p2, x2, pnu Bits
+ // compute P \ N(u). next lines are only difference from BK1
+ pnu.Set(*P)
+ for _, to := range a[pivot(P, X)] {
+ pnu.SetBit(to, 0)
+ }
+ // remaining code like BK2
+ pf := func(n NI) bool {
+ r2.Set(*R)
+ r2.SetBit(n, 1)
+ p2.Clear()
+ x2.Clear()
+ for _, to := range a[n] {
+ if P.Bit(to) == 1 {
+ p2.SetBit(to, 1)
+ }
+ if X.Bit(to) == 1 {
+ x2.SetBit(to, 1)
+ }
+ }
+ if !f(&r2, &p2, &x2) {
+ return false
+ }
+ P.SetBit(n, 0)
+ X.SetBit(n, 1)
+ return true
+ }
+ if !pnu.Iterate(pf) {
+ return false
+ }
+ case X.Zero():
+ return emit(R.Slice())
+ }
+ return true
+ }
+ var R, P, X Bits
+ P.SetAll(len(a))
+ // code above same as BK2
+ // code below new to BK3
+ _, ord, _ := g.Degeneracy()
+ var p2, x2 Bits
+ for _, n := range ord {
+ R.SetBit(n, 1)
+ p2.Clear()
+ x2.Clear()
+ for _, to := range a[n] {
+ if P.Bit(to) == 1 {
+ p2.SetBit(to, 1)
+ }
+ if X.Bit(to) == 1 {
+ x2.SetBit(to, 1)
+ }
+ }
+ if !f(&R, &p2, &x2) {
+ return
+ }
+ R.SetBit(n, 0)
+ P.SetBit(n, 0)
+ X.SetBit(n, 1)
+ }
+}
+
+// ConnectedComponentBits returns a function that iterates over connected
+// components of g, returning a member bitmap for each.
+//
+// Each call of the returned function returns the order (number of nodes)
+// and bits of a connected component. The returned function returns zeros
+// after returning all connected components.
+//
+// There are equivalent labeled and unlabeled versions of this method.
+//
+// See also ConnectedComponentReps, which has lighter weight return values.
+func (g Undirected) ConnectedComponentBits() func() (order int, bits Bits) {
+ a := g.AdjacencyList
+ var vg Bits // nodes visited in graph
+ var vc *Bits // nodes visited in current component
+ var nc int
+ var df func(NI)
+ df = func(n NI) {
+ vg.SetBit(n, 1)
+ vc.SetBit(n, 1)
+ nc++
+ for _, nb := range a[n] {
+ if vg.Bit(nb) == 0 {
+ df(nb)
+ }
+ }
+ return
+ }
+ var n NI
+ return func() (o int, bits Bits) {
+ for ; n < NI(len(a)); n++ {
+ if vg.Bit(n) == 0 {
+ vc = &bits
+ nc = 0
+ df(n)
+ return nc, bits
+ }
+ }
+ return
+ }
+}
+
+// ConnectedComponentLists returns a function that iterates over connected
+// components of g, returning the member list of each.
+//
+// Each call of the returned function returns a node list of a connected
+// component. The returned function returns nil after returning all connected
+// components.
+//
+// There are equivalent labeled and unlabeled versions of this method.
+//
+// See also ConnectedComponentReps, which has lighter weight return values.
+func (g Undirected) ConnectedComponentLists() func() []NI {
+ a := g.AdjacencyList
+ var vg Bits // nodes visited in graph
+ var m []NI // members of current component
+ var df func(NI)
+ df = func(n NI) {
+ vg.SetBit(n, 1)
+ m = append(m, n)
+ for _, nb := range a[n] {
+ if vg.Bit(nb) == 0 {
+ df(nb)
+ }
+ }
+ return
+ }
+ var n NI
+ return func() []NI {
+ for ; n < NI(len(a)); n++ {
+ if vg.Bit(n) == 0 {
+ m = nil
+ df(n)
+ return m
+ }
+ }
+ return nil
+ }
+}
+
+// ConnectedComponentReps returns a representative node from each connected
+// component of g.
+//
+// Returned is a slice with a single representative node from each connected
+// component and also a parallel slice with the order, or number of nodes,
+// in the corresponding component.
+//
+// This is fairly minimal information describing connected components.
+// From a representative node, other nodes in the component can be reached
+// by depth first traversal for example.
+//
+// There are equivalent labeled and unlabeled versions of this method.
+//
+// See also ConnectedComponentBits and ConnectedComponentLists which can
+// collect component members in a single traversal, and IsConnected which
+// is an even simpler boolean test.
+func (g Undirected) ConnectedComponentReps() (reps []NI, orders []int) {
+ a := g.AdjacencyList
+ var c Bits
+ var o int
+ var df func(NI)
+ df = func(n NI) {
+ c.SetBit(n, 1)
+ o++
+ for _, nb := range a[n] {
+ if c.Bit(nb) == 0 {
+ df(nb)
+ }
+ }
+ return
+ }
+ for n := range a {
+ if c.Bit(NI(n)) == 0 {
+ reps = append(reps, NI(n))
+ o = 0
+ df(NI(n))
+ orders = append(orders, o)
+ }
+ }
+ return
+}
+
+// Copy makes a deep copy of g.
+// Copy also computes the arc size ma, the number of arcs.
+//
+// There are equivalent labeled and unlabeled versions of this method.
+func (g Undirected) Copy() (c Undirected, ma int) {
+ l, s := g.AdjacencyList.Copy()
+ return Undirected{l}, s
+}
+
+// Degeneracy computes k-degeneracy, vertex ordering and k-cores.
+//
+// See Wikipedia https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)
+//
+// There are equivalent labeled and unlabeled versions of this method.
+func (g Undirected) Degeneracy() (k int, ordering []NI, cores []int) {
+ a := g.AdjacencyList
+ // WP algorithm
+ ordering = make([]NI, len(a))
+ var L Bits
+ d := make([]int, len(a))
+ var D [][]NI
+ for v, nb := range a {
+ dv := len(nb)
+ d[v] = dv
+ for len(D) <= dv {
+ D = append(D, nil)
+ }
+ D[dv] = append(D[dv], NI(v))
+ }
+ for ox := range a {
+ // find a non-empty D
+ i := 0
+ for len(D[i]) == 0 {
+ i++
+ }
+ // k is max(i, k)
+ if i > k {
+ for len(cores) <= i {
+ cores = append(cores, 0)
+ }
+ cores[k] = ox
+ k = i
+ }
+ // select from D[i]
+ Di := D[i]
+ last := len(Di) - 1
+ v := Di[last]
+ // Add v to ordering, remove from Di
+ ordering[ox] = v
+ L.SetBit(v, 1)
+ D[i] = Di[:last]
+ // move neighbors
+ for _, nb := range a[v] {
+ if L.Bit(nb) == 1 {
+ continue
+ }
+ dn := d[nb] // old number of neighbors of nb
+ Ddn := D[dn] // nb is in this list
+ // remove it from the list
+ for wx, w := range Ddn {
+ if w == nb {
+ last := len(Ddn) - 1
+ Ddn[wx], Ddn[last] = Ddn[last], Ddn[wx]
+ D[dn] = Ddn[:last]
+ }
+ }
+ dn-- // new number of neighbors
+ d[nb] = dn
+ // re--add it to it's new list
+ D[dn] = append(D[dn], nb)
+ }
+ }
+ cores[k] = len(ordering)
+ return
+}
+
+// Degree for undirected graphs, returns the degree of a node.
+//
+// The degree of a node in an undirected graph is the number of incident
+// edges, where loops count twice.
+//
+// If g is known to be loop-free, the result is simply equivalent to len(g[n]).
+// See handshaking lemma example at AdjacencyList.ArcSize.
+//
+// There are equivalent labeled and unlabeled versions of this method.
+func (g Undirected) Degree(n NI) int {
+ to := g.AdjacencyList[n]
+ d := len(to) // just "out" degree,
+ for _, to := range to {
+ if to == n {
+ d++ // except loops count twice
+ }
+ }
+ return d
+}
+
+// FromList constructs a FromList representing the tree reachable from
+// the given root.
+//
+// The connected component containing root should represent a simple graph,
+// connected as a tree.
+//
+// For nodes connected as a tree, the Path member of the returned FromList
+// will be populated with both From and Len values. The MaxLen member will be
+// set but Leaves will be left a zero value. Return value cycle will be -1.
+//
+// If the connected component containing root is not connected as a tree,
+// a cycle will be detected. The returned FromList will be a zero value and
+// return value cycle will be a node involved in the cycle.
+//
+// Loops and parallel edges will be detected as cycles, however only in the
+// connected component containing root. If g is not fully connected, nodes
+// not reachable from root will have PathEnd values of {From: -1, Len: 0}.
+//
+// There are equivalent labeled and unlabeled versions of this method.
+func (g Undirected) FromList(root NI) (f FromList, cycle NI) {
+ p := make([]PathEnd, len(g.AdjacencyList))
+ for i := range p {
+ p[i].From = -1
+ }
+ ml := 0
+ var df func(NI, NI) bool
+ df = func(fr, n NI) bool {
+ l := p[n].Len + 1
+ for _, to := range g.AdjacencyList[n] {
+ if to == fr {
+ continue
+ }
+ if p[to].Len > 0 {
+ cycle = to
+ return false
+ }
+ p[to] = PathEnd{From: n, Len: l}
+ if l > ml {
+ ml = l
+ }
+ if !df(n, to) {
+ return false
+ }
+ }
+ return true
+ }
+ p[root].Len = 1
+ if !df(-1, root) {
+ return
+ }
+ return FromList{Paths: p, MaxLen: ml}, -1
+}
+
+// IsConnected tests if an undirected graph is a single connected component.
+//
+// There are equivalent labeled and unlabeled versions of this method.
+//
+// See also ConnectedComponentReps for a method returning more information.
+func (g Undirected) IsConnected() bool {
+ a := g.AdjacencyList
+ if len(a) == 0 {
+ return true
+ }
+ var b Bits
+ b.SetAll(len(a))
+ var df func(NI)
+ df = func(n NI) {
+ b.SetBit(n, 0)
+ for _, to := range a[n] {
+ if b.Bit(to) == 1 {
+ df(to)
+ }
+ }
+ }
+ df(0)
+ return b.Zero()
+}
+
+// IsTree identifies trees in undirected graphs.
+//
+// Return value isTree is true if the connected component reachable from root
+// is a tree. Further, return value allTree is true if the entire graph g is
+// connected.
+//
+// There are equivalent labeled and unlabeled versions of this method.
+func (g Undirected) IsTree(root NI) (isTree, allTree bool) {
+ a := g.AdjacencyList
+ var v Bits
+ v.SetAll(len(a))
+ var df func(NI, NI) bool
+ df = func(fr, n NI) bool {
+ if v.Bit(n) == 0 {
+ return false
+ }
+ v.SetBit(n, 0)
+ for _, to := range a[n] {
+ if to != fr && !df(n, to) {
+ return false
+ }
+ }
+ return true
+ }
+ v.SetBit(root, 0)
+ for _, to := range a[root] {
+ if !df(root, to) {
+ return false, false
+ }
+ }
+ return true, v.Zero()
+}
+
+// Size returns the number of edges in g.
+//
+// See also ArcSize and HasLoop.
+func (g Undirected) Size() int {
+ m2 := 0
+ for fr, to := range g.AdjacencyList {
+ m2 += len(to)
+ for _, to := range to {
+ if to == NI(fr) {
+ m2++
+ }
+ }
+ }
+ return m2 / 2
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-30 12:55:39 +0000