A pattern I've never figured out how to properly implement

So I'll try an generalize this question. So say you have an object called Node, which are stored in a Graph object. Now you want every Node to be aware of what Graph it is in, so you make a property for that. But, you also want the ability to move a Node from one Graph to another. Now a Node can have many other various objects referencing it, so you can't simply delete it and re-create it in the new Graph, you have to actually set the Graph reference in the Node to the new Graph and remove it from the old Graph's list and put it in the new one's. So here are some problems:

• You don't want the ability to change a Node's Graph property. This could lead to a situation where a Graph thinks it contains a Node, but that Node thinks it belongs to another Graph.
• If you put the Graph reference in the constructor, and make it a get only property, it can't be changed.
• The main problem is keeping the data in sync. Basically, whenever you change one variable, the other must also be changed

Anyone have any suggestions?

 

How about some kind of graph operations master. The class could contain a list of graphs and what nodes they contain. If you want to swap nodes, you query the master or your nodes can query the master themselves. The master handles the exchange locally. All data is contained in the master.

The nodes could implement a graph property like you want, but the get accessor would go along the lines of

Code (CSharp):

1. public Graph Container { get { return GraphData.Instance.GetGraphByNode(this); } }

 

So I tried that, as well as a GUID based system, but what do you think of this:

Nodes have a TransferToGraph methed, and graphs have an AcceptNodeTransfer method. The TransferToGraph method sets the Node's Graph to the selected Graph, and then calls AcceptNodeTransfer on that Graph. AcceptNodeTransfer removes the Node from its previous graph, and puts it into itself, only provided the node already has its graph set to itself. This way, node transfers can only be done through TransferToGraph, and AcceptNodeTransfer simply throws an error if you use it improperly.

So something like:

Graph.cs

Code (CSharp):

1. AcceptNodeTransfer(Node node)
2. {
3.     if (node.graph == this)
4.     {
5.         // accept
6.     }
7.     else
8.     {
9.         // throw error
10.     }
11. }

Node.cs

Code (CSharp):

1. TransferToGraph(Graph graph)
2. {
3.     this.graph = graph;
4.     graph.AcceptNodeTransfer(this);
5. }

 

My experience with graphs and trees has taught me that a "good" implementation depends entirely on the context of how it is being used. There is a reason there is no "Tree<T>" collection in the standard Microsoft collection catalogue.

In the scenarios I've made use of a distributed collection of nodes, it was not really necessary to have a class represent the concept of a "graph". The nodes are the graph.

Your implementation seems fine, but it's really impossible to evaluate in a vacuum. If you explain a more concrete problem, you'll probably get some better responses.

My suggestion is to think more about the problem you want to solve and less about the problems you could solve with one particular solution.​

 

In my case, the graph is a world, with nodes being points of interest in that world, and the edges being paths to travel between points of interest. There are multiple worlds, however, that the player can travel between, so I need some way to group what nodes and edges belong to what world. Certain events can cause part of one world to be pulled into another, and thus the nodes and paths need to move worlds while still retaining all their original properties. For now at least, my solution seems to be working. It feels a bit odd to have a method that is only able to be called from one other class without returning an error, but technically it works.

In World.cs:

Code (CSharp):

1. public void AcceptNode(Node node, World oldWorld)
2. {
3.     if (node.World == this && (oldWorld == null || oldWorld.RemoveNode(node)))
4.     {
5.         this.nodes.Add(node);
6.     }
7. }

Just a note: RemoveNode returns true if the node was found and removed, otherwise it returns false.

In Node.cs:

Code (CSharp):

1.  
2. public void SetWorld(World world)
3. {
4.     World oldWorld = this.World;
5.     this.World = world;
6.     this.World.AcceptNode(this, oldWorld);
7. }

 

You could do it like this:

Code (CSharp):

1. using JetBrains.Annotations;
2. using System.Collections.Generic;
3.  
4. public class Graph
5. {
6.     private readonly List<Node> nodes = new List<Node>();
7.  
8.     public class Node
9.     {
10.         [NotNull]
11.         private Graph graph;
12.  
13.         public Node([NotNull]Graph setGraph)
14.         {
15.             graph = setGraph;
16.             setGraph.nodes.Add(this);
17.         }
18.  
19.         public void MoveToGraph([NotNull]Graph newGraph)
20.         {
21.             graph.nodes.Remove(this);
22.             newGraph.nodes.Add(this);
23.             graph = newGraph;
24.         }
25.     }
26. }

 

The workaround, I think, is to have one class able to access the private properties of another. Nested classes are one way to accomplish that in C#. Nice example @SisusCo.


Taking a step back from implementation again, I'm just wondering, is it important that one node not belong to two worlds at once? What would it mean for a node to be part of a graph, but not connected to another node in that graph? Do you have some rule in mind for how the node will be attached to the other nodes?

So far, there isn't any discussion about how nodes are disconnected from their neighbors in the old graph and connected to ones inside the new graph.

What I'm driving at is that a class representing the umbrella concept "graph" is not always needed and it complicates the problem. Having a series of nodes connected together already is a graph. If you want to have both concepts at all times, you are adding synchronization considerations to an already complex problem.​

 

Ah. Normally a node moving from one graph to another is pointless. You'd need to remove every path in the old graph, leaving merely a node with a pointer to some data. It's easier to make a new node for the new graph.

In this case, the interesting thing is preserving _some_ of the edges. The input would be a list of nodes to move (or a rule such as "node A, and everything connected"). The trick is to mark every node to transfer, then destroy every path between staying nodes and leaving ones.

 

I agree a lot with what Eisenpony says here:

...

To give you an example of how I worked with this. I'll show you my A*/Dijkstra implementations found here:
https://github.com/lordofduct/space...ter/SPPathfinding/Graphs/AStarPathResolver.cs
https://github.com/lordofduct/space.../SPPathfinding/Graphs/DijkstraPathResolver.cs

So my A* and Dijkstra algorithms don't require a specific class but instead allow you to pass in any graph as long as it implements a simple interface of IGraph:

Code (csharp):

1.  
2.     public interface IGraph<T> : IEnumerable<T>
3.     {
4.  
5.         int Count { get; }
6.  
7.         IEnumerable<T> GetNeighbours(T node);
8.         int GetNeighbours(T node, ICollection<T> buffer);
9.         bool Contains(T node);
10.  
11.     }
12.  

https://github.com/lordofduct/space....0/blob/master/SPPathfinding/Graphs/IGraph.cs

All we need to know is that we have an enumerable of all the nodes in the graph, the ability to get a neighbours of a node in the graph, and if the graph contains a node. That's it. With that information we can pathfind through a graph.

As for setting up graphs... it's completely separate from what we needed the graph for (in this case for pathfinding... but this is why eisenpony brings up needing to know what you're using it for).

Since I've defined my graph so generically as an interface though. I can now define graphs any which way I want.

For example here is a graph that is just a NxN grid, called a GridGraph. The neighbours are dictated by the graph itself since the neighbours of a given node are relative to the graph's grid. A given node doesn't necessarily need to know anything about the graph, you instead ask the graph for that information:
https://github.com/lordofduct/space...blob/master/SPPathfinding/Graphs/GridGraph.cs

Same goes for the HexGraph:
https://github.com/lordofduct/space.../blob/master/SPPathfinding/Graphs/HexGraph.cs

But lets say we have a loosely setup graph. We COULD go about it by allowing the graph define relationships. Like this LinkedNodeGraph where we add nodes to it, and then tell the graph who the neighbours are:
https://github.com/lordofduct/space...aster/SPPathfinding/Graphs/LinkedNodeGraph.cs

But we don't necessarily have to do that... we COULD just let the nodes of a graph define its neighbours and have a method on it to get those neighbours. Completely subverting the need for the graph itself to set up those relationships.

Code (csharp):

1.  
2.     public interface INode<T> where T : INode<T>
3.     {
4.  
5.         IEnumerable<T> GetNeighbours();
6.         int GetNeighbours(ICollection<T> buffer);
7.     }
8.    
9.     public class NodeOfInterest : INode<NodeOfInterest>
10.     {
11.         private HashSet<NodeOfInterest> _neighbours = new HashSet<NodeOfInterest>();
12.        
13.         public bool AddNeighbour(NodeOfInterest node)
14.         {
15.             return _neighbours.Add(node);
16.         }
17.        
18.         public bool RemoveNeighbour(NodeOfInterest node)
19.         {
20.             return _neighbours.Remove(node);
21.         }
22.        
23.         public bool ContainsNeighbour(NodeOfInterest node)
24.         {
25.             return _neighbours.Contains(node);
26.         }
27.        
28.         #region INode Interface
29.        
30.         public IEnumerable<NodeOfInterest> GetNeighbours()
31.         {
32.             return _neighbours;
33.         }
34.        
35.         public int GetNeighbours(ICollection<NodeOfInterest> buffer)
36.         {
37.             foreach(var n in _neighbours) buffer.Add(n);
38.             return _neighbours.Count;
39.         }
40.        
41.         #endregion
42.     }
43.  

https://github.com/lordofduct/space...3.0/blob/master/SPPathfinding/Graphs/INode.cs

And if you want to use this loose nit of nodes, we can stick them in a basic wrapper that implement IGraph so it can be used:
https://github.com/lordofduct/space...blob/master/SPPathfinding/Graphs/NodeGraph.cs

...

Note in this entire design a node needing to know its graph is really unnecessary. Why would a node need to know what graph it's in?

That's like saying you have a List of GameObjects, and you want the GameObject to know which List its in. Why? It could be in any number of Lists!

If it's truly necessary... then yeah, tell it what collections its members of by giving it a reference to it. And remove that reference if it ever gets removed.

But if you really need it for whatever weird reason... this could work:

Code (csharp):

1.  
2.     public interface ISelfAwareNode<T> : where T : ISelfAwareNode<T>
3.     {
4.         void AddOwner(IGraph<T> owner);
5.         void RemoveOwner(IGraph<T> owner);
6.     }
7.    
8.     public class SelfAwareNode : ISelfAwareNode<SelfAwareNode>
9.     {
10.         private HashSet<IGraph<SelfAwareNode>> _owners = new HashSet<IGraph<SelfAwareNode>>();
11.        
12.         public ICollection<IGraph<SelfAwareNode>> Owners { get { return _owners; } }
13.        
14.         public void AddOwner(IGraph<SelfAwareNode> owner)
15.         {
16.             _owners.Add(owner);
17.         }
18.        
19.         public void RemoveOwner(IGraph<SelfAwareNode> owner)
20.         {
21.             _owners.Remove(owner);
22.         }
23.     }
24.    
25.     public class SomeGraph : IGraph<SelfAwareNode>
26.     {
27.        
28.         private HashSet<SelfAwareNode> _nodes = new HashSet<SelfAwareNode>();
29.        
30.         public void AddNode(SelfAwareNode node)
31.         {
32.             _nodes.Add(node);
33.             node.AddOwner(this);
34.         }
35.        
36.         public void RemoveNode(SelfAwareNode node)
37.         {
38.             if(_nodes.Remove(node))
39.             {
40.                 node.RemoveOwner(this);
41.             }
42.         }
43.  
44.  
45.         //TODO - implement IGraph as necessary
46.     }
47.  

Or any number of ways of doing it. This example allows the concept of a node being in multiple graphs.

 

Thank you all for such detailed answers! You've convinced me I need to re-think the design, and whether or not a node actually needs to know what world it's in. The concept of a "Graph" for sure needs to exist in my case, since worlds have names, types, ect, as well as needing to know what nodes are in what world so the system knows what nodes to display depending on what world the player is currently in. However, none of that requires the node to know what world it is in, but rather the world to know what nodes it contains, which is simple enough to manage.

Besides that, I'm currently storing nodes in a KeyedCollection using GUID's to identify them, so checking if a world contains a node is O(1), so if I really really needed to look up what world a node was in, I could always just search through n worlds, giving me O(n). I don't foresee the number of worlds climbing past a dozen or two, so even that shouldn't be too much a of a problem.