scalax.collection.Graph User Guide Peter Empen 1 Introduction .................

scalax.collection.Graph User Guide Peter Empen 1 Introduction .................................................................................................................................. 2 1.1 Why Use Graph ..................................................................................................................... 2 1.2 Terminology............................................................................................................................ 2 1.3 Status of Work........................................................................................................................ 2 1.4 Limitations .............................................................................................................................. 2 2 Initializing Graphs ........................................................................................................................ 3 2.1 Prerequisites .......................................................................................................................... 3 2.2 Type Parameters.................................................................................................................... 3 2.3 Edge Factories ....................................................................................................................... 4 2.4 Instantiating Graphs ............................................................................................................... 6 2.5 Type Parameter Inference...................................................................................................... 7 2.6 Choosing an Implementation .................................................................................................. 8 3 Inner and Outer Objects............................................................................................................... 9 4 Graph Operations....................................................................................................................... 10 4.1 Iterating ................................................................................................................................ 10 4.2 Looking up Nodes and Edges............................................................................................... 10 4.3 Equality of Inner and Outer Objects...................................................................................... 11 4.4 Adding and Subtracting ........................................................................................................ 11 4.5 Computing Union, Difference and Intersection...................................................................... 13 4.6 Inspecting Endpoints ............................................................................................................ 13 4.7 Inspecting Neighbors and Incident Edges............................................................................. 13 4.8 Querying by Function ........................................................................................................... 14 4.9 Finding Paths ....................................................................................................................... 15 4.10 Traversing ............................................................................................................................ 16 4.11 Measuring Graphs and Grouping Nodes by Degree ............................................................. 18 4.12 Classifying Graphs ............................................................................................................... 18 4.13 Chaining Method Calls.......................................................................................................... 18 5 Customizing Graphs .................................................................................................................. 19 5.1 Defining Custom Edges........................................................................................................ 19 5.2 Defining User Constraints..................................................................................................... 20 5.3 Narrowing Type Parameters................................................................................................. 20 5.4 Modifying Methods ............................................................................................................... 20 5.5 Adding new Methods ............................................................................................................ 21 5.6 Providing new Implementations............................................................................................ 21 6 Run-time Characteristics........................................................................................................... 21 scalax.collection.Graph User Guide / 2 P. Empen 1 Introduction This document provides an example-driven, comprehensive coverage of the functionality of Graph as part of the Extended Scala Library. In each chapter examples are listed first. You may then read the explanations following the examples to make them more coherent or skip them and go directly to the next chapter. References to specific Graph classes in this document may be looked up in the Scaladoc API reference. This guide is not meant to be complete. For the sake of simplicity, most examples are based on graphs spanned over nodes of the type Int. Graph customization is shown by the node type Airport and the edge type Flight. 1.1 Why Use Graph The most important reasons why Graph speeds up your development are: a) Simplicity: Creating, manipulating and querying Graph is intuitive. b) Consistency: Graph seamlessly maintains a consistent state of nodes and edges including prevention of duplicates, intelligent addition and removal. c) Conformity: As a regular collection class, Graph has the same “look and feel” as other members of the Scala collection framework. Whenever appropriate, result types are Scala collection types themselves. d) Flexibility: All kinds of graphs including mixed graphs, multi-graphs and hypergraphs are supported. e) Functional Style: Graph facilitates a concise, functional style of utilizing graph functionality, including traversals, not seen in Java-based libraries. f) Extendibility: You can easily customize Graph to reflect the needs of you application retaining all benefits of Graph. g) Documentation: Ideal progress curve through adequate documentation. Look and see! 1.2 Terminology Throughout the library we use the terms node as a synonym to vertex and edge as a generic term for hyperedge, line (undirected edge) or arc (directed edge). 1.3 Status of Work Graph creation, editing as well as functional traversal and path operations have been completed. More functionality is due to be added. You are invited to request enhancements based on your problem domain. 1.4 Limitations • There is no direct support for half-edges but they can be simulated by Option. • Neither node nor edge sets may be infinite although this could be achieved by a custom implementation. scalax.collection.Graph User Guide / 3 P. Empen 2 Initializing Graphs 2.1 Prerequisites The downloadable binaries are named Graph-<module>_<Scala-version>-<Graph- version>.jar following the community-convention. For each <module> (here: core) there is a separate User Guide. To run the examples in the current documentation ensure that Graph- core_*.jar is on your class path. In most cases you need to import the following: import scalax.collection.Graph // or scalax.collection.mutable.Graph import scalax.collection.GraphPredef._, scalax.collection.GraphEdge._ 2.2 Type Parameters trait Graph[N, E[X] <: EdgeLikeIn[X]] N is the type of the nodes of a graph instance. E[X] is the kind of type of edges of a graph instance. The trait Graph and most related templates have two type parameters: one for the contained nodes and one for the kind of contained edges. Graph doesn’t impose any restriction on the type of nodes meaning that for the upper bound of the node type parameter any type including Any may be chosen. In contrast, the type parameter for edges is required to have at least the upper bound EdgeLikeIn. When selecting between the predefined edge types it might help you to understand their inheritance relationships: Table 2.2.1: Edge type hierarchy All edge classes derive from trait EdgeLike and, optionally, from trait DiEdgeLike. There are four edge categories: hyperdedge, directed hyperedge, undirected and directed edge. Each of these categories has predefined edge classes representing any combination of non-weighted, weighted (W), key-weighted (Wk), labeled (L) and key-labeled (Lk). See 2.3 Edge Factories for examples and more details. Based on the above inheritance hierarchy, graph types in the sense of graph theory are governed by the edge type parameter E[X] as follows: scalax.collection.Graph User Guide / 4 P. Empen Type of graph Definition The graph contains… Edge Type (kind of type parameter) … or any corresponding custom edge type Simple only undirected edges without multi- edges UnDiEdge or any of its variants W*, L* or WL* where the user is responsible to avoid adding directed edges as the type system does not restrict she to do so Mixed more than one type of edges without multi-edges UnDiEdge or its parent types such as HyperEdge or any of their variants except the keyed ones or, as a use case, directed and undirected edges without multi-edges UnDiEdge or any of its variants except the keyed ones Weighted edges with the special label weight any of the predefined edge classes containing W in its prefix Multi One or more edge types with multi- edges any of the predefined edge classes containing K in its prefix Table 2.2.2: Graph types mapped to edge types Although there is no constraint on the node type, you should be especially careful when designing mutable nodes: the hashCode returned by your nodes should not change over their lifetime even if nodes are mutating.1 Otherwise, looking up mutated elements in a graph will fail - at least in case of the HashMap-based default implementation.2 This is clearly the very same behavior as with scala.collection.Set or Map. 2.3 Edge Factories Shortcut Named Factory Meaning 1~2~3 HyperEdge(1,2,3) (undirected) hyperedge between 1, 2 and 3 1~>2~>3 DiHyperEdge(1,2,3) directed hyperedge from 1 via 2 to 3 "A"~"B" UnDiEdge("A","B") undirected edge between "A" and "B" "A"~>"B" DiEdge("A","B") directed edge from "A" to "B" 1~2 % 5 WUnDiEdge(1,2,5) undirected edge between 1 and 2 with a weight of 5 1~>2 % 0 WDiEdge(1,2,0) directed edge from 1 to 2 with a weight of 0 (1 ~+> 2)(x) LDiEdge(1,2)(x) directed edge from 1 to 2 labeled with x (1 ~+#> 2)(x) LkDiEdge(1,2)(x) directed edge from 1 to 2 key-labeled with x (1 ~%+# 2)(x) WLkUnDiEdge(1,2)(5,x) undirected edge between 1 and 2 with a weight of 5 and key-labeled with x Table 2.3.1: Edge factory examples Edge factories are simply apply methods of companion objects of edge classes. They are typically called whenever an edge is passed to a Graph method as an argument. The above table contains factory examples for some of the predefined edge classes. 1 “Note: great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map.” (http://download.oracle.com/javase/1.4.2/docs/api/java/util/Map.html) 2 You may still find mutated elements calling find or filter with a having-argument, but these calls start a full scan. scalax.collection.Graph User Guide / 5 P. Empen Apart from the four basic edge classes [Di]HyperEdge and [Un]DiEdge there are plenty of convenience edge class variants enabling easy creation of weighted and / or labeled edges: Edge Category Edge Class Shortcut Description HyperEdge ~ hyperedge WHyperEdge ~% weighted hyperedge WkHyperEdge ~%# key-weighted hyperedge LHyperEdge ~+ labeled hyperedge LkHyperEdge ~+# key-labeled hyperedge WLHyperEdge ~%+ weighted labeled hyperedge WkLHyperEdge ~%#+ key-weighted labeled hyperedge WLkHyperEdge ~%+# weighted key-labeled hyperedge Hyperedge WkLkHyperEdge ~%#+# key-weighted key-labeled hyperedge DiHyperEdge ~> directed hyperedge WDiHyperEdge ~%> weighted directed hyperedge WkDiHyperEdge ~%#> key-weighted directed hyperedge LDiHyperEdge ~+> labeled directed hyperedge LkDiHyperEdge ~+#> key-labeled directed hyperedge WLDiHyperEdge ~%+> weighted labeled directed hyperedge WkLDiHyperEdge ~%#+> key-weighted labeled directed hyperedge WLkDiHyperEdge ~%+#> weighted key-labeled directed hyperedge Directed Hyperedge WkLkDiHyperEdge ~%#+#> key-weighted key-labeled directed hyperedge UnDiEdge ~ undirected edge WUnDiEdge ~% weighted undirected edge WkUnDiEdge ~%# key-weighted undirected edge LUnDiEdge ~+ labeled undirected edge LkUnDiEdge ~+# key-labeled undirected edge WLUnDiEdge ~%+ weighted labeled undirected edge WkLUnDiEdge ~%#+ key-weighted labeled undirected edge WLkUnDiEdge ~%+# weighted key-labeled undirected edge Undirected Edge WkLkUnDiEdge ~%#+# key-weighted key-labeled undirected edge DiEdge ~> directed edge WDiEdge ~%> weighted directed edge WkDiEdge ~%#> key-weighted directed edge LDiEdge ~+> labeled directed edge LkDiEdge ~+#> key-labeled directed edge WLDiEdge ~%+> weighted labeled directed edge WkLDiEdge ~%#+> key-weighted labeled directed edge WLkDiEdge ~%+#> weighted key-labeled directed edge Directed Edge WkLkDiEdge ~%#+#> key-weighted key-labeled directed uploads/s1/ graph4scala-userguide 1 .pdf

Documents similaires

scalax.collection.Graph User Guide Peter Empen 1 Introduction ................. 0 0

• Détails
• Publié le Dec 27, 2021
• Catégorie Administration
• Langue French
• Taille du fichier 0.1250MB