Primus2\Falcraft: New Data Types (unordered/ordered node)

In graph theory a vertex is a point that may or may not be connected to other points in the graph.

Vertices

I shall quote Wikipedia:

In mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graphconsists of a set of vertices and a set of arcs (ordered pairs of vertices). In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another.

From the point of view of graph theory, vertices are treated as featureless and indivisible objects, although they may have additional structure depending on the application from which the graph arises; for instance, a semantic network is a graph in which the vertices represent concepts or classes of objects.

I’ve developed a system in PHP that implements this idea of a vertex (a node as we shall call it).  These data structures are defined in Falcraft\Data\Types.

First we need a general and abstract idea as to what a vertex has associated with it.  What can we do with a vertex?  Any vertex is connected to any other vertex, and in the case of a directed graph may be incoming or outgoing.  A given vertex then will have incoming, outgoing, and mutual connections to other vertices.  In order to give us a reference so that we can deal with vertices representing different data structures, we need an abstract interface for a vertex.  I provide an interface which directly addresses incoming, outgoing, and mutual connections (github):

Alright, as we can see you can connect, disconnect, retrieve and set vertices to incoming, mutual, and outgoing.  We should bind incoming, mutual, and outgoing to member variables.  As well, we can provide an identifier for the vertex so that it is uniquely identifiable.  I accomplish this with the AbstractVertex class (github):

We set up all the methods defined in the interface, and provide basic member variables for their functionality, but we still don’t address the implementation.

Nodes

A graph can be an unlimited number of things.  For instance it could be a 3D model, where vertices are connected by lines forming planes.  It could be a hierarchical tree, where nodes are parents and children of each other.

When I created the node class, I originally strove for a hierarchical tree structure.  In this way, incoming was the ‘parents’ of the node, outgoing were the ‘children’ of the node, and mutual were the ‘siblings’ of the node.

This wasn’t a one-parent-many-children tree, no, each node can have unlimited number of parents, and children, forming quite a web.

UnorderedNode

I decided that I’d use a Restricted Set to store all the vertices an individual vertex would link to.  Each member variable would be such a set.  I set this up in the constructor of UnorderedNode (github):

This sets up the Restricted Sets containing vertex objects of various kinds.  It then connects the referenced vertices to itself as needed.  One interesting note about this is that when the nodes are connected as children, their mutual connections are automatically added as their siblings.  This is true and selective for multiple parents as well.  You can see in the incoming methods, and in the mutual connection methods.

Here we make calls to the mutual methods from the incoming methods automatically:

This calls a mutual connections and disconnection method through a piece of functional programming wizardry (mapping on a set).  The mutual functionality can be seen here:

So, in the end incoming, outgoing, and mutual connections are stored in an object as restricted sets with some gluing functionality that allows you to connect them together distinctly.

However, these are all out of order.  It doesn’t matter what vertex comes before or after any other vertex.  What happens when you want your graph (tree) to have some semblance of first and second, such as a DOM tree?  That’s where Ordered Nodes come in.

OrderedNode

But before we can address Ordered Nodes, we have to encounter the Vertex List.  A Vertex List is a list of edges that specify a list of nodes.  For review an edge is a connection between two vertices as we can see (previous and next) (github):

So, an ordered list of vertices is really an ordered list of edges.  Now, I realize that this is introducing an added layer of complexity to the process.  If I want an ordered list of nodes, then I should just store them in an ordered array by index.  Then the array keeps track of which nodes are first, second, etc.  and I can splice nodes or take them out wherever they’re needed.

I opted for this more complex approach in order to preserve the idea that nodes are connected by edges, and that they are connected to each other.  Other data structures in the library use, or will use, edges to relate themselves to vertices.  These edges can be utilized in structures outside of the vertex list.  The vertex list has a list interface, but stores s SET of edges.  The edges themselves are what determines the order of the vertices, not any particular array.

Here’s the setup for VertexList (github):

This creates really complex addition and removing logic depending on where we are in the tree.  The edges are linked as a double linked list (OrderedEdge), so we must traverse that, and then traverse the next’s and previous’s.  Here is an example of inserting a vertex before a vertex (identified):

This results in being able to have a list of vertices that are in a particular order.

Now, NOTE, that an OrderedNode is a node whose children are in order.  The OrderedNode doesn’t itself imply that it itself is in order in some other hierarchy.  You can mix UnorderedNodes and OrderedNodes in a tree as you see fit, they will work together.  An Ordered Node is finally defined using a vertex list (github):

Conclusion

Nodes are very important when it comes to trees, which are a form of graphs.  They can be connected to each other in various ways, usually denoted by the ‘direction’ of the connection.  Thus there are incoming, outgoing, and mutual connections between nodes or vertices.

These data structures allow you to define parent and child relationships using a set of vertex information and classes.  These are best suited to dealing with a tree of nodes, a common data structure encountered by optimization and artificial intelligence.

photo credit: SWband via photopin (license)

Liked it? Take a second to support kadar on Patreon!

kadar

I'm just a wunk, trying to enjoy life. I am a cofounder of http//originalpursuitssoc.com/ and I like computers, code, creativity, and friends.

You may also like...

Leave a Reply

%d bloggers like this: