Digraphs, Dags, and Trees in Java

Graphs are a collection of nodes connected by edges. Programmers run into graphs fairly regularly because almost any collection of things with binary relationships can be viewed as a graph. As practitioners we need to understand both graph theory (abstract structures) and graph data structures (concrete representations).

Three common families of graphs are:

Digraphs (directed graphs): Graphs with directed edges (arcs).
Dags (directed-acyclic graphs): Digraphs that don’t contain cycles.
Trees: Dags with a single root and where non-roots have one parent. (Technically this is a rooted tree.)

This article looks at digraphs, dags, and trees from a programmer’s perspective. Where do we see them in practice? How can we recognize them? What can we do with them?

This article also includes a Java library for working with digraphs, dags, and trees. The library code is available at https://github.com/stevewedig/blog and is published to Maven for easy usage as a dependency. This is the third in a series of Java libraries I’m sharing on this blog. The first two were:

Article Outline

Continue reading →

Type Safe Heterogenous Containers in Java

As someone who has shifted from Python to Java, this article discusses two of the problems I’ve faced in Java that don’t exist in Python:

Java’s type system cannot represent containers or maps with heterogenous value types. Python dicts can hold anything.
Java’s methods lack named and optional parameters. These useful language features are provided by Python, Ruby, and C#.

As a response to these problems, this article presents a small library that makes them a bit less painful. We build on Effective Java’s item #29: consider typesafe heterogeneous containers. The library code is available at https://github.com/stevewedig/blog and is published to Maven for easy usage as a dependency. This is the second in a series of Java libraries I’m sharing on this blog (the first was Value Objects in Java & Python).

Article Outline

Continue reading →

A Software Developer’s Reading List

“An investment in knowledge always pays the best interest.” – Benjamin Franklin

Many of the best software developers have T-Shaped Skills: Deep expertise in programming and software development, and broad knowledge of diverse areas including testing, DevOps, UX design, team organization, customer interaction, and their domain areas. While there is unfortunately no substitute for experience, reading is probably the next best thing. Over the past 10 years I’ve read a lot in an effort to deepen and broaden my knowledge as a software developer. Along the way I’ve been organizing books and concepts into the reading list I share below. I have been trying to design a core curriculum for “modern” software development by asking myself:

What core concepts are required to be a world class software developer?
What is the best book for introducing and teaching each concept?

The result is a list of 16 essential software development concepts presented by 16 excellent books…

Continue reading →

Relationships Between Component Design Principles

Component Design is one of the concepts on my software developer’s reading list. There are a lot of component design principles (heuristics), so to help me keep them straight, I’ve organized them into this (imperfect) mental model for how they relate to each other:

Graph: Minimize complexity of the static component graph
- Strive for high cohesion within components, and low coupling between components
- Minimize responsibility duplication: DRY/SPOT (Don’t Repeat Yourself/Single Point of Truth)
Graph Nodes: Minimize complexity within components (nodes)
- Responsibility: Have a single responsibility by separating: concerns, command/query, option/operand, creation/usage, policy/mechanism, domain model/persistence, domain model/distribution, and facets (who, what, when, where, why, how)
- Inputs / Outputs: Generally try to minimize the number of inputs/outputs. Similar concepts include imports/exports, dependencies/clients, fan-in/fan-out, efferent coupling/afferent coupling
- Implementation: Design code to communicate intent (see the Code Design concept on the reading list)
Graph Arcs: Minimize complexity in dependencies & relationships between components (nodes)
- Interface Size
  - Width: thick vs. thin, interface segregation
  - Depth: Suggestion of Demeter
  - Intimacy: State mutation, side effects, lack of abstraction, lack of encapsulation, lack of Liskov substitutability
- Dependency Binding Mechanism
  - Dependency Inversion is Good: Statically depend on interfaces, not implementations (Dependency Inversion Principle). Implementations are provided at runtime.
  - Dependency Pyramid is Bad: Statically import implementations, so implementations cannot be changed at runtime.
  - Relationship to Testability: Dependencies must be provided at runtime before you’ll be able to use Test Doubles (for more details, see the Test-Driven Development notes in the reading list).

If I had to summarize component design into one sentence, I might say something like: Manage complexity by using interfaces (information hiding and abstraction) to decouple the components in your system.

A Few Python Tricks

(Edit: This is a fairly old library. If you are interested in @once, frozendict, and Opt, these are included as part of the newer value objects library.)

A while ago I gave a talk to the LA Python user group about a few Python tricks we use at my company Lingospot. Three years later we’re still using all of these techniques. There isn’t any particular theme, it’s just a mix of tricks that are simple and widely applicable. You can find the slides and sample code here.

If I recall, the talk was generally well received. Interestingly some audience members didn’t find Option Types to be “Pythonic”, which very well may be true. Nowadays I prefer to use Java for reasons I describe in Why & How I Write Java. For Option Types in Java I use Google Guava’s Optional. I certainly don’t miss the errors caused by null/None.