Distances on Directed Graphs in R
mpadge.tngl.sh
1/* Directed Graphs
2 * ----------------------------------------------------------------------------
3 * Author: Mark Padgham, modified from code by Shane Saunders
4 */
5#include "dgraph.h"
6
7#include <Rcpp.h>
8//#include <cstdio>
9
10/*--- DGraph ----------------------------------------------------------------*/
11
12/* --- Constructor ---
13 * Creates a DGraph object containing n vertices.
14 */
15DGraph::DGraph(size_t n) : m_vertices(n)
16{
17 initVertices();
18}
19
20/* --- Destructor ---
21*/
22DGraph::~DGraph()
23{
24 clear();
25}
26
27// length of vertices
28size_t DGraph::nVertices() const
29{
30 return static_cast <size_t> (m_vertices.size());
31}
32
33const std::vector<DGraphVertex>& DGraph::vertices() const
34{
35 return m_vertices;
36}
37
38/* --- clear() ---
39 * Clears all edges from the graph.
40 */
41void DGraph::clear()
42{
43 DGraphEdge *edge, *nextEdge;
44 for(size_t i = 0; i < m_vertices.size(); i++) {
45 edge = m_vertices[i].outHead;
46
47 while(edge) {
48 nextEdge = edge->nextOut;
49 delete edge;
50 edge = nextEdge;
51 }
52 }
53 initVertices();
54}
55
56void DGraph::initVertices()
57{
58 for(size_t i = 0; i < m_vertices.size(); i++) {
59 m_vertices[i].outHead = m_vertices[i].outTail = nullptr;
60 m_vertices[i].inHead = m_vertices[i].inTail = nullptr;
61 m_vertices[i].outSize = m_vertices[i].inSize = 0;
62 }
63}
64
65/* --- addNewEdge() ---
66 * Adds a new edge from vertex 'source' to vertex 'target' with
67 * with a corresponding distance of dist.
68 */
69void DGraph::addNewEdge(size_t source, size_t target,
70 double dist, double wt, size_t edge_id)
71{
72 DGraphEdge *newEdge = new DGraphEdge;
73 newEdge->source = source;
74 newEdge->target = target;
75 newEdge->edge_id = edge_id;
76 newEdge->dist = dist;
77 newEdge->wt = wt;
78 newEdge->nextOut = nullptr;
79 newEdge->nextIn = nullptr;
80
81 DGraphVertex *vertex = &m_vertices[source];
82 if(vertex->outTail) {
83 vertex->outTail->nextOut = newEdge;
84 }
85 else {
86 vertex->outHead = newEdge;
87 }
88 vertex->outTail = newEdge;
89 vertex->outSize++;
90
91 vertex = &m_vertices[target];
92 if(vertex->inTail) {
93 vertex->inTail->nextIn = newEdge;
94 }
95 else {
96 vertex->inHead = newEdge;
97 }
98 vertex->inTail = newEdge;
99 vertex->inSize++;
100}
101
102bool DGraph::edgeExists(size_t v, size_t w) const
103{
104 /* Scan all existing edges from v to determine whether an edge to w exists.
105 */
106 const DGraphEdge *edge = m_vertices[v].outHead;
107 while(edge) {
108 if(edge->target == w) return true;
109 edge = edge->nextOut;
110 }
111 return false;
112}
113
114/* --- reachable() ---
115 * Test whether all vertices are reachable from the source vertex s.
116 */
117bool DGraph::reachable (size_t s) const
118{
119 std::vector<size_t> stack(m_vertices.size());
120 size_t tos = 0;
121
122 std::vector<size_t> visited(m_vertices.size(), 0);
123
124 size_t vertexCount = 0;
125 visited [s] = 1;
126 stack [tos++] = s;
127 DGraphEdge *edge;
128 size_t v, w;
129 while (tos) {
130 v = stack [--tos];
131 vertexCount++;
132 edge = m_vertices [v].outHead;
133 while (edge) {
134 w = edge->target;
135 if (!visited [w]) {
136 visited [w] = 1;
137 stack [tos++] = w;
138 }
139 edge = edge->nextOut;
140 }
141 }
142
143 return vertexCount == m_vertices.size();
144}
145
146
147/* --- print() ---
148 * Prints a text representation of the graph to the standard output.
149 */
150void DGraph::print() const
151{
152 const DGraphEdge *edge;
153
154 Rcpp::Rcout << "Graph (vertex: edge{dist} list) = " << std::endl;
155
156 for(size_t i = 0; i < m_vertices.size(); i++) {
157 Rcpp::Rcout << i << ": ";
158 edge = m_vertices[i].outHead;
159 while(edge) {
160 Rcpp::Rcout << edge->target << "{" << edge->dist << "} ";
161 edge = edge->nextOut;
162 }
163 Rcpp::Rcout << std::endl;
164 }
165}