gyuho / goraph Goto Github PK

Need to implement graph traversal algorithm with some visualization

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

this line nil error can denote true,I think a bool return value is a duplicate.

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)
}

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?

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.

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?

Most basic tree

the direction of an edge from node "s" to "c" with weight 9 in graph_01.png is wrong

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

Right now, it is implemented in map and value is fixed in float type. We need interface.

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?

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)

For the ones too big to fit in memory

Need to implement

topologicalSortVisit can be converted to an iterative method instead of recursion.

Hello,

great library. Is there a way to export the graph to svg or are there plans?

edit: i guess that should be done with graphviz?

Thanks,
Gerald

The function JSONGraph loads from a JSON graph, but how do I write it (eg to use the conversion to dot).

goraph should contain only graph related packages.

Just call the graphviz commands to export .DOT file to png

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

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.

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?