Graph (abstract data type) | EPFL Graph Search

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.

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.

About this result

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 (4)

Related people (1)

Related concepts (19)

Related courses (19)

Related lectures (167)

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.

CS-250: Algorithms

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

Graph Representation Learning with Optimal Transport: Analysis and Applications

Effrosyni Simou

In several machine learning settings, the data of interest are well described by graphs. Examples include data pertaining to transportation networks or social networks. Further, biological data, such

EPFL2022

FlowPool: Pooling Graph Representations with Wasserstein Gradient Flows

Effrosyni Simou

In several machine learning tasks for graph structured data, the graphs under consideration may be composed of a varying number of nodes. Therefore, it is necessary to design pooling methods that aggr

2021

Graph Signal Processing

Ntorina Thanou

Over the past few decades we have been experiencing an explosion of information generated by large networks of sensors and other data sources. Much of this data is intrinsically structured, such as tr

EPFL2016

Graph (abstract data type)

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.

Belief Propagation in Random Graphs PHYS-512: Statistical physics of computation

Explores belief propagation in random graphs and Bethe free entropy.

Algorithmes: introduction CS-119(a): Information, Computation, Communication MOOC: 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 PHYS-754: Lecture series on scientific machine learning

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