2086396149

Build # 2086396149

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/<a class="double-link" href="https://git"><a class=hub.com/metagraph-dev/graphblas-algorithms/commit/122d8f90a96acb7725416f048a64e55174fd107f">122d8f90a">&lt;a href=&quot;https://github.com/metagraph-dev/graphblas-algorithms/commit/</a><a class="double-link" href="https://github.com/metagraph-dev/graphblas-algorithms/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/metagraph-dev/graphblas-algorithms/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/metagraph-dev/graphblas-algorithms/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/metagraph-dev/graphblas-algorithms/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/metagraph-dev/graphblas-algorithms/commit/122d8f90a96acb7725416f048a64e55174fd107f">122d8f90a</a><a href="https://github.com/metagraph-dev/graphblas-algorithms/commit/122d8f90a96acb7725416f048a64e55174fd107f">&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/&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/&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/122d8f90a96acb7725416f048a64e55174fd107f&quot;&gt;122d8f90a&lt;/a&gt;&lt;a href=&quot;https://github.com/metagraph-dev/graphblas-algorithms/commit/122d8f90a96acb7725416f048a64e55174fd107f&quot;&gt;&amp;quot;&amp;gt;&amp;amp;lt;a href=&amp;amp;quot;https://github.com/metagraph-dev/graphblas-algorithms/commit/&amp;lt;/a&amp;gt;&amp;lt;a... (continued)

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

Run Details

42 of 48 branches covered (87.5%)

Branch coverage included in aggregate %.

90 of 97 new or added lines in 4 files covered. (92.78%)

92 of 99 relevant lines covered (92.93%)

8.36 hits per line

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

90.0

/graphblas_algorithms/link_analysis.py

from collections import OrderedDict
from warnings import warn

import networkx as nx
from grblas import Matrix, Vector, binary, monoid, 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
        S *= A.reduce_scalar(monoid.any)
        # S *= A.ss.iso_value  # This would be nice to have
        semiring = plus_first
    else:
        semiring = plus_times

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

metagraph-dev / graphblas-algorithms / 2086396149

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