![\"weighted-digraph.png\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_256.png?resize=155%2C182\")
<\/p>\n<\/p>\n
The next interesting variant on graphs is directed graphs<\/em>, or digraphs<\/em> for <\/p>\n A lot of things change when you’re using digraphs instead of simple graphs. For example, the shortest Digraphs come up in many places – basically anywhere where direction matters. Think, for example, of For a less obvious example of this, we can look at something very close to home for me. There’s This is important, because there are often many steps to compiling a software system. For example, a program that I wrote to generate some fractals consists of:<\/p>\n So, to generate an image, I write a GDF. Then the python program runs on the GDF, generating Suppose I write a GDF file which generates a nice picture of the mandelbrot set. Then I run Then I want to use a different GDF file – this time, I want to generate a Julia fractal. There’s no I look at my Julia image, and it’s no good – it’s very pixelated. So I add some kind of That’s what make is for. It figures out what needs to be redone, based an what changed. The way \tTo build the executable for my fractal generator So, now, suppose I edit “foo.gdf”. That means I need to rebuild everything on any path If I updated the version of my C++ library, then I would just need to recompile and link “foo.cc”.<\/p>\n","protected":false},"excerpt":{"rendered":" The next interesting variant on graphs is directed graphs, or digraphs for short. A digraph is a graph where each edge distinguished between its source and its target – so an edge is from one node, and to another node. Unlike a simple graph, where if A is adjacent to B, then you can follow […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[25],"tags":[],"class_list":["post-498","post","type-post","status-publish","format-standard","hentry","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-82","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/498","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=498"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/498\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=498"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=498"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=498"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nshort. A digraph is a graph where each edge distinguished between its source and its target – so an edge is from<\/em> one node, and to<\/em> another node. Unlike a simple graph, where if A is adjacent to B, then you can follow the edge either from A to B, or from B to A, in a directed graph, A to B and B to A are different edges.<\/p>\n
\npath: the shortest path from A to B is different<\/em> than the shortest path from B to A. Look at the
\nfollowing example of a weighted digraph. The shortest path from A to B is 2 (A→B); the shortest path
\nfrom B to A is 9 (B→D→C→E→A).<\/p>\n
\nNew York City streets. Every intersection is a vertex; streets between intersections are edges. How do you
\nget from 96th street and Madison to 18th street and 4th ave? Since most of the streets in Manhattan are
\none-way, you don’t want to try to do this with an undirected graph – you’ll get directions that you can’t
\nfollow. You need to know the directions of the edges. (An important point, which this illustrates, is
\nthat in a digraph, you can have both<\/em> an edge from A to B and<\/em> an edge from B to A.
\nTwo way streets get modeled as two edges – one in each direction.)<\/p>\n
\na very famous software tool, first implemented at Bell Labs, called “make”. The purpose of make
\nis to provide an automated way of compiling software, which ensures that no more work is done compiling than necessary.<\/p>\n\n
\nimage, but which know how to generate “pdf” image files – that is used by the C++ program to
\ngenerate the image.<\/li>\n
\nand by the PDF library. I don’t have to compile this – but it’s a component that gets
\nincluded to turn anything into an executable.<\/li>\n<\/ol>\n
\na C++ program. Then the C++ program is compiled. The library is compiled; and then the compiled
\nC++ program and the two libraries are linked and run, to generate the image.<\/p>\n
\nmake to compile it. It generates C++, compiles the C++ and the library, and runs the program
\nto generate the image.<\/p>\n
\nreason to recompile the C++ library. I already did that when I was generating a mandelbrot, and
\nthe library hasn’t changed. I can just re-use the library from last time. <\/p>\n
\nscaling factor to the library. But I’m not changing my gdf file, and I’m not changing the python script. I shouldn’t need to rerun the python script on the unchanged GDF; and that means that
\nthe generated C++ program can’t change either. I need to recompile the library, and I need to
\nrelink the compiled C++.<\/p>\n
\nthat it does that is by using a dependency graph<\/em>. A dependency graph is a digraph which
\nhas a vertex for every input to, and every output from, any step of a build process. There is an edge
\nfrom a vertex A to a vertex B if changing A means that B needs to be recompiled. For example, below is
\nthe digraph for the scenario I described above. In it, I’ve made C++ files red\/orange, libraries and executables green, python source blue, and my gdf file purple. Source files are rounded boxes, libraries are ovals, object files are diamonds, and executables are rectangles.<\/p>\n![\"depgraph.png\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_257.png?resize=454%2C234\")
<\/p>\n
\n(“foo.exe”), I need to have the generated source file “foo.cc”, the pdf library (“libpdf.a”), and
\nthe C++ standard library (“libstdc++.a”); to build “foo.cc”, I need
\nboth an input file, “foo.gdf”, and the python script “gen.py”, and so on. <\/p>\n
\nfrom “foo.gdf” up to “foo.exe”: so I need to run “gen.py” to build “foo.cc”; then I need to compile
\n“foo.cc”, and link it against the two libraries to build “foo.exe”.<\/p>\n