Graph.h Source File (original) (raw)

27 public:

33 return std::numeric_limits::max();

34 }

38 return std::numeric_limits::max();

39 }

40 };

47 private:

48 using CostAllocator = typename SolverT::CostAllocator;

50 public:

51 using RawVector = typename SolverT::RawVector;

52 using RawMatrix = typename SolverT::RawMatrix;

53 using Vector = typename SolverT::Vector;

54 using Matrix = typename SolverT::Matrix;

55 using VectorPtr = typename CostAllocator::VectorPtr;

56 using MatrixPtr = typename CostAllocator::MatrixPtr;

61 private:

62 class NodeEntry {

63 public:

64 using AdjEdgeList = std::vector;

65 using AdjEdgeIdx = AdjEdgeList::size_type;

66 using AdjEdgeItr = AdjEdgeList::const_iterator;

68 NodeEntry(VectorPtr Costs) : Costs(std::move(Costs)) {}

70 static AdjEdgeIdx getInvalidAdjEdgeIdx() {

71 return std::numeric_limits::max();

72 }

74 AdjEdgeIdx addAdjEdgeId(EdgeId EId) {

75 AdjEdgeIdx Idx = AdjEdgeIds.size();

76 AdjEdgeIds.push_back(EId);

77 return Idx;

78 }

80 void removeAdjEdgeId(Graph &G, NodeId ThisNId, AdjEdgeIdx Idx) {

87 G.getEdge(AdjEdgeIds.back()).setAdjEdgeIdx(ThisNId, Idx);

88 AdjEdgeIds[Idx] = AdjEdgeIds.back();

89 AdjEdgeIds.pop_back();

90 }

92 const AdjEdgeList& getAdjEdgeIds() const { return AdjEdgeIds; }

97 private:

98 AdjEdgeList AdjEdgeIds;

99 };

100

101 class EdgeEntry {

102 public:

103 EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs)

104 : Costs(std::move(Costs)) {

105 NIds[0] = N1Id;

106 NIds[1] = N2Id;

107 ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx();

108 ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx();

109 }

110

111 void connectToN(Graph &G, EdgeId ThisEdgeId, unsigned NIdx) {

112 assert(ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() &&

113 "Edge already connected to NIds[NIdx].");

114 NodeEntry &N = G.getNode(NIds[NIdx]);

115 ThisEdgeAdjIdxs[NIdx] = N.addAdjEdgeId(ThisEdgeId);

116 }

117

118 void connect(Graph &G, EdgeId ThisEdgeId) {

119 connectToN(G, ThisEdgeId, 0);

120 connectToN(G, ThisEdgeId, 1);

121 }

122

123 void setAdjEdgeIdx(NodeId NId, typename NodeEntry::AdjEdgeIdx NewIdx) {

124 if (NId == NIds[0])

125 ThisEdgeAdjIdxs[0] = NewIdx;

126 else {

127 assert(NId == NIds[1] && "Edge not connected to NId");

128 ThisEdgeAdjIdxs[1] = NewIdx;

129 }

130 }

131

132 void disconnectFromN(Graph &G, unsigned NIdx) {

133 assert(ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() &&

134 "Edge not connected to NIds[NIdx].");

135 NodeEntry &N = G.getNode(NIds[NIdx]);

136 N.removeAdjEdgeId(G, NIds[NIdx], ThisEdgeAdjIdxs[NIdx]);

137 ThisEdgeAdjIdxs[NIdx] = NodeEntry::getInvalidAdjEdgeIdx();

138 }

139

141 if (NId == NIds[0])

142 disconnectFromN(G, 0);

143 else {

144 assert(NId == NIds[1] && "Edge does not connect NId");

145 disconnectFromN(G, 1);

146 }

147 }

148

149 NodeId getN1Id() const { return NIds[0]; }

150 NodeId getN2Id() const { return NIds[1]; }

151

154

155 private:

157 typename NodeEntry::AdjEdgeIdx ThisEdgeAdjIdxs[2];

158 };

159

160

161

163 CostAllocator CostAlloc;

164 SolverT *Solver = nullptr;

165

166 using NodeVector = std::vector;

167 using FreeNodeVector = std::vector;

168 NodeVector Nodes;

169 FreeNodeVector FreeNodeIds;

170

171 using EdgeVector = std::vector;

172 using FreeEdgeVector = std::vector;

173 EdgeVector Edges;

174 FreeEdgeVector FreeEdgeIds;

175

177

178

179

180 NodeEntry &getNode(NodeId NId) {

181 assert(NId < Nodes.size() && "Out of bound NodeId");

182 return Nodes[NId];

183 }

184 const NodeEntry &getNode(NodeId NId) const {

185 assert(NId < Nodes.size() && "Out of bound NodeId");

186 return Nodes[NId];

187 }

188

189 EdgeEntry& getEdge(EdgeId EId) { return Edges[EId]; }

190 const EdgeEntry& getEdge(EdgeId EId) const { return Edges[EId]; }

191

192 NodeId addConstructedNode(NodeEntry N) {

194 if (!FreeNodeIds.empty()) {

195 NId = FreeNodeIds.back();

196 FreeNodeIds.pop_back();

197 Nodes[NId] = std::move(N);

198 } else {

199 NId = Nodes.size();

200 Nodes.push_back(std::move(N));

201 }

202 return NId;

203 }

204

205 EdgeId addConstructedEdge(EdgeEntry E) {

207 "Attempt to add duplicate edge.");

209 if (!FreeEdgeIds.empty()) {

210 EId = FreeEdgeIds.back();

211 FreeEdgeIds.pop_back();

212 Edges[EId] = std::move(E);

213 } else {

214 EId = Edges.size();

215 Edges.push_back(std::move(E));

216 }

217

218 EdgeEntry &NE = getEdge(EId);

219

220

221 NE.connect(*this, EId);

222 return EId;

223 }

224

225 void operator=(const Graph &Other) {}

226

227 public:

228 using AdjEdgeItr = typename NodeEntry::AdjEdgeItr;

229

231 public:

237

239 : CurNId(CurNId), EndNId(G.Nodes.size()), FreeNodeIds(G.FreeNodeIds) {

240 this->CurNId = findNextInUse(CurNId);

241 }

242

247

248 private:

250 while (NId < EndNId && is_contained(FreeNodeIds, NId)) {

251 ++NId;

252 }

253 return NId;

254 }

255

256 NodeId CurNId, EndNId;

257 const FreeNodeVector &FreeNodeIds;

258 };

259

261 public:

263 : CurEId(CurEId), EndEId(G.Edges.size()), FreeEdgeIds(G.FreeEdgeIds) {

264 this->CurEId = findNextInUse(CurEId);

265 }

266

271

272 private:

274 while (EId < EndEId && is_contained(FreeEdgeIds, EId)) {

275 ++EId;

276 }

277 return EId;

278 }

279

280 EdgeId CurEId, EndEId;

281 const FreeEdgeVector &FreeEdgeIds;

282 };

283

285 public:

287

290

291 bool empty() const { return G.Nodes.empty(); }

292

293 typename NodeVector::size_type size() const {

294 return G.Nodes.size() - G.FreeNodeIds.size();

295 }

296

297 private:

298 const Graph& G;

299 };

300

302 public:

304

307

308 bool empty() const { return G.Edges.empty(); }

309

310 typename NodeVector::size_type size() const {

311 return G.Edges.size() - G.FreeEdgeIds.size();

312 }

313

314 private:

315 const Graph& G;

316 };

317

319 public:

321

322 typename NodeEntry::AdjEdgeItr begin() const {

323 return NE.getAdjEdgeIds().begin();

324 }

325

326 typename NodeEntry::AdjEdgeItr end() const {

327 return NE.getAdjEdgeIds().end();

328 }

329

330 bool empty() const { return NE.getAdjEdgeIds().empty(); }

331

332 typename NodeEntry::AdjEdgeList::size_type size() const {

333 return NE.getAdjEdgeIds().size();

334 }

335

336 private:

337 const NodeEntry &NE;

338 };

339

340

342

343

345

346

348

349

351

352

353

354

355

357 assert(!Solver && "Solver already set. Call unsetSolver().");

358 Solver = &S;

359 for (auto NId : nodeIds())

360 Solver->handleAddNode(NId);

361 for (auto EId : edgeIds())

362 Solver->handleAddEdge(EId);

363 }

364

365

367 assert(Solver && "Solver not set.");

368 Solver = nullptr;

369 }

370

371

372

373

374 template

376

377 VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));

378 NodeId NId = addConstructedNode(NodeEntry(AllocatedCosts));

379 if (Solver)

380 Solver->handleAddNode(NId);

381 return NId;

382 }

383

384

385

386

387

388

389

390

391

392

393

394

395 template

397 NodeId NId = addConstructedNode(NodeEntry(Costs));

398 if (Solver)

399 Solver->handleAddNode(NId);

400 return NId;

401 }

402

403

404

405

406

407

408 template

411 getNodeCosts(N2Id).getLength() == Costs.getCols() &&

412 "Matrix dimensions mismatch.");

413

414 MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));

415 EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, AllocatedCosts));

416 if (Solver)

417 Solver->handleAddEdge(EId);

418 return EId;

419 }

420

421

422

423

424

425

426

427

428

429

430

431

432

433 template

435 OtherMatrixPtrT Costs) {

437 getNodeCosts(N2Id).getLength() == Costs->getCols() &&

438 "Matrix dimensions mismatch.");

439

440 EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, Costs));

441 if (Solver)

442 Solver->handleAddEdge(EId);

443 return EId;

444 }

445

446

447 bool empty() const { return NodeIdSet(*this).empty(); }

448

449 NodeIdSet nodeIds() const { return NodeIdSet(*this); }

450 EdgeIdSet edgeIds() const { return EdgeIdSet(*this); }

451

452 AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); }

453

454

455

456 unsigned getNumNodes() const { return NodeIdSet(*this).size(); }

457

458

459

460 unsigned getNumEdges() const { return EdgeIdSet(*this).size(); }

461

462

463

464

465 template

467 VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));

468 if (Solver)

469 Solver->handleSetNodeCosts(NId, *AllocatedCosts);

470 getNode(NId).Costs = AllocatedCosts;

471 }

472

473

474

475

476

477

478

479

480

482 return getNode(NId).Costs;

483 }

484

485

486

487

491

493 return getNode(NId).Metadata;

494 }

495

497 return getNode(NId).Metadata;

498 }

499

501 return getNode(NId).getAdjEdgeIds().size();

502 }

503

504

505

506

507 template

509 MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));

510 if (Solver)

511 Solver->handleUpdateCosts(EId, *AllocatedCosts);

512 getEdge(EId).Costs = AllocatedCosts;

513 }

514

515

516

517

518

519

520

521

522

524 return getEdge(EId).Costs;

525 }

526

527

528

529

531 return *getEdge(EId).Costs;

532 }

533

535 return getEdge(EId).Metadata;

536 }

537

539 return getEdge(EId).Metadata;

540 }

541

542

543

544

546 return getEdge(EId).getN1Id();

547 }

548

549

550

551

553 return getEdge(EId).getN2Id();

554 }

555

556

557

558

559

561 EdgeEntry &E = getEdge(EId);

562 if (E.getN1Id() == NId) {

563 return E.getN2Id();

564 }

565 return E.getN1Id();

566 }

567

568

569

570

571

572

577 return AEId;

578 }

579 }

581 }

582

583

584

586 if (Solver)

587 Solver->handleRemoveNode(NId);

588 NodeEntry &N = getNode(NId);

589

590 for (AdjEdgeItr AEItr = N.adjEdgesBegin(),

591 AEEnd = N.adjEdgesEnd();

592 AEItr != AEEnd;) {

594 ++AEItr;

596 }

597 FreeNodeIds.push_back(NId);

598 }

599

600

601

602

603

604

605

606

607

608

609

610

611

612

613

614

615

616

617

618

619

620

621

622

623

624

626 if (Solver)

627 Solver->handleDisconnectEdge(EId, NId);

628

629 EdgeEntry &E = getEdge(EId);

630 E.disconnectFrom(*this, NId);

631 }

632

633

634

639

640

641

642

643

645 EdgeEntry &E = getEdge(EId);

646 E.connectTo(*this, EId, NId);

647 if (Solver)

648 Solver->handleReconnectEdge(EId, NId);

649 }

650

651

652

654 if (Solver)

655 Solver->handleRemoveEdge(EId);

656 EdgeEntry &E = getEdge(EId);

657 E.disconnect();

658 FreeEdgeIds.push_back(EId);

659 Edges[EId].invalidate();

660 }

661

662

664 Nodes.clear();

665 FreeNodeIds.clear();

666 Edges.clear();

667 FreeEdgeIds.clear();

668 }

669 };