mpadge.tngl.sh
many-to-many multi-modal routing aggregator
1/* Directed Graphs
2 * ----------------------------------------------------------------------------
3 * Author: Mark Padgham
4 * Copied straight from 'dodgr' code, with these functions removed here:
5 * - edgeExists
6 * - reachable
7 * - print
8 */
9#include "dgraph.h"
10
11#include <Rcpp.h>
12//#include <cstdio>
13
14/*--- DGraph ----------------------------------------------------------------*/
15
16/* --- Constructor ---
17 * Creates a DGraph object containing n vertices.
18 */
19DGraph::DGraph(size_t n) : m_vertices(n)
20{
21 initVertices();
22}
23
24/* --- Destructor ---
25*/
26DGraph::~DGraph()
27{
28 clear();
29}
30
31// length of vertices
32size_t DGraph::nVertices() const
33{
34 return static_cast <size_t> (m_vertices.size());
35}
36
37const std::vector<DGraphVertex>& DGraph::vertices() const
38{
39 return m_vertices;
40}
41
42/* --- clear() ---
43 * Clears all edges from the graph.
44 */
45void DGraph::clear()
46{
47 DGraphEdge *edge, *nextEdge;
48 for(size_t i = 0; i < m_vertices.size(); i++) {
49 edge = m_vertices[i].outHead;
50
51 while(edge) {
52 nextEdge = edge->nextOut;
53 delete edge;
54 edge = nextEdge;
55 }
56 }
57 initVertices();
58}
59
60void DGraph::initVertices()
61{
62 for(size_t i = 0; i < m_vertices.size(); i++) {
63 m_vertices[i].outHead = m_vertices[i].outTail = nullptr;
64 m_vertices[i].inHead = m_vertices[i].inTail = nullptr;
65 m_vertices[i].outSize = m_vertices[i].inSize = 0;
66 }
67}
68
69/* --- addNewEdge() ---
70 * Adds a new edge from vertex 'source' to vertex 'target' with
71 * with a corresponding distance of dist.
72 */
73void DGraph::addNewEdge(size_t source, size_t target,
74 double dist, double wt, size_t edge_id)
75{
76 DGraphEdge *newEdge = new DGraphEdge;
77 newEdge->source = source;
78 newEdge->target = target;
79 newEdge->edge_id = edge_id;
80 newEdge->dist = dist;
81 newEdge->wt = wt;
82 newEdge->nextOut = nullptr;
83 newEdge->nextIn = nullptr;
84
85 DGraphVertex *vertex = &m_vertices[source];
86 if(vertex->outTail) {
87 vertex->outTail->nextOut = newEdge;
88 }
89 else {
90 vertex->outHead = newEdge;
91 }
92 vertex->outTail = newEdge;
93 vertex->outSize++;
94
95 vertex = &m_vertices[target];
96 if(vertex->inTail) {
97 vertex->inTail->nextIn = newEdge;
98 }
99 else {
100 vertex->inHead = newEdge;
101 }
102 vertex->inTail = newEdge;
103 vertex->inSize++;
104}