Giter Club home page Giter Club logo

metagraphs.jl's Introduction

MetaGraphs

Build Status Codecov branch

Project Status: As of 8 October 2021 MetaGraphs is no longer under active development. It will remain available on Github at sbromberger/MetaGraphs.jl. The JuliaGraphs organization will continue to maintain packages that use MetaGraphs and transition development over the long term.

LightGraphs.jl graphs with arbitrary metadata.

Documentation

Full documentation is available at GitHub Pages. Documentation for methods is also available via the Julia REPL help system.

Installation

Installation is straightforward: from the Julia pkg prompt,

add MetaGraphs

Example Usage

julia> using LightGraphs, MetaGraphs

# create a standard simplegraph
julia> g = path_graph(5)
{5, 4} undirected simple Int64 graph

# create a metagraph based on the simplegraph, with optional default edgeweight
julia> mg = MetaGraph(g, 3.0)
{5, 4} undirected Int64 metagraph with Float64 weights defined by :weight (default weight 3.0)

# create a directed metagraph based on the simplegraph, with optional default edgeweight
julia> mdg = MetaDiGraph(g, 3.0)
{5, 8} directed Int64 metagraph with Float64 weights defined by :weight (default weight 3.0)

# set some properties for the graph itself
julia> set_prop!(mg, :description, "This is a metagraph.")
Dict{Symbol,Any} with 1 entry:
  :description => "This is a metagraph."

# set properties on a vertex in bulk
julia> set_props!(mg, 1, Dict(:name=>"Susan", :id => 123))
true

# set individual properties
julia> set_prop!(mg, 2, :name, "John")
true

# set a property on an edge
julia> set_prop!(mg, Edge(1, 2), :action, "knows")
true

julia> using Dates: Date

# set another property on an edge by specifying source and destination
julia> set_prop!(mg, 1, 2, :since, Date("20170501", "yyyymmdd"))
Dict{Symbol,Any} with 2 entries:
  :since   => 2017-05-01
  :action => "knows"

# get all the properties for an element
julia> props(mg, 1)
Dict{Symbol,Any} with 2 entries:
  :id   => 123
  :name => "Susan"

# get a specific property by name
julia> get_prop(mg, 2, :name)
"John"

# delete a specific property
julia> rem_prop!(mg, 1, :name)
Dict{Symbol,Any} with 1 entry:
  :id => 123

# clear all properties for vertex 2
julia> clear_props!(mg, 2)
Dict{Symbol,Any} with 0 entries

# confirm there are no properties set for vertex 2
julia> props(mg, 2)
Dict{Symbol,Any} with 0 entries

# all LightGraphs analytics work
julia> betweenness_centrality(mg)
5-element Array{Float64,1}:
 0.0
 0.5
 0.666667
 0.5
 0.0

# using weights
julia> mg = MetaGraph(complete_graph(3))
{3, 3} undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)

julia> enumerate_paths(dijkstra_shortest_paths(mg, 1), 3)
2-element Array{Int64,1}:
 1
 3

julia> set_prop!(mg, 1, 2, :weight, 0.2)
true

julia> set_prop!(mg, 2, 3, :weight, 0.6)
true

julia> enumerate_paths(dijkstra_shortest_paths(mg, 1), 3)
3-element Array{Int64,1}:
 1
 2
 3

# use vertex values as indices
julia> G = MetaGraph(100)
{100, 0} undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)

julia> for i in 1:100
           set_prop!(G, i, :name, "node$i")
       end

julia> set_indexing_prop!(G, :name)
Set(Symbol[:name])

# nodes can now be found by the value in the index
julia> G["node4", :name]
4

# You can also find the value of an index by the vertex number (note, this behavior will dominate if index values are also integers)
julia> G[4, :name]
"node4"

julia> set_prop!(G, 3, :name, "name3") # or set_indexing_prop!(G, 3, :name, "name3")
Set(Symbol[:name])

metagraphs.jl's People

Contributors

affie avatar bovine3dom avatar danberge avatar dehann avatar dilumaluthge avatar femtocleaner[bot] avatar jpfairbanks avatar karajan9 avatar kescobo avatar leclere avatar matbesancon avatar pierretotale avatar r-barnes avatar sbromberger avatar serenity4 avatar simonschoelly avatar skleinbo avatar yuehhua avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar

metagraphs.jl's Issues

Metadata lost when a vertex is removed.

In the following snippet, I create a graph with 5 nodes each labeled from "1" to "5". I then delete the node labeled "1" (which happens to be the first node) using the rem_vertex! function. As a result, the label "5" is lost. Is it the intended behavior?

  let g = MetaGraph(Graph(5))
    for v in vertices(g)
      set_prop!(g, v, :name, string(v))
    end
    for v in vertices(g)
      if get_prop(g, v, :name) == "1"
        rem_vertex!(g, v)  
      end
    end
    map(v -> (v, get_prop(g, v, :name)), filter_vertices(g, :name))
  end
  
  julia> 3-element Array{Tuple{Int64,String},1}:
   (2, "2")
   (3, "3")
   (4, "4")

I understand why it is so (removing a vertex swaps it with the last vertex without copying the associated metadata) but that makes the metadata quite brittle.

dijkstra_shortest_paths() doesn't accept graph of type MetaGraphs

I'm solving the shortest path problem on a graph modelled using MetaGraphs.jl package. The function dijkstra_shortest_paths() returns an error.
ERROR: LoadError: MethodError: no method matching dijkstra_shortest_paths(::MetaGraphs.MetaDiGraph{Int64,Float64}, ::Int64, ::Int64). Is there a way around this problem or do I have to switch to SimpleWeightedGraphs.jl to model my graph?

Issue reversing a metagraph with function "reverse()"

Hi,
I am currently working on Julia with the MetaGraphs.jl package.

I have created the Graph with a dataset, the characteristic of the graph is that there's one start vertex and one end vertex. However the graph is created by creating all possible options so some edges which "take too much time" don't reach the final vertex. In order to have a decent graph for my next step/ an optimization problem. I am cleaning the graph by simply going through all edges and those who don't reach the end vertex are deleted. But this method is costly in time and I know a wiser way to do it. The method is simple:

  1. reversing the graph (end vertex becomes start vertex)
  2. Calculating the distance of all vertices from the start vertex
  3. erase the vertices which don't have a defined distance with the start vertex

I have created an example of a small digraph that would be the same type as mine:

module EssaiModule
using LightGraphs, MetaGraphs

g = DiGraph(8)
mg = MetaDiGraph(g, 1.0)

add_vertex!(mg)
add_edge!(mg,1,2)
add_edge!(mg,1,3)
add_edge!(mg,1,4)
add_edge!(mg,2,4)
add_edge!(mg,2,5)
add_edge!(mg,3,5)
add_edge!(mg,5,6)
add_edge!(mg,4,6)
add_edge!(mg,3,7)
add_edge!(mg,4,8)

rg=reverse(mg)

end

the end vertex is number 6 so normally I would like to erase edges 3->7 and 4->8 But I can't even start my function because I simply cannot reverse this graph.

I get the error message "LoadError: type MetaDiGraph has no field badjlist" I know it's because the graph is a metaGraph and not a lightGraph but shouldn't we be able to reverse a metagraph? it seems like a basic function that could be useful on many occasions while working with graphs.

convert `MetaWeights` object to matrix

Great package, thanks!

The function weights(g::SimpleWeightedGraphs.SimpleWeightedGraph) return a (sparse) matrix of the weights, while weights(g::MetaGraphs.MetaDiGraph) returns a MetaWeights object. Is there a built-in way to convert this to a matrix?

We shouldn't be allowed to set_indexing_prop! on nonexistent vertices

julia> g = MetaGraph(1)
{1, 0} undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)

julia> set_indexing_prop!(g, 2, :index, "v2")
Set(Symbol[:index])

julia> g.vprops
Dict{Int64,Dict{Symbol,Any}} with 2 entries:
  2 => Dict{Symbol,Any}(:index=>"v2")
  1 => Dict{Symbol,Any}(:index=>"index1")

Removing vertices fails on some graphs with self loops

Consider the following example. I construct a graph with some boolean data on the vertices and edges.

using LightGraphs
using MetaGraphs

G = Graph(6)

M = MetaGraph(G)

for (i, v) in enumerate(vertices(M))
    set_prop!(M, v, :node, isodd(i))
end

for i in 1:6
    for j in i:6
        add_edge!(M, i, j)
        set_prop!(M, i, j, :edge, isodd(i+j))
    end
end

Print the data:

for e in edges(M)
    println(e)
    println(props(M, e))
end

for v in vertices(M)
    println(v)
    println(props(M, v))
end

Now I try to remove some vertices

V = [v for v in filter_vertices(M, :node, true)]
println(V)

while length(V) > 0
    v = V[1]
    println(v)

    rem_vertex!(M, v)
    println("removed")

    V = [v for v in filter_vertices(M, :node, true)]
    println(V)
end

This crashes with the following out-of-bounds error:

ERROR: LoadError: BoundsError: attempt to access 4-element Array{Array{Int64,1},1} at index [5]                                                                                                                                                                                  
Stacktrace:                                                                                                                                                                                                                                                                      
 [1] rem_edge!(::LightGraphs.SimpleGraphs.SimpleGraph{Int64}, ::LightGraphs.SimpleGraphs.SimpleEdge{Int64}) at /home/raoul/.julia/v0.6/LightGraphs/src/graphtypes/simplegraphs/simplegraph.jl:142                                                                                
 [2] rem_vertex!(::LightGraphs.SimpleGraphs.SimpleGraph{Int64}, ::Int64) at /home/raoul/.julia/v0.6/LightGraphs/src/graphtypes/simplegraphs/SimpleGraphs.jl:105                                                                                                                  
 [3] rem_vertex!(::MetaGraphs.MetaGraph{Int64,Float64}, ::Int64) at /home/raoul/.julia/v0.6/MetaGraphs/src/MetaGraphs.jl:135                                                                                                                                                     
 [4] macro expansion at /home/raoul/LightGraphs Edge Removal Test.jl:38 [inlined]                                                                                                                                                                                                
 [5] anonymous at ./<missing>:?                                                                                                                                                                                                                                                  
 [6] include_from_node1(::String) at ./loading.jl:576                                                                                                                                                                                                                            
 [7] include(::String) at ./sysimg.jl:14                                                                                                                                                                                                                                         
 [8] process_options(::Base.JLOptions) at ./client.jl:305                                                                                                                                                                                                                        
 [9] _start() at ./client.jl:371 

The full output is:

Edge 1 => 1
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, false))
Edge 1 => 2
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, true))
Edge 1 => 3
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, false))
Edge 1 => 4
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, true))
Edge 1 => 5
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, false))
Edge 1 => 6
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, true))
Edge 2 => 2
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, false))
Edge 2 => 3
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, true))
Edge 2 => 4
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, false))
Edge 2 => 5
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, true))
Edge 2 => 6
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, false))
Edge 3 => 3
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, false))
Edge 3 => 4
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, true))
Edge 3 => 5
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, false))
Edge 3 => 6
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, true))
Edge 4 => 4
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, false))
Edge 4 => 5
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, true))
Edge 4 => 6
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, false))
Edge 5 => 5
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, false))
Edge 5 => 6
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, true))                                                                                                                                                                                                                                  
Edge 6 => 6                                                                                                                                                                                                                                                                      
Dict{Symbol,Any}(Pair{Symbol,Any}(:edge, false))                                                                                                                                                                                                                                 
1                                                                                                                                                                                                                                                                                
Dict{Symbol,Any}(Pair{Symbol,Any}(:node, true))                                                                                                                                                                                                                                  
2                                                                                                                                                                                                                                                                                
Dict{Symbol,Any}(Pair{Symbol,Any}(:node, false))                                                                                                                                                                                                                                 
3                                                                                                                                                                                                                                                                                
Dict{Symbol,Any}(Pair{Symbol,Any}(:node, true))                                                                                                                                                                                                                                  
4                                                                                                                                                                                                                                                                                
Dict{Symbol,Any}(Pair{Symbol,Any}(:node, false))                                                                                                                                                                                                                                 
5                                                                                                                                                                                                                                                                                
Dict{Symbol,Any}(Pair{Symbol,Any}(:node, true))                                                                                                                                                                                                                                  
6                                                                                                                                                                                                                                                                                
Dict{Symbol,Any}(Pair{Symbol,Any}(:node, false))                                                                                                                                                                                                                                 
[1, 3, 5]                                                                                                                                                                                                                                                                        
1                                                                                                                                                                                                                                                                                
removed                                                                                                                                                                                                                                                                          
[3, 5]                                                                                                                                                                                                                                                                           
3                                                                                                                                                                                                                                                                                
removed                                                                                                                                                                                                                                                                          
[3]                                                                                                                                                                                                                                                                              
3                                                                                                                                                                                                                                                                                
ERROR: LoadError: BoundsError: attempt to access 4-element Array{Array{Int64,1},1} at index [5]   
...        

I tried to be extra careful when removing vertices and not to invalidate the iterator.
Am I doing something wrong? What would be the correct way to remove all
vertices that match filter_vertices(M, :node, true)?

Outdated README

Under the installation section, instead of

julia> Pkg.add("MetaGraphs")

You can have something like this here,

julia> using Pkg
julia> Pkg.add("MetaGraphs")

# alternatively
julia> ]
(v1.0) pkg> add MetaGraphs

I can possibly raise a PR if you guys think similar.

rem_vertex! key not found when adding edges

I am implementing a function merges two vertices of a MetaDiGraph and retains the current edges

using LightGraphs, MetaGraphs

function joinedge!(graph, v1, v2)
    add_vertex!(graph)
    v = nv(graph)
    for i in vcat(outneighbors(graph,v1),outneighbors(graph,v2))
        add_edge!(graph,v,i)
    end
    for i in vcat(inneighbors(graph,v1),inneighbors(graph,v2))
        add_edge!(graph,i,v)
    end
    rem_vertex!(graph, max(v1,v2))
    rem_vertex!(graph, min(v1,v2))
    graph
end

When I run this on for example a wheelgraph

g=wheel_digraph(10)
mg=MetaDiGraph(g)
joinedge(mg,2,3)

I get the following error

ERROR: LoadError: KeyError: key 3 not found

I am guessing that this is related to #21 because when I change my code to

function joinedge!(graph, v1, v2)
    add_vertex!(graph)
    v = nv(graph)
    for i in vcat(outneighbors(graph,v1),outneighbors(graph,v2))
        if !(i in (v1,v2))
            add_edge!(graph,v,i)
        end
    end
    for i in vcat(inneighbors(graph,v1),inneighbors(graph,v2))
        if !(i in (v1,v2))
            add_edge!(graph,i,v)
        end
    end
    rem_vertex!(graph, max(v1,v2))
    rem_vertex!(graph, min(v1,v2))
    graph
end

it works. The difference here is that I am no longer adding edges to the joined vertex which produce self-loops.

MetaGraph of directed graph?

When I want to make a metagraph of a directed graph object, the underlying graph becomes an undirected graph? This behaviour is unwanted.
metagraph

support metadata in add_vertex!

When adding a new vertex to the MetaGraph the best way I found to give properties was the following

add_vertex!(g)

 set_props!(g, nv(g), Dict(:prop1=>prop1, :prop2 => prop2))

Is there a way to do this in a single line ? If not I suggest to add methods to add_vertex! to allow it.

Writing MetaGraph to graphviz (dot format)

Does anyone have code to render a MetaGraph as a dotfile?

I wrote this up real quick, but it probably doesn't cover all the use cases.

function dotfile(io::IO, g::MetaDiGraph)
    write(io, "digraph G {\n")
    for p in props(g)
        write(io, "$(p[1])=$(p[2]);\n")
    end

    for v in vertices(g)
        write(io, "$v")
        if length(props(g, v)) > 0
            write(io, " [ ")
        end
        for p in props(g, v)
            key = p[1]
            write(io, "$key=\"$(p[2])\",")
        end
        if length(props(g, v)) > 0
            write(io, "];")
        end
        write(io, "\n")
    end

    for e in edges(g)
        write(io, "$(src(e)) -> $(dst(e)) [ ")
        for p in props(g,e)
            write(io, "$(p[1])=$(p[2]), ")
        end
        write(io, "]\n")
    end
    write(io, "}\n")
end

Should we extend flow algorithm to MetaGraphs.jl?

I don't know if there is any perf benefits to use MetaGraphs with weights instead of weights matrices for current flow algorithms, but it would definitively makes sense to have those available.

Removing last vertex causes BoundsError

Removing the last vertex in a MetaDiGraph causes a BoundsError:

julia> g = MetaDiGraph(); add_vertices!(g, 3); rem_vertex!(g, 3)
ERROR: BoundsError: attempt to access 2-element Array{Array{Int64,1},1} at index [3]
Stacktrace:
 [1] rem_vertex!(::MetaGraphs.MetaDiGraph{Int64,Float64}, ::Int64) at /Users/epatters/.julia/v0.6/MetaGraphs/src/MetaGraphs.jl:154

How to create loop graph?

For example, two edges connecting "same" two vertices, like --O--

g = Graph(4)
add_edge!(g,1,2) # this is okay
add_edge!(g,1,2) # but this will fail

I have checked also MetaGraph, but did not find any information about this.

Package MetaGraphs does not have Random in its dependencies

Since updating to v0.6.2, I'm seeing new warnings

┌ Warning: Package MetaGraphs does not have Random in its dependencies:
│ - If you have MetaGraphs checked out for development and have
│   added Random as a dependency but haven't updated your primary
│   environment's manifest file, try `Pkg.resolve()`.
│ - Otherwise you may need to report an issue with MetaGraphs
└ Loading Random into MetaGraphs from project dependency, future warnings for MetaGraphs are suppressed.

Document MetaDiGraph

Hey graphs crew. So I am mucking around in your package, and found, by accident you all have implemented MetaDiGraphs! It's not documented. So I am making an issue to remind you all to document it :)

rem_prop! and clear_props! on vertex leaves dangling metaindex

Neither rem_prop!(g, v, :prop) or clear_props!(g, v) clears associated metaindex. Should rem_prop! and clear_props! clear the associated metaindex?

julia> g=MetaGraph()
{0, 0} undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)

julia> set_indexing_prop!(g,:name)
Set(Symbol[:name])

julia> add_vertex!(g,:name,"Original Name")
true

julia> clear_props!(g,1)
Dict{Int64,Dict{Symbol,Any}} with 0 entries

julia> set_prop!(g,1,:name,"New Name")
Set(Symbol[:name])

julia> g["New Name",:name]
1

julia> g["Original Name",:name]
1

julia> g.vprops
Dict{Int64,Dict{Symbol,Any}} with 1 entry:
  1 => Dict{Symbol,Any}(:name=>"New Name")

julia> g.metaindex
Dict{Symbol,Dict{Any,Integer}} with 1 entry:
  :name => Dict{Any,Integer}("New Name"=>1,"Original Name"=>1)
julia> g=MetaGraph()
{0, 0} undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)

julia> set_indexing_prop!(g,:name)
Set(Symbol[:name])

julia> add_vertex!(g,:name,"Original Name")
true

julia> rem_prop!(g,1,:name)
Dict{Symbol,Any} with 0 entries

julia> set_prop!(g,1,:name,"New Name")
Set(Symbol[:name])

julia> g["New Name",:name]
1

julia> g["Original Name",:name]
1

julia> g.vprops
Dict{Int64,Dict{Symbol,Any}} with 1 entry:
  1 => Dict{Symbol,Any}(:name=>"New Name")

julia> g.metaindex
Dict{Symbol,Dict{Any,Integer}} with 1 entry:
  :name => Dict{Any,Integer}("New Name"=>1,"Original Name"=>1)

can this handle directed graphs?

I want to add properties to vertices of directed graphs.

using MetaGraphs, LightGraphs

g = DiGraph(3)
simplecycles(g) # runs fine
mg = MetaGraph(g)
simplecycles(mg)

yields an error message suggesting that metagraphs is not accounting for the directedness of my graph:

ERROR: MethodError: no method matching simplecycles(::Type{SimpleTraits.Not{IsDirected{MetaGraph{Int64,Float64}}}}, ::MetaGraph{Int64,Float64})
Closest candidates are:
  simplecycles(::Type{IsDirected{##446}}, ::##446) where ##446 at /home/cokes/.julia/packages/SimpleTraits/CZOA2/src/SimpleTraits.jl:332
  simplecycles(::##446) where ##446 at /home/cokes/.julia/packages/SimpleTraits/CZOA2/src/SimpleTraits.jl:350
Stacktrace:
 [1] simplecycles(::MetaGraph{Int64,Float64}) at /home/cokes/.julia/packages/SimpleTraits/CZOA2/src/SimpleTraits.jl:350
 [2] top-level scope at none:0

weakly_connected_components fails with directed MetaGraphs

weakly_connected_components generates the following error consistently when used with a directed MetaGraph.

MethodError: Cannot convert an object of type MetaGraphs.MetaDiGraph{Int64,Float64} to an object of type LightGraphs.SimpleGraphs.SimpleGraph
This may have arisen from a call to the constructor LightGraphs.SimpleGraphs.SimpleGraph(...),
since type constructors fall back to convert methods.

I attach a Jupyter notebook file and a Julia (jl) file that should show the issue.
weaklyconnected.zip

DOTFormat does not escape punctuation

I am running into an issue where I have " inside my string which leads to issues when I am exporting my files to DOTFormat. (see line 18)
image
image
Another issue is that the edges are not enclosed in "'s
image

An issue while updating packages

I bumped into an issue while updating my packages. Can you please let me know what is happening here? I'm posting the stacktrace below.

julia> Pkg.update()
INFO: Updating METADATA...
INFO: Updating SimpleWeightedGraphs master...
INFO: Updating MetaGraphs master...
INFO: Computing changes...
WARNING: julia is fixed at 0.6.0 conflicting with requirement for SimpleWeightedGraphs: [1.0.0,∞)
WARNING: julia is fixed at 0.6.0 conflicting with requirement for MetaGraphs: [0.7.0-,∞)
ERROR: fixed packages introduce conflicting requirements for LightGraphs: 
         SimpleWeightedGraphs requires versions [1.0.0,∞) [none of the available versions can satisfy this requirement]
         MetaGraphs requires versions [0.13.0,∞) [none of the available versions can satisfy this requirement]
       available versions are 0.1.0, 0.1.1, 0.1.2, 0.1.3, 0.1.4, 0.1.5, 0.1.6, 0.1.7, 0.1.8, 0.1.9, 0.1.10, 0.1.11, 0.1.12, 0.1.13, 0.1.14, 0.1.15, 0.2.0, 0.2.1, 0.2.2, 0.3.0, 0.3.1, 0.3.2, 0.3.3, 0.3.4, 0.3.5, 0.3.6, 0.3.7, 0.4.0, 0.4.1, 0.4.2, 0.5.0, 0.5.2, 0.5.3, 0.5.4, 0.7.0, 0.7.1, 0.7.2, 0.7.3, 0.7.4, 0.7.5, 0.7.6, 0.7.7, 0.8.0, 0.9.0, 0.9.1, 0.9.2, 0.9.3, 0.9.4, 0.9.5, 0.10.0, 0.10.1, 0.10.2, 0.10.3, 0.10.4, 0.10.5, 0.11.0, 0.11.1 and 0.12.0
Stacktrace:
 [1] check_requirements(::Dict{String,Base.Pkg.Types.VersionSet}, ::Dict{String,Dict{VersionNumber,Base.Pkg.Types.Available}}, ::Dict{String,Base.Pkg.Types.Fixed}) at ./pkg/query.jl:222
 [2] resolve(::Dict{String,Base.Pkg.Types.VersionSet}, ::Dict{String,Dict{VersionNumber,Base.Pkg.Types.Available}}, ::Dict{String,Tuple{VersionNumber,Bool}}, ::Dict{String,Base.Pkg.Types.Fixed}, ::Dict{String,VersionNumber}, ::Set{String}) at ./pkg/entry.jl:496
 [3] update(::String, ::Set{String}) at ./pkg/entry.jl:461
 [4] (::Base.Pkg.Dir.##4#7{Array{Any,1},Base.Pkg.Entry.#update,Tuple{String,Set{String}}})() at ./pkg/dir.jl:36
 [5] cd(::Base.Pkg.Dir.##4#7{Array{Any,1},Base.Pkg.Entry.#update,Tuple{String,Set{String}}}, ::String) at ./file.jl:70
 [6] #cd#1(::Array{Any,1}, ::Function, ::Function, ::String, ::Vararg{Any,N} where N) at ./pkg/dir.jl:36
 [7] update() at ./pkg/pkg.jl:228

TIA

rem_vertex! breaks when indexing properties are in use

julia> g
{2902, 13599} directed Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)
julia> rem_vertex!(g, 4)
ERROR: The following properties are indexing_props and cannot be updated: Set(Symbol[:name])

Induced subgraphs

Functions like induced subgraph need to handle renumbering the vertices correctly. Or you could implement graphs with vertex set that is not a 1:nv range.

Type stable version?

Metadata as Dict{Symbol,Any} is type unstable. If you know that each node will have the same typed metadata, it might make more sense to have these be named tuples instead?

MetaGraph does not retain directed property of graph

When making a metagraph from a directed graph, the resulting graph is undirected.

In REPL, Julia 0.6.3:

julia> gr = DiGraph( 3 )
{3, 0} directed simple Int64 graph

julia> mgr = MetaGraph( gr )
{3, 0} undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)

reverse() on MetaDiGraph reverses vertex properties unneccessarily

Reversing a MetaDiGraph reverses the vertex properties unecessarily.

begin
    g=MetaDiGraph(StarDiGraph(4))
    set_indexing_prop!(g,:nodelabel)
    foreach(v->set_indexing_prop!(g,v,:nodelabel,"Vertex $v"),vertices(g))
    foreach(e->set_prop!(g,e,:edgelabel,"Edge ($(e.src),$(e.dst))"),edges(g))
end

The functionality besides the vprops appear to be correct.

g.graph.fadjlist==reverse(g).graph.badjlist #true as expected
g.graph.badjlist==reverse(g).graph.fadjlist #true as expected
get_prop(g,1,2,:edgelabel)==get_prop(reverse(g),2,1,:edgelabel) # true as expected

Vertex properties are incorrect

g["Vertex 1",:nodelabel]==reverse(g)["Vertex 1",:nodelabel] #false, which is not correct

vprops keys are reversed, causing the issue.

g.vprops
Dict{Int64,Dict{Symbol,Any}} with 4 entries:
  4 => Dict{Symbol,Any}(:nodelabel=>"Vertex 4")
  2 => Dict{Symbol,Any}(:nodelabel=>"Vertex 2")
  3 => Dict{Symbol,Any}(:nodelabel=>"Vertex 3")
  1 => Dict{Symbol,Any}(:nodelabel=>"Vertex 1")

reverse(g).vprops
Dict{Int64,Dict{Symbol,Any}} with 4 entries:
  4 => Dict{Symbol,Any}(:nodelabel=>"Vertex 1")
  2 => Dict{Symbol,Any}(:nodelabel=>"Vertex 3")
  3 => Dict{Symbol,Any}(:nodelabel=>"Vertex 2")
  1 => Dict{Symbol,Any}(:nodelabel=>"Vertex 4")

The forward graph
forward graph

and the incorrect reverse(g)
reverse graph

The correct reverse(g) should be
corrected graph

rem_vertex! fails to preserve edge metadata during the swap

MetaGraphs.rem_vertex! calls SimpleGraphs.rem_vertex! for the underlying simplegraph, which itself calls SimpleGraphs.rem_edge! to remove the edges from the target vertex v and the last vertex n, and then "swaps" the vertices by adding ns edges back to v.

The issue is that the internal edge manipulation doesn't preserve metadata since it's being called on the underlying simplegraph.

The fix is for MetaGraph's rem_vertex! to store the edge metadata for n prior to calling the simplegraph rem_vertex!, and then restore the metadata to v on return. This should be a relatively straightforward fix.

Utility for making MetaGraph from DataFrame

This something worth trying to integrate into library? Takes DataFrame edgelist (where entries can be names or strings, not necessarily sequential vertex ids) and returns MetaGraph. Obviously some places for generalization (directed versus undirected; edge attributes; etc.)

function create_metagraph_from_df(df, origin, destination)

    # Map node labels to indices
    nodes = [df[origin]; df[destination]]
    nodes = unique(nodes)
    sort!(nodes)

    vertex_names = DataFrame(Dict(:name => nodes))
    vertex_names[:vertex_id] = 1:nrow(vertex_names)

    # Merge in to original
    for c in [origin, destination]
        temp = rename(vertex_names, :vertex_id => Symbol(c, :_id), :name => c)
        df = join(df, temp, on=c)
    end

    g = DiGraph(nrow(vertex_names))
    mg = MetaDiGraph(g)
    for r in eachrow(df)
        add_edge!(mg, r[Symbol(origin, :_id)], r[Symbol(origin, :_id)])
    end

    for r in eachrow(vertex_names)
        set_prop!(mg, r[:vertex_id], :name, r[:name])
    end

    return mg
end

Check if graph is empty

Hi, I'd like to check if a graph is empty or not.

When I create a graph using MetaGraph() the printed output says:

empty undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)

Attempting to use isempty doesn't work because it is not defined for MetaGraph input. Is there a different function that returns whether a graph is empty? If not, what might be a decent approach so that I can make one.

I suppose this might, more fundamentally, apply to LightGraphs. Perhaps the code belongs there....

Thanks!

consistent handling of weight property

Right now if you do get_prop(mg, 1, 2, :weight) you get an error if Edge(1,2) uses the default weight. It would be nice if you always get the weight. Right now this would give a performance hit unless the :weight key is explicitly added to the Dict, so I'm not sure what the best way of handling it would be. Perhaps it would be worth adding a getweight function? I don't see that in the docs.

Warnings upon pre-compiling in Julia 1.0

not sure if this is important, but though I'd post it in case:

[ Info: Precompiling MetaGraphs [626554b9-1ddb-594c-aa3c-2596fe9399a5]
WARNING: could not import Base.start into MetaGraphs
WARNING: could not import Base.next into MetaGraphs
WARNING: could not import Base.done into MetaGraphs

How to update vertex / node color in a loop

New user here. I was wondering how we can update the vertex / node color in a loop and display the updated graph in the same loop as exampled below (the example is for Mathematica)

image

Couldn't find explicit documentation on this in LightGraphs or MetaGraphs. Appreciate any help.

set_prop!/set_props! return nothing

julia> g = MetaDiGraph()
{0, 0} directed Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)

julia> add_vertex!(g)
true

julia> set_prop!(g, 1, 2, :name, "hello2")

julia> set_props!(g, 1, 2, Dict(:name => "hello2"))

julia> g.eprops
Dict{LightGraphs.SimpleGraphs.SimpleEdge{Int64},Dict{Symbol,Any}} with 0 entries

to be consistent with LightGraphs, set_prop! and set_props! should return a Bool.

Adding weights is "undirected", getting weights "directed"

When I change a weight

using LightGraphs
using MetaGraphs
g = MetaGraph(2)
add_edge!(g, 1, 2)
set_prop!(g, 2, 1, :weight, 7.0)

the edge is treated as "undirected":

set_props!(g::MetaGraph, _e::SimpleEdge, d::Dict)
    e = LightGraphs.is_ordered(_e) ? _e : reverse(_e)
    [...]

If I then try to retrieve the value via get_prop vs weights

get_prop(g, 1, 2, :weight) == 7.0
get_prop(g, 2, 1, :weight) == 7.0
weights(g)[1, 2] == 7.0
weights(g)[2, 1] == 1.0 (defaultweight)

weights seems to treat the edges as "directed", which results in

dijkstra_shortest_paths(g, 1).dists[2] == 7.0
dijkstra_shortest_paths(g, 2).dists[1] == 1.0 (defaultweight)

without the graph being intentionally directed.

I use Julia v0.7 with LightGraphs v1.2.0 and MetaGraphs v0.6.0. If there are any questions, I'm happy to help.

rem_vertex! fails if indexing_props is set

The following properties are indexing_props and cannot be updated: Set(Symbol[:label])
in top-level scope at base/none
in rem_vertex! at MetaGraphs/kAvjf/src/MetaGraphs.jl:155
in set_props! at MetaGraphs/kAvjf/src/MetaGraphs.jl:274
in error at base/error.jl:33

get_prop on nonexistent property

What should get_prop(g, :nonexistent) do? Choices are

  1. throw a KeyError (current behavior)
  2. return nothing (since the property dictionary is Symbol=>Any, this is "type-stable")
  3. something else

I'm leaning towards 2) since I'm tired of having to check has_prop before calling get_prop.

This would also allow us to remove has_prop.

Tag 6.1.0

Can we tag 6.1 for the DOTFormat stuff?

Bug in `set_indexing_prop!` following `add_vertex!`

MWE:

julia> mg = MetaGraph(DiGraph())
{0, 0} undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)

julia> add_vertex!(mg)
true

julia> set_indexing_prop!(mg, 1, :a, 10)
Set(Symbol[:a])

julia> props(mg, 1)
Dict{Symbol,Any} with 1 entry:
  :a => 10

julia> mg.metaindex
Dict{Symbol,Dict{Any,Integer}} with 1 entry:
  :a => Dict{Any,Integer}(Pair{Any,Integer}(10, 1))

julia> add_vertex!(mg)
true

julia> set_indexing_prop!(mg, 2, :a, 20)
ERROR: KeyError: key 2 not found
Stacktrace:
 [1] getindex at ./dict.jl:474 [inlined]
 [2] set_indexing_prop!(::MetaGraphs.MetaGraph{Int64,Float64}, ::Int64, ::Symbol, ::Int64) at /Users/seth/.julia/v0.6/MetaGraphs/src/MetaGraphs.jl:361

It seems that the delete! call on L361 is the problem.

@kescobo - do you have a few minutes to chase this down?

clear_props! type-unstable

Following the example from the README, calling clear_props! several times returns different types:

julia> clear_props!(mg, 2)
Dict{Int64,Dict{Symbol,Any}} with 1 entry:
  1 => Dict{Symbol,Any}(:id=>123)

julia> clear_props!(mg, 2)
false

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.