topo

package
v0.9.2 Latest Latest
Warning

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

 Go to latest Published: May 11, 2021 License: BSD-3-Clause Imports: 8 Imported by: 0

Documentation

Overview

Package topo provides graph topology analysis functions.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func BronKerbosch 

func BronKerbosch(g graph.Undirected) [][]graph.Node

BronKerbosch returns the set of maximal cliques of the undirected graph g.

func CliqueGraph 

func CliqueGraph(dst Builder, g graph.Undirected)

CliqueGraph builds the clique graph of g in dst using Clique and CliqueGraphEdge nodes and edges. The nodes returned by calls to Nodes on the nodes and edges of the constructed graph are the cliques and the common nodes between cliques respectively. The dst graph is not cleared.

func ConnectedComponents 

func ConnectedComponents(g graph.Undirected) [][]graph.Node

ConnectedComponents returns the connected components of the undirected graph g.

func DegeneracyOrdering 

func DegeneracyOrdering(g graph.Undirected) (order []graph.Node, cores [][]graph.Node)

DegeneracyOrdering returns the degeneracy ordering and the k-cores of the undirected graph g.

func DirectedCyclesIn 

func DirectedCyclesIn(g graph.Directed) [][]graph.Node

DirectedCyclesIn returns the set of elementary cycles in the graph g.

func Equal 

func Equal(a, b graph.Graph) bool

Equal returns whether two graphs are topologically equal. To be considered topologically equal, a and b must have identical sets of nodes and be identically traversable.

func IsPathIn 

func IsPathIn(g graph.Graph, path []graph.Node) bool

IsPathIn returns whether path is a path in g.

As special cases, IsPathIn returns true for a zero length path or for a path of length 1 when the node in path exists in the graph.

func KCore 

func KCore(k int, g graph.Undirected) []graph.Node

KCore returns the k-core of the undirected graph g with nodes in an optimal ordering for the coloring number.

func PathExistsIn 

func PathExistsIn(g graph.Graph, from, to graph.Node) bool

PathExistsIn returns whether there is a path in g starting at from extending to to.

PathExistsIn exists as a helper function. If many tests for path existence are being performed, other approaches will be more efficient.

func Sort 

func Sort(g graph.Directed) (sorted []graph.Node, err error)

Sort performs a topological sort of the directed graph g returning the 'from' to 'to' sort order. If a topological ordering is not possible, an Unorderable error is returned listing cyclic components in g with each cyclic component's members sorted by ID. When an Unorderable error is returned, each cyclic component's topological position within the sorted nodes is marked with a nil graph.Node.

func SortStabilized 

func SortStabilized(g graph.Directed, order func([]graph.Node)) (sorted []graph.Node, err error)

SortStabilized performs a topological sort of the directed graph g returning the 'from' to 'to' sort order, or the order defined by the in place order sort function where there is no unambiguous topological ordering. If a topological ordering is not possible, an Unorderable error is returned listing cyclic components in g with each cyclic component's members sorted by the provided order function. If order is nil, nodes are ordered lexically by node ID. When an Unorderable error is returned, each cyclic component's topological position within the sorted nodes is marked with a nil graph.Node.

func TarjanSCC 

func TarjanSCC(g graph.Directed) [][]graph.Node

TarjanSCC returns the strongly connected components of the graph g using Tarjan's algorithm.

A strongly connected component of a graph is a set of vertices where it's possible to reach any vertex in the set from any other (meaning there's a cycle between them.)

Generally speaking, a directed graph where the number of strongly connected components is equal to the number of nodes is acyclic, unless you count reflexive edges as a cycle (which requires only a little extra testing.)

Example (TwoSAT) 
package main

import (
	"bufio"
	"fmt"
	"io"
	"log"
	"sort"
	"strings"

	"gonum.org/v1/gonum/graph/simple"
	"gonum.org/v1/gonum/graph/topo"
)

var systems = []string{
	// Unsatisfiable system.
	`𝑥_a ∨ ¬𝑥_b
¬𝑥_b ∨ 𝑥_f
𝑥_h ∨ 𝑥_i
𝑥_a ∨ 𝑥_b
𝑥_k ∨ 𝑥_c
¬𝑥_f ∨ 𝑥_h
𝑥_c ∨ 𝑥_g
𝑥_f ∨ 𝑥_g
𝑥_h ∨ ¬𝑥_l
¬𝑥_h ∨ 𝑥_i
𝑥_i ∨ 𝑥_b
¬𝑥_i ∨ ¬𝑥_h
𝑥_i ∨ ¬𝑥_c
𝑥_l ∨ 𝑥_d
¬𝑥_j ∨ ¬𝑥_i
¬𝑥_a ∨ ¬𝑥_j
¬𝑥_a ∨ 𝑥_b
¬𝑥_d ∨ 𝑥_e
¬𝑥_k ∨ 𝑥_h
𝑥_l ∨ ¬𝑥_d
𝑥_l ∨ 𝑥_d
𝑥_l ∨ ¬𝑥_f
𝑥_b ∨ 𝑥_d
𝑥_b ∨ ¬𝑥_g
𝑥_d ∨ ¬𝑥_l
¬𝑥_l ∨ ¬𝑥_k
`,
	// Satisfiable system.
	`𝑥_a ∨ ¬𝑥_b
¬𝑥_b ∨ 𝑥_f
𝑥_h ∨ 𝑥_i
𝑥_a ∨ 𝑥_b
𝑥_k ∨ 𝑥_c
¬𝑥_f ∨ 𝑥_h
𝑥_c ∨ 𝑥_g
𝑥_f ∨ 𝑥_g
𝑥_h ∨ ¬𝑥_l
¬𝑥_h ∨ 𝑥_i
𝑥_i ∨ 𝑥_b
¬𝑥_i ∨ 𝑥_e
𝑥_i ∨ ¬𝑥_c
¬𝑥_g ∨ ¬𝑥_a
𝑥_l ∨ 𝑥_f
¬𝑥_j ∨ ¬𝑥_i
¬𝑥_a ∨ ¬𝑥_j
¬𝑥_a ∨ 𝑥_b
¬𝑥_d ∨ 𝑥_e
𝑥_k ∨ ¬𝑥_a
𝑥_k ∨ 𝑥_h
𝑥_l ∨ ¬𝑥_d
𝑥_l ∨ 𝑥_e
𝑥_l ∨ ¬𝑥_f
𝑥_b ∨ 𝑥_d
𝑥_b ∨ ¬𝑥_g
𝑥_d ∨ ¬𝑥_l
𝑥_l ∨ 𝑥_e
`,

	`fun ∨ ¬fun
fun ∨ ¬Gonum
Gonum ∨ Gonum
`,
}

// twoSat returns whether the system described in the data read from r is
// satisfiable and a set of states that satisfies the system.
// The syntax used by twoSat is "𝑥 ∨ 𝑦" where 𝑥 and 𝑦 may be negated by
// leading "¬" characters. twoSat uses the implication graph approach to
// system analysis.
func twoSat(r io.Reader) (state map[string]bool, ok bool) {
	g := simple.NewDirectedGraph()

	sc := bufio.NewScanner(r)
	nodes := make(map[string]node)
	for count := 1; sc.Scan(); count++ {
		line := sc.Text()
		fields := strings.Split(line, "∨")
		if len(fields) != 2 {
			log.Fatalf("failed to parse on line %d %q: invalid syntax", count, line)
		}
		var variables [2]node
		for i, f := range fields {
			f = strings.TrimSpace(f)
			var negate bool
			for strings.Index(f, "¬") == 0 {
				f = strings.TrimPrefix(f, "¬")
				negate = !negate
			}
			n, ok := nodes[f]
			if !ok {
				n = node{
					id:   int64(len(nodes) + 1), // id must not be zero.
					name: f,
				}
				nodes[f] = n
			}
			if negate {
				n = n.negated()
			}
			variables[i] = n
		}

		// Check for tautology.
		if variables[0].negated().ID() == variables[1].ID() {
			for _, v := range variables {
				if g.Node(v.ID()) == nil {
					g.AddNode(v)
				}
			}
			continue
		}

		// Add implications to the graph.
		g.SetEdge(simple.Edge{F: variables[0].negated(), T: variables[1]})
		g.SetEdge(simple.Edge{F: variables[1].negated(), T: variables[0]})
	}

	// Find implication inconsistencies.
	sccs := topo.TarjanSCC(g)
	for _, c := range sccs {
		set := make(map[int64]struct{})
		for _, n := range c {
			id := n.ID()
			if _, ok := set[-id]; ok {
				return nil, false
			}
			set[id] = struct{}{}
		}
	}

	// Assign states.
	state = make(map[string]bool)
unknown:
	for _, c := range sccs {
		for _, n := range c {
			if _, known := state[n.(node).name]; known {
				continue unknown
			}
		}
		for _, n := range c {
			n := n.(node)
			state[n.name] = n.id > 0
		}
	}

	return state, true
}

type node struct {
	id   int64
	name string
}

func (n node) ID() int64     { return n.id }
func (n node) negated() node { return node{-n.id, n.name} }

func main() {
	for i, s := range systems {
		state, ok := twoSat(strings.NewReader(s))
		if !ok {
			fmt.Printf("system %d is not satisfiable\n", i)
			continue
		}
		var ps []string
		for v, t := range state {
			ps = append(ps, fmt.Sprintf("%s:%t", v, t))
		}
		sort.Strings(ps)
		fmt.Printf("system %d is satisfiable: %s\n", i, strings.Join(ps, " "))
	}

}

Output:

system 0 is not satisfiable
system 1 is satisfiable: 𝑥_a:true 𝑥_b:true 𝑥_c:true 𝑥_d:true 𝑥_e:true 𝑥_f:true 𝑥_g:false 𝑥_h:true 𝑥_i:true 𝑥_j:false 𝑥_k:true 𝑥_l:true
system 2 is satisfiable: Gonum:true fun:true

func UndirectedCyclesIn 

func UndirectedCyclesIn(g graph.Undirected) [][]graph.Node

UndirectedCyclesIn returns a set of cycles that forms a cycle basis in the graph g. Any cycle in g can be constructed as a symmetric difference of its elements.

Types

type Builder 

type Builder interface {
	AddNode(graph.Node)
	SetEdge(graph.Edge)
}

Builder is a pure topological graph construction type.

type Clique 

type Clique struct {
	// contains filtered or unexported fields
}

Clique is a node in a clique graph.

func (Clique) ID 

func (n Clique) ID() int64

ID returns the node ID.

func (Clique) Nodes 

func (n Clique) Nodes() []graph.Node

Nodes returns the nodes in the clique.

type CliqueGraphEdge 

type CliqueGraphEdge struct {
	// contains filtered or unexported fields
}

CliqueGraphEdge is an edge in a clique graph.

func (CliqueGraphEdge) From 

func (e CliqueGraphEdge) From() graph.Node

From returns the from node of the edge.

func (CliqueGraphEdge) Nodes 

func (e CliqueGraphEdge) Nodes() []graph.Node

Nodes returns the common nodes in the cliques of the underlying graph corresponding to the from and to nodes in the clique graph.

func (CliqueGraphEdge) ReversedEdge 

func (e CliqueGraphEdge) ReversedEdge() graph.Edge

ReversedEdge returns a new CliqueGraphEdge with the edge end points swapped. The nodes of the new edge are shared with the receiver.

func (CliqueGraphEdge) To 

func (e CliqueGraphEdge) To() graph.Node

To returns the to node of the edge.

type Unorderable 

type Unorderable [][]graph.Node

Unorderable is an error containing sets of unorderable graph.Nodes.

func (Unorderable) Error 

func (e Unorderable) Error() string

Error satisfies the error interface.

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.