What is a cyclic data structure good for?

Question

Hello,

I was just reading through "Learning Python" by Mark Lutz and came across this code sample:

>>> L = ['grail']
>>> L.append(L)
>>> L
['grail', [...]]

It was identified as a cyclic data structure.

So I was wondering, and here is my question:

What is a 'cyclic data structure' used for in real life programming?

There seems to be a little confusion, which i think stems from the very brief code sample... here's a few more lines using the same object L

>>> L[0]
'grail'
>>> L[1][0]
'grail'
>>> L[1][1][0]
'grail'

edit: I'll be honest, I still don't really get it. can anyone give some code samples?

Answer 1

Erm, I am not sure as I a haven't used them at all in real life, but it could be used to simulate a nested data structure? See this link

Answer 2

One example would be a linked list where the last item points the first. This would allow you to create a fixed number of items but always be able to get a next item.

Answer 3

Lots of things. Circular buffer, for example: you have some collection of data with a front and a back, but an arbitrary number of nodes, and the "next" item from the last should take you back to the first.

Graph structures are often cyclic; acyclicity is a special case. Consider, for example, a graph containing all the cities and roads in a traveling salesman problem.

---

Okay, here's a particular example for you. I set up a collection of towns here in Colorado:

V=["Boulder", "Denver", "Colorado Springs", "Pueblo", "Limon"]

I then set up pairs of cities where there is a road connecting them.

E=[["Boulder", "Denver"],
   ["Denver", "Colorado Springs"],
   ["Colorado Springs", "Pueblo"],
   ["Denver", "Limon"],
   ["Colorado Springs", "Limon"]]

This has a bunch of cycles. For example, you can drive from Colorado Springs, to Limon, to Denver, and back to Colorado Springs.

If you create a data structure that contains all the cities in V and all the roads in E, that's a graph data structure. This graph would have cycles.

Answer 4

when doing lattice simulations cyclic/toroidal boundary conditions are often used. usually a simple lattice[i%L] would suffice, but i suppose one could create the lattice to be cyclic.

Answer 5

A nested structure could be used in a test case for a garbage collector.

Answer 6

I recently created a cyclic data structure to represent the eight cardinal and ordinal directions. Its useful for each direction to know its neighbors. For instance, Direction.North knows that Direction.NorthEast and Direction.NorthWest are its neighbors.

This is cyclic because each neighor knows its neighbors until it goes full swing around (the "->" represents clockwise):

North -> NorthEast -> East -> SouthEast -> South -> SouthWest -> West -> NorthWest -> North -> ...

Notice we came back to North.

That allows me to do stuff like this (in C#):

public class Direction
{
    ...
    public IEnumerable<Direction> WithTwoNeighbors
    {
        get {
           yield return this;
           yield return this.CounterClockwise;
           yield return this.Clockwise;
        }
    }
}
...
public void TryToMove (Direction dir)
{
    dir = dir.WithTwoNeighbors.Where (d => CanMove (d)).First ()
    Move (dir);
}

This turned out to be quite handy and made a lot of things much less complicated. Here's the full class.

Answer 7

Suppose you have limited storage, and data constantly accumulates. In many real life cases, you don't mind getting rid of old data, but you don't want to move data. You can use a cyclic vector; implemented using a vector v of size N with two special indices: begin and end, which initiate on 0.

Insertion of "new" data now goes like this:

v[end] = a;
end = (end+1) % N;
if (begin == end)
  begin = (begin+1) % N;

You can insert "old" data and erase "old" or "new" data in a similar way. Scanning the vector goes like this

for (i=begin; i != end; i = (i+1) % N) {
 // do stuff
}

Answer 8

Cyclic data structures are usually used to represent circular relationships. That sounds obvious, but it happens more than you think. I can't think of any times I've used terribly complicated cyclical data structures, but bidirectional relationships are fairly common. For example, suppose I wanted to make an IM client. I could do something like this:

class Client(object):
    def set_remote(self, remote_client):
        self.remote_client = remote_client

    def send(self, msg):
        self.remote_client.receive(msg)

    def receive(self, msg):
        print msg

Jill = Client()
Bob = Client()
Bob.set_remote(Jill)    
Jill.set_remote(Bob)

Then if Bob wanted to send a message to Jill, you could just do this:

Bob.send("Hi, Jill!")

Of course, Jill may want to send a message back, so she could do this:

Jill.send("Hi, Bob!")

Admittedly, this is a bit of a contrived example, but it should give you an example of when you may want to use a cyclical data structure.

Answer 9

Any kind of object hierarchy where parents know about their children and children know about their parents. I'm always having to deal with this in ORMs because I want databases to know their tables and tables to know what database they're a part of, and so on.

Answer 10

It is a bit confusing since it is a list that contains itself, but the way I made sense of it is to not think of L as a list, but a node, and instead of things in a list, you think of it as other nodes reachable by this node.

To put a more real world example, think of them as flight paths from a city.

So chicago = [denver, los angeles, new york city, chicago] (realistically you wouldn't list chicago in itself, but for the sake of example you can reach chicago from chicago)

Then you have denver = [phoenix, philedelphia] and so on.

phoenix = [chicago, new york city]

Now you have cyclic data both from

chicago -> chicago

but also

chicago -> denver -> phoenix -> chicago

Now you have:

chicago[0] == denver
chicago[0][0] == phoenix
chicago[0][0][0] == chicago

Answer 11

L just contains a reference to itself as one of it's elements. Nothing really special about this. There are some obvious uses of cyclical structures where the last element knows about the first element. But this functionality is already covered by regular python lists.

You can get the first element by using [-1]. You can use python lists as queues with append() and pop(). You can split python lists. Which are the regular uses of a cyclical data structure.

>>> L = ['foo', 'bar']
>>> L.append(L)
>>> L
['foo', 'bar', [...]]
>>> L[0]
'foo'
>>> L[1]
'bar'
>>> L[2]
['foo', 'bar', [...]]
>>> L[2].append('baz')
>>> L
['foo', 'bar', [...], 'baz']
>>> L[2]
['foo', 'bar', [...], 'baz']
>>> L[2].pop()
'baz'
>>> L
['foo', 'bar', [...]]
>>> L[2]
['foo', 'bar', [...]]

Answer 12

The data structures iterated by deterministic finite automata are often cyclical.

Answer 13

Let's look at a single practical example.

Let us say we're programming a menu navigation for a game. We want to store for each menu-item

1. The entry's name
2. The other menu we'll reach after pressing it.
3. The action that would be performed when pressing the menu.

When a menu-item is pressed, we'll activate the menu-item action and then move to the next menu. So our menu would be a simple list of dictionaries, like so:

options,start_menu,about = [],[],[]

def do_nothing(): pass

about += [
    {'name':"copyright by...",'action':None,'menu':about},
    {'name':"back",'action':do_nothing,'menu':start_menu}
    ]
options += [
    {'name':"volume up",'action':volumeUp,'menu':options},
    {'name':"save",'action':save,'menu':start_menu},
    {'name':"back without save",'action':do_nothing,'menu':start_menu}
    ]
start_menu += [
    {'name':"Exit",'action':f,'menu':None}, # no next menu since we quite
    {'name':"Options",'action':do_nothing,'menu':options},
    {'name':"About",'action':do_nothing,'menu':about}
    ]

See how about is cyclic:

>>> print about
[{'action': None, 'menu': [...], 'name': 'copyright by...'},#etc.
# see the ellipsis (...)

When a menu item is pressed we'll issue the following on-click function:

def menu_item_pressed(item):
    log("menu item '%s' pressed" % item['name'])
    item['action']()
    set_next_menu(item['menu'])

Now, if we wouldn't have cyclic data structures, we wouldn't be able to have a menu item that points to itself, and, for instance, after pressing the volume-up function we would have to leave the options menu.

If cyclic data structures wouldn't be possible, we'll have to implement it ourselves, for example the menu item would be:

class SelfReferenceMarkerClass: pass
#singleton global marker for self reference
SelfReferenceMarker = SelfReferenceMarkerClass()
about += [
    {'name':"copyright by...",'action':None,'menu':srm},
    {'name':"back",'action':do_nothing,'menu':start_menu}
    ]

the menu_item_pressed function would be:

def menu_item_pressed(item):
    item['action']()
    if (item['menu'] == SelfReferenceMarker):
        set_next_menu(get_previous_menu())
    else:
        set_next_menu(item['menu'])

The first example is a little bit nicer, but yes, not supporting self references is not such a big deal IMHO, as it's easy to overcome this limitation.

The menus example is like a graph with self references, where we store the graph by lists of vertex pointers (every vertex is a list of pointers to other vertices). In this example we needed self edges (a vertex that points to itself), thus python's support for cyclic data structures is useful.