graph-tool:2e0b08d3d025861ad3b5b692a3e9a8558ad2e478 commitshttps://git.skewed.de/count0/graph-tool/-/commits/2e0b08d3d025861ad3b5b692a3e9a8558ad2e4782012-05-02T09:27:43+02:00https://git.skewed.de/count0/graph-tool/-/commit/6b959e206bc7afcd126a11a943083713d5029e25Update copyright information2012-05-02T09:27:43+02:00Tiago de Paula Peixototiago@skewed.dehttps://git.skewed.de/count0/graph-tool/-/commit/0791156256a469b927d2c565f865ffe379a18d27Allow the disabling of probability caching in random_rewire()2012-04-30T01:52:00+02:00Tiago de Paula Peixototiago@skewed.de
This makes the code more efficient if the input parameter combinations
are much larger than the graph itself.https://git.skewed.de/count0/graph-tool/-/commit/7b2aa166d57295ef39db0e76eb838129fc598caaImplement vertex intersection in graph_union()2012-04-30T01:52:00+02:00Tiago de Paula Peixototiago@skewed.dehttps://git.skewed.de/count0/graph-tool/-/commit/bad741263b11d34b2433e0aa4c66de27c0ae32a6Generalize "probabilistic" random graph generation/rewiring to a blockmodel2011-08-27T00:30:04+02:00Tiago de Paula Peixototiago@skewed.de
This implements a general "blockmodel" generation / rewiring algorithm,
using Gibbs acceptence / rejection sampling (a.k.a Metropolis-Hastings).
This also implements some optimizations in the rewiring code, which
makes it more efficient on filtered graphs.https://git.skewed.de/count0/graph-tool/-/commit/8240714e21c4108907d40b9ffac0245f0702da90Several improvements to random_rewire() / random_graph()2011-08-24T15:30:56+02:00Tiago de Paula Peixototiago@skewed.de
This introduces several simplifications and corrections to the graph
rewire algorithm, to guarantee unbiased sampling.
Now a move is outright rejected if it produces a
self-loop/parallel-edge, instead of retried. This also adds a
"non-sweep" mode, where edges are rewired randomly, possibly with
repetition.
The edge moves are now simplified to the target of the edges only,
since swaping sources is redundant.
The number of iterations can now be explicitly modified, so it is not
necessary to call the function more than once, and it is emphasized in
the documentation that only after sufficiently many iterations can the
graph be guaranteed to be fully mixed.https://git.skewed.de/count0/graph-tool/-/commit/011d7b65b197dcfdef5474f8bb26e67b6d8995bbUpdate copyright year2011-02-10T14:23:12+01:00Tiago de Paula Peixototiago@skewed.dehttps://git.skewed.de/count0/graph-tool/-/commit/6758e857b6b6e36edcbe8927d2e61d027e5149b0Change domain to skewed.de2010-11-13T21:20:03+01:00Tiago de Paula Peixototiago@skewed.dehttps://git.skewed.de/count0/graph-tool/-/commit/5697be4a6007446e377b54555640f52de1fb1c88Add price and barabási-albert network generation2010-11-13T21:06:11+01:00Tiago de Paula Peixototiago@skewed.dehttps://git.skewed.de/count0/graph-tool/-/commit/6b3e626978a2b931b63ca9db1c5fdcb835d12cdfAdd lattice and geometric network generation2010-10-04T13:40:53+02:00Tiago de Paula Peixototiago@skewed.dehttps://git.skewed.de/count0/graph-tool/-/commit/63c2cae14ff3e3ac8e9ba9eed7a87afa1b1922d1Improve performace of random graph generation2010-05-03T12:40:58+02:00Tiago de Paula Peixototiago@skewed.de
Vectors are used now instead of unordered_sets, which dramatically
improves performace.https://git.skewed.de/count0/graph-tool/-/commit/b9bbc35016cbbdfc3d2bd1c79aee6ef7d6d50e31Update encoding and copyright information in source files2010-03-07T12:14:19+01:00Tiago de Paula Peixototiago@skewed.dehttps://git.skewed.de/count0/graph-tool/-/commit/1f28345e3fa6c28fd0516f8519aae5cc39ae4567Refactor random_graph()2010-02-20T21:00:52+01:00Tiago de Paula Peixototiago@skewed.de
Now the degree sequence is verified with Erdös-Gallai inequalities, and
the edges are connected in a deterministic fashion. The edges then are
rewired with the random_rewire() function.https://git.skewed.de/count0/graph-tool/-/commit/0d9607cf5ecc681b7cc3e70a6b1f10dcfff05f59Implement periodic delaunay triangulation2010-01-11T00:16:02+01:00Tiago de Paula Peixototiago@skewed.dehttps://git.skewed.de/count0/graph-tool/-/commit/d1aa20b7bd7c800ec6696cf2f8918f77a5fea691Add support for triangulation() in generation module2009-12-06T23:21:12+01:00Tiago de Paula Peixototiago@skewed.de
This also includes the library CGAL as a dependency.https://git.skewed.de/count0/graph-tool/-/commit/0ac9b1f61ab0f6e15d94f37a39f98a5dc682b605Implement graph_union()2009-09-06T19:15:16+02:00Tiago de Paula Peixototiago@skewed.de
This returns the union of two graphs, and optionally specified property
maps.https://git.skewed.de/count0/graph-tool/-/commit/b4249772c7ef2a579361505ad0d56640f962f145Resuscitate the line_graph() code2009-08-28T00:15:43+02:00Tiago de Paula Peixototiago@skewed.dehttps://git.skewed.de/count0/graph-tool/-/commit/7fb5d71da3df0b11c00f0343607c5b9ff3d15900Dump lambda::bind in favor of boost::bind2009-08-21T17:43:19+02:00Tiago de Paula Peixototiago@skewed.de
This is a large commit which replaces lambda::bind with boost::bind in
most parts of the code. This improves compilation time, and slightly
decreases compilation memory usage in some cases.https://git.skewed.de/count0/graph-tool/-/commit/217b9d7a323df0642c753d26b41a0f1bedc48da7Implement predecessor_tree()2009-08-17T19:30:30+02:00Tiago de Paula Peixototiago@skewed.dehttps://git.skewed.de/count0/graph-tool/-/commit/b0c2a3c362e38400b845d5fab62fb915d6b69bddMove random_rewire() to 'generation' module2009-08-04T15:59:56+02:00Tiago de Paula Peixototiago@skewed.dehttps://git.skewed.de/count0/graph-tool/-/commit/e1dd1665fff22a40a3b0e904f4401fc53bb18a98Improve correlated graph generation2009-07-15T20:09:47+02:00Tiago de Paula Peixototiago@skewed.de
random_graph() now uses a modified algorithm for generation of
correlated graphs, which is more efficient. Instead of giving a function
which returns a sample of the correlated target degree, the user must
give a function which will just compute its probability. This
probability will then be used to choose the edges.https://git.skewed.de/count0/graph-tool/-/commit/7505190fd3e1633593934c6fbb47e05b33bcf263Switch from boost::random to tr1::random2009-05-23T13:22:24+02:00Tiago de Paula Peixototiago@skewed.de
The generators from boost::random seem to have a bug which causes them
to be biased. The generators from tr1::random seem to be in better
shape.
See: <a href="http://thread.gmane.org/gmane.comp.lib.boost.user/48006" rel="nofollow noreferrer noopener" target="_blank">http://thread.gmane.org/gmane.comp.lib.boost.user/48006</a>https://git.skewed.de/count0/graph-tool/-/commit/6063ece02ba30a627efe530138a8c29e70b03f76Rewritten graph generation routine.2008-04-06T18:39:24+02:00Tiago de Paula Peixototiago@skewed.de
It is now much simpler, and works better.https://git.skewed.de/count0/graph-tool/-/commit/3cfff0cb2954d5c7d7603896b627713e1bea7665Split libgraph_tool into sub-modules and add test cases2008-02-17T11:57:13-03:00Tiago de Paula Peixototiago@skewed.de
This commit splits libraph_tool into different libraries:
- libgraph_tool_core
- libgraph_tool_clustering (*)
- libgraph_tool_community (*)
- libgraph_tool_correlations (*)
- libgraph_tool_distance (*)
- libgraph_tool_generation (*)
- libgraph_tool_layout (*)
- libgraph_tool_misc (*)
- libgraph_tool_stats (*)
It also adds the python sub-module 'test', which provides extensive unit
testing of the core functionality. The core library is fully functional
and all test pass successfully.
(*) -> module needs to be ported to new refactoring, and does not yet buildhttps://git.skewed.de/count0/graph-tool/-/commit/0b66e272dc498358778aa6d81c0dd99adbabb136Refactor metaprogramming engine2008-02-10T02:42:51-02:00Tiago de Paula Peixototiago@skewed.de
This is a huge commit which completely refactors the metaprogramming
engine which generates and selects (at run time) the graph view type and
the desired algorithm implementation (template instantiation) that runs
on it.
Things are laid out now as following. There exists a main underlying
graph type (GraphInterface::multigraph_t) and several other template
classes that mask it some way or another, in a hierarchic fashion:
multigraph_t -> filtered_graph (edges only, vertices only, both)
| | | |
| | | |
|-------(reversed_graph)--------|-----------|-----------|
| | | |
\------(UndirectedAdaptor)------------------------------/
The filtered_graph filters out edges and/or vertices from the graph
based on some scalar boolean property. The reversed_graph reversed the
direction of the edges and, finally, the UndirectedAdaptor treats the
original directed graphs as undirected, transversing the in- and
out-edges of each vertex indifferently. Thus, the total number of graph
view types is 12. (The option --disable-graph-filtering can be passed to
the configure script, which will disable graph filtering altogether and
bring the total number down to 3, to reduce compile time and memory
usage)
In general, some specific algorithm, implemented as a template function
object, needs to be instantiated for each of those types. Furthermore,
the algorithm may also depend on other types, such as specific
property_maps. Thus, the following scheme is used:
struct my_algorithm // algorithm to be implemented
{
template <class Graph, class PropertyMap>
void operator()(Graph *g, PropertyMap p, double& result) const
{
// ...
}
};
// in order for the above code to be instantiated at compile time
// and selected at run time, the run_action template function object
// is used from a member function of the GraphInterface class:
double GraphInterface::MyAlgorithm(string prop_name)
{
double result;
boost::any vprop = prop(property, _vertex_index, _properties);
run_action<>()(*this, bind<void>(my_algorithm(), _1, _2,
var(result)),
vertex_scalar_properties())(vprop);
return result;
}
The whole code was changed to reflect this scheme, but now things are
more centralized and less ad-hoc code needed to be
written. Unfortunately, due to GCC's high memory usage during template
instantiations, some of the code (namely all the degree correlation
things) had to be split in multiple compilation units... Maybe this will
change in the future if GCC gets optimized.
This commit also touches other parts of code. More specifically, the way
filtering gets done is very different. Now we only filter on boolean
properties, and with the above scheme, the desired implementation runs
with the correct chosen type, and no implicit type conversions should
ever happen, which would have a bad impact on performance.https://git.skewed.de/count0/graph-tool/-/commit/cb15708b4886861ae2486ddb7f437b02897072efSome reorganization and change check_filter() to run_action()2007-12-13T01:29:01-02:00Tiago de Paula Peixototiago@skewed.dehttps://git.skewed.de/count0/graph-tool/-/commit/06358b7c421166f0d00affcb15e5d28835765d87Further improvement of python interface2007-11-26T11:57:11-02:00Tiago de Paula Peixototiago@skewed.de
Vertices and edges can be accessed from the graph class, as such:
import graph_tool
g = graph_tool.Graph()
for v in g.vertices():
for e in v.out_edges():
# do something...
Additionally, the --edit-{vertex|edge|graph}-property was ported to the
new interface, and is working again, as it used to.
The Vertex and Edge class no longer have the 'get_property' and
'set_property' method. They'll be replaced by a new method of accessing
property maps.https://git.skewed.de/count0/graph-tool/-/commit/07be3fdc0ef03ce0ebd5dddb891424e14209c0bfCode cleanups, and cosmetic changes2007-11-04T01:11:17-02:00Tiago de Paula Peixototiago@skewed.de
Line breaks at column 80 were added, and all trailing whitespace was deleted. Code
comments were modified and some more were added.https://git.skewed.de/count0/graph-tool/-/commit/32990eb6578e4e80c41619770e897b5f7a5ff4c52007-07-11T04:09:23+00:00Tiago de Paula Peixototiago@skewed.de * ChangeLog: updated ChangeLog file with svn history
* src/graph/graph_filtering.hh: added add_edge() and remove_edge() functions for filtered graphs
* src/graph/shared_map.hh: included SharedContainer
* src/graph/graph_rewiring.cc: initial support for random graph rewiring
git-svn-id: <a href="https://svn.forked.de/graph-tool/trunk@114" rel="nofollow noreferrer noopener" target="_blank">https://svn.forked.de/graph-tool/trunk@114</a> d4600afd-f417-0410-95de-beed9576f240https://git.skewed.de/count0/graph-tool/-/commit/d199d4bbb5e20130cc90374b74fac026301812b7graph-tool is now GPL v32007-06-30T00:23:28+00:00Tiago de Paula Peixototiago@skewed.de
git-svn-id: <a href="https://svn.forked.de/graph-tool/trunk@101" rel="nofollow noreferrer noopener" target="_blank">https://svn.forked.de/graph-tool/trunk@101</a> d4600afd-f417-0410-95de-beed9576f240https://git.skewed.de/count0/graph-tool/-/commit/531da979425f51f6cb557b113e826e07682a98be_really_ change all tabs to spaces (sed, why have you forsaken me?)2006-11-15T02:28:15+00:00Tiago de Paula Peixototiago@skewed.de
git-svn-id: <a href="https://svn.forked.de/graph-tool/trunk@59" rel="nofollow noreferrer noopener" target="_blank">https://svn.forked.de/graph-tool/trunk@59</a> d4600afd-f417-0410-95de-beed9576f240https://git.skewed.de/count0/graph-tool/-/commit/6b764b67918c7221c0902a7da0ab7790333754a6converted tabs to spaces (emacs, why have you forsaken me?)2006-11-14T23:36:39+00:00Tiago de Paula Peixototiago@skewed.de
git-svn-id: <a href="https://svn.forked.de/graph-tool/trunk@58" rel="nofollow noreferrer noopener" target="_blank">https://svn.forked.de/graph-tool/trunk@58</a> d4600afd-f417-0410-95de-beed9576f240https://git.skewed.de/count0/graph-tool/-/commit/c27d124cb25cb953aa149ef8745daab04d8b6e7d* fix bug with mersenne twister rng seeding on amd642006-10-05T13:42:03+00:00Tiago de Paula Peixototiago@skewed.de* fix command line help
git-svn-id: <a href="https://svn.forked.de/graph-tool/trunk@49" rel="nofollow noreferrer noopener" target="_blank">https://svn.forked.de/graph-tool/trunk@49</a> d4600afd-f417-0410-95de-beed9576f240https://git.skewed.de/count0/graph-tool/-/commit/ed814636145877febd391f3c55fede2678994112* much improved directed correlation generation2006-07-30T22:03:11+00:00Tiago de Paula Peixototiago@skewed.de* fixed bug related to negative sampled degrees
git-svn-id: <a href="https://svn.forked.de/graph-tool/trunk@14" rel="nofollow noreferrer noopener" target="_blank">https://svn.forked.de/graph-tool/trunk@14</a> d4600afd-f417-0410-95de-beed9576f240https://git.skewed.de/count0/graph-tool/-/commit/b11d52fdac84d871bc85cafbfd1c51ad0295a9bbimproved correlated vertex sampling2006-07-24T05:24:42+00:00Tiago de Paula Peixototiago@skewed.de
git-svn-id: <a href="https://svn.forked.de/graph-tool/trunk@12" rel="nofollow noreferrer noopener" target="_blank">https://svn.forked.de/graph-tool/trunk@12</a> d4600afd-f417-0410-95de-beed9576f240https://git.skewed.de/count0/graph-tool/-/commit/a9aff6b4f95feb3681a1390508347c471465f9b0Initial import2006-07-10T01:34:03+00:00Tiago de Paula Peixototiago@skewed.de
git-svn-id: <a href="https://svn.forked.de/graph-tool/trunk@1" rel="nofollow noreferrer noopener" target="_blank">https://svn.forked.de/graph-tool/trunk@1</a> d4600afd-f417-0410-95de-beed9576f240