1

I'm solving a search problem for which the nodes of the graph are naturally labeled by nested lists. I want to use methods (e.g. uniform cost) for which I need to associate a cost function to each node.

My instinct is to use a lookup table with the node labels (= nested lists) as keys, yielding a list of cost function values for each key. I understand why unhashable objects like lists can't be used as keys in dicts, e.g., Lookup table for unhashable in Python. But the node labels ought to be mutable - when I compute the neighbors of a node, this is done by operations on the node label.

Alternatively I could make a Node class with a property that is the node label. However, I don't have a set of initially defined nodes - it grows during the search. So I need to keep extracting the list of node labels from the list of nodes.

Right now I am leaning toward converting the node labels back and forth from mutable to immutable types, so that I can both (1) compute a node's neighbors from its label and (2) use the node label as a dict key. But this feels dirty. Is there a better way?

Community
  • 1
  • 1
Dave Kielpinski
  • 1,152
  • 1
  • 9
  • 20
  • You could have an object that has some immutable attributes (used for implementing `__hash__` and `__eq__`) and some mutable attributes. – jonrsharpe Feb 26 '15 at 12:10
  • @jonrsharpe OK, but then I'm in for computing the mutable attributes of the neighbors from the mutable attributes, then searching for the neighbor objects via their mutable attributes. Since each node label is a nested list, it seems more natural just to convert back and forth using `tuple` and `list`, which was my original (unsatisfactory) thought. – Dave Kielpinski Feb 26 '15 at 12:17
  • Could you provide a concrete minimal example of what you're trying to achieve? It's hard to answer in the generic here. – jonrsharpe Feb 26 '15 at 12:18

1 Answers1

1

While it's somewhat hard to understand your question (a concrete example of a simple graph would be nice), it seems you are conflating three possibly different concepts: node identity, node labeling and the node adjacency matrix/list. Mixing these up, either in your head or in your code will probably lead to bad results.

Alternatively I could make a Node class with a property that is the node label.

This is probably a good idea to help you separate those.

However, I don't have a set of initially defined nodes - it grows during the search. So I need to keep extracting the list of node labels from the list of nodes.

I can't see a good reason why you wouldn't be able to create new nodes when needed and assign them the adjacency list (or update a adjacency matrix).

You may want to review a existing implementation with this class structure.

loopbackbee
  • 21,962
  • 10
  • 62
  • 97
  • Thanks. I know my question is a little vague. Since I'm trying to understand the merits of different general approaches, I'm having a hard time cooking up a minimal code example. Your link was very helpful - I think I just need to look at a range of example implementations. Of course I Googled a bunch of these before posting here, but couldn't find anything really satisfactory. – Dave Kielpinski Feb 27 '15 at 01:05
  • @DaveKielpinski If you're just starting out implementing graphs, it's probably worth reviewing [this wikipedia page](https://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29), in particular the *Representations* section, before diving into implementations – loopbackbee Feb 27 '15 at 10:47