Graph data structures model many of the things you interact with day-to-day. They can model social networks, tiles in a maze, dependencies between components of a system, even trees.
A Graph is made up of a set of Nodes. Links between Nodes are known as edges. Nodes can have many edges. There is no concept of hierarchy in a graph, it's simply a data structure that allows us to maintain a web of interconnected things.
A Node
in the context of a Graph is similar to a Node in a LinkedList, but a graph may have multiple outgoing edges as opposed to the single outgoing edge that a node has in a Linked List.
In addition to edges, Nodes typically contain a value attached to that node.
The Wikipedia entry on Graphs includes more vocabulary along with definitions.
- Some graphs have edges with direction. In other words, an edge from A to B does not imply an edge from B to A. These are known as directed graphs. The graph in the upper right corner is a directed graph (note the arrows indicating direction).
- Some directed graphs have no path from a node back to itself. These graphs are known as acyclic graphs. The graph in the upper right corner is not acyclic because it's possible to follow a series of directed edges back to the first node (resulting in a "graph cycle").
We model many things as graphs in computing. A few examples:
- Your social network
- Each person is a node and friendships are an edge. The value might be a kind of "Person" object.
- Spreadsheets
- Each cell is a node, dependencies between cells (e.g.
=C2+B4
) are edges.
- Each cell is a node, dependencies between cells (e.g.
- Topologies
- A network of interdependent services is a graph, with edges representing dependencies between services
- Trees
- Trees could be thought of as graphs with more restrictions
There are also a slew of common algorithms for searching and working with graphs. You may have heard of Depth-First Search, Breadth-First Search, or Topological Sorting (handy for spreadsheets).
Create and test a Node
class. This Graph should be a directed graph, so your Node's edges will only go one direction (though there's nothing stopping you from having two edges on two nodes that point to each other).
Node::new(value)
: Instantiate a new Node containingvalue
Node#add_edge(other_node)
: Add an edge between this node andother_node
Node#value
: Return the value of this nodeNode#nodes
: Return a collection of nodes to which this node has an outgoing edgeNode#exists? {|node| }
: Return true if the block passes for any of the nodes "downstream" from this one by following graph edges.
Here's an example graph to consider:
In this graph we can see users that "follow" each other on a social network. It's a directed graph, because I can follow someone, but they might not follow me back.
In this graph, given a node named matt
, matt.exists?{|node| node.value == 'Alyssa'}
should return true because:
Matt
followsMike
Mike
followsDuke
- and
Duke
followsAlyssa.
On the other hand, matt.exists?{|node| node.value == 'Jones'}
will return false because there is no chain of followers from Matt to Jones.
Try tests on this example graph. Also come up with your own interesting test cases. For example, does #exists?
work on a cyclic graph