graph

README

Graph

This package provides a simple implementation of a graph data structures useing adjacency list representation written in Go.

features

graph.DirectedGraph : directed graph
graph.UndirectedGraph : undirected graph

Both structure implements graph.Graph.

type Graph interface {
	AddEdge(i1, i2 int)
	DeleteEdge(i1, i2 int)
	ForEachSuccessor(index int, f func(int))
	GetDegree(index int) int
	HasEdge(i1, i2 int) bool
	Order() int
	Size() int
	Clear()
}

example

package main

import (
	"fmt"

	"github.com/TadaTeruki/graph"
)

func main() {
	g := graph.NewDirectedGraph(4) // Create a new graph with 4 vertices

	g.AddEdge(0, 1) // Add an edge from 0 to 1

	g.AddEdge(2, 3) // Add an edge from 0 to 2

	// Add more edges
	g.AddEdge(1, 2)
	g.AddEdge(0, 2)

	for i := 0; i < g.Order(); i++ {
		fmt.Println("Vertex", i, "has degree", g.GetDegree(i))
		g.ForEachSuccessor(i, func(j int) {
			fmt.Println("Vertex", i, "has edge for: ", j)
		})
	}
}

Documentation

Overview

Package graph implements a simple graph data structure.

Package graph implements a simple graph data structure.

Package graph implements a simple graph data structure.

Index

• type DirectedGraph
  • func NewDirectedGraph(order int) *DirectedGraph
  • func (g *DirectedGraph) AddEdge(i1, i2 int)
  • func (g *DirectedGraph) Clear()
  • func (g *DirectedGraph) DeleteEdge(i1, i2 int)
  • func (g *DirectedGraph) ForEachSuccessor(index int, f func(int))
  • func (g *DirectedGraph) GetDegree(index int) int
  • func (g *DirectedGraph) HasEdge(i1, i2 int) bool
  • func (g *DirectedGraph) Order() int
  • func (g *DirectedGraph) Size() int
• type Graph
• type UndirectedGraph
  • func NewUndirectedGraph(order int) *UndirectedGraph
  • func (g *UndirectedGraph) AddEdge(i1, i2 int)
  • func (g *UndirectedGraph) Clear()
  • func (g *UndirectedGraph) DeleteEdge(i1, i2 int)
  • func (g *UndirectedGraph) ForEachSuccessor(index int, f func(int))
  • func (g *UndirectedGraph) GetDegree(index int) int
  • func (g *UndirectedGraph) HasEdge(i1, i2 int) bool
  • func (g *UndirectedGraph) Order() int
  • func (g *UndirectedGraph) Size() int

Types

type DirectedGraph

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

DirectedGraph is the directed graph.

func NewDirectedGraph

func NewDirectedGraph(order int) *DirectedGraph

NewDirectedGraph creates a new directed graph with a given order (number of vertices).

func (*DirectedGraph) AddEdge

func (g *DirectedGraph) AddEdge(i1, i2 int)

AddEdge adds a directed edge from i1 to i2 in the graph.

func (*DirectedGraph) Clear

func (g *DirectedGraph) Clear()

Clear removes all edges from the graph.

func (*DirectedGraph) DeleteEdge

func (g *DirectedGraph) DeleteEdge(i1, i2 int)

DeleteEdge removes a directed edge from i1 to i2 in the graph.

func (*DirectedGraph) ForEachSuccessor

func (g *DirectedGraph) ForEachSuccessor(index int, f func(int))

ForEachSuccessor applies the given function to each vertex that is a successor of the vertex with the given index.

func (*DirectedGraph) GetDegree

func (g *DirectedGraph) GetDegree(index int) int

GetDegree returns the degree of the vertex with the given index.

func (*DirectedGraph) HasEdge

func (g *DirectedGraph) HasEdge(i1, i2 int) bool

HasEdge returns true if there is an edge from i1 to i2 in the graph, and false otherwise.

func (*DirectedGraph) Order

func (g *DirectedGraph) Order() int

Order returns the number of vertices in the graph.

func (*DirectedGraph) Size

func (g *DirectedGraph) Size() int

Size returns the number of edges in the graph. Requires O(N) to compute.

type Graph

type Graph interface {
	AddEdge(i1, i2 int)
	DeleteEdge(i1, i2 int)
	ForEachSuccessor(index int, f func(int))
	GetDegree(index int) int
	HasEdge(i1, i2 int) bool
	Order() int
	Size() int
	Clear()
}

Graph is an interface for a graph data structure.

type UndirectedGraph

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

UndirectedGraph is the undirected graph.

func NewUndirectedGraph

func NewUndirectedGraph(order int) *UndirectedGraph

NewUndirectedGraph creates a new undirected graph with a given order (number of vertices).

func (*UndirectedGraph) AddEdge

func (g *UndirectedGraph) AddEdge(i1, i2 int)

AddEdge adds an undirected edge between i1 and i2 in the graph.

func (*UndirectedGraph) Clear

func (g *UndirectedGraph) Clear()

Clear removes all edges from the graph.

func (*UndirectedGraph) DeleteEdge

func (g *UndirectedGraph) DeleteEdge(i1, i2 int)

DeleteEdge removes an undirected edge between i1 and i2 in the graph.

func (*UndirectedGraph) ForEachSuccessor

func (g *UndirectedGraph) ForEachSuccessor(index int, f func(int))

ForEachSuccessor applies the given function to each vertex that is a successor of the vertex with the given index.

func (*UndirectedGraph) GetDegree

func (g *UndirectedGraph) GetDegree(index int) int

GetDegree returns the degree of the vertex with the given index.

func (*UndirectedGraph) HasEdge

func (g *UndirectedGraph) HasEdge(i1, i2 int) bool

HasEdge returns true if there is an edge between i1 and i2 in the graph, and false otherwise.

func (*UndirectedGraph) Order

func (g *UndirectedGraph) Order() int

Order returns the number of vertices in the graph.

func (*UndirectedGraph) Size

func (g *UndirectedGraph) Size() int

Size returns the number of edges in the graph. Requires O(N) to compute.