next up previous contents index
Next: Face Circulators ( FaceCirc Up: Graphs and Iterators Previous: Adjacency Iterators for incoming   Contents   Index


Adjacency Iterators ( AdjIt )

Definition

a variable it of class AdjIt is an adjacency iterator that marks a node (which is fixed in contrast to linear node iterators) and iterates over the edges that leave or enter this node. At first, all outgoing edges will be traversed.

Internally, this iterator creates two instances of OutAdjIt and InAdjIt. The iteration is a sequenced iteration over both iterators. Note that this only fits for directed graph, for undirected graph you should use OutAdjIt instead.

#include < LEDA/graph/graph_iterator.h >

Creation

AdjIt it introduces a variable it of this class associated with no graph.

AdjIt it(const leda::graph& G) introduces a variable it of this class associated with G. The marked node is initialized by n=G.first_node() and the edge by G.first_adj_edge(n).

AdjIt it(const leda::graph& G, leda::node n)
    introduces a variable it of this class marked with n and associated with G. The marked edge is initialized by by G.first_adj_edge(n).

Precondition: n is a node of G.

AdjIt it(const leda::graph& G, leda::node n, leda::edge e)
    introduces a variable it of this class marked with n and e and associated with G.

Precondition: n is a node and e an edge of G and source(e)=n.

Operations

void it.init(const graphtype& G)
    associates it with G and marks it with n'=G.first_node() and G.first_adj_edge(n').

void it.init(const graphtype& G, const nodetype& n)
    associates it with G and marks it with n and G.first_adj_edge(v).

Precondition: n is a node of G.

void it.init(const graphtype& G, const nodetype& n, const edgetype& e)
    associates it with G and marks it with n and e.

Precondition: n is a node and e an edge of G and source(e)=n.

void it.update(leda::edge e) it marks e afterwards.

void it.reset() resets it to G.first_adj_edge(n) where G and n are the marked node and associated graph.

void it.insert(const AdjIt& other)
    creates a new edge from the marked node of it to the marked node of other. it is marked with the new edge afterwards. The marked node of it does not change.

void it.del() deletes the marked leaving edge, i.e. it.valid() returns false afterwards.

Precondition: it.valid() returns true.

void it.reset_end() resets it to G.last_adj_edge(n) where G and n are the marked node and associated graph.

void it.make_invalid() makes it invalid, i.e. it.valid() will be false afterwards and it marks no node.

void it.update(leda::node n) it marks n and the first leaving edge of n afterwards.

void it.update(leda::node n, leda::edge e)
    it marks n and e afterwards.

AdjIt& it = const AdjIt& it2 assigns it2 to it. This method returns a reference to it.

bool it == const AdjIt& it2 returns true if and only if it and it2 are equal, i.e. if the marked nodes and edges are equal.

bool it.has_node() returns true if and only if it marks a node.

bool it.eol() returns !it.valid() which is true if and only if there is no successor edge left, i.e. if all edges of the edge set are passed (eol: end of list).

bool it.valid() returns true if and only if end of sequence not yet passed, i.e. if there is an edge in the edge set that was not yet passed.

leda::edge it.get_edge() returns the marked edge or nil if it.valid() returns false.

leda::node it.get_node() returns the marked node or nil if it.has_node() returns false.

const leda::graph& it.get_graph() returns the associated graph.

AdjIt it.curr_adj() If the currently associated edge leaves the marked node, this method returns a new adjacency iterator that is associated with n'=target(e) and G.first_adj_edge(n') where G is the associated graph. Otherwise it returns a new adjacency iterator that is associated with n'=source(e) and G.first_in_edge(n') where G is the associated graph.

Precondition: it.valid() returns true.

AdjIt& ++it performs one step forward in the list of incident edges of the marked node. If the formerly marked edge was a leaving edge and there is no successor edge, it is associated to G.first_in_edge(n) where G and n are the associated graph and node. If the formerly marked edge was an incoming edge and there is no successor edge, it.eol() will be true afterwards. This method returns a reference to it.

Precondition: it.valid() returns true.

AdjIt& -it performs one step backward in the list of incident edges of the marked node. If the formerly marked edge was an incoming edge and there is no predecessor edge, it is associated to G.last_adj_edge(n) where G and n are the associated graph and node. If the formerly marked edge was a leaving edge and there is no successor edge, it.eol() will be true afterwards. This method returns a reference to it.

Precondition: it.valid() returns true.

Implementation

Creation of an iterator and all methods take constant time.


next up previous contents index
Next: Face Circulators ( FaceCirc Up: Graphs and Iterators Previous: Adjacency Iterators for incoming   Contents   Index
root 2008-01-09