Struct Graph

pub struct Graph<GH> { /* private fields */ }

| Simple undirected unweighted graph | data structure no checks whatsoever | should call init_size(..) first then | insert_edge(..) to populate | | IMP: nodes have indexes from 0 to n-1 | | IMP: graph is assumed to be connected |

Implementations

impl<GH> Graph<GH>

where GH: BccGraphHashInterface,

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 debug_all(&self) -> bool

pub fn adjacency_list_for_dachshund(&self) -> Vec<(usize, usize)>

impl<GH> Graph<GH>

pub fn node_to_muc_debugger<'g>( &'g self, ) -> NodeToMinimumUnionCycleDebugger<'g, Self>

Trait Implementations

impl<GH> ApproxBrandesIterationRuntimeOnBccSubgraph for Graph<GH>

where GH: CreateNamedEmpty + DebugIterationStep + FindPruningCounts + GetEdges + GetNeighborsForNode + GetNodeIdRange + GetSigmaValueForNode + HasEdge + InitDebugIteration + InsertEdge + MappedNodes + NumEdges + NumNodes + PairDependencyForNode + ParentsForNode + RemoveEdge + BccGraphHashInterface,

fn approx_bcc_iter_tm( &mut self, src: NodeId, dst: NodeId, avg_iter_time: &mut Duration, num_iter: Option<usize>, ) -> Result<(), BetweennessCentralityError>

| approximates the runtime of Brandes | iteration on a bcc subgraph by doing | @num_iter iteration and taking the average | if @num_iter is -1 the number of iteration | is just going to be the number of nodes in | the graph |

impl<GH> BuildGraphHashMappingForConnVertex<GH> for Graph<GH>

where GH: InsertNode + InsertEdge + CreateNamedEmpty,

fn build_graphhash_mapping_for_conn_vertex_step( &self, gh: &mut GH, bfs_source: NodeId, conn_vert: NodeId, item: (NodeId, &Vec<NodeId>), muc_id: MinimumUnionCycleId, ) -> Result<(), BetweennessCentralityError>

fn build_graphhash_mapping_for_conn_vertex( &self, item: (NodeId, &Vec<NodeId>), muc_id: MinimumUnionCycleId, ) -> Result<(NodeId, Arc<GH>), BetweennessCentralityError>

impl<GH> ClearMucs for Graph<GH>

where GH: IsValid + ExtendWith<GH> + GetConnectedComponentSizes + GetEdges + GetNeighborsForNode + GetNodeIdRange + HasMapForNode + InsertEdge + InsertNode + MappedNodes + NumEdges + NumNodes,

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

impl<GH> CollectAllMucEdges for Graph<GH>

where GH: GetConnectedComponentSizes + ExtendWith<GH> + GetEdges + GetNeighborsForNode + GetNodeIdRange + HasMapForNode + InsertEdge + InsertNode + MappedNodes + NumEdges + NumNodes,

fn collect_all_edges_in_mucs_in_one_set( &mut self, ) -> Result<Edges, BetweennessCentralityError>

impl<GH> ConnectNodeIds for Graph<GH>

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

impl<GH> ConnectedComponentSize for Graph<GH>

fn connected_component_size_through_v_and_this_edge( &self, visit_markers: &mut VisitMarkers, u: NodeId, ) -> usize

do a dfs from this guy to figure out the size of the connected component connected to the bcc through v and this edge

impl<GH> ConstructMucs<GH> for Graph<GH>

where GH: GetEdges + InsertEdge + NumEdges + GetConnectedComponentSizes + InsertNode + GetNeighborsForNode + GetNodeIdRange + HasMapForNode + MappedNodes + NumNodes + ExtendWith<GH>,

fn construct_mucs(&mut self, conn_comp_vec: Vec<GH>)

impl<GH> ConstructMucsForConnectedComponent<GH> for Graph<GH>

where GH: NumNodes + ExtendWith<GH> + GetConnectedComponentSizes + GetEdges + GetNeighborsForNode + GetNodeIdRange + HasMapForNode + InsertEdge + InsertNode + MappedNodes + NumEdges,

fn maybe_construct_mucs_for_connected_component(&mut self, component: GH)

fn construct_mucs_for_connected_component(&mut self, component: GH)

impl<GH> ConstructSingleNodeMucs for Graph<GH>

where GH: GetConnectedComponentSizes + ExtendWith<GH> + GetEdges + GetNeighborsForNode + GetNodeIdRange + HasMapForNode + InsertEdge + InsertNode + MappedNodes + NumEdges + NumNodes,

fn maybe_construct_single_node_muc(&mut self, idx: NodeId)

fn construct_single_node_mucs(&mut self)

impl<GH> CreateAndPushNewMuc for Graph<GH>

where GH: ExtendWith<GH, Error = BetweennessCentralityError> + GetConnectedComponentSizes + GetEdges + GetNeighborsForNode + GetNodeIdRange + HasMapForNode + InsertEdge + InsertNode + MappedNodes + NumEdges + NumNodes,

type Error = BetweennessCentralityError

fn create_and_push_new_muc( &mut self, shortest_path: &Vec<NodeId>, edge: &Edge, src_muc_id: MinimumUnionCycleId, dst_muc_id: MinimumUnionCycleId, ) -> Result<MinimumUnionCycleId, Self::Error>

impl<GH> CreateNamedEmpty for Graph<GH>

fn empty(name: &str) -> Self

impl<GH> CreateRandomConnected for Graph<GH>

fn random_connected(n_vertices: usize, n_edges: usize) -> Self

TODO: This is probably inefficient, but maybe not that bad

impl<GH> CreateScoresVector for Graph<GH>

fn create_scores_vector(&self) -> BetweennessScores

impl<GH> CreateSingleVertexMucs for Graph<GH>

where GH: GetConnectedComponentSizes + ExtendWith<GH> + GetEdges + GetNeighborsForNode + GetNodeIdRange + HasMapForNode + InsertEdge + InsertNode + MappedNodes + NumEdges + NumNodes,

fn create_single_vertex_muc(&mut self, idx: NodeId)

fn maybe_create_single_vertex_muc(&mut self, idx: NodeId)

fn create_single_vertex_mucs(&mut self)

impl<GH> Debug for Graph<GH>

where GH: BccGraphHashInterface,

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

Formats the value using the given formatter.

impl<GH> FindAllMucSubgraphs for Graph<GH>

where GH: GetEdges + ClearMucs + CreateNamedEmpty + Debug + ExtendWith<GH, Error = BetweennessCentralityError> + FindConnectedComponents<GH, Error = BetweennessCentralityError> + GetConnectedComponentSizes + GetNeighborsForNode + GetNodeIdRange + HasMapForNode + InsertEdge + InsertNode + IsValid + MappedNodes + NewFromCycleVec + NewFromGraphRef<Self> + NumEdges + NumNodes + RemoveBridges,

fn find_all_muc_subgraphs(&mut self)

find the disconnected subgraphs that will result from the deletion of connection vertices

impl<GH> FindConnVerts for Graph<GH>

where GH: GetEdges + ClearMucs + ExtendWith<GH> + GetConnectedComponentSizes + GetNeighborsForNode + GetNodeIdRange + HasMapForNode + InsertEdge + InsertNode + IsValid + MappedNodes + NumEdges + NumNodes,

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

find the connection vertices for each muc

edges that belong to the graph and don’t belong to any muc connect two connection vertices

1. collect all edges in mucs in one set

2. do simple subtraction of edges and update muc’s

impl<GH> FindEdgeBccWithComponent<GH> for Graph<GH>

where GH: HasEdge + ConnectedComponentSize + RemoveEdge + CreateNamedEmpty + MappedNodes + NumNodes + Named + GetNeighborsForNode + GetNodeIdRange + GetEdges + BccGraphHashInterface,

fn find_edge_bcc_with_component_step( &mut self, gh: &GH, v: NodeId, component: &mut Component, e: &Edge, ) -> Result<(), BetweennessCentralityError>

the node is an articulation point and it belongs to the bcc of interest, so it must be added to the art point of this bcc along with the sizes of the subgraphs it connects the bcc to

fn find_edge_bcc_with_component( &mut self, component: &mut Component, e: &Edge, ) -> Result<(), BetweennessCentralityError>

a. find the bcc subgraph

b. find the articulation points in bcc

c. find the sizes of the subgraphs connected to each art point

IMP: assumes @e is not in the graph already

impl<GH> FindEdgeBccWithDelta<GH> for Graph<GH>

where GH: ResetWith<GH> + RemoveEdge + FindSingleSourceShortestPaths + MappedNodes + NumNodes + GetNodeIdRange + GetNeighborsForNode + ParentsForNode + InitDebugIteration + DebugIterationStep + NumEdges + FindPruningCounts + HasEdge + GetEdges + InsertEdge + PathCountForNode + PairDependencyForNode + SetPairDependencyForNode + SetSigmaValueForNode + GetSigmaValueForNode + BccGraphHashInterface,

fn find_edge_bcc_with_delta( &mut self, bcc: &mut BiconnectedComponentsDelta<GH>, edge: &Edge, ) -> Result<(), BetweennessCentralityError>

a. find the bcc subgraph

b. find the articulation points in bcc

c. find the sizes of the subgraphs connected to each art point

fn find_edge_bcc_with_delta_step( &mut self, v: NodeId, bcc: &mut BiconnectedComponentsDelta<GH>, edge: &Edge, ) -> Result<(), BetweennessCentralityError>

the node is an articulation point and it belongs to the bcc of interest, so it must be added to the art point of this bcc along with the sizes of the subgraphs it connects the bcc to

impl<GH> FindEdgeBccWithScratch<GH> for Graph<GH>

where GH: DebugIterationStep + FindPruningCounts + GetEdges + GetNeighborsForNode + GetNodeIdRange + GetSigmaValueForNode + HasEdge + InitDebugIteration + InsertEdge + MappedNodes + NumEdges + NumNodes + PairDependencyForNode + ParentsForNode + RemoveEdge + BccGraphHashInterface,

fn find_edge_bcc_with_scratch( &mut self, bcc: &mut BiconnectedComponentsScratch<GH>, edge: &Edge, ) -> Result<(), BetweennessCentralityError>

a. find the bcc subgraph

b. find the articulation points in bcc

c. find the sizes of the subgraphs connected to each art point

fn find_edge_bcc_with_scratch_step( &mut self, v: NodeId, bcc: &mut BiconnectedComponentsScratch<GH>, edge: &Edge, ) -> Result<(), BetweennessCentralityError>

the node is an articulation point and it belongs to the bcc of interest, so it must be added to the art point of this bcc along with the sizes of the subgraphs it connects the bcc to

impl<GH> FindMucMcb<GH> for Graph<GH>

where GH: GetEdges + ClearMucs + CreateNamedEmpty + Debug + ExtendWith<GH, Error = BetweennessCentralityError> + FindConnectedComponents<GH, Error = BetweennessCentralityError> + GetConnectedComponentSizes + GetNeighborsForNode + GetNodeIdRange + HasMapForNode + InsertEdge + InsertNode + IsValid + MappedNodes + NewFromCycleVec + NewFromGraphRef<Self> + NumEdges + NumNodes + RemoveBridges,

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

fn find_muc_mcb_for_cycle( &mut self, src: NodeId, cycle_graph: &GH, visit_markers: &mut VisitMarkers, ) -> Result<(), BetweennessCentralityError>

impl<GH> FindMucSubgraphs for Graph<GH>

where GH: GetConnectedComponentSizes + ClearMucs + CreateNamedEmpty + ExtendWith<GH, Error = BetweennessCentralityError> + GetEdges + GetNeighborsForNode + GetNodeIdRange + GraphHashMucInterface + HasMapForNode + InsertEdge + InsertNode + IsValid + MappedNodes + NumEdges + NumNodes,

fn find_muc_subgraphs( &mut self, muc_id: MinimumUnionCycleId, ) -> Result<(), BetweennessCentralityError>

| TODO not sure what to do with single node | muc’s, will not do anything for them | now |

impl<GH> FindMucs for Graph<GH>

where GH: GetEdges + ClearMucs + CreateNamedEmpty + Debug + BccGraphHashInterface + ExtendWith<GH, Error = BetweennessCentralityError> + FindConnectedComponents<GH, Error = BetweennessCentralityError> + GetConnectedComponentSizes + GetNeighborsForNode + GetNodeIdRange + HasMapForNode + InsertEdge + InsertNode + IsValid + MappedNodes + NewFromCycleVec + NewFromGraphRef<Self> + NumEdges + NumNodes + RemoveBridges,

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

1. find bridges

2. delete bridges

3. find connected components of size >=3 (these are MinimumUnionCycles)

fn find_mucs(&mut self)

impl<GH> FindSingleSourceShortestPaths for Graph<GH>

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

impl<GH> From<GraphMock> for Graph<GH>

fn from(mock: GraphMock) -> Self

Converts to this type from the input type.

impl<GH> FromFilename for Graph<GH>

where GH: BccGraphHashInterface,

fn from_filename(filename: &str) -> Self

impl<GH> GetEdgeListDebugger for Graph<GH>

fn edgelist_debugger<'g>(&'g self) -> EdgeListDebugger<'g, Self>

impl<GH> GetEdges for Graph<GH>

fn edges(&self) -> &Edges

impl<GH> GetMuc<GH> for Graph<GH>

fn muc(&self, idx: MinimumUnionCycleId) -> &MinimumUnionCycle<GH>

fn muc_mut(&mut self, idx: MinimumUnionCycleId) -> &mut MinimumUnionCycle<GH>

impl<GH> GetMucDebuggerWithNodes for Graph<GH>

fn muc_debugger_with_nodes<'g>(&'g self) -> MinimumUnionCycleDebugger<'g, Self>

impl<GH> GetMucDebuggerWithoutNodes for Graph<GH>

fn muc_debugger_without_nodes<'g>( &'g self, ) -> MinimumUnionCycleDebugger<'g, Self>

impl<GH> GetMucs<GH> for Graph<GH>

fn get_mucs<'a>(&'a self) -> &Vec<MinimumUnionCycle<GH>>

impl<GH> GetNeighborsForNode for Graph<GH>

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

impl<GH> GetNodesToMucs for Graph<GH>

fn get_nodes_to_mucs<'a>(&'a self) -> &'a MucIdMap

impl<GH> GetNumMucs for Graph<GH>

fn get_num_mucs(&mut self) -> usize

impl<GH> GetShortestPath for Graph<GH>

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

impl<GH> HasEdge for Graph<GH>

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

impl<GH> InitBetweennessCentrality for Graph<GH>

where GH: GetLimitedNodeIdRange, Self: GetLimitedNodeIdRange,

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

impl<GH> InitInternals for Graph<GH>

type Error = BetweennessCentralityError

fn init_internals(&mut self) -> Result<(), Self::Error>

impl<GH> InitWithSize for Graph<GH>

fn init_size(&mut self, num_nodes: usize)

impl<GH> InsertEdge for Graph<GH>

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

impl<GH> InsertEdgeUpdateBc for Graph<GH>

where GH: GraphHashMucInterface + ResetWith<GH> + RemoveEdge + CreateNamedEmpty + FindSingleSourceShortestPaths + GetNodeIdRange + GetNeighborsForNode + ParentsForNode + InitDebugIteration + DebugIterationStep + FindPruningCounts + HasEdge + PathCountForNode + PairDependencyForNode + SetPairDependencyForNode + SetSigmaValueForNode + GetSigmaValueForNode + BccGraphHashInterface,

fn insert_edge_update_bc_experimental( &mut self, edge: &Edge, bcc_stat: &mut BiconnectedComponentsStat, max_iter_d1: Option<usize>, max_iter_d2: Option<usize>, ) -> Result<(), BetweennessCentralityError>

impl<GH> InsertEdgeUpdateMuc for Graph<GH>

where GH: GraphHashMucInterface + ClearMucs + CreateNamedEmpty + ExtendWith<GH, Error = BetweennessCentralityError> + GetConnectedComponentSizes + GetNeighborsForNode + GetNodeIdRange + IsValid,

fn insert_edge_and_update_muc_when_full_edge_contained_in_muc( &mut self, edge: &Edge, src_muc_id: MinimumUnionCycleId, )

case 1: both @src and @dst are in the same muc

    then just update the graph and the
    muc graph

just update the muc and the graph

fn insert_edge_and_update_muc_when_we_are_not_in_the_same_muc( &mut self, edge: &Edge, src_muc_id: MinimumUnionCycleId, dst_muc_id: MinimumUnionCycleId, ) -> Result<(), BetweennessCentralityError>

case 2: @src and @dst are not in the same muc

fn insert_edge_update_muc(&mut self, edge: &Edge)

impl<GH> McbFind for Graph<GH>

fn mcb_find(&self)

will store into self.mcb

impl<GH> MergeMucCycle<GH> for Graph<GH>

where GH: GetConnectedComponentSizes + ExtendWith<GH> + GetEdges + GetNeighborsForNode + GetNodeIdRange + HasMapForNode + InsertEdge + InsertNode + MappedNodes + NumEdges + NumNodes,

fn merge_muc_cycle(&mut self, muc: &mut MinimumUnionCycle<GH>, cycle: &Cycle)

| add all the edges in cycle to muc |

impl<GH> Named for Graph<GH>

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

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

impl<GH> NodeIdToMucId for Graph<GH>

fn nodeid_to_mucid(&self, idx: NodeId) -> MinimumUnionCycleId

impl<GH> NumEdges for Graph<GH>

fn num_edges(&self) -> usize

impl<GH> NumNodes for Graph<GH>

fn num_nodes(&self) -> usize

impl<GH> PrintHeader for Graph<GH>

fn print_header(&self)

impl<GH> ReadGraph for Graph<GH>

where GH: BccGraphHashInterface,

type Error = BetweennessCentralityError

fn read_graph(&mut self, path: &str) -> Result<(), Self::Error>

impl<GH> RemoveEdge for Graph<GH>

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

impl<GH> ResetVisitMarkersAndVisitNode for Graph<GH>

fn reset_visit_markers_and_visit_node(&mut self, node: NodeId)

impl<GH> SetGraphName for Graph<GH>

fn set_graph_name(&mut self, name: &str)

impl<GH> SetMucDebug for Graph<GH>

where GH: GraphHashMucInterface,

fn set_muc_debug(&self, val: bool)

impl<GH> SubtractEdge for Graph<GH>

where GH: GetConnectedComponentSizes + ExtendWith<GH> + GetEdges + GetNeighborsForNode + GetNodeIdRange + HasMapForNode + InsertEdge + InsertNode + MappedNodes + NumEdges + NumNodes,

fn simple_subtract_edge_and_update_mucs(&mut self, edge: &Edge)

fn maybe_simple_subtract_edge_and_update_mucs( &mut self, edge: &Edge, all_muc_edges: &Edges, )

fn do_simple_subtraction_of_edges_and_update_mucs( &mut self, all_muc_edges: &Edges, )

impl<GH> VisitMarkersHandle for Graph<GH>

fn visit_markers_handle(&mut self) -> &mut VisitMarkers