mpadge.tngl.sh
many-to-many multi-modal routing aggregator
1#ifndef DGRAPH_H
2#define DGRAPH_H
3
4#include <vector>
5#include <limits>
6
7typedef std::size_t size_t;
8
9/* Directed Graphs
10 * ----------------------------------------------------------------------------
11 * Author: Mark Padgham
12 * Copied straight from 'dodgr' code, with these functions removed here:
13 * - edgeExists
14 * - reachable
15 * - print
16 */
17
18
19/*--- Directed Graph Classes ------------------------------------------------*/
20
21/* --- Directed graph edge class ---
22 * Each edge object represents an outgoing edge of some vertex and is stored in
23 * that vertexes linked list of edges. The member 'target' is the edge's
24 * target vertex number, whereas 'source' is the edge's source vertex number.
25 * The member 'dist' is the associated edge distance. The pointers 'nextIn'
26 * and 'nextOut' are used to form a linked lists of a vertices incoming and
27 * outgoing edges respectively. Such linked lists are terminated with a null
28 * pointer.
29 */
30class DGraphEdge {
31 public:
32 size_t source, target, edge_id; // edge_id only used in centrality
33 double dist, wt;
34 DGraphEdge *nextOut, *nextIn;
35};
36
37/* --- Directed graph vertex class ---
38 * Each vertex object has an associated linked lists of edge objects
39 * representing the outgoing and incoming edges of that vertex. The member
40 * pointers outHead and inHead points to the first edge object in the linked
41 * list of outgoing, and incoming edges respectively. Similarly, outTail and
42 * inTail point to the last edge of each linked list. The number of outgoing
43 * and incoming edges are stored in outSize and inSize respectively.
44 */
45class DGraphVertex {
46 public:
47 DGraphEdge *outHead, *outTail;
48 DGraphEdge *inHead, *inTail;
49 int outSize, inSize;
50};
51
52/* --- Directed graph class ---
53 * Vertices in the graph are stored as an array of vertex objects, pointed to
54 * by the member variable 'vertices'. Each vertex is identified by a number
55 * corresponding to its index in the vertices[] array. The member
56 * nVertices is the number of vertices in the graph.
57 *
58 * clear() - Remove all edges from graph.
59 *
60 * addNewEdge() - Adds a new edge to the edge to the graph.
61 *
62 * print() - Prints a text representation of the graph to the standard
63 * output.
64 */
65class DGraph {
66 public:
67 DGraph(size_t n);
68 ~DGraph();
69
70 size_t nVertices() const;
71 const std::vector<DGraphVertex>& vertices() const;
72
73 // disable copy/assign as will crash (double-delete)
74 DGraph(const DGraph&) = delete;
75 DGraph& operator=(const DGraph&) = delete;
76
77 void clear();
78 void addNewEdge(size_t srcVertexNo, size_t destVertexNo,
79 double dist, double wt, size_t edge_id);
80 private:
81 void initVertices();
82
83 std::vector<DGraphVertex> m_vertices;
84
85};
86
87
88/*---------------------------------------------------------------------------*/
89#endif