Code Monkey home page Code Monkey logo

data-structures-graph-challenge's Introduction

Graphs

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.

Special kinds of Graphs

  • 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").

Why is this important?

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.
  • 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).

Release 1, Implement a Graph

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).

Interface

  • Node::new(value): Instantiate a new Node containing value
  • Node#add_edge(other_node): Add an edge between this node and other_node
  • Node#value: Return the value of this node
  • Node#nodes: Return a collection of nodes to which this node has an outgoing edge
  • Node#exists? {|node| }: Return true if the block passes for any of the nodes "downstream" from this one by following graph edges.

Example

Here's an example graph to consider:

social graph

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 follows Mike
  • Mike follows Duke
  • and Duke follows Alyssa.

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

data-structures-graph-challenge's People

Contributors

mattbaker avatar

Watchers

 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.