Graph

Representation	Space	Time
		Access	Lookup	Insertion	Deletion
Adjacency Matrix	`O(V²)`	`O(1)`	`O(V)`	`O(1)`	`O(1)`
Adjacency List	`O(V+E)` • `V` is the number of vertices • `E` is the number of edges	`O(1)`	`O(1)`	`O(1)`	`O(1)`

Definition

Short
Detailed

Graph is a collection of nodes connected by edges, where each node represents a entity and each edge represents a relationship between 2 entities.

Simplified

Graph in software engineering is like a city map. It shows how different things, like cities (nodes), are connected by roads (edges). It's used to solve complex problems, like finding the shortest route or recommending friends on social media.

Practice

Practice
Solution

Aspect	Pseudo Code
Graph Edge	`GraphEdge get_key() return start_vertex.value + '_' + end_vertex.value reverse() tmp = start_vertex start_vertex = end_vertex end_vertex = tmp`
Graph Vertex	GraphVertex add_edge(edge) edges.append(edge) delete_edge(edge) edges.delete(edge) get_neighbors() neighbors = [] for (node in edges): if node.value.start_vertex == this: neighbors.add(node.value.end_vertex) else: neighbors.add(node.value.start_vertex) return neighbors getEdges() edges = [] for (node in edges): edges.add(node.value) get_degree() edges.length has_edge(required_edge) return edges.find(required_edge) has_neighbor(vertex) return edges.find(start_vertex === vertex or edge.end_vertex === vertex) find_edge(vertex) return edges.find(edge.start_vertex === vertex or edge.end_vertex === vertex) delete_all_edges() for (node in get_edges()): delete_edge(node)
Get Vertex by Key	`get_vertex_by_key(vertexKey) return vertices[vertexKey]`
Add Edge	add_edge(edge) start_vertex = get_vertex_by_key(edge.start_vertex.value) end_vertex = get_vertex_by_key(edge.end_vertex.value) if start_vertex != ø: add_vertex(edge.start_vertex) start_vertex = get_vertex_by_key(edge.start_vertex.value) if end_vertex != ø: add_vertex(edge.end_vertex) end_vertex = get_vertex_by_key(edge.end_vertex.value) if edges[edge.get_key()]: throw Error('Edge has already been added before') else: edges[edge.get_key()] = edge if isDirected: start_vertex.add_edge(edge) else: start_vertex.add_edge(edge) end_vertex.add_edge(edge) add_vertex(new_vertex) vertices[new_vertex.value] = new_vertex
Delete Edge	`delete_edge(edge) if edges[edge.get_key()]: delete edges[edge.get_key()] else: 'Edge not found in graph' start_vertex = get_vertex_by_key(edge.start_vertex.value) end_vertex = get_vertex_by_key(edge.end_vertex.value) start_vertex.delete_edge(edge) end_vertex.delete_edge(edge)`
Get All Edges	`get_all_edges() edges = [] for {key, edge} in edges: vertices.add(vertex) return edges`
Get Weight	`get_weight() weight = 0 for graph_edge in get_all_edges(): weight += graph_edge.weight return weight`
Reverse	`reverse() for edge in get_all_edges(): delete_edge(edge) edge.reverse() add_edge(edge)`
Find Edge	`find_edge(start_vertex, end_vertex) vertex = get_vertex_by_key(start_vertex.value) if vertex != ø return null return vertex.find_edge(end_vertex)`
Get Adjacency Matrix	get_adjacency_matrix() vertices_indices = get_vertices_indices() adjacency_matrix = [][] for {i, vertex} in get_all_vertices(): for neighbor in vertex.get_neighbors(): adjacency_matrix[vertexIndex][vertices_indices[neighbor.get_key()]] = find_edge(vertex, neighbor).weight)) return adjacency_matrix get_vertices_indices() vertices_indices = Map() for {i, vertex} in vertices: vertices_indices[vertex.value] = index return vertices_indices get_neighbors(vertex) return vertex.get_neighbors() get_all_vertices() vertices = [] for {key, vertex} in vertices: vertices.add(vertex) return vertices

package main

import (
	"strings"
)

type GraphEdge struct {
	startVertex *GraphVertex
	endVertex   *GraphVertex
	weight      int
}

func NewGraphEdge(startVertex, endVertex *GraphVertex, weight int) *GraphEdge {
	return &GraphEdge{
		startVertex: startVertex,
		endVertex:   endVertex,
		weight:      weight,
	}
}

func (edge *GraphEdge) GetKey() string {
	startVertexKey := edge.startVertex.GetKey()
	endVertexKey := edge.endVertex.GetKey()
	return fmt.Sprintf("%s_%s", startVertexKey, endVertexKey)
}

func (edge *GraphEdge) Reverse() *GraphEdge {
	edge.startVertex, edge.endVertex = edge.endVertex, edge.startVertex
	return edge
}

type GraphVertex struct {
	value interface{}
	edges []*GraphEdge
}

func NewGraphVertex(value interface{}) *GraphVertex {
	if value == nil {
		panic("Graph vertex must have a value")
	}

	return &GraphVertex{
		value: value,
		edges: make([]*GraphEdge, 0),
	}
}

func (vertex *GraphVertex) AddEdge(edge *GraphEdge) *GraphVertex {
	vertex.edges = append(vertex.edges, edge)
	return vertex
}

func (vertex *GraphVertex) DeleteEdge(edge *GraphEdge) {
	for i, e := range vertex.edges {
		if e == edge {
			vertex.edges = append(vertex.edges[:i], vertex.edges[i+1:]...)
			return
		}
	}
}

func (vertex *GraphVertex) GetNeighbors() []*GraphVertex {
	neighbors := make([]*GraphVertex, 0)
	for _, edge := range vertex.edges {
		if edge.startVertex == vertex {
			neighbors = append(neighbors, edge.endVertex)
		} else {
			neighbors = append(neighbors, edge.startVertex)
		}
	}
	return neighbors
}

func (vertex *GraphVertex) GetEdges() []*GraphEdge {
	return vertex.edges
}

func (vertex *GraphVertex) GetDegree() int {
	return len(vertex.edges)
}

func (vertex *GraphVertex) HasEdge(requiredEdge *GraphEdge) bool {
	for _, edge := range vertex.edges {
		if edge == requiredEdge {
			return true
		}
	}
	return false
}

func (vertex *GraphVertex) HasNeighbor(neighbor *GraphVertex) bool {
	for _, edge := range vertex.edges {
		if edge.startVertex == neighbor || edge.endVertex == neighbor {
			return true
		}
	}
	return false
}

func (vertex *GraphVertex) FindEdge(neighbor *GraphVertex) *GraphEdge {
	for _, edge := range vertex.edges {
		if edge.startVertex == neighbor || edge.endVertex == neighbor {
			return edge
		}
	}
	return nil
}

func (vertex *GraphVertex) GetKey() string {
	return fmt.Sprintf("%v", vertex.value)
}

func (vertex *GraphVertex) DeleteAllEdges() *GraphVertex {
	for _, edge := range vertex.edges {
		edge.startVertex.DeleteEdge(edge)
		edge.endVertex.DeleteEdge(edge)
	}
	vertex.edges = nil
	return vertex
}

type Graph struct {
	vertices    map[string]*GraphVertex
	edges       map[string]*GraphEdge
	isDirected  bool
}

func NewGraph(isDirected bool) *Graph {
	return &Graph{
		vertices:   make(map[string]*GraphVertex),
		edges:      make(map[string]*GraphEdge),
		isDirected: isDirected,
	}
}

func (graph *Graph) AddVertex(newVertex *GraphVertex) *Graph {
	graph.vertices[newVertex.GetKey()] = newVertex
	return graph
}

func (graph *Graph) GetVertexByKey(vertexKey string) *GraphVertex {
	return graph.vertices[vertexKey]
}

func (graph *Graph) GetNeighbors(vertex *GraphVertex) []*GraphVertex {
	return vertex.GetNeighbors()
}

func (graph *Graph) GetAllVertices() []*GraphVertex {
	vertices := make([]*GraphVertex, 0, len(graph.vertices))
	for _, vertex := range graph.vertices {
		vertices = append(vertices, vertex)
	}
	return vertices
}

func (graph *Graph) GetAllEdges() []*GraphEdge {
	edges := make([]*GraphEdge, 0, len(graph.edges))
	for _, edge := range graph.edges {
		edges = append(edges, edge)
	}
	return edges
}

func (graph *Graph) AddEdge(edge *GraphEdge) *Graph {
  startVertex := graph.GetVertexByKey(edge.startVertex.GetKey())
  endVertex := graph.GetVertexByKey(edge.endVertex.GetKey())

  if startVertex == nil {
    graph.AddVertex(edge.startVertex)
    startVertex = graph.GetVertexByKey(edge.startVertex.GetKey())
  }

  if endVertex == nil {
    graph.AddVertex(edge.endVertex)
    endVertex = graph.GetVertexByKey(edge.endVertex.GetKey())
  }

  if existingEdge := graph.edges[edge.GetKey()]; existingEdge != nil {
    panic("Edge has already been added before")
  } else {
    graph.edges[edge.GetKey()] = edge
  }

  if graph.isDirected {
    startVertex.AddEdge(edge)
  } else {
    startVertex.AddEdge(edge)
    endVertex.AddEdge(edge)
  }

  return graph
}

func (graph *Graph) DeleteEdge(edge *GraphEdge) *Graph {
  if existingEdge := graph.edges[edge.GetKey()]; existingEdge != nil {
    delete(graph.edges, edge.GetKey())
  } else {
    panic("Edge not found in graph")
  }

  startVertex := graph.GetVertexByKey(edge.startVertex.GetKey())
  endVertex := graph.GetVertexByKey(edge.endVertex.GetKey())

  startVertex.DeleteEdge(edge)
  endVertex.DeleteEdge(edge)

  return graph
}

func (graph *Graph) FindEdge(startVertex, endVertex *GraphVertex) *GraphEdge {
  vertex := graph.GetVertexByKey(startVertex.GetKey())

  if vertex == nil {
    return nil
  }

  return vertex.FindEdge(endVertex)
}

func (graph *Graph) GetWeight() int {
  totalWeight := 0
  for _, graphEdge := range graph.GetAllEdges() {
    totalWeight += graphEdge.weight
  }
  return totalWeight
}

func (graph *Graph) Reverse() *Graph {
  for _, graphEdge := range graph.GetAllEdges() {
    graph.DeleteEdge(graphEdge)
    graphEdge.Reverse()
    graph.AddEdge(graphEdge)
  }
  return graph
}

func (graph *Graph) GetVerticesIndices() map[string]int {
  verticesIndices := make(map[string]int)
  allVertices := graph.GetAllVertices()

  for index, vertex := range allVertices {
    verticesIndices[vertex.GetKey()] = index
  }

  return verticesIndices
}

func (graph *Graph) GetAdjacencyMatrix() [][]int {
  vertices := graph.GetAllVertices()
  verticesIndices := graph.GetVerticesIndices()

  adjacencyMatrix := make([][]int, len(vertices))
  for i := range adjacencyMatrix {
    adjacencyMatrix[i] = make([]int, len(vertices))
    for j := range adjacencyMatrix[i] {
      adjacencyMatrix[i][j] = int(^uint(0) >> 1)
    }
  }

  for vertexIndex, vertex := range vertices {
    for _, neighbor := range vertex.GetNeighbors() {
      neighborIndex := verticesIndices[neighbor.GetKey()]
      adjacencyMatrix[vertexIndex][neighborIndex] = graph.FindEdge(vertex, neighbor).weight
    }
  }

  return adjacencyMatrix
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class GraphEdge {

  private final GraphVertex startVertex;
  private final GraphVertex endVertex;
  private final int weight;

  public GraphEdge(GraphVertex startVertex, GraphVertex endVertex, int weight) {
    this.startVertex = startVertex;
    this.endVertex = endVertex;
    this.weight = weight;
  }

  public String getKey() {
    String startVertexKey = startVertex.getKey();
    String endVertexKey = endVertex.getKey();
    return startVertexKey + "_" + endVertexKey;
  }

  public GraphEdge reverse() {
    GraphVertex tmp = startVertex;
    startVertex = endVertex;
    endVertex = tmp;
    return this;
  }

  public String toString() {
    return getKey();
  }
}

class GraphVertex {

  private final Object value;
  private final List<GraphEdge> edges;

  public GraphVertex(Object value) {
    if (value == null) {
      throw new IllegalArgumentException("Graph vertex must have a value");
    }

    this.value = value;
    this.edges = new ArrayList<>();
  }

  public GraphVertex addEdge(GraphEdge edge) {
    edges.add(edge);
    return this;
  }

  public void deleteEdge(GraphEdge edge) {
    edges.remove(edge);
  }

  public List<GraphVertex> getNeighbors() {
    List<GraphVertex> neighbors = new ArrayList<>();
    for (GraphEdge edge : edges) {
      neighbors.add(edge.startVertex == this ? edge.endVertex : edge.startVertex);
    }
    return neighbors;
  }

  public List<GraphEdge> getEdges() {
    List<GraphEdge> result = new ArrayList<>();
    for (GraphEdge edge : edges) {
      result.add(edge);
    }
    return result;
  }

  public int getDegree() {
    return edges.size();
  }

  public boolean hasEdge(GraphEdge requiredEdge) {
    return edges.contains(requiredEdge);
  }

  public boolean hasNeighbor(GraphVertex vertex) {
    for (GraphEdge edge : edges) {
      if (edge.startVertex == vertex || edge.endVertex == vertex) {
        return true;
      }
    }
    return false;
  }

  public GraphEdge findEdge(GraphVertex vertex) {
    for (GraphEdge edge : edges) {
      if (edge.startVertex == vertex || edge.endVertex == vertex) {
        return edge;
      }
    }
    return null;
  }

  public Object getKey() {
    return value;
  }

  public GraphVertex deleteAllEdges() {
    edges.clear();
    return this;
  }
}

class Graph {

  private final Map<Object, GraphVertex> vertices;
  private final Map<String, GraphEdge> edges;
  private final boolean isDirected;

  public Graph(boolean isDirected) {
    this.vertices = new HashMap<>();
    this.edges = new HashMap<>();
    this.isDirected = isDirected;
  }

  public Graph addVertex(GraphVertex newVertex) {
    vertices.put(newVertex.getKey(), newVertex);
    return this;
  }

  public GraphVertex getVertexByKey(Object vertexKey) {
    return vertices.get(vertexKey);
  }

  public List<GraphVertex> getNeighbors(GraphVertex vertex) {
    return vertex.getNeighbors();
  }

  public List<GraphVertex> getAllVertices() {
    return new ArrayList<>(vertices.values());
  }

  public List<GraphEdge> getAllEdges() {
    return new ArrayList<>(edges.values());
  }

  public Graph addEdge(GraphEdge edge) {
    GraphVertex startVertex = getVertexByKey(edge.startVertex.getKey());
    GraphVertex endVertex = getVertexByKey(edge.endVertex.getKey());

    if (startVertex == null) {
      addVertex(edge.startVertex);
      startVertex = getVertexByKey(edge.startVertex.getKey());
    }

    if (endVertex == null) {
      addVertex(edge.endVertex);
      endVertex = getVertexByKey(edge.endVertex.getKey());
    }

    if (edges.containsKey(edge.getKey())) {
      throw new IllegalStateException("Edge has already been added before");
    } else {
      edges.put(edge.getKey(), edge);
    }

    if (isDirected) {
      startVertex.addEdge(edge);
    } else {
      startVertex.addEdge(edge);
      endVertex.addEdge(edge);
    }

    return this;
  }

  public Graph deleteEdge(GraphEdge edge) {
    if (edges.containsKey(edge.getKey())) {
      edges.remove(edge.getKey());
    } else {
      throw new IllegalStateException("Edge not found in graph");
    }

    GraphVertex startVertex = getVertexByKey(edge.startVertex.getKey());
    GraphVertex endVertex = getVertexByKey(edge.endVertex.getKey());

    startVertex.deleteEdge(edge);
    endVertex.deleteEdge(edge);

    return this;
  }

  public GraphEdge findEdge(GraphVertex startVertex, GraphVertex endVertex) {
    GraphVertex vertex = getVertexByKey(startVertex.getKey());

    if (vertex == null) {
      return null;
    }

    return vertex.findEdge(endVertex);
  }

  public int getWeight() {
    int totalWeight = 0;
    for (GraphEdge graphEdge : getAllEdges()) {
      totalWeight += graphEdge.weight;
    }
    return totalWeight;
  }

  public Graph reverse() {
    for (GraphEdge graphEdge : getAllEdges()) {
      deleteEdge(graphEdge);
      graphEdge.reverse();
      addEdge(graphEdge);
    }

    return this;
  }

  public Map<Object, Integer> getVerticesIndices() {
    Map<Object, Integer> verticesIndices = new HashMap<>();
    List<GraphVertex> allVertices = getAllVertices();

    for (int index = 0; index < allVertices.size(); index++) {
      verticesIndices.put(allVertices.get(index).getKey(), index);
    }

    return verticesIndices;
  }

  public int[][] getAdjacencyMatrix() {
    List<GraphVertex> vertices = getAllVertices();
    Map<Object, Integer> verticesIndices = getVerticesIndices();

    int[][] adjacencyMatrix = new int[vertices.size()][vertices.size()];

    for (int i = 0; i < vertices.size(); i++) {
      for (int j = 0; j < vertices.size(); j++) {
        adjacencyMatrix[i][j] = Integer.MAX_VALUE;
      }
    }

    for (int vertexIndex = 0; vertexIndex < vertices.size(); vertexIndex++) {
      for (GraphVertex neighbor : vertices.get(vertexIndex).getNeighbors()) {
        int neighborIndex = verticesIndices.get(neighbor.getKey());
        GraphEdge edge = findEdge(vertices.get(vertexIndex), neighbor);
        adjacencyMatrix[vertexIndex][neighborIndex] = (edge != null) ? edge.weight : Integer.MAX_VALUE;
      }
    }

    return adjacencyMatrix;
  }
}

import java.util.*

class GraphEdge(startVertex: GraphVertex, endVertex: GraphVertex, weight: Int = 0) {
    var startVertex: GraphVertex = startVertex
    var endVertex: GraphVertex = endVertex
    var weight: Int = weight

    fun getKey(): String {
        val startVertexKey = startVertex.getKey()
        val endVertexKey = endVertex.getKey()
        return "${startVertexKey}_${endVertexKey}"
    }

    fun reverse(): GraphEdge {
        val tmp = startVertex
        startVertex = endVertex
        endVertex = tmp
        return this
    }
}

class GraphVertex(value: Any) {
    var value: Any = value
        private set

    init {
        if (value == null) {
            throw IllegalArgumentException("Graph vertex must have a value")
        }
    }

    var edges: MutableList<GraphEdge> = mutableListOf()

    fun addEdge(edge: GraphEdge): GraphVertex {
        edges.add(edge)
        return this
    }

    fun deleteEdge(edge: GraphEdge) {
        edges.remove(edge)
    }

    fun getNeighbors(): List<GraphVertex> {
        val neighborsConverter: (GraphEdge) -> GraphVertex = { node ->
            if (node.startVertex == this) node.endVertex else node.startVertex
        }
        return edges.map(neighborsConverter)
    }

    fun getEdges(): List<GraphEdge> {
        return edges.map { it }
    }

    fun getDegree(): Int {
        return edges.size
    }

    fun hasEdge(requiredEdge: GraphEdge): Boolean {
        return edges.any { it == requiredEdge }
    }

    fun hasNeighbor(vertex: GraphVertex): Boolean {
        return edges.any { it.startVertex == vertex || it.endVertex == vertex }
    }

    fun findEdge(vertex: GraphVertex): GraphEdge? {
        return edges.firstOrNull { it.startVertex == vertex || it.endVertex == vertex }
    }

    fun getKey(): String {
        return value.toString()
    }

    fun deleteAllEdges(): GraphVertex {
        edges.forEach { deleteEdge(it) }
        return this
    }
}

class Graph(isDirected: Boolean = false) {
    var vertices: MutableMap<String, GraphVertex> = mutableMapOf()
    var edges: MutableMap<String, GraphEdge> = mutableMapOf()
    var isDirected: Boolean = isDirected

    fun addVertex(newVertex: GraphVertex): Graph {
        vertices[newVertex.getKey()] = newVertex
        return this
    }

    fun getVertexByKey(vertexKey: String): GraphVertex? {
        return vertices[vertexKey]
    }

    fun getNeighbors(vertex: GraphVertex): List<GraphVertex> {
        return vertex.getNeighbors()
    }

    fun getAllVertices(): List<GraphVertex> {
        return ArrayList(vertices.values)
    }

    fun getAllEdges(): List<GraphEdge> {
        return ArrayList(edges.values)
    }

    fun addEdge(edge: GraphEdge): Graph {
        var startVertex = getVertexByKey(edge.startVertex.getKey())
        var endVertex = getVertexByKey(edge.endVertex.getKey())

        if (startVertex == null) {
            addVertex(edge.startVertex)
            startVertex = getVertexByKey(edge.startVertex.getKey())
        }

        if (endVertex == null) {
            addVertex(edge.endVertex)
            endVertex = getVertexByKey(edge.endVertex.getKey())
        }

        if (edges.containsKey(edge.getKey())) {
            throw Error("Edge has already been added before")
        } else {
            edges[edge.getKey()] = edge
        }

        if (isDirected) {
            startVertex!!.addEdge(edge)
        } else {
            startVertex!!.addEdge(edge)
            endVertex!!.addEdge(edge)
        }

        return this
    }

    fun deleteEdge(edge: GraphEdge) {
        if (edges.containsKey(edge.getKey())) {
            edges.remove(edge.getKey())
        } else {
            throw Error("Edge not found in graph")
        }

        val startVertex = getVertexByKey(edge.startVertex.getKey())
        val endVertex = getVertexByKey(edge.endVertex.getKey())

        startVertex?.deleteEdge(edge)
        endVertex?.deleteEdge(edge)
    }

    fun findEdge(startVertex: GraphVertex, endVertex: GraphVertex): GraphEdge? {
        val vertex = getVertexByKey(startVertex.getKey())

        return if (vertex != null) {
            vertex.findEdge(endVertex)
        } else {
            null
        }
    }

    fun getWeight(): Int {
        return getAllEdges().fold(0) { weight, graphEdge -> weight + graphEdge.weight }
    }

    fun reverse(): Graph {
        getAllEdges().forEach { edge ->
            deleteEdge(edge)
            edge.reverse()
            addEdge(edge)
        }

        return this
    }

    fun getVerticesIndices(): Map<String, Int> {
        val verticesIndices = mutableMapOf<String, Int>()
        getAllVertices().forEachIndexed { index, vertex -> verticesIndices[vertex.getKey()] = index }
        return verticesIndices
    }

    fun getAdjacencyMatrix(): Array<IntArray> {
        val vertices = getAllVertices()
        val verticesIndices = getVerticesIndices()

        val adjacencyMatrix = Array(vertices.size) { IntArray(vertices.size) { Int.MAX_VALUE } }

        vertices.forEachIndexed { vertexIndex, vertex ->
            vertex.getNeighbors().forEach { neighbor ->
                val neighborIndex = verticesIndices[neighbor.getKey()]!!
                adjacencyMatrix[vertexIndex][neighborIndex] = findEdge(vertex, neighbor)?.weight ?: 0
            }
        }

        return adjacencyMatrix
    }
}

class GraphEdge(
        var startVertex: GraphVertex,
        var endVertex: GraphVertex,
        var weight: Int = 0
) {
    fun getKey(): String {
        val startVertexKey = startVertex.getKey()
        val endVertexKey = endVertex.getKey()
        return "${startVertexKey}_${endVertexKey}"
    }

    fun reverse(): GraphEdge {
        val tmp = startVertex
        startVertex = endVertex
        endVertex = tmp
        return this
    }

    override fun toString(): String {
        return getKey()
    }
}

class GraphVertex(value: Any) {
    var value: Any = value
        private set

    init {
        if (value == null) {
            throw IllegalArgumentException("Graph vertex must have a value")
        }
    }

    var edges: MutableList<GraphEdge> = mutableListOf()

    fun addEdge(edge: GraphEdge): GraphVertex {
        edges.add(edge)
        return this
    }

    fun deleteEdge(edge: GraphEdge) {
        edges.remove(edge)
    }

    fun getNeighbors(): List<GraphVertex> {
        val neighborsConverter: (GraphEdge) -> GraphVertex = { node ->
            if (node.startVertex == this) node.endVertex else node.startVertex
        }
        return edges.map(neighborsConverter)
    }

    fun getEdges(): List<GraphEdge> {
        return edges.map { it }
    }

    fun getDegree(): Int {
        return edges.size
    }

    fun hasEdge(requiredEdge: GraphEdge): Boolean {
        return edges.any { it == requiredEdge }
    }

    fun hasNeighbor(vertex: GraphVertex): Boolean {
        return edges.any { it.startVertex == vertex || it.endVertex == vertex }
    }

    fun findEdge(vertex: GraphVertex): GraphEdge? {
        return edges.firstOrNull { it.startVertex == vertex || it.endVertex == vertex }
    }

    fun getKey(): String {
        return value.toString()
    }

    fun deleteAllEdges(): GraphVertex {
        edges.forEach { deleteEdge(it) }
        return this
    }

    fun toString(callback: ((Any) -> String)? = null): String {
        return callback?.invoke(value) ?: value.toString()
    }
}

class Graph(isDirected: Boolean = false) {
    var vertices: MutableMap<String, GraphVertex> = mutableMapOf()
    var edges: MutableMap<String, GraphEdge> = mutableMapOf()
    var isDirected: Boolean = isDirected

    fun addVertex(newVertex: GraphVertex): Graph {
        vertices[newVertex.getKey()] = newVertex
        return this
    }

    fun getVertexByKey(vertexKey: String): GraphVertex? {
        return vertices[vertexKey]
    }

    fun getNeighbors(vertex: GraphVertex): List<GraphVertex> {
        return vertex.getNeighbors()
    }

    fun getAllVertices(): List<GraphVertex> {
        return ArrayList(vertices.values)
    }

    fun getAllEdges(): List<GraphEdge> {
        return ArrayList(edges.values)
    }

    fun addEdge(edge: GraphEdge): Graph {
        var startVertex = getVertexByKey(edge.startVertex.getKey())
        var endVertex = getVertexByKey(edge.endVertex.getKey())

        if (startVertex == null) {
            addVertex(edge.startVertex)
            startVertex = getVertexByKey(edge.startVertex.getKey())
        }

        if (endVertex == null) {
            addVertex(edge.endVertex)
            endVertex = getVertexByKey(edge.endVertex.getKey())
        }

        if (edges.containsKey(edge.getKey())) {
            throw Error("Edge has already been added before")
        } else {
            edges[edge.getKey()] = edge
        }

        if (isDirected) {
            startVertex!!.addEdge(edge)
        } else {
            startVertex!!.addEdge(edge)
            endVertex!!.addEdge(edge)
        }

        return this
    }

    fun deleteEdge(edge: GraphEdge) {
        if (edges.containsKey(edge.getKey())) {
            edges.remove(edge.getKey())
        } else {
            throw Error("Edge not found in graph")
        }

        val startVertex = getVertexByKey(edge.startVertex.getKey())
        val endVertex = getVertexByKey(edge.endVertex.getKey())

        startVertex?.deleteEdge(edge)
        endVertex?.deleteEdge(edge)
    }

    fun findEdge(startVertex: GraphVertex, endVertex: GraphVertex): GraphEdge? {
        val vertex = getVertexByKey(startVertex.getKey())

        return if (vertex != null) {
            vertex.findEdge(endVertex)
        } else {
            null
        }
    }

    fun getWeight(): Int {
        return getAllEdges().fold(0) { weight, graphEdge -> weight + graphEdge.weight }
    }

    fun reverse(): Graph {
        getAllEdges().forEach { edge ->
            deleteEdge(edge)
            edge.reverse()
            addEdge(edge)
        }

        return this
    }

    fun getVerticesIndices(): Map<String, Int> {
        val verticesIndices = mutableMapOf<String, Int>()
        getAllVertices().forEachIndexed { index, vertex -> verticesIndices[vertex.getKey()] = index }
        return verticesIndices
    }

    fun getAdjacencyMatrix(): Array<IntArray> {
        val vertices = getAllVertices()
        val verticesIndices = getVerticesIndices()

        val adjacencyMatrix = Array(vertices.size) { IntArray(vertices.size) { Int.MAX_VALUE } }

        vertices.forEachIndexed { vertexIndex, vertex ->
            vertex.getNeighbors().forEach { neighbor ->
                val neighborIndex = verticesIndices[neighbor.getKey()]!!
                adjacencyMatrix[vertexIndex][neighborIndex] = findEdge(vertex, neighbor)?.weight ?: 0
            }
        }

        return adjacencyMatrix
    }

    override fun toString(): String {
        return vertices.keys.toString()
    }
}

class GraphEdge:
    def __init__(self, start_vertex, end_vertex, weight=0):
        self.start_vertex = start_vertex
        self.end_vertex = end_vertex
        self.weight = weight

    def get_key(self):
        start_vertex_key = self.start_vertex.get_key()
        end_vertex_key = self.end_vertex.get_key()
        return f"{start_vertex_key}_{end_vertex_key}"

    def reverse(self):
        tmp = self.start_vertex
        self.start_vertex = self.end_vertex
        self.end_vertex = tmp
        return self


class GraphVertex:
    def __init__(self, value):
        if value is None:
            raise ValueError('Graph vertex must have a value')
        self.value = value
        self.edges = LinkedList(lambda edge_a, edge_b: (edge_a.get_key() > edge_b.get_key()) - (edge_a.get_key() < edge_b.get_key()))

    def add_edge(self, edge):
        self.edges.append(edge)
        return self

    def delete_edge(self, edge):
        self.edges.delete(edge)

    def get_neighbors(self):
        edges = self.edges.to_array()

        def neighbors_converter(node):
            return node.value.start_vertex if node.value.start_vertex != self else node.value.end_vertex

        return list(map(neighbors_converter, edges))

    def get_edges(self):
        return list(map(lambda node: node.value, self.edges.to_array()))

    def get_degree(self):
        return len(self.edges.to_array())

    def has_edge(self, required_edge):
        edge_node = self.edges.find(callback=lambda edge: edge == required_edge)
        return edge_node is not None

    def has_neighbor(self, vertex):
        vertex_node = self.edges.find(callback=lambda edge: edge.start_vertex == vertex or edge.end_vertex == vertex)
        return vertex_node is not None

    def find_edge(self, vertex):
        edge_finder = lambda edge: edge.start_vertex == vertex or edge.end_vertex == vertex
        edge_node = self.edges.find(callback=edge_finder)
        return edge_node.value if edge_node else None

    def get_key(self):
        return self.value

    def delete_all_edges(self):
        edges = self.get_edges()
        for edge in edges:
            self.delete_edge(edge)
        return self


class Graph:
    def __init__(self, is_directed=False):
        self.vertices = {}
        self.edges = {}
        self.is_directed = is_directed

    def add_vertex(self, new_vertex):
        self.vertices[new_vertex.get_key()] = new_vertex
        return self

    def get_vertex_by_key(self, vertex_key):
        return self.vertices.get(vertex_key)

    def get_neighbors(self, vertex):
        return vertex.get_neighbors()

    def get_all_vertices(self):
        return list(self.vertices.values())

    def get_all_edges(self):
        return list(self.edges.values())

    def add_edge(self, edge):
        start_vertex = self.get_vertex_by_key(edge.start_vertex.get_key())
        end_vertex = self.get_vertex_by_key(edge.end_vertex.get_key())

        if not start_vertex:
            self.add_vertex(edge.start_vertex)
            start_vertex = self.get_vertex_by_key(edge.start_vertex.get_key())

        if not end_vertex:
            self.add_vertex(edge.end_vertex)
            end_vertex = self.get_vertex_by_key(edge.end_vertex.get_key())

        if edge.get_key() in self.edges:
            raise ValueError('Edge has already been added before')
        else:
            self.edges[edge.get_key()] = edge

        if self.is_directed:
            start_vertex.add_edge(edge)
        else:
            start_vertex.add_edge(edge)
            end_vertex.add_edge(edge)

        return self

    def delete_edge(self, edge):
        if edge.get_key() in self.edges:
            del self.edges[edge.get_key()]
        else:
            raise ValueError('Edge not found in graph')

        start_vertex = self.get_vertex_by_key(edge.start_vertex.get_key())
        end_vertex = self.get_vertex_by_key(edge.end_vertex.get_key())

        start_vertex.delete_edge(edge)
        end_vertex.delete_edge(edge)

    def find_edge(self, start_vertex, end_vertex):
        vertex = self.get_vertex_by_key(start_vertex.get_key())

        if not vertex:
            return None

        return vertex.find_edge(end_vertex)

    def get_weight(self):
        return sum([graph_edge.weight for graph_edge in self.get_all_edges()])

    def reverse(self):
        for edge in self.get_all_edges():
            self.delete_edge(edge)
            edge.reverse()
            self.add_edge(edge)

        return self

    def get_vertices_indices(self):
        vertices_indices = {}
        for index, vertex in enumerate(self.get_all_vertices()):
            vertices_indices[vertex.get_key()] = index

        return vertices_indices

    def get_adjacency_matrix(self):
        vertices = self.get_all_vertices()
        vertices_indices = self.get_vertices_indices()

        num_vertices = len(vertices)
        adjacency_matrix = [[float('inf')] * num_vertices for _ in range(num_vertices)]

        for vertex_index, vertex in enumerate(vertices):
            for neighbor in vertex.get_neighbors():
                neighbor_index = vertices_indices[neighbor.get_key()]
                edge = self.find_edge(vertex, neighbor)
                adjacency_matrix[vertex_index][neighbor_index] = edge.weight
        return adjacency_matrix

use std::collections::{HashMap, HashSet};

// Define GraphEdge struct
#[derive(Debug, Clone)]
struct GraphEdge<T> {
    start_vertex: T,
    end_vertex: T,
    weight: i32,
}

impl<T: Eq + std::hash::Hash + Clone> GraphEdge<T> {
    fn get_key(&self) -> String {
        format!("{}_{}", self.start_vertex.get_key(), self.end_vertex.get_key())
    }

    fn reverse(&mut self) {
        std::mem::swap(&mut self.start_vertex, &mut self.end_vertex);
    }
}

// Define GraphVertex struct
#[derive(Debug, Clone)]
struct GraphVertex<T> {
    value: T,
    edges: Vec<GraphEdge<T>>,
}

impl<T: Eq + std::hash::Hash + Clone> GraphVertex<T> {
    fn new(value: T) -> Self {
        Self {
            value,
            edges: Vec::new(),
        }
    }

    fn add_edge(&mut self, edge: GraphEdge<T>) {
        self.edges.push(edge);
    }

    fn delete_edge(&mut self, edge: &GraphEdge<T>) {
        self.edges.retain(|e| e != edge);
    }

    fn get_neighbors(&self) -> Vec<T> {
        self.edges.iter().map(|edge| edge.end_vertex.clone()).collect()
    }

    fn get_edges(&self) -> Vec<GraphEdge<T>> {
        self.edges.clone()
    }

    fn get_degree(&self) -> usize {
        self.edges.len()
    }

    fn has_edge(&self, required_edge: &GraphEdge<T>) -> Option<&GraphEdge<T>> {
        self.edges.iter().find(|edge| edge == required_edge)
    }

    fn has_neighbor(&self, vertex: &GraphVertex<T>) -> Option<&GraphEdge<T>> {
        self.edges.iter().find(|edge| edge.start_vertex == *vertex || edge.end_vertex == *vertex)
    }

    fn find_edge(&self, vertex: &GraphVertex<T>) -> Option<&GraphEdge<T>> {
        self.edges.iter().find(|edge| edge.start_vertex == *vertex || edge.end_vertex == *vertex)
    }

    fn get_key(&self) -> String {
        self.value.get_key()
    }

    fn delete_all_edges(&mut self) {
        self.edges.clear();
    }
}

// Define Graph struct
#[derive(Debug, Clone)]
struct Graph<T> {
    vertices: HashMap<String, GraphVertex<T>>,
    edges: HashMap<String, GraphEdge<T>>,
    is_directed: bool,
}

impl<T: Eq + std::hash::Hash + Clone> Graph<T> {
    fn new(is_directed: bool) -> Self {
        Self {
            vertices: HashMap::new(),
            edges: HashMap::new(),
            is_directed,
        }
    }

    fn add_vertex(&mut self, new_vertex: GraphVertex<T>) -> &mut Self {
        self.vertices.insert(new_vertex.get_key(), new_vertex);
        self
    }

    fn get_vertex_by_key(&self, vertex_key: &str) -> Option<&GraphVertex<T>> {
        self.vertices.get(vertex_key)
    }

    fn get_neighbors(&self, vertex: &GraphVertex<T>) -> Vec<T> {
        vertex.get_neighbors()
    }

    fn get_all_vertices(&self) -> Vec<&GraphVertex<T>> {
        self.vertices.values().collect()
    }

    fn get_all_edges(&self) -> Vec<&GraphEdge<T>> {
        self.edges.values().collect()
    }

    fn add_edge(&mut self, edge: GraphEdge<T>) -> &mut Self {
        let start_vertex_key = edge.start_vertex.get_key();
        let end_vertex_key = edge.end_vertex.get_key();

        if !self.vertices.contains_key(&start_vertex_key) {
            self.add_vertex(edge.start_vertex.clone());
        }

        if !self.vertices.contains_key(&end_vertex_key) {
            self.add_vertex(edge.end_vertex.clone());
        }

        if self.edges.contains_key(&edge.get_key()) {
            panic!("Edge has already been added before");
        } else {
            self.edges.insert(edge.get_key(), edge.clone());
        }

        if self.is_directed {
            if let Some(start_vertex) = self.vertices.get_mut(&start_vertex_key) {
                start_vertex.add_edge(edge);
            }
        } else {
            if let Some(start_vertex) = self.vertices.get_mut(&start_vertex_key) {
                start_vertex.add_edge(edge.clone());
            }

            if let Some(end_vertex) = self.vertices.get_mut(&end_vertex_key) {
                end_vertex.add_edge(edge);
            }
        }

        self
    }

    fn delete_edge(&mut self, edge: &GraphEdge<T>) {
        if self.edges.contains_key(&edge.get_key()) {
            self.edges.remove(&edge.get_key());
        } else {
            panic!("Edge not found in graph");
        }

        if let Some(start_vertex) = self.vertices.get_mut(&edge.start_vertex.get_key()) {
            start_vertex.delete_edge(edge);
        }

        if let Some(end_vertex) = self.vertices.get_mut(&edge.end_vertex.get_key()) {
            end_vertex.delete_edge(edge);
        }
    }

    fn find_edge(&self, start_vertex: &GraphVertex<T>, end_vertex: &GraphVertex<T>) -> Option<&GraphEdge<T>> {
        if let Some(vertex) = self.vertices.get(&start_vertex.get_key()) {
            vertex.find_edge(end_vertex)
        } else {
            None
        }
    }

    fn get_weight(&self) -> i32 {
        self.edges.values().map(|edge| edge.weight).sum()
    }

    fn reverse(&mut self) -> &mut Self {
        for edge in self.edges.values_mut() {
            self.delete_edge(edge);
            edge.reverse();
            self.add_edge(edge.clone());
        }

        self
    }

    fn get_vertices_indices(&self) -> HashMap<String, usize> {
        self.vertices
            .values()
            .enumerate()
            .map(|(index, vertex)| (vertex.get_key(), index))
            .collect()
    }

    fn get_adjacency_matrix(&self) -> Vec<Vec<i32>> {
        let vertices = self.get_all_vertices();
        let vertices_indices = self.get_vertices_indices();

        let mut adjacency_matrix = vec![vec![i32::MAX; vertices.len()]; vertices.len()];

        for (vertex_index, vertex) in vertices.iter().enumerate() {
            for neighbor in vertex.get_neighbors() {
                if let Some(edge) = vertex.find_edge(self.get_vertex_by_key(&neighbor).unwrap()) {
                    let neighbor_index = vertices_indices[&neighbor];
                    adjacency_matrix[vertex_index][neighbor_index] = edge.weight;
                }
            }
        }

        adjacency_matrix
    }
}

class LinkedListNode<T> {
  value: T;
  next: LinkedListNode<T> | null;

  constructor(value: T) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList<T> {
  head: LinkedListNode<T> | null;
  compare: (a: T, b: T) => number;

  constructor(compare: (a: T, b: T) => number) {
    this.head = null;
    this.compare = compare;
  }

  append(value: T): void {
    const newNode = new LinkedListNode(value);

    if (!this.head) {
      this.head = newNode;
      return;
    }

    let current = this.head;
    while (current.next) {
      current = current.next;
    }

    current.next = newNode;
  }

  delete(value: T): void {
    if (!this.head) {
      return;
    }

    if (this.compare(this.head.value, value) === 0) {
      this.head = this.head.next;
      return;
    }

    let current = this.head;
    while (current.next) {
      if (this.compare(current.next.value, value) === 0) {
        current.next = current.next.next;
        return;
      }
      current = current.next;
    }
  }

  toArray(): T[] {
    const result: T[] = [];
    let current = this.head;

    while (current) {
      result.push(current.value);
      current = current.next;
    }

    return result;
  }

  find(params: { callback: (value: T) => boolean }): LinkedListNode<T> | null {
    if (!this.head) {
      return null;
    }

    let current = this.head;
    while (current) {
      if (params.callback(current.value)) {
        return current;
      }
      current = current.next;
    }

    return null;
  }
}

class GraphEdge<T> {
  startVertex: GraphVertex<T>;
  endVertex: GraphVertex<T>;
  weight: number;

  constructor(
    startVertex: GraphVertex<T>,
    endVertex: GraphVertex<T>,
    weight = 0,
  ) {
    this.startVertex = startVertex;
    this.endVertex = endVertex;
    this.weight = weight;
  }

  getKey(): string {
    const startVertexKey = this.startVertex.getKey();
    const endVertexKey = this.endVertex.getKey();
    return `${startVertexKey}_${endVertexKey}`;
  }

  reverse(): this {
    const tmp = this.startVertex;
    this.startVertex = this.endVertex;
    this.endVertex = tmp;
    return this;
  }
}

class GraphVertex<T> {
  value: T;
  edges: LinkedList<GraphEdge<T>>;

  constructor(value: T) {
    if (value === undefined) {
      throw new Error("Graph vertex must have a value");
    }

    const edgeComparator = (edgeA: GraphEdge<T>, edgeB: GraphEdge<T>) => {
      if (edgeA.getKey() === edgeB.getKey()) {
        return 0;
      }

      return edgeA.getKey() < edgeB.getKey() ? -1 : 1;
    };

    this.value = value;
    this.edges = new LinkedList(edgeComparator);
  }

  addEdge(edge: GraphEdge<T>): this {
    this.edges.append(edge);
    return this;
  }

  deleteEdge(edge: GraphEdge<T>): void {
    this.edges.delete(edge);
  }

  getNeighbors(): T[] {
    const edges = this.edges.toArray();

    const neighborsConverter = (node: LinkedListNode<GraphEdge<T>>) => {
      return node.value.startVertex === this
        ? node.value.endVertex
        : node.value.startVertex;
    };

    return edges.map(neighborsConverter);
  }

  getEdges(): GraphEdge<T>[] {
    return this.edges.toArray();
  }

  getDegree(): number {
    return this.edges.toArray().length;
  }

  hasEdge(requiredEdge: GraphEdge<T>): LinkedListNode<GraphEdge<T>> | null {
    return this.edges.find({
      callback: (edge) => edge === requiredEdge,
    });
  }

  hasNeighbor(vertex: T): LinkedListNode<GraphEdge<T>> | null {
    return this.edges.find({
      callback: (edge) =>
        edge.startVertex === vertex || edge.endVertex === vertex,
    });
  }

  findEdge(vertex: T): GraphEdge<T> | null {
    const edgeFinder = (edge: GraphEdge<T>) => {
      return edge.startVertex === vertex || edge.endVertex === vertex;
    };

    const edgeNode = this.edges.find({ callback: edgeFinder });

    return edgeNode ? edgeNode.value : null;
  }

  getKey(): string {
    return String(this.value);
  }

  deleteAllEdges(): this {
    this.getEdges().forEach((edge) => this.deleteEdge(edge));
    return this;
  }
}

class Graph<T> {
  vertices: { [key: string]: GraphVertex<T> };
  edges: { [key: string]: GraphEdge<T> };
  isDirected: boolean;

  constructor(isDirected = false) {
    this.vertices = {};
    this.edges = {};
    this.isDirected = isDirected;
  }

  addVertex(newVertex: GraphVertex<T>): this {
    this.vertices[newVertex.getKey()] = newVertex;
    return this;
  }

  getVertexByKey(vertexKey: string): GraphVertex<T> | undefined {
    return this.vertices[vertexKey];
  }

  getNeighbors(vertex: GraphVertex<T>): T[] {
    return vertex.getNeighbors();
  }

  getAllVertices(): GraphVertex<T>[] {
    return Object.values(this.vertices);
  }

  getAllEdges(): GraphEdge<T>[] {
    return Object.values(this.edges);
  }

  addEdge(edge: GraphEdge<T>): this {
    let startVertex = this.getVertexByKey(edge.startVertex.getKey());
    let endVertex = this.getVertexByKey(edge.endVertex.getKey());

    if (!startVertex) {
      this.addVertex(edge.startVertex);
      startVertex = this.getVertexByKey(edge.startVertex.getKey())!;
    }

    if (!endVertex) {
      this.addVertex(edge.endVertex);
      endVertex = this.getVertexByKey(edge.endVertex.getKey())!;
    }

    if (this.edges[edge.getKey()]) {
      throw new Error("Edge has already been added before");
    } else {
      this.edges[edge.getKey()] = edge;
    }

    if (this.isDirected) {
      startVertex.addEdge(edge);
    } else {
      startVertex.addEdge(edge);
      endVertex.addEdge(edge);
    }

    return this;
  }

  deleteEdge(edge: GraphEdge<T>): void {
    if (this.edges[edge.getKey()]) {
      delete this.edges[edge.getKey()];
    } else {
      throw new Error("Edge not found in graph");
    }

    const startVertex = this.getVertexByKey(edge.startVertex.getKey());
    const endVertex = this.getVertexByKey(edge.endVertex.getKey());

    startVertex?.deleteEdge(edge);
    endVertex?.deleteEdge(edge);
  }

  findEdge(
    startVertex: GraphVertex<T>,
    endVertex: GraphVertex<T>,
  ): GraphEdge<T> | null {
    const vertex = this.getVertexByKey(startVertex.getKey());

    if (!vertex) {
      return null;
    }

    return vertex.findEdge(endVertex.getKey());
  }

  getWeight(): number {
    return this.getAllEdges().reduce((weight, graphEdge) => {
      return weight + graphEdge.weight;
    }, 0);
  }

  reverse(): this {
    this.getAllEdges().forEach((edge) => {
      this.deleteEdge(edge);
      edge.reverse();
      this.addEdge(edge);
    });

    return this;
  }

  getVerticesIndices(): { [key: string]: number } {
    const verticesIndices: { [key: string]: number } = {};
    this.getAllVertices().forEach((vertex, index) => {
      verticesIndices[vertex.getKey()] = index;
    });

    return verticesIndices;
  }

  getAdjacencyMatrix(): number[][] {
    const vertices = this.getAllVertices();
    const verticesIndices = this.getVerticesIndices();

    const adjacencyMatrix: number[][] = Array(vertices.length)
      .fill(null)
      .map(() => {
        return Array(vertices.length).fill(Infinity);
      });

    vertices.forEach((vertex, vertexIndex) => {
      vertex.getNeighbors().forEach((neighbor) => {
        const neighborIndex = verticesIndices[neighbor.getKey()];
        const edge = this.findEdge(
          vertex,
          this.getVertexByKey(neighbor.getKey())!,
        );
        adjacencyMatrix[vertexIndex][neighborIndex] = edge.weight;
      });
    });

    return adjacencyMatrix;
  }
}

Definition​

Practice​

Definition

Practice