Elementa v8.0.0
Minimalistic library for any C++ application (C++11 and up)
Loading...
Searching...
No Matches
graph_search.h
Go to the documentation of this file.
1
3#include "elementa/license.inc"
4#include "elementa/checks.inc"
5
6#ifndef ELEMENTA_ADTS_GRAPH_SEARCH_H
7#define ELEMENTA_ADTS_GRAPH_SEARCH_H
8
9#define ELE_PRE_TRACED
10
11#include <string>
12#include <algorithm>
13#include "elementa/base/debugging.h"
14#include "elementa/base/exceptions.h"
15#include "elementa/adts/graphs/graphs.h"
16#include "elementa/adts/graphs/graph_paths.h"
17
18
19namespace elementa
20{
21
22namespace adts
23{
24
25namespace graphs
26{
27
48/* ===========================================================================
49
50 SEARCHING ANY PATH
51
52============================================================================= */
53
54
55/* ***************************************************************************
56
57 Template class: AllPathsVertices
58
59*******************************************************************************/
60
62
66template <class Vertex, class Edge, GPathKind KIND>
67class AllPathsVertices
68{
69 public:
70
75 using GraphType = Graph<Vertex,Edge>;
76
78 using PathType = GPath<Vertex,Edge,KIND>;
79
87
95 AllPathsVertices(const GraphType & gr,
96 const typename GraphType::viterator & vit0,
97 const typename GraphType::viterator & vit1,
98 bool detectcycles = true,
99 const typename GraphType::EPred & epred =
100 GraphType::trivial_epred);
101
102 AllPathsVertices(const AllPathsVertices &) = delete;
103 AllPathsVertices(AllPathsVertices &&) = delete;
104 AllPathsVertices & operator=(const AllPathsVertices &) = delete;
105 AllPathsVertices & operator=(AllPathsVertices &&) = delete;
106
114 bool found(void) const noexcept { return(!isend_); }
115
117 bool next(void) { return(isend_ ? false :
118 next_hidden(GPathKindType<KIND>{})); }
119
121
122 const PathType & current(void) const
123 { checkEnd(ELE_CODE_PLACE); return(curpath_); }
124
127 private:
128
129 const GraphType * g_;
130 const typename GraphType::viterator vit0_,vit1_;
131 const typename GraphType::EPred * epred_;
132 bool detectcycles_;
133 PathType curpath_;
134 bool isend_;
135 typename GraphType::eiterator eend_, eit_;
136
137 void checkEnd(const std::string & place) const;
138 bool isACycle(const typename GraphType::viterator & v,
139 GPathKindType<GPathKind::kVertexPath>) const;
140 bool isACycle(const typename GraphType::viterator & v,
141 GPathKindType<GPathKind::kEdgePath>) const;
142 void doBacktrack(void);
143 void nextEdge(void);
144 void constr_hidden(const typename GraphType::viterator & v0,
145 GPathKindType<GPathKind::kVertexPath>);
146 void constr_hidden(const typename GraphType::viterator & v0,
147 GPathKindType<GPathKind::kEdgePath>);
148 bool next_hidden(GPathKindType<GPathKind::kVertexPath>);
149 bool next_hidden(GPathKindType<GPathKind::kEdgePath>);
150};
151
152
153
154/* ===========================================================================
155
156 SEARCHING SHORTEST PATHS
157
158============================================================================= */
159
160
161/* ***************************************************************************
162
163 Template class: FloydWarshall
164
165*******************************************************************************/
166
168
181template <class Vertex, class Edge, class Weight = double>
182class FloydWarshall
183{
184 public:
185
187 using Gr = Graph<Vertex,Edge>;
188
190
197 FloydWarshall(const Gr & g,
198 const EdgeWeightFunction<Vertex,Edge,Weight> & w =
199 trivial_edge_weight<Vertex,Edge>,
200 const typename Gr::MapOfVItPos * mpos = nullptr,
201 const typename Gr::EPred & epred = Gr::trivial_epred);
202
204 FloydWarshall(FloydWarshall &&);
205
206 FloydWarshall & operator=(FloydWarshall &&) = delete;
207 FloydWarshall(const FloydWarshall &) = delete;
208 FloydWarshall & operator=(const FloydWarshall &) = delete;
209
211 ~FloydWarshall(void) { clean(); }
212
213
215 const typename Gr::MapOfVItPos & mapOfVPoses(void) const {return(*posmap_);}
216
218 bool filled(void) const noexcept { return(distMatrix_ != nullptr); }
219
221
224 bool shortest(const typename Gr::viterator vit0,
225 const typename Gr::viterator vit1,
226 Weight & d) const;
227
229
233 bool shortest(const typename Gr::viterator vit0,
234 const typename Gr::viterator vit1,
235 Weight & d,
236 GPath<Vertex,Edge,GPathKind::kVertexPath> & path) const;
237
239
244 private:
245
246 size_vertex V_;
247 size_t V2Size_;
248
249 Weight * distMatrix_;
250 std::vector<bool> infs_;
251 typename Graph<Vertex,Edge>::viterator * nextMatrix_;
252 typename Gr::MapOfVItPos * posmap_;
253 bool ownposmap_;
254
255 void clean(void);
256 size_t offset(size_vertex i, size_vertex j) const noexcept
257 { return(static_cast<size_t>(i) * static_cast<size_t>(V_) +
258 static_cast<size_t>(j)); }
259 void indexes(const typename Gr::viterator vit0,
260 const typename Gr::viterator vit1,
261 size_vertex & i, size_vertex & j) const;
262 void checkCalcs(void) const
263 { if (!filled())
264 ELE_CODE_INVSTATE("No shortest path calculated previously"); }
265
266};
267
268
269
270/* ===========================================================================
271
272 ========== IMPLEMENTATION OF TEMPLATES ===========
273
274============================================================================= */
275
276
277/* ***************************************************************************
278
279 Template class: AllPathsVertices
280
281*******************************************************************************/
282
283template <class Vertex, class Edge, GPathKind KIND>
284AllPathsVertices<Vertex,Edge,KIND>::AllPathsVertices(
285 const GraphType & gr,
286 const typename GraphType::viterator & vit0,
287 const typename GraphType::viterator & vit1,
288 bool detectcycles,
289 const typename GraphType::EPred & epred):
290 g_{&gr},vit0_{vit0},vit1_{vit1},
291 detectcycles_{detectcycles},
292 epred_{&epred},isend_{false}
293{ELE_CODE_TRACE_OFF;
294
295 auto r = gr.erangeDepthFirst(vit0);
296 eend_ = r.end();
297 eit_ = gr.erangeDepthFirst(vit0).begin();
298 if (eit_ == eend_)
299 {
300 ELE_CODE_TRACEPOINT;
301 isend_ = true;
302 }
303 else constr_hidden(vit0_,GPathKindType<KIND>{});
304 // substitute partial method specialization by overloading
305 ELE_CODE_TRACE({},"isend_: " << isend_);
306}
307
308template <class Vertex, class Edge, GPathKind KIND>
309void AllPathsVertices<Vertex,Edge,KIND>::
310checkEnd(const std::string & place) const
311{
312 if (isend_)
313 throw(elementa::base::invstate{"No more paths"}.asEXC(place));
314}
315
316// Check whether there is a cycle in the current path to node V
317// version for vertex paths
318template <class Vertex, class Edge, GPathKind KIND>
319bool AllPathsVertices<Vertex,Edge,KIND>::isACycle
320 (const typename GraphType::viterator & v,
321 GPathKindType<GPathKind::kVertexPath>) const
322{/*ELE_CODE_TRACE_OFF;
323
324 ELE_CODE_TRACE({},"Checking cycle of " << std::to_string(*v) << " against "
325 "path " << curpath_.to_string(*g_)); // only works with
326 // paths with
327 // std::to_string()
328 // in vertices/edges
329*/ for (const auto & vit : curpath_)
330 if (vit == v) return(true);
331 return(false);
332}
333
334// Check whether there is a cycle in the current path to node V
335// version for edge paths
336template <class Vertex, class Edge, GPathKind KIND>
337bool AllPathsVertices<Vertex,Edge,KIND>::isACycle
338 (const typename GraphType::viterator & v,
339 GPathKindType<GPathKind::kEdgePath>) const
340{
341 bool first{true};
342 typename GraphType::viterator vo,vd;
343 for (const auto & eit : curpath_)
344 {
345 g_->connection(eit,vo,vd);
346 if (first)
347 {
348 if (vo == v) return(true);
349 first = false;
350 }
351 if (vd == v) return(true);
352 }
353 return(false);
354}
355
356// Do backtrack and adjust path
357template <class Vertex, class Edge, GPathKind KIND>
358void AllPathsVertices<Vertex,Edge,KIND>::doBacktrack(void)
359{//ELE_CODE_TRACE_OFF;
360
361 auto howmanyback = GraphType::ERange_DepthFirst::forceBacktrack(eit_);
362/* ELE_CODE_TRACE({},"backtracking " << howmanyback <<
363 " with path " << curpath_.to_string(*g_) <<
364 (eit_ == eend_ ? " cannot backtrack any more" :
365 ", successfully")); // only works with
366 // paths with
367 // std::to_string()
368 // in vertices/edges*/
369 if (eit_ == eend_)
370 {
371 isend_ = true;
372 return;
373 }
374 curpath_.resize(curpath_.size()-howmanyback); // drop what backtracked
375}
376
377// Find next edge for the path (path not completed yet); do not add it to path
378template <class Vertex, class Edge, GPathKind KIND>
379void AllPathsVertices<Vertex,Edge,KIND>::nextEdge(void)
380{
381 if (isend_) return;
382 auto eit{eit_};
383 ++eit;
384 if (eit == eend_) doBacktrack();
385 eit_ = eit;
386 typename GraphType::viterator vo,vd;
387 g_->connection(eit_,vo,vd);
388 if (vd == vit1_) return; // complete path found
389 if ((detectcycles_)&&(isACycle(vd,GPathKindType<KIND>{}))) doBacktrack();
390}
391
392// Create for vertex paths. Eit_ is the first edge and is not end
393template <class Vertex, class Edge, GPathKind KIND>
394void AllPathsVertices<Vertex,Edge,KIND>::constr_hidden(
395 const typename GraphType::viterator & v0,
396 GPathKindType<GPathKind::kVertexPath>)
397{ELE_CODE_TRACE_OFF;
398
399 ELE_CODE_TRACEPOINT;
400 curpath_.push_back(v0);
401 typename GraphType::viterator vo,vd;
402 do
403 {
404 g_->connection(eit_,vo,vd);
405/* ELE_CODE_TRACE({},"\tCurrent path: " << curpath_.to_string(*g_) <<
406 ", current edge from " << std::to_string(*vo) <<
407 " to " << std::to_string(*vd)); // only works with
408 // paths with
409 // std::to_string()
410 // in vertices/edges
411*/ ELE_CODE_PAUSE({},"");
412 if (vd == vit1_)
413 {
414 curpath_.push_back(vd);
415 return; // 1st path already completed
416 }
417 if ((detectcycles_)&&(isACycle(vd,GPathKindType<KIND>{})))
418 {
419 curpath_.push_back(vd);
420 doBacktrack();
421 if (isend_) return; // no path
422 }
423 else
424 {
425 curpath_.push_back(vd);
426 ++eit_;
427 if (eit_ == eend_)
428 {
429 doBacktrack();
430 if (isend_) return; // no path
431 }
432 }
433 } while (1);
434}
435
436// Inc for vertex paths.
437template <class Vertex, class Edge, GPathKind KIND>
438bool AllPathsVertices<Vertex,Edge,KIND>::next_hidden(
439 GPathKindType<GPathKind::kVertexPath>)
440{
441 doBacktrack();
442 if (isend_) return(false); // no more paths
443 typename GraphType::viterator vo,vd;
444 g_->connection(eit_,vo,vd);
445 curpath_.pop_back(); // to add vo without duplications in the next call:
446 constr_hidden(vo,GPathKindType<GPathKind::kVertexPath>{});
447 return(!isend_);
448}
449
450// Create for edge paths. Eit_ is the first edge and is not end
451template <class Vertex, class Edge, GPathKind KIND>
452void AllPathsVertices<Vertex,Edge,KIND>::constr_hidden(
453 const typename GraphType::viterator & v0,
454 GPathKindType<GPathKind::kEdgePath>)
455{
456 typename GraphType::viterator vo,vd;
457 do
458 {
459 g_->connection(eit_,vo,vd);
460 if (vd == vit1_)
461 {
462 curpath_.push_back(eit_);
463 return; // 1st path already completed
464 }
465 if ((detectcycles_)&&(isACycle(vd,GPathKindType<KIND>{})))
466 {
467 curpath_.push_back(eit_);
468 doBacktrack();
469 if (isend_) return; // no path
470 }
471 else
472 {
473 curpath_.push_back(eit_);
474 ++eit_;
475 if (eit_ == eend_)
476 {
477 doBacktrack();
478 if (isend_) return; // no path
479 }
480 }
481 } while (1);
482}
483
484// Inc for edge paths
485template <class Vertex, class Edge, GPathKind KIND>
486bool AllPathsVertices<Vertex,Edge,KIND>::next_hidden(
487 GPathKindType<GPathKind::kEdgePath>)
488{
489 doBacktrack();
490 if (isend_) return(false); // no more paths
491 constr_hidden(vit0_,GPathKindType<GPathKind::kEdgePath>{});
492 return(!isend_);
493}
494
495
496/* ***************************************************************************
497
498 Template class: FloydWarshall
499
500*******************************************************************************/
501
502template <class Vertex, class Edge, class Weight>
503void FloydWarshall<Vertex,Edge,Weight>::clean(void)
504{ELE_CODE_TRACE_OFF;
505
506 ELE_CODE_TRACE({},"Cleaning Floyd-Warshall");
507 if (ownposmap_) delete posmap_;
508 if (distMatrix_ != nullptr) delete [] distMatrix_;
509 if (nextMatrix_ != nullptr) delete [] nextMatrix_;
510 posmap_ = nullptr;
511 ownposmap_ = false;
512 distMatrix_ = nullptr;
513 infs_.clear();
514 nextMatrix_ = nullptr;
515}
516
517template <class Vertex, class Edge, class Weight>
518void FloydWarshall<Vertex,Edge,Weight>::
519 indexes(const typename Gr::viterator vit0,
520 const typename Gr::viterator vit1,
521 size_vertex & i, size_vertex & j) const
522{
523 checkCalcs();
524
525 i = posmap_->at(vit0);
526 if (vit0 == vit1) j = i;
527 else j = posmap_->at(vit1);
528}
529
530template <class Vertex, class Edge, class Weight>
531FloydWarshall<Vertex,Edge,Weight>::
532 FloydWarshall(const Gr & g,
533 const EdgeWeightFunction<Vertex,Edge,Weight> & w,
534 const typename Gr::MapOfVItPos * mpos,
535 const typename Gr::EPred & epred):
536 V_{0},V2Size_{0},
537 distMatrix_{nullptr},
538 nextMatrix_{nullptr},
539 posmap_{nullptr},
540 ownposmap_{false}
541{ELE_CODE_TRACE_OFF;
542
543 if (g.size_edges() == 0) return;
544 V_ = g.size_vertices();
545 V2Size_ = static_cast<size_t>(V_) * static_cast<size_t>(V_);
546 ELE_CODE_TRACE({},"Creating FLoyd-Warshall for " << g.size_vertices() <<
547 " vertices and " << g.size_edges() << " edges, V2Size_: "
548 << V2Size_);
549
550 distMatrix_ = new double[V2Size_];
551 infs_ = std::vector<bool>(V2Size_,true);
552 nextMatrix_ = new typename Gr::viterator[V2Size_];
553 std::fill(nextMatrix_,nextMatrix_ + V2Size_, g.vrangeAll().end());
554
555 // calculate position map if needed
556 posmap_ = const_cast<typename Gr::MapOfVItPos *>(mpos);
557 // we will not change the content
558 if (mpos == nullptr)
559 {
560 posmap_ = new typename Gr::MapOfVItPos{g};
561 ownposmap_ = true;
562 }
563
564 try
565 {
566 ELE_CODE_TRACE({},"Initiating matrices with V = " << V_);
567 // initiate matrices
568 auto eit = g.erangeAll().begin();
569 typename Gr::viterator vit0,vit1;
570 size_vertex pos0,pos1;
571 size_t offs;
572 while (eit != g.erangeAll().end())
573 {
574 if (epred(*eit))
575 {
576 g.connection(eit,vit0,vit1);
577 pos0 = posmap_->at(vit0);
578 pos1 = posmap_->at(vit1);
579 offs = offset(pos0,pos1);
580 infs_[offs] = false;
581 distMatrix_[offs] = w(eit);
582 nextMatrix_[offs] = vit1;
583 }
584 ++eit;
585 }
586 auto vit = g.vrangeAll().begin();
587 while (vit != g.vrangeAll().end())
588 {
589 pos0 = posmap_->at(vit);
590 offs = offset(pos0,pos0);
591 infs_[offs] = false;
592 distMatrix_[offs] = 0.0;
593 nextMatrix_[offs] = vit;
594 ++vit;
595 }
596
597 ELE_CODE_TRACE({},"Running search");
598 // Floyd-Warshall core
599 size_t offsij,offsik,offskj;
600 for (size_vertex i = 0; i < V_; ++i)
601 for (size_vertex j = 0; j < V_; ++j)
602 {
603 offsij = offset(i,j);
604 for (size_vertex k = 0; k < V_; ++k)
605 {
606 offsik = offset(i,k);
607 offskj = offset(k,j);
608 if ((!infs_[offsik]) && (!infs_[offskj]))
609 {
610 Weight sum{distMatrix_[offsik] + distMatrix_[offskj]};
611 if (infs_[offsij] || (distMatrix_[offsij] > sum))
612 {
613 infs_[offsij] = false;
614 distMatrix_[offsij] = sum;
615 ELE_CODE_TRACE({},"Changed dist(" << i << "," <<
616 j << ") to " << sum);
617 nextMatrix_[offsij] = nextMatrix_[offsik];
618 }
619 }
620 }
621 }
622 ELE_CODE_TRACE_IF
623 if (std::find(infs_.begin(),infs_.end(),true) != infs_.end())
624 ELE_CODE_TRACE({},"Infs not wiped out");
625 ELE_CODE_TRACE_ENDIF
626 }
627 catch (...)
628 {
629 clean();
630 throw;
631 }
632 ELE_CODE_TRACE({},"Search finished ok. posmap_: " << posmap_);
633}
634
635template <class Vertex, class Edge, class Weight>
636FloydWarshall<Vertex,Edge,Weight>::FloydWarshall(FloydWarshall && o)
637{
638 V_ = o.V_;
639 V2Size_ = o.V2Size_;
640 distMatrix_ = o.distMatrix_;
641 infs_ = std::move(o.infs_);
642 nextMatrix_ = o.nextMatrix_;
643 ownposmap_ = o.ownposmap_;
644 posmap_ = o.posmap_;
645
646 o.V_ = 0;
647 o.V2Size_ = 0;
648 o.distMatrix_ = nullptr;
649 o.nextMatrix_ = nullptr;
650 o.posmap_ = nullptr;
651 o.ownposmap_ = false;
652}
653
654template <class Vertex, class Edge, class Weight>
655bool FloydWarshall<Vertex,Edge,Weight>::
656 shortest(const typename Gr::viterator vit0,
657 const typename Gr::viterator vit1,
658 Weight & w) const
659{ELE_CODE_TRACE_OFF;
660
661 checkCalcs();
662 ELE_CODE_TRACE({},std::endl << "vit0: " << vit0.to_string() << std::endl <<
663 "vit1: " << vit1.to_string() << std::endl <<
664 "vit0 == vit1: " << (vit0==vit1) <<
665 " posmap_: " << elementa::base::to_number(posmap_));
666
667 size_vertex i,j;
668 indexes(vit0,vit1,i,j);
669
670 auto o = offset(i,j);
671 if (infs_[o]) return(false);
672 w = distMatrix_[o];
673 return(true);
674}
675
676template <class Vertex, class Edge, class Weight>
677bool FloydWarshall<Vertex,Edge,Weight>::
678 shortest(const typename Gr::viterator vit0,
679 const typename Gr::viterator vit1,
680 Weight & d,
681 GPath<Vertex,Edge,GPathKind::kVertexPath> & path) const
682{ELE_CODE_TRACE_OFF;
683
684 checkCalcs();
685 ELE_CODE_TRACE({},std::endl << "vit0: " << vit0.to_string() << std::endl <<
686 "vit1: " << vit1.to_string() << std::endl <<
687 "vit0 == vit1: " << (vit0==vit1) <<
688 " posmap_: " << elementa::base::to_number(posmap_));
689
690 size_vertex i,j;
691 indexes(vit0,vit1,i,j);
692
693 path.clear();
694 auto o = offset(i,j);
695 if (infs_[o]) return(false);
696 d = distMatrix_[o];
697
698 auto vit = vit0;
699 path.push_back(vit);
700 while (vit != vit1)
701 {
702 indexes(vit,vit1,i,j);
703 vit = nextMatrix_[offset(i,j)];
704 path.push_back(vit);
705 }
706
707 return(true);
708}
709
710
713} // end graphs namespace
714
715} // end adts namespace
716
717} // end elementa namespace
718
719
720#endif
721
722
elementa::adts::graphs::Graph::ERange_All::begin
eiterator begin(void) const
Must return an iterator pointing to the first element.
Definition: graphs.h:353
elementa::adts::graphs::Graph::ERange_All::end
eiterator end(void) const
Must return an iterator pointing past the last element.
Definition: graphs.h:354
elementa::adts::graphs::Graph::ERange_DepthFirst::begin
eiterator begin(void) const
Must return an iterator pointing to the first element.
Definition: graphs.h:471
elementa::adts::graphs::Graph::ERange_DepthFirst::end
eiterator end(void) const
Must return an iterator pointing past the last element.
Definition: graphs.h:472
elementa::adts::graphs::Graph::MapOfVItPos
A map (hash) from vertex iterators in a graph to their num. positions.
Definition: graphs.h:174
elementa::adts::graphs::Graph::VRange_All::end
viterator end(void) const
Must return an iterator pointing past the last element.
Definition: graphs.h:299
elementa::adts::graphs::Graph::VRange_All::begin
viterator begin(void) const
Must return an iterator pointing to the first element.
Definition: graphs.h:298
graph_paths.h
ELE_CODE_TRACE_OFF
#define ELE_CODE_TRACE_OFF
Place this inside local scope (e.g., routine) to deactivate traces there.
Definition: debugging.h:283
ELE_CODE_TRACE_ENDIF
#define ELE_CODE_TRACE_ENDIF
Place this after a part of code that should be executed in debug only.
Definition: debugging.h:295
ELE_CODE_PLACE
#define ELE_CODE_PLACE
Produces a std::string with the place of source where the macro is placed.
Definition: debugging.h:194
ELE_CODE_TRACE_IF
#define ELE_CODE_TRACE_IF
Place this before a part of code that should be executed in debug only.
Definition: debugging.h:289
elementa::base::invstate
Exception for indicating that some object is in invalid state.
Definition: exceptions.h:230
ELE_CODE_INVSTATE
#define ELE_CODE_INVSTATE(expl)
To throw an invalid-state exception with an explanation.
Definition: exceptions.h:306
elementa::base::to_number
LongestUnsigned to_number(const void *p)
Convert a pointer address to a number.
elementa::adts::graphs::GPath
A path in a graph whose vertices are of type Vertex and edges of type Edge.
Definition: graph_paths.h:79
elementa::adts::graphs::EdgeWeightFunction
std::function< Weight(const typename Graph< Vertex, Edge >::eiterator &) > EdgeWeightFunction
A family of functions that return the weight of an edge.
Definition: graph_paths.h:188
elementa::adts::graphs::GPathKindType
A type corresponding to each constant value of the kind of a path.
Definition: graph_paths.h:62
elementa::adts::graphs::AllPathsVertices::PathType
GPath< Vertex, Edge, KIND > PathType
Shortcut for the path type.
Definition: graph_search.h:78
elementa::adts::graphs::AllPathsVertices::found
bool found(void) const noexcept
Return TRUE if there is some current path already found.
Definition: graph_search.h:114
elementa::adts::graphs::AllPathsVertices::GraphType
Graph< Vertex, Edge > GraphType
Shortcut for graph type.
Definition: graph_search.h:75
elementa::adts::graphs::AllPathsVertices::current
const PathType & current(void) const
Return a reference to the last path found.
Definition: graph_search.h:122
elementa::adts::graphs::FloydWarshall::filled
bool filled(void) const noexcept
Return TRUE if there is some previous calculation in the object.
Definition: graph_search.h:218
elementa::adts::graphs::FloydWarshall::~FloydWarshall
~FloydWarshall(void)
Destructor.
Definition: graph_search.h:211
elementa::adts::graphs::AllPathsVertices::next
bool next(void)
Search for another path and return TRUE if any is found.
Definition: graph_search.h:117
elementa::adts::graphs::FloydWarshall::mapOfVPoses
const Gr::MapOfVItPos & mapOfVPoses(void) const
Return the vertex mapping used by the object.
Definition: graph_search.h:215
elementa::adts::graphs::AllPathsVertices
A class that search for all paths connecting a given pair of vertices.
Definition: graph_search.h:68
elementa::adts::graphs::FloydWarshall
Floyd-Warshall data and algorithm to find all shortest paths in a graph.
Definition: graph_search.h:183
elementa::adts::graphs::AllPathsVertices::AllPathsVertices
AllPathsVertices(const GraphType &gr, const typename GraphType::viterator &vit0, const typename GraphType::viterator &vit1, bool detectcycles=true, const typename GraphType::EPred &epred=GraphType::trivial_epred)
Constructor for two given vertices.
Definition: graph_search.h:284
elementa::adts::graphs::FloydWarshall::FloydWarshall
FloydWarshall(const Gr &g, const EdgeWeightFunction< Vertex, Edge, Weight > &w=trivial_edge_weight< Vertex, Edge >, const typename Gr::MapOfVItPos *mpos=nullptr, const typename Gr::EPred &epred=Gr::trivial_epred)
Constructor: prepare data and perform the search.
Definition: graph_search.h:532
elementa::adts::graphs::FloydWarshall::shortest
bool shortest(const typename Gr::viterator vit0, const typename Gr::viterator vit1, Weight &d) const
Get the shortest distance (sum of weights) from vit0 to vit1.
Definition: graph_search.h:656
elementa::adts::graphs::Graph::connection
virtual void connection(const eiterator &it, viterator &vorg, viterator &vdest) const
Fill VORG and VDEST with VRange_All iterators to the edge vertices.
Definition: graphs.h:574
elementa::adts::graphs::Graph::EPred
std::function< bool(const Edge &) > EPred
Predicate that indicates which edges to iterate on.
Definition: graphs.h:279
elementa::adts::graphs::Graph::size_edges
virtual size_edge size_edges(void) const =0
Must return the number of edges.
elementa::adts::graphs::Graph::erangeDepthFirst
ERange_DepthFirst erangeDepthFirst(const viterator &v) const
Return a range to iterate on edges in depth-first fashion.
Definition: graphs.h:746
elementa::adts::graphs::Graph::size_vertices
virtual size_vertex size_vertices(void) const =0
Must return the number of vertices.
elementa::adts::graphs::Graph::trivial_epred
static constexpr bool trivial_epred(const Edge &) noexcept
A trivial predicate that always return true.
Definition: graphs.h:282
elementa::adts::graphs::Graph::eiterator
elementa::base::MultIterator< Edge > eiterator
Edge iterator. ForwardLegacyIterator.
Definition: graphs.h:121
elementa::adts::graphs::Graph::viterator
elementa::base::MultIterator< Vertex > viterator
Vertex iterator. ForwardLegacyIterator.
Definition: graphs.h:118
elementa::adts::graphs::Graph::vrangeAll
VRange_All vrangeAll(void) const
Return a range to iterate on all Vertex data, no special order.
Definition: graphs.h:721
elementa::adts::graphs::Graph::erangeAll
ERange_All erangeAll(void) const
Return a range to iterate on all Edge data, no special order.
Definition: graphs.h:730
elementa::adts::graphs::Graph
All graph classes derive from this one.
Definition: graphs.h:107
elementa::adts::graphs::size_vertex
size_t size_vertex
For holding numbers of vertices of a graph.
Definition: graphs.h:68
elementa::base::MultIterator::to_string
std::string to_string(void) const
Return a string with info about the iterator.
Definition: iterators.h:398
elementa::base::MultIterator
A mutable iterator that can have multiple iteration behaviors. Forward case.
Definition: iterators.h:299