a Graph is a series of vertices (nodes) connected by edges (“segments”). it\u00a0can articulate\u00a0data, perform operations and provide insights on them.\u00a0data visualization makes massive use of 2d planar graphs (you’ve probably seen many Force Directed Graphs) but a display list, a 2D polygon,\u00a0a\u00a03D mesh, a roadmap are also graphs of some sort.<\/p>\n

in its simplest form this would be a Graph:<\/p>\n

var Vertex = function( data ){ \/*store the data*\/ }\r\n\r\nvar Edge = function( v0, v1 ){\r\n    this.v0 = v0;\r\n    this.v1 = v1;\r\n}\r\n\r\nvar Graph = function( vertices, edges ){\r\n    this.vertices = vertices;\r\n    this.edges = edges;\r\n}\r\n\r\n\/\/create two vertices\r\nvar A = new Vertex( data );\r\nvar B = new Vertex( data );\r\n\r\n\/\/create an edge to bind the two vertices\r\nvar E = new Edge( A, B );\r\n\r\n\/\/create a graph\r\nvar graph = new Graph( [ A, B ], [ E ] );<\/pre>\n
the\u00a0graph contains 2 vertices A & B connected with\u00a0an edge E.<\/p>\n
now\u00a0if vertices are letters, it can represent a word, if vertices are numbers,\u00a0the graph can be a\u00a0mathematical\u00a0operation, if vertices are 2D or 3D points, the graph is a line in 2 or 3 dimensions, etc.\u00a0depending on the nature of the vertices, the edge can also represent different things, from a concatenation if vertices are letters, an operation if vertices are numbers or just maintain two references to the vertices pointers. an edge can be undirected<\/em>\u00a0meaning that the connection from E( A,B )\u00a0== E( B,\u00a0A )\u00a0or directed<\/em>\u00a0which means that\u00a0E( A,B ) != E( B,A ).\u00a0if you think of our graph\u00a0as\u00a0a roadmap, the\u00a0edge we created earlier would be a\u00a0one way street between A\u00a0and B.\u00a0this is important, especially\u00a0in geometry\u00a0; for instance it\u00a0allows to test the winding<\/em> of triangle\u00a0and eventually unify or flip it.\u00a0if we need to go back to A\u00a0from B in a directed graph, we have to add a new Edge like so :<\/p>\n
graph.edges.push( new Edge( B,A\u00a0) );<\/pre>\n
then we can go back from B\u00a0to A.
\na directed graphs can be cyclic<\/em>\u00a0which means that there are\u00a0“loops”, if you take\u00a0a triangle with 3 vertices A, B, C and 3 edges between them,\u00a0it’s possible to go from A\u00a0to\u00a0B, then from B to C and from C to A, that’s a cycle.\u00a0it makes some operations a\u00a0bit tricky as we must be careful\u00a0not to fall into a cycle while traversing the graph.<\/p>\n
otherwise, both the vertices and the edges can be updated separately\u00a0making it\u00a0a very flexible data structure, \u00a0a graph is N dimensional, N being the dimension of its\u00a0vertices (the edges always have a cardinality of 2). the edges often have a value usually called a weight <\/em>which can represent anything that\u00a0happens between the 2 vertices it binds.<\/p>\n
trees \u00a0are a special case of graphs ; trees\u00a0are directed connected acyclic<\/em> graphs ; directed means that E( A,B ) != E( B,A ), everything originates from a single vertex\u00a0(the root<\/em>) and every vertex\u00a0is\u00a0connected to a\u00a0parent or the root node (connected), an edge must not create a loop or cycle\u00a0(acyclic).<\/p>\n
I’ll leave the theory\u00a0here, it was just to give an overview, there are gazillions\u00a0of books and articles about graphs and graph theory.<\/p>\n
as I\u00a0care mostly\u00a0about graphics, let’s start with\u00a02d graphs,\u00a0usually they represent hierarchies, networks or relationships between nodes. below I create a bunch of random points, perform a Delaunay triangulation (the grey mesh) then I use the triangles’ centers to build a second set of vertices. then I compute the Minimum Spanning Tree (MST: a tree that covers all the nodes of the graph) and paint it in blue (click to reset).<\/p>\n