luanpotter/graphs

## graphs
Graphs
===================

Definition
---

A graph is a mathematical structure that represents a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices (also called nodes or points), and the links that connect some pairs of vertices are called edges (also called arcs or lines or edges). Edges might have direction or not, depending on the kind of Graph, and more generally can have a cost associated with then, or a real number representing something of the structure being modeled.

Representation
---

There are several ways to represent this structure. Two of the most common ones are:

* Adjacency list:  The Graph is a Set of Nodes, and a Node is a structure that has the object (vertex per si) and a List of adjacent Nodes.
* Adjacency matrix:  A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. Here each vertex is identified by an integer (index of the matrix) and its value must be stored externally (in a Set, for instance). Only the cost for one edge can be stored between each pair of vertices. If there is no cost nor direction, the matrix can have boolean component type.

Depending on how sparse the graph is, one or the other might be more interesting.

Traversal
---

There are also several ways to traverse a graph. We will focus on two of the most common:

* Depth-First Search (DFS):  visits the child vertices before visiting the sibling vertices; that is, it traverses the depth of any particular path before exploring its breadth. An algorithm might use a Stack to do so.
* Breadth-First Search (BFS): visits the sibling vertices before visiting the child vertices, and a queue is used in the search process.

Note that on both cases, unless the specific case of a Tree, there can be repetitions, and those must be accounted for to avoid infinite loops.

Exercise
---

Choose a language of your choice that supports functions as First Class Citizens and implement (from scratch):

* a Adjacent list cost-less graph with a DFS transversal method
* a Adjacent matrix weighted graph with a BFS transversal method

Each method should take a function to consume each node exactly once.
	Graphs
	===================

	Definition
	---

	A graph is a mathematical structure that represents a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices (also called nodes or points), and the links that connect some pairs of vertices are called edges (also called arcs or lines or edges). Edges might have direction or not, depending on the kind of Graph, and more generally can have a cost associated with then, or a real number representing something of the structure being modeled.

	Representation
	---

	There are several ways to represent this structure. Two of the most common ones are:

	* Adjacency list: The Graph is a Set of Nodes, and a Node is a structure that has the object (vertex per si) and a List of adjacent Nodes.
	* Adjacency matrix: A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. Here each vertex is identified by an integer (index of the matrix) and its value must be stored externally (in a Set, for instance). Only the cost for one edge can be stored between each pair of vertices. If there is no cost nor direction, the matrix can have boolean component type.

	Depending on how sparse the graph is, one or the other might be more interesting.

	Traversal
	---

	There are also several ways to traverse a graph. We will focus on two of the most common:

	* Depth-First Search (DFS): visits the child vertices before visiting the sibling vertices; that is, it traverses the depth of any particular path before exploring its breadth. An algorithm might use a Stack to do so.
	* Breadth-First Search (BFS): visits the sibling vertices before visiting the child vertices, and a queue is used in the search process.

	Note that on both cases, unless the specific case of a Tree, there can be repetitions, and those must be accounted for to avoid infinite loops.

	Exercise
	---

	Choose a language of your choice that supports functions as First Class Citizens and implement (from scratch):

	* a Adjacent list cost-less graph with a DFS transversal method
	* a Adjacent matrix weighted graph with a BFS transversal method

	Each method should take a function to consume each node exactly once.