Creating Linked Lists in Python

[J-Burns]

Hey thr,

I need some help here actually. So i thought i could get it easily
from here.

I need to make a linked list that can do the following:

1) Point to multiple nodes at one time
2) Should have 2 values:
a) The node no.
b) The value of that node in reference to the next node that it is
pointing to

For example, this means that there can be a start node supposedly.
Having a value of 0. It is pointing to node 1 with the value of "a"
and to node 2 with the value of "b". Trying to make something like an
NFA. Where id be changing regular expressions to NFAs.

How can I do this? And if I could do this by some other way than using
linked lists than do tell me about that as well.

 

[John Machin]

Hey thr,

I need some help here actually. So i thought i could get it easily
from here.

I need to make a linked list that can do the following:

1) Point to multiple nodes at one time

The term "linked list" is usually restricted to a collection of nodes
each of which has a value, a pointer to the next mode in the list, and
maybe a pointer to the previous node in the list. You want much more
than that.

2) Should have 2 values:
    a) The node no.
    b) The value of that node in reference to the next node that it is
pointing to

For example, this means that there can be a start node supposedly.
Having a value of 0. It is pointing to node 1 with the value of "a"
and to node 2 with the value of "b". Trying to make something like an
NFA. Where id be changing regular expressions to NFAs.

How can I do this? And if I could do this by some other way than using
linked lists than do tell me about that as well.

What you want is a collection of nodes each of which has a value (that
you haven't specified and may not need) plus a mapping from something
to other nodes. In this case the something appears to be the input
characters from a text to be match against your RE.

The simplest structure for that in Python, omitting your maybe-needed
node value, would be a list of nodes, where each node is a dict
mapping input characters to node numbers ...

nfa = [
{'a': 1, 'b': 2, }, # this is node 0
etc,
etc,
]

Instead of a Python list and using list indexes as node IDs, you may
end up writing a class that maintains an NFA as a collection of nodes,
where each node is an instance of an NFANode class ... each such node
would have as an attribute a dict mapping input characters to other
nodes -- this is the essential concept.

BTW, is this homework?

Cheers,
John

 

[Aaron Brady]

J-Burns wrote: snip

For example, this means that there can be a start node supposedly.
Having a value of 0. It is pointing to node 1 with the value of "a"
and to node 2 with the value of "b". Trying to make something like an
NFA. Where id be changing regular expressions to NFAs.

How can I do this? And if I could do this by some other way than using
linked lists than do tell me about that as well.

when you mention NFAs and regular expressions, you make me think that you
don't want a linked list at all, but a graph.  there are various ways of
storing a graph, but one of the simplest is to use a dict() that maps from
source to destination node(s).

in your case you could use ints for the nodes and a dict([int]) for the
graph.  so:

{1: [2,3], 2: [3], 3: [3]}

is a graph in which 1 and 2 are connected in each direction, both 1 and 2
are linked to 3, and 3 has a loop that links back to itself.

andrew

WARNING, spoiler.

So far, Andrew's and John's structures can be used for both a DFA and
a NFA. The only thing further you need is a collection instead of a
single value to hold current state.

states= set( [ 1 ] )
while 1:
_newstates= set( )
for state in states:
_newstates.update( transitions[ state ] )
states= _newstates
# or states.clear( ); states.update( _newstates )

How will you mark a state as 'final'/ success?

 

[Tim Chase]

For example, this means that there can be a start node supposedly.

Having a value of 0. It is pointing to node 1 with the value of "a"
and to node 2 with the value of "b". Trying to make something like an
NFA. Where id be changing regular expressions to NFAs.

John has already pointed out the preconception problems of
"linked list".

In the past, I've done NFA with a state machine:

(STATE_A,
STATE_B,
STATE_C,
STATE_D,
) = range(4)

transitions = {
# values are tuples of (newstate, transition_function)
STATE_A: [
(STATE_B, lambda x: x > 5),
(STATE_C, lambda x: x > 10),
(STATE_D, lambda x: x > 100),
],
STATE_B: [
(STATE_A, lambda x: x < 5),
(STATE_C, lambda x: x > 10),
],
STATE_C: [
(STATE_B, lambda x: x < 10),
(STATE_D, lambda x: x > 100),
],
STATE_D: [],
}

You may have to carry around extra information regarding your
state, and tweak accordingly. Instead of tuples of (newstate,
transition_function), you could just use transition functions
that return the new state, or None if they're not satisfied.

You then simply maintain your current state, and then test your
incoming stream of tokens/data against your transition function
to see if you can transition to the resulting state. Depending
on whether you need back-tracking, you'll want to gather all the
possible results, or otherwise may just settle for the first
available transition to a new state.

-tkc

 

[Giuliano Vilela]

I've done something similar on the past week, regarding RE's and
NFA's: http://code.google.com/p/yaree/

The significant code is on re_fsa.py, on the svn repository. The
implementation is also a dict, of the form: { Node -> { Character ->
Set(Node) } }. That is, it is a mapping of Node's to a mapping M
representing it's transitions. M is a mapping of characters to set's
of nodes. That way, it supports both FA's and NFA's.

 

[grocery_stocker]

For example, this means that there can be a start node supposedly.
Having a value of 0. It is pointing to node 1 with the value of "a"
and to node 2 with the value of "b". Trying to make something like an
NFA. Where id be changing regular expressions to NFAs.

John has already pointed out the preconception problems of
"linked list".

In the past, I've done NFA with a state machine:

(STATE_A,
STATE_B,
STATE_C,
STATE_D,
) = range(4)

transitions = {
# values are tuples of (newstate, transition_function)
STATE_A: [
(STATE_B, lambda x: x > 5),
(STATE_C, lambda x: x > 10),
(STATE_D, lambda x: x > 100),
],
STATE_B: [
(STATE_A, lambda x: x < 5),
(STATE_C, lambda x: x > 10),
],
STATE_C: [
(STATE_B, lambda x: x < 10),
(STATE_D, lambda x: x > 100),
],
STATE_D: [],
}

You may have to carry around extra information regarding your
state, and tweak accordingly. Instead of tuples of (newstate,
transition_function), you could just use transition functions
that return the new state, or None if they're not satisfied.

You then simply maintain your current state, and then test your
incoming stream of tokens/data against your transition function
to see if you can transition to the resulting state. Depending
on whether you need back-tracking, you'll want to gather all the
possible results, or otherwise may just settle for the first
available transition to a new state.

And if you don't mind me asking. How do you invoke lambda from
transitions?

 

[grocery_stocker]

John has already pointed out the preconception problems of
"linked list".

In the past, I've done NFA with a state machine:

(STATE_A,
STATE_B,
STATE_C,
STATE_D,
) = range(4)

transitions = {
# values are tuples of (newstate, transition_function)
STATE_A: [
(STATE_B, lambda x: x > 5),
(STATE_C, lambda x: x > 10),
(STATE_D, lambda x: x > 100),
],
STATE_B: [
(STATE_A, lambda x: x < 5),
(STATE_C, lambda x: x > 10),
],
STATE_C: [
(STATE_B, lambda x: x < 10),
(STATE_D, lambda x: x > 100),
],
STATE_D: [],
}

You may have to carry around extra information regarding your
state, and tweak accordingly. Instead of tuples of (newstate,
transition_function), you could just use transition functions
that return the new state, or None if they're not satisfied.

You then simply maintain your current state, and then test your
incoming stream of tokens/data against your transition function
to see if you can transition to the resulting state. Depending
on whether you need back-tracking, you'll want to gather all the
possible results, or otherwise may just settle for the first
available transition to a new state.

And if you don't mind me asking. How do you invoke lambda from
transitions?

Disregard that. I think I figured it out.

If you had something like...

transitions = {1: [2, lambda x: 2*x]}

You would probably call it like...

transitions[1][1](4)

8

 

[Tim Chase]

transitions = {

# values are tuples of (newstate, transition_function)
STATE_A: [
(STATE_B, lambda x: x > 5),
(STATE_C, lambda x: x > 10),
(STATE_D, lambda x: x > 100),
],
STATE_B: [
(STATE_A, lambda x: x < 5),
(STATE_C, lambda x: x > 10),
],
STATE_C: [
(STATE_B, lambda x: x < 10),
(STATE_D, lambda x: x > 100),
],
STATE_D: [],
}

And if you don't mind me asking. How do you invoke lambda from
transitions?

Disregard that. I think I figured it out.

If you had something like...

transitions = {1: [2, lambda x: 2*x]}

You would probably call it like...

transitions[1][1](4)

8

I tend to use them with tuple assignment which I find reads more
cleanly than directly indexing:

for input in source():
available_states = []
for new_state, function in transitions[state]:
if function(input):
available_states.append(new_state)
do_something(available_states)

-tkc

 

[Aaron Brady]

snip


And if you don't mind me asking. How do you invoke lambda from
transitions?

I think you are looking at a composite or a piece-wise function.
'numpy' has those.

 

[grocery_stocker]

transitions = {
# values are tuples of (newstate, transition_function)
STATE_A: [
(STATE_B, lambda x: x > 5),
(STATE_C, lambda x: x > 10),
(STATE_D, lambda x: x > 100),
],
STATE_B: [
(STATE_A, lambda x: x < 5),
(STATE_C, lambda x: x > 10),
],
STATE_C: [
(STATE_B, lambda x: x < 10),
(STATE_D, lambda x: x > 100),
],
STATE_D: [],
}
And if you don't mind me asking. How do you invoke lambda from
transitions?

Disregard that. I think I figured it out.

If you had something like...

transitions = {1: [2, lambda x: 2*x]}

You would probably call it like...

transitions[1][1](4)

8

I tend to use them with tuple assignment which I find reads more
cleanly than directly indexing:

for input in source():
available_states = []
for new_state, function in transitions[state]:
if function(input):
available_states.append(new_state)
do_something(available_states)

To my defense, I would like to say that I started with python like 2
weeks ago.

 

[Roy Smith]

In the past, I've done NFA with a state machine:

What I've done at times is have each state be a function. The function
returns an (output, next_state) tuple, and the main loop becomes something
like this:

state = start
for input in whatever:
output, state = state(input)

and the states look like:

def start(input):
next_state = blah
output = blah
return (output, next_state)

It's not always the right organization (and is almost certainly not for
machines with large numbers of states), but I've found it useful for a lot
of ad-hoc file parsing that I've done.

 

[Aahz]

(I've just noticed that the comments in Sequence are incorrect,
unfortunately - please ignore any mention of "index").

s/comments/lies/ per my .sig ;-)
--
Aahz ([email protected]) <*> http://www.pythoncraft.com/

"At Resolver we've found it useful to short-circuit any doubt and just
refer to comments in code as 'lies'. "
--Michael Foord paraphrases Christian Muirhead on python-dev, 2009-3-22

 

[Aahz]

(I've just noticed that the comments in Sequence are incorrect,
unfortunately - please ignore any mention of "index").

s/comments/lies/ per my .sig ;-) [...]
"At Resolver we've found it useful to short-circuit any doubt and just
refer to comments in code as 'lies'. "

yeah, it's hard. i tend to add comments as i work through the problem,
but maybe i should delete them all at the end - in that case i originally
had the definition of the regexps and their evaluation all mixed up in the
same objects. it was chaos. i find writing a package like that in spare
time is surprisingly hard - more pressure than at work in some ways (want
to do so much more, have much less time). andrew

This is one reason why my preferred unit test approach focuses on
doctest. (Another big reason is that I'm a lazy bum. ;-)
--
Aahz ([email protected]) <*> http://www.pythoncraft.com/

"At Resolver we've found it useful to short-circuit any doubt and just
refer to comments in code as 'lies'. "
--Michael Foord paraphrases Christian Muirhead on python-dev, 2009-3-22