Class Graph
Graph class.

Implements ContainerConcept
All Subcl's AlignmentGraph, Automaton, DirectedGraph, HmmGraph, Tree, UndirectedGraph, WordGraph
All Impl'd AssignableConcept, ContainerConcept, DestructibleConcept
Defined in <seqan/graph_types.h>
Signature template <[typename TSpec]> class Graph;

Template Parameters

TSpec The specializing type. Default: Directed<>.

Member Function Overview

Member Functions Inherited From AssignableConcept

Interface Function Overview

Interface Functions Inherited From AssignableConcept

Interface Functions Inherited From ContainerConcept

Interface Metafunction Overview

Interface Metafunctions Inherited From ContainerConcept

Detailed Description

Examples

This is an example for Dijktra's algorithm on a directed graph with an external property map. The property map labels the edges with weights. The xample only outputs distances, not th edetails of the paths.

// A tutorial about the dijkstra's algorithm, once using an external map and once using an internal map.
#include <iostream>
#include <seqan/graph_algorithms.h>

using namespace seqan2;

int main()
{
    typedef Graph<Directed<> > TGraph;

    // Graph creation: 10 directed edges (0,1), (0,3), ...
    TGraph g;
    Size<TGraph>::Type numEdges = 10;
    VertexDescriptor<TGraph>::Type edges[] = {0, 1, 0, 3, 1, 2, 1, 3, 2, 4, 3, 1, 3, 2, 3, 4, 4, 0, 4, 2};
    addEdges(g, edges, numEdges);

    // One external property map: Weight map
    unsigned int weights[] =    {10, 5, 1, 2, 4, 3, 9, 2, 7, 6};
    String<unsigned int> weightMap;
    assignEdgeMap(weightMap, g, weights);

    // Out-parameters: Predecessor and distance map
    String<unsigned int> predMap;
    String<unsigned int> distMap;

    // Dijkstra from vertex 0 (single source shortest paths)
    dijkstra(predMap, distMap, g, 0, weightMap);

    // Output distances of shortest paths
    Iterator<TGraph, VertexIterator>::Type it(g);
    while (!atEnd(it))
    {
        std::cout << "Distance from 0 to " << getValue(it) << ": ";
        std::cout << getProperty(distMap, getValue(it)) << std::endl;
        goNext(it);
    }
    return 0;
}
Demo: demos/dox/graph_types/graph_algo_dijkstra.cpp

The output of the distances is as follows:

Distance from 0 to 0: 0
Distance from 0 to 1: 8
Distance from 0 to 2: 9
Distance from 0 to 3: 5
Distance from 0 to 4: 7

Interface Functions Detail

TEdgeDescriptor addEdge(g, source, target, label[, cargo]); TEdgeDescriptor addEdge(g, source, target, cargo);

Adds a new edge to a graph, either with or without cargo.

Parameters

g The Graph to add the edge to.
source Descriptor of the source vertex.
source Descriptor of the target vertex.
label Label of the edge, of alphabet type of the Automaton.
cargo Cargo object for the edge.

Returns

TEdgeDescriptor Descriptor of the added edge.

Remarks

For Automaton objects, a label is required but the label can only be given for Automatons.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

void addEdges(graph, edges, size);

Shortcut to add multiple edges at once; vertices are created implicitely.

Parameters

graph The Graph to add the edges to.
edges An array of vertex descriptions.
size Size of the array. Must be a even.

It is assumed that the edges in edges are stored as an array of vertex ids: source1, target1, source2, target2, .... For a tree, the root must be the first vertex in this array and the enumeration is parent, child, parent, child.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

TVertexDescriptor addVertex(g);

Add a vertex to a graph.

Parameters

g The Graph to add a vertex to.

Returns

TVertexDescriptor The descriptor of the added vertex.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

void assignEdgeMap(g, pm, prop);

Initializes a vertex map with values of an array.

Parameters

pm An property map.
prop An array with properties that are to be assigned to the items in the property map.
g A Graph.

For every edge id there must be an entry in the array.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

void assignVertexMap(g, pm, prop);

Initializes a vertex map with values of an array.

Parameters

pm A property map.
g A Graph.
prop An array with properties that are to be assigned to the items in the property map.

For every vertex descriptor there must be an entry in the array.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

void clear(g);

Remove all edges and vertices from a graph.

Parameters

g The graph to remove edges and vertices from.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

void clearEdges(g);

Removes all edges from a graph.

Parameters

g The graph to remove the edges from.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

void clearVertices(g);

Removes all vertices from a graph.

Parameters

g The graph to remove the vertices from.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

TSize degree(g, v);

Return degree of a vertex.

Parameters

g The Graph to query.
v The descriptor of the vertex to query for its degree.

Returns

TSize The number of edges adjacent to vertex v.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

bool empty(g);

Returns whether there are no vertices and edges in the graph or not.

Parameters

g The Graph to query.

Returns

bool true if g is empty and false if not.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

TEdgeDescriptor findEdge(g, v, c); TEdgeDescriptor findEdge(g, v, w);

Finds an edge.

Parameters

g The Graph to query.
v The descriptor of the source vertex.
c An edge label.
w The descriptor of the target descriptor.

Returns

TEdgeDescriptor Edge descriptor of the found edge. 0 if not present. NB: in automatons, there is always a valid edge descriptor but the target may be nil.

Remarks

In an automaton, an edge is uniquely defined by a vertex and a label. In all other graphs, two adjacent vertices uniquely define an edge. If tehre are multiple edges between two vertices then the behaviour is undefined.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

void getAdjacencyMatrix(g, matrix);

Build an adjacency matrix representation of the graph.

Parameters

g The Graph to compute ajacency matrix for.
matrix A String filled with n * n elements of IntegerConcept where matrix[i + n * j] gives the edge count between vertices i and j.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

T getNil(ptr); T getNil<T>();

Returning a "nil" value for graphs.

Parameters

ptr Pointer to T to select the type.

Returns

T Pseudo nil value for type T.

Usefulf or various graph algorithms, e.g. missing predecessors or vertices that have not been visited.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

void getVertexAdjacencyVector(vectIn, vectOut, g, vertex);

Build an adjacency vector representation of a vertex of the graph.

Parameters

vectIn A String filled with n elements of IntegerConcept where vectIn[i] gives the id number of the source vertex
vectOut A String filled with n elements of IntegerConcept where vectOut[i] gives the id number of the target vertex
g The Graph under exploration.
vertex The vertex to compute ajacency vector for.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

TSize inDegree(g, v);

Return in degree of a vertex.

Parameters

g The Graph to query.
v The descriptor of the vertex to query for its in degree.

Returns

TSize The number of in edges to vertex v.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

TSize numEdges(g);

Returns the number of edges in a graph.

Parameters

g The Graph to query for its number of edges.

Returns

TSize The number of edges. TSize is the size type of g.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

TSize numVertices(g);

Returns the number of vertices in a graph.

Parameters

g The Graph to query for its number of vertices.

Returns

TSize The number of vertices. TSize is the size type of g.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

TSize outDegree(g, v);

Return out degree of a vertex.

Parameters

g The Graph to query.
v The descriptor of the vertex to query for its out degree.

Returns

TSize The number of out edges from vertex v.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

void removeEdge(g, source, target[, label]); void removeEdge(g, e);

Removes an edge from the graph. For automatons, a label is required.

Parameters

g The Graph to remove the edge from.
source Descriptor of the source vertex.
target Descriptor of the target vertex.
e Descriptor of the edge to remove.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

void removeOutEdges(g, v);

Removes the incoming edges of a given vertex.

Parameters

g The Graph to remove the edges from.
v The descriptor of the vertex to remove incoming edges from.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

void removeOutEdges(g, v);

Removes the outgoing edges of a given vertex.

Parameters

g The Graph to remove the edges from.
v The descriptor of the vertex to remove outgoing edges from.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

void removeVertex(g, v);

Remove a vertex from a Graph.

Parameters

g The Graph to remove the vertex from.
v The descriptor of the vertex to remove.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

void resizeEdgeMap(pm, g[, prototype]);;

Initializes an edge map.

Parameters

pm A property map.
g A Graph.
prototype An optional prototype that is used for initializing the property map.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

void resizeVertexMap(pm, g[, prototype]);

Initializes a vertex map.

Parameters

pm A property map.
g A Graph.
prototype An optional prototype that is used for initializing the property map.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

TVertexDescriptor sourceVertex(g, e); TVertexDescriptor sourceVertex(it);

Returns the source vertex of an edge.

Parameters

g The Graph the edge is in.
e The descriptor of the edge to remove.
it An edge iterator.

Remarks

In a tree, the source vertex is always the child. In an undirected graph, the larger vertex descriptor of the two end points i the source. For an out-edge iterator, the source is always the OutEdgeIterator has been initialized with.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

TVertexDescriptor targetVertex(g, e); TVertexDescriptor targetVertex(it);

Returns the target vertex of an edge.

Parameters

g The Graph the edge is in.
e The descriptor of the edge to remove.
it An edge iterator.

Remarks

In a tree, the target vertex is always the child. In an undirected graph, the larger vertex descriptor of the two end points i the target. For an out-edge iterator, the target is always the OutEdgeIterator has not been initialized with.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

void transpose(source, dest); void transpose(g);

Transposes a graph, either in place or from source to dest.

Parameters

source The input Graph.
dest The output Graph.
g The Graph to transpose.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

void writeRecords(file, graph[, nodeMap[, edgeMap]], tag);

Write out a graph record.

Parameters

file The StreamConcept to write to.
graph The Graph to write out.
nodeMap Vertex labels for each vertex; optional.
edgeMap Edge label for each edge; optional.
tag Format tag to use for writing. Types: DotDrawing.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

Interface Metafunctions Detail

Cargo<T>::Type;

Type for the graph's cargo.

Template Parameters

T The Graph type to query.

Returns

Type The resulting cargo type.

EdgeDescriptor<T>::Type;

Type of an object that represents an edge descriptor.

Template Parameters

T The Graph type to query.

Returns

Type The resulting edge descriptor type.

The edge descriptor is a unique handle to a given edge in a graph. It is used in various graph functions, e.g. to remove edges, to assign cargo to an edge or to get the end points of an edge. It is also used to attache properties to edges via property maps.

Examples

EdgeDescriptor<Graph<> >::Type ed;  // eD is an edge descriptor

EdgeIdHandler<T>::Type;

Type of an object that represents an IdManager.

Template Parameters

T The Graph to query.

Returns

Type The IdManager type.

The exact IdManager type depends on the edge stump type. If the edge stump has no ids then the IdManager simply counts edge ids and otherwise it manages a list of free and used ids.

EdgeType<T>::Type;

Edge type of a graph class.

Template Parameters

T The Graph type to query.

Returns

Type The resulting edge stump type that is used in the graph.

Examples

EdgeType<TGraph>::Type e;  // e is an edge in a TGraph

Size<TGraph>::Type;

Size type of the Graph.

Template Parameters

TGraph The graph type to query for its size type.

Returns

Type The size type.

VertexIdHandler<T>::Type;

Type of an object that repreestns an IdManager.

Template Parameters

T The Graph to query.

Returns

Type The IdManager type.