Fork me on GitHub
#off-topic
<
2018-10-20
>
a-luz15:10:00

Hey guys, after trying out cider for a while now, I am trying to figure something out. Currently, when i do cider-jack-in, cider initiates well and all, but if I want test a namespace out, I need to manually evaluate the namespace so it can be called inside cider. Is this the usual workflow? I though when I loaded a project I would have access to all the namespaces in the project by default

eccentric J20:10:21

Is there a defining characteristic that makes a hash-map a graph?

emccue21:10:33

well, any unweighted graph can be simplified to a map of a vertex to the list of vertices reachable from that vertex

emccue21:10:34

thats usually the representation i worked with for my algorithms classes

eccentric J22:10:16

I gotta look up some of those terms but based on my research so far would it be fair to say a hash-map is a graph when it models a relationship over structure?

andy.fingerhut22:10:48

A hash-map can certainly be used to represent a graph. It can also be used to represent things that most people do not think of as a graph at all.

andy.fingerhut22:10:06

From one perspective, you could say a hash-map is always like a graph, e.g. the keys are nodes in the graph, and each has a directed edge to the node representing its value. Values can be duplicated, so some value nodes could have multiple edges into them.

andy.fingerhut22:10:28

That is a restricted kind of graph, so that perspective is not useful for representing arbitrary graphs with cycles, for example.

eccentric J22:10:28

Oooh that is starting to make sense. Thanks!

andy.fingerhut22:10:52

A way to represent an arbitrary graph with directed edges using a hash-map would be to pick a value to represent each node, and use those as the keys of the map. The corresponding value associated with a key would be a set or list of other nodes that it has directed edges towards.

eccentric J22:10:08

Something like that right?

andy.fingerhut22:10:58

Then there are more general techniques that enable additional capabilities. For example, that representation doesn't make it easy to associate value with edges (e.g. maybe you want an edge from city A to city B to have a distance in miles associated with it).

andy.fingerhut22:10:25

One more general approach is to also pick values to represent each edge. One hash-map could map node values to lists of edge values.

andy.fingerhut22:10:57

A separate hash-map would map edge values to a map with properties of the edge, e.g. `{:from <from-node-value> :to <to-node-value> :distance <number}`

andy.fingerhut22:10:22

I don't know if such a generalization is overloading you with different ways of doing things, though.

eccentric J22:10:40

It is pretty clear and it was more general curiosity. After a few years of not being satisfied with our application architecture at work I found inspiration from the component Clojure library and am roughing out an interface to create layers that make up our apps and each layer will at least have a name and a list of dependencies.

eccentric J22:10:55

But then I realized that I don’t know why the dependencies make up a graph, I only know that the component library in clojure refers to it as a graph thus began my curiosity for what makes data a graph.

andy.fingerhut22:10:07

The simplest kind of mathematical structure called a "graph" that I know of is a set of nodes, and a set of edges, where each edge has a from node and a to node. There are also undirected variants where edges don't have a direction.

andy.fingerhut22:10:49

There are many variations of how to represent that mathematical idea in data structures.

eccentric J22:10:01

I’m starting to see that 🙂

eccentric J22:10:15

Oooh I just realized that the map of edge values with properties is probably how GPS route finders work right? They may have a network of roads with distance, speed limit, and current traffic values and the GPS would ideally find the route with the shortest distance, highest speed limit, and least amount of traffic.

andy.fingerhut22:10:54

yes, the idea of a graph has many applications, including route finders.

andy.fingerhut22:10:29

There are lots of books and research articles (thousands, I am sure) on using graphs to represent different kinds of problems, and algorithms for solving those problems.

eccentric J22:10:04

I do have an algorithms book I haven’t dived into yet but I may need to find one more targeted on that subject.

andy.fingerhut22:10:21

There are a few Computer Science textbooks that give good overviews, if you are curious to dig into algorithms and their efficiency, but there are also open source implementations of many of those algorithms if you just want to use them rather than know how they work.

eccentric J22:10:01

Hmm would it be better to know how a few of them work or know how to use many?

andy.fingerhut22:10:10

Mark Engelberg has published a Clojure library called `ubergraph` that implements some of those algorithms.

andy.fingerhut23:10:27

It depends upon what you want to learn, but I think it is worth knowing at least a few of the fundamental graph algorithms that have efficient run times (e.g. linear time in the size of the graph, or quadratic), and which take much longer to solve, but have known algorithms, in case you run across a problem that could be solved using that algorithm.

eccentric J23:10:00

That’s a good point.

andy.fingerhut23:10:02

e.g shortest path algorithms from node A to node B are widely known and have easily found open source implementations. Finding 'connected components', spanning trees, minimum size 'cut sets', i.e. the smallest set of edges you can remove from a graph that make it impossible to get from node A to node B after they are removed, etc.

andy.fingerhut23:10:11

If your goal is to solve other problems, knowing that there might be an already-implemented algorithm that can solve it for you, if you represent it as that kind of problem on a graph, can help you get to a solution for that problem faster than if you created it on your own from scratch.

eccentric J23:10:35

Right. In my day job I mostly do frontend so probably don’t need that in the day to day. But I do have to learn it to make any progress on my side projects which fortunately I can take my time on.

andy.fingerhut23:10:52

Even knowing just enough of the graph lingo like nodes/vertices and edges/arcs, and paths, cycles, etc. can help you ask others who know more about such algorithms whether an efficient algorithm exists for solving a problem.

eccentric J23:10:42

Very good point!

emccue23:10:50

oops meant to do the message in the same thing, whatever

emccue23:10:49

anyways I'm a college student so I just got out of an Algorithms class last semester so if you need any rote book knowledge feel free to ask

emccue23:10:07

Its all still fresh in my head

emccue23:10:02

(8 weeks of graph junk basically)