changeset 1123 | a2e93889a604 |
parent 1119 | d3504fc075dc |
child 1124 | 12623f7ecb37 |
11:05ef95f9a6b5 | 12:07fe0c0e7d21 |
---|---|
70 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
70 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
71 /// |
71 /// |
72 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap; |
72 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap; |
73 ///Instantiates a PredMap. |
73 ///Instantiates a PredMap. |
74 |
74 |
75 ///\todo Please document... |
75 ///This function instantiates a \ref PredMap. |
76 ///\param G is the graph, to which we would like to define the PredMap. |
|
76 ///\todo The graph alone may be insufficient for the initialization |
77 ///\todo The graph alone may be insufficient for the initialization |
77 static PredMap *createPredMap(const GR &G) |
78 static PredMap *createPredMap(const GR &G) |
78 { |
79 { |
79 return new PredMap(G); |
80 return new PredMap(G); |
80 } |
81 } |
84 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
85 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
85 /// |
86 /// |
86 typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap; |
87 typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap; |
87 ///Instantiates a PredNodeMap. |
88 ///Instantiates a PredNodeMap. |
88 |
89 |
89 ///\todo Please document... |
90 ///This function instantiates a \ref PredNodeMap. |
90 /// |
91 ///\param G is the graph, to which we would like to define the \ref PredNodeMap |
91 static PredNodeMap *createPredNodeMap(const GR &G) |
92 static PredNodeMap *createPredNodeMap(const GR &G) |
92 { |
93 { |
93 return new PredNodeMap(G); |
94 return new PredNodeMap(G); |
94 } |
95 } |
95 |
96 |
100 ///\todo If it is set to a real map, Dijkstra::reached() should read this. |
101 ///\todo If it is set to a real map, Dijkstra::reached() should read this. |
101 ///\todo named parameter to set this type, function to read and write. |
102 ///\todo named parameter to set this type, function to read and write. |
102 typedef NullMap<typename Graph::Node,bool> ReachedMap; |
103 typedef NullMap<typename Graph::Node,bool> ReachedMap; |
103 ///Instantiates a ReachedMap. |
104 ///Instantiates a ReachedMap. |
104 |
105 |
105 ///\todo Please document... |
106 ///This function instantiates a \ref ReachedMap. |
106 /// |
107 ///\param G is the graph, to which we would like to define the \ref ReachedMap |
107 static ReachedMap *createReachedMap(const GR &G) |
108 static ReachedMap *createReachedMap(const GR &G) |
108 { |
109 { |
109 return new ReachedMap(); |
110 return new ReachedMap(); |
110 } |
111 } |
111 ///The type of the map that stores the dists of the nodes. |
112 ///The type of the map that stores the dists of the nodes. |
113 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
114 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
114 /// |
115 /// |
115 typedef typename Graph::template NodeMap<typename LM::Value> DistMap; |
116 typedef typename Graph::template NodeMap<typename LM::Value> DistMap; |
116 ///Instantiates a DistMap. |
117 ///Instantiates a DistMap. |
117 |
118 |
118 ///\todo Please document... |
119 ///This function instantiates a \ref DistMap. |
119 /// |
120 ///\param G is the graph, to which we would like to define the \ref DistMap |
120 static DistMap *createDistMap(const GR &G) |
121 static DistMap *createDistMap(const GR &G) |
121 { |
122 { |
122 return new DistMap(G); |
123 return new DistMap(G); |
123 } |
124 } |
124 }; |
125 }; |
504 /// |
505 /// |
505 bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; } |
506 bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; } |
506 |
507 |
507 }; |
508 }; |
508 |
509 |
510 /// Default traits used by \ref DijkstraWizard |
|
511 |
|
512 /// To make it easier to use Dijkstra algorithm we created a wizard class. |
|
513 /// This \ref DijkstraWizard class also needs default traits. |
|
514 /// The \ref DijkstraWizardBase is a class to be the default traits of the |
|
515 /// \ref DijkstraWizard class. |
|
509 template<class GR,class LM> |
516 template<class GR,class LM> |
510 class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM> |
517 class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM> |
511 { |
518 { |
512 |
519 |
513 typedef DijkstraDefaultTraits<GR,LM> Base; |
520 typedef DijkstraDefaultTraits<GR,LM> Base; |
523 ///Pointer to the map of distances. |
530 ///Pointer to the map of distances. |
524 void *_dist; |
531 void *_dist; |
525 ///Pointer to the source node. |
532 ///Pointer to the source node. |
526 void *_source; |
533 void *_source; |
527 |
534 |
535 /// Type of the nodes in the graph. |
|
528 typedef typename Base::Graph::Node Node; |
536 typedef typename Base::Graph::Node Node; |
529 |
537 |
530 public: |
538 public: |
539 /// Constructor. |
|
540 |
|
541 /// This constructor does not require parameters, therefore it initiates |
|
542 /// all of the attributes to default values (0, INVALID). |
|
531 DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0), |
543 DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0), |
532 _dist(0), _source(INVALID) {} |
544 _dist(0), _source(INVALID) {} |
533 |
545 |
546 /// Constructor. |
|
547 |
|
548 /// This constructor requires some parameters, listed in the parameters list. |
|
549 /// Others are initiated to 0. |
|
550 /// \param g is the initial value of \ref _g |
|
551 /// \param l is the initial value of \ref _length |
|
552 /// \param s is the initial value of \ref _source |
|
534 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : |
553 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : |
535 _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0), |
554 _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0), |
536 _dist(0), _source((void *)&s) {} |
555 _dist(0), _source((void *)&s) {} |
537 |
556 |
538 }; |
557 }; |
539 |
558 |
540 ///\e |
559 /// A class to make easier the usage of Dijkstra algorithm |
541 |
560 |
542 ///\e |
561 /// This class is created to make it easier to use Dijkstra algorithm. |
562 /// It uses the functions and features of the plain \ref Dijkstra, |
|
563 /// but it is much more simple to use it. |
|
543 /// |
564 /// |
565 /// Simplicity means that the way to change the types defined |
|
566 /// in the traits class is based on functions that returns the new class |
|
567 /// and not on templatable built-in classes. When using the plain \Dijkstra |
|
568 /// the new class with the modified type comes from the original by using the :: |
|
569 /// operator. In this case only a function have to be called and it will |
|
570 /// return the needed class. |
|
571 /// |
|
572 /// It does not have own \ref run method. When its \ref run method is called |
|
573 /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run |
|
574 /// method of it. |
|
544 template<class TR> |
575 template<class TR> |
545 class DijkstraWizard : public TR |
576 class DijkstraWizard : public TR |
546 { |
577 { |
547 typedef TR Base; |
578 typedef TR Base; |
548 |
579 |
549 //The type of the underlying graph. |
580 ///The type of the underlying graph. |
550 typedef typename TR::Graph Graph; |
581 typedef typename TR::Graph Graph; |
551 //\e |
582 //\e |
552 typedef typename Graph::Node Node; |
583 typedef typename Graph::Node Node; |
553 //\e |
584 //\e |
554 typedef typename Graph::NodeIt NodeIt; |
585 typedef typename Graph::NodeIt NodeIt; |
555 //\e |
586 //\e |
556 typedef typename Graph::Edge Edge; |
587 typedef typename Graph::Edge Edge; |
557 //\e |
588 //\e |
558 typedef typename Graph::OutEdgeIt OutEdgeIt; |
589 typedef typename Graph::OutEdgeIt OutEdgeIt; |
559 |
590 |
560 //The type of the map that stores the edge lengths. |
591 ///The type of the map that stores the edge lengths. |
561 typedef typename TR::LengthMap LengthMap; |
592 typedef typename TR::LengthMap LengthMap; |
562 //The type of the length of the edges. |
593 ///The type of the length of the edges. |
563 typedef typename LengthMap::Value Value; |
594 typedef typename LengthMap::Value Value; |
564 //\brief The type of the map that stores the last |
595 ///\brief The type of the map that stores the last |
565 //edges of the shortest paths. |
596 ///edges of the shortest paths. |
566 typedef typename TR::PredMap PredMap; |
597 typedef typename TR::PredMap PredMap; |
567 //\brief The type of the map that stores the last but one |
598 ///\brief The type of the map that stores the last but one |
568 //nodes of the shortest paths. |
599 ///nodes of the shortest paths. |
569 typedef typename TR::PredNodeMap PredNodeMap; |
600 typedef typename TR::PredNodeMap PredNodeMap; |
570 //The type of the map that stores the dists of the nodes. |
601 ///The type of the map that stores the dists of the nodes. |
571 typedef typename TR::DistMap DistMap; |
602 typedef typename TR::DistMap DistMap; |
572 |
603 |
573 //The heap type used by the dijkstra algorithm. |
604 ///The heap type used by the dijkstra algorithm. |
574 typedef typename TR::Heap Heap; |
605 typedef typename TR::Heap Heap; |
575 public: |
606 public: |
607 /// Constructor. |
|
576 DijkstraWizard() : TR() {} |
608 DijkstraWizard() : TR() {} |
577 |
609 |
610 /// Constructor that requires parameters. |
|
611 /// These parameters will be the default values for the traits class. |
|
578 DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) : |
612 DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) : |
579 TR(g,l,s) {} |
613 TR(g,l,s) {} |
580 |
614 |
615 ///Copy constructor |
|
581 DijkstraWizard(const TR &b) : TR(b) {} |
616 DijkstraWizard(const TR &b) : TR(b) {} |
582 |
617 |
583 ~DijkstraWizard() {} |
618 ~DijkstraWizard() {} |
584 |
619 |
585 ///\e |
620 ///Runs Dijkstra algorithm from a given node. |
621 |
|
622 ///Runs Dijkstra algorithm from a given node. |
|
623 ///The node can be given by the \ref source function. |
|
586 void run() |
624 void run() |
587 { |
625 { |
588 if(_source==0) throw UninitializedData(); |
626 if(_source==0) throw UninitializedData(); |
589 Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length); |
627 Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length); |
590 if(_pred) Dij.predMap(*(PredMap*)_pred); |
628 if(_pred) Dij.predMap(*(PredMap*)_pred); |
591 if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode); |
629 if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode); |
592 if(_dist) Dij.distMap(*(DistMap*)_dist); |
630 if(_dist) Dij.distMap(*(DistMap*)_dist); |
593 Dij.run(*(Node*)_source); |
631 Dij.run(*(Node*)_source); |
594 } |
632 } |
595 |
633 |
596 ///\e |
634 ///Runs Dijkstra algorithm from a given node. |
635 |
|
636 ///Runs Dijkstra algorithm from a given node. |
|
637 ///\param s is the given source. |
|
597 void run(Node s) |
638 void run(Node s) |
598 { |
639 { |
599 _source=(void *)&s; |
640 _source=(void *)&s; |
600 run(); |
641 run(); |
601 } |
642 } |
605 typedef T PredMap; |
646 typedef T PredMap; |
606 static PredMap *createPredMap(const Graph &G) { return 0; }; |
647 static PredMap *createPredMap(const Graph &G) { return 0; }; |
607 DefPredMapBase(const Base &b) : Base(b) {} |
648 DefPredMapBase(const Base &b) : Base(b) {} |
608 }; |
649 }; |
609 |
650 |
610 ///\e |
651 /// \ref named-templ-param "Named parameter" function for setting PredMap type |
652 |
|
653 /// \ref named-templ-param "Named parameter" function for setting PredMap type |
|
611 template<class T> |
654 template<class T> |
612 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t) |
655 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t) |
613 { |
656 { |
614 _pred=(void *)&t; |
657 _pred=(void *)&t; |
615 return DijkstraWizard<DefPredMapBase<T> >(*this); |
658 return DijkstraWizard<DefPredMapBase<T> >(*this); |
621 typedef T PredNodeMap; |
664 typedef T PredNodeMap; |
622 static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; }; |
665 static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; }; |
623 DefPredNodeMapBase(const Base &b) : Base(b) {} |
666 DefPredNodeMapBase(const Base &b) : Base(b) {} |
624 }; |
667 }; |
625 |
668 |
626 ///\e |
669 /// \ref named-templ-param "Named parameter" function for setting PredNodeMap type |
670 |
|
671 /// \ref named-templ-param "Named parameter" function for setting PredNodeMap type |
|
627 template<class T> |
672 template<class T> |
628 DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) |
673 DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) |
629 { |
674 { |
630 _predNode=(void *)&t; |
675 _predNode=(void *)&t; |
631 return DijkstraWizard<DefPredNodeMapBase<T> >(*this); |
676 return DijkstraWizard<DefPredNodeMapBase<T> >(*this); |
636 typedef T DistMap; |
681 typedef T DistMap; |
637 static DistMap *createDistMap(const Graph &G) { return 0; }; |
682 static DistMap *createDistMap(const Graph &G) { return 0; }; |
638 DefDistMapBase(const Base &b) : Base(b) {} |
683 DefDistMapBase(const Base &b) : Base(b) {} |
639 }; |
684 }; |
640 |
685 |
641 ///\e |
686 /// \ref named-templ-param "Named parameter" function for setting DistMap type |
687 |
|
688 /// \ref named-templ-param "Named parameter" function for setting DistMap type |
|
642 template<class T> |
689 template<class T> |
643 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t) |
690 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t) |
644 { |
691 { |
645 _dist=(void *)&t; |
692 _dist=(void *)&t; |
646 return DijkstraWizard<DefDistMapBase<T> >(*this); |
693 return DijkstraWizard<DefDistMapBase<T> >(*this); |
647 } |
694 } |
648 |
695 |
649 ///\e |
696 /// Sets the source node, from which the Dijkstra algorithm runs. |
697 |
|
698 /// Sets the source node, from which the Dijkstra algorithm runs. |
|
699 /// \param s is the source node. |
|
650 DijkstraWizard<TR> &source(Node s) |
700 DijkstraWizard<TR> &source(Node s) |
651 { |
701 { |
652 source=(void *)&s; |
702 source=(void *)&s; |
653 return *this; |
703 return *this; |
654 } |
704 } |