> LEDA Guide > Graphs and Related Data Types > Graphs

Graphs

The data type graph is the basic data type for representing graphs in LEDA. It can represent directed and undirected graphs G=(V,E), where V is the list of nodes and E is the list of directed, respectively undirected, edges. Nodes and edges are of type item.

The main difference between directed and undirected graphs is the way edges incident to a node are stored. An edge is incident to a node if the node is an end vertex of the edge. Details can be found on the Graph Manual Page.

The data type graph can also represent maps. Maps are the data type of choice for embedded graphs. Embedded graphs can be used to represent drawings of a graph.

Simple example of how to use graph

Strengths

  • universal data type for representing graphs (can represent directed, undirected graphs, maps, and planar maps)
  • very broad interface, i.e., many operations available
  • very convenient to use
  • efficient
  • needs only space O(|V|+|E|)
  • fully dynamic, that is, nodes and edges can be deleted and added during the program

Disadvantages

  • not as efficient (in time and space) as specialized graph data structures for static graphs

Tips

Use graph to represent directed and undirected graphs, and planar maps. Only if you have good reasons use Planar Maps.

See also:

Parameterized Graphs

Planar Maps

Graphs and Related Data Types

How to Associate Information with graphs

Graph Algorithms

GraphWin for visualizing graphs and graph algorithms

Manual Entries:

Manual Page Graphs

LEDA Item Concept



Algorithmic Solutions Software GmbH