Specific thoughts on what deserves more commenting?
I tend to prefer explicit type annotations and unit tests (later) over comments except when I feel like there's something non-intuitive that's not at all obvious from the code. Comments are also critical for future-safety against "fixes" that "look right" but will actually break the code.
I tend to have a "60-second rule". If it took 60 seconds for me to figure this out, then I should comment. For example, I commented the need for a curried function signature in Utils.mergeMaps because it wasn't at all obvious, and I kept getting type errors till I got it right.
Personally, I think the worst thing about what I have right now is that it really deserves to be split into more than one file, but I'm delaying the build system question (I dislike Maven, SBT seems neat has a bad reputation) for a little white.
I would ignore advice on commenting. Things should be clear, not commented. Docstrings are nice if you are going to generate some documentation for end users; googling for "string isempty java" is easier than opening up java/lang/String.java and searching for "empty" in your text editor. (But both techniques have their advantages and disadvantages.)
Tests are a great way to show what your library can do. I recommend adding those before you worry about documentation. (How do you know your code, as posted, works?)
One thing I have to decide on this project is whether I'm going to follow the convention (which I don't like) of putting "test/" in a separate directory from "main/". I dislike it because I think unit tests should be included inline if short and relevant to the purpose of the function.
Generally, my testing practice is to REPL-test and then include the tests in code for posterity. It makes the testing process more playful to start in REPL testing. I know it's the opposite of TDD but it works for me.
Michael, could you explain why you are using Scala over Clojure? I know you've got experience with both, but Clojure has always seemed more appealing to me.
As for commenting - code that is meant to be a library should have a clearly documented API. Perhaps not from the beginning, but as the API gets stable, the JavaDoc comments for generated documentation should be there.
Though at the current state, tests and "getting started" examples (create a graph, list all nodes, determine if there is an edge from A to B, ...) would be sufficient (and would really help).
And since you're writing a graph library, there definitely should be a detailed commentary on the implementation of the graph (e.g. representation of the graph structure, memory complexity of the representation, and time complexity of common operations). Once you start working with larger graphs, using the correct representation and algorithms for your task makes a huge difference and it is something that must not be hidden from the users.
