Creating Linked Lists in Python
J-Burns
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
andrew cooke
> 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.
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
andrew cooke
[...]
i messed up my example; corrected below (I hope)
> in your case you could use ints for the nodes and a dict([int]) for the
> graph. so:
>
{1: [2,3], 2: [1,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.
and to take it a little further, you might also want to store the letter
associated with the transition. so for the NFA at
http://en.wikipedia.org/wiki/Automata_theory you'd use:
{1: [('a',1),('b',1),('a',2)], 2:[('a',3),('b',3)]}
or you could replace the list of transitions with a dict:
{1: {'a':[1,2], 'b':[1]}, 2:{'a':[3], 'b':[3]}}
andrew
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
> 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
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
And if you don't mind me asking. How do you invoke lambda from
transitions?
grocery_stocker
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
>>> # 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: [],
>>> }
>>
>> 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
> On Mar 21, 6:38 am, Tim Chase <python.l...@tim.thechases.com> wrote:
>
>
>
> > > 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:
>
> > 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?
I think you are looking at a composite or a piece-wise function.
'numpy' has those.
grocery_stocker
To my defense, I would like to say that I started with python like 2
weeks ago.
Roy Smith
Tim Chase <pytho...@tim.thechases.com> wrote:
> 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.
andrew cooke
[...]
> 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.
Just been reminded of this thread by Gabriel's summary - I've now released
an an initial version of code that represents DFAs and NFAs (and can
convert from NFA to DFA) for arbitrary alphabets. It's documented at
http://www.acooke.org/lepl/api/lepl.regexp.core-module.html (you can see
the source there too) and available as part of LEPL.
(I've just noticed that the comments in Sequence are incorrect,
unfortunately - please ignore any mention of "index").
Andrew
Aahz
andrew cooke <and...@acooke.org> wrote:
>
>(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 (aa...@pythoncraft.com) <*> 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
andrew cooke
> In article <mailman.2838.1238247...@python.org>,
> andrew cooke <and...@acooke.org> wrote:
>>(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
Aahz
This is one reason why my preferred unit test approach focuses on
doctest. (Another big reason is that I'm a lazy bum. ;-)
--
Aahz (aa...@pythoncraft.com) <*> 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'. :-)"
andrew cooke
> 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.
replying to this dead thread mainly for anyone using google. there's now
a python regular expression engine in lepl and the source code can be seen
via http://www.acooke.org/lepl/api/lepl.regexp-module.html
in particular, i found that the critical collection was a map from
interval to values which automatically fragments (i think discussion of
this thread ended up looking at maps). so, for example, if (1,10) maps to
'foo' then adding (4,5) -> 'bar' gives:
(1,3) -> foo
(4,5) -> foo, bar
(6,10) -> foo
in simple terms that lets you construct transitions for ranges of values -
typically a range of character with a mapped value that is the new state
in the machine. so if you have a-d going to state 5, and then add d-f
going to state 6, you want d (ie ('d','d')) to go to both 5 and 6 when
constructing a nfa.
that structure is here -
http://www.acooke.org/lepl/api/lepl.regexp.interval-pysrc.html#TaggedFragments
(minimal docs at
http://www.acooke.org/lepl/api/lepl.regexp.interval.TaggedFragments-class.html)
hope that makes sense. it could probably be more efficient (does an O(n)
scan of all intervals each time a new interval is added so is O(n^2)), but
since this is used in the "compile" part of a regexp, speed may not be as
important as in the "match" phase.
andrew