0
\$\begingroup\$

I'm developing a game, which involves the use of nodes (buildings), and I need to implement neighbour networks that nodes can use to either directly or indirectly access other nodes. Nodes can be created, destroyed, or bridged to at any point in the game.

At the moment, I'm creating a list of all the nodes in a neighbour network, which is re-calculated whenever there is a new addition to the network. Each node in the network will hold a reference to this list. This system works, but I feel that there is a more efficient way to do this.

This is my current code for my node class

public class Node {
    public List<Node> directNeighbours;
    public List<Node> network;

    public void addNeighbour(Node n) {
        directNeighbours.add(n);
        recalculateNetwork();
    }

    public void removeNeighbour(Node n) {
        directNeighbours.remove(n);
        recalculateNetwork();
    }

    public void recalculateNetwork() {
        recalculateNetwork(new Network(), new HashSet<Node>());
    }

    void recalculateNetwork(List<Node> network, Set<Node> searched) {
        if (searched.contains(this)) return;

        network.add(this);
        this.network = network;

        for (Node neighbour : directNeighbours) {
            neighbour.recalculateNetwork(network, searched);
        }
    }
}

Is this the best way to keep track of direct and indirect neighbours? If not, could anyone please give me ideas on how to make this better?

\$\endgroup\$
  • 1
    \$\begingroup\$ Is this Java? Could use a language tag. \$\endgroup\$ – Wyck Mar 1 '18 at 15:50
  • \$\begingroup\$ There are many things wrong with your code snippet. Seems to be missing this.alreadySerached = true (sic - re: spelling mistake) Throwaway new network without assigning it to an object. It sounds like you're asking for a representation of the network. In which class, you should have a Network class (if it's just a List<Node> then that's find) and you should show your Node class (Hopefully it has a List<Node> neighbours field.) Not sure what algorithms on the network you're trying to make fast. Search for graph theory algorithms though. \$\endgroup\$ – Wyck Mar 1 '18 at 15:56
  • 2
    \$\begingroup\$ Efficient in terms of what? Different graph representations involve trade offs between memory consumption, speed & simplicity. What are you trying to improve? \$\endgroup\$ – Pikalek Mar 1 '18 at 17:23
  • \$\begingroup\$ I'm trying to cut back on the amount of times I actually have to call this method (which traverses all neighbouring nodes). At the moment, I'm calling it every time I add or remove a node from the network, and this could cause a noticeable amount of lag once the network starts to grow to larger sizes. I've edited my answer to include my whole node class. \$\endgroup\$ – invertedPanda Mar 3 '18 at 5:16
  • \$\begingroup\$ What exactly is recalculateNetwork() intended to do? Side note: past a certain point, recursion often scales poorly. \$\endgroup\$ – Pikalek Mar 3 '18 at 5:39
0
\$\begingroup\$

Your basic approach is okay, but there's some issues with your implementation. Specifically:

  • recalculateNetwork() creates a new network every time it gets called
  • recalculateNetwork(List<Node> network, Set<Node> searched) is recursive. As of 2015, Java doesn't optimize for tail-recursion. Until that changes, it's generally good to avoid it if performance is an issue.

That being said, some problems in general graph structures are always going to be problematic. For instance, whenever you remove an edge (i.e. by removing a direct neighbor relationship between nodes A & B) there's a chance that you've partition the graph into two unconnected sub-graphs. Here's an example:

Y-Z 
| |  
X-A-B-D-E

Removing the edge A,B results in two sub graphs as shown:

Y-Z 
| |  
X-A B-D-E

The only way to determine that is to start at one node & see if the other is reachable or not. Some conditions allow you to speed this up (chunking, caching, restrictions on connections), but in the general case, you have to search all nodes before you can be certain that the graph needs to be split.

Here's some sample code & a tester. Personally, I would consider making the network field its own class instead of directly using the HashMap, but that's me. I opted for this instead as it more closely follows what you were already doing & isn't necessarily wrong per say. I've tried to strike a balance between understandability & performance. If this is still not fast enough, then we'll need to examine other parts of the problem & code to see if there's anything else to take advantage of.

Some comments about hash keys: It wasn't clear how many Nodes you might need, so went with integer IDs for hash keys. If each node has some other unique identifier (name, coordinate location, etc), use that instead. If you plan on generating many different nodes, but never exceed some maximum value, consider using keys from an object pool. Finally, there's universally unique identifiers (UUIDs); they seemed like overkill for this, but if you outgrow this code, you might need to consider them.

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;

public class Node {
    private static int nextID = 0;
    private final int ID;
    private final HashMap<Integer, Node> neighbors;
    private HashMap<Integer, Node> network;

    /**
     * build a new node in its own network
     */
    public Node(){
        ID = nextID++;
        if(nextID == 0){
            throw new IllegalStateException("exhausted all node IDs");
        }
        neighbors = new HashMap<>();
        network = new HashMap<>();
        network.put(ID, this);
    }
    /**
     * build a new node & make it a direct neighbor of n
     * @param n the Node to make this node a direct neighbor of
     */
    public Node(Node n){
        ID = nextID++;
        neighbors = new HashMap<>();        
        this.network = n.network;
        network.put(ID, this);
        addNeighbor(n);
    }
    public int getID(){
        return ID;
    }    
    public boolean hasDirctNeighbor(Node n){
        return neighbors.containsKey(n.ID);
    }
    public boolean hasIndirctNeighbor(Node n){
        return network.containsKey(n.ID);
    }
    /**
     * get all of the direct neighbors of this node
     * @return collection of all direct neighbors
     */
    public Collection<Node> getDirectNeighbors(){
        return new ArrayList<>(neighbors.values());
    }
    /**
     * get all of the nodes in network of this node
     * @return collection of all nodes in the network
     */
    public Collection<Node> getAllNeighbors(){
        return new ArrayList<>(network.values());
    }
    private void mergeNetworks(HashMap<Integer, Node> other){
        HashMap<Integer, Node> larger = network;
        HashMap<Integer, Node> smaller = other;
        if(other.size() > network.size()){
            larger = other;
            smaller = network;
        }
        for(Node n : smaller.values()){
            n.network = larger;
            network.put(n.ID, n);
        }
        smaller.clear();
    }
    /**
     * add n to this node's direct neighbors - merges the networks if 
     * necessary
     * @param n the node to add - note cannot be the same as this node
     */
    public final void addNeighbor(Node n){
        if(n == this){
            throw new IllegalStateException("cannot make node a neighbor with itself");
        }
        // if the node don't already share a network, then the two networks 
        // must be merged
        if(!network.containsKey(n.ID)){
            mergeNetworks(n.network);
        }
        neighbors.put(n.ID, n);
        n.neighbors.put(this.ID, this);
    }
    /**
     * remove n from this node's direct neighbors (but not necessarily the network)
     * splits the network only if necessary
     * @param n the node to remove - note cannot be the same as this node
     */
    public void removeNeighbor(Node n){
        if(n == this){
            throw new IllegalStateException("cannot remove a node from itself");
        }
        neighbors.remove(n.ID);
        n.neighbors.remove(this.ID);
        // check if any other node we can reach from this node
        HashMap<Integer, Node> tempNetwork = new HashMap<>();
        ArrayList<Node> queue = new ArrayList<>();
        queue.add(this);
        tempNetwork.put(ID, this);
        while(!queue.isEmpty()){
            Node tempNode = queue.remove(0);
            for(Node neighborOfTempNode : tempNode.neighbors.values()){
                // found it, no need to split the network
                if(neighborOfTempNode == n){
                    return;
                }
                if(!tempNetwork.containsKey(neighborOfTempNode.ID)){
                    queue.add(neighborOfTempNode);
                    tempNetwork.put(neighborOfTempNode.ID, neighborOfTempNode);
                }
            }
        }
        // unable reach n from this node, therefore we must split
        for(Node local : tempNetwork.values()){
            local.network = tempNetwork;
            n.network.remove(local.ID);
        }
    }
    /**
     * removes this node from the network & from an direct neighbors it had
     */
    public void removeFromNetwork(){
        Collection<Node> oldNeighbors = this.getDirectNeighbors();
        for(Node n : oldNeighbors){
            n.removeNeighbor(this);
        }        
    }
}

Tester/demo code:

public class Tester {
    public static void main(String[] args){
        Node[] nodes = new Node[7];
        for(int a=0; a<nodes.length; a++){
            nodes[a] = new Node();
        }
        for(Node n : nodes){
            System.out.println(info(n));
        }
        add(nodes[0], nodes[1]);
        add(nodes[2], nodes[3]);
        add(nodes[4], nodes[5]);
        add(nodes[4], nodes[6]);
        for(Node n : nodes){
            System.out.println(info(n));
        }
        add(nodes[0], nodes[6]);
        add(nodes[0], nodes[5]);
        for(Node n : nodes){
            System.out.println(info(n));
        }
        remove(nodes[0], nodes[1]);
        remove(nodes[4], nodes[6]);
        for(Node n : nodes){
            System.out.println(info(n));
        }
        isolate(nodes[5]);
        for(Node n : nodes){
            System.out.println(info(n));
        }
    }
    public static void add(Node n1, Node n2){
        System.out.println("adding " + n2.getID() + " to " + n1.getID());
        n1.addNeighbor(n2);
    }
    public static void remove(Node n1, Node n2){
        System.out.println("removing " + n2.getID() + " from " + n1.getID());
        n1.removeNeighbor(n2);
    }
    public static void isolate(Node n){
        System.out.println("removing " + n.getID() + " completely from its network");
        n.removeFromNetwork();
    }
    public static String info(Node n){
        String result = "ID: " + n.getID();
        result += "\tfull network: " + networkString(n);
        result += "\tdirect neighbors: " + neigborString(n);
        return result;
    }
    public static String neigborString(Node n){
        String result = "(";
        for(Node t : n.getDirectNeighbors()){
            result += " " + t.getID();
        }
        result += " )";
        return result;
    }
    public static String networkString(Node n){
        String result = "< ";
        for(Node t : n.getAllNeighbors()){
            result += t.getID() + " ";
        }
        result += ">";
        return result;
    }
}
\$\endgroup\$
  • \$\begingroup\$ This is exactly what I needed, thank you so much. :) \$\endgroup\$ – invertedPanda Mar 9 '18 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.