FilesExpand file tree

 master

/

mod.rs

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

147 lines (128 loc) · 4.24 KB

 master

/

mod.rs

Copy path

Top

File metadata and controls

• Code
• Blame

147 lines (128 loc) · 4.24 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

//! Basic graph module without explicit support for deletion.

//!

//! # Panics

//!

//! All methods will panic if given an out-of-bounds element index.

pub mod connectivity;

pub mod flow;

pub mod util;

/// Represents a union of disjoint sets. Each set's elements are arranged in a

/// tree, whose root is the set's representative.

pub struct DisjointSets {

parent: Vec<usize>,

}

impl DisjointSets {

/// Initializes disjoint sets containing one element each.

pub fn new(size: usize) -> Self {

Self {

parent: (0..size).collect(),

}

}

/// Finds the set's representative. Do path compression along the way to make

/// future queries faster.

pub fn find(&mut self, u: usize) -> usize {

let pu = self.parent[u];

if pu != u {

self.parent[u] = self.find(pu);

}

self.parent[u]

}

/// Merges the sets containing u and v into a single set containing their

/// union. Returns true if u and v were previously in different sets.

pub fn merge(&mut self, u: usize, v: usize) -> bool {

let (pu, pv) = (self.find(u), self.find(v));

self.parent[pu] = pv;

pu != pv

}

}

/// A compact graph representation. Edges are numbered in order of insertion.

/// Each adjacency list consists of all edges pointing out from a given vertex.

pub struct Graph {

/// Maps a vertex id to the first edge in its adjacency list.

first: Vec<Option<usize>>,

/// Maps an edge id to the next edge in the same adjacency list.

next: Vec<Option<usize>>,

/// Maps an edge id to the vertex that it points to.

endp: Vec<usize>,

}

impl Graph {

/// Initializes a graph with vmax vertices and no edges. To reduce

/// unnecessary allocations, emax_hint should be close to the number of

/// edges that will be inserted.

pub fn new(vmax: usize, emax_hint: usize) -> Self {

Self {

first: vec![None; vmax],

next: Vec::with_capacity(emax_hint),

endp: Vec::with_capacity(emax_hint),

}

}

/// Returns the number of vertices.

pub fn num_v(&self) -> usize {

self.first.len()

}

/// Returns the number of edges, double-counting undirected edges.

pub fn num_e(&self) -> usize {

self.endp.len()

}

/// Adds a directed edge from u to v.

pub fn add_edge(&mut self, u: usize, v: usize) {

self.next.push(self.first[u]);

self.first[u] = Some(self.num_e());

self.endp.push(v);

}

/// An undirected edge is two directed edges. If edges are added only via

/// this funcion, the reverse of any edge e can be found at e^1.

pub fn add_undirected_edge(&mut self, u: usize, v: usize) {

self.add_edge(u, v);

self.add_edge(v, u);

}

/// If we think of each even-numbered vertex as a variable, and its

/// odd-numbered successor as its negation, then we can build the

/// implication graph corresponding to any 2-CNF formula.

/// Note that u||v == !u -> v == !v -> u.

pub fn add_two_sat_clause(&mut self, u: usize, v: usize) {

self.add_edge(u ^ 1, v);

self.add_edge(v ^ 1, u);

}

/// Gets vertex u's adjacency list.

pub fn adj_list(&self, u: usize) -> AdjListIterator {

AdjListIterator {

graph: self,

next_e: self.first[u],

}

}

}

/// An iterator for convenient adjacency list traversal.

pub struct AdjListIterator<'a> {

graph: &'a Graph,

next_e: Option<usize>,

}

impl<'a> Iterator for AdjListIterator<'a> {

type Item = (usize, usize);

/// Produces an outgoing edge and vertex.

fn next(&mut self) -> Option<Self::Item> {

self.next_e.map(|e| {

let v = self.graph.endp[e];

self.next_e = self.graph.next[e];

(e, v)

})

}

}

#[cfg(test)]

mod test {

use super::*;

#[test]

fn test_adj_list() {

let mut graph = Graph::new(5, 6);

graph.add_edge(2, 3);

graph.add_edge(2, 4);

graph.add_edge(4, 1);

graph.add_edge(1, 2);

graph.add_undirected_edge(0, 2);

let adj = graph.adj_list(2).collect::<Vec<_>>();

assert_eq!(adj, vec![(5, 0), (1, 4), (0, 3)]);

for (e, v) in adj {

assert_eq!(v, graph.endp[e]);

}

}

}