Skip to content

Commit d1168b0

Browse files
authored
Avoid creating dummy NodeIds in matching (#442)
Fixes a crash with GraphMaps
1 parent 5a7fc2e commit d1168b0

1 file changed

Lines changed: 73 additions & 53 deletions

File tree

‎src/matching.rs‎

Lines changed: 73 additions & 53 deletions
Original file line numberDiff line numberDiff line change
@@ -11,15 +11,15 @@ use super::visit::{
1111
/// of the graph.
1212
pub struct Matching<G: GraphBase> {
1313
graph: G,
14-
mate: Vec<G::NodeId>,
14+
mate: Vec<Option<G::NodeId>>,
1515
n_edges: usize,
1616
}
1717

1818
impl<G> Matching<G>
1919
where
2020
G: GraphBase,
2121
{
22-
fn new(graph: G, mate: Vec<G::NodeId>, n_edges: usize) -> Self {
22+
fn new(graph: G, mate: Vec<Option<G::NodeId>>, n_edges: usize) -> Self {
2323
Self {
2424
graph,
2525
mate,
@@ -36,13 +36,7 @@ where
3636
///
3737
/// Returns `None` if the node is not matched or does not exist.
3838
pub fn mate(&self, node: G::NodeId) -> Option<G::NodeId> {
39-
self.mate.get(self.graph.to_index(node)).and_then(|&mate| {
40-
if mate != self.graph.dummy() {
41-
Some(mate)
42-
} else {
43-
None
44-
}
45-
})
39+
self.mate.get(self.graph.to_index(node)).and_then(|&id| id)
4640
}
4741

4842
/// Iterates over all edges from the matching.
@@ -105,16 +99,13 @@ where
10599
}
106100

107101
trait WithDummy: NodeIndexable {
108-
fn dummy(&self) -> Self::NodeId;
109102
fn dummy_idx(&self) -> usize;
110103
fn node_bound_with_dummy(&self) -> usize;
104+
/// Convert `i` to a node index, returns None for the dummy node
105+
fn try_from_index(self: &Self, i: usize) -> Option<Self::NodeId>;
111106
}
112107

113108
impl<G: NodeIndexable> WithDummy for G {
114-
fn dummy(&self) -> Self::NodeId {
115-
self.from_index(self.dummy_idx())
116-
}
117-
118109
fn dummy_idx(&self) -> usize {
119110
// Gabow numbers the vertices from 1 to n, and uses 0 as the dummy
120111
// vertex. Our vertex indices are zero-based and so we use the node
@@ -125,11 +116,19 @@ impl<G: NodeIndexable> WithDummy for G {
125116
fn node_bound_with_dummy(&self) -> usize {
126117
self.node_bound() + 1
127118
}
119+
120+
fn try_from_index(self: &Self, i: usize) -> Option<Self::NodeId> {
121+
if i != self.dummy_idx() {
122+
Some(self.from_index(i))
123+
} else {
124+
None
125+
}
126+
}
128127
}
129128

130129
pub struct MatchedNodes<'a, G: GraphBase> {
131130
graph: &'a G,
132-
mate: &'a [G::NodeId],
131+
mate: &'a [Option<G::NodeId>],
133132
current: usize,
134133
}
135134

@@ -144,7 +143,7 @@ where
144143
let current = self.current;
145144
self.current += 1;
146145

147-
if self.mate[current] != self.graph.dummy() {
146+
if self.mate[current].is_some() {
148147
return Some(self.graph.from_index(current));
149148
}
150149
}
@@ -155,7 +154,7 @@ where
155154

156155
pub struct MatchedEdges<'a, G: GraphBase> {
157156
graph: &'a G,
158-
mate: &'a [G::NodeId],
157+
mate: &'a [Option<G::NodeId>],
159158
current: usize,
160159
}
161160

@@ -170,14 +169,14 @@ where
170169
let current = self.current;
171170
self.current += 1;
172171

173-
let mate = self.mate[current];
174-
175-
// Check if the mate is a node after the current one. If not, then
176-
// do not report that edge since it has been already reported (the
177-
// graph is considered undirected).
178-
if mate != self.graph.dummy() && self.graph.to_index(mate) > current {
179-
let this = self.graph.from_index(current);
180-
return Some((this, mate));
172+
if let Some(mate) = self.mate[current] {
173+
// Check if the mate is a node after the current one. If not, then
174+
// do not report that edge since it has been already reported (the
175+
// graph is considered undirected).
176+
if self.graph.to_index(mate) > current {
177+
let this = self.graph.from_index(current);
178+
return Some((this, mate));
179+
}
181180
}
182181
}
183182

@@ -204,15 +203,16 @@ where
204203
G::NodeId: Eq + Hash,
205204
G::EdgeId: Eq + Hash,
206205
{
207-
let (mate, n_edges) = greedy_matching_inner(&graph);
208-
Matching::new(graph, mate, n_edges)
206+
let (mates, n_edges) = greedy_matching_inner(&graph);
207+
Matching::new(graph, mates, n_edges)
209208
}
210209

211-
fn greedy_matching_inner<G>(graph: &G) -> (Vec<G::NodeId>, usize)
210+
#[inline]
211+
fn greedy_matching_inner<G>(graph: &G) -> (Vec<Option<G::NodeId>>, usize)
212212
where
213213
G: Visitable + IntoNodeIdentifiers + NodeIndexable + IntoNeighbors,
214214
{
215-
let mut mate = vec![graph.dummy(); graph.node_bound()];
215+
let mut mate = vec![None; graph.node_bound()];
216216
let mut n_edges = 0;
217217
let visited = &mut graph.visit_map();
218218

@@ -224,8 +224,8 @@ where
224224
non_backtracking_dfs(graph, start, visited, |next| {
225225
// Alternate matched and unmatched edges.
226226
if let Some(pred) = last.take() {
227-
mate[graph.to_index(pred)] = next;
228-
mate[graph.to_index(next)] = pred;
227+
mate[graph.to_index(pred)] = Some(next);
228+
mate[graph.to_index(next)] = Some(pred);
229229
n_edges += 1;
230230
} else {
231231
last = Some(next);
@@ -327,6 +327,8 @@ impl<G: GraphBase> PartialEq for Label<G> {
327327
/// *O(|V|³)*. An algorithm with a better time complexity might be used in the
328328
/// future.
329329
///
330+
/// **Panics** if `g.node_bound()` is `std::usize::MAX`.
331+
///
330332
/// # Examples
331333
///
332334
/// ```
@@ -362,22 +364,29 @@ pub fn maximum_matching<G>(graph: G) -> Matching<G>
362364
where
363365
G: Visitable + NodeIndexable + IntoNodeIdentifiers + IntoEdges,
364366
{
367+
// The dummy identifier needs an unused index
368+
assert_ne!(
369+
graph.node_bound(),
370+
std::usize::MAX,
371+
"The input graph capacity should be strictly less than std::usize::MAX."
372+
);
373+
365374
// Greedy algorithm should create a fairly good initial matching. The hope
366375
// is that it speeds up the computation by doing les work in the complex
367376
// algorithm.
368377
let (mut mate, mut n_edges) = greedy_matching_inner(&graph);
369378

370379
// Gabow's algorithm uses a dummy node in the mate array.
371-
mate.push(graph.dummy());
372-
373-
let len = graph.node_bound_with_dummy();
380+
mate.push(None);
381+
let len = graph.node_bound() + 1;
374382
debug_assert_eq!(mate.len(), len);
383+
375384
let mut label: Vec<Label<G>> = vec![Label::None; len];
376385
let mut first_inner = vec![std::usize::MAX; len];
377386
let visited = &mut graph.visit_map();
378387

379388
for start in 0..graph.node_bound() {
380-
if mate[start] != graph.dummy() {
389+
if mate[start].is_some() {
381390
// The vertex is already matched. A start must be a free vertex.
382391
continue;
383392
}
@@ -387,6 +396,7 @@ where
387396
first_inner[start] = graph.dummy_idx();
388397
graph.reset_map(visited);
389398

399+
// start is never a dummy index
390400
let start = graph.from_index(start);
391401

392402
// Queue will contain outer vertices that should be processed next. The
@@ -406,13 +416,13 @@ where
406416
let other_vertex = edge.target();
407417
let other_idx = graph.to_index(other_vertex);
408418

409-
if mate[other_idx] == graph.dummy() && other_vertex != start {
419+
if mate[other_idx].is_none() && other_vertex != start {
410420
// An augmenting path was found. Augment the matching. If
411421
// `other` is actually the start node, then the augmentation
412422
// must not be performed, because the start vertex would be
413423
// incident to two edges, which violates the matching
414424
// property.
415-
mate[other_idx] = outer_vertex;
425+
mate[other_idx] = Some(outer_vertex);
416426
augment_path(&graph, outer_vertex, other_vertex, &mut mate, &label);
417427
n_edges += 1;
418428

@@ -438,7 +448,7 @@ where
438448
);
439449
} else {
440450
let mate_vertex = mate[other_idx];
441-
let mate_idx = graph.to_index(mate_vertex);
451+
let mate_idx = mate_vertex.map_or(graph.dummy_idx(), |id| graph.to_index(id));
442452

443453
if label[mate_idx].is_inner() {
444454
// Mate of `other` vertex is inner (no label has been
@@ -452,10 +462,12 @@ where
452462
first_inner[mate_idx] = other_idx;
453463
}
454464

455-
if visited.visit(mate_vertex) {
456-
// Add the vertex to the queue only if this is its first
457-
// discovery.
458-
queue.push_back(mate_vertex);
465+
// Add the vertex to the queue only if it's not the dummy and this is its first
466+
// discovery.
467+
if let Some(mate_vertex) = mate_vertex {
468+
if visited.visit(mate_vertex) {
469+
queue.push_back(mate_vertex);
470+
}
459471
}
460472
}
461473
}
@@ -476,7 +488,7 @@ where
476488
fn find_join<G, F>(
477489
graph: &G,
478490
edge: G::EdgeRef,
479-
mate: &Vec<G::NodeId>,
491+
mate: &Vec<Option<G::NodeId>>,
480492
label: &mut Vec<Label<G>>,
481493
first_inner: &mut Vec<usize>,
482494
mut visitor: F,
@@ -513,7 +525,10 @@ fn find_join<G, F>(
513525
}
514526

515527
// Set left to the next inner vertex in P(source) or P(target).
516-
left = first_inner[graph.to_index(label[graph.to_index(mate[left])].to_vertex().unwrap())];
528+
// The unwraps are safe because left is not the dummy node.
529+
let left_mate = graph.to_index(mate[left].unwrap());
530+
let next_inner = label[left_mate].to_vertex().unwrap();
531+
left = first_inner[graph.to_index(next_inner)];
517532

518533
if !label[left].is_flagged(edge.id()) {
519534
// The inner vertex is not flagged yet, so flag it.
@@ -530,12 +545,15 @@ fn find_join<G, F>(
530545
let mut inner = first_inner[endpoint];
531546
while inner != join {
532547
// Notify the caller about labeling a vertex.
533-
visitor(graph.from_index(inner));
548+
if let Some(ix) = graph.try_from_index(inner) {
549+
visitor(ix);
550+
}
534551

535552
label[inner] = Label::Edge(edge.id(), [edge.source(), edge.target()]);
536553
first_inner[inner] = join;
537-
inner = first_inner
538-
[graph.to_index(label[graph.to_index(mate[inner])].to_vertex().unwrap())];
554+
let inner_mate = graph.to_index(mate[inner].unwrap());
555+
let next_inner = label[inner_mate].to_vertex().unwrap();
556+
inner = first_inner[graph.to_index(next_inner)];
539557
}
540558
}
541559

@@ -555,27 +573,29 @@ fn augment_path<G>(
555573
graph: &G,
556574
outer: G::NodeId,
557575
other: G::NodeId,
558-
mate: &mut Vec<G::NodeId>,
576+
mate: &mut Vec<Option<G::NodeId>>,
559577
label: &Vec<Label<G>>,
560578
) where
561579
G: NodeIndexable,
562580
{
563581
let outer_idx = graph.to_index(outer);
564582

565583
let temp = mate[outer_idx];
566-
let temp_idx = graph.to_index(temp);
567-
mate[outer_idx] = other;
584+
let temp_idx = temp.map_or(graph.dummy_idx(), |id| graph.to_index(id));
585+
mate[outer_idx] = Some(other);
568586

569-
if mate[temp_idx] != outer {
587+
if mate[temp_idx] != Some(outer) {
570588
// We are at the end of the path and so the entire path is completely
571589
// rematched/augmented.
572590
return;
573591
} else if let Label::Vertex(vertex) = label[outer_idx] {
574592
// The outer vertex has a vertex label which refers to another outer
575593
// vertex on the path. So we set this another outer node as the mate for
576594
// the previous mate of the outer node.
577-
mate[temp_idx] = vertex;
578-
augment_path(graph, vertex, temp, mate, label);
595+
mate[temp_idx] = Some(vertex);
596+
if let Some(temp) = temp {
597+
augment_path(graph, vertex, temp, mate, label);
598+
}
579599
} else if let Label::Edge(_, [source, target]) = label[outer_idx] {
580600
// The outer vertex has an edge label which refers to an edge in a
581601
// blossom. We need to augment both directions along the blossom.

0 commit comments

Comments
 (0)