Package goraph implements graph data structure and algorithms.

Hi, I started Go and I was searching for a graph library in Go, and found this project. Looks good to me.

I think you plan to implement a module to import/export from/to dot language from and it's really a good idea. But, how about other visualization technique such as treemap?

HeiankyoView, I have implemented, is another method of visualizing tree structure and now implemented in Python. https://github.com/akiradeveloper/HeiankyoView I have a plan to rewrite this in Go and probably the best way is to construct it on top of standard graph library, which I suppose this is.

If I implement HeiankyoView on top of goraph. Will you merge? (drill down viz/heiankyoview)

or do you introduce me better graph library?

Hi,

When I try to build shortest_path.go, I get the following error messages:

.\shortest_path.go:54: undefined: nodeDistanceHeap .\shortest_path.go:72: undefined: nodeDistance .\shortest_path.go:86: undefined: nodeDistance

I couldn't find any reference to nodeDistanceHeap or nodeDistance in the project. Am I missing something?

Hi, and thank you for this package.

I notice a slight problem when adding edge before declaring both vertex: the edge is not added silently. I think it should either complain or directly add a new vertex.

func Works() {
    workingGraph := graph.NewDefaultGraph()
    workingGraph.AddVertex("A")
    workingGraph.AddVertex("B")
    workingGraph.AddEdge("A", "B", 1)
    fmt.Printf("Graph is printing: %v", workingGraph)
    order, _ := graph.TopologicalSort(workingGraph)
    fmt.Printf("Order is right: %v\n\n", order)
}

func Fails() {
    workingGraph := graph.NewDefaultGraph()
    workingGraph.AddVertex("A")
    workingGraph.AddEdge("A", "B", 1) // Silently accept Edge on non-existent
    workingGraph.AddVertex("B")
    fmt.Printf("Graph is not printing: %v\n", workingGraph)
    order, _ := graph.TopologicalSort(workingGraph)
    fmt.Printf("Order is wrong: %v\n", order)
}

GetNode currently returns nil for a non-existent node, however other functions (for example GetTargets) return an error for a non-existent node. This patch adds an error return value to GetNode to make it consistent with the rest of the package.

This patch is not a merge candidate because it includes import path changes. These were necessary in order to run travis build but clearly another solution is needed.

Hi,

Just had a quick thought about how we could implement these patterns to nanomsg (https://github.com/gdamore/mangos) in order to dynamic distributed searches like (https://daniel-j-h.github.io/post/distributed-search-nanomsg-bond/). I am working on an advanced version of Iris ( http://iris.karalabe.com/) with an Etcd store in order to dynamically dispatch queries.

That would be awesome.

Hope u can match my idea.

Cheers, Luc Michalski

https://github.com/gyuho/goraph/blob/refactor/graph/graph.go#L280

why not just,d.outEdge[src] = append(d.OutEdges[src][:idx],d.OutEdges[src][idx+1:]...)? Is there any reason for efficiency?

Whilst it seems to maintain the correct ordering, the Topological sort seems to vary slightly the order of results in between executions. Perhaps there is a map in there some where giving it random order?

Hi @gyuho ,

I added NewGraphFromYAML function to graph.go to generate a graph from yaml file, based on NewGraphFromJSON function. Could you take a look at this PR?

I think buffer size 1024 should NOT be hard-coded into the source code, but I don't know best practices to deal with io.Reader because I don't have much experiences with golang...

d := make([]byte, 1024)
for {
	n, err := rd.Read(d)
	if err == io.EOF {
		break
	}

	data = append(data, d[0:n]...)
}

IMO, file parsers such as NewGraphFrom... should be divided into another file from graph.go because of its readability, however, I have just added the NewGraphFromYAML function right below the NewGraphFromJSON function.

Currently GetNode returns nil (zero value for map) if GetNode is passed a non-existent ID. Other functions in the package return an error value in this case, func (g *graph) GetTargets(id ID) (map[ID]Node, error).

This patch adds an error return value to GetNode(). Also updates all call sites and tests. Slightly improves error detection in Prim() (minimum_spanning_tree.go)

Test code in the testdata directory breaks the convention used by certain build system, where "testdata" only contains data such as images and blobs.

This change moves the test data to a "testgraph" directory, to avoid breaking such conventions.

Sorry for sending a patch before discussing it. If this is not acceptable, feel free to reject this change. :)

Also updating the copyright notice, as required by my employer.

package github.com/gyuho/goraph/... imports github.com/gyuho/goraph/algorithm/tsdfs imports github.com/gyuho/goraph/algorithm/tsdfs: /usr/local/google/home/samschaevitz/gocode/src/github.com/gyuho/goraph/algorithm/tsdfs/tsdfs_test.go:26:4: expected 'package', found 'EOF'

Situation:

• need for a count of all edge of a Graph
• need for a count of all edge of a Node

Problem:

• Graph Interface does not provide such a function
• Node does not provide such a function

Situation: I have a graph with close to 2 Millions nodes and many more edges

Problem: call to Tarjan provokes a stack limit error

Note: goraph is great piece of SW and this is a minor issue. A work around was found.

row  1726 4030 MiBGraph nb of nodes                1992378
runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow

runtime stack:
runtime.throw(0x551515, 0xe)
        C:/Go/src/runtime/panic.go:608 +0x79
runtime.newstack()
        C:/Go/src/runtime/stack.go:1008 +0x737
runtime.morestack()
        C:/Go/src/runtime/asm_amd64.s:429 +0x97

goroutine 1 [running]:
runtime.interhash(0xc0f0001450, 0xe8426d0d, 0x42a209)
        C:/Go/src/runtime/alg.go:140 +0x182 fp=0xc0f0001368 sp=0xc0f0001360 pc=0x402f92
runtime.mapaccess2(0x524820, 0xc0271566f0, 0xc0f0001450, 0x3011f, 0x0)
        C:/Go/src/runtime/map.go:456 +0x78 fp=0xc0f00013b0 sp=0xc0f0001368 pc=0x40d038
github.com/gyuho/goraph.(*graph).unsafeExistID(...)
        C:/Users/Tensor/go/src/github.com/gyuho/goraph/graph.go:220
github.com/gyuho/goraph.(*graph).GetTargets(0xc027156780, 0x571f00, 0xc01d2b91a0, 0x0, 0x0, 0x0)
        C:/Users/Tensor/go/src/github.com/gyuho/goraph/graph.go:389 +0xde fp=0xc0f00014d0 sp=0xc0f00013b0 pc=0x4fc4ae
github.com/gyuho/goraph.tarjan(0x573200, 0xc027156780, 0x571f00, 0xc01d2b91a0, 0xc00009c0c0)
        C:/Users/Tensor/go/src/github.com/gyuho/goraph/strongly_connected_components.go:138 +0x1fe fp=0xc0f00016d0 sp=0xc0f00014d0 pc=0x4fd00e
github.com/gyuho/goraph.tarjan(0x573200, 0xc027156780, 0x571f00, 0xc01d2b9220, 0xc00009c0c0)
        C:/Users/Tensor/go/src/github.com/gyuho/goraph/strongly_connected_components.go:148 +0x4a3 fp=0xc0f00018d0 sp=0xc0f00016d0 pc=0x4fd2b3
github.com/gyuho/goraph.tarjan(0x573200, 0xc027156780, 0x571f00, 0xc01d2b92e0, 0xc00009c0c0)
        C:/Users/Tensor/go/src/github.com/gyuho/goraph/strongly_connected_components.go:148 +0x4a3 fp=0xc0f0001ad0 sp=0xc0f00018d0 pc=0x4fd2b3
github.com/gyuho/goraph.tarjan(0x573200, 0xc027156780, 0x571f00, 0xc04810c6e0, 0xc00009c0c0)

goraph uses errors.New() to create errors to signal missing graph nodes in numerous places. e.g.

return fmt.Errorf("%s does not exist in the graph.", id1)

It would be better to create specific error type instead. This would reduce code duplication and would allow callers to distinguish missing nodes from other things that may have go wrong when using the library.

Hi, As I want to generate a shortest path tree, can I use the the Dihkstra function in goraph to generate a shortest path tree if I do not specified the target node.