Struct ContiguousSubgraph 

pub struct ContiguousSubgraph<G: SwhGraph, N: ContractionBackend, MAPS: MaybeMaps, TIMESTAMPS: MaybeTimestamps, PERSONS: MaybePersons, CONTENTS: MaybeContents, STRINGS: MaybeStrings, LABELNAMES: MaybeLabelNames> { /* private fields */ }

A view over SwhGraph and related traits, that filters out some nodes, and renumbers remaining nodes so that the set of valid nodes becomes a range.

Due to limitations in the Rust type system, properties available on the underlying SwhGraph are not automatically available on ContiguousSubgraph. They need to be explicitly enabled in a builder-like pattern on ContiguousSubgraph using these methods:

• with_maps,
• with_timestamps,
• with_persons,
• with_contents,
• with_strings,
• with_label_names,

Examples

Build a ContiguousSubgraph made of only content and directory nodes:

use dsi_progress_logger::progress_logger;
use swh_graph::properties;
use swh_graph::NodeConstraint;
use swh_graph::graph::SwhGraphWithProperties;
use swh_graph::views::{ContiguousSubgraph, Contraction, Subgraph, ContractionBackend};

fn filesystem_subgraph<G>(graph: &G) -> ContiguousSubgraph<
        Subgraph<&'_ G, impl Fn(usize) -> bool + use<'_, G>, fn(usize, usize) -> bool>,
        impl ContractionBackend,
        properties::NoMaps,
        properties::NoTimestamps,
        properties::NoPersons,
        properties::NoContents,
        properties::NoStrings,
        properties::NoLabelNames,
    >
    where G: SwhGraphWithProperties<Maps: properties::Maps> + Sync {
    let sparse_subgraph = Subgraph::with_node_constraint(graph, "cnt,ori".parse().unwrap());
    ContiguousSubgraph::new_from_noncontiguous_graph(sparse_subgraph)
}

The graph created above is slightly suboptimal, as ContiguousSubgraph wraps a Subgraph, causing Subgraph to add needless overhead by checking that nodes exist, even though ContiguousSubgraph does it too. This should not be noticeable, but if it is an issue, you can skip the Subgraph by manually building a Contraction:

use dsi_progress_logger::progress_logger;
use sux::dict::elias_fano::{EfSeqDict, EliasFanoBuilder};
use swh_graph::properties;
use swh_graph::{NodeType};
use swh_graph::graph::SwhGraphWithProperties;
use swh_graph::views::{ContiguousSubgraph, Contraction, Subgraph, ContractionBackend};

fn filesystem_subgraph<G>(graph: &G) -> ContiguousSubgraph<
        &'_ G,
        EfSeqDict,
        properties::NoMaps,
        properties::NoTimestamps,
        properties::NoPersons,
        properties::NoContents,
        properties::NoStrings,
        properties::NoLabelNames,
    >
    where G: SwhGraphWithProperties<Maps: properties::Maps> {

    // compute exact number of nodes in the subgraph, which is required
    // by EliasFanoBuilder
    let pl = progress_logger!(
        item_name = "node",
        expected_updates = Some(graph.num_nodes()),
    );
    let num_nodes = graph
        .iter_nodes(pl)
        .filter(|&node| match graph.properties().node_type(node) {
            NodeType::Content | NodeType::Directory => true,
            _ => false,
        })
        .count();

    // compute set of nodes in the subgraph
    let mut nodes_efb = EliasFanoBuilder::new(num_nodes, graph.num_nodes());
    for node in 0..graph.num_nodes() {
        match graph.properties().node_type(node) {
            NodeType::Content | NodeType::Directory => nodes_efb.push(node),
            _ => (),
        }
    }
    let contraction = Contraction(nodes_efb.build_with_seq_and_dict());

    // assemble the subgraph
    ContiguousSubgraph::new_from_contraction(graph, contraction)
}

Implementations

impl<G: SwhGraphWithProperties<Contents: OptContents>, N: ContractionBackend, MAPS: MaybeMaps, TIMESTAMPS: MaybeTimestamps, PERSONS: MaybePersons, STRINGS: MaybeStrings, LABELNAMES: MaybeLabelNames> ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, NoContents, STRINGS, LABELNAMES>

pub fn with_contents( self, ) -> ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, ContiguousSubgraphContents<G, N>, STRINGS, LABELNAMES>

Makes OptContents available on this ContiguousSubgraph.

Requires the underlying graph to implement OptContents

impl<G: SwhGraphWithProperties<LabelNames: LabelNames>, N: ContractionBackend, MAPS: MaybeMaps, TIMESTAMPS: MaybeTimestamps, PERSONS: MaybePersons, CONTENTS: MaybeContents, STRINGS: MaybeStrings> ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, NoLabelNames>

pub fn with_label_names( self, ) -> ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, ContiguousSubgraphLabelNames<G, N>>

Makes properties::LabelNames available on this ContiguousSubgraph.

Requires the underlying graph to implement properties::LabelNames.

impl<G: SwhGraphWithProperties<Maps: Maps>, N: ContractionBackend, TIMESTAMPS: MaybeTimestamps, PERSONS: MaybePersons, CONTENTS: MaybeContents, STRINGS: MaybeStrings, LABELNAMES: MaybeLabelNames> ContiguousSubgraph<G, N, NoMaps, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, LABELNAMES>

pub fn with_maps( self, ) -> ContiguousSubgraph<G, N, ContiguousSubgraphMaps<G, N>, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, LABELNAMES>

Makes properties::Maps available on this ContiguousSubgraph.

Requires the underlying graph to implement properties::Maps.

impl<G: SwhGraphWithProperties<Persons: OptPersons>, N: ContractionBackend, MAPS: MaybeMaps, TIMESTAMPS: MaybeTimestamps, CONTENTS: MaybeContents, STRINGS: MaybeStrings, LABELNAMES: MaybeLabelNames> ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, NoPersons, CONTENTS, STRINGS, LABELNAMES>

pub fn with_persons( self, ) -> ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, ContiguousSubgraphPersons<G, N>, CONTENTS, STRINGS, LABELNAMES>

Makes OptPersons available on this ContiguousSubgraph.

Requires the underlying graph to implement OptPersons.

impl<G: SwhGraphWithProperties<Strings: OptStrings>, N: ContractionBackend, MAPS: MaybeMaps, TIMESTAMPS: MaybeTimestamps, PERSONS: MaybePersons, CONTENTS: MaybeContents, LABELNAMES: MaybeLabelNames> ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, NoStrings, LABELNAMES>

pub fn with_strings( self, ) -> ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, ContiguousSubgraphStrings<G, N>, LABELNAMES>

Makes OptStrings available on this ContiguousSubgraph.

Requires the underlying graph to implement OptStrings.

impl<G: SwhGraphWithProperties<Timestamps: OptTimestamps>, N: ContractionBackend, MAPS: MaybeMaps, PERSONS: MaybePersons, CONTENTS: MaybeContents, STRINGS: MaybeStrings, LABELNAMES: MaybeLabelNames> ContiguousSubgraph<G, N, MAPS, NoTimestamps, PERSONS, CONTENTS, STRINGS, LABELNAMES>

pub fn with_timestamps( self, ) -> ContiguousSubgraph<G, N, MAPS, ContiguousSubgraphTimestamps<G, N>, PERSONS, CONTENTS, STRINGS, LABELNAMES>

Makes OptTimestamps available on this ContiguousSubgraph.

Requires the underlying graph to implement OptTimestamps.

impl<G: SwhGraphWithProperties, N: ContractionBackend> ContiguousSubgraph<G, N, NoMaps, NoTimestamps, NoPersons, NoContents, NoStrings, NoLabelNames>

pub fn new_from_contraction(graph: G, contraction: Contraction<N>) -> Self

Creates a new ContiguousSubgraph by keeping only nodes in the Contraction

impl<G: SwhGraph, N: ContractionBackend> ContiguousSubgraph<G, N, NoMaps, NoTimestamps, NoPersons, NoContents, NoStrings, NoLabelNames>

pub fn underlying_graph(&self) -> &G

Returns the graph this graph is a subgraph of

Use Self::contraction to get the mapping between both sets of node ids

pub fn contraction(&self) -> &Contraction<N>

The structure used to match the underlying graph’s node ids with this graph’s node ids

impl<G: SwhGraphWithProperties> ContiguousSubgraph<G, EfSeqDict, NoMaps, NoTimestamps, NoPersons, NoContents, NoStrings, NoLabelNames>

pub fn new_from_noncontiguous_graph(graph: G) -> Self

where G: Sync,

Creates a new ContiguousSubgraph from an existing graph with “holes”.

Trait Implementations

impl<G: SwhBackwardGraph, N: ContractionBackend, MAPS: MaybeMaps, TIMESTAMPS: MaybeTimestamps, PERSONS: MaybePersons, CONTENTS: MaybeContents, STRINGS: MaybeStrings, LABELNAMES: MaybeLabelNames> SwhBackwardGraph for ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, LABELNAMES>

type Predecessors<'succ> = TranslatedSuccessors<'succ, <<G as SwhBackwardGraph>::Predecessors<'succ> as IntoIterator>::IntoIter, N> where Self: 'succ

fn predecessors(&self, node_id: NodeId) -> Self::Predecessors<'_>

Return an IntoIterator over the predecessors of a node.

fn indegree(&self, node_id: NodeId) -> usize

Return the number of predecessors of a node.

impl<G: SwhForwardGraph, N: ContractionBackend, MAPS: MaybeMaps, TIMESTAMPS: MaybeTimestamps, PERSONS: MaybePersons, CONTENTS: MaybeContents, STRINGS: MaybeStrings, LABELNAMES: MaybeLabelNames> SwhForwardGraph for ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, LABELNAMES>

type Successors<'succ> = TranslatedSuccessors<'succ, <<G as SwhForwardGraph>::Successors<'succ> as IntoIterator>::IntoIter, N> where Self: 'succ

fn successors(&self, node_id: NodeId) -> Self::Successors<'_>

Return an IntoIterator over the successors of a node.

fn outdegree(&self, node_id: NodeId) -> usize

Return the number of successors of a node.

impl<G: SwhGraph, N: ContractionBackend, MAPS: MaybeMaps, TIMESTAMPS: MaybeTimestamps, PERSONS: MaybePersons, CONTENTS: MaybeContents, STRINGS: MaybeStrings, LABELNAMES: MaybeLabelNames> SwhGraph for ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, LABELNAMES>

fn path(&self) -> &Path

Return the base path of the graph

fn is_transposed(&self) -> bool

Returns whether the graph is in the ori->snp->rel,rev->dir->cnt direction (with a few dir->rev arcs)

fn num_nodes(&self) -> usize

Return the largest node id in the graph plus one.

fn has_node(&self, node_id: NodeId) -> bool

Returns whether the given node id exists in the graph

fn num_arcs(&self) -> u64

Return the number of arcs in the graph.

fn num_nodes_by_type(&self) -> Result<HashMap<NodeType, usize>>

Returns the number of nodes of each type, if known.

fn num_arcs_by_type(&self) -> Result<HashMap<(NodeType, NodeType), usize>>

Returns the number of arcs of each type, if known.

fn has_arc(&self, src_node_id: NodeId, dst_node_id: NodeId) -> bool

Return whether there is an arc going from src_node_id to dst_node_id.

fn actual_num_nodes(&self) -> Result<usize>

Returns the number of nodes in the graph, if known.

fn iter_nodes<'a>( &'a self, pl: impl ProgressLog + 'a, ) -> impl Iterator<Item = NodeId> + 'a

Returns an iterator on all the nodes

fn par_iter_nodes<'a>( &'a self, pl: impl ConcurrentProgressLog + 'a, ) -> impl ParallelIterator<Item = NodeId> + 'a

where Self: Sync,

Returns a parallel iterator on all the nodes

impl<G: SwhGraphWithProperties, N: ContractionBackend, MAPS: MaybeMaps, TIMESTAMPS: MaybeTimestamps, PERSONS: MaybePersons, CONTENTS: MaybeContents, STRINGS: MaybeStrings, LABELNAMES: MaybeLabelNames> SwhGraphWithProperties for ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, LABELNAMES>

type Maps = MAPS

type Timestamps = TIMESTAMPS

type Persons = PERSONS

type Contents = CONTENTS

type Strings = STRINGS

type LabelNames = LABELNAMES

fn properties( &self, ) -> &SwhGraphProperties<Self::Maps, Self::Timestamps, Self::Persons, Self::Contents, Self::Strings, Self::LabelNames>

impl<G: SwhLabeledBackwardGraph, N: ContractionBackend, MAPS: MaybeMaps, TIMESTAMPS: MaybeTimestamps, PERSONS: MaybePersons, CONTENTS: MaybeContents, STRINGS: MaybeStrings, LABELNAMES: MaybeLabelNames> SwhLabeledBackwardGraph for ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, LABELNAMES>

type LabeledArcs<'arc> = <G as SwhLabeledBackwardGraph>::LabeledArcs<'arc> where Self: 'arc

type LabeledPredecessors<'node> = TranslatedLabeledSuccessors<'node, <ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, LABELNAMES> as SwhLabeledBackwardGraph>::LabeledArcs<'node>, <<G as SwhLabeledBackwardGraph>::LabeledPredecessors<'node> as IntoIterator>::IntoIter, N> where Self: 'node

fn untyped_labeled_predecessors( &self, node_id: NodeId, ) -> Self::LabeledPredecessors<'_>

Return an IntoIterator over the predecessors of a node along with a list of labels of each arc

fn labeled_predecessors( &self, node_id: NodeId, ) -> impl Iterator<Item = (usize, impl Iterator<Item = EdgeLabel>)>

where Self: SwhGraphWithProperties + Sized, <Self as SwhGraphWithProperties>::Maps: Maps,

Return an IntoIterator over the predecessors of a node along with a list of labels of each arc

impl<G: SwhLabeledForwardGraph, N: ContractionBackend, MAPS: MaybeMaps, TIMESTAMPS: MaybeTimestamps, PERSONS: MaybePersons, CONTENTS: MaybeContents, STRINGS: MaybeStrings, LABELNAMES: MaybeLabelNames> SwhLabeledForwardGraph for ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, LABELNAMES>

type LabeledArcs<'arc> = <G as SwhLabeledForwardGraph>::LabeledArcs<'arc> where Self: 'arc

type LabeledSuccessors<'node> = TranslatedLabeledSuccessors<'node, <ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, LABELNAMES> as SwhLabeledForwardGraph>::LabeledArcs<'node>, <<G as SwhLabeledForwardGraph>::LabeledSuccessors<'node> as IntoIterator>::IntoIter, N> where Self: 'node

fn untyped_labeled_successors( &self, node_id: NodeId, ) -> Self::LabeledSuccessors<'_>

Return an IntoIterator over the successors of a node along with a list of labels of each arc

fn labeled_successors( &self, node_id: NodeId, ) -> impl Iterator<Item = (usize, impl Iterator<Item = EdgeLabel>)> + IntoFlattenedLabeledArcsIterator<EdgeLabel>

where Self: SwhGraphWithProperties + Sized, <Self as SwhGraphWithProperties>::Maps: Maps,

Return an IntoIterator over the successors of a node along with a list of labels of each arc