davecom / swiftgraph Goto Github PK

I'm interested in contributing graph union operation: http://mathworld.wolfram.com/GraphUnion.html
It should be quite straightforward for unweighted graphs. For weighted graphs, we need to add different ways to handle weight conflicts on common edges:

• Built in "reducers": sum, average, min, max.
• Support custom reducers.
• Report conflicts as exceptions or errors (this could be modeled as a reducer too)

My only question is how to compute the disjoint set union. You store edges and nodes as Array. Is building a Set from one array, use Set.formUnion and then convert back to array a good solution? I can't find info on computational complexity for these operations.

PS: maybe it makes more sense for the weighted case to just treat edges between same nodes as distinct edges. Then add another operation that merges edges between common nodes.

Hello,
I have string vertices in a weighted undirected graph. I created edges doing AddEdge(from: "name1", to: "name2", weight: xx). When i run BFS/DFS and print the list of edges i get back, the u and v fields are ints. I assume this is the index of the vertices. Is there a way to get the string name associated with the vertex at this point?
Thanks.

Hello.

I was trying SwiftGraph with Swift 3 and I'm getting the following error:

Type Graph<V> does not conform to protocol IndexableBase for the below declaration inside Graph.swift:

public class Graph<V: Equatable>: CustomStringConvertible, Swift.Sequence, Swift.Collection { ... }

Any leads? Thanks.

It would be great to add an encoder for the dot language of https://www.graphviz.org/
This way applications can export the graphs they build with SwiftGraph for human visualization.

CocoaPods 1.0.1 with Xcode 8 Beta 3 seems to be rebasing the git repository for some bizarre reason:

Davids-Air:swiftgraph dave$ pod trunk push SwiftGraph.podspec
Updating spec repo `master`

CocoaPods 1.1.0.beta.1 is available.
To update use: `sudo gem install cocoapods --pre`
[!] This is a test version we'd love you to try.

For more information, see https://blog.cocoapods.org and the CHANGELOG for this version at https://github.com/CocoaPods/CocoaPods/releases/tag/1.1.0.beta.1

Validating podspec
 -> SwiftGraph (1.1.0)
    - ERROR | [iOS] unknown: Encountered an unknown error (Must be in the root of the repo (/Users/dave/.cocoapods/repos/master), instead in /Users/dave/Documents/Projects/SwiftGraph.) during validation.

[!] The spec did not pass validation, due to 1 error.

Please add a CHANGELOG.md file to make it easier to track recent changes in the framework.

https://github.com/JamitLabs/Accio

We are SwiftPM compatible, so we should work almost out of the box.

• Check that we can install SwiftGraph on a project using Accio
• Add Accio support badge

Hi,

Native swift types like Array only conform to Codable when their elements are Codable.
It looks like Graph doesn't have any special need for being Codable.
Would it be possible to make Graph conform to Codable only when its vertices are? I've a use case where I'm not interested in the Graph being codable and adding conformance to the vertex type would be a lot of work.

Add an extended example to the homepage of doing useful things with SwiftGraph and add badges to show Linux support, Swift 4 support, it's building, etc.

Since now Graph is a protocol, we don't use inheritance that much. The only class that is still inheriting is UniqueElementsGraph. Shall we convert all the graph classes to structs?
UnweightedGraph and WeightedGraph store the graph in a couple of arrays, which are value types. So it makes sense for the graph classes to also be value types from this point of view.
This will also allow us to remove the Codable specific classes and implement it in an extension right?

CocoaPods has stopped its documentation service. We could generate our own docs again on GitHub pages or find another automated service.

In the original version of SwiftGraph, developed under Swift 1, Swift did not support protocol extensions (function implementations in protocols) so it was not particularly useful to make Graph a protocol. I need to see how much existing code would be broken by refactoring Graph into a protocol. Since this would be a large breaking change, it would only be made permanent for version 2.0 of SwiftGraph.

Calling
public func removeAllEdges(from: V, to: V, bidirectional: Bool = true)
crashes at calling
public func removeAllEdges(from: Int, to: Int, bidirectional: Bool = true)
with fatal error: Index out of range

Is it present/planned? If not I would be interested in adding it.

Would it be possible to speed up detectCycles and detectCyclesAsEdges by making them run parts of the search in parallel? I don't know whether the algorithm is suitable for parallelization, but it could be worth looking into.

Background: I've been modifying my juggling code to deal with throwing multiple objects at the same time, and the state graphs for this technique are way bigger than for throwing a single object at once. For 3 balls, for a maximum throw height of 6, there are 110,552 cycles in the graph. I don't know how many there are for a maximum throw height of 7 because I haven't been able to run the code for long enough yet to find out.

For graphs this large, memory usage is also a concern. My current test run searching for a max throw height of 7 is up over 1 GB used.

(Much of this is academic. I don't know if I have a real-world use case for searching for cycles on graphs this large, at least not quickly. If my app needs to use them, I'll probably generate them once and bake them into the app.)

It would be useful to have a method that finds all elementary cycles (where no vertex is repeated except for the start/end one) in a directed graph. Here's an example from Mathematica: https://mathematica.stackexchange.com/questions/9434/finding-elementary-cycles-of-directed-graphs

Probably Prim's Algorithm

What are the reasons to add the xcodeproj in git?

My proposal is to remove it from git and just let swift package generate one whenever is needed by a user. Otherwise it's difficult to add a dependency in Package.swift

Also, swift test can generate the testing boilerplate for linux, I also propose to use it.

Let's say I have two weighted and not directed edges, connecting the same vertices, as follows:

let edgeA = WeightedEdge<Int> = WeightedEdge(u: 0, v: 1, directed: false, weight: 10)
let edgeB = WeightedEdge<Int> = WeightedEdge(u: 1, v: 0, directed: false, weight: 10)

Currently we have so that edgeA == edgeB returns false.

Shouldn't the ==(_:_:) operator take into consideration whether they're directed? Or am I missing something?
So in this particular scenario I would expect edgeA == edgeB to return true, as they are not directed.

In summary we would have:

let directedEdgeA = WeightedEdge<Int> = WeightedEdge(u: 0, v: 1, directed: false, weight: 10)
let directedEdgeB = WeightedEdge<Int> = WeightedEdge(u: 1, v: 0, directed: false, weight: 10)
directedEdgeA == directedEdgeB // returns `true`


let undirectedEdgeC = WeightedEdge<Int> = WeightedEdge(u: 0, v: 1, directed: true, weight: 10)
let undirectedEdgeD = WeightedEdge<Int> = WeightedEdge(u: 1, v: 0, directed: true, weight: 10)
undirectedEdgeC == undirectedEdgeD // returns `false`

If there are any worries about how changing the ==(_:_:) implementation would affect other features, should we have a separate method to compare two edges?
Any thoughts on this?

Check all is well on Swift 5 after the final release of it ships with Xcode 10.2 and if any changes are needed. Review the changes in recent pull requests by @ZevEisenberg and @ferranpujolcamins .

Development for Swift 5/SwiftGraph 2.1 is taking place in the release2.1/swift5 branch.

By having a pure Swift implementation of a Graph, there's currently no way, as far as I can tell, to write a Graph to disk with NSKeyedArchiving / NSCoding.

I'm getting an array index out of bounds crash when removing a vertex, the crash is in Graph.swift line 207 and 226. It seems strange that it could crash there so I modified the function a bit to collect some more data by checking the index and printing out out some more data.

The modified loop in the function looks like:

        for j in 0..<index {
            print("Removing Vertices")
            let beginningCount = edges[j].count
            var toRemove: [Int] = [Int]()
            for l in 0..<edges[j].count {
                if edges[j][l].v == index {
                    toRemove.append(l)
                    continue
                }
                if edges[j][l].v > index {
                    edges[j][l].v -= 1
                }
            }
            for f in toRemove {
                
                if f < edges[j].count {
                    edges[j].remove(at: f)
                }
                else {
                    print("Number Of edges: \(edges[j].count), starting count: \(beginningCount) , toRemove: \(f)")
                }
            }
        }

When I run it I get things in the console like:

Removing Vertices
Number Of edges: 91, starting count: 144 , toRemove: 91
Number Of edges: 91, starting count: 144 , toRemove: 92
Number Of edges: 91, starting count: 144 , toRemove: 93
Number Of edges: 91, starting count: 144 , toRemove: 94
Number Of edges: 91, starting count: 144 , toRemove: 95
Number Of edges: 91, starting count: 144 , toRemove: 96
Number Of edges: 91, starting count: 144 , toRemove: 97
Number Of edges: 91, starting count: 144 , toRemove: 98
Number Of edges: 91, starting count: 144 , toRemove: 99
Number Of edges: 91, starting count: 144 , toRemove: 100
Number Of edges: 91, starting count: 144 , toRemove: 101
Number Of edges: 91, starting count: 144 , toRemove: 102

It seems as if the array is being modified from the beginning of the loop when it has 144 elements and the array of vertices to be removed is being calculate, to the next step when the vertices are being removed, but I can't see where the modification is being made.

Read more here

Unfortunately the function anyGenerator() (lowercase a) used in the SequenceType implementation has been deprecated and replaced with AnyGenerator() in Swift 2.2 causing the build issue.

Is there a reason to make the convenience methods public?
I've had a small issue when attempting to create graphs with them, as sometimes they work and sometimes they don't (depending on the type used).

For instance, take the following graph declaration:

var graph:UnweightedGraph<String> = UnweightedGraph<String>()

graph.addVertex("Hello")
graph.addVertex("World")
graph.addEdge("Hello", to: "World")

print(graph.description)

This prints the graph correctly.
However, when replacing the graph type from String to Int, the method (and the other convenience methods for addEdge) throws an ambiguous use error.

var graph2: UnweightedGraph<Int> = UnweightedGraph<Int>()

graph2.addVertex(123)
graph2.addVertex(456)
graph2.addEdge(0, to: 1, directed: false)        // Throws ambiguous use error
graph2.addEdge(0, to: 1)                         // Throws ambiguous use error
graph2.addEdge(UnweightedEdge.init(u: 0, v: 1, directed: false)) // Works fine (as intended)

print(graph2.description)

Hi,
I tried to use this library for PERT https://en.wikipedia.org/wiki/Program_evaluation_and_review_technique

i have something like this:

code:

    let A = Activity(a: 1,m: 2,b: 3, name: "A")
    let B = Activity(a: 2,m: 3,b: 4, name: "B")
    let C = Activity(a: 1, m: 2, b: 3, name: "C")
    let D = Activity(a: 1, m: 2, b: 3, name: "D")
    let E = Activity(a: 3, m: 4, b: 5, name: "E")
    let F = Activity(a: 2, m: 4, b: 6, name: "F")
    let G = Activity(a: 1, m: 3, b: 5, name: "G")
    let H = Activity(a: 3, m: 5, b: 7, name: "H")
    let I = Activity(a: 5, m: 7, b: 9, name: "I")
    
    let graph = UnweightedGraph<Activity>(vertices: [A,B,C,D,E,F,G,H,I])
    graph.addEdge(from: A, to: C, directed: true)
    graph.addEdge(from: A, to: D, directed: true)
    graph.addEdge(from: B, to: E, directed: true)
    graph.addEdge(from: D, to: F, directed: true)
    graph.addEdge(from: E, to: F, directed: true)
    graph.addEdge(from: C, to: G, directed: true)
    graph.addEdge(from: C, to: H, directed: true)
    graph.addEdge(from: F, to: I, directed: true)
    graph.addEdge(from: H, to: I, directed: true)
    
    print(graph.neighborsForVertex(E) ?? [])

struct Activity {
    let a: Int
    let m: Int
    let b: Int
    let name: String
}

extension Activity: Equatable {
    
    func estimationTime() -> Double {
        let time  = a + 4 * m + b
        return Double(time) / 6.0
    }
    
    func standardVariation() -> Double {
        let time = b - a
        return Double(time) / 6.0
    }
    
    //MARK: Equatable
    static public func ==(lhs: Activity, rhs: Activity) -> Bool {
        return lhs.estimationTime() == rhs.estimationTime()
    }
}

neightbors for E prints me something like:
[PERT.Activity(a: 3, m: 4, b: 5, name: "E"), PERT.Activity(a: 5, m: 7, b: 9, name: "I")]

Maybe i missunderstood something, but i think its not working correctly