This week's book giveaway is in the OCAJP 8 forum. We're giving away four copies of OCA Java SE 8 Programmer I Study Guide and have Edward Finegan & Robert Liguori on-line! See this thread for details.
I am writing an artificial intelligence application and I need a forked linked list of objects searchable in both directions. An object of type A will point to one or more objects of type B and objects type B can point to one or more objects type A. The network of objects must be added to and grown by the user and an object of type B can be removed and replaced by a new subnetwork. I have no idea how to do this.
Years ago in C I wrote a linked list of functions as follows:
typedef void (*wordPointer)(void); // define a pointer to a void function
wordPointer X; // create such a pointer X
later in a function
(*X)(); // heres the link in a function pointing to the next function in the list
I did not quite follow what you were explaining there, for starters have you considered using java.util.LinkedList
Joined: Mar 15, 2009
First place i looked was linked lists. Didn't seem to do the job. What I need to know is how do I modify a linked list. My list has forks and branches (multiple pathways). With AI you can start with a premise or axiom and search forward through rules and relationships to see if you can find an answer. Or you can start with a hypothesis (at the end) and search backwards through relationships and see if you can prove it from the axiom. You usually want to do both. But I also need to break the chain in the middle and insert a more complex set of rules and relationships as the knowledge grows.
It would be easy if I could make dynamic pointers to structures as with Pascal or C. But I am completely new to java (3 weeks).
I will paste a GIF diagram to see if it explains it better.
Joined: Mar 07, 2009
I seriously doubt that you will be able to trivially use any of the collections classes for this kind of data structure. Extending an existing collection would, IMO, not be the best option either, but this is obviously a debatable point.
From your post it seems like you have done similar work in C/Pascal. It would be much easier to do such a data structure in Java given its object oriented nature and easier memory management. If I were you I would start looking at the source code of LinkedList to get an idea how to implement it. If you know the semantics of the data structure, it should not be too hard for you.
There isn't an existing class for this in the API. I first thought about using a TreeNode, but then I saw your picture which also allows a node to have two "parents" - something not possible in a Tree.
Perhaps you can base your new class on the TreeNode interface; the only difference is that there shouldn't be a getParent() method but a getParents() method that returns a collection of all parents. And if you're going to copy that interface, please remove all references to Enumeration - Iterator is the way to go.
So what you have here is a graph. I think you'd need to implement a GraphNode class yourself (perhaps abstract and subclass it with TypeAGraphNode and TypeBGraphNode) with methods like public List<GraphNode> getChildren() and public List<GraphNode> getParents() and maybe public void replace(TypeBGraphNode n) for TypeBGraphNode. That's what comes to my mind...
Joined: Mar 15, 2009
Thanks for the help everyone. I did have a look at trees as well as linked lists. Coming from C I am used to just opening a header file to get at the source and I still find it disconcerting to chase up through several generations of classes to find the heart of the technique.
Here's what I did: I had two choices. I could write the data structure and inference engine in C and pass the data through shared data files to a Java GUI. I can hear the purists wincing, but I am an engineer and whatever works . . . Or I could stick to Java and forget about pointers and operate through integer identifiers in the class to replace the pointers. Then put all the objects (A&B) in two vectors which the inference engine can search.
I wrote a prototype in C (without pointers) which works beautifully and because it is well structured allows me to define the classes in Java. The only penalty is that without pointers the integer ID searches consume extra processing time. Looks like it is going to work and it is surprisingly compact. I will look at GraphNode classes next.