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.

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 ]);

Meta