• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

JohnSnowLabs / spark-nlp / 4947838414

pending completion
4947838414

Pull #13796

github

GitHub
Merge 30bdeef19 into ef7906c5e
Pull Request #13796: Add unzip param to downloadModelDirectly in ResourceDownloader

39 of 39 new or added lines in 2 files covered. (100.0%)

8632 of 13111 relevant lines covered (65.84%)

0.66 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

97.73
/src/main/scala/com/johnsnowlabs/nlp/util/GraphBuilder.scala
1
/*
2
 * Copyright 2017-2022 John Snow Labs
3
 *
4
 * Licensed under the Apache License, Version 2.0 (the "License");
5
 * you may not use this file except in compliance with the License.
6
 * You may obtain a copy of the License at
7
 *
8
 *    http://www.apache.org/licenses/LICENSE-2.0
9
 *
10
 * Unless required by applicable law or agreed to in writing, software
11
 * distributed under the License is distributed on an "AS IS" BASIS,
12
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13
 * See the License for the specific language governing permissions and
14
 * limitations under the License.
15
 */
16

17
package com.johnsnowlabs.nlp.util
18

19
import scala.collection.mutable
20
import scala.collection.mutable.ListBuffer
21
import scala.util.control.Breaks.{break, breakable}
22

23
/** Graph Builder that creates a graph representation as an Adjacency List
24
  *
25
  * Adjacency List: An array of lists is used. The size of the array is equal to the number of
26
  * vertices. Let the array be an array[]. An entry array[i] represents the list of vertices
27
  * adjacent to the ith vertex.
28
  * @param numberOfVertices
29
  */
30
class GraphBuilder(numberOfVertices: Int) {
31

32
  if (numberOfVertices <= 0) {
1✔
33
    throw new IllegalArgumentException("Graph should have at least two vertices")
1✔
34
  }
35

36
  private val graph: Map[Int, mutable.Set[Int]] = (0 until numberOfVertices).toList.flatMap {
1✔
37
    vertexIndex =>
38
      Map(vertexIndex -> mutable.Set[Int]())
1✔
39
  }.toMap
1✔
40

41
  def addEdge(source: Int, destination: Int): Unit = {
42
    validateDestinationVertex(destination)
1✔
43
    val adjacentNodes = getAdjacentVertices(source)
1✔
44
    adjacentNodes += destination
1✔
45
  }
46

47
  def getNumberOfVertices: Int = {
48
    graph.size
1✔
49
  }
50

51
  def getAdjacentVertices(source: Int): mutable.Set[Int] = {
52
    val adjacentNodes = graph
53
      .get(source)
54
      .orElse(throw new NoSuchElementException(s"Source vertex $source does not exist"))
1✔
55
    adjacentNodes.get
1✔
56
  }
57

58
  def edgeExists(source: Int, destination: Int): Boolean = {
59
    validateDestinationVertex(destination)
1✔
60
    val adjacentNodes = getAdjacentVertices(source)
1✔
61
    adjacentNodes.contains(destination)
1✔
62
  }
63

64
  private def validateDestinationVertex(destination: Int): Unit = {
65
    if (destination > graph.size - 1) {
1✔
66
      throw new NoSuchElementException(s"Destination vertex $destination does not exist")
1✔
67
    }
68
  }
69

70
  /** Find a path using Depth-first search (DFS) algorithm DFS traverses a tree or graph data
71
    * structures. The algorithm starts at a source node and explores as far as possible along each
72
    * branch before backtracking It uses a stack to store the path of visited nodes
73
    */
74
  def findPath(source: Int, destination: Int): List[Int] = {
75

76
    if (source > graph.size || destination > graph.size) {
1✔
77
      throw new IllegalArgumentException(
1✔
78
        "Source or destination vertices cannot be greater than the size of the graph.")
79
    }
80

81
    val visited: Array[Boolean] = (0 until graph.size).toList.map(_ => false).toArray
1✔
82
    val elementsStack: ListBuffer[Int] = ListBuffer(source)
1✔
83
    val pathStack = new ListBuffer[Int]()
1✔
84

85
    breakable {
1✔
86
      while (elementsStack.nonEmpty) {
1✔
87

88
        val topVertex: Int = elementsStack.last
1✔
89

90
        if (!visited(topVertex)) {
×
91
          elementsStack.remove(elementsStack.length - 1)
1✔
92
          visited(topVertex) = true
1✔
93
          pathStack += topVertex
1✔
94
          if (pathStack.contains(destination)) {
1✔
95
            break
1✔
96
          }
97
        }
98

99
        val adjacentVertices = getAdjacentVertices(topVertex).iterator
1✔
100

101
        while (adjacentVertices.hasNext) {
1✔
102
          val vertex = adjacentVertices.next()
1✔
103
          if (!visited(vertex)) {
1✔
104
            elementsStack += vertex
1✔
105
          }
106
        }
107

108
        var cleaningPathStack = true
1✔
109
        while (cleaningPathStack) {
1✔
110
          val topElement = pathStack.last
1✔
111
          val missingVisitedVertices =
112
            getAdjacentVertices(topElement).filter(vertex => !visited(vertex))
1✔
113
          if (pathStack.length == 1 || missingVisitedVertices.nonEmpty) {
1✔
114
            cleaningPathStack = false
1✔
115
          }
116
          if (visited(topElement) && missingVisitedVertices.isEmpty) {
1✔
117
            pathStack.remove(pathStack.length - 1)
1✔
118
          }
119
        }
120
      }
121
    }
122

123
    pathStack.toList
1✔
124
  }
125

126
}
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2025 Coveralls, Inc