Struct SubGraph

pub struct SubGraph { /* private fields */ }

| all functions here assume the given | node ids are proper ones from 0 to n-1 | so, the caller must use |

Implementations

impl SubGraph

pub fn new_from_graph_hash_ref<GH>(gh: &GH, name: &str) -> Self

where GH: NumNodes + MappedNodes + GetEdges + GetNodeIdRange + GetNeighborsForNode,

QUESTION: why is this impl different from &Graph

pub fn new_from_graph_ref<G>(g: &G, name: &str) -> Self

where G: NumNodes + MappedNodes + GetNodeIdRange + GetNeighborsForNode + GetEdges,

QUESTION: why is this impl different from &GraphHash

impl SubGraph

pub fn debug_without_nodes<'g>(&'g self) -> SubGraphDebugger<'g>

pub fn debug_with_nodes<'g>(&'g self) -> SubGraphDebugger<'g>

impl SubGraph

pub fn stack_push(&mut self, n: NodeId)

pub fn stack_pop(&mut self) -> Option<NodeId>

pub fn stack_len(&self) -> usize

pub fn stack_node_at_index(&self, idx: usize) -> NodeId

pub fn stack_set_node_at_index(&mut self, idx: usize, n: NodeId)

impl SubGraph

pub fn queue_len(&self) -> usize

pub fn enqueue(&mut self, n: NodeId)

pub fn dequeue(&mut self) -> Option<NodeId>

impl SubGraph

pub fn clear_parents(&mut self)

pub fn clear_node_parents(&mut self, node: NodeId)

pub fn parents_for_node(&self, v_n: NodeId) -> Vec<NodeId>

pub fn num_parents_for_node(&self, v_n: NodeId) -> usize

pub fn set_single_parent(&mut self, node: NodeId, parent: NodeId)

pub fn set_parents_for_node(&mut self, node: NodeId, parents: Vec<NodeId>)

pub fn has_parent(&self, node: NodeId, candidate: NodeId) -> bool

pub fn add_parent(&mut self, node: NodeId, parent: NodeId)

pub fn reinit_parents(&mut self, len: usize)

pub fn fill_to_len(&mut self, len: usize, val: Vec<NodeId>)

impl SubGraph

pub fn visited(&self, id: NodeId) -> bool

pub fn unvisited(&self, id: NodeId) -> bool

pub fn visit(&mut self, id: NodeId)

pub fn unvisit(&mut self, id: NodeId)

pub fn reinit_visit_markers(&mut self, len: usize)

pub fn fill_visit_markers(&mut self, val: bool)

pub fn fill_visit_markers_to_len(&mut self, len: usize, val: bool)

impl SubGraph

pub fn label_map_clear(&mut self)

pub fn label_map_inout(&self, node: NodeId) -> NodeId

pub fn label_map_outin(&self, node: NodeId) -> NodeId

pub fn label_map_mapped_edge(&self, theirs: &Edge) -> Edge

pub fn label_map_projected_edge(&self, mine: &Edge) -> Edge

pub fn label_map_insert_outin(&mut self, src: NodeId, dst: NodeId)

pub fn label_map_resize_inout(&mut self, len: usize, default: NodeId)

impl SubGraph

pub fn distance_is_farther_away(&self, x: NodeId, y: NodeId) -> bool

pub fn distance_is_farther_than_one_away(&self, x: NodeId, y: NodeId) -> bool

pub fn distance_is_one_step_away(&self, x: NodeId, y: NodeId) -> bool

pub fn distance_is_infinite(&self, node: NodeId) -> bool

pub fn distance(&self, node: NodeId) -> f64

pub fn set_distance_for_node(&mut self, node: NodeId, val: f64)

pub fn set_distance_one_step_away(&mut self, dst: NodeId, src: NodeId)

pub fn set_distance_zero(&mut self, source: NodeId)

pub fn distance_reinit(&mut self, len: usize)

impl SubGraph

pub fn sigma_update(&mut self, v_p: NodeId, v_n: NodeId, sp_sn: f64)

pub fn sigma_set_node_to_zero(&mut self, node: NodeId)

pub fn sigma_set_node_to_one(&mut self, node: NodeId)

pub fn increment_sigma_value_for_node(&mut self, v_n: NodeId, c_t: f64)

pub fn reinit_sigmas(&mut self, len: usize)

pub fn sigma_ratio(&self, v_p: NodeId, v_n: NodeId) -> f64

pub fn fill_sigmas(&mut self, val: f64)

impl SubGraph

pub fn new_sigmas_sigma_update(&mut self, v_p: NodeId, v_n: NodeId, sp_sn: f64)

pub fn new_sigmas_sigma_set_node_to_zero(&mut self, node: NodeId)

pub fn new_sigmas_sigma_set_node_to_one(&mut self, node: NodeId)

pub fn new_sigmas_sigma_value_for_node(&self, node: NodeId) -> f64

pub fn new_sigmas_set_sigma_value_for_node(&mut self, node: NodeId, val: f64)

pub fn new_sigmas_increment_sigma_value_for_node( &mut self, v_n: NodeId, c_t: f64, )

pub fn reinit_new_sigmas(&mut self, len: usize)

pub fn new_sigmas_sigma_ratio(&self, v_p: NodeId, v_n: NodeId) -> f64

pub fn new_sigmas_fill_sigmas(&mut self, val: f64)

impl SubGraph

pub fn pair_dependency_for_node(&self, node: NodeId) -> f64

pub fn set_pair_dependency_for_node(&mut self, node: NodeId, val: f64)

pub fn reinit_pair_dependencies(&mut self, len: usize)

pub fn increment_pair_dependency_for_node(&mut self, node: NodeId, val: f64)

impl SubGraph

pub fn new_pair_dependencies_pair_dependency_for_node( &self, node: NodeId, ) -> f64

pub fn new_pair_dependencies_set_pair_dependency_for_node( &mut self, node: NodeId, val: f64, )

pub fn new_pair_dependencies_reinit(&mut self, len: usize)

pub fn new_pair_dependencies_increment_pair_dependency_for_node( &mut self, node: NodeId, val: f64, )

impl SubGraph

pub fn increment_path_count_for_node(&mut self, node: NodeId, val: usize)

pub fn increment_path_count_for_node_from( &mut self, node: NodeId, other: NodeId, )

pub fn update_path_counts(&mut self, dst: NodeId, src: NodeId)

pub fn path_count_for_node(&self, node: NodeId) -> usize

pub fn set_path_count_for_node(&mut self, node: NodeId, count: usize)

pub fn path_count_ratio(&self, v_p: NodeId, v_n: NodeId) -> f64

pub fn set_path_count_to_one(&mut self, source: NodeId)

pub fn set_path_count_to_zero(&mut self, source: NodeId)

pub fn path_counts_reinit(&mut self, len: usize)

impl SubGraph

pub fn new_path_counts_increment_path_count_for_node( &mut self, node: NodeId, val: usize, )

pub fn new_path_counts_increment_path_count_for_node_from( &mut self, node: NodeId, other: NodeId, )

pub fn new_path_counts_update_path_counts(&mut self, dst: NodeId, src: NodeId)

pub fn new_path_counts_path_count_for_node(&self, node: NodeId) -> usize

pub fn new_path_counts_set_path_count_for_node( &mut self, node: NodeId, count: usize, )

pub fn new_path_counts_path_count_ratio(&self, v_p: NodeId, v_n: NodeId) -> f64

pub fn new_path_counts_set_path_count_to_one(&mut self, source: NodeId)

pub fn new_path_counts_set_path_count_to_zero(&mut self, source: NodeId)

pub fn new_path_counts_reinit(&mut self, len: usize)

impl SubGraph

pub fn inc_path_counts_increment_path_count_for_node( &mut self, node: NodeId, val: usize, )

pub fn inc_path_counts_increment_path_count_for_node_from( &mut self, node: NodeId, other: NodeId, )

pub fn inc_path_counts_update_path_counts(&mut self, dst: NodeId, src: NodeId)

pub fn inc_path_counts_path_count_for_node(&self, node: NodeId) -> usize

pub fn inc_path_counts_set_path_count_for_node( &mut self, node: NodeId, count: usize, )

pub fn inc_path_counts_path_count_ratio(&self, v_p: NodeId, v_n: NodeId) -> f64

pub fn inc_path_counts_set_path_count_to_one(&mut self, source: NodeId)

pub fn inc_path_counts_set_path_count_to_zero(&mut self, source: NodeId)

pub fn inc_path_counts_reinit(&mut self, len: usize)

impl SubGraph

pub fn nodeid_range(&self) -> Vec<NodeId>

pub fn limited_nodeid_range(&self, cap: Option<usize>) -> Vec<NodeId>

pub fn mapped_nodes(&self) -> Vec<NodeId>

pub fn set_neighbors(&mut self, node: NodeId, nbrs: Vec<NodeId>)

pub fn add_neighbor(&mut self, node: NodeId, nbr: NodeId)

pub fn has_map_for_node(&self, node: NodeId) -> bool

pub fn remove_node_and_neighbors(&mut self, node: NodeId)

pub fn neighbors(&self, node: NodeId) -> Neighbors

pub fn extend_mapped_nodes(&mut self, other: &NeighborsMap)

pub fn nodes_map_unlink_all(&mut self, src: NodeId, dst: NodeId)

pub fn nodes_map_add_edge(&mut self, e: &Edge)

pub fn nodes_map_unlink_edge(&mut self, e: &Edge)

pub fn nodes_map_reinit(&mut self, len: usize)

pub fn nodes_map_clear(&mut self)

pub fn nodes_map_add_isolated_node(&mut self, node: NodeId)

pub fn num_edges(&self) -> usize

pub fn clear_edges(&mut self)

pub fn has_edge(&self, edge: &Edge) -> bool

pub fn connects(&self, src: NodeId, dst: NodeId) -> bool

pub fn unlink_all_edges_between(&mut self, src: NodeId, dst: NodeId)

pub fn edges_to_node(&self, src: NodeId) -> Vec<Edge>

pub fn edges_from_node(&self, src: NodeId) -> Vec<Edge>

pub fn iteration1_build_stack( &mut self, src: NodeId, dst: NodeId, stack: &mut Stack<NodeId>, ) -> Result<(), BetweennessCentralityError>

pub fn iteration2_build_stack( &mut self, s: NodeId, stack: &mut Vec<NodeId>, ) -> Result<(), BetweennessCentralityError>

pub fn init_iteration1(&mut self, source: NodeId)

pub fn iteration1_step1_process_nodes( &mut self, v_i: NodeId, stack: &mut Stack<NodeId>, src: NodeId, dst: NodeId, )

pub fn iteration1_fill_stack( &mut self, stack: &mut Stack<NodeId>, src: NodeId, dst: NodeId, ) -> Result<(), BetweennessCentralityError>

pub fn init_iteration2(&mut self, source: NodeId)

pub fn adjust_stack(&self, stack: &mut Vec<NodeId>)

pub fn resize_pair_dependencies_and_sigma_based_on_map_len(&mut self)

pub fn iteration2_update1( &mut self, stack: &mut Vec<NodeId>, ) -> Result<(), BetweennessCentralityError>

pub fn iteration2_update2_process_neighbor(&mut self, v: NodeId, nbr: NodeId)

pub fn iteration2_update2(&mut self) -> Result<(), BetweennessCentralityError>

pub fn bfs_maybe_visit(&mut self, node: NodeId)

pub fn maybe_augment_bc_value_for_node( &self, source: NodeId, v_n: NodeId, scores: &mut BetweennessScores, )

pub fn maybe_attenuate_bc_value_for_node( &self, source: NodeId, v_n: NodeId, scores: &mut BetweennessScores, )

pub fn maybe_attenuate_bc_value_for_node_using_vertex_map<GH: NumNodes>( &self, source: NodeId, v_n: NodeId, scores: &mut BetweennessScores, tmp_subgraph_map: &SubGraphMap<GH>, tmp_conn_vertex_map: &ConnVertexMap, )

pub fn maybe_augment_bc_value_for_node_using_vertex_map<GH: NumNodes>( &self, source: NodeId, v_n: NodeId, scores: &mut BetweennessScores, tmp_subgraph_map: &SubGraphMap<GH>, tmp_conn_vertex_map: &ConnVertexMap, )

pub fn rbfs1_to_add_the_new_pair_dependencies_step<GH: NumNodes>( &mut self, v_n: NodeId, source: NodeId, stack: &Vec<NodeId>, tmp_subgraph_map: &SubGraphMap<GH>, tmp_conn_vertex_map: &ConnVertexMap, scores: &mut BetweennessScores, )

pub fn rbfs1_to_add_the_new_pair_dependencies<GH: NumNodes>( &mut self, source: NodeId, stack: &Vec<NodeId>, tmp_subgraph_map: &SubGraphMap<GH>, tmp_conn_vertex_map: &ConnVertexMap, scores: &mut BetweennessScores, ) -> Result<(), BetweennessCentralityError>

pub fn rbfs2_to_add_the_new_pair_dependencies_step<GH: NumNodes>( &mut self, v_n: NodeId, source: NodeId, stack: &Vec<NodeId>, tmp_subgraph_map: &SubGraphMap<GH>, tmp_conn_vertex_map: &ConnVertexMap, scores: &mut BetweennessScores, ) -> Result<(), BetweennessCentralityError>

pub fn rbfs2_to_add_the_new_pair_dependencies<GH: NumNodes>( &mut self, source: NodeId, stack: &Vec<NodeId>, tmp_subgraph_map: &SubGraphMap<GH>, tmp_conn_vertex_map: &ConnVertexMap, scores: &mut BetweennessScores, )

pub fn src_dist_is_greater_than_dst_plus_one( &self, src: NodeId, dst: NodeId, ) -> bool

pub fn src_dist_equals_dst_plus_one(&self, src: NodeId, dst: NodeId) -> bool

pub fn iteration_2<GH: NumNodes>( &mut self, tmp_subgraph_map: &SubGraphMap<GH>, tmp_conn_vertex_map: &ConnVertexMap, source: NodeId, src: NodeId, dst: NodeId, src_distance: f64, dst_distance: f64, scores: &mut BetweennessScores, ) -> Result<(), BetweennessCentralityError>

pub fn iteration2_step3_when_src_dist_is_greater_than_dst_plus_one( &mut self, w: NodeId, v: NodeId, ) -> Result<(), BetweennessCentralityError>

pub fn iteration2_step3_when_src_dist_equals_dst_plus_one( &mut self, w: NodeId, v: NodeId, ) -> Result<(), BetweennessCentralityError>

pub fn iteration2_step3_process_neighbor( &mut self, v: NodeId, nbr: NodeId, ) -> Result<(), BetweennessCentralityError>

pub fn iteration2_step3_process(&mut self, v: NodeId)

pub fn iteration2_step3(&mut self)

Trait Implementations

impl BfsFromSource for SubGraph

fn do_bfs_from_source_count_vertices_and_mark_visited( &self, source: NodeId, visit_markers: &mut VisitMarkers, out_vec: &mut Vec<i32>, ) -> Result<(), BetweennessCentralityError>

do a BFS from s, count the number of vertices, and mark the visited

impl Clear for SubGraph

fn clear(&mut self)

impl ComputeNewPathCountsAndPaths for SubGraph

fn compute_new_path_counts_and_paths(&mut self, src: NodeId, dst: NodeId)

impl CreateDistanceMaps for SubGraph

fn create_distance_maps( &self, edge: &Edge, ) -> Result<(DistanceMap, DistanceMap), BetweennessCentralityError>

impl CreateNamedEmpty for SubGraph

fn empty(name: &str) -> Self

impl Debug for SubGraph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl FindPruningCounts for SubGraph

fn find_pruning_counts_exp( &mut self, src: NodeId, dst: NodeId, ) -> Result<(i32, i32, i32), BetweennessCentralityError>

impl FindSingleSourceShortestPaths for SubGraph

fn find_single_source_shortest_paths( &self, s: NodeId, ) -> Result<DistanceMap, BetweennessCentralityError>

impl GetConnectedComponentSizes for SubGraph

fn conn_comp_sizes(&self) -> Result<Vec<i32>, BetweennessCentralityError>

| the vector @out_vec will have sizes | of the connected components in the graph |

impl GetEdges for SubGraph

fn edges(&self) -> &Edges

impl GetNeighborsForNode for SubGraph

fn neighbors(&self, node: NodeId) -> Neighbors

impl GetNodes for SubGraph

fn nodes(&self) -> &NeighborsMap

impl GetSigmaValueForNode for SubGraph

fn sigma_value_for_node(&self, node: NodeId) -> f64

impl InsertEdge for SubGraph

fn insert_edge(&mut self, edge: &Edge) -> Result<(), BetweennessCentralityError>

impl InsertEdgeBetweenNodes for SubGraph

fn insert_edge_between_nodes( &mut self, src: NodeId, dst: NodeId, ) -> Result<(), BetweennessCentralityError>

impl MucAttenuate for SubGraph

fn muc_attenuate_no_new( &mut self, v_n: NodeId, source: NodeId, tmp_conn_vertex_map: &ConnVertexMap, scores: &mut BetweennessScores, )

impl MucAttenuateParent for SubGraph

fn muc_attenuate_parent_no_new( &mut self, parent: NodeId, v_n: NodeId, source: NodeId, tmp_conn_vertex_map: &ConnVertexMap, scores: &mut BetweennessScores, )

impl MucAugment for SubGraph

fn muc_augment_no_new( &mut self, v_n: NodeId, source: NodeId, tmp_conn_vertex_map: &ConnVertexMap, scores: &mut BetweennessScores, )

impl MucAugmentParent for SubGraph

fn muc_augment_parent_no_new( &mut self, parent: NodeId, v_n: NodeId, source: NodeId, tmp_conn_vertex_map: &ConnVertexMap, scores: &mut BetweennessScores, )

impl MucComputeNewPathCountsAndPaths for SubGraph

fn muc_compute_new_path_counts_and_paths(&mut self, src: NodeId, dst: NodeId)

impl MucUpdate for SubGraph

fn muc_update( &mut self, v_n: NodeId, source: NodeId, tmp_conn_vertex_map: &ConnVertexMap, scores: &mut BetweennessScores, )

impl MucUpdateParent for SubGraph

fn muc_update_parent( &mut self, parent: NodeId, v_n: NodeId, source: NodeId, tmp_conn_vertex_map: &ConnVertexMap, scores: &mut BetweennessScores, )

impl Named for SubGraph

fn name(&self) -> Cow<'_, str>

Returns the name associated with self. We use Cow to allow both owned and borrowed strings.

impl NumNodes for SubGraph

fn num_nodes(&self) -> usize

impl ReinitMaps for SubGraph

fn reinit_maps(&mut self)

impl RemoveEdgeBetweenNodes for SubGraph

fn remove_edge_between_nodes( &mut self, src: NodeId, dst: NodeId, ) -> Result<(), BetweennessCentralityError>

impl<G: NumNodes + GetNodeIdRange + GetNeighborsForNode + GetEdges> ResetWith<G> for SubGraph

fn reset_with(&mut self, g: &G)

impl SetSigmaValueForNode for SubGraph

fn set_sigma_value_for_node(&mut self, node: NodeId, val: f64)

impl UpdatePairDependencies for SubGraph

fn update_pair_dependencies(&mut self, v_p: NodeId, v_n: NodeId)

fn update_new_pair_dependencies(&mut self, v_p: NodeId, v_n: NodeId)

impl UpdateSigmas for SubGraph

fn maybe_update_all_sigmas<GH: NumNodes>( &mut self, v_n: NodeId, source: NodeId, subgraph_map: &SubGraphMap<GH>, conn_vertex_map: &ConnVertexMap, ) -> Result<(), BetweennessCentralityError>

fn maybe_update_all_sigmas_and_do_new<GH: NumNodes>( &mut self, v_n: NodeId, source: NodeId, subgraph_map: &SubGraphMap<GH>, conn_vertex_map: &ConnVertexMap, ) -> Result<(), BetweennessCentralityError>

fn update_all_sigmas(&mut self, v_p: NodeId, v_n: NodeId)

fn update_new_sigmas(&mut self, v_p: NodeId, v_n: NodeId)

fn update_sigmas(&mut self, v_p: NodeId, v_n: NodeId)

impl UpdateWithSrcDst for SubGraph

fn update(&mut self, src: NodeId, dst: NodeId)