DataStructures-and-Algorithms

Implementation: Graphs

Specifications

• Read all of these instructions carefully.
• Name things exactly as described.
• Do all your work in a your data-structures-and-algorithms public repository.
• Create a new branch in your repo named as noted below.
• Follow the language-specific instructions for the challenge type listed below.
• Update the “Table of Contents” - in the README at the root of the repository - with a link to this challenge’s README file.

Challenge Setup & Execution

Branch Name: graph

Challenge Type: New Implementation

Features

Implement your own Graph. The graph should be represented as an adjacency list, and should include the following methods:

• add node
  • Arguments: value
  • Returns: The added node
  • Add a node to the graph
• add edge
  • Arguments: 2 nodes to be connected by the edge, weight (optional)
  • Returns: nothing
  • Adds a new edge between two nodes in the graph
  • If specified, assign a weight to the edge
  • Both nodes should already be in the Graph
• get nodes
  • Arguments: none
  • Returns all of the nodes in the graph as a collection (set, list, or similar)
  • Empty collection returned if there are no nodes
• get neighbors
  • Arguments: node
  • Returns a collection of edges connected to the given node
    • Include the weight of the connection in the returned collection
  • Empty collection returned if there are no nodes
• size
  • Arguments: none
  • Returns the total number of nodes in the graph
  • 0 if there are none

Structure and Testing

Utilize the Single-responsibility principle: any methods you write should be clean, reusable, abstract component parts to the whole challenge. You will be given feedback and marked down if you attempt to define a large, complex algorithm in one function definition.

Be sure to follow your language/frameworks standard naming conventions (e.g. C# uses PascalCasing for all method and class names).

Any exceptions or errors that come from your code should be contextual, descriptive, capture-able errors. For example, rather than a default error thrown by your language, your code should raise/throw a custom error that describes what went wrong in calling the methods you wrote for this lab.

Write tests to prove the following functionality:

1. Node can be successfully added to the graph
2. An edge can be successfully added to the graph
3. A collection of all nodes can be properly retrieved from the graph
4. All appropriate neighbors can be retrieved from the graph
5. Neighbors are returned with the weight between nodes included
6. The proper size is returned, representing the number of nodes in the graph
7. A graph with only one node and edge can be properly returned

Ensure your tests are passing before you submit your solution.

Documentation: Your README.md

# Graphs
<!-- Short summary or background information -->

## Challenge
<!-- Description of the challenge -->

## Approach & Efficiency
<!-- What approach did you take? Why? What is the Big O space/time for this approach? -->

## API
<!-- Description of each method publicly available in your Graph -->

Submission Instructions

1. Create a pull request from your branch to your main branch
2. In your open pull request, leave as a comment a checklist of the specifications and tasks above, with the actual steps that you completed checked off
3. Submitting your completed work:
   1. Copy the link to your open pull request and paste it into the corresponding assignment
   2. Leave a description of how long this assignment took you in the comments box
   3. Add any additional comments you like about your process or any difficulties you may have had with the assignment
4. Merge your branch into main, and delete your branch (don’t worry, the PR link will still work)