TrimTree trims a Graph in forest form, keeping only the nodes in kept. This will not work correctly if even a single node has multiple parents.
(kept NodePtrSet)
| 477 | // TrimTree trims a Graph in forest form, keeping only the nodes in kept. This |
| 478 | // will not work correctly if even a single node has multiple parents. |
| 479 | func (g *Graph) TrimTree(kept NodePtrSet) { |
| 480 | // Creates a new list of nodes |
| 481 | oldNodes := g.Nodes |
| 482 | g.Nodes = make(Nodes, 0, len(kept)) |
| 483 | |
| 484 | for _, cur := range oldNodes { |
| 485 | // A node may not have multiple parents |
| 486 | if len(cur.In) > 1 { |
| 487 | panic("TrimTree only works on trees") |
| 488 | } |
| 489 | |
| 490 | // If a node should be kept, add it to the new list of nodes |
| 491 | if _, ok := kept[cur]; ok { |
| 492 | g.Nodes = append(g.Nodes, cur) |
| 493 | continue |
| 494 | } |
| 495 | |
| 496 | // If a node has no parents, then delete all of the in edges of its |
| 497 | // children to make them each roots of their own trees. |
| 498 | if len(cur.In) == 0 { |
| 499 | for _, outEdge := range cur.Out { |
| 500 | delete(outEdge.Dest.In, cur) |
| 501 | } |
| 502 | continue |
| 503 | } |
| 504 | |
| 505 | // Get the parent. This works since at this point cur.In must contain only |
| 506 | // one element. |
| 507 | if len(cur.In) != 1 { |
| 508 | panic("Get parent assertion failed. cur.In expected to be of length 1.") |
| 509 | } |
| 510 | var parent *Node |
| 511 | for _, edge := range cur.In { |
| 512 | parent = edge.Src |
| 513 | } |
| 514 | |
| 515 | parentEdgeInline := parent.Out[cur].Inline |
| 516 | |
| 517 | // Remove the edge from the parent to this node |
| 518 | delete(parent.Out, cur) |
| 519 | |
| 520 | // Reconfigure every edge from the current node to now begin at the parent. |
| 521 | for _, outEdge := range cur.Out { |
| 522 | child := outEdge.Dest |
| 523 | |
| 524 | delete(child.In, cur) |
| 525 | child.In[parent] = outEdge |
| 526 | parent.Out[child] = outEdge |
| 527 | |
| 528 | outEdge.Src = parent |
| 529 | outEdge.Residual = true |
| 530 | // If the edge from the parent to the current node and the edge from the |
| 531 | // current node to the child are both inline, then this resulting residual |
| 532 | // edge should also be inline |
| 533 | outEdge.Inline = parentEdgeInline && outEdge.Inline |
| 534 | } |
| 535 | } |
| 536 | g.RemoveRedundantEdges() |