**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Graph (abstract data type)

Summary

In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from the field of graph theory within mathematics.
A graph data structure consists of a finite (and possibly mutable) set of vertices (also called nodes or points), together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges (also called links or lines), and for a directed graph are also known as edges but also sometimes arrows or arcs. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.
A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).
The basic operations provided by a graph data structure G usually include:
tests whether there is an edge from the vertex x to the vertex y;
lists all vertices y such that there is an edge from the vertex x to the vertex y;
adds the vertex x, if it is not there;
removes the vertex x, if it is there;
adds the edge z from the vertex x to the vertex y, if it is not there;
removes the edge from the vertex x to the vertex y, if it is there;
returns the value associated with the vertex x;
sets the value associated with the vertex x to v.
Structures that associate values to the edges usually also provide:
returns the value associated with the edge (x, y);
sets the value associated with the edge (x, y) to v.
Adjacency list
Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices. This data structure allows the storage of additional data on the vertices. Additional data can be stored if edges are also stored as objects, in which case each vertex stores its incident edges and each edge stores its incident vertices.
Adjacency matrix
A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (174)

Related people (41)

Related units (4)

Related concepts (16)

Related courses (21)

Related lectures (78)

Directed graph

In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. In formal terms, a directed graph is an ordered pair where V is a set whose elements are called vertices, nodes, or points; A is a set of ordered pairs of vertices, called arcs, directed edges (sometimes simply edges with the corresponding set named E instead of A), arrows, or directed lines.

Graph database

A graph database (GDB) is a database that uses graph structures for semantic queries with nodes, edges, and properties to represent and store data. A key concept of the system is the graph (or edge or relationship). The graph relates the data items in the store to a collection of nodes and edges, the edges representing the relationships between the nodes. The relationships allow data in the store to be linked together directly and, in many cases, retrieved with one operation.

Adjacency list

In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each unordered list within an adjacency list describes the set of neighbors of a particular vertex in the graph. This is one of several commonly used representations of graphs for use in computer programs. An adjacency list representation for a graph associates each vertex in the graph with the collection of its neighbouring vertices or edges.

EE-626: Graph representations for biology and medicine

Systems of interacting entities, modeled as graphs, are pervasive in biology and medicine. The class will cover advanced topics in signal processing and machine learning on graphs and networks, and wi

ME-427: Networked control systems

This course offers an introduction to control systems using communication networks for interfacing sensors, actuators, controllers, and processes. Challenges due to network non-idealities and opportun

MATH-448: Statistical analysis of network data

A first course in statistical network analysis and applications.

Belief Propagation in Random Graphs

Explores belief propagation in random graphs and Bethe free entropy.

Algorithmes: introductionMOOC: Information, Calcul, Communication: Introduction à la pensée informatique

Covers the basics of algorithms, problem-solving, and efficient resolution methods.

Predicting Reaction Yields with Deep Learning

Explores predicting reaction yields with deep learning models and the importance of high-quality data sets in chemistry.

Wenlong Liao, Qi Liu, Zhe Yang

Reactive power optimization of distribution networks is traditionally addressed by physical model based methods, which often lead to locally optimal solutions and require heavy online inference time consumption. To improve the quality of the solution and r ...

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...

This article proposes an exploration technique for multiagent reinforcement learning (MARL) with graph-based communication among agents. We assume that the individual rewards received by the agents are independent of the actions by the other agents, while ...