DEV Community: DB

graph: A library for creating generic graph data structures and modifying, analyzing, and visualizing them.

DB — Wed, 14 Sep 2022 17:24:44 +0000

graph is a Go library for creating generic graph data structures and modifying, analyzing, and visualizing them.

Features

Generic vertices of any type, such as int or City.
Graph traits with corresponding validations, such as cycle checks in acyclic graphs.
Algorithms for finding paths or components, such as shortest paths or strongly connected components.
Algorithms for transformations and representations, such as transitive reduction or topological order.
Algorithms for non-recursive graph traversal, such as DFS or BFS.
Edges with optional metadata, such as weights or custom attributes.
Visualization of graphs using the DOT language and Graphviz.
Extensive tests with ~90% coverage, and zero dependencies.

Status: Because graph is in version 0, the public API shouldn't be considered stable.

Getting started

go get github.com/dominikbraun/graph

Quick examples

Create a graph of integers

g := graph.New(graph.IntHash)

g.AddVertex(1)
g.AddVertex(2)
g.AddVertex(3)
g.AddVertex(4)
g.AddVertex(5)

_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 4)
_ = g.AddEdge(2, 3)
_ = g.AddEdge(2, 4)
_ = g.AddEdge(2, 5)
_ = g.AddEdge(3, 5)

Create a directed acyclic graph of integers

g := graph.New(graph.IntHash, graph.Directed(), graph.Acyclic())

g.AddVertex(1)
g.AddVertex(2)
g.AddVertex(3)
g.AddVertex(4)

_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 3)
_ = g.AddEdge(2, 3)
_ = g.AddEdge(2, 4)
_ = g.AddEdge(3, 4)

Create a graph of a custom type

To understand this example in detail, see the concept of hashes.

type City struct {
    Name string
}

cityHash := func(c City) string {
    return c.Name
}

g := graph.New(cityHash)

g.AddVertex(london)

Create a weighted graph

g := graph.New(cityHash, graph.Weighted())

g.AddVertex(london)
g.AddVertex(munich)
g.AddVertex(paris)
g.AddVertex(madrid)

_ = g.AddEdge("london", "munich", graph.EdgeWeight(3))
_ = g.AddEdge("london", "paris", graph.EdgeWeight(2))
_ = g.AddEdge("london", "madrid", graph.EdgeWeight(5))
_ = g.AddEdge("munich", "madrid", graph.EdgeWeight(6))
_ = g.AddEdge("munich", "paris", graph.EdgeWeight(2))
_ = g.AddEdge("paris", "madrid", graph.EdgeWeight(4))

Perform a Depth-First Search

This example traverses and prints all vertices in the graph in DFS order.

g := graph.New(graph.IntHash, graph.Directed())

g.AddVertex(1)
g.AddVertex(2)
g.AddVertex(3)
g.AddVertex(4)

_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 3)
_ = g.AddEdge(3, 4)

_ = graph.DFS(g, 1, func(value int) bool {
    fmt.Println(value)
    return false
})

1 3 4 2

Find strongly connected components

g := graph.New(graph.IntHash)

// Add vertices and edges ...

scc, _ := graph.StronglyConnectedComponents(g)

fmt.Println(scc)

[[1 2 5] [3 4 8] [6 7]]

Find the shortest path

g := graph.New(graph.StringHash, graph.Weighted())

// Add vertices and weighted edges ...

path, _ := graph.ShortestPath(g, "A", "B")

fmt.Println(path)

[A C E B]

Perform a topological sort

g := graph.New(graph.IntHash, graph.Directed(), graph.Acyclic())

// Add vertices and weighted edges ...

order, _ := graph.TopologicalSort(g)

fmt.Println(order)

[1 2 3 4 5]

Cycle checks for acyclic graphs

g := graph.New(graph.IntHash, graph.Acyclic())

g.AddVertex(1)
g.AddVertex(2)
g.AddVertex(3)

_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 3)

if err := g.AddEdge(2, 3); err != nil {
    panic(err)
}

panic: an edge between 2 and 3 would introduce a cycle

Visualize a graph using Graphviz

The following example will generate a DOT description for g and write it into the given file.

g := graph.New(graph.IntHash, graph.Directed())

g.AddVertex(1)
g.AddVertex(2)
g.AddVertex(3)

_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 3)

file, _ := os.Create("./mygraph.gv")
_ = draw.DOT(g, file)

To generate an SVG from the created file using Graphviz, use a command such as the following:

dot -Tsvg -O mygraph.gv

Setting edge attributes

Edges may have one or more attributes which can be used to store metadata. Attributes will be taken
into account when visualizing a graph. For example, this edge
will be rendered in red color:

_ = g.AddEdge(1, 2, graph.EdgeAttribute("color", "red"))

To get an overview of all supported attributes, take a look at the
DOT documentation.

Concepts

Hashes

A graph consists of nodes (or vertices) of type T, which are identified by a hash value of type
K. The hash value is obtained using the hashing function passed to graph.New.

Primitive types

For primitive types such as string or int, you may use a predefined hashing function such as
graph.IntHash – a function that takes an integer and uses it as a hash value at the same time:

g := graph.New(graph.IntHash)

This also means that only one vertex with a value like 5 can exist in the graph if
graph.IntHash used.

Custom types

For storing custom data types, you need to provide your own hashing function. This example function
takes a City and returns the city name as an unique hash value:

cityHash := func(c City) string {
    return c.Name
}

Creating a graph using this hashing function will yield a graph with vertices of type City
identified by hash values of type string.

g := graph.New(cityHash)

Traits

The behavior of a graph, for example when adding or retrieving edges, depends on its traits. You
can set the graph's traits using the functional options provided by this library:

g := graph.New(graph.IntHash, graph.Directed(), graph.Weighted())

Documentation

The full documentation is available at pkg.go.dev.

Check out graph on GitHub: dominikbraun/graph

timetrace: New features of the time tracking CLI

DB — Thu, 17 Jun 2021 09:45:52 +0000

Since its initial release in May, a lot of powerful features have been added to timetrace, a simple time tracking CLI. I'm going to introduce some of the features present in timetrace v0.10.0 in this article.

Installing timetrace

If you're on macOS, you can simply use Homebrew:

brew tap dominikbraun/timetrace
brew install timetrace

timetrace is available for all major platforms. Check out the installation instructions and pick yours.

Basic usage: If you're new to timetrace, Tracking my working time using timetrace might be a good read. There also are detailed examples and the CLI reference.

🔥 Project modules

With version 0.7.0, support for project modules has been added to timetrace. Project modules are sub-projects of an existing project.

For example, we could create a project called make-coffee:

timetrace create project make-coffee

Project modules are the exact same thing as projects, expect that they can be associated with a parent project. This association is marked by an @. For example, grind-beans@make-coffee is a module of the project make-coffee. Therefore, creating this project is fairly simple:

timetrace create project grind-beans@make-coffee

timetrace recognizes those modules. For example, when listing all records for a given project, its modules will be included:

timetrace list records today -p make-coffee
+-----+-------------------------+---------+-------+------------+
|  #  |   PROJECT               |  START  |  END  |  BILLABLE  |
+-----+-------------------------+---------+-------+------------+
|   1 | make-coffee             | 08:28   | 08:35 | no         |
|   2 | grind-beans@make-coffee | 08:25   | 08:27 | no         |
+-----+-------------------------+---------+-------+------------+

To view all projects along with their modules, just run timetrace list projects.

🔥 Revert changes to projects and records

timetrace v0.8.0 introduced the --revert flag for the edit project, delete project, edit record and delete record commands. It allows to restore the resource prior to its modification.

For example, let's delete the make-coffee project:

timetrace delete project make-coffee

Oops! That shouldn't have happened. Let's restore the state of the project prior to the delete command:

timetrace delete project make-coffee --revert

The --revert flag reverts the change introduced by the previous command, thus our project exists again.

Edited or deleted records can be restored the exact same way. The following command will edit the newest record and lengthen it by 1 hour:

timetrace edit record latest --plus 1h

This will increase the end time of the records by 1 hour.

Hint: To get a list of the available records of today and the record key for editing them, use timetrace list records today.

If this was a mistake, reverting the previous command is very simple:

timetrace edit record latest --revert

The end time of the record will now be the same as before.

🔥 An enhanced tracking status

The timetrace status command got some love with timetrace v0.9.0 and v0.10.0, addressing some requested features.

First of all, status now not only calculates the overall work time of the current day but also the overall break time. How long have you been taking breaks today? Take a look at the right column!

Print your custom status

It is also possible to print the tracking status in your custom format using the --format flag. There is a pre-defined set of variables. For example, {project} will be replaced with the name of the current project.

To print an output like Currently working on make-coffee - Worked today: 2h, issue the following command:

timetrace status --format "Currently working on {project} - Worked today: {trackedTimeToday}"

Another new option is --output. It allows the users to specify an output format. The default is the table shown above, but it is also possible to output the same data as JSON:

timetrace status --output json

This will produce the following output:

{
        "project": "web-store",
        "trackedTimeCurrent": "1h 45min",
        "trackedTimeToday": "7h 30min",
        "breakTimeToday": "0h 30min"
}

Note that the JSON keys are the same as the formatting variables used by --format.

This also enables a simple Starship integration.

Now you're good to give those features a try, bookmark the project or provide some feedback!

⭐ dominikbraun/timetrace ⭐

Tracking my working time using timetrace

DB — Tue, 18 May 2021 13:00:00 +0000

In my new job, I'm not required to track my working time anymore. This feels great, but since I'm getting paid for working 40 hours a week, I decided to track it myself and built a simple and friendly CLI tool: timetrace.

Installing timetrace

timetrace is available for many platforms. Since I'm on macOS, I'll simply use Homebrew:

brew tap dominikbraun/timetrace
brew install timetrace

For other installation methods, check out the installation instructions.

Creating a project

timetrace uses projects to store what you are currently working on. For example, creating a project called make-coffee is pretty simple:

timetrace create project make-coffee

Tracking time

To start tracking time for a project, run the start command and provide the project name:

timetrace start make-coffee

You'll see the following output:

✔️ Started tracking time

Current tracking status

What project are you currently working on? And how long have you been working on it? The status command answers such questions.

timetrace status
+-----------------+--------------------+--------------+
| CURRENT PROJECT | WORKED SINCE START | WORKED TODAY |
+-----------------+--------------------+--------------+
| make-coffee     | 0h 5min            | 4h 20min     |
+-----------------+--------------------+--------------+

Stop tracking time

Once you've finished your work, stop tracking time.

timetrace stop

List today's records

Tracked time is stored as a record. To list all records, use the list records command and provide the current date. On our example, this is only one record:

timetrace list records 2021-05-18
+---+-------------+-------+-----+----------+
| # |   PROJECT   | START | END | BILLABLE |
+---+-------------+-------+-----+----------+
| 1 | make-coffee | 14:44 | --- | no       |
+---+-------------+-------+-----+----------+

This overview is useful for running other commands like get record, edit record or delete record, since you'll have to provide the record's start time for them.

To get a complete list of available commands, run timetrace -h or check out the command reference

Planned features

This was a quick usage example including the most important commands I'm using every day. But there are more advanced features planned. Some of them are:

Lengthen and shorten existing records
Generating reports of tracked time
Reverting changes done with edit or delete
Project modules for managing sub-modules

If you'd like to contribute or have some suggestions, check out timetrace's open issues!

How to create your website using verless

DB — Tue, 13 Oct 2020 20:48:27 +0000

Since I planned to create a new personal website for myself and didn't want to stick with PHP again, I created a simple and lightweight Static Site Generator called verless. In this article, I'll demonstrate how to rapidly create static websites using verless.

Of course, you need to install verless first or run it with Docker.

Scaffolding a new project

First of all, we're going to initialize a new project - a Coffee Blog - to get started quickly. verless makes this fairly easy:

$ verless create project coffee-blog

This creates a small, customizable standard project. Basically, a project is nothing else than a directory containing some components required for verless. In this case, our directory is called coffee-blog.

Developing and customizing a project

You don't need a third-party webserver like Apache for local development, because verless already comes with a built-in webserver.

One of the disadvantages of Static Site Generators is that you have to re-build your entire website each time you change a single file in your project. Fortunately, verless is able to watch your project for changes when serving the website, and it will automatically re-build the project each time you change a file.

This will serve our project on localhost:8080:

$ verless serve -w coffee-blog

The -w or --watch flag will verless make watch the project for changes.

Project configuration

verless created a top-level configuration file called verless.yml for you. Here you can set metadata, define your navigation items, enable plugins and set your theme.

Let's change into the coffee-blog directory and put some stuff into verless.yml:

version: 1
site:
  meta:
    title: My Coffee Blog
    subtitle: About Espresso & Cappuccino
    description: I'm Clara and write alot about coffee.
    author: Clara Crema
    base: http://localhost
  nav:
    items:
      - label: Home
        target: http://localhost
plugins:
  - atom
theme: default
build:
  overwrite: true

Creating content

Time to create our first article! All content is stored as Markdown files inside the content directory of our project. If you haven't quit serve yet, press Ctrl + C to stop it. Run the following command inside the project directory to create a new file:

$ verless create file making-barista-quality-espresso.md

This creates a new Markdown file as content/making-barista-quality-espresso.md. The filename defines the URL of the page, and it is relative to the content directory - so this one will be available at localhost:8080/making-barista-quality-espresso. It is that simple.

Editing content

The advantage of verless create file is that it initializes a Markdown file with a default Front Matter. The Front Matter is a small YAML section inside the Markdown where you can define metadata:

---
Title:
Description:
Date: 2020-10-12
---

Let's write some content about Barista-Quality Espresso:

---
Title: Making Barista-Quality Espresso
Date: 2020-08-14
Description: This is a guide for making italian Espresso.
Tags:
    - Espresso
    - Coffee
Img: /static/espresso.jpg
Credit: Burst on Pexels
---

Do you enjoy a high-quality italian Espresso as much as I do? Quite
frankly, making Espresso at this level isn't easy - but with the right
tools, patience and practice, you'll be able to make delicious coffee
at home.

...

I've also copied a photo into the static top-level directory of our project, using it as an image in the Img field. It will be available under localhost:8080/static/espresso.jpg.

Themes

Maybe you've already seen that our project contains a themes directory where verless stores all themes. After creating a new project, it already contains the default theme.

For our Coffee Blog, we could merely customize the default theme, but we're going to create an own theme called light for this tutorial. Just issue this command inside our project directory:

$ verless create theme light

This creates a new light directory inside themes, containing all components that a theme requires: A configuration called theme.yml and the templates and assets directories.

With these basics, we're good to start templating and styling.

Templating

Each theme requires at least two templates:

A template for rendering Markdown content: page.html
A template for rendering overview pages for each directory: list-page.html

Let's edit templates/page.html inside our new theme and write something like this:

<!DOCTYPE html>
<html>
    <head>
        <title>{{.Page.Title}}</title>
        <link rel="stylesheet" href="/assets/style.css" />
    </head>
    <body>

        <h1>{{.Page.Title}}</h1>

        <img src="{{.Page.Img}}" />

        <p>{{.Page.Description}}</p>
        <small>
            Posted on {{.Page.Date.Format "Jan 2 2006"}}.
            Photo: {{.Page.Credit}}
        </small>
        <p>{{.Page.Content}}</p>

    </body>
</html>

As you see, verless provides a stable and type-safe template API: In page.html, there are objects like .Page and .Meta available, and they possess fields like .Title. This makes verless themes re-usable across projects.

To get a complete list of available fields in the particular templates, check out the template reference.

Next, we'll edit templates/list-page.html. For each directory inside content - for example, a blog directory -, verless generates a overview page containing all pages in that directory. These are so-called list pages.

In our list-page.html, we want to provide a simple list of page titles with hyperlinks the individual pages:

<!DOCTYPE html>
<html>
    <head>
        <title>{{.Page.Title}}</title>
        <link rel="stylesheet" href="/assets/style.css" />
    </head>
    <body>

        {{range $page := .Pages}}
            <div>
                <h3>{{$page.Title}}</h3>
                <small>
                    Posted on {{$page.Date.Format "Jan 2 2006"}}
                </small>
                <p>{{$page.Description}}</p>
                <p><a href="{{$page.Href}}">read post</a></p>
            </div>
        {{end}}

    </body>
</html>

Don't forget to set the theme! We need to enable the theme in verless.yml by replacing theme: default with our new theme:

theme: light

Serving or building the website

If you're inside the project directory, serve the website using the following command and check if everything works as expected:

$ verless serve -w .

The generated website should look similar to this:

To get a deployable website that you can upload to your web hosting or cloud provider, you can build the project using verless build:

$ verless build .

The built website will go into the target directory of our project and you're good to upload it.

Plugins

verless supports some plugins that are desirable for many, but not all project out there - so verless wants you to explicitly active the plugins you need. Maybe you noticed that small plugins section in verless.yml:

plugins:
  - atom

This small plugin automatically generates a RSS feed for you. When serving our project, check it out here: localhost:8080/atom.xml
You may also check out the plugin reference.

You're now good to create your own styles, configure your pre-build hooks for generating CSS and create your very own website!

Announcing: The verless Static Site Generator

DB — Tue, 29 Sep 2020 07:01:58 +0000

So I've created a new personal website for myself and, instead of sticking with PHP again, I desired a purely static website. This means that I author content as clean & simple Markdown files, define my own HTML templates and then render the content using those templates.

Eventually, I came up with my very own Static Site Generator that perfectly fits my needs:

Flexible templating through an own theming system.
Interchangeable themes due to pre-defined template variables.
Local development without a third-party webserver.
Creating projects & themes within a single command.
High performance, parallelized site builds.
Optional RSS feeds and overview pages for tags.
Auto-generated, overwritable overview pages for all directories.
Pre-build hooks for generating assets.
Simple configuration via YAML, TOML or JSON in a central file.

So here it is: The verless Static Site Generator

It is in active development and pre-build hooks specifically or themes are coming soon, but the public API already is stable. Maybe it is useful for some of you as well!