Struct Adjacency

Source

pub struct Adjacency {
    pub id: usize,
    pub to: usize,
}

Fields§

§id: usize§to: usize

Implementations§

Source §

impl Adjacency

Source

pub fn new(id: usize, to: usize) -> Adjacency

Examples found in repository ?

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

81    fn construct_graph(vsize: usize, edges: Vec<(usize, usize)>) -> SparseGraph<Self> {
82        let mut start: Vec<_> = vec![0usize; vsize + 1];
83        for (from, _) in edges.iter().cloned() {
84            start[from] += 1;
85        }
86        for i in 1..=vsize {
87            start[i] += start[i - 1];
88        }
89        let mut elist = Vec::<Adjacency>::with_capacity(edges.len());
90        let ptr = elist.as_mut_ptr();
91        for (id, (from, to)) in edges.iter().cloned().enumerate() {
92            start[from] -= 1;
93            unsafe { ptr.add(start[from]).write(Adjacency::new(id, to)) };
94        }
95        unsafe { elist.set_len(edges.len()) };
96        SparseGraph {
97            vsize,
98            start,
99            elist,
100            edges,
101            _marker: PhantomData,
102        }
103    }
104}
105
106impl SparseGraphConstruction for UndirectedEdge {
107    fn construct_graph(vsize: usize, edges: Vec<(usize, usize)>) -> SparseGraph<Self> {
108        let mut start: Vec<_> = vec![0usize; vsize + 1];
109        for (from, to) in edges.iter().cloned() {
110            start[to] += 1;
111            start[from] += 1;
112        }
113        for i in 1..=vsize {
114            start[i] += start[i - 1];
115        }
116        let mut elist = Vec::<Adjacency>::with_capacity(edges.len() * 2);
117        let ptr = elist.as_mut_ptr();
118        for (id, (from, to)) in edges.iter().cloned().enumerate() {
119            start[from] -= 1;
120            unsafe { ptr.add(start[from]).write(Adjacency::new(id, to)) };
121            start[to] -= 1;
122            unsafe { ptr.add(start[to]).write(Adjacency::new(id, from)) };
123        }
124        unsafe { elist.set_len(edges.len() * 2) };
125        SparseGraph {
126            vsize,
127            start,
128            elist,
129            edges,
130            _marker: PhantomData,
131        }
132    }
133}
134
135impl SparseGraphConstruction for BidirectionalEdge {
136    fn construct_graph(vsize: usize, edges: Vec<(usize, usize)>) -> SparseGraph<Self> {
137        let mut start: Vec<_> = vec![0usize; vsize + 1];
138        for (from, to) in edges.iter().cloned() {
139            start[to] += 1;
140            start[from] += 1;
141        }
142        for i in 1..=vsize {
143            start[i] += start[i - 1];
144        }
145        let mut elist = Vec::<Adjacency>::with_capacity(edges.len() * 2);
146        let ptr = elist.as_mut_ptr();
147        for (id, (from, to)) in edges.iter().cloned().enumerate() {
148            start[from] -= 1;
149            unsafe { ptr.add(start[from]).write(Adjacency::new(id * 2, to)) };
150            start[to] -= 1;
151            unsafe { ptr.add(start[to]).write(Adjacency::new(id * 2 + 1, from)) };
152        }
153        unsafe { elist.set_len(edges.len() * 2) };
154        SparseGraph {
155            vsize,
156            start,
157            elist,
158            edges,
159            _marker: PhantomData,
160        }
161    }