"Fossies" - the Fresh Open Source Software Archive

Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/undir.go" (28 May 2021, 8669 Bytes) of package /linux/misc/old/gdrive-2.1.1.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Go source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    1 // Copyright 2014 Sonia Keys
    2 // License MIT: http://opensource.org/licenses/MIT
    3 
    4 package graph
    5 
    6 // undir.go has methods specific to undirected graphs, Undirected and
    7 // LabeledUndirected.
    8 
    9 import "errors"
   10 
   11 // AddEdge adds an edge to a graph.
   12 //
   13 // It can be useful for constructing undirected graphs.
   14 //
   15 // When n1 and n2 are distinct, it adds the arc n1->n2 and the reciprocal
   16 // n2->n1.  When n1 and n2 are the same, it adds a single arc loop.
   17 //
   18 // The pointer receiver allows the method to expand the graph as needed
   19 // to include the values n1 and n2.  If n1 or n2 happen to be greater than
   20 // len(*p) the method does not panic, but simply expands the graph.
   21 func (p *Undirected) AddEdge(n1, n2 NI) {
   22     // Similar code in LabeledAdjacencyList.AddEdge.
   23 
   24     // determine max of the two end points
   25     max := n1
   26     if n2 > max {
   27         max = n2
   28     }
   29     // expand graph if needed, to include both
   30     g := p.AdjacencyList
   31     if int(max) >= len(g) {
   32         p.AdjacencyList = make(AdjacencyList, max+1)
   33         copy(p.AdjacencyList, g)
   34         g = p.AdjacencyList
   35     }
   36     // create one half-arc,
   37     g[n1] = append(g[n1], n2)
   38     // and except for loops, create the reciprocal
   39     if n1 != n2 {
   40         g[n2] = append(g[n2], n1)
   41     }
   42 }
   43 
   44 // EulerianCycleD for undirected graphs is a bit of an experiment.
   45 //
   46 // It is about the same as the directed version, but modified for an undirected
   47 // multigraph.
   48 //
   49 // Parameter m in this case must be the size of the undirected graph -- the
   50 // number of edges.  Use Undirected.Size if the size is unknown.
   51 //
   52 // It works, but contains an extra loop that I think spoils the time
   53 // complexity.  Probably still pretty fast in practice, but a different
   54 // graph representation might be better.
   55 func (g Undirected) EulerianCycleD(m int) ([]NI, error) {
   56     if len(g.AdjacencyList) == 0 {
   57         return nil, nil
   58     }
   59     e := newEulerian(g.AdjacencyList, m)
   60     for e.s >= 0 {
   61         v := e.top()
   62         e.pushUndir() // call modified method
   63         if e.top() != v {
   64             return nil, errors.New("not balanced")
   65         }
   66         e.keep()
   67     }
   68     if !e.uv.Zero() {
   69         return nil, errors.New("not strongly connected")
   70     }
   71     return e.p, nil
   72 }
   73 
   74 // TarjanBiconnectedComponents decomposes a graph into maximal biconnected
   75 // components, components for which if any node were removed the component
   76 // would remain connected.
   77 //
   78 // The receiver g must be a simple graph.  The method calls the emit argument
   79 // for each component identified, as long as emit returns true.  If emit
   80 // returns false, TarjanBiconnectedComponents returns immediately.
   81 //
   82 // See also the eqivalent labeled TarjanBiconnectedComponents.
   83 func (g Undirected) TarjanBiconnectedComponents(emit func([]Edge) bool) {
   84     // Implemented closely to pseudocode in "Depth-first search and linear
   85     // graph algorithms", Robert Tarjan, SIAM J. Comput. Vol. 1, No. 2,
   86     // June 1972.
   87     //
   88     // Note Tarjan's "adjacency structure" is graph.AdjacencyList,
   89     // His "adjacency list" is an element of a graph.AdjacencyList, also
   90     // termed a "to-list", "neighbor list", or "child list."
   91     number := make([]int, len(g.AdjacencyList))
   92     lowpt := make([]int, len(g.AdjacencyList))
   93     var stack []Edge
   94     var i int
   95     var biconnect func(NI, NI) bool
   96     biconnect = func(v, u NI) bool {
   97         i++
   98         number[v] = i
   99         lowpt[v] = i
  100         for _, w := range g.AdjacencyList[v] {
  101             if number[w] == 0 {
  102                 stack = append(stack, Edge{v, w})
  103                 if !biconnect(w, v) {
  104                     return false
  105                 }
  106                 if lowpt[w] < lowpt[v] {
  107                     lowpt[v] = lowpt[w]
  108                 }
  109                 if lowpt[w] >= number[v] {
  110                     var bcc []Edge
  111                     top := len(stack) - 1
  112                     for number[stack[top].N1] >= number[w] {
  113                         bcc = append(bcc, stack[top])
  114                         stack = stack[:top]
  115                         top--
  116                     }
  117                     bcc = append(bcc, stack[top])
  118                     stack = stack[:top]
  119                     top--
  120                     if !emit(bcc) {
  121                         return false
  122                     }
  123                 }
  124             } else if number[w] < number[v] && w != u {
  125                 stack = append(stack, Edge{v, w})
  126                 if number[w] < lowpt[v] {
  127                     lowpt[v] = number[w]
  128                 }
  129             }
  130         }
  131         return true
  132     }
  133     for w := range g.AdjacencyList {
  134         if number[w] == 0 && !biconnect(NI(w), 0) {
  135             return
  136         }
  137     }
  138 }
  139 
  140 /* half-baked.  Read the 72 paper.  Maybe revisit at some point.
  141 type BiconnectedComponents struct {
  142     Graph  AdjacencyList
  143     Start  int
  144     Cuts   big.Int // bitmap of node cuts
  145     From   []int   // from-tree
  146     Leaves []int   // leaves of from-tree
  147 }
  148 
  149 func NewBiconnectedComponents(g Undirected) *BiconnectedComponents {
  150     return &BiconnectedComponents{
  151         Graph: g,
  152         From:  make([]int, len(g)),
  153     }
  154 }
  155 
  156 func (b *BiconnectedComponents) Find(start int) {
  157     g := b.Graph
  158     depth := make([]int, len(g))
  159     low := make([]int, len(g))
  160     // reset from any previous run
  161     b.Cuts.SetInt64(0)
  162     bf := b.From
  163     for n := range bf {
  164         bf[n] = -1
  165     }
  166     b.Leaves = b.Leaves[:0]
  167     d := 1 // depth. d > 0 means visited
  168     depth[start] = d
  169     low[start] = d
  170     d++
  171     var df func(int, int)
  172     df = func(from, n int) {
  173         bf[n] = from
  174         depth[n] = d
  175         dn := d
  176         l := d
  177         d++
  178         cut := false
  179         leaf := true
  180         for _, nb := range g[n] {
  181             if depth[nb] == 0 {
  182                 leaf = false
  183                 df(n, nb)
  184                 if low[nb] < l {
  185                     l = low[nb]
  186                 }
  187                 if low[nb] >= dn {
  188                     cut = true
  189                 }
  190             } else if nb != from && depth[nb] < l {
  191                 l = depth[nb]
  192             }
  193         }
  194         low[n] = l
  195         if cut {
  196             b.Cuts.SetBit(&b.Cuts, n, 1)
  197         }
  198         if leaf {
  199             b.Leaves = append(b.Leaves, n)
  200         }
  201         d--
  202     }
  203     nbs := g[start]
  204     if len(nbs) == 0 {
  205         return
  206     }
  207     df(start, nbs[0])
  208     var rc uint
  209     for _, nb := range nbs[1:] {
  210         if depth[nb] == 0 {
  211             rc = 1
  212             df(start, nb)
  213         }
  214     }
  215     b.Cuts.SetBit(&b.Cuts, start, rc)
  216     return
  217 }
  218 */
  219 
  220 // AddEdge adds an edge to a labeled graph.
  221 //
  222 // It can be useful for constructing undirected graphs.
  223 //
  224 // When n1 and n2 are distinct, it adds the arc n1->n2 and the reciprocal
  225 // n2->n1.  When n1 and n2 are the same, it adds a single arc loop.
  226 //
  227 // If the edge already exists in *p, a parallel edge is added.
  228 //
  229 // The pointer receiver allows the method to expand the graph as needed
  230 // to include the values n1 and n2.  If n1 or n2 happen to be greater than
  231 // len(*p) the method does not panic, but simply expands the graph.
  232 func (p *LabeledUndirected) AddEdge(e Edge, l LI) {
  233     // Similar code in AdjacencyList.AddEdge.
  234 
  235     // determine max of the two end points
  236     max := e.N1
  237     if e.N2 > max {
  238         max = e.N2
  239     }
  240     // expand graph if needed, to include both
  241     g := p.LabeledAdjacencyList
  242     if max >= NI(len(g)) {
  243         p.LabeledAdjacencyList = make(LabeledAdjacencyList, max+1)
  244         copy(p.LabeledAdjacencyList, g)
  245         g = p.LabeledAdjacencyList
  246     }
  247     // create one half-arc,
  248     g[e.N1] = append(g[e.N1], Half{To: e.N2, Label: l})
  249     // and except for loops, create the reciprocal
  250     if e.N1 != e.N2 {
  251         g[e.N2] = append(g[e.N2], Half{To: e.N1, Label: l})
  252     }
  253 }
  254 
  255 // TarjanBiconnectedComponents decomposes a graph into maximal biconnected
  256 // components, components for which if any node were removed the component
  257 // would remain connected.
  258 //
  259 // The receiver g must be a simple graph.  The method calls the emit argument
  260 // for each component identified, as long as emit returns true.  If emit
  261 // returns false, TarjanBiconnectedComponents returns immediately.
  262 //
  263 // See also the eqivalent unlabeled TarjanBiconnectedComponents.
  264 func (g LabeledUndirected) TarjanBiconnectedComponents(emit func([]LabeledEdge) bool) {
  265     // Implemented closely to pseudocode in "Depth-first search and linear
  266     // graph algorithms", Robert Tarjan, SIAM J. Comput. Vol. 1, No. 2,
  267     // June 1972.
  268     //
  269     // Note Tarjan's "adjacency structure" is graph.AdjacencyList,
  270     // His "adjacency list" is an element of a graph.AdjacencyList, also
  271     // termed a "to-list", "neighbor list", or "child list."
  272     //
  273     // Nearly identical code in undir.go.
  274     number := make([]int, len(g.LabeledAdjacencyList))
  275     lowpt := make([]int, len(g.LabeledAdjacencyList))
  276     var stack []LabeledEdge
  277     var i int
  278     var biconnect func(NI, NI) bool
  279     biconnect = func(v, u NI) bool {
  280         i++
  281         number[v] = i
  282         lowpt[v] = i
  283         for _, w := range g.LabeledAdjacencyList[v] {
  284             if number[w.To] == 0 {
  285                 stack = append(stack, LabeledEdge{Edge{v, w.To}, w.Label})
  286                 if !biconnect(w.To, v) {
  287                     return false
  288                 }
  289                 if lowpt[w.To] < lowpt[v] {
  290                     lowpt[v] = lowpt[w.To]
  291                 }
  292                 if lowpt[w.To] >= number[v] {
  293                     var bcc []LabeledEdge
  294                     top := len(stack) - 1
  295                     for number[stack[top].N1] >= number[w.To] {
  296                         bcc = append(bcc, stack[top])
  297                         stack = stack[:top]
  298                         top--
  299                     }
  300                     bcc = append(bcc, stack[top])
  301                     stack = stack[:top]
  302                     top--
  303                     if !emit(bcc) {
  304                         return false
  305                     }
  306                 }
  307             } else if number[w.To] < number[v] && w.To != u {
  308                 stack = append(stack, LabeledEdge{Edge{v, w.To}, w.Label})
  309                 if number[w.To] < lowpt[v] {
  310                     lowpt[v] = number[w.To]
  311                 }
  312             }
  313         }
  314         return true
  315     }
  316     for w := range g.LabeledAdjacencyList {
  317         if number[w] == 0 && !biconnect(NI(w), 0) {
  318             return
  319         }
  320     }
  321 }