STL double-linked list

[hectorDUQUE]

hi guys,
i wonder if somebody knows where to find an STL library for implemeting a double-linked list: previous and next element and so on ...

thanks in advance,

hector

 

[uolj]

The standard list class should work for you. The implementation details are not standardized, but I believe most implementations use a double-linked list underneath the list interface. That shouldn't really matter anyway, since you will be programming to the interface anyway.

There isn't a previous and next function, mostly because there isn't really a node exposed for the list class. Instead you use iterators. The iterators can be moved forward and backward with ++ and -- which is equivalent to previous and next.

Many other standard C++ containers provide an interface for forward and backward iteration, so if that is all you need it is possible that vector, deque, set or some other container could work for you as well.

 

[hectorDUQUE]

thanks uolj for comments,

i also need to implement a type of graph, because i have to reference the two next nodes instead of a previous one.

i mean, i could have something like this:


|<------------|
| |
|<-- | |
| | |
|--> 8 ---> 10 ---> 25 --> etc
^ |
|________________|

so i need a doubled-link, but different than the usual next and previous.

which container do you guys recomend me?

i wonder if you have a litlle example code ?

cheers,

hector

 

[hectorDUQUE]

there exist GTL, but is not free and is much much more than i need :-(
hector

 

[uolj]

For a graph system like that, I might just keep track of the edges on my own rather than choosing a specific container to do that. For example, you could use a map to hold the nodes and edges. Each node would be a key in the multimap, and the value would be a list (or vector) of edges. Something like this:

#include <map>
#include <vector>
#include <utility>
#include <iostream>

int main()
{
    typedef std::vector<int> edge_list_type;
    typedef std::map<int, edge_list_type> graph_type;

    graph_type graph;

    graph.insert(std::make_pair(8, std::vector<int>()));
    graph.insert(std::make_pair(10, std::vector<int>()));
    graph.insert(std::make_pair(25, std::vector<int>()));
    graph.insert(std::make_pair(37, std::vector<int>()));

    graph[8].push_back(8);
    graph[8].push_back(10);
    graph[10].push_back(8);
    graph[10].push_back(25);
    graph[25].push_back(37);

    for (graph_type::const_iterator cur_node = graph.begin(),
        end_node = graph.end(); cur_node != end_node; ++cur_node)
    {
        std::cout << "Edges for node " << cur_node->first << ':';

        for (edge_list_type::const_iterator cur_edge = cur_node->second.begin(),
            end_edge = cur_node->second.end(); cur_edge != end_edge; ++cur_edge)
        {
            std::cout << ' ' << *cur_edge;
        }
        std::cout << '\n';
    }
}

It might also be better to create a struct or class that holds a node and its edges, so that you could encapsulate operations on them better.

Finally, there are other libraries out there that might help you. I have not used any, but I believe boost has a graph library that is free, and in general boost libraries are excellent. You might want to look at their website (boost.org).

 

[hectorDUQUE]

thanks uolj for your important contribution,

i'll take a look at ...

i've also found STLplus:

http://stlplus.sourceforge.net/

it is free ang has a STL extention for directed graphs. I hope it works.

i will also take a look at boost; yes, they have something for graphs.

hector

 

[jstreich]

If I am reading your picture right, your not looking for a double-linked list but a odd list implementation of a heap.

A heap implements a tree structure in a dynamic array. where the children of the of node at index i (not using 0 based indecies, but 1 based indecies) is i*2 and i*2+1,

So, node 1 has children 2 and 3
node 2 has children 4 and 5,
node 3 has children 6 and 7, and so on.

To find a parent, you need only to devide the index by 2 using int devision.

Heaps are sorted such that each parent is less than both of it's two children, in this way the lowest is always first.

As a implimented as an odd "linked list" you lose the benifits over a traditional tree structure, and you are probably better off using a BinarySearchTree.

If this is what you are looking for, try looking at the STL's heap and set.

[plug=shameless]

http://game-master.us/phpx-3.4.0/

[/plug]

 

[hectorDUQUE]

thanks jstreich for comments, but the structure i need is not a heap, it is a graph. It looks like my picture loss some white characters and is not as clear as i wanted.

i'll try this notation (node4 is new one):

node1 = 8
node2 = 10
node3 = 25
node4 = 50
arc1 = node1 to node1
arc2 = node2 to node1
arc3 = node1 to node2
arc4 = node2 to node3
arc5 = node3 to node4
arc6 = node3 to node1
arc7 = node4 to node2
arc8 = node4 to node3

so, it is not a tree because there are nodes directed to a previous one.

i am taking a look at STLplus, but i not understand very well how to chose one of two output arcs in order to follow one of the possible paths. I mean, for example from node3 i could go to node4 OR to go to node1. How can i chose one of those arcs ?

it looks like i must use arc_select_fn ... does someone of you have a little piece of example code ?

hector

 

[hectorDUQUE]

btw,
take a look at an STLplus implementation:

#include "stlplus.hpp"
#include <vector>
using namespace std;


#define WON			1
#define LOSS                    0



void hD_initGraph(digraph<string,int>& graph){


    digraph<string,int>::iterator node1 = graph.insert("1");
    digraph<string,int>::iterator node2 = graph.insert("3");
    digraph<string,int>::iterator node3 = graph.insert("7");
    digraph<string,int>::iterator node4 = graph.insert("15");

    digraph<string,int>::arc_iterator arc1 = graph.arc_insert(node1, node2, LOSS);
    digraph<string,int>::arc_iterator arc2 = graph.arc_insert(node2, node3, LOSS);
    digraph<string,int>::arc_iterator arc3 = graph.arc_insert(node3, node4, LOSS);


    digraph<string,int>::arc_iterator arc5 = graph.arc_insert(node1, node1, WON);
    digraph<string,int>::arc_iterator arc6 = graph.arc_insert(node2, node1, WON);
    digraph<string,int>::arc_iterator arc7 = graph.arc_insert(node3, node1, WON);

    digraph<string,int>::arc_iterator arc8 = graph.arc_insert(node4, node1, WON);
    digraph<string,int>::arc_iterator arc9 = graph.arc_insert(node4, node1, LOSS);

}//hD_initGraph



digraph<string,int>::const_iterator getNextNode(const digraph<string,int>& graph,  const digraph<string,int>::const_iterator node, int lastBetResult){

  static char lastBetResult_ch[10];


  digraph<string,int>::const_arc_iterator out_arc;
  digraph<string,int>::const_iterator nextNODE;

  if (lastBetResult==LOSS)
    sprintf(lastBetResult_ch, "%s", "LOSS");
  else if (lastBetResult==WON)
    sprintf(lastBetResult_ch, "%s", "WON");
  


  for (unsigned it = 0; it < graph.fanout(node); it++)
  {

     out_arc = graph.output(node, it);

     if (*out_arc==lastBetResult)
     {
       nextNODE=graph.arc_to(out_arc);
       fout << "for node: " << *node << " next selected node:  " <<  *nextNODE << " if " << lastBetResult << " " << lastBetResult_ch << endl;
     }
  }

  return (nextNODE);

}//getNextNode

static void hD_traverse (const digraph<string,int>& graph)
{


  fout << "***********************************>>>>>>>>>>>>>>>" << endl;

  digraph<string,int>::const_iterator theNextNode;

  for (digraph<string,int>::const_iterator thisNode = graph.begin(); thisNode!= graph.end(); thisNode++)
  {

    fout << "  " << *thisNode << " is a node, "  << endl;

    theNextNode=getNextNode(graph, thisNode, WON);
    fout << "theNextNode " << *theNextNode << endl;

    theNextNode=getNextNode(graph, thisNode, LOSS);
    fout << "theNextNode " << *theNextNode << endl;
  }//for

   fout << "... END hD_traverse" << endl;

}//hD_traverse




int main(int argc, char* argv[])
{


    digraph<string,int> graph;

    hD_initGraph(graph);

    hD_traverse(graph);



}

for compiling, you have to link stlpuls library and to access STLplus headers:

... -I$(STL_DIR)
... -L$(STL_DIR)/LINUX-i686-debug -lstlplus

thanks for help ...

hector