Struct transit_grid::graphs::TopologyGraph

pub struct TopologyGraph {
    pub graph: StableDiGraph<TopoNode, TopoEdge, u32>,
    /* private fields */
}

Represents the topological graph of a transit network as a skew-symmetric graph.

A TopologyGraph is a directed graph where each node in the topological graph maps to a node in the physical graph. This is particularly useful for scenarios such as rail switches where the directionality of edges matters.

Skew-Symmetric Model

The TopologyGraph struct uses a skew-symmetric model based on the definition by Goldberg & Karzanov (1996). In this model, let G = (V, E) be the directed graph with a function σ mapping vertices of G to other vertices, satisfying the following properties:

1. For every vertex v, σ(v) ≠ v.
2. For every vertex v, σ(σ(v)) = v.
3. For every edge (u, v), (σ(v), σ(u)) must also be an edge.

In the context of TopologyGraph,

• For each node v in V, there are two nodes in V_t, denoted as v_entry and v_exit.
• For each edge (u, v) in E, there are two directed edges in E_t: one from u_exit to v_entry and one from v_exit to u_entry.

Mathematically,

• V_t = {v_entry, v_exit | v ∈ V}
• E_t = {(u_exit, v_entry), (v_exit, u_entry) | (u, v) ∈ E}

Bigroup Algebraic Structure (Additional Information)

According to Dr. R. Muthuraj and P. M. Sitharselvam, M. S. Muthuraman (2010), a set G with two binary operations + and * is called a bigroup if there exist two proper subsets G1 and G2 of G such that G = G1 ∪ G2.

Fields

graph: StableDiGraph<TopoNode, TopoEdge, u32>

the inner graph

Implementations

impl TopologyGraph

pub fn new() -> Self

Creates a new instance of TopologyGraph.

pub fn index_to_id(&self, index: NodeIndex) -> Option<&NodeId>

Returns the NodeId corresponding to a given NodeIndex.

This method is useful when you have the index of a node in the graph and you want to retrieve its identifier.

Arguments

• index - The NodeIndex of the node.

Returns

• NodeId - The identifier of the node corresponding to the input index.

Panics

This function will panic if the NodeIndex does not exist in the graph.

pub fn id_to_index(&self, id: NodeId) -> Option<&(NodeIndex, NodeIndex)>

Returns the NodeIndex corresponding to a given NodeId.

This method is useful when you have the identifier of a node and you want to retrieve its index in the graph. As each NodeId maps to two TopoNodes in the graph, this function returns a tuple of NodeIndex.

Arguments

• id - The NodeId of the node.

Returns

• A tuple of two NodeIndex values corresponding to the two TopoNodes for the input NodeId.

Panics

This function will panic if the NodeId does not exist in the graph.

pub fn add_node(&mut self, node_id: NodeId) -> (NodeIndex, NodeIndex)

Adds a Node with a NodeId to the topological graph. This internally adds two TopoNodes to the graph.

Arguments

• node_id - The NodeId to be added to the graph.

Returns

• A tuple of two TopoNodeIds corresponding to the two TopoNodes added for the input NodeId.

pub fn add_edge( &mut self, edge_id: EdgeId, from_node_id: NodeId, to_node_id: NodeId ) -> (EdgeIndex, EdgeIndex)

Adds a TopoEdge to the topological graph.

Arguments

• edge_id - The EdgeId to be added to the graph.
• from_node_id - The NodeId from which the edge is originating.
• to_node_id - The NodeId to which the edge is pointing.

Returns

• TopoEdgeId - The ID of the added edge.

pub fn no_edges_in_direction( &self, topo_node_id: NodeIndex, neighbors: Vec<NodeId>, dir: Direction ) -> bool

Checks if there are no edges in the specified direction leading to any of the nodes in the neighbors list.

Arguments

• topo_node_id - The NodeIndex of the node to check.
• neighbors - A vector of NodeId that the node should not have edges towards in the given direction.
• dir - The direction of the edges to check (Outgoing or Incoming).

Returns

• bool - True if none of the neighbors have an edge in the given direction to the node, otherwise false.

pub fn find_node_index_with_edges( &self, node_id: NodeId, neighbors: Vec<NodeId>, dir: Direction ) -> Option<NodeIndex>

Returns the NodeIndex of the NodeId that does not have any edge in the opposite direction leading to any node in neighbors.

Arguments

• node_id - The ID of the node to check.
• neighbors - A vector of NodeIds to check.
• dir - The Direction in which to check the edges.

Returns

• Option<NodeIndex> - The NodeIndex of the NodeId if it does not have any edge in the opposite direction leading to nodes in neighbors, otherwise None.

pub fn get_other_toponode(&self, topo_node_id: NodeIndex) -> Option<NodeIndex>

Returns the NodeIndex of the other TopoNode for a given TopoNode.

Arguments

• topo_node_id - The NodeIndex of the TopoNode.

Returns

• Option<NodeIndex> - The NodeIndex of the other TopoNode for the given TopoNode, if it exists.

pub fn add_edge_with_accessibility( &mut self, edge_id: EdgeId, from_node_id: NodeId, to_node_id: NodeId, accessability: Accessability ) -> (EdgeIndex, EdgeIndex)

Adds an edge with a certain accessibility into the graph.

Arguments

• edge_id - The identifier of the edge that should be added.
• from_node_id - The identifier of the node where the edge should start.
• to_node_id - The identifier of the node where the edge should end.
• accessability - The type of accessability of the edge. This can be either ReachableNodes or UnreachableNodes.

Returns

A tuple of EdgeIndex values that were assigned to the newly created edges.

Panics

The function will panic if it’s unable to add an edge with the provided accessibility. This might occur if it cannot find nodes with the desired edge accessability or if the respective TopoNodes for the given nodes cannot be found.

pub fn has_incoming(&self, node: NodeIndex) -> bool

Checks if a node has an incoming edge in the topological graph.

Arguments

• node - The ID of the node to check.

Returns

• bool - true if the node has at least one incoming edge, false otherwise.

pub fn reverse_edge(&mut self, edge_index: EdgeIndex)

Reverse the direction of a given edge.

Arguments

• edge_index - The index of the edge to reverse.

Panics

This function will panic if the edge does not exist in the graph.

pub fn find_edge_indices( &self, node1_id: NodeId, node2_id: NodeId ) -> Option<(EdgeIndex, EdgeIndex)>

Returns the indices of edges between two nodes in all directions.

Arguments

• node1_id - The ID of the first node.
• node2_id - The ID of the second node.

Returns

• Option<(EdgeIndex, EdgeIndex)> - The indices of the two edges between the nodes, if they exist.

Panics

This function will panic if the nodes do not exist in the graph.

pub fn edge_is_in_neighbors_direction(&self, edge_index: EdgeIndex) -> bool

Checks if an edge is in the same direction as its neighboring edges.

Arguments

• edge_index - The EdgeIndex of the edge to check.

Returns

• bool - true if the edge is in the same direction as its neighboring edges, false otherwise.

Panics

This function will panic if the EdgeIndex does not exist in the graph.

Trait Implementations

impl Clone for TopologyGraph

fn clone(&self) -> TopologyGraph

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for TopologyGraph

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

Formats the value using the given formatter.

impl Default for TopologyGraph

fn default() -> Self

Returns the “default value” for a type.

impl TopologyGraphRepairer for TopologyGraph

fn repair_edge(&mut self, node1: NodeId, node2: NodeId)

Repairs the direction of edges in a graph if they are incorrectly directed.

fn reverse_dual_edge(&mut self, node1: NodeId, node2: NodeId)

Reverse the dual edge defined by the two given node IDs.

fn cross_link_dual_edge(&mut self, node1: NodeId, node2: NodeId)

Cross-link the dual edge defined by the two given node IDs.