search

pnnl / chgl

Chapel HyperGraph Library (CHGL) - HPC-class Hypergraphs in Chapel
https://pnnl.github.io/chgl/
MIT License
29 stars 8 forks source link

Introduce a more efficient `getToplexes` algorithm #34

Closed LouisJenkinsCS closed 4 years ago

LouisJenkinsCS commented 6 years ago

Currently, computing toplexes is performed in an O(N^2) way. This can be vastly improved by simply determining if we can s-walk from an edge e to e', where s is |e|. This easily identifies edges which are toplexes as those without any edges to s-walk to will be by-definition toplex edges as no other edges share all of the same vertices as it.

One alternative that @marcinz suggested was to make s=1 and then segment edges into edges that were toplexes and those that are not. This definitely is an optimization as duplicate work can be avoided since we prune off searches for edges that can easily be determined by a toplex edge to be non-toplexes.

LouisJenkinsCS commented 6 years ago

This can then be used to implement a collapseToToplex style of graph for faster DNS data.

LouisJenkinsCS commented 6 years ago

As well, collapseToToplex can replace collapseEdges since it will be able to remove duplicates in a more efficient way than collapseEdges will.

github-actions[bot] commented 4 years ago

This issue is stale and should either be closed or eventually resolved.