## Agenda

• The birth of Graph Theory

• How to make money from Graph Theory

## Who am I?

• A Full Stack Expert

• A pragmatic theorist

• A freak of interactivity

• A partner in a software consulting company (We are hiring!)

## Simplification and Abstraction

``//abstractBridges()``

## Let’s give it a name

``bridges.nodes().map(x=> `\${x.id()}: \${x.degree()}`).join("\n")``

• Vertices

• Edges

Properties:

• Degree

• Cycle

• Neighboors

• Clusters

## Representing a graph

List of nodes and edges

``````listNodesAndEdges = [
{ id: 'a' },
{ id: 'b' },
{ id: 'c' },
{ id: 'd' },
{ source: 'a', target: 'b' },
{ source: 'a', target: 'c' },
{ source: 'a', target: 'd' },
{ source: 'b', target: 'c' },
{ source: 'b', target: 'c' },
{ source: 'c', target: 'd' },
{ source: 'c', target: 'd' }
];``````

``````adjacencyList = {
'a': ['b', 'c', 'd'],
'b': ['c', 'c'],
'c': ['d','d'],
'd': []
};``````

``````adjacencyMatrix = [
[0, 1, 1, 1],
[1, 0, 1, 0]
[1, 1, 0, 1],
[1, 0, 1, 0]
];``````

## Type of graphs

• Weighted graph

• Direct Acyclic Graph (DAG)

## Waze

Djikstra algorithm

``````var map = cytoscape({
...weightedGraphOptions(),
container: document.getElementById('map'),
elements: [
{ data: { id: 'Tel-Aviv' }},
{ data: { id: 'Jerusalem' }},
{ data: { id: 'Haifa' }},
{ data: { id: 'Eilat' }},
{ data: { source: 'Tel-Aviv', target: 'Jerusalem', weight: 5 }},
{ data: { source: 'Jerusalem', target: 'Haifa', weight: 6 }},
{ data: { source: 'Haifa', target: 'Eilat', weight: 3 }},
{ data: { source: 'Tel-Aviv', target: 'Eilat', weight: 30 }}]});``````

``````var shortestPath = dijkstraAlgo(map,'Tel-Aviv')
.pathTo( map.\$('#Eilat') )
var shortestDistance = dijkstraAlgo(map, 'Tel-Aviv')
.distanceTo( map.\$('#Eilat') );
console.log(`shortest distance: \${shortestDistance}`);
console.log(`shortest path: \${pathToArrows(shortestPath)}`);``````

## Page Rank

``````var pages = cytoscape({
...defaultGraphOptions,
container: document.getElementById('pages'),
elements: [
{ data: { id: 'wikipedia.org' }},
{ data: { id: 'cnn.com' }},
{ data: { id: 'stackoverflow.com' }},
{ data: { id: 'meetup.com' }},
{ data: { id: 'myblog.com' }},
{ data: { source: 'meetup.com', target: 'wikipedia.org'}},
{ data: { source: 'cnn.com', target: 'wikipedia.org'}},
{ data: { source: 'stackoverflow.com', target: 'wikipedia.org'}},
{ data: { source: 'wikipedia.org', target: 'myblog.com'}},
{ data: { source: 'stackoverflow.com' , target: 'cnn.com' }},
{ data: { source: 'meetup.com', target: 'cnn.com' }}]});``````

``````var pr = pages.elements().pageRank();
pages.nodes().map(node => `\${node.id()}: \${pr.rank(node)}`).join("\n")``````

## What else?

• Social networks (Clustering, Affinity)

• Dependency resolution (toplogcal sort)

• Online Store (Recommendation)

• Fraud detection

• …​

Good Luck!