RemoveRedundantEdges removes residual edges if the destination can be reached through another path. This is done to simplify the graph while preserving connectivity.
()
| 897 | // be reached through another path. This is done to simplify the graph |
| 898 | // while preserving connectivity. |
| 899 | func (g *Graph) RemoveRedundantEdges() { |
| 900 | // Walk the nodes and outgoing edges in reverse order to prefer |
| 901 | // removing edges with the lowest weight. |
| 902 | for i := len(g.Nodes); i > 0; i-- { |
| 903 | n := g.Nodes[i-1] |
| 904 | in := n.In.Sort() |
| 905 | for j := len(in); j > 0; j-- { |
| 906 | e := in[j-1] |
| 907 | if !e.Residual { |
| 908 | // Do not remove edges heavier than a non-residual edge, to |
| 909 | // avoid potential confusion. |
| 910 | break |
| 911 | } |
| 912 | if isRedundantEdge(e) { |
| 913 | delete(e.Src.Out, e.Dest) |
| 914 | delete(e.Dest.In, e.Src) |
| 915 | } |
| 916 | } |
| 917 | } |
| 918 | } |
| 919 | |
| 920 | // isRedundantEdge determines if there is a path that allows e.Src |
| 921 | // to reach e.Dest after removing e. |
no test coverage detected