Skip to content

read-only induced subgraph #39

Description

@IanChenUIUC

Motivation

Currently, the only way to build induced subgraphs in Icebug is via NetworKit::GraphTools::subgraphFromNodes. The implementation initializes a GraphW object and adds edges incrementally.

I think it would fit with the existing Icebug framework to have a memory-efficient InducedSubgraphView that is read-only and computes neighbors on demand, similar to the CoarsenedGraphView. Ideally, it would be a subclass of Graph, so that Algorithms can run on induced subgraphs. A realize function or similar can be used to copy it into a GraphR or GraphW.

Proposed API

import networkit as nk


g = build_demo_graph()
subg_view = nk.GraphTools.subgraphViewFromNodes(g, {0, 1, 2, 3})

cores = nk.centrality.CoreDecomposition(subg_view) # can run Algorithms on subgraph views
cores.run()

subg = subg_view.realize() # same as nk.GraphTools.subgraphFromNodes(g, {0, 1, 2, 3}, compact=False)

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions