I have a function that I’m running on subgraphs. It is effectively a
bread-first outwards search for all paths from the originating vertex. It
assigns probabilities to each of the end-points, which are then used for
computing a type of index.
In terms of speed, I’ve wondered about three things:
1 - Whether it would be faster to adapt one of the existing graph-tool search
algorithms and find a way to assign probabilities from the results…
2 - Whether there are ways to more speedily implement this algorithm through
rejigging the algorithm;
3 - And, whether implementing through Cython may provide speedups.
Regarding #1, I’ve looked at using the built-in breadth-first search, but I
haven’t yet figured out how to use the visitor object to create the list of
probabilities. Though will try to take a closer look at this sometime soon.
Regarding #3, I’ve looked at a Cython implementation, but it doesn’t appear to
provide any significant speedups. I suspect this is because the function uses
graph and vertex objects and I’m assuming that Cython doesn’t have the capacity
to efficiently implement these.
Any pointers would be appreciated. Thanks.
Here is the function: (Currently a .pyx file for Cython)
from scipy.stats import entropy
def nodeOutProb(g, v):
# Calculates probabilities of all possible routes from node within cutoff
distance
visitedNodes = set()
claimedEdges = set()
branches = {}
probabilities = []
# add origin
cdef float o = 1.0
branches[v] = o # add starting node with starting probability
visitedNodes.add(v) # add starting node to visited set
cdef float r, cV, newVal
# start iterating through branches...adding and removing as you go
while len(branches) > 0:
for key, val in branches.items():
newVal = 0.0
newEdges = []
for e in key.all_edges():
if e not in claimedEdges:
newVal += 1
claimedEdges.add(e)
newEdges.append(e)
if newVal == 0:
probabilities.append(1/val)
else:
cV = newVal * val
for n in key.all_neighbours():
if n not in visitedNodes:
visitedNodes.add(n)
branches[n] = cV
elif g.edge(key, n) in newEdges:
probabilities.append(1/cV)
del branches[key]
return entropy(probabilities, base=2)_______________________________________________
graph-tool mailing list
[email protected]
http://lists.skewed.de/mailman/listinfo/graph-tool
