Adjacent convenience - algorithms on adjacent pairs

  • Permalink
  • submit to reddit
  • Email
  • Follow


The Standard C++ Library currently includes a couple of algorithms that
operates on adjacent pairs in a sequence --- adjacent_find and
adjacent_difference. Unfortunately, in my experience, these are not
sufficient to cover some seemingly common needs, such as invoking a
function over all adjacent pairs, as well as transforms and
accumulation. I would think standard algorithms for these operations
would have been convenient in many areas such as geometry/graphics,
statistics, signal processing, compression, etc.

Searches on the net do not turn up very many hits for such extensions.
Is everyone writing manual loops in these cases?

In particular, I see the need for the following algorithms:

   template <class II, class Proc>
   inline Fun for_each_adjacent (II first, II last, Proc);

   template <class II, class OI, class BinOp>
   inline OI transform_adjacent (II first, II last, OI dest, BinOp);

   template <class II, class T, class BinOp>
   inline T accumulate_adjacent (II first, II last, T val, BinOp);

Code examples/rationale:

   typedef vector <Point> Points;
   typedef vector <Line> Lines;
   Points p = GetPoints ();

   // Perform op on all adjacent pairs.

   void DrawLine (Point a, Point b);
   for_each_adjacent (p.begin (), p.end (), &DrawLine);

   // Transform all adjacent pairs (create line segments).

   Line CreateLine (Point a, Point b);
   Lines s; s.reserve (p.size () - 1);
   transform_adjacent (p.begin (), p.end (), back_inserter (s),
     &CreateLine);

   // Accumulate op on adjacent pairs (calculate distance).

   float Distance (Point a, Point b);
   float d1 = accumulate_adjacent (p.begin (), p.end (), float (0),
     &Distance);

Any comments about these algorithms, alternatives or their suitability
for inclusion in the standard library, are welcomed.

Regards,
Vidar


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply vattilah-groups (72) 10/22/2006 2:23:53 PM

See related articles to this posting


Hello Vidar!
Vidar Hasfjord wrote:
> The Standard C++ Library currently includes a couple of algorithms that
> operates on adjacent pairs in a sequence --- adjacent_find and
> adjacent_difference. Unfortunately, in my experience, these are not
> sufficient to cover some seemingly common needs, such as invoking a
> function over all adjacent pairs, as well as transforms and
> accumulation. I would think standard algorithms for these operations
> would have been convenient in many areas such as geometry/graphics,
> statistics, signal processing, compression, etc.
>
> Searches on the net do not turn up very many hits for such extensions.
> Is everyone writing manual loops in these cases?

Maybe but there is no need for doing so: the standard library already
includes appropriate algorithms for these!

> In particular, I see the need for the following algorithms:
>
>    template <class II, class Proc>
>    inline Fun for_each_adjacent (II first, II last, Proc);

You can use std::mismatch() for this: use a predicate always returning
true
after applying you procedure and increment the first iterator before
passing
it to the algorithm. In summary, your for_each_adjacent() would looks
something like this:

   template <typename ForwardIterator, typename Proc>
   Fun for_each_adjacent(ForwardIterator beg, ForwardIterator end,
                                       Proc proc)
   {
     ForwardIterator tmp(beg);
     std::mismatch(++tmp, end, beg, true_predicate(proc));
     return proc;
   }

>    template <class II, class OI, class BinOp>
>    inline OI transform_adjacent (II first, II last, OI dest, BinOp);

This one is an obvious application of std::transform() taking two
  sequences.

>    template <class II, class T, class BinOp>
>    inline T accumulate_adjacent (II first, II last, T val, BinOp);

.... and this one is std::mismatch() again.

> Any comments about these algorithms, alternatives or their suitability
> for inclusion in the standard library, are welcomed.

I wouldn't include algorithms like this into the standard library:
there
seem to be rather special cases. Possibly, something like a "zip()"
algorithm which takes two input sequences and an operation could
be a reasonable thing, however: this would avoid the somewhat ugly
reversal of arguments passed to the predicate (although this can be
easily handled by the functor, too). What is missing are versions of
the algorithms taking two sequences (e.g. std::mismatch() and
std::transform()) which check both the first and the second sequence
for having terminated.

Good luck, Denise.


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Denise 10/22/2006 5:07:13 PM

Thanks for your reply, Denise!

> > Is everyone writing manual loops in these cases?
>
> Maybe but there is no need for doing so: the standard library already
> includes appropriate algorithms for these!

I was aware of some algorithms that could be utilised (e.g.
adjacent_find with a dummy predicate via an adapter). You have made me
aware of a few more. That said, I am not sure I agree that these
algorithms are "appropriate" in this context. These adaptations may
solve the problem (I'll outline a few problems below), but the solution
is not straight-forward nor intuitive.

> >    inline Fun for_each_adjacent (II first, II last, Proc);
> You can use std::mismatch() for this: use a predicate always returning true

Yes, this is similar to using adjacent_find in a similar manner. I find
adjacent_find semantically closer to the intention. Unfortunately, both
solutions require ForwardIterator. While the standard algorithms you
use may require only InputIterators, providing the same InputIterator
or copies for two inputs will operate outside the iterator requirements
(one pass requirement). The for_each algorithm works with
InputIterator, and it would be convenient if for_each_adjacent did the
same. My following implementation is close:

   template <class II, class Fun>
   inline Fun for_each_adjacent (II first, II last, Fun fun)
     {
     if (first != last)
       for (II prev; (prev = first, ++first != last);)
         fun (*prev, *first);
     return fun;
     }

This is a single-pass algorithm in the sense that the increment
operator is applied only std::distance (first, last) times. Every item
is referenced twice, although this is not against the rules.
Unfortunately, "prev" is dereferenced after the increment of "first",
and this is outside the InputIterator requirements: "++r --- post: any
copies of the previous value of r are no longer required either to be
dereferenceable or to be in the domain of ==" (Working Draft, Standard
for Programming Language C++, p599). Although it isn't compliant, I
have found the implementation above to work fine with stream iterators
on my platform (VC++ 2005).

An InputIterator compliant implementation of for_each_adjacent will
have to use copying to avoid this problem:

   template <class II, class Fun>
   inline Fun for_each_adjacent (II first, II last, Fun fun)
     {
     if (first != last) for (;;) {
       std::iterator_traits <II>::value_type prev (*first);
       if (++first == last) break;
       fun (prev, *first);
       }
     return fun;
     }

As far as I see this implementation should be InputIterator compliant,
but if I've overlooked something, please let me know.

Usage scenario:

   // Draw line segments from a stream of formatted points.
   istream_iterator <Point> begin (cin), end;
   for_each_adjacent (begin, end, DrawLine);

> >    inline OI transform_adjacent (II first, II last, OI dest, BinOp);
> This one is an obvious application of std::transform() taking

Again, this doesn't work with InputIterator.

> >    inline T accumulate_adjacent (II first, II last, T val, BinOp);
> ... and this one is std::mismatch() again.

Same problem.

> I wouldn't include algorithms like this into the standard library:
> there seem to be rather special cases.

You may be right, although I find it somewhat surprising. I would think
that this sort of thing was fairly common (i.e. prosessing successive
pairs of elements in a sequence). But then again, the lack of hits from
my net searches supports your view.

Regards,
Vidar


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Vidar 10/23/2006 5:01:46 AM
comp.lang.c++.moderated 10637 articles. 9 followers. Post

2 Replies
321 Views

Similar Articles

[PageSpeed] 7


  • Permalink
  • submit to reddit
  • Email
  • Follow


Reply:

Similar Artilces:

Adjacency matrix vs Adjacency list?
When is it proper to use which ? Am i correct in the assumption that the adjacency matrix must have way shorter lookup-times(finding an element) especially for a large amount of nodes, since it can simply be implemented as a "double array" i.e. no search needed. For large amount of nodes the adjacency matrix should consume a lot of memory. Consider the Ford-Fulkersson method: Which representation(adj.matrix or adj.list) provides for the fastest execution of that algorithm ? Sure for large amounts of nodes an adj. matrix representation would use up a lot of memory, but that wouldn�t...

Adjacency
A well-known approach to representing long strings is to denote them as a set of shorter strings with nothing but white space or newline characters between them. Such a set of adjacent strings is to be read as one string, and creates no great parsing problem. It's suprising that this technique is not more widely adopted. In SWI Prolog, for instance, long format strings may contain a line continuation character, which is extra syntax. Furthermore, it clashes with an automatic source code formatter which tries to indent lines. In Prolog, adjacency could be employed for long lists, which are...

node-node adjacency matrix to a node-arc adjacency matrix
I have been trying to figure out how to create a arc-node adjacency matrix from a node-node adjacency matrix, for example: node-node adj A = [0 1 0 1 1; 0 0 1 1 0; 0 0 0 1 1; 0 0 0 0 1; 0 0 0 0 0]; looking for the following links: 1-2,1-4,1-5,2-3,2-4,3-4,3-5,4-5 arc-node adj B =[ 1 1 1 0 0 0 0 0 -1 0 0 1 1 0 0 0 0 0 0 -1 0 1 1 0 0 -1 0 0 -1 -1 0 1 0 0 -1 0 0 0 -1 -1]; Any help will be greatly appreciated: I have tried to develop a for loop using "A" and assigning -1 to the tail end of the link but with no succes...

adjacency matrix
Need help in solving the problem below. Any help would be highly appreciated Implement the adt graph as a C++ class first by using an adjacency matrix to represent the graph then by using an adjacency list to represent the graph. Extend the programming problem by adding adt operations such as Isconnected and HasCycle. also include operations that perform a topological sort for a directed graph without cycles. Determine the dfs and bfs spanning trees for a connected graph and determine a minimum spanning tree for a connected undirected graph. ...

Adjacency List
Could someone please rpovide an example how to generate Adjacency List (with Uniform Skewed, and Two-Tier distributions)? Then convert the adjacency list into the corresponding adjacency matrix. Once the matrix is in place ... How to create "Ordered/Connected" pairs and create the Vertex Coloring graph Thank you! Leo ...

Adjacency graph
Hi How do I get the adjacency graph for a row data (one raw matrix) in Matlab Thank you Eiman ...

adjacency problem
suppose I have a matrix M {assign}24 24 {rho}{iota}576 I'm trying to efficiently generate an array R that contains adjacency information about the entries of M. for example, my adjaceny rule is such that for M[1;1] which is 1, I would want 1 2 25 26 and for M[1;2] I want 1 2 3 25 25 27 and for M[2;2] I want 1 2 325 26 27 49 50 51 and so on. The number of adjacent values can be either 4, 6, or 9 depending if the cell is a corner, edge but not corner, or interior. The output matrix R needs to be rectangular so in the case of a corner or edge the adjacency values can be repeated ...

adjacency matrix
Hi everyone, I wrote a code and i want to create an adjacency matrix for that by selecting one of the points marked with red clc clear clf L = linspace(0,2.*pi,100); xv = cos(L)';yv = sin(L)'; % 6 yi artt?r?nca yuvarla?a yakla??yor. Kenar say?s? k?saca o. xv = [xv ; xv(1)]; yv = [yv ; yv(1)]; xmin = -5; xmax = 5; npts = 500; x = xmin + (xmax-xmin)*rand(npts,1); ymin = -5; ymax= 5; y = ymin + (ymax-ymin)*rand(npts,1); p=[x y]; in = inpolygon(x,y,xv,yv); tri = delaunay(x,y); triplot(tri,x,y) hold on plot(xv,yv,x(in),y(in),'r*',x(~...

Adjacent selector
I was just experimenting with adjacent selectors today. Isn't the HTML and CSS below good enough to set the color orange on "li + span"??? (It didn't work in latest versions of Firefox or Chrome) <!DOCTYPE html> <html><head><title>CSS</title> <meta http-equiv="Content-Type" content="text/html; charset=utf-8"/> <style> li + span { color: orange; } </style> </head> <body> <ul> <li>Black</li> <li><span>!ORANGE!</span></li> &...

OSPF question about adjacencies
I'm a bit confused about adjacencies. Is the router adjacent only to other routers that are directly connected to an interface, or could it be adjacent to any router that it gets a hello packet from that contains it's own RouterID? Also, are hello packets sent out only to directly connected routers, or do the directly connected routers also pass this hello packet to all other routers? Finally, what is the mechanism that allows a DR and BDR to send out link state packets on the entire network that makes sure all routers, within the OSPF area, receive all the link states? -Sameer ...

Finding Adjacent Vertices
Given a graph G = (V, E) and an element v of V, what is the quickest way to find the vertices adjacent to v? The fastest algorithm I can think of is this one: for each edge (u, w) in E do if u = v then return w if w = v then return u done which takes time proportional to |E|. Given the adjancency matrix A of G, I could find the adjacent vertices in time proportional to |V| like so: for each u in V do if A[v][u] = 1 then return u done However, I would have to deal with building A first which takes at least time proportional to |E| (since every edge must be visited to determine whethe...

IS-IS Routers not establishing adjacency
Hi, I am working through an IS-IS configuration in the SYBEX BSCI book. I followed the example configs exactly but my routers can not establish adjacency. Any IS-IS gurus with any ideas? I don't want to post configs yet as the config from the sample chapter is very straightforward. I'm probably missing a trick. Thanks <alex_edwards2000@hotmail.com> wrote in message news:1143484789.016211.202150@g10g2000cwb.googlegroups.com... > Hi, > > I am working through an IS-IS configuration in the SYBEX BSCI book. I > followed the example configs exactly but my routers can...

adjacency matrix for a graph
Hi guys, I am trying to find the adjacency matrix for a graph A=(aij) which is constructed through this rule: aij= 1 ,if there is an edge connecting Pj to Pi. 0 .otherwise. The graph has ten 10 vertices : P1,P2,....,P5. So, the dimension of the matrix is 10x10. >> clear >> n=5; % n= no. of vertices. >> A=zeros(n,n) % preallocatation of the matrix. A = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 >> % if there is an edge connecting Pj t...

ISIS Adjacency Problem
Hi all, first let me tell I' not ver familar with ISIS...yesterday night I try to troubleshoot a adjacency problembetween two cisco systems.... on is a AS5800 and on the other side a cisco 7609 On both systems are IOS version 12.2 The connectivity is done over fiber SX gigabit ports...because the systems are in the same room and side by side. The AS is redundant connected to 2 7606 So from AS gi 6/0 is going to router 1 gig 2/21 and gig6/1 is going to router 2/21 When I debug on the AS that it sends and receives clns packets over 6/1...but it only send over 6/0 and doesn't receive.....

triangle strip with adjacency
Hey, is it just me or does anyone else think Figure 2.6 is a bit weird? i'm looking at the version at: http://www.opengl.org/registry/doc/glspec41.core.20100725.pdf I understand the doc below it, but the figure just seems wrong. A bunch of issues: 1) On the top left, the triangle connecting 3,5,6 *should* be an adjacent triangle, but it is drawn solid. 2) On the top right, vertex 9 should really be vertex 8, and the triangle connecting 7.5,8 should be adjacent, but it is drawn solid 3) The bottom two images look correct, but they are identical (not sure why they are repeated) On Sa...

baselines in adjacent minipages
hello - i have posted this question some time earlier, but probably never hit someone's specific latex nerv. i am posting it here again with a different problem explication: i am creating a package for a boxed logic calculus a la kalish-montague. for those not familiar with it: typesettingwise it consists of 3 columns - the 1st for line numbers, the third for comments and the middle one consists of multiply framed lines (with different height math symbols) like 1 line 1 comment 1 ___________ 2 | line 2 | comment 2 3 | line 3 | comme...

building an adjacency matrix
Hello, I would like to load data into matlab and then build an adjacency matrix. my data is in excel format. 1 2 45 1 4 44 1 5 10 ... ... 10 2 567 10 5 45 10 6 2 ... ... it is a 40x40 matrix where the elements of the matrix are in the 3rd column above. It is the first time I am using matlab.. please help. Thank you "s.naaz " <noune19@gmail.com> wrote in message <h4s8ep$gec$1@fred.mathworks.com>... > Hello, > > I would like to load data into matlab and then build an adjacency matrix. my data is in excel format. > 1 2 45 > 1 4 44 > 1 5 10 > .. &...

to make a adjacent matrix
how to make a 32 by 32 connection matrix , in which every node have 16 connection by bi-direction, it means aij=aji (symmetric matrix) selection of node is random. ...

Adjacency matrix compression..?
Hi there, Given a 3d polygon model, adjacency matrix is a matrix with rows and columns labeled by graphics vertices, with a 1 or 0 in position (Vi,Vj) according to whether Vi and Vj are adjacent or not. The element of the matrix is usually 0. It seems like a black-white images but black color is in the majority. Can anybody have any simple idea to compress the kind of matrix? Thanks in advance. Best Regards, Brian Brian <cuckoo@cs.nchu.edu.tw> wrote: > Given a 3d polygon model, adjacency matrix is a matrix with rows and columns > labeled by graphics vertices, with a 1 or 0 i...

A Question about adjacency matrix
Dear Sir I have a question about the adjacency matrix My question: How to get adjacency matrix for a graph composed of points in {x,y,z} ? Thanks in advance Marwa Ali An adjacency matrix describes relationship between nodes (connection or no connection). There is often, but not necessarily a weight involved. For nodes that are 3D coordinates one could use one of several distance functions Mathematica has built-in, such as EuclideanDistance, as weight. But you can think of many others that do not involve distance in 3D at all. Any matrix element m[[i,j]] describes t...

convert into adjacency matrix
Hi all! I have a set of points (obtained using another tool) which I need to represent in the form of an adjacency matrix so that I can view the connectivity between these points. For e.g. 5 2 6 9 4 7 3 3 1 6 2 5 8 4 2 3 5 1 4 6 5 % points represent a path Is there any function that I can use to indicate the link between say, 5 and 6? Or do I need to do: links=zeros(7,7); links(5,2)=1; ... like this for all the points..but isn't this tedious? Thanks for your replies, Marat "Marat " <nemesis_810@yahoo.com> wrote in message <grhpsp$pin$1@fred.mathworks.com>... >...

Find adjacent points
Given two contiguous disjoint sets Ai & Aj of (x,y) coordinates, is there an efficient method of determining which points (xi,yi) in Ai and (xj,yj) in Aj are adjacent; i.e. such that |xi-xj|<=1 and |yi-yj|<=1? I'm currently using a for...end loop to test the kth coordinate in one set against the vectorised representation of the other in a find statement. This seems inefficient, especially for large sets. Is there a fully vectorised method of achieving the same end? "Brian Flemming" <qzxj37@googlemail.com> wrote in message <ibhqg1$a4o$1@fred.mathworks.com...

Adjacency lists with sqlalchemy...
I'm desperately trying to declare an adjacency list table with declarative_base() but I can't figure it out. Strangely, all the documentation avoids declarative_base() like the plague and does everything the hard way. What the hell is this thing for if we're not supposed to use it? If anyone can show me how to declaratively create ORM adjacency list or explain to me why this can't be done, I'd be very grateful. Thank you! ...

Adjacent array elements
Hi all! I have a huge 2-dimensional array. For each element of this array I need to get all adjacent elements. a b c d e f g h i j k l m n o p q r s t u v w x y For example, for an element 'm' - adjacent elements are [g h i l n q r s]. Is there an efficient way to get those adjacent elements? The solution should be 'extendable' because there is the same problem for 3D and 4D arrays. I don't want to write it in a loop like offsetting by one in each dimension. I would like to know if a 'vectorized' solution exists. I'll be glad for any advise. Thank you...

Adjacency matrix and graph
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi, Given an adjacency matrix A of a graph G, G can be drawn easily. Is there a package or a program which would allow me to introduce A, and output G, to put G in a LaTeX document? If so, how, and which one? Thanks. - -- Merciadri Luca See http://www.student.montefiore.ulg.ac.be/~merciadri/ -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Processed by Mailcrypt 3.5.8 <http://mailcrypt.sourceforge.net/> iEYEARECAAYFAkrsOYAACgkQM0LLzLt8MhzQnQCgp/SO0PWGPwlUtjwf9Umybilq 0PoAn3Sqa5z4bcvuCSaGRcOXNy7hJt6u =FFHu -----EN...