cspf

package module
v0.0.0-...-6fd406b Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 3, 2020 License: MIT Imports: 5 Imported by: 0

README

Constrained Shortest Path First

GoDoc License Build Status Coverage Status Go Report Card

Introduction

This package implements the Constrained Shortest Path First algorithm with a generic tag system and condition-matching engine powered by gval.

CSPF theory abridged

Let's assume we have the following graph, consisting of 5 vertices and edges belonging to two different categories: red and blue. With CSPF it is possible to find out what the shortest path that connects vertex A to vertex E and that includes only red edges is.

CSPF uses a slightly modified version of the Dijkstra algorithm. For each round of the Dijkstra algorithm, it considers only the edges that match the constraint expression. This is basically equivalent to pruning the edges that do not satisfy the constraint from the initial graph and then runnning the Dijkstra algorithm.

API Documentation

Documentation can be found here.

Example

Here is an example that shows how to create a graph with labeled edges and call the CSPF algorithm on it. The graph in this example is the same showed in the theory section.

// Create a graph with five vertices.
// A -> B -> C -> E
// A -> D -> E
var graph cspf.Graph
a := cspf.Vertex{ID: "A"}
b := cspf.Vertex{ID: "B"}
c := cspf.Vertex{ID: "C"}
d := cspf.Vertex{ID: "D"}
e := cspf.Vertex{ID: "E"}

// Create red and blue tag
tagBlue := cspf.Tag{
    Key:   "link",
    Value: "blue",
}
tagRed := cspf.Tag{
    Key:   "link",
    Value: "red",
}

// Add the edges with labels
graph.AddEdge(a, b, 2, tagRed)
graph.AddEdge(b, c, 2, tagRed)
graph.AddEdge(c, e, 2, tagRed)
graph.AddEdge(a, d, 1, tagBlue)
graph.AddEdge(d, e, 1, tagBlue)

// Run the CSPF algorithm to
// derive the graph containing
// the shortest path from A to E that 
// includes only red edges.
cspfGraph, _ := graph.CSPF(a, d, `link == "red"`)

// List the path from vertex A
// to vertex E.
paths := cspfGraph.Paths(a, e)

fmt.Println(paths)
// Output: [[{{A} {B} 2 map[link:red]} {{B} {C} 2 map[link:red]} {{C} {E} 2 map[link:red]}]]

Benchmarks and performance

This package is in its early stages and there is room for improvements. Below benchmark's stats are the results of 20 repetitions with a fully-connected graph of 100 vertices. CSPF is much slower than normal SPF (Dijkstra) due to the additional complexity added by gval to parse and evalaute the generic expressions.

goos: darwin
goarch: amd64

name      time/op
SPF-16     740µs ± 2%
Paths-16  24.7µs ± 3%
CSPF-16   3.87ms ± 4%

name      alloc/op
SPF-16    55.3kB ± 0%
Paths-16  15.2kB ± 0%
CSPF-16   1.10MB ± 0%

name      allocs/op
SPF-16       144 ± 0%
Paths-16     208 ± 0%
CSPF-16    29.9k ± 0%

License

The cspf package is licensed under the MIT License. Please see the LICENSE file for details.

Contributing and bug reports

This package surely needs your help and feedbacks. You are welcome to open a new issue here on GitHub.

Documentation

Overview

Package cspf implements the Costrained Shortest Path First algorithm to find the shortest paths in a graph that satisfy a set of generic conditions. Every edge that connects two vertices of the graph can be labeled with generic key/value pairs. The conditions are parsed and evaluated using github.com/PaesslerAG/gval package. Thus, any expression and value type currently supported by this package can be used to state the constraints.

Index

Examples

Constants

This section is empty.

Variables

View Source 
var (
	// ErrDuplicateTagKey is returned by AddEdge method
	// when one Tag's key was specified more than once.
	ErrDuplicateTagKey = errors.New("DuplicateTagKey")
	// ErrNilGraph is returned whenever one method
	// was called on a nil cspf.Graph object
	ErrNilGraph = errors.New("NilGraph")
)

Functions

This section is empty.

Types

type Edge 

type Edge struct {
	// Source vertex of this edge.
	From Vertex
	// Destination vertex of this edge.
	To Vertex
	// Numeric cost of this edge.
	Cost uint64
	// Set of generic key/value tags.
	// Tag key is a unique string, whereas
	// the value can be of any type.
	Tags map[string]interface{}
}

Edge represents a directed edge that connects one vertex to another. Edge must have a non-negative cost and can have a set of generic tags. Each tag must have a unique key string. CSPF conditions apply on these tags.

type Graph 

type Graph struct {
	// Set of vertices of this graph
	// with associated list of edges originating
	// from every vertex.
	VertexSet map[Vertex][]Edge
	// contains filtered or unexported fields
}

Graph represents a directed graph.

Example 
package main

import (
	"fmt"

	"github.com/bigmikes/cspf"
)

func main() {
	// A cspf.Graph needs no initialization.
	var graph cspf.Graph

	// Create two vertices.
	a := cspf.Vertex{ID: "A"}
	b := cspf.Vertex{ID: "B"}

	// Add an directed edge between
	// the two vertices: A -> B.
	graph.AddEdge(a, b, 1)

	// List all the paths from vertex A
	// to vertex B.
	paths := graph.Paths(a, b)

	fmt.Println(paths)
}

Output:

[[{{A} {B} 1 map[]}]]

func (*Graph) AddEdge 

func (g *Graph) AddEdge(from, to Vertex, cost uint64, tags ...Tag) error

AddEdge adds a new edge between two vertices with an associated cost and possibly a set of tags. If the two vertices do not exist, AddEdge adds them to the graph automatically.

func (*Graph) AddNode 

func (g *Graph) AddNode(v Vertex)

AddNode adds a new vertex to the graph with no edges. It is preferable to use AddEdge, given that it adds the vertex automatically if missing.

func (*Graph) CSPF 

func (g *Graph) CSPF(from, to Vertex, exp string) (*Graph, error)

CSPF runs the Constrained Shortest Path First algorithm to find the shortest paths whose edges all satisfy the specified expression. An edge cannot be part of the resulting graph if its tags do not satisfy the specified expression. The tag key/value pairs and the generic expression are internally evaluated through github.com/PaesslerAG/gval package.

Example 
package main

import (
	"fmt"

	"github.com/bigmikes/cspf"
)

func main() {
	// Create a graph with five vertices.
	// A -> B -> C -> E
	// A -> D -> E
	var graph cspf.Graph
	a := cspf.Vertex{ID: "A"}
	b := cspf.Vertex{ID: "B"}
	c := cspf.Vertex{ID: "C"}
	d := cspf.Vertex{ID: "D"}
	e := cspf.Vertex{ID: "E"}

	// Create red and blue tag
	tagBlue := cspf.Tag{
		Key:   "link",
		Value: "blue",
	}
	tagRed := cspf.Tag{
		Key:   "link",
		Value: "red",
	}

	// Add the edges with labels
	graph.AddEdge(a, b, 2, tagRed)
	graph.AddEdge(b, c, 2, tagRed)
	graph.AddEdge(c, e, 2, tagRed)
	graph.AddEdge(a, d, 1, tagBlue)
	graph.AddEdge(d, e, 1, tagBlue)

	// Run the CSPF algorithm to
	// derive the graph containing
	// the shortest path from A to E that
	// includes only red edges.
	cspfGraph, _ := graph.CSPF(a, d, `link == "red"`)

	// List the path from vertex A
	// to vertex E.
	paths := cspfGraph.Paths(a, e)

	fmt.Println(paths)
}

Output:

[[{{A} {B} 2 map[link:red]} {{B} {C} 2 map[link:red]} {{C} {E} 2 map[link:red]}]]

func (*Graph) Paths 

func (g *Graph) Paths(from, to Vertex) (paths [][]Edge)

Paths lists all the possible paths of the graph that connect from one vertex to the other. Paths are listed through Depth-First Search algorithm.

func (*Graph) SPF 

func (g *Graph) SPF(from, to Vertex) (*Graph, error)

SPF runs the Dijkstra algorithm to build a result graph only containing the shortest paths from one vertex to another. All shortest paths with equal cost are part of the result graph.

Example 
package main

import (
	"fmt"

	"github.com/bigmikes/cspf"
)

func main() {
	// Create a graph with four vertices.
	// A -> B -> D
	// A -> C -> D
	var graph cspf.Graph
	a := cspf.Vertex{ID: "A"}
	b := cspf.Vertex{ID: "B"}
	c := cspf.Vertex{ID: "C"}
	d := cspf.Vertex{ID: "D"}

	// Add the edges
	graph.AddEdge(a, b, 1)
	graph.AddEdge(a, c, 2)
	graph.AddEdge(b, d, 1)
	graph.AddEdge(c, d, 1)

	// Run the Dijkstra algorithm to
	// derive the graph containing only
	// the shortest paths (equal cost)
	// from A to D.
	spfGraph, _ := graph.SPF(a, d)

	// List the path from vertex A
	// to vertex D.
	paths := spfGraph.Paths(a, d)

	fmt.Println(paths)
}

Output:

[[{{A} {B} 1 map[]} {{B} {D} 1 map[]}]]

type Tag 

type Tag struct {
	// Key is the unique key string
	Key string
	// Value is a generic value
	Value interface{}
}

Tag contains a generic key/value pair that can be attached to cspf.Edge. Key must be unique within a single cspf.Edge.

type Vertex 

type Vertex struct {
	// ID uniquely identifies a vertex inside
	// the graph.
	ID string
}

Vertex represents a vertex of the graph.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.