Graph

A bipartite graph.

class Graph (

A

B

EdgeDataAB = size_t

EdgeDataBA = size_t

) if (

!is(A == B)

) {

alias Opposite(Vertex : A) = B;

alias Opposite(Vertex : B) = A;

alias EdgeData(From : A, To : B) = EdgeDataAB;

alias EdgeData(From : B, To : A) = EdgeDataBA;

eponymoustemplate isVertex(Vertex);

eponymoustemplate isEdge(From, To);

size_t length [@property getter];

bool empty [@property getter];

Data data(Vertex v);

size_t degreeIn(Vertex v);

size_t degreeOut(Vertex v);

void put(Vertex v);

void remove(Vertex v);

void put(A from, B to, EdgeDataAB data);

void put(B from, A to, EdgeDataBA data);

void remove(From from, To to);

auto vertices [@property getter];

struct Edges(From, To);

auto outgoing(Vertex v);

struct Visited(Value);

void traverse(Context ctx, TaskPool pool);

typeof(this) subgraph(const(A[]) rootsA, const(B[]) rootsB);

auto diffVertices(typeof(this) other);

auto diffEdges(typeof(this) other);

auto tarjan [@property getter];

immutable(SCC)[] cycles [@property getter];

}

Members

Aliases

EdgeData alias EdgeData(From : A, To : B) = EdgeDataAB: Uniform way of referencing edge data.
EdgeData alias EdgeData(From : B, To : A) = EdgeDataBA: Undocumented in source.
Opposite alias Opposite(Vertex : A) = B: Find the opposite vertex type of the given vertex type.
Opposite alias Opposite(Vertex : B) = A: Undocumented in source.

Classes

Data class Data: Bookkeeping data associated with each vertex.

Enums

isEdge eponymoustemplate isEdge(From, To): Undocumented in source.
isVertex eponymoustemplate isVertex(Vertex): Undocumented in source.

Functions

data Data data(Vertex v): Returns data associated with the given vertex.
degreeIn size_t degreeIn(Vertex v): Returns the number of edges going into the given vertex.
degreeOut size_t degreeOut(Vertex v): Returns the number of edges going out of the given vertex.
diffEdges auto diffEdges(typeof(this) other): Returns the set of changes between the edges in this graph and the other.
diffVertices auto diffVertices(typeof(this) other): Returns the set of changes between the vertices in this graph and the other.
edges auto edges(): Returns an array of edges of the given type.
outgoing auto outgoing(Vertex v): Returns a range of outgoing neighbors from the given node.
put void put(Vertex v): Adds a vertex if it does not already exist.
put void put(A from, B to, EdgeDataAB data): Adds an edge. Both vertices must be added to the graph first.
put void put(B from, A to, EdgeDataBA data): Undocumented in source. Be warned that the author may not have intended to support it.
remove void remove(Vertex v): Removes a vertex and all the incoming and outgoing edges associated with it.
remove void remove(From from, To to): Removes an edge.
subgraph typeof(this) subgraph(const(A[]) rootsA, const(B[]) rootsB): Creates a subgraph using the given roots. This is done by traversing the graph and only adding the vertices and edges that we come across.
traverse void traverse(Context ctx, TaskPool pool): Traverses the entire graph depth-first calling the given visitor functions.

Properties

cycles immutable(SCC)[] cycles [@property getter]: Returns an array of cycles in the graph.
empty bool empty [@property getter]: Returns true if the graph is empty.
length size_t length [@property getter]: Returns the number of vertices for the given type.
tarjan auto tarjan [@property getter]: Using Tarjan's algorithm, returns a range of strongly connected components (SCCs). Each SCC consists of a list of vertices that are strongly connected. The SCCs are listed in reverse topological order.
vertices auto vertices [@property getter]: Returns a range of vertices of the given type.

Structs

Edges struct Edges(From, To): Undocumented in source.
SCC struct SCC: A strongly connected component.
Visited struct Visited(Value): Bookkeeping structure for helping keep track of vertices that have been visited.

Meta

Source

See Implementation

button graph classes

Graph