lightningnetwork / lnd / 13980275562

func (s *stack) push(v int) {

        s.stack = append(s.stack, v)

}

func (s *stack) top() int {

        return s.stack[len(s.stack)-1]

}

func (s *stack) pop() {

        s.stack = s.stack[:len(s.stack)-1]

}

func (s *stack) empty() bool {

        return len(s.stack) == 0

}

func (q *queue) push(v int) {

        q.queue = append(q.queue, v)

}

func (q *queue) front() int {

        return q.queue[0]

}

func (q *queue) pop() {

        q.queue = q.queue[1:]

}

func (q *queue) empty() bool {

        return len(q.queue) == 0

}

                return nil, fmt.Errorf("workers must be positive")

        }

func (bc *BetweennessCentrality) Name() string {

        return "betweenness_centrality"

}

func betweennessCentrality(g *SimpleGraph, s int, centrality []float64) {

        // pred[w] is the list of nodes that immediately precede w on a

        // shortest path from s to t for each node t.

        pred := make([][]int, len(g.Nodes))

        // sigma[t] is the number of shortest paths between nodes s and t

        // for each node t.

        sigma := make([]int, len(g.Nodes))

        sigma[s] = 1

        // dist[t] holds the distance between s and t for each node t.

        // We initialize this to -1 (meaning infinity) for each t != s.

        dist := make([]int, len(g.Nodes))

        for i := range dist {

                dist[i] = -1

        }

        dist[s] = 0

        var (

                st stack

                q  queue

        )

        q.push(s)

        // BFS to calculate the shortest paths (sigma and pred)

        // from s to t for each node t.

        for !q.empty() {

                v := q.front()

                q.pop()

                st.push(v)

                for _, w := range g.Adj[v] {

                        // If distance from s to w is infinity (-1)

                        // then set it and enqueue w.

                        if dist[w] < 0 {

                                dist[w] = dist[v] + 1

                                q.push(w)

                        }

                        if dist[w] == dist[v]+1 {

                                sigma[w] += sigma[v]

                                pred[w] = append(pred[w], v)

                        }

        delta := make([]float64, len(g.Nodes))

        for !st.empty() {

                w := st.top()

                st.pop()

                // pred[w] is the list of nodes that immediately precede w on a

                // shortest path from s.

                for _, v := range pred[w] {

                        // Update delta using Brandes' equation.

                        delta[v] += (float64(sigma[v]) / float64(sigma[w])) * (1.0 + delta[w])

                }

                if w != s {

                        // As noted above centrality is simply the sum

                        // of delta[w] for each w != s.

                        centrality[w] += delta[w]

                }

func (bc *BetweennessCentrality) Refresh(graph ChannelGraph) error {

        cache, err := NewSimpleGraph(graph)

        if err != nil {

                return err

        }

        var wg sync.WaitGroup

        work := make(chan int)

        partials := make(chan []float64, bc.workers)

        // Each worker will compute a partial result.

        // This partial result is a sum of centrality updates

        // on roughly N / workers nodes.

        worker := func() {

                defer wg.Done()

                partial := make([]float64, len(cache.Nodes))

                // Consume the next node, update centrality

                // parital to avoid unnecessary synchronization.

                for node := range work {

                        betweennessCentrality(cache, node, partial)

                }

                partials <- partial

        wg.Add(bc.workers)

        for i := 0; i < bc.workers; i++ {

                go worker()

        }

        for node := range cache.Nodes {

                work <- node

        }

        close(work)

        wg.Wait()

        close(partials)

        // Collect and sum partials for final result.

        centrality := make([]float64, len(cache.Nodes))

        for partial := range partials {

                for i := 0; i < len(partial); i++ {

                        centrality[i] += partial[i]

                }

        bc.min = 0

        bc.max = 0

        if len(centrality) > 0 {

                for _, v := range centrality {

                        if v < bc.min {

                                bc.min = v

                        } else if v > bc.max {

                                bc.max = v

                        }

        bc.min /= 2.0

        bc.max /= 2.0

        bc.centrality = make(map[NodeID]float64)

        for u, value := range centrality {

                // Divide by two as this is an undirected graph.

                bc.centrality[cache.Nodes[u]] = value / 2.0

        }

        return nil

func (bc *BetweennessCentrality) GetMetric(normalize bool) map[NodeID]float64 {

        // Normalization factor.

        var z float64

        if (bc.max - bc.min) > 0 {

                z = 1.0 / (bc.max - bc.min)

        }

        centrality := make(map[NodeID]float64)

        for k, v := range bc.centrality {

                if normalize {

                        v = (v - bc.min) * z

                }

                centrality[k] = v

        return centrality