1// Copyright 2014 Sonia Keys 2// License MIT: http://opensource.org/licenses/MIT 3 4package graph 5 6import ( 7 "bytes" 8 "errors" 9 "fmt" 10 "math" 11 "reflect" 12 "text/template" 13 14 "github.com/soniakeys/bits" 15) 16 17// graph.go contains type definitions for all graph types and components. 18// Also, go generate directives for source transformations. 19// 20// For readability, the types are defined in a dependency order: 21// 22// NI 23// AdjacencyList 24// Directed 25// Undirected 26// Bipartite 27// Subgraph 28// DirectedSubgraph 29// UndirectedSubgraph 30// LI 31// Half 32// fromHalf 33// LabeledAdjacencyList 34// LabeledDirected 35// LabeledUndirected 36// LabeledBipartite 37// LabeledSubgraph 38// LabeledDirectedSubgraph 39// LabeledUndirectedSubgraph 40// Edge 41// LabeledEdge 42// LabeledPath 43// WeightFunc 44// WeightedEdgeList 45// TraverseOption 46 47//go:generate cp adj_cg.go adj_RO.go 48//go:generate gofmt -r "LabeledAdjacencyList -> AdjacencyList" -w adj_RO.go 49//go:generate gofmt -r "n.To -> n" -w adj_RO.go 50//go:generate gofmt -r "Half -> NI" -w adj_RO.go 51//go:generate gofmt -r "LabeledSubgraph -> Subgraph" -w adj_RO.go 52 53//go:generate cp dir_cg.go dir_RO.go 54//go:generate gofmt -r "LabeledDirected -> Directed" -w dir_RO.go 55//go:generate gofmt -r "LabeledDirectedSubgraph -> DirectedSubgraph" -w dir_RO.go 56//go:generate gofmt -r "LabeledAdjacencyList -> AdjacencyList" -w dir_RO.go 57//go:generate gofmt -r "labEulerian -> eulerian" -w dir_RO.go 58//go:generate gofmt -r "newLabEulerian -> newEulerian" -w dir_RO.go 59//go:generate gofmt -r "Half{n, -1} -> n" -w dir_RO.go 60//go:generate gofmt -r "n.To -> n" -w dir_RO.go 61//go:generate gofmt -r "Half -> NI" -w dir_RO.go 62 63//go:generate cp undir_cg.go undir_RO.go 64//go:generate gofmt -r "LabeledUndirected -> Undirected" -w undir_RO.go 65//go:generate gofmt -r "LabeledBipartite -> Bipartite" -w undir_RO.go 66//go:generate gofmt -r "LabeledUndirectedSubgraph -> UndirectedSubgraph" -w undir_RO.go 67//go:generate gofmt -r "LabeledAdjacencyList -> AdjacencyList" -w undir_RO.go 68//go:generate gofmt -r "newLabEulerian -> newEulerian" -w undir_RO.go 69//go:generate gofmt -r "Half{n, -1} -> n" -w undir_RO.go 70//go:generate gofmt -r "n.To -> n" -w undir_RO.go 71//go:generate gofmt -r "Half -> NI" -w undir_RO.go 72 73// NI is a "node int" 74// 75// It is a node number or node ID. NIs are used extensively as slice indexes. 76// NIs typically account for a significant fraction of the memory footprint of 77// a graph. 78type NI int32 79 80var NIBits = reflect.TypeOf(NI(0)).Bits() 81 82// An AdjacencyList represents a graph as a list of neighbors for each node. 83// The "node ID" of a node is simply it's slice index in the AdjacencyList. 84// For an AdjacencyList g, g[n] represents arcs going from node n to nodes 85// g[n]. 86// 87// Adjacency lists are inherently directed but can be used to represent 88// directed or undirected graphs. See types Directed and Undirected. 89type AdjacencyList [][]NI 90 91// Directed represents a directed graph. 92// 93// Directed methods generally rely on the graph being directed, specifically 94// that arcs do not have reciprocals. 95type Directed struct { 96 AdjacencyList // embedded to include AdjacencyList methods 97} 98 99// Undirected represents an undirected graph. 100// 101// In an undirected graph, for each arc between distinct nodes there is also 102// a reciprocal arc, an arc in the opposite direction. Loops do not have 103// reciprocals. 104// 105// Undirected methods generally rely on the graph being undirected, 106// specifically that every arc between distinct nodes has a reciprocal. 107type Undirected struct { 108 AdjacencyList // embedded to include AdjacencyList methods 109} 110 111// Bipartite represents a bipartite graph. 112// 113// In a bipartite graph, nodes are partitioned into two sets, or 114// "colors," such that every edge in the graph goes from one set to the 115// other. 116// 117// Member Color represents the partition with a bitmap of length the same 118// as the number of nodes in the graph. For convenience N0 stores the number 119// of zero bits in Color. 120// 121// To construct a Bipartite object, if you can easily or efficiently use 122// available information to construct the Color member, then you should do 123// this and construct a Bipartite object with a Go struct literal. 124// 125// If partition information is not readily available, see the constructor 126// Undirected.Bipartite. 127// 128// Alternatively, in some cases where the graph may have multiple connected 129// components, the lower level Undirected.BipartiteComponent can be used to 130// control color assignment by component. 131type Bipartite struct { 132 Undirected 133 Color bits.Bits 134 N0 int 135} 136 137// Subgraph represents a subgraph mapped to a supergraph. 138// 139// The subgraph is the embedded AdjacencyList and so the Subgraph type inherits 140// all methods of Adjacency list. 141// 142// The embedded subgraph mapped relative to a specific supergraph, member 143// Super. A subgraph may have fewer nodes than its supergraph. 144// Each node of the subgraph must map to a distinct node of the supergraph. 145// 146// The mapping giving the supergraph node for a given subgraph node is 147// represented by member SuperNI, a slice parallel to the the subgraph. 148// 149// The mapping in the other direction, giving a subgraph NI for a given 150// supergraph NI, is represented with map SubNI. 151// 152// Multiple Subgraphs can be created relative to a single supergraph. 153// The Subgraph type represents a mapping to only a single supergraph however. 154// 155// See graph methods InduceList and InduceBits for construction of 156// node-induced subgraphs. 157// 158// Alternatively an empty subgraph can be constructed with InduceList(nil). 159// Arbitrary subgraphs can then be built up with methods AddNode and AddArc. 160type Subgraph struct { 161 AdjacencyList // the subgraph 162 Super *AdjacencyList // the supergraph 163 SubNI map[NI]NI // subgraph NIs, indexed by supergraph NIs 164 SuperNI []NI // supergraph NIs indexed by subgraph NIs 165} 166 167// DirectedSubgraph represents a subgraph mapped to a supergraph. 168// 169// See additional doc at Subgraph type. 170type DirectedSubgraph struct { 171 Directed 172 Super *Directed 173 SubNI map[NI]NI 174 SuperNI []NI 175} 176 177// UndirectedSubgraph represents a subgraph mapped to a supergraph. 178// 179// See additional doc at Subgraph type. 180type UndirectedSubgraph struct { 181 Undirected 182 Super *Undirected 183 SubNI map[NI]NI 184 SuperNI []NI 185} 186 187// LI is a label integer, used for associating labels with arcs. 188type LI int32 189 190// Half is a half arc, representing a labeled arc and the "neighbor" node 191// that the arc leads to. 192// 193// Halfs can be composed to form a labeled adjacency list. 194type Half struct { 195 To NI // node ID, usable as a slice index 196 Label LI // half-arc ID for application data, often a weight 197} 198 199// fromHalf is a half arc, representing a labeled arc and the "neighbor" node 200// that the arc originates from. 201// 202// This used internally in a couple of places. It used to be exported but is 203// not currently needed anwhere in the API. 204type fromHalf struct { 205 From NI 206 Label LI 207} 208 209// A LabeledAdjacencyList represents a graph as a list of neighbors for each 210// node, connected by labeled arcs. 211// 212// Arc labels are not necessarily unique arc IDs. Different arcs can have 213// the same label. 214// 215// Arc labels are commonly used to assocate a weight with an arc. Arc labels 216// are general purpose however and can be used to associate arbitrary 217// information with an arc. 218// 219// Methods implementing weighted graph algorithms will commonly take a 220// weight function that turns a label int into a float64 weight. 221// 222// If only a small amount of information -- such as an integer weight or 223// a single printable character -- needs to be associated, it can sometimes 224// be possible to encode the information directly into the label int. For 225// more generality, some lookup scheme will be needed. 226// 227// In an undirected labeled graph, reciprocal arcs must have identical labels. 228// Note this does not preclude parallel arcs with different labels. 229type LabeledAdjacencyList [][]Half 230 231// LabeledDirected represents a directed labeled graph. 232// 233// This is the labeled version of Directed. See types LabeledAdjacencyList 234// and Directed. 235type LabeledDirected struct { 236 LabeledAdjacencyList // embedded to include LabeledAdjacencyList methods 237} 238 239// LabeledUndirected represents an undirected labeled graph. 240// 241// This is the labeled version of Undirected. See types LabeledAdjacencyList 242// and Undirected. 243type LabeledUndirected struct { 244 LabeledAdjacencyList // embedded to include LabeledAdjacencyList methods 245} 246 247// LabeledBipartite represents a bipartite graph. 248// 249// In a bipartite graph, nodes are partitioned into two sets, or 250// "colors," such that every edge in the graph goes from one set to the 251// other. 252// 253// Member Color represents the partition with a bitmap of length the same 254// as the number of nodes in the graph. For convenience N0 stores the number 255// of zero bits in Color. 256// 257// To construct a LabeledBipartite object, if you can easily or efficiently use 258// available information to construct the Color member, then you should do 259// this and construct a LabeledBipartite object with a Go struct literal. 260// 261// If partition information is not readily available, see the constructor 262// Undirected.LabeledBipartite. 263// 264// Alternatively, in some cases where the graph may have multiple connected 265// components, the lower level LabeledUndirected.BipartiteComponent can be used 266// to control color assignment by component. 267type LabeledBipartite struct { 268 LabeledUndirected 269 Color bits.Bits 270 N0 int 271} 272 273// LabeledSubgraph represents a subgraph mapped to a supergraph. 274// 275// See additional doc at Subgraph type. 276type LabeledSubgraph struct { 277 LabeledAdjacencyList 278 Super *LabeledAdjacencyList 279 SubNI map[NI]NI 280 SuperNI []NI 281} 282 283// LabeledDirectedSubgraph represents a subgraph mapped to a supergraph. 284// 285// See additional doc at Subgraph type. 286type LabeledDirectedSubgraph struct { 287 LabeledDirected 288 Super *LabeledDirected 289 SubNI map[NI]NI 290 SuperNI []NI 291} 292 293// LabeledUndirectedSubgraph represents a subgraph mapped to a supergraph. 294// 295// See additional doc at Subgraph type. 296type LabeledUndirectedSubgraph struct { 297 LabeledUndirected 298 Super *LabeledUndirected 299 SubNI map[NI]NI 300 SuperNI []NI 301} 302 303// Edge is an undirected edge between nodes N1 and N2. 304type Edge struct{ N1, N2 NI } 305 306// LabeledEdge is an undirected edge with an associated label. 307type LabeledEdge struct { 308 Edge 309 LI 310} 311 312// LabeledPath is a start node and a path of half arcs leading from start. 313type LabeledPath struct { 314 Start NI 315 Path []Half 316} 317 318// Distance returns total path distance given WeightFunc w. 319func (p LabeledPath) Distance(w WeightFunc) float64 { 320 d := 0. 321 for _, h := range p.Path { 322 d += w(h.Label) 323 } 324 return d 325} 326 327// WeightFunc returns a weight for a given label. 328// 329// WeightFunc is a parameter type for various search functions. The intent 330// is to return a weight corresponding to an arc label. The name "weight" 331// is an abstract term. An arc "weight" will typically have some application 332// specific meaning other than physical weight. 333type WeightFunc func(label LI) (weight float64) 334 335// WeightedEdgeList is a graph representation. 336// 337// It is a labeled edge list, with an associated weight function to return 338// a weight given an edge label. 339// 340// Also associated is the order, or number of nodes of the graph. 341// All nodes occurring in the edge list must be strictly less than Order. 342// 343// WeigtedEdgeList sorts by weight, obtained by calling the weight function. 344// If weight computation is expensive, consider supplying a cached or 345// memoized version. 346type WeightedEdgeList struct { 347 Order int 348 WeightFunc 349 Edges []LabeledEdge 350} 351 352// DistanceMatrix constructs a distance matrix corresponding to the weighted 353// edges of l. 354// 355// An edge n1, n2 with WeightFunc return w is represented by both 356// d[n1][n2] == w and d[n2][n1] = w. In case of parallel edges, the lowest 357// weight is stored. The distance from any node to itself d[n][n] is 0, unless 358// the node has a loop with a negative weight. If g has no edge between n1 and 359// distinct n2, +Inf is stored for d[n1][n2] and d[n2][n1]. 360// 361// The returned DistanceMatrix is suitable for DistanceMatrix.FloydWarshall. 362func (l WeightedEdgeList) DistanceMatrix() (d DistanceMatrix) { 363 d = newDM(l.Order) 364 for _, e := range l.Edges { 365 n1 := e.Edge.N1 366 n2 := e.Edge.N2 367 wt := l.WeightFunc(e.LI) 368 // < to pick min of parallel arcs (also nicely ignores NaN) 369 if wt < d[n1][n2] { 370 d[n1][n2] = wt 371 d[n2][n1] = wt 372 } 373 } 374 return 375} 376 377// A DistanceMatrix is a square matrix representing some distance between 378// nodes of a graph. If the graph is directected, d[from][to] represents 379// some distance from node 'from' to node 'to'. Depending on context, the 380// distance may be an arc weight or path distance. A value of +Inf typically 381// means no arc or no path between the nodes. 382type DistanceMatrix [][]float64 383 384// little helper function, makes a blank distance matrix for FloydWarshall. 385// could be exported? 386func newDM(n int) DistanceMatrix { 387 inf := math.Inf(1) 388 d := make(DistanceMatrix, n) 389 for i := range d { 390 di := make([]float64, n) 391 for j := range di { 392 di[j] = inf 393 } 394 di[i] = 0 395 d[i] = di 396 } 397 return d 398} 399 400// FloydWarshall finds all pairs shortest distances for a weighted graph 401// without negative cycles. 402// 403// It operates on a distance matrix representing arcs of a graph and 404// destructively replaces arc weights with shortest path distances. 405// 406// In receiver d, d[fr][to] will be the shortest distance from node 407// 'fr' to node 'to'. An element value of +Inf means no path exists. 408// Any diagonal element < 0 indicates a negative cycle exists. 409// 410// See DistanceMatrix constructor methods of LabeledAdjacencyList and 411// WeightedEdgeList for suitable inputs. 412func (d DistanceMatrix) FloydWarshall() { 413 for k, dk := range d { 414 for _, di := range d { 415 dik := di[k] 416 for j := range d { 417 if d2 := dik + dk[j]; d2 < di[j] { 418 di[j] = d2 419 } 420 } 421 } 422 } 423} 424 425// PathMatrix is a return type for FloydWarshallPaths. 426// 427// It encodes all pairs shortest paths. 428type PathMatrix [][]NI 429 430// Path returns a shortest path from node start to end. 431// 432// Argument p is truncated, appended to, and returned as the result. 433// Thus the underlying allocation is reused if possible. 434// If there is no path from start to end, p is returned truncated to 435// zero length. 436// 437// If receiver m is not a valid populated PathMatrix as returned by 438// FloydWarshallPaths, behavior is undefined and a panic is likely. 439func (m PathMatrix) Path(start, end NI, p []NI) []NI { 440 p = p[:0] 441 for { 442 p = append(p, start) 443 if start == end { 444 return p 445 } 446 start = m[start][end] 447 if start < 0 { 448 return p[:0] 449 } 450 } 451} 452 453// FloydWarshallPaths finds all pairs shortest paths for a weighted graph 454// without negative cycles. 455// 456// It operates on a distance matrix representing arcs of a graph and 457// destructively replaces arc weights with shortest path distances. 458// 459// In receiver d, d[fr][to] will be the shortest distance from node 460// 'fr' to node 'to'. An element value of +Inf means no path exists. 461// Any diagonal element < 0 indicates a negative cycle exists. 462// 463// The return value encodes the paths. See PathMatrix.Path. 464// 465// See DistanceMatrix constructor methods of LabeledAdjacencyList and 466// WeightedEdgeList for suitable inputs. 467// 468// See also similar method FloydWarshallFromLists which has a richer 469// return value. 470func (d DistanceMatrix) FloydWarshallPaths() PathMatrix { 471 m := make(PathMatrix, len(d)) 472 inf := math.Inf(1) 473 for i, di := range d { 474 mi := make([]NI, len(d)) 475 for j, dij := range di { 476 if dij == inf { 477 mi[j] = -1 478 } else { 479 mi[j] = NI(j) 480 } 481 } 482 m[i] = mi 483 } 484 for k, dk := range d { 485 for i, di := range d { 486 mi := m[i] 487 dik := di[k] 488 for j := range d { 489 if d2 := dik + dk[j]; d2 < di[j] { 490 di[j] = d2 491 mi[j] = mi[k] 492 } 493 } 494 } 495 } 496 return m 497} 498 499// FloydWarshallFromLists finds all pairs shortest paths for a weighted 500// graph without negative cycles. 501// 502// It operates on a distance matrix representing arcs of a graph and 503// destructively replaces arc weights with shortest path distances. 504// 505// In receiver d, d[fr][to] will be the shortest distance from node 506// 'fr' to node 'to'. An element value of +Inf means no path exists. 507// Any diagonal element < 0 indicates a negative cycle exists. 508// 509// The return value encodes the paths. The FromLists are fully populated 510// with Leaves and Len values. See for example FromList.PathTo for 511// extracting paths. Note though that for i'th FromList of the return 512// value, PathTo(j) will return the path from j's root, which will not 513// be i in the case that there is no path from i to j. You must check 514// the first node of the path to see if it is i. If not, there is no 515// path from i to j. See example. 516// 517// See DistanceMatrix constructor methods of LabeledAdjacencyList and 518// WeightedEdgeList for suitable inputs. 519// 520// See also similar method FloydWarshallPaths, which has a lighter 521// weight return value. 522func (d DistanceMatrix) FloydWarshallFromLists() []FromList { 523 l := make([]FromList, len(d)) 524 inf := math.Inf(1) 525 for i, di := range d { 526 li := NewFromList(len(d)) 527 p := li.Paths 528 for j, dij := range di { 529 if i == j || dij == inf { 530 p[j] = PathEnd{From: -1} 531 } else { 532 p[j] = PathEnd{From: NI(i)} 533 } 534 } 535 l[i] = li 536 } 537 for k, dk := range d { 538 pk := l[k].Paths 539 for i, di := range d { 540 dik := di[k] 541 pi := l[i].Paths 542 for j := range d { 543 if d2 := dik + dk[j]; d2 < di[j] { 544 di[j] = d2 545 pi[j] = pk[j] 546 } 547 } 548 } 549 } 550 for _, li := range l { 551 li.RecalcLeaves() 552 li.RecalcLen() 553 } 554 return l 555} 556 557// AddEdge adds an edge to a subgraph. 558// 559// For argument e, e.N1 and e.N2 must be NIs in supergraph s.Super. As with 560// AddNode, AddEdge panics if e.N1 and e.N2 are not valid node indexes of 561// s.Super. 562// 563// Edge e must exist in s.Super. Further, the number of 564// parallel edges in the subgraph cannot exceed the number of corresponding 565// parallel edges in the supergraph. That is, each edge already added to the 566// subgraph counts against the edges available in the supergraph. If a matching 567// edge is not available, AddEdge returns an error. 568// 569// If a matching edge is available, subgraph nodes are added as needed, the 570// subgraph edge is added, and the method returns nil. 571func (s *UndirectedSubgraph) AddEdge(n1, n2 NI) error { 572 // verify supergraph NIs first, but without adding subgraph nodes just yet. 573 if int(n1) < 0 || int(n1) >= s.Super.Order() { 574 panic(fmt.Sprint("AddEdge: NI ", n1, " not in supergraph")) 575 } 576 if int(n2) < 0 || int(n2) >= s.Super.Order() { 577 panic(fmt.Sprint("AddEdge: NI ", n2, " not in supergraph")) 578 } 579 // count existing matching edges in subgraph 580 n := 0 581 a := s.Undirected.AdjacencyList 582 if b1, ok := s.SubNI[n1]; ok { 583 if b2, ok := s.SubNI[n2]; ok { 584 // both NIs already exist in subgraph, need to count edges 585 for _, t := range a[b1] { 586 if t == b2 { 587 n++ 588 } 589 } 590 if b1 != b2 { 591 // verify reciprocal arcs exist 592 r := 0 593 for _, t := range a[b2] { 594 if t == b1 { 595 r++ 596 } 597 } 598 if r < n { 599 n = r 600 } 601 } 602 } 603 } 604 // verify matching edges are available in supergraph 605 m := 0 606 for _, t := range (*s.Super).AdjacencyList[n1] { 607 if t == n2 { 608 if m == n { 609 goto r // arc match after all existing arcs matched 610 } 611 m++ 612 } 613 } 614 return errors.New("edge not available in supergraph") 615r: 616 if n1 != n2 { 617 // verify reciprocal arcs 618 m = 0 619 for _, t := range (*s.Super).AdjacencyList[n2] { 620 if t == n1 { 621 if m == n { 622 goto good 623 } 624 m++ 625 } 626 } 627 return errors.New("edge not available in supergraph") 628 } 629good: 630 // matched enough edges. nodes can finally 631 // be added as needed and then the edge can be added. 632 b1 := s.AddNode(n1) 633 b2 := s.AddNode(n2) 634 s.Undirected.AddEdge(b1, b2) 635 return nil // success 636} 637 638// AddEdge adds an edge to a subgraph. 639// 640// For argument e, e.N1 and e.N2 must be NIs in supergraph s.Super. As with 641// AddNode, AddEdge panics if e.N1 and e.N2 are not valid node indexes of 642// s.Super. 643// 644// Edge e must exist in s.Super with label l. Further, the number of 645// parallel edges in the subgraph cannot exceed the number of corresponding 646// parallel edges in the supergraph. That is, each edge already added to the 647// subgraph counts against the edges available in the supergraph. If a matching 648// edge is not available, AddEdge returns an error. 649// 650// If a matching edge is available, subgraph nodes are added as needed, the 651// subgraph edge is added, and the method returns nil. 652func (s *LabeledUndirectedSubgraph) AddEdge(e Edge, l LI) error { 653 // verify supergraph NIs first, but without adding subgraph nodes just yet. 654 if int(e.N1) < 0 || int(e.N1) >= s.Super.Order() { 655 panic(fmt.Sprint("AddEdge: NI ", e.N1, " not in supergraph")) 656 } 657 if int(e.N2) < 0 || int(e.N2) >= s.Super.Order() { 658 panic(fmt.Sprint("AddEdge: NI ", e.N2, " not in supergraph")) 659 } 660 // count existing matching edges in subgraph 661 n := 0 662 a := s.LabeledUndirected.LabeledAdjacencyList 663 if b1, ok := s.SubNI[e.N1]; ok { 664 if b2, ok := s.SubNI[e.N2]; ok { 665 // both NIs already exist in subgraph, need to count edges 666 h := Half{b2, l} 667 for _, t := range a[b1] { 668 if t == h { 669 n++ 670 } 671 } 672 if b1 != b2 { 673 // verify reciprocal arcs exist 674 r := 0 675 h.To = b1 676 for _, t := range a[b2] { 677 if t == h { 678 r++ 679 } 680 } 681 if r < n { 682 n = r 683 } 684 } 685 } 686 } 687 // verify matching edges are available in supergraph 688 m := 0 689 h := Half{e.N2, l} 690 for _, t := range (*s.Super).LabeledAdjacencyList[e.N1] { 691 if t == h { 692 if m == n { 693 goto r // arc match after all existing arcs matched 694 } 695 m++ 696 } 697 } 698 return errors.New("edge not available in supergraph") 699r: 700 if e.N1 != e.N2 { 701 // verify reciprocal arcs 702 m = 0 703 h.To = e.N1 704 for _, t := range (*s.Super).LabeledAdjacencyList[e.N2] { 705 if t == h { 706 if m == n { 707 goto good 708 } 709 m++ 710 } 711 } 712 return errors.New("edge not available in supergraph") 713 } 714good: 715 // matched enough edges. nodes can finally 716 // be added as needed and then the edge can be added. 717 n1 := s.AddNode(e.N1) 718 n2 := s.AddNode(e.N2) 719 s.LabeledUndirected.AddEdge(Edge{n1, n2}, l) 720 return nil // success 721} 722 723// utility function called from all of the InduceList methods. 724func mapList(l []NI) (sub map[NI]NI, sup []NI) { 725 sub = map[NI]NI{} 726 // one pass to collect unique NIs 727 for _, p := range l { 728 sub[NI(p)] = -1 729 } 730 if len(sub) == len(l) { // NIs in l are unique 731 sup = append([]NI{}, l...) // just copy them 732 for b, p := range l { 733 sub[p] = NI(b) // and fill in map 734 } 735 } else { // NIs in l not unique 736 sup = make([]NI, 0, len(sub)) 737 for _, p := range l { // preserve ordering of first occurrences in l 738 if sub[p] < 0 { 739 sub[p] = NI(len(sup)) 740 sup = append(sup, p) 741 } 742 } 743 } 744 return 745} 746 747// utility function called from all of the InduceBits methods. 748func mapBits(t bits.Bits) (sub map[NI]NI, sup []NI) { 749 sup = make([]NI, 0, t.OnesCount()) 750 sub = make(map[NI]NI, cap(sup)) 751 t.IterateOnes(func(n int) bool { 752 sub[NI(n)] = NI(len(sup)) 753 sup = append(sup, NI(n)) 754 return true 755 }) 756 return 757} 758 759// OrderMap formats maps for testable examples. 760// 761// OrderMap provides simple, no-frills formatting of maps in sorted order, 762// convenient in some cases for output of testable examples. 763func OrderMap(m interface{}) string { 764 // in particular exclude slices, which template would happily accept but 765 // which would probably represent a coding mistake 766 if reflect.TypeOf(m).Kind() != reflect.Map { 767 panic("not a map") 768 } 769 t := template.Must(template.New("").Parse( 770 `map[{{range $k, $v := .}}{{$k}}:{{$v}} {{end}}]`)) 771 var b bytes.Buffer 772 if err := t.Execute(&b, m); err != nil { 773 panic(err) 774 } 775 if bytes.HasSuffix(b.Bytes(), []byte(" ]")) { 776 b.Truncate(b.Len() - 2) 777 b.WriteByte(']') 778 } 779 return b.String() 780} 781