{5} Accepted, Active Tickets by Owner (Full Description) (23 matches)

List tickets accepted, group by ticket owner. This report demonstrates the use of full-row display.

gemacke (21 matches)

Ticket Summary Component Milestone Type Created
#4193 Fix code that assumes edges initialized in CSR graph aren't reordered 1.2 defect 12/05/14

The CSR graph used to leave edges in the order they were passed to init(). The update in r4026 was a rewrite to the CSR graph to reduce memory usage and add internal properties. This broke the assumption that edges were left in the order they were passed to init() for directed and bidirectional graphs. Not having this assumption is the right way to do it, but there is code that makes the assumption. We need to fix all the code that expects the ordering of the edges to not change.

#4040 remove_vertices and edges in adjacency_list.hpp 1.2 defect 08/23/11

We should be able to remove vertices and edges (and a single vertex or edge) without associated property maps. The current code doesn't allow this. The call to removeEdges at Line 381 doesn't compile if there is no emap, and won't work anyway since there aren't checks in case emap is null.

#4131 Change vertex betweenness algorithm 1.2 defect 05/25/12

The current vertex betweenness algorithm doesn't perform very well on the XMT. When I tried to write a Qthreads version, the performance was HORRIBLE. We need a new algorithm because the locking in this one kills performance.

One possibility is the algorithm described in "A faster parallel algorithm and efficient multithreaded implementations for evaluating betweenness centrality on massive datasets."

#3877 Clean up the breadth first search code. 1.2 enhancement 08/13/09

There are multiple implementations of breadth first search. Some of them are old and deprecated and should be removed. We want the good one to be located in breadth_first_search.hpp.

#3905 Improve mutable graph concepts. 1.2 enhancement 03/04/10

We need to improve the mutable graph concepts. This includes making the add_vertices() and add_edges() work well and correctly and adding remove_vertices() and remove_edges().

#3960 Add bidirectional support for adjacency list adapter 1.2 enhancement 08/20/10

You can't create a bidirectional graph with an adjacency list adapter. We need to add the code to allow this.

#3961 Move classes and such in the mtgl namespace that are not intended to be used by library users into the namespace mtgl::detail 1.2 enhancement 08/20/10

There are lots of classes, functions, etc. that are subpieces of other code that are currently polluting the mtgl namespace. These are things that are used by other things in the mtgl namespace but that are never intended to be used by a normal library user. One example is the static_vertex_iterator class in mtgl/static_graph_adapter.hpp.

Let's follow the boost convention and put all of these subpieces into the namespace mtgl::detail.

#3962 Get rid of hot spot in the constructor of xmt_hash_table_adapter 1.2 enhancement 08/20/10

There's a hot spot in the constructor of xmt_hash_table_adapter. The constructor uses xmt_hash_table::visit() where the visitor increments a shared index by one. Switch to using the range_iterators and the for all streams pragma to get rid of the hot spot.

#3973 Standardize the graph search visitor interface 1.2 enhancement 10/26/10

We need to standardize the visitor interface across all searches provided by MTGL. We will definitely provide a BFS and some form of psearch that is the closest we can get to DFS while still being parallel. Standardize may not mean that each visitor has the exact same set of functions but that they share functions where appropriate. We also need to document the visitor concepts when they are finalized.

We probably want to try to imitate the BGL interface as much as possible deviating only where it causes performance problems. BGL has a different set of functions for visitors used by  BFS and  DFS. They share functions between the BFS and DFS visitors where appropriate, but there are different important events since the searches are different.

It is useful to get edges at different points in the search vs. just getting the vertices. This might be more expensive, though, as we'll need to create the edge descriptor objects.

#3979 need option to synchronize edge_property_map updates with edge deletion in adjacency_list 1.2 enhancement 11/17/10

This has been a known issue for some time, but the issue is being forced because I need a solution now. The quickest way would be to pass the map into the remove_vertices and remove_edges functions. It remains to work out a reasonable API.

#3984 Do we need to switch to ints instead of unsigned ints for size types? 1.2 enhancement 02/24/11

As part of the recent fix to bug 759547 in release 1.5 of the XMT runtime, certain optimizations for unsigned integers have been turned off by default. There were problems caused by overflows due to unsigned ints having values greater than those storable by signed ints.

Is this going to impact performance of MTGL considering that we use unsigned long (same as unsigned int on XMT) for most of our size types? Should we change to using long instead? It is unlikely that any of our size types will be larger than the value held by a 64 bit integer. From a design standpoint, it makes more sense to have unsigned integer values as that is what the underlying data really is, however, if it is necessary to get better performance, I don't see a problem with switching to signed integers.

#3985 Switch to using exact width integer types 1.2 enhancement 02/24/11

Since we are running on many different platforms (XMT, various Linux distros, OS X) that have different sizes for the built-in types such as int, it might make sense for us to start using exact width integer types such as int64_t. This would make portability issues easier to deal with, and it would insure that the same sized types would be used across all platforms.

#4046 Add internal property maps 1.2 enhancement 10/04/11

MTGL currently supports only external property maps. It would be very useful to support internal property maps as well. External property maps are intended only to exist temporarily. For instance, a color array used by BFS. Internal property maps are intended to exist for the lifetime of the graph. If vertices or edges are added or deleted, the internal properties for those objects are updated as necessary.

Currently, MTGL uses external property maps where we should be using internal property maps. This causes several problems. First, it requires edges and vertices to have ids. If a user only needs internal properties, then ids are not necessary. Second, it requires edges to be assigned ids based on the order they are given in the sources and dests array passed to init() which requires extra unnecessary storage and extra indirection when accessing edge ids. The reason this is necessary is so that edge properties that exist at graph creation time can still be associated with the correct edge in the graph.

#4049 Improve error reporting in read_matrix_market() and read_dimacs() 1.2 enhancement 10/05/11

This ticket assumes responsibility for unfinished work in #3981.

The functions read_matrix_market() and read_dimacs() report errors in the main loops that parse the text by printing an error message and calling exit(). I did this originally because it parallelized okay and still gave the user error feedback. However, this doesn't fit in with the spirit of the read_* functions returning a boolean to indicate an error. Changing the way this is done may also improve performance of the loops.

One possibility is to keep an error buffer and an error count. When an iteration encounters an error, it could increment the error count. If the returned value of the increment is 0, that thread would copy its error message to the buffer. That way there would be no loop exits inside the loops. After the loops, print out the error message and return false if the error count is greater than 0.

This method needs to be tested to see how it parallelizes. It needs to pass canal and have the same or better performance in tests. If this doesn't work, then some other method needs to be used.

#4086 Improve the sort interace 1.2 enhancement 01/12/12

We need a single sorting function called "sort" that calls the best sorting algorithm depending on the platform. We want to make this as simple as possible. In most cases people don't care about the specific algorithm as long as it is good. For cases where other algorithms are appropriate, we can provide specifically named functions.

Where should sorting algorithms be located? Maybe in the "algorithm" header like in C++.

We also need to support sorting structures other than C-style arrays. At a minimum, dynamic_array. If possible, using the STL-style interface that uses iterators would be my first choice. However, this might cause problems with the pointer swapping used in merge_sort(). If there is some way to determine the data structure pointed to by an iterator, then we could declare a second version of the data structure and do iterator swapping. But, is this necessary? Which data structures should sort work for anyway?

#4091 Move binary search to algorithm.hpp and standardize 1.2 enhancement 01/23/12

We should move binary_search() to algorithm.hpp.

Get rid of the position parameter. Add lower_bound() and upper_bound(). Add versions of all three that take a comparator function object.

#4187 Add functions to mmap adjacency_list 1.2 enhancement 07/22/14

#4222 Modify the test harness to take optional command-line parameters 1.2 enhancement 06/04/15

Currently, the test harness in mtgl/mtgl_test.hpp only allows you to define required parameters. It would be useful to modify it to allow the user to define optional parameters as well.

#2423 SCC/topsort_prefix 1.2 defect 08/03/06

The strongly connected components algorithm typically finds one large scc per connected component on the Cray "fancy graph"s (power law). The other scc's are single vertex scc's. The "topsort prefix" and "topsort suffix" algorithms in TopSort?.cpp are designed to find these leading and trailing vertices not involved in any cycle. However, the number of vertices in the (topsort_prefix union topsort_suffix) doesn't match the number of singleton scc's. Any vertex not in a cycle should be a singleton scc and in (topsort_prefix union topsort_suffix).

#3319 induced subgraph using VMASK ignores disconnected vertices 1.2 defect 05/10/07

If the induced subgraph is called using a vertex mask where the vertex-mask contains only one vertex or a graph that also contains disconnected vertices, those singletons will not be included in the induced subgraph.

This occurs because the current VMASK method simply generates an EMASK and passes that to the induced_subgraph generator.

#2641 Exception handling 1.2 defect 09/04/06

MTGL doesn't currently do any "real" exception handling. In most cases we don't do a lot of checking for errors but instead let people shoot themselves in the foot. The reason for this is that exception handling / checking for errors has a HUGE potential for causing parallelization problems.

This is something that we should visit in the future, but it will probably require a lot of work and may not be supported very well. We should investigate using C++ exception handling as well as just checks for errors in the code.

jberry (2 matches)

Ticket Summary Component Milestone Type Created
#3927 vertex_betweenness infinite loop 1.2 defect 06/02/10

Out-of-bounds array reference if a bfs finds nothing.

#3919 duplicate adapter should be able to handle base adapters with no global edge iteration 1.2 task 04/14/10

The constructor iterates through all edges to build srcs and dests arrays. This could be done by iterating through adjacencies as well.

Note: See TracReports for help on using and creating reports.