Graph Types/Classes in Python

[BradReesWork]

cuGraph needs to expand its list of graph types to better capture and support the fully range of graph analytics. Various graph types require different processing, and having well defined classes helps control and ensure accurate processing and analytical results. cuGraph currently supports a single data structure, called Graph, that is used for every possible graph problem. Some of the issues are:

• Some methods are only for one graph type, with requires a lot of status flag checking
• Some graph types require different input parameters

Any refactoring that results in user-facing changes needs to include a Deprecation Warning for at least one release before the breaking API change is finalized in the next release.

Class	Directed & Undirected	Self-loops Allowed	Parallel edges Allowed	Isolated vertices Allowed	Distributed-capable	Batch-capable	Release
Graph	Yes	Yes	No	Yes	Yes	Yes
MultiGraph	Yes	Yes	Yes	Yes	Yes	?
BipartiteGraph	Yes	Yes	Yes	Yes	Yes	?
HyperGraph	Yes	Yes	Yes	Yes	Yes	?
Tree	Yes	No	No	No	Yes	?
Property	Directed-only	Yes	Yes	Yes	?	?

Tasks:

• [DOC] Create new Graph Class design  #1384 Design new class inheritance structure
• New Design document
• [ENH] Document which algorithms work on which graph types and formats #1095 Document graph types to algorithms
• new Graph Class, GraphImpl internal class & docs+tests
• Add DiGraph backwards-compat class with DeprecationWarning
• Renumbering: extend in-progress impl and retire current/legacy
• Add new from_edgelist() API & docs+tests
• Add filtering API (remove verts/edges based on lambda) & docs+tests
• Add pruning API (remove: self-loops, isolated verts, sinks, verts based on degree, explicit vert/edge) & docs+tests
• Add updating API (update weights based on lambda) & docs+tests
• Add insert API (add vert/edge) & docs+tests
• Add compat module for CuPy & docs+test refactoring
• Add compat module for NetworkX & docs+test refactoring
• Add compat module for SciPy/Pandas (if necessary) & docs+test refactoring
• Notebook update based on new classes/APIs
• Blog on new classes, new compat modules, etc.
• Add expert mode APIs (allow user to perform specific graph/algo-prep operations upfront with documented caveats) & docs+tests
• Expert mode notebook
• Blog on expert mode (if applicable)
• Add new MultiGraph Class, internal Impl class if necessary, & docs+tests
• Add Bipartite Graph Class, internal Impl class if necessary, & docs+tests
• Add HyperGraph Class, internal Impl class if necessary, & docs+tests
• Add Tree Class, internal Impl class if necessary, & docs+tests
• Add Forest Class, internal Impl class if necessary, & docs+tests
• Add Property Class, internal Impl class if necessary, & docs+tests
• New classes notebook(s)
• Blog 3 if applicable

Also address:

• [ENH] Replace the legacy graph class with the new graph class. #1207

Related Tasks

Preview Give feedback

1. [ENH] from_cudf_edgelist should support NULL mask for isolated vertices #1372
   improvement +1