of the form

em  = EdgeMap(g, e -> f(e))
vm = VertexMap(g, i -> f(i))

g = erdos_renyi(50, 0.1) gives a complete graph instead of a random graph with edge existence probability 0.1.

pull request here JuliaLang/METADATA.jl#8085

The tag name "v"0.4.0"" is not of the appropriate SemVer form (vX.Y.Z).
cc: @CarloLucibello

It would make sense to have as the default type the more flexible Network instead of Graph, so that by default one is able to have graph/edge/vertex property maps.

For the time being rebuild! just applies sort! on each vector of the adjacency list.
It should also

• union!
• check that if j is in the adjlist of i, also i is in the adjlist of j

fastest known algorithm is Algorithm 4 here
https://arxiv.org/pdf/1607.00547.pdf

for the Network type, and more generally for graphs with indexed edges.

Right now edges are iterated in lexycographic order for (src,dst):

julia> g= Network(10,20)
Network(10, 20) with [] graph, [] vertex, [] edge properties

julia> collect(edges(g))
20-element Array{Erdos.IndexedEdge,1}:
 (1=>4,4)  
 (1=>7,11) 
 (1=>5,16) 
 (1=>9,17) 
 (2=>3,7)  
 (2=>9,12) 
 (3=>10,9) 
 (3=>7,10) 
 (3=>8,18) 
 (4=>10,2) 
 (4=>5,5)  
 (4=>6,6)  
 (4=>7,15) 
 (5=>9,1)  
 (5=>6,19) 
 (6=>8,14) 
 (6=>9,20) 
 (7=>9,3)  
 (8=>9,8)  
 (8=>10,13)

as discovered in #33

Probably an error due to ParserCombinator

For the time being matching with continuous weights is roughly rounded to an integer matching problem and solved with BlossomV. This sometimes produces incorrect results (TODO: add failiing example)

Since BlossomV supports conitnuous weights, the BlossomV.jl should compile and expose both versions (integer and float). An attempt is made in mlewe/BlossomV.jl#10

For the time being, building the docs locally and deploying with mkdocs gh-deploy

... instead of Union{Vector{T},Dict{Int,T}}

I have a problem precompiling module Erdos, related to BlossomV (see the screenshot).

Then, when I run BinDeps.debug("BlossomV") I get the following message
INFO: Reading build script...
The package declares 2 dependencies.

• Library "blossom5int32"
  • Providers:
    • Simple Build Process
• Library "blossom5float64"
  • Providers:
    • Simple Build Process

But again, building BlossomV gives me:

Does anyone know how to fix this issue?

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.

If you'd like for me to do this for you, comment TagBot fix on this issue.
I'll open a PR within a few hours, please be patient!

Mainly due to the use of the wrong data structures (e.g. finding, deleting and inserting in the middle of arrays)

At the present time it creates a Dict.
The same holds for eprop(g, name, e).

a list of the things in the docs that could be improve

• Need some examples of edge maps use and constructors both in the docstrings and in the page https://carlolucibello.github.io/Erdos.jl/maps/
• Basic Interface: split in paragraphs or in different pages and add some comments. Also an index would be of help
  https://carlolucibello.github.io/Erdos.jl/core/
• README: give some prominence to the possibility to work with networks
• add some IJulia examples

...when the map is over an undirected graph. This can be done wrapping the matrix A in s=Symmetric(A) and accessing the elements thorugh s.data[u,v], with u<=v.

Some efficient and easy to implement algorithms have appeared recently for the problem of graph dismantling. We should implement them in LightGraphs

One is here

http://arxiv.org/pdf/1506.08326 (CI algorithm)

and another here

http://arxiv.org/pdf/1607.03276v1.pdf (CoreHD algorithm)

This issue is probably due to ParserCombinator.jl: ref andrewcooke/ParserCombinator.jl#22

The problem is not fixed by #30

Would be nice to find a substitute for ParserCombinator.jl, since it is slow and not actively maintained

The tag name "0.1.1" is not of the appropriate SemVer form (vX.Y.Z).
cc: @CarloLucibello

Greetings,

We are some security researchers who have built a scanner to detect known security weaknesses. For your repository, we have found instances of INSECURE-HTTP in the following locations:

Location-1:

Please give us feedback. Do you think these are valid instances on security weaknesses? Will you fix them?

maybe use just one method : community_detection(g, algo=ALGX, ....)

Also some of the tests wich intermittently fail on Travis, and are now deactivated (in particular for label propagation), should be changed and reactivated

• Erdos.jl already addressed in #43
• Clustering.jl's ones here JuliaStats/Clustering.jl#82
• ParserCombinator.jl first attempt here andrewcooke/ParserCombinator.jl#21

TODO: As soon as 0.6 is out, drop julia 0.5 support and make use of 0.6 syntax (e.g. where).
People on 0.5 will use last 0.5-compatible tagged version

using BenchmarkTools.jl. Shouldn't be too difficult

At /src/shortestpaths/astar.jl line 49 there is an escape character . It should be removed in order to avoid an invalid syntax ERROR during compilation. In Julia 0.7.0. there are also several WARNINGS easy to fix.

For the core interface, the time complexity should be guaranteed by all (user defined) graph types

Here is a partial list of missing algorithms. For hard problems (as most problems in this list) both exact and heuristic solvers should be implemented.

Problems not yet addressed in Erdos

• coloring for fixed q
• coloring number and optimal coloring
• maximum independent set (also known as vertex packing problem)
• maximum weight independent set (weights on vertices)
• minimum vertex cover
• graph isomorphism
  • fastest known exact algorithm is Algorithm 4 here https://arxiv.org/pdf/1607.00547.pdf
• prize collecting steiner tree
  • message passing heuristic https://arxiv.org/abs/1309.0346
• travelling salesman problem
• clique problems
• maximum weight b-matching
  • efficient exact solver (Edmond's)
  • linear programming as bootstrap for interger programming
  • message passing heuristic http://www.jmlr.org/proceedings/papers/v15/huang11a/huang11a.pdf

New algorithms for "old" problems

• Community Detection
  • SCoDA https://arxiv.org/pdf/1703.02955.pdf
• Matching
  • Hungarian Algorithm https://github.com/Gnimuc/Hungarian.jl

Most problems can be formulated as integer programming problems and solved (at least for small instances) through JuMP and generict IP solver.

Simulated Annealing could be implemented as a general heuristic solver.
See also https://github.com/carlobaldassi/RRRMC.jl.

For most problems message passing heuristics (belief propagation) can be found in the literature

• ensure compatibility with existing plotting libraries
• eventually build a new (interactive?) (opengl?) visualization library

It would be nice to have

for (e, val) in emap
   ....
end

for (v, val) in vmap
   ....
end

An option for an iterator would be

(emap[e] for e in edges(emap.g) if haskey(emap, e))

Hello,

I have just installed Julia v1.0 and when I run
import Pkg; Pkg.add("Erdos")
I get the following error message:

Updating registry at ~/.julia/registries/General
Updating git-repo https://github.com/JuliaRegistries/General.git
Resolving package versions...
ERROR: Unsatisfiable requirements detected for package Erdos [90d7349d]:
Erdos [90d7349d] log:
├─possible versions are: [0.1.0, 0.1.2-0.1.3, 0.2.0, 0.3.0, 0.4.0, 0.5.0, 0.6.0-0.6.3] or uninstalled
├─restricted to versions * by an explicit requirement, leaving only versions [0.1.0, 0.1.2-0.1.3, 0.2.0, 0.3.0, 0.4.0, 0.5.0, 0.6.0-0.6.3]
└─restricted by julia compatibility requirements to versions: uninstalled — no versions left
Stacktrace:
[1] #propagate_constraints!#61(::Bool, ::Function, ::Pkg.GraphType.Graph, ::Set{Int64}) at /Users/osx/buildbot/slave/package_osx64/build/usr/share/julia/stdlib/v1.0/Pkg/src/GraphType.jl:1005
[2] propagate_constraints! at /Users/osx/buildbot/slave/package_osx64/build/usr/share/julia/stdlib/v1.0/Pkg/src/GraphType.jl:946 [inlined]
[3] #simplify_graph!#121(::Bool, ::Function, ::Pkg.GraphType.Graph, ::Set{Int64}) at /Users/osx/buildbot/slave/package_osx64/build/usr/share/julia/stdlib/v1.0/Pkg/src/GraphType.jl:1460
[4] simplify_graph! at /Users/osx/buildbot/slave/package_osx64/build/usr/share/julia/stdlib/v1.0/Pkg/src/GraphType.jl:1460 [inlined]
[5] macro expansion at ./logging.jl:319 [inlined]
[6] resolve_versions!(::Pkg.Types.Context, ::Array{Pkg.Types.PackageSpec,1}) at /Users/osx/buildbot/slave/package_osx64/build/usr/share/julia/stdlib/v1.0/Pkg/src/Operations.jl:338
[7] #add_or_develop#58(::Array{Base.UUID,1}, ::Function, ::Pkg.Types.Context, ::Array{Pkg.Types.PackageSpec,1}) at /Users/osx/buildbot/slave/package_osx64/build/usr/share/julia/stdlib/v1.0/Pkg/src/Operations.jl:1164
[8] #add_or_develop at ./none:0 [inlined]
[9] #add_or_develop#13(::Symbol, ::Bool, ::Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}, ::Function, ::Pkg.Types.Context, ::Array{Pkg.Types.PackageSpec,1}) at /Users/osx/buildbot/slave/package_osx64/build/usr/share/julia/stdlib/v1.0/Pkg/src/API.jl:64
[10] #add_or_develop#12 at ./none:0 [inlined]
[11] #add_or_develop at ./none:0 [inlined]
[12] #add_or_develop#11 at /Users/osx/buildbot/slave/package_osx64/build/usr/share/julia/stdlib/v1.0/Pkg/src/API.jl:28 [inlined]
[13] #add_or_develop at ./none:0 [inlined]
[14] #add_or_develop#10 at /Users/osx/buildbot/slave/package_osx64/build/usr/share/julia/stdlib/v1.0/Pkg/src/API.jl:27 [inlined]
[15] #add_or_develop at ./none:0 [inlined]
[16] #add#18 at /Users/osx/buildbot/slave/package_osx64/build/usr/share/julia/stdlib/v1.0/Pkg/src/API.jl:69 [inlined]
[17] add(::String) at /Users/osx/buildbot/slave/package_osx64/build/usr/share/julia/stdlib/v1.0/Pkg/src/API.jl:69
[18] top-level scope at none:0

Could anyone help to solve this problem?

where some value is assumed as a default for any element, unless another value is specifically assigned to that element