2091046568

Build # 2091046568

Build Type

github

Committed by GitHub

Commit Message

<a href="https://github.com/metagraph-dev/graphblas-algorithms/commit/<a class=hub.com/metagraph-dev/graphblas-algorithms/commit/<a class="double-link" href="https://git"><a class=hub.com/metagraph-dev/graphblas-algorithms/commit/<a class="double-link" href="https://git"><a class=hub.com/metagraph-dev/graphblas-algorithms/commit/f285432272baa69b5d17a3008418a78749b8d5fc">f28543227<a href="https://github.com/metagraph-dev/graphblas-algorithms/commit/f285432272baa69b5d17a3008418a78749b8d5fc">&quot;&gt;&amp;lt;a href=&amp;quot;https://github.com/metagraph-dev/graphblas-algorithms/commit/&lt;/a&gt;&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/metagraph-dev/graphblas-algorithms/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/metagraph-dev/graphblas-algorithms/commit/f285432272baa69b5d17a3008418a78749b8d5fc&quot;&gt;f28543227&lt;/a&gt;&lt;a href=&quot;https://github.com/metagraph-dev/graphblas-algorithms/commit/f285432272baa69b5d17a3008418a78749b8d5fc&quot;&gt;&amp;lt;a href=&amp;quot;https://github.com/metagraph-dev/graphblas-algorithms/commit/f285432272baa69b5d17a3008418a787&lt;/a&gt;49b8d5fc&quot;&gt;&amp;quot;&gt;Merge &lt;/a&gt;&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/metagraph-dev/graphblas-algorithms/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/metagraph-dev/graphblas-algorithms/commit/<a class="double-link" href="https://github.com/metagraph-dev/graphblas-algorithms/commit/85d535b8b3f2afc58abb4dd764366fdac717457e">85d535b8b</a><a href="https://github.com/metagraph-dev/graphblas-algorithms/commit/f285432272baa69b5d17a3008418a78749b8d5fc">&amp;quot;&amp;gt;85d535b8b&amp;lt;/a&amp;gt;&amp;quot;&amp;gt;85d535b8b&amp;lt;/a&amp;gt;&amp;lt;a href=&amp;quot;https://github.com/metagraph-dev/graphblas-algorithms/commit/f285432272baa69b5d17a3008418a78749b8d&lt;/a&gt;5fc&quot;&gt; into &lt;/a&gt;&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/metagraph-dev/graphblas-algorithms/commit/<a class="double-link" href="https://github.com/metagraph-dev/graphblas-algorithms/commit/c544c79b5">c544c79b5">c544c79b5</a>

Pull Request Pull Request #1: Add initial attempt at pagerank with hacky tests

Run Details

44 of 50 branches covered (88.0%)

Branch coverage included in aggregate %.

93 of 99 new or added lines in 4 files covered. (93.94%)

95 of 101 relevant lines covered (94.06%)

8.47 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

91.04

/graphblas_algorithms/link_analysis.py

from collections import OrderedDict
from warnings import warn

import grblas as gb
import networkx as nx
from grblas import Vector, binary, unary
from grblas.semiring import plus_first, plus_times


def pagerank_core(
    A,
    alpha=0.85,
    personalization=None,
    max_iter=100,
    tol=1e-06,
    nstart=None,
    dangling=None,
    row_degrees=None,
    name="pagerank",
):
    N = A.nrows
    if A.nvals == 0:
        return Vector.new(float, N, name=name)

    # Initial vector
    x = Vector.new(float, N, name="x")
    if nstart is None:
        x[:] = 1.0 / N
    else:
        denom = nstart.reduce(allow_empty=False).value
        if denom == 0:
            raise ZeroDivisionError()
        x << nstart / denom

    # Personalization vector or scalar
    if personalization is None:
        p = 1.0 / N
    else:
        denom = personalization.reduce(allow_empty=False).value
        if denom == 0:
            raise ZeroDivisionError()
        p = (personalization / denom).new(name="p")

    # Inverse of row_degrees
    # Fold alpha constant into S
    if row_degrees is None:
        S = A.reduce_rowwise().new(float, name="S")
        S << alpha / S
    else:
        S = (alpha / row_degrees).new(name="S")

    if A.ss.is_iso:
        # Fold iso-value of A into S
        # This lets us use the plus_first semiring, which is faster
        iso_value = A.ss.iso_value
        if iso_value != 1:
            S *= iso_value
        semiring = plus_first[float]
    else:
        semiring = plus_times[float]

    is_dangling = S.nvals < N
    if is_dangling:
        dangling_mask = Vector.new(float, N, name="dangling_mask")
        dangling_mask(mask=~S.S) << 1.0
        # Fold alpha constant into dangling_weights (or dangling_mask)
        if dangling is not None:
            dangling_weights = (alpha / dangling.reduce(allow_empty=False).value * dangling).new(
                name="dangling_weights"
            )
        elif personalization is None:
            # Fast case (and common case); is iso-valued
            dangling_mask(mask=dangling_mask.S) << alpha * p
        else:
            dangling_weights = (alpha * p).new(name="dangling_weights")

    # Fold constant into p
    p *= 1 - alpha

    # Power iteration: make up to max_iter iterations
    xprev = Vector.new(float, N, name="x_prev")
    w = Vector.new(float, N, name="w")
    for _ in range(max_iter):
        xprev, x = x, xprev

        # x << alpha * ((xprev * S) @ A + "dangling_weights") + (1 - alpha) * p
        x << p
        if is_dangling:
            if dangling is None and personalization is None:
                # Fast case: add a scalar; x is still iso-valued (b/c p is also scalar)
                x += xprev @ dangling_mask
            else:
                # Add a vector
                x += plus_first(xprev @ dangling_mask) * dangling_weights
        w << xprev * S
        x += semiring(w @ A)  # plus_first if A.ss.is_iso else plus_times

        # Check convergence, l1 norm: err = sum(abs(xprev - x))
        xprev << binary.minus(xprev | x, require_monoid=False)
        xprev << unary.abs(xprev)
        err = xprev.reduce().value
        if err < N * tol:
            x.name = name
            return x
    raise nx.PowerIterationFailedConvergence(max_iter)


def pagerank(
    G,
    alpha=0.85,
    personalization=None,
    max_iter=100,
    tol=1e-06,
    nstart=None,
    weight="weight",
    dangling=None,
):
    warn("", DeprecationWarning, stacklevel=2)
    N = len(G)
    if N == 0:
        return {}
    node_ids = OrderedDict((k, i) for i, k in enumerate(G))
    A = gb.io.from_networkx(G, nodelist=node_ids, weight=weight, dtype=float)

    x = p = dangling_weights = None
    # Initial vector (we'll normalize later)
    if nstart is not None:
        indices, values = zip(*((node_ids[key], val) for key, val in nstart.items()))
        x = Vector.from_values(indices, values, size=N, dtype=float, name="nstart")
    # Personalization vector (we'll normalize later)
    if personalization is not None:
        indices, values = zip(*((node_ids[key], val) for key, val in personalization.items()))
        p = Vector.from_values(indices, values, size=N, dtype=float, name="personalization")
    # Dangling nodes (we'll normalize later)
    row_degrees = A.reduce_rowwise().new(name="row_degrees")
    if dangling is not None:
        if row_degrees.nvals < N:  # is_dangling
            indices, values = zip(*((node_ids[key], val) for key, val in dangling.items()))
            dangling_weights = Vector.from_values(
                indices, values, size=N, dtype=float, name="dangling"
            )
    result = pagerank_core(
        A,
        alpha=alpha,
        personalization=p,
        max_iter=max_iter,
        tol=tol,
        nstart=x,
        dangling=dangling_weights,
        row_degrees=row_degrees,
    )
    if result.nvals != N:
        # Not likely, but fill with 0 just in case
        result(mask=~result.S) << 0
    return dict(zip(node_ids, result.to_values()[1]))

1	from collections import OrderedDict	9✔
2	from warnings import warn	9✔
3
4	import grblas as gb	9✔
5	import networkx as nx	9✔
6	from grblas import Vector, binary, unary	9✔
7	from grblas.semiring import plus_first, plus_times	9✔
8
9
10	def pagerank_core(	9✔
11	A,
12	alpha=0.85,
13	personalization=None,
14	max_iter=100,
15	tol=1e-06,
16	nstart=None,
17	dangling=None,
18	row_degrees=None,
19	name="pagerank",
20	):
21	N = A.nrows	9✔
22	if A.nvals == 0:	9!
NEW 23	return Vector.new(float, N, name=name)	×
24
25	# Initial vector
26	x = Vector.new(float, N, name="x")	9✔
27	if nstart is None:	9✔
28	x[:] = 1.0 / N	9✔
29	else:
30	denom = nstart.reduce(allow_empty=False).value	9✔
31	if denom == 0:	9!
NEW 32	raise ZeroDivisionError()	×
33	x << nstart / denom	9✔
34
35	# Personalization vector or scalar
36	if personalization is None:	9✔
37	p = 1.0 / N	9✔
38	else:
39	denom = personalization.reduce(allow_empty=False).value	9✔
40	if denom == 0:	9✔
41	raise ZeroDivisionError()	9✔
42	p = (personalization / denom).new(name="p")	9✔
43
44	# Inverse of row_degrees
45	# Fold alpha constant into S
46	if row_degrees is None:	9!
NEW 47	S = A.reduce_rowwise().new(float, name="S")	×
NEW 48	S << alpha / S	×
49	else:
50	S = (alpha / row_degrees).new(name="S")	9✔
51
52	if A.ss.is_iso:	9✔
53	# Fold iso-value of A into S
54	# This lets us use the plus_first semiring, which is faster
55	iso_value = A.ss.iso_value	9✔
56	if iso_value != 1:	9!
NEW 57	S *= iso_value	×
58	semiring = plus_first[float]	9✔
59	else:
60	semiring = plus_times[float]	9✔
61
62	is_dangling = S.nvals < N	9✔
63	if is_dangling:	9✔
64	dangling_mask = Vector.new(float, N, name="dangling_mask")	9✔
65	dangling_mask(mask=~S.S) << 1.0	9✔
66	# Fold alpha constant into dangling_weights (or dangling_mask)
67	if dangling is not None:	9✔
68	dangling_weights = (alpha / dangling.reduce(allow_empty=False).value * dangling).new(	9✔
69	name="dangling_weights"
70	)
71	elif personalization is None:	9✔
72	# Fast case (and common case); is iso-valued
73	dangling_mask(mask=dangling_mask.S) << alpha * p	9✔
74	else:
75	dangling_weights = (alpha * p).new(name="dangling_weights")	9✔
76
77	# Fold constant into p
78	p *= 1 - alpha	9✔
79
80	# Power iteration: make up to max_iter iterations
81	xprev = Vector.new(float, N, name="x_prev")	9✔
82	w = Vector.new(float, N, name="w")	9✔
83	for _ in range(max_iter):	9✔
84	xprev, x = x, xprev	9✔
85
86	# x << alpha * ((xprev * S) @ A + "dangling_weights") + (1 - alpha) * p
87	x << p	9✔
88	if is_dangling:	9✔
89	if dangling is None and personalization is None:	9✔
90	# Fast case: add a scalar; x is still iso-valued (b/c p is also scalar)
91	x += xprev @ dangling_mask	9✔
92	else:
93	# Add a vector
94	x += plus_first(xprev @ dangling_mask) * dangling_weights	9✔
95	w << xprev * S	9✔
96	x += semiring(w @ A) # plus_first if A.ss.is_iso else plus_times	9✔
97
98	# Check convergence, l1 norm: err = sum(abs(xprev - x))
99	xprev << binary.minus(xprev \| x, require_monoid=False)	9✔
100	xprev << unary.abs(xprev)	9✔
101	err = xprev.reduce().value	9✔
102	if err < N * tol:	9✔
103	x.name = name	9✔
104	return x	9✔
105	raise nx.PowerIterationFailedConvergence(max_iter)	9✔
106
107
108	def pagerank(	9✔
109	G,
110	alpha=0.85,
111	personalization=None,
112	max_iter=100,
113	tol=1e-06,
114	nstart=None,
115	weight="weight",
116	dangling=None,
117	):
118	warn("", DeprecationWarning, stacklevel=2)	9✔
119	N = len(G)	9✔
120	if N == 0:	9✔
121	return {}	9✔
122	node_ids = OrderedDict((k, i) for i, k in enumerate(G))	9✔
123	A = gb.io.from_networkx(G, nodelist=node_ids, weight=weight, dtype=float)	9✔
124
125	x = p = dangling_weights = None	9✔
126	# Initial vector (we'll normalize later)
127	if nstart is not None:	9✔
128	indices, values = zip(*((node_ids[key], val) for key, val in nstart.items()))	9✔
129	x = Vector.from_values(indices, values, size=N, dtype=float, name="nstart")	9✔
130	# Personalization vector (we'll normalize later)
131	if personalization is not None:	9✔
132	indices, values = zip(*((node_ids[key], val) for key, val in personalization.items()))	9✔
133	p = Vector.from_values(indices, values, size=N, dtype=float, name="personalization")	9✔
134	# Dangling nodes (we'll normalize later)
135	row_degrees = A.reduce_rowwise().new(name="row_degrees")	9✔
136	if dangling is not None:	9✔
137	if row_degrees.nvals < N: # is_dangling	9!
138	indices, values = zip(*((node_ids[key], val) for key, val in dangling.items()))	9✔
139	dangling_weights = Vector.from_values(	9✔
140	indices, values, size=N, dtype=float, name="dangling"
141	)
142	result = pagerank_core(	9✔
143	A,
144	alpha=alpha,
145	personalization=p,
146	max_iter=max_iter,
147	tol=tol,
148	nstart=x,
149	dangling=dangling_weights,
150	row_degrees=row_degrees,
151	)
152	if result.nvals != N:	9!
153	# Not likely, but fill with 0 just in case
NEW 154	result(mask=~result.S) << 0	×
155	return dict(zip(node_ids, result.to_values()[1]))	9✔

metagraph-dev / graphblas-algorithms / 2091046568

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous