Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!

Idiom #40 Graph with adjacency lists

Declare a Graph data structure in which each Vertex has a collection of its neighbouring vertices.

type Vertex struct{
	Id int
	Label string
	Neighbours map[*Vertex]bool
}

type Graph []*Vertex
type Graph[L any] []*Vertex[L]

type Vertex[L any] struct {
	Label      L
	Neighbours map[*Vertex[L]]bool
}
struct Vertex
{
	float x, y, z;
	Vertex* [] adjacentVertices;
}
datatype Node = Int
datatype Adjacencies = [ Node ]
datatype Graph = [ Adjacencies ]
import java.util.List;
class Graph{
  List<Vertex> vertices;

  static class Vertex{
    int id;
    List<Vertex> neighbours;
  }
}
import java.util.Set;
class Graph{
  Set<Vertex> vertices;

  static class Vertex{
    int id;
    Set<Vertex> neighbours;
  }
}
inline class VertexId(val id: Int)
data class Vertex(val id: VertexId, val neighbours: Set<VertexId>)
data class Graph(val vertices: Set<Vertex>)
use Graph::Undirected qw();
my $G = Graph::Undirected->new(edges => [
    [1,3], [2,4], [3,4], [3,5], [4,5]
]);
from collections import defaultdict
class Vertex(set): pass
class Graph(defaultdict):
  def __init__(self, *paths):
    self.default_factory = Vertex
    for path in paths:
      self.make_path(path)

  def make_path(self, labels):
    for l1, l2 in zip(labels, labels[1:]):
      self[l1].add(l2)
      self[l2].add(l1)

G = Graph((0, 1, 2, 3), (1, 4, 2))
Vertex = Struct.new(:x, :y, :z)
Graph = Struct.new(:vertex, :neighbours)

v = Vertex.new(1, 2, 3)
neighbours = [ Vertex.new(2, 3, 4), Vertex.new(4, 5, 6) ]
graph = Graph.new(v, neighbours)

New implementation...