37 #ifndef VIGRA_ADJACENCY_LIST_GRAPH_HXX
38 #define VIGRA_ADJACENCY_LIST_GRAPH_HXX
45 #include "multi_array.hxx"
46 #include "multi_gridgraph.hxx"
48 #include "tinyvector.hxx"
49 #include "random_access_set.hxx"
50 #include "graph_maps.hxx"
51 #include "iteratorfacade.hxx"
53 #include "algorithm.hxx"
54 #include "graph_item_impl.hxx"
64 namespace detail_adjacency_list_graph{
66 template<
class G,
class ITEM>
68 :
public ForwardIteratorFacade<
69 ItemIter<G,ITEM>,ITEM,true
73 typedef vigra::GraphItemHelper<G,ITEM> ItemHelper;
74 typedef typename G::index_type index_type;
77 ItemIter(
const lemon::Invalid & iv = lemon::INVALID)
87 item_(ItemHelper::itemFromId(*graph_,id_))
89 while( !isEnd() && item_==lemon::INVALID ){
91 item_ = ItemHelper::itemFromId(*graph_,id_);
95 ItemIter(
const G & g,
const ITEM & item)
105 friend class vigra::IteratorFacadeCoreAccess;
107 return graph_==NULL || ItemHelper::itemNum(*graph_)==0 || id_>ItemHelper::maxItemId(*graph_);
109 bool isBegin( )
const{
110 return graph_!=NULL && id_ == 0 ;
113 bool equal(
const ItemIter & other)
const{
114 return (isEnd() && other.isEnd() ) || (isEnd()==other.isEnd() && (id_ == other.id_) );
119 item_ = ItemHelper::itemFromId(*graph_,id_);
120 while( !isEnd() && item_==lemon::INVALID ){
122 item_ = ItemHelper::itemFromId(*graph_,id_);
125 const ITEM & dereference()
const{
135 template<
class GRAPH>
137 :
public ForwardIteratorFacade<
139 typename GRAPH::Arc,true
144 typedef typename Graph::Arc Arc;
145 typedef typename Graph::Edge Edge;
146 typedef typename Graph::EdgeIt EdgeIt;
147 ArcIt(
const lemon::Invalid invalid = lemon::INVALID )
154 ArcIt(
const GRAPH & g )
158 veryEnd_( g.edgeNum()==0 ? true : false),
162 ArcIt(
const GRAPH & g ,
const Arc & arc )
164 pos_(g,arc.edgeId()),
165 inFirstHalf_(g.id(arc)<=g.maxEdgeId()),
170 friend class vigra::IteratorFacadeCoreAccess;
172 return veryEnd_ || graph_==NULL;
176 return graph_!=NULL && veryEnd_==
false && pos_ == EdgeIt(*graph_);
181 if(pos_ == lemon::INVALID ) {
182 pos_ = EdgeIt(*graph_);
189 if(pos_ == lemon::INVALID){
197 bool equal(ArcIt
const& other)
const{
200 isEnd()==other.isEnd() &&
201 inFirstHalf_==other.inFirstHalf_
203 (isEnd() || graph_==NULL || pos_==other.pos_ )
208 const Arc & dereference()
const {
210 arc_ = graph_->direct(*pos_,inFirstHalf_);
215 const GRAPH * graph_;
233 typedef Int64 index_type;
237 typedef detail::GenericNodeImpl<index_type,false> NodeStorage;
238 typedef detail::GenericEdgeImpl<index_type > EdgeStorage;
239 typedef detail::NeighborNodeFilter<GraphType> NnFilter;
240 typedef detail::IncEdgeFilter<GraphType> IncFilter;
241 typedef detail::IsInFilter<GraphType> InFlter;
242 typedef detail::IsOutFilter<GraphType> OutFilter;
243 typedef detail::IsBackOutFilter<GraphType> BackOutFilter;
248 typedef detail::GenericNode<index_type>
Node;
250 typedef detail::GenericEdge<index_type>
Edge;
252 typedef detail::GenericArc<index_type>
Arc;
254 typedef detail_adjacency_list_graph::ItemIter<GraphType,Edge>
EdgeIt;
256 typedef detail_adjacency_list_graph::ItemIter<GraphType,Node>
NodeIt;
258 typedef detail_adjacency_list_graph::ArcIt<GraphType>
ArcIt;
261 typedef detail::GenericIncEdgeIt<GraphType,NodeStorage,IncFilter >
IncEdgeIt;
263 typedef detail::GenericIncEdgeIt<GraphType,NodeStorage,InFlter >
InArcIt;
265 typedef detail::GenericIncEdgeIt<GraphType,NodeStorage,OutFilter >
OutArcIt;
267 typedef detail::GenericIncEdgeIt<GraphType,NodeStorage,NnFilter > NeighborNodeIt;
271 typedef detail::GenericIncEdgeIt<GraphType,NodeStorage,BackOutFilter >
OutBackArcIt;
276 typedef boost::directed_tag directed_category;
278 typedef NeighborNodeIt adjacency_iterator;
279 typedef EdgeIt edge_iterator;
280 typedef NodeIt vertex_iterator;
285 typedef size_t degree_size_type;
286 typedef size_t edge_size_type;
287 typedef size_t vertex_size_type;
289 typedef Edge edge_descriptor;
290 typedef Node vertex_descriptor;
295 struct EdgeMap : DenseEdgeReferenceMap<GraphType,T> {
296 EdgeMap(): DenseEdgeReferenceMap<GraphType,T>(){
299 : DenseEdgeReferenceMap<GraphType,T>(g){
302 : DenseEdgeReferenceMap<GraphType,T>(g,val){
308 struct NodeMap : DenseNodeReferenceMap<GraphType,T> {
309 NodeMap(): DenseNodeReferenceMap<GraphType,T>(){
312 : DenseNodeReferenceMap<GraphType,T>(g){
315 : DenseNodeReferenceMap<GraphType,T>(g,val){
321 struct ArcMap : DenseArcReferenceMap<GraphType,T> {
322 ArcMap(): DenseArcReferenceMap<GraphType,T>(){
325 : DenseArcReferenceMap<GraphType,T>(g){
328 : DenseArcReferenceMap<GraphType,T>(g,val){
415 index_type
id(
const Node & node)
const;
421 index_type
id(
const Arc & arc )
const;
453 Node addNode(
const index_type
id);
462 Edge addEdge(
const index_type
u ,
const index_type
v);
465 size_t maxDegree()
const{
467 for(
NodeIt it(*
this);it!=lemon::INVALID;++it){
468 std::max(md,
size_t( degree(*it) ) );
479 vertex_iterator get_vertex_iterator()
const;
480 vertex_iterator get_vertex_end_iterator()
const ;
481 edge_iterator get_edge_iterator()
const;
482 edge_iterator get_edge_end_iterator()
const ;
483 degree_size_type degree(
const vertex_descriptor & node)
const{
484 return nodeImpl(node).numberOfEdges();
487 static const bool is_directed =
false;
491 typedef std::vector<NodeStorage> NodeVector;
492 typedef std::vector<EdgeStorage> EdgeVector;
496 template<
class G,
class NIMPL,
class FILT>
497 friend class detail::GenericIncEdgeIt;
500 friend struct detail::NeighborNodeFilter;
502 friend struct detail::IncEdgeFilter;
504 friend struct detail::BackEdgeFilter;
506 friend struct detail::IsOutFilter;
508 friend struct detail::IsBackOutFilter;
510 friend struct detail::IsInFilter;
513 friend class detail_adjacency_list_graph::ItemIter<GraphType,
Node>;
514 friend class detail_adjacency_list_graph::ItemIter<GraphType,
Edge>;
517 const NodeStorage & nodeImpl(
const Node & node)
const{
518 return nodes_[node.id()];
521 NodeStorage & nodeImpl(
const Node & node){
522 return nodes_[node.id()];
542 const size_t reserveNodes,
543 const size_t reserveEdges
550 nodes_.reserve(reserveNodes);
551 edges_.reserve(reserveEdges);
556 AdjacencyListGraph::addNode(){
557 const index_type
id = nodes_.size();
558 nodes_.push_back(NodeStorage(
id));
564 AdjacencyListGraph::addNode(
const AdjacencyListGraph::index_type
id){
565 if(
id == nodes_.size()){
566 nodes_.push_back(NodeStorage(
id));
570 else if((std::size_t)
id < nodes_.size()){
572 if(node==lemon::INVALID){
573 nodes_[
id]=NodeStorage(
id);
583 while(nodes_.size() < (std::size_t)
id){
584 nodes_.push_back(NodeStorage(lemon::INVALID));
586 nodes_.push_back(NodeStorage(
id));
593 AdjacencyListGraph::addEdge(
598 if(foundEdge!=lemon::INVALID){
601 else if(u==lemon::INVALID || v==lemon::INVALID){
602 return Edge(lemon::INVALID);
605 const index_type eid = edges_.size();
606 const index_type uid = u.id();
607 const index_type vid = v.id();
608 edges_.push_back(EdgeStorage(uid,vid,eid));
609 nodeImpl(u).insert(vid,eid);
610 nodeImpl(v).insert(uid,eid);
617 AdjacencyListGraph::addEdge(
618 const AdjacencyListGraph::index_type u ,
619 const AdjacencyListGraph::index_type v
621 const Node uu = addNode(u);
622 const Node vv = addNode(v);
623 return addEdge(uu,vv);
633 if(edge!=lemon::INVALID){
635 return Arc(
id(edge),
id(edge));
640 return Arc(lemon::INVALID);
650 return Arc(
id(edge),
id(edge));
652 else if(
v(edge)==node){
656 return Arc(lemon::INVALID);
673 return Node(edges_[
id(edge)].
u());
681 return Node(edges_[
id(edge)].
v());
690 const index_type arcIndex =
id(arc);
692 const index_type edgeIndex = arc.edgeId();
697 const index_type edgeIndex = arcIndex;
709 const index_type arcIndex =
id(arc);
711 const index_type edgeIndex = arc.edgeId();
716 const index_type edgeIndex = arcIndex;
728 const Node uNode =
u(e);
729 const Node vNode =
v(e);
730 if(
id(uNode)==
id(n)){
733 else if(
id(vNode)==
id(n)){
776 inline AdjacencyListGraph::index_type
782 inline AdjacencyListGraph::index_type
788 inline AdjacencyListGraph::index_type
794 inline AdjacencyListGraph::index_type
796 return edges_.back().id();
800 inline AdjacencyListGraph::index_type
802 return nodes_.back().id();
806 inline AdjacencyListGraph::index_type
813 inline AdjacencyListGraph::index_type
821 inline AdjacencyListGraph::index_type
829 inline AdjacencyListGraph::index_type
840 const AdjacencyListGraph::index_type
id
842 if((std::size_t)
id < edges_.size() && edges_[
id].id() != -1)
843 return Edge(edges_[
id].
id());
845 return Edge(lemon::INVALID);
851 const AdjacencyListGraph::index_type
id
853 if((std::size_t)
id < nodes_.size() && nodes_[
id].id() != -1)
854 return Node(nodes_[
id].
id());
856 return Node(lemon::INVALID);
862 const AdjacencyListGraph::index_type
id
866 return Arc(lemon::INVALID);
871 const index_type edgeId =
id - (
maxEdgeId() + 1);
873 return Arc(lemon::INVALID);
875 return Arc(
id,edgeId);
886 std::pair<index_type,bool> res = nodes_[
id(a)].findEdge(
id(b));
888 return Edge(res.first);
891 return Edge(lemon::INVALID);
902 if(e==lemon::INVALID){
903 return Arc(lemon::INVALID);
916 inline AdjacencyListGraph::vertex_iterator
917 AdjacencyListGraph::get_vertex_iterator()
const{
922 inline AdjacencyListGraph::vertex_iterator
923 AdjacencyListGraph::get_vertex_end_iterator()
const{
929 inline AdjacencyListGraph::edge_iterator
930 AdjacencyListGraph::get_edge_iterator()
const{
935 inline AdjacencyListGraph::edge_iterator
936 AdjacencyListGraph::get_edge_end_iterator()
const{
949 inline vigra::AdjacencyListGraph::vertex_size_type
953 inline vigra::AdjacencyListGraph::edge_size_type
963 inline vigra::AdjacencyListGraph::degree_size_type
968 inline vigra::AdjacencyListGraph::degree_size_type
973 inline vigra::AdjacencyListGraph::degree_size_type
982 inline vigra::AdjacencyListGraph::vertex_descriptor
987 inline vigra::AdjacencyListGraph::vertex_descriptor
995 inline std::pair< vigra::AdjacencyListGraph::vertex_iterator, vigra::AdjacencyListGraph::vertex_iterator >
997 return std::pair< vigra::AdjacencyListGraph::vertex_iterator, vigra::AdjacencyListGraph::vertex_iterator >(
998 g.get_vertex_iterator(), g.get_vertex_end_iterator());
1000 inline std::pair< vigra::AdjacencyListGraph::edge_iterator, vigra::AdjacencyListGraph::edge_iterator >
1002 return std::pair< vigra::AdjacencyListGraph::edge_iterator, vigra::AdjacencyListGraph::edge_iterator >(
1003 g.get_edge_iterator(),g.get_edge_end_iterator());
1007 inline std::pair< vigra::AdjacencyListGraph::in_edge_iterator, vigra::AdjacencyListGraph::in_edge_iterator >
1009 return std::pair< vigra::AdjacencyListGraph::in_edge_iterator, vigra::AdjacencyListGraph::in_edge_iterator >(
1010 vigra::AdjacencyListGraph::in_edge_iterator(g,v),vigra::AdjacencyListGraph::in_edge_iterator(lemon::INVALID)
1013 inline std::pair< vigra::AdjacencyListGraph::out_edge_iterator, vigra::AdjacencyListGraph::out_edge_iterator >
1015 return std::pair< vigra::AdjacencyListGraph::out_edge_iterator, vigra::AdjacencyListGraph::out_edge_iterator >(
1016 vigra::AdjacencyListGraph::out_edge_iterator(g,v),vigra::AdjacencyListGraph::out_edge_iterator(lemon::INVALID)