Graph

This structure represents a graph with optional edge payloads. The graph is represented as a list of edges which is particularly suited for sparse graphs. While the set of nodes is fixed the set of edges is mutable.

struct Graph (

Node

Weight = void

Flag!"isDirected" isDirected = No.isDirected

EdgePayload = void

) {

enum isWeighted;

enum hasEdgePayload;

struct Edge;

static Edge edge(T args);

Node[] _nodes;

Appender!(Edge[]) _edges;

const(Node[]) nodes [@property getter];

auto edges [@property getter];

this(Node[] nodes);

this(Node[] nodes, Edge[] edges);

void bulkAddForce(R edges);

void opOpAssign(Edge edge);

struct ConflictStrategy;

Edge forceAdd(Edge edge);

Edge replaceEdge(in size_t edgeIdx, Edge newEdge);

bool opBinaryRight(in Node node);

bool has(in Node node);

bool opBinaryRight(in Edge edge);

bool has(in Edge edge);

auto ref get(in Edge edge);

size_t indexOf(in Node n);

size_t indexOf(in Edge edge);

auto inEdges(Node n);

auto outEdges(Node n);

size_t inDegree(Node n);

size_t outDegree(Node n);

auto incidentEdges(Node n);

alias inEdges = incidentEdges;

alias outEdges = incidentEdges;

size_t[][] adjacencyList();

size_t degree(Node n);

alias inDegree = degree;

alias outDegree = degree;

}

Constructors

this this(Node[] nodes)
this(Node[] nodes, Edge[] edges): Construct a graph from a set of nodes (and edges). Modifies nodes while sorting but releases it after construction.

Postblit

A postblit is present on this object, but not explicitly documented in the source.

Members

Aliases

inDegree alias inDegree = degree: Get the degree of node n.
inEdges alias inEdges = incidentEdges: Returns a range of all edges incident to node n.
outDegree alias outDegree = degree: Get the degree of node n.
outEdges alias outEdges = incidentEdges: Returns a range of all edges incident to node n.

Functions

adjacencyList size_t[][] adjacencyList(): Get the adjacencyList of this graph where nodes are represented by their index in the nodes list.
bulkAddForce void bulkAddForce(R edges): Add a set of edges to this graph without any checks.
degree size_t degree(Node n): Get the degree of node n.
forceAdd Edge forceAdd(Edge edge): Forcibly add an edge to this graph.
get auto ref get(in Edge edge): Get the designated edge from this graph. Only the start and end node will be compared.
has bool has(in Node node): Check if edge/node exists in this graph. Ignores the weight if weighted.
has bool has(in Edge edge): Check if edge exists in this graph. Only the start and end node will be compared.
inDegree size_t inDegree(Node n): Get the in/out degree of node n.
inEdges auto inEdges(Node n)
auto inEdges(Node n): Returns a range of in/outgoing edges of node n.
incidentEdges auto incidentEdges(Node n)
auto incidentEdges(Node n): Returns a range of all edges incident to node n.
indexOf size_t indexOf(in Node n): Returns the index of node n in the list of nodes.
indexOf size_t indexOf(in Edge edge): Returns the index of node n in the list of nodes.
opBinaryRight bool opBinaryRight(in Node node): Check if edge/node exists in this graph. Ignores the weight if weighted.
opBinaryRight bool opBinaryRight(in Edge edge): Check if edge exists in this graph. Only the start and end node will be compared.
opOpAssign void opOpAssign(Edge edge): Add an edge to this graph.
outDegree size_t outDegree(Node n): Get the in/out degree of node n.
outEdges auto outEdges(Node n)
auto outEdges(Node n): Returns a range of in/outgoing edges of node n.
replaceEdge Edge replaceEdge(in size_t edgeIdx, Edge newEdge): Replace an edge in this graph.

Properties

edges auto edges [@property getter]: Get the set (ordered list) of edges in this graph.
nodes const(Node[]) nodes [@property getter]: The set (ordered list) of nodes.

Static functions

edge Edge edge(T args): Construct an edge for this graph.

Structs

ConflictStrategy struct ConflictStrategy: Some pre-defined conflict handlers for add.
Edge struct Edge

Examples

1 //   +-+  +-+
2 //   \ /  \ /
3 //   (1)--(2)
4 auto g1 = Graph!int([1, 2]);
5 
6 g1 ~= g1.edge(1, 1);
7 g1 ~= g1.edge(1, 2);
8 g1.add(g1.edge(2, 2));
9 
10 assert(g1.edge(1, 1) in g1);
11 assert(g1.edge(1, 2) in g1);
12 assert(g1.edge(2, 1) in g1);
13 assert(g1.has(g1.edge(2, 2)));
14 assert(g1.allDegrees().degrees == [2, 2]);
15 assert(g1.allIncidentEdges().incidentEdges == [
16     [g1.edge(1, 1), g1.edge(1, 2)],
17     [g1.edge(1, 2), g1.edge(2, 2)],
18 ]);
19 
20 //   0.5     0.5
21 //   +-+     +-+
22 //   \ /     \ /
23 //   (1)-----(2)
24 //       1.0
25 auto g2 = Graph!(int, double)([1, 2]);
26 
27 g2 ~= g2.edge(1, 1, 0.5);
28 g2 ~= g2.edge(1, 2, 1.0);
29 g2.add(g2.edge(2, 2, 0.5));
30 
31 assert(g2.edge(1, 1) in g2);
32 assert(g2.edge(1, 2) in g2);
33 assert(g2.edge(2, 1) in g2);
34 assert(g2.has(g2.edge(2, 2)));
35 assert(g2.allDegrees().degrees == [2, 2]);
36 assert(g2.allIncidentEdges().incidentEdges == [
37     [g2.edge(1, 1, 0.5), g2.edge(1, 2, 1.0)],
38     [g2.edge(1, 2, 1.0), g2.edge(2, 2, 0.5)],
39 ]);
40 
41 //   0.5     0.5
42 //   +-+     +-+
43 //   \ v     v /
44 //   (1)---->(2)
45 //       1.0
46 auto g3 = Graph!(int, double, Yes.isDirected)([1, 2]);
47 
48 g3 ~= g3.edge(1, 1, 0.5);
49 g3 ~= g3.edge(1, 2, 1.0);
50 g3.add(g3.edge(2, 2, 0.5));
51 
52 assert(g3.edge(1, 1) in g3);
53 assert(g3.edge(1, 2) in g3);
54 assert(!(g3.edge(2, 1) in g3));
55 assert(g3.has(g3.edge(2, 2)));
56 
57 //   +-+   +-+
58 //   \ v   v /
59 //   (1)-->(2)
60 auto g4 = Graph!(int, void, Yes.isDirected)([1, 2]);
61 
62 g4 ~= g4.edge(1, 1);
63 g4 ~= g4.edge(1, 2);
64 g4.add(g4.edge(2, 2));
65 
66 assert(g4.edge(1, 1) in g4);
67 assert(g4.edge(1, 2) in g4);
68 assert(!(g4.edge(2, 1) in g4));
69 assert(g4.has(g4.edge(2, 2)));
70 
71 //   +-+  +-+
72 //   \ /  \ /
73 //   (1)--(2)
74 //
75 // payload(1, 1) = [1];
76 // payload(1, 2) = [2];
77 // payload(2, 2) = [3];
78 auto g5 = Graph!(int, void, No.isDirected, int[])([1, 2]);
79 
80 g5 ~= g5.edge(1, 1, [1]);
81 g5 ~= g5.edge(1, 2, [2]);
82 g5.add(g5.edge(2, 2, [3]));
83 
84 assert(g5.edge(1, 1) in g5);
85 assert(g5.get(g5.edge(1, 1)).payload == [1]);
86 assert(g5.edge(1, 2) in g5);
87 assert(g5.get(g5.edge(1, 2)).payload == [2]);
88 assert(g5.edge(2, 1) in g5);
89 assert(g5.get(g5.edge(2, 1)).payload == [2]);
90 assert(g5.has(g5.edge(2, 2)));
91 assert(g5.get(g5.edge(2, 2)).payload == [3]);
92 assert(g5.allDegrees().degrees == [2, 2]);
93 assert(g5.allIncidentEdges().incidentEdges == [
94     [g5.edge(1, 1), g5.edge(1, 2)],
95     [g5.edge(1, 2), g5.edge(2, 2)],
96 ]);

1 //     -1     1         1
2 // (1)----(2)---(3) (4)---(5) (6)
3 size_t[] contigs = [1, 2, 3, 4, 5, 6];
4 auto contigGraph = Graph!(size_t, int)([1, 2, 3, 4, 5, 6]);
5 
6 contigGraph.add(contigGraph.edge(1, 2, -1));
7 contigGraph.add(contigGraph.edge(2, 3, 1));
8 contigGraph.add(contigGraph.edge(4, 5, 1));
9 
10 foreach (contig; contigs)
11 {
12     assert(contigGraph.degree(contig) <= 2);
13 }
14 assert(contigGraph.allDegrees().degrees == [1, 2, 1, 1, 1, 0]);
15 assert(contigGraph.allIncidentEdges().incidentEdges == [
16     [contigGraph.edge(1, 2, -1)],
17     [contigGraph.edge(1, 2, -1), contigGraph.edge(2, 3, 1)],
18     [contigGraph.edge(2, 3, 1)],
19     [contigGraph.edge(4, 5, 1)],
20     [contigGraph.edge(4, 5, 1)],
21     [],
22 ]);