Struct Neighbor

Source

pub struct Neighbor<V, L> {
    pub to: V,
    pub label: L,
}

Expand description

A neighboring vertex and the label of the arc used to reach it.

Fields§

§to: V§label: L

Implementations§

Source §

impl<V, L> Neighbor<V, L>

Source

pub fn new(to: V, label: L) -> Self

Examples found in repository ?

crates/competitive/src/graph/graph_base.rs (line 18)

17    fn from((to, label): (V, L)) -> Self {
18        Self::new(to, label)
19    }

More examples

Hide additional examples

crates/competitive/src/graph/adjacency_list.rs (line 19)

18    pub fn add_edge(&mut self, from: usize, to: usize) {
19        self.graph[from].push(Neighbor::new(to, self.esize));
20        self.esize += 1;
21    }
22    pub fn add_undirected_edge(&mut self, u: usize, v: usize) {
23        self.graph[u].push(Neighbor::new(v, self.esize));
24        self.graph[v].push(Neighbor::new(u, self.esize));
25        self.esize += 1;
26    }

crates/competitive/src/graph/sparse_graph.rs (line 77)

65    fn construct_graph(vsize: usize, edges: Vec<(usize, usize)>) -> SparseGraph<Self> {
66        let mut start: Vec<_> = vec![0usize; vsize + 1];
67        for (from, _) in edges.iter().cloned() {
68            start[from] += 1;
69        }
70        for i in 1..=vsize {
71            start[i] += start[i - 1];
72        }
73        let mut neighbors = Vec::<Neighbor<usize, usize>>::with_capacity(edges.len());
74        let ptr = neighbors.as_mut_ptr();
75        for (id, (from, to)) in edges.iter().cloned().enumerate() {
76            start[from] -= 1;
77            unsafe { ptr.add(start[from]).write(Neighbor::new(to, id)) };
78        }
79        unsafe { neighbors.set_len(edges.len()) };
80        SparseGraph {
81            vsize,
82            start,
83            neighbors,
84            edges,
85            _marker: PhantomData,
86        }
87    }
88}
89
90impl SparseGraphConstruction for UndirectedEdge {
91    fn construct_graph(vsize: usize, edges: Vec<(usize, usize)>) -> SparseGraph<Self> {
92        let mut start: Vec<_> = vec![0usize; vsize + 1];
93        for (from, to) in edges.iter().cloned() {
94            start[to] += 1;
95            start[from] += 1;
96        }
97        for i in 1..=vsize {
98            start[i] += start[i - 1];
99        }
100        let mut neighbors = Vec::<Neighbor<usize, usize>>::with_capacity(edges.len() * 2);
101        let ptr = neighbors.as_mut_ptr();
102        for (id, (from, to)) in edges.iter().cloned().enumerate() {
103            start[from] -= 1;
104            unsafe { ptr.add(start[from]).write(Neighbor::new(to, id)) };
105            start[to] -= 1;
106            unsafe { ptr.add(start[to]).write(Neighbor::new(from, id)) };
107        }
108        unsafe { neighbors.set_len(edges.len() * 2) };
109        SparseGraph {
110            vsize,
111            start,
112            neighbors,
113            edges,
114            _marker: PhantomData,
115        }
116    }
117}
118
119impl SparseGraphConstruction for BidirectionalEdge {
120    fn construct_graph(vsize: usize, edges: Vec<(usize, usize)>) -> SparseGraph<Self> {
121        let mut start: Vec<_> = vec![0usize; vsize + 1];
122        for (from, to) in edges.iter().cloned() {
123            start[to] += 1;
124            start[from] += 1;
125        }
126        for i in 1..=vsize {
127            start[i] += start[i - 1];
128        }
129        let mut neighbors = Vec::<Neighbor<usize, usize>>::with_capacity(edges.len() * 2);
130        let ptr = neighbors.as_mut_ptr();
131        for (id, (from, to)) in edges.iter().cloned().enumerate() {
132            start[from] -= 1;
133            unsafe { ptr.add(start[from]).write(Neighbor::new(to, id * 2)) };
134            start[to] -= 1;
135            unsafe { ptr.add(start[to]).write(Neighbor::new(from, id * 2 + 1)) };
136        }
137        unsafe { neighbors.set_len(edges.len() * 2) };
138        SparseGraph {
139            vsize,
140            start,
141            neighbors,
142            edges,
143            _marker: PhantomData,
144        }
145    }