graph

Documentation

Overview

Package graph provides graph implementation

Interface methods GetNodes, Add, AddBidirectional are the ways to interact with graph data structure. Node, Edge structures are also available with metadata for more advanced scenarios The Examples, file example_itinerary_test.go, example_connected_components_test.go are implementations of graph use cases to illustrate available features

Index

• type Edge
• type Graph
  • func NewGraph() *Graph
  • func (g *Graph) Add(source, target *Node)
  • func (g *Graph) AddBidirectional(node1, node2 *Node)
  • func (g *Graph) GetNodes() map[string]*Node
• type Interface
• type Node
  • func NewNode(name string, data interface{}) *Node

Examples

• Graph (Connected_components)
• Graph (Itinerary)

Types

type Edge

type Edge struct {
	Source   *Node
	Target   *Node
	Metadata lib.Metadata
}

Edge from source to target with metadata

type Graph

type Graph struct {
	Nodes map[string]*Node
	MData lib.Metadata
}

Graph with Nodes and metadata

Example (Connected_components)

This example uses graph for finding connected components in a collection based on certain criteria

package main

import (
	"fmt"
	"math"
	"sort"

	"github.com/qulia/go-qulia/lib/graph"
)

const (
	isVisited = "isVisited"
)

type city struct {
	name, country string
	population    int
}

// This example uses graph for finding connected components in a collection based on certain criteria
func main() {
	// Given a collection of cities, find the connected groups that are in the same country and population 1000 apart with another city
	cities := []city{
		{name: "c1", country: "country1", population: 10000},
		{name: "c2", country: "country1", population: 20000},
		{name: "c3", country: "country1", population: 10010},
		{name: "c4", country: "country1", population: 11010}, // c1 is connected with c3, c3 connected with c4, therefore c1, c3, c4 are in the same group
		{name: "c5", country: "country1", population: 20010},
		{name: "c6", country: "country2", population: 20010},
		{name: "c7", country: "country3", population: 20010},
		{name: "c8", country: "country3", population: 20011},
	}

	cityGraph := graph.NewGraph()
	// add cities to the graph
	for _, currentCity := range cities {
		newNode := graph.NewNode(currentCity.name, currentCity)
		for _, otherNode := range cityGraph.Nodes {
			otherCity := otherNode.Data.(city)
			if connected(currentCity, otherCity) {
				cityGraph.AddBidirectional(newNode, otherNode)
				// Finding one connected sufficient
				break
			}
		}

		// If not added yet, add as node
		if _, ok := cityGraph.Nodes[currentCity.name]; !ok {
			cityGraph.Add(newNode, nil)
		}
	}

	// Now find connected groups of cities
	var connected [][]city
	for _, node := range cityGraph.Nodes {
		if _, ok := node.MData[isVisited]; !ok {
			node.MData[isVisited] = true
			// Not visited yet
			connectedGroup := []city{node.Data.(city)}
			collectConnected(node, &connectedGroup)
			connected = append(connected, connectedGroup)
		}
	}

	// Sort before output for consistent result
	for _, group := range connected {
		sort.Slice(group, func(i, j int) bool {
			return group[i].name < group[j].name
		})
	}

	sort.Slice(connected, func(i, j int) bool {
		return connected[i][0].name < connected[j][0].name
	})

	fmt.Printf("%v", connected)

}

// recursively visit all reachable nodes and add to connectedgroup
func collectConnected(node *graph.Node, connectedGroup *[]city) {
	if node == nil {
		return
	}

	for _, vertex := range node.EdgesOut {
		otherNode := vertex.Target
		if _, ok := otherNode.MData[isVisited]; !ok {
			// Not visited yet
			otherNode.MData[isVisited] = true
			*connectedGroup = append(*connectedGroup, otherNode.Data.(city))
			collectConnected(otherNode, connectedGroup)
		}
	}
}

func connected(c1, c2 city) bool {
	// assume case sensitive comparison
	return c1.country == c2.country && int(math.Abs(float64(c1.population-c2.population))) <= 1000
}

Output:

[[{c1 country1 10000} {c3 country1 10010} {c4 country1 11010}] [{c2 country1 20000} {c5 country1 20010}] [{c6 country2 20010}] [{c7 country3 20010} {c8 country3 20011}]]

Example (Itinerary)

This is a problem where we need to find the itinerary using the tickets e.g. tickets [A, B] [B, C] [B,D] [C,B] itinerary A->B->C->B->D using all tickets Note that if we had picked A->B->D we would not be able to use all tickets, so not the right path Since we need to keep track of all edges we visited, metadata support on the edge can be used There could be multiple tickets available for the same source, dest pair. So we can keep track of "available edges" in the metadata

package main

import (
	"fmt"
	"sort"

	"github.com/qulia/go-qulia/lib/graph"
)

const (
	availableCount = "availableCount"
)

// This is a problem where we need to find the itinerary using the tickets
// e.g. tickets [A, B] [B, C] [B,D] [C,B] itinerary A->B->C->B->D using all tickets
// Note that if we had picked A->B->D we would not be able to use all tickets, so not the right path
// Since we need to keep track of all edges we visited, metadata support on the edge can be used
// There could be multiple tickets available for the same source, dest pair. So we can keep track of
// "available edges" in the metadata
func main() {
	tickets := [][]string{{"A", "B"}, {"B", "C"}, {"B", "D"}, {"C", "B"}}
	fmt.Printf("%v\n", testWithTickets(tickets))

	tickets = [][]string{{"A", "B"}, {"A", "C"}, {"C", "A"}}
	fmt.Printf("%v\n", testWithTickets(tickets))

	// Note there are two tickets D,B so availableCount is initially 2 for this edge
	tickets = [][]string{{"E", "F"}, {"D", "B"}, {"B", "C"}, {"C", "B"}, {"B", "E"}, {"D", "B"}, {"F", "D"}, {"D", "C"}, {"B", "D"}, {"C", "D"}}
	fmt.Printf("%v", testWithTickets(tickets))
}

func testWithTickets(tickets [][]string) []string {
	// Create graph with source, dest in tickets
	cGraph := graph.NewGraph()
	for _, ticket := range tickets {
		cGraph.Add(createOrGetNewNode(cGraph, ticket[0]), createOrGetNewNode(cGraph, ticket[1]))
		m := cGraph.Nodes[ticket[0]].EdgesOut[ticket[1]].Metadata
		if _, ok := m[availableCount]; !ok {
			m[availableCount] = 0
		}
		m[availableCount] = m[availableCount].(int) + 1
	}
	//Find itinerary using all edges
	numEdges := len(tickets)
	var itinerary []string

	// sort nodes to get lexical order in result
	var nodeNames []string
	for key := range cGraph.Nodes {
		nodeNames = append(nodeNames, key)
	}

	sort.Strings(nodeNames)
	for _, nodeName := range nodeNames {
		node := cGraph.Nodes[nodeName]
		itinerary = append(itinerary, node.Name)
		if visitAll(node, numEdges, &itinerary) {
			break
		} else {
			itinerary = itinerary[:len(itinerary)-1]
		}
	}

	return itinerary
}

func visitAll(node *graph.Node, numEdges int, itinerary *[]string) bool {
	if len(*itinerary) == numEdges+1 {
		return true
	}

	// sort targets to get lexical order in result
	var edgeNames []string
	for key := range node.EdgesOut {
		edgeNames = append(edgeNames, key)
	}

	sort.Strings(edgeNames)
	for _, edgeName := range edgeNames {
		edge := node.EdgesOut[edgeName]
		m := edge.Metadata
		if m[availableCount].(int) > 0 {
			m[availableCount] = m[availableCount].(int) - 1
			target := edge.Target
			*itinerary = append(*itinerary, target.Name)
			if visitAll(target, numEdges, itinerary) {
				return true
			} else {
				// backtrack so it can be visited again
				m[availableCount] = m[availableCount].(int) + 1
				*itinerary = (*itinerary)[:len(*itinerary)-1]
			}
		}
	}

	return false
}

func createOrGetNewNode(cGraph graph.Interface, name string) *graph.Node {
	if node, ok := cGraph.GetNodes()[name]; ok {
		return node
	}
	return graph.NewNode(name, nil)
}

Output:

[A B C B D]
[A C A B]
[B C B D B E F D C D B]

func NewGraph

func NewGraph() *Graph

NewGraph initialized graph structure

func (*Graph) Add

func (g *Graph) Add(source, target *Node)

Add relation to the graph, directional from source node to target node

func (*Graph) AddBidirectional

func (g *Graph) AddBidirectional(node1, node2 *Node)

Add relation to the graph, bidirectional with node1 and node2, each direction with its own metadata

func (*Graph) GetNodes

func (g *Graph) GetNodes() map[string]*Node

GetNodes

type Interface

type Interface interface {
	// GetNodes returns map of all nodes in the graph
	GetNodes() map[string]*Node

	// Add relation from source to target node
	// if target is nil just add the node with no connection
	Add(source, target *Node)

	// Add bidirectional relation between node1 and node2, equivalent to calling
	// Add(node1, node2) Add(node2, node1)
	AddBidirectional(node1, node2 *Node)
}

type Node

type Node struct {
	Name string

	// The data associated with Node, e.g. person
	Data interface{}

	// Outgoing edges Target node.Name is the key, current node is the source
	EdgesOut map[string]Edge

	// Source node.Name is the key, current node is the target
	EdgesIn map[string]Edge

	// This is free form map to set values while traversing graph, e.g. "isVisited = true"
	// Normally would be used for more advanced scenarios
	MData lib.Metadata
}

Node with name, object holding the data, connections in and out, and metadata

func NewNode

func NewNode(name string, data interface{}) *Node

NewNode creates a node later to be added to the graph