In computer science, a graph is an abstract data structure that is meant to implement the graph concept from mathematics.
A graph data structure consists mainly of a finite (and possibly mutable) set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices. As in mathematics, an edge (x,y) is said to point or go from x to y. The nodes 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.).
Contents |
Operations
The basic operations provided by a graph data structure G usually include
adjacent(G, x,y): tests whether there is an edge from node x to node y.neighbors(G, x): lists all nodes y such that there is an edge from x to y.add(G, x,y): adds to G the edge from x to y, if it is not there.delete(G, x,y): removes the edge from x to y, if it is there.get_node_value(G, x): returns the value associated with the node x.set_node_value(G, x, a): sets the value associated with the node x to a.
Structures that associate values to the edges usually provide also
get_edge_value(G, x,y): returns the value associated to the edge (x,y).set_edge_value(G, x,y,v): sets the value associated to the edge (x,y) to v.
Representations
Different data structures for the representation of graphs are used in practice, e.g.:
- Adjacency list - An adjacency list is implemented as an array with one linked list for each source node, containing the destination nodes of the edges that leave each node.
- Incidence list - A variant of the adjacency list that allows for the description of the edges at the cost of additional edges.
- Adjacency matrix - A two-dimensional Boolean matrix, in which the rows and columns represent source and destination vertices and entries in the array indicate whether an edge exists between the vertices.
- Incidence matrix - A two-dimensional Boolean matrix, in which the rows represent the vertices and columns represent the edges. The array entries indicate if both are related, i.e. incident.
Adjacency lists are preferred for sparse graphs; otherwise, an adjacency matrix is a good choice.
For graphs with some regularity in the placement of edges, a symbolic graph is a possible choice of representation.
Algorithms
Graph algorithms are a significant field of interest within computer science. Typical higher-level operations associated with graphs are: finding a path between two nodes, like depth-first search and breadth-first search and finding the shortest path from one node to another, like Dijkstra's algorithm. A solution to finding the shortest path from each node to every other node also exists in the form of the Floyd-Warshall algorithm.
A directed graph can be seen as a flow network, where each edge has a capacity and each edge receives a flow. The Ford-Fulkerson algorithm is used to find out the maximum flow from a source to a sink in a graph.
External links
- Algraf Project: Graphical tool to draw graphs, apply several algorithms to them and export to XML
- Boost Graph Library: a powerful C++ graph library
- Graph Data Structures (PDF, 280 KiB)
- Graphviz - Graph Visualization Software (Open Source)
- Java Universal Network/Graph Framework (JUNG)
- Java Graph and algorithm API (Annas)
- NetworkX - a Python Graph package
- Perl graph routines
- Prefuse - Java framework for interactive data visualizations
- QuickGraph: Graph Data Structures And Algorithms for .NET
Categories: Graph theory | Graph data structures | Abstract data types
|
