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 89)

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