//abstractBridges()What’s in a DAG?
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!)
Once upon a time, there was a (unsolvable) riddle
Then, came Euler
Simplification and Abstraction
prettyFormat = x=>x;
function undirectedGraphOptions() {
var options = JSON.parse(JSON.stringify(defaultGraphOptions));
options.style[1].style["target-arrow-shape"] = "line";
return options;
}
function weightedGraphOptions() {
var options = JSON.parse(JSON.stringify(defaultGraphOptions));
options.style[1].style.label = "data(weight)"
return options;
}
function dijkstraAlgo(graph, id) {
return graph.elements().dijkstra('#' + id, function(edge){
return edge.data('weight');
});
}
function pathToArrows(path) {
return path
.filter((x,i) => i %2 === 0)
.map(x => x.id()).join(" -> ");
}
function abstractBridges() {
window.bridges = cytoscape({
...undirectedGraphOptions(),
container: document.getElementById('bridges'),
elements: [
{ data: { id: 'a' }},
{ data: { id: 'b' }},
{ data: { id: 'c' }},
{ data: { id: 'd' }},
{ data: { source: 'a', target: 'b' }},
{ data: { source: 'a', target: 'c' }},
{ data: { source: 'a', target: 'd' }},
{ data: { source: 'b', target: 'c' }},
{ data: { source: 'b', target: 'c' }},
{ data: { source: 'c', target: 'd' }},
{ data: { source: 'c', target: 'd' }}]});
}
How many times this door was opened?
Let’s give it a name
bridges.nodes().map(x=> `${x.id()}: ${x.degree()}`).join("\n")Graph Theory was born: Happy Birthday!
Basic Graph concepts
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' }
];Adjacency list
adjacencyList = {
'a': ['b', 'c', 'd'],
'b': ['c', 'c'],
'c': ['d','d'],
'd': []
};Adjacency matrix
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
…
Storing a graph in a SQL database
Good Luck!